大家好，我是小林。

騰訊面試風格是比較注重計算機基礎的，操作系統和網絡都會問的比較多，所以大家針對不同公司面試的時候，要有一個準備的側重點。

今天分析一位同學騰訊校招后端開發面經，足足面了 2 個小時，1 小時手撕算法，1 小時基礎拷打，最累一場面試，雖然面的很累，但是同學反饋面試官人很好，會一直引導。

這次面經的考點，我簡單羅列一下：

• Java：HashMap、垃圾回收算法、線程模型
• 操作系統：用戶態與內核態、進程調度、進程間通信、虛擬內存、進程&線程&協程
• 網絡：TCP三次握手、擁塞控制、https
• Redis：5 種數據結構
• MySQL：b+樹
• 算法：4 個算法題

Java

Java里面的線程和操作系統的線程一樣嗎？

Java 底層會調用 pthread_create 來創建線程，所以本質上 java 程序創建的線程，就是和操作系統線程是一樣的，是 1 對 1 的線程模型。

圖片

HashMap的底層原理？

圖片

存儲對象時，我們將K/V傳給put方法時，它調用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據當前bucket的占用情況自動調整容量(超過Load Facotr則resize為原來的2倍)。

獲取對象時，我們將K傳給get，它調用hashCode計算hash從而得到bucket位置，并進一步調用equals()方法確定鍵值對。如果發生碰撞的時候，Hashmap通過鏈表將產生碰撞沖突的元素組織起來，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。

如何判斷一個對象是無用對象？

判斷一個對象是否為無用對象（即不再被引用，并且可以被垃圾回收器回收）通常依賴于垃圾回收器的工作。Java的垃圾回收器使用了可達性分析算法來確定對象是否可達，如果一個對象不可達，則可以被判定為無用對象。

具體判斷一個對象是否為無用對象的方式如下：

1. 引用計數法（Reference Counting）：該方法通過在對象中維護一個引用計數器，每當有一個引用指向該對象時，計數器加1，當引用指向該對象的引用被釋放時，計數器減1。當計數器為0時，可以判定該對象為無用對象。然而，Java的垃圾回收器并不使用引用計數法，因為它無法解決循環引用的問題。
2. 可達性分析法（Reachability Analysis）：Java的垃圾回收器主要使用可達性分析法來判斷對象的可達性。該方法從一組稱為"GC Roots"的根對象開始，通過遍歷對象圖，標記所有從根對象可達的對象。那些未被標記的對象則被判定為無用對象。

假設HashMap里面存放100萬個對象，那么gc可能會有什么問題？

對象太多，使用可達性分析法去掃描這些無用對象的時候花費的時間比較長，gc花費的時間就會變長。

操作系統

用戶態和內核態有什么區別？

用戶態（User Mode）和內核態（Kernel Mode）是操作系統中的兩種特權級別，它們有以下幾個區別：

1. 訪問權限：在用戶態下，應用程序只能訪問受限的資源和執行受限的操作，例如用戶空間的內存、文件和設備。而在內核態下，操作系統具有完全的訪問權限，可以訪問系統的所有資源和執行所有操作。
2. CPU指令集：在用戶態下，CPU只能執行非特權指令，例如算術運算、邏輯運算等。而在內核態下，CPU可以執行特權指令，例如訪問設備、修改系統狀態等。
3. 中斷和異常處理：在用戶態下，當發生中斷或異常時，操作系統會進行中斷處理，將控制權轉移到內核態下的中斷處理程序中。而在內核態下，操作系統可以直接處理中斷和異常，并進行相應的處理操作。
4. 內存保護：在用戶態下，應用程序只能訪問自己的內存空間，無法訪問其他應用程序的內存空間和操作系統的內存空間。而在內核態下，操作系統可以訪問所有的內存空間，包括應用程序的內存空間。
5. 安全性：由于用戶態的應用程序受到限制，操作系統可以對其進行隔離和保護，防止惡意代碼對系統造成損害。而內核態下的操作系統具有更高的權限，需要對其進行嚴格的安全管理，以防止非法訪問和惡意操作。

進程調度算法說一下

01 先來先服務調度算法

最簡單的一個調度算法，就是非搶占式的先來先服務（*First Come First Serve, FCFS*）算法了。

FCFS 調度算法

顧名思義，先來后到，每次從就緒隊列選擇最先進入隊列的進程，然后一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業先運行了，那么后面的短作業等待的時間就會很長，不利于短作業。

FCFS 對長作業有利，適用于 CPU 繁忙型作業的系統，而不適用于 I/O 繁忙型作業的系統。

02 最短作業優先調度算法

最短作業優先（*Shortest Job First, SJF*）調度算法同樣也是顧名思義，它會優先選擇運行時間最短的進程來運行，這有助于提高系統的吞吐量。

SJF 調度算法

這顯然對長作業不利，很容易造成一種極端現象。

比如，一個長作業在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那么就會使得長作業不斷的往后推，周轉時間變長，致使長作業長期不會被運行。

03 高響應比優先調度算法

前面的「先來先服務調度算法」和「最短作業優先調度算法」都沒有很好的權衡短作業和長作業。

那么，高響應比優先 （*Highest Response Ratio Next, HRRN*）調度算法主要是權衡了短作業和長作業。

每次進行進程調度時，先計算「響應比優先級」，然后把「響應比優先級」最高的進程投入運行，「響應比優先級」的計算公式：

圖片

從上面的公式，可以發現：

• 如果兩個進程的「等待時間」相同時，「要求的服務時間」越短，「響應比」就越高，這樣短作業的進程容易被選中運行；
• 如果兩個進程「要求的服務時間」相同時，「等待時間」越長，「響應比」就越高，這就兼顧到了長作業進程，因為進程的響應比可以隨時間等待的增加而提高，當其等待時間足夠長時，其響應比便可以升到很高，從而獲得運行的機會；

04 時間片輪轉調度算法

最古老、最簡單、最公平且使用最廣的算法就是時間片輪轉（*Round Robin, RR*）調度算法。

RR 調度算法

每個進程被分配一個時間段，稱為時間片（*Quantum*），即允許該進程在該時間段中運行。

• 如果時間片用完，進程還在運行，那么將會把此進程從 CPU 釋放出來，并把 CPU 分配給另外一個進程；
• 如果該進程在時間片結束前阻塞或結束，則 CPU 立即進行切換；

另外，時間片的長度就是一個很關鍵的點：

• 如果時間片設得太短會導致過多的進程上下文切換，降低了 CPU 效率；
• 如果設得太長又可能引起對短作業進程的響應時間變長。將

一般來說，時間片設為 20ms~50ms 通常是一個比較合理的折中值。

05 最高優先級調度算法

前面的「時間片輪轉算法」做了個假設，即讓所有的進程同等重要，也不偏袒誰，大家的運行時間都一樣。

但是，對于多用戶計算機系統就有不同的看法了，它們希望調度是有優先級的，即希望調度程序能從就緒隊列中選擇最高優先級的進程進行運行，這稱為最高優先級（*Highest Priority First，HPF*）調度算法。

進程的優先級可以分為，靜態優先級和動態優先級：

• 靜態優先級：創建進程時候，就已經確定了優先級了，然后整個運行時間優先級都不會變化；
• 動態優先級：根據進程的動態變化調整優先級，比如如果進程運行時間增加，則降低其優先級，如果進程等待時間（就緒隊列的等待時間）增加，則升高其優先級，也就是隨著時間的推移增加等待進程的優先級。

該算法也有兩種處理優先級高的方法，非搶占式和搶占式：

• 非搶占式：當就緒隊列中出現優先級高的進程，運行完當前進程，再選擇優先級高的進程。
• 搶占式：當就緒隊列中出現優先級高的進程，當前進程掛起，調度優先級高的進程運行。

但是依然有缺點，可能會導致低優先級的進程永遠不會運行。

06 多級反饋隊列調度算法

多級反饋隊列（*Multilevel Feedback Queue*）調度算法是「時間片輪轉算法」和「最高優先級算法」的綜合和發展。

顧名思義：

• 「多級」表示有多個隊列，每個隊列優先級從高到低，同時優先級越高時間片越短。
• 「反饋」表示如果有新的進程加入優先級高的隊列時，立刻停止當前正在運行的進程，轉而去運行優先級高的隊列；

多級反饋隊列

來看看，它是如何工作的：

• 設置了多個隊列，賦予每個隊列不同的優先級，每個隊列優先級從高到低，同時優先級越高時間片越短；
• 新的進程會被放入到第一級隊列的末尾，按先來先服務的原則排隊等待被調度，如果在第一級隊列規定的時間片沒運行完成，則將其轉入到第二級隊列的末尾，以此類推，直至完成；
• 當較高優先級的隊列為空，才調度較低優先級的隊列中的進程運行。如果進程運行時，有新進程進入較高優先級的隊列，則停止當前運行的進程并將其移入到原隊列末尾，接著讓較高優先級的進程運行；

可以發現，對于短作業可能可以在第一級隊列很快被處理完。對于長作業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也變更長了，所以該算法很好的兼顧了長短作業，同時有較好的響應時間。

進程間的通信機制？

圖片

由于每個進程的用戶空間都是獨立的，不能相互訪問，這時就需要借助內核空間來實現進程間通信，原因很簡單，每個進程都是共享一個內核空間。

Linux 內核提供了不少進程間通信的方式，其中最簡單的方式就是管道，管道分為「匿名管道」和「命名管道」。

匿名管道顧名思義，它沒有名字標識，匿名管道是特殊文件只存在于內存，沒有存在于文件系統中，shell 命令中的「|」豎線就是匿名管道，通信的數據是無格式的流并且大小受限，通信的方式是單向的，數據只能在一個方向上流動，如果要雙向通信，需要創建兩個管道，再來匿名管道是只能用于存在父子關系的進程間通信，匿名管道的生命周期隨著進程創建而建立，隨著進程終止而消失。

命名管道突破了匿名管道只能在親緣關系進程間的通信限制，因為使用命名管道的前提，需要在文件系統創建一個類型為 p 的設備文件，那么毫無關系的進程就可以通過這個設備文件進行通信。另外，不管是匿名管道還是命名管道，進程寫入的數據都是緩存在內核中，另一個進程讀取數據時候自然也是從內核中獲取，同時通信數據都遵循先進先出原則，不支持 lseek 之類的文件定位操作。

消息隊列克服了管道通信的數據是無格式的字節流的問題，消息隊列實際上是保存在內核的「消息鏈表」，消息隊列的消息體是可以用戶自定義的數據類型，發送數據時，會被分成一個一個獨立的消息體，當然接收數據時，也要與發送方發送的消息體的數據類型保持一致，這樣才能保證讀取的數據是正確的。消息隊列通信的速度不是最及時的，畢竟每次數據的寫入和讀取都需要經過用戶態與內核態之間的拷貝過程。

共享內存可以解決消息隊列通信中用戶態與內核態之間數據拷貝過程帶來的開銷，它直接分配一個共享空間，每個進程都可以直接訪問，就像訪問進程自己的空間一樣快捷方便，不需要陷入內核態或者系統調用，大大提高了通信的速度，享有最快的進程間通信方式之名。但是便捷高效的共享內存通信，帶來新的問題，多進程競爭同個共享資源會造成數據的錯亂。

那么，就需要信號量來保護共享資源，以確保任何時刻只能有一個進程訪問共享資源，這種方式就是互斥訪問。信號量不僅可以實現訪問的互斥性，還可以實現進程間的同步，信號量其實是一個計數器，表示的是資源個數，其值可以通過兩個原子操作來控制，分別是 P 操作和 V 操作。

與信號量名字很相似的叫信號，它倆名字雖然相似，但功能一點兒都不一樣。信號是異步通信機制，信號可以在應用進程和內核之間直接交互，內核也可以利用信號來通知用戶空間的進程發生了哪些系統事件，信號事件的來源主要有硬件來源（如鍵盤 Cltr+C ）和軟件來源（如 kill 命令），一旦有信號發生，進程有三種方式響應信號 1. 執行默認操作、2. 捕捉信號、3. 忽略信號。有兩個信號是應用進程無法捕捉和忽略的，即 SIGKILL 和 SIGSTOP，這是為了方便我們能在任何時候結束或停止某個進程。

前面說到的通信機制，都是工作于同一臺主機，如果要與不同主機的進程間通信，那么就需要 Socket 通信了。Socket 實際上不僅用于不同的主機進程間通信，還可以用于本地主機進程間通信，可根據創建 Socket 的類型不同，分為三種常見的通信方式，一個是基于 TCP 協議的通信方式，一個是基于 UDP 協議的通信方式，一個是本地進程間通信方式。

IO多路復用，select、poll、epoll 的區別？

select 實現多路復用的方式是，將已連接的 Socket 都放到一個文件描述符集合，然后調用 select 函數將文件描述符集合拷貝到內核里，讓內核來檢查是否有網絡事件產生，檢查的方式很粗暴，就是通過遍歷文件描述符集合的方式，當檢查到有事件產生后，將此 Socket 標記為可讀或可寫， 接著再把整個文件描述符集合拷貝回用戶態里，然后用戶態還需要再通過遍歷的方法找到可讀或可寫的 Socket，然后再對其處理。

所以，對于 select 這種方式，需要進行 2 次「遍歷」文件描述符集合，一次是在內核態里，一個次是在用戶態里 ，而且還會發生 2 次「拷貝」文件描述符集合，先從用戶空間傳入內核空間，由內核修改后，再傳出到用戶空間中。

select 使用固定長度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的個數是有限制的，在 Linux 系統中，由內核中的 FD_SETSIZE 限制， 默認最大值為 1024，只能監聽 0~1023 的文件描述符。

poll 不再用 BitsMap 來存儲所關注的文件描述符，取而代之用動態數組，以鏈表形式來組織，突破了 select 的文件描述符個數限制，當然還會受到系統文件描述符限制。

但是 poll 和 select 并沒有太大的本質區別，都是使用「線性結構」存儲進程關注的 Socket 集合，因此都需要遍歷文件描述符集合來找到可讀或可寫的 Socket，時間復雜度為 O(n)，而且也需要在用戶態與內核態之間拷貝文件描述符集合，這種方式隨著并發數上來，性能的損耗會呈指數級增長。

epoll 通過兩個方面，很好解決了 select/poll 的問題。

• 第一點，epoll 在內核里使用紅黑樹來跟蹤進程所有待檢測的文件描述字，把需要監控的 socket 通過 epoll_ctl() 函數加入內核中的紅黑樹里，紅黑樹是個高效的數據結構，增刪改一般時間復雜度是 O(logn)。而 select/poll 內核里沒有類似 epoll 紅黑樹這種保存所有待檢測的 socket 的數據結構，所以 select/poll 每次操作時都傳入整個 socket 集合給內核，而 epoll 因為在內核維護了紅黑樹，可以保存所有待檢測的 socket ，所以只需要傳入一個待檢測的 socket，減少了內核和用戶空間大量的數據拷貝和內存分配。
• 第二點， epoll 使用事件驅動的機制，內核里維護了一個鏈表來記錄就緒事件，當某個 socket 有事件發生時，通過回調函數內核會將其加入到這個就緒事件列表中，當用戶調用 epoll_wait() 函數時，只會返回有事件發生的文件描述符的個數，不需要像 select/poll 那樣輪詢掃描整個 socket 集合，大大提高了檢測的效率。

從下圖你可以看到 epoll 相關的接口作用：

圖片

epoll 的方式即使監聽的 Socket 數量越多的時候，效率不會大幅度降低，能夠同時監聽的 Socket 的數目也非常的多了，上限就為系統定義的進程打開的最大文件描述符個數。因而，epoll 被稱為解決 C10K 問題的利器。

為什么操作系統要設計虛擬內存？

如果沒有虛擬內存，程序直接操作物理內存的話。

圖片

在這種情況下，要想在內存中同時運行兩個程序是不可能的。如果第一個程序在 2000 的位置寫入一個新的值，將會擦掉第二個程序存放在相同位置上的所有內容，所以同時運行兩個程序是根本行不通的，這兩個程序會立刻崩潰。

這里關鍵的問題是這兩個程序都引用了絕對物理地址，而這正是我們最需要避免的。

進程的中間層

我們可以把進程所使用的地址「隔離」開來，即讓操作系統為每個進程分配獨立的一套「虛擬地址」，人人都有，大家自己玩自己的地址就行，互不干涉。但是有個前提每個進程都不能訪問物理地址，至于虛擬地址最終怎么落到物理內存里，對進程來說是透明的，操作系統已經把這些都安排的明明白白了。

操作系統會提供一種機制，將不同進程的虛擬地址和不同內存的物理地址映射起來。如果程序要訪問虛擬地址的時候，由操作系統轉換成不同的物理地址，這樣不同的進程運行的時候，寫入的是不同的物理地址，這樣就不會沖突了。

進程和線程的區別？

• 資源分配：進程是操作系統中的一個執行實體，擁有獨立的地址空間、文件描述符、打開的文件等資源。每個進程都被分配了獨立的系統資源。而線程是進程中的一個執行單元，多個線程共享同一個進程的地址空間和其他資源，包括文件描述符、打開的文件等。
• 調度和切換：進程的調度是由操作系統內核進行的，切換進程需要進行上下文切換，涉及用戶態和內核態之間的切換，開銷相對較大。而線程的調度是在用戶程序中完成，切換線程可以在用戶態下快速切換，減少了系統調用的開銷。
• 并發性：進程是獨立的執行實體，不同進程之間通過進程間通信（IPC）來進行數據交換和共享。進程間通信的方式包括管道、信號量、共享內存等。而線程是在同一個進程中執行的，多個線程之間共享同一進程的資源，可以通過共享內存的方式進行數據交換和共享。

進程的地址空間里面有什么？

虛擬內存空間劃分

通過這張圖你可以看到，用戶空間內存，從低到高分別是 6 種不同的內存段：

• 代碼段，包括二進制可執行代碼；
• 數據段，包括已初始化的靜態常量和全局變量；
• BSS 段，包括未初始化的靜態變量和全局變量；
• 堆段，包括動態分配的內存，從低地址開始向上增長；
• 文件映射段，包括動態庫、共享內存等；
• 棧段，包括局部變量和函數調用的上下文等。棧的大小是固定的，一般是 8 MB。當然系統也提供了參數，以便我們自定義大小；

上圖中的內存布局可以看到，代碼段下面還有一段內存空間的（灰色部分），這一塊區域是「保留區」，之所以要有保留區這是因為在大多數的系統里，我們認為比較小數值的地址不是一個合法地址，例如，我們通常在 C 的代碼里會將無效的指針賦值為 NULL。因此，這里會出現一段不可訪問的內存保留區，防止程序因為出現 bug，導致讀或寫了一些小內存地址的數據，而使得程序跑飛。

在這 7 個內存段中，堆和文件映射段的內存是動態分配的。比如說，使用 C 標準庫的 malloc() 或者 mmap() ，就可以分別在堆和文件映射段動態分配內存。

線程切換要保存哪些上下文？

• 寄存器上下文：線程切換時需要保存和恢復線程所使用的寄存器的值，以便切換后能夠繼續執行。常見的寄存器包括通用寄存器（如EAX、EBX、ECX等）、指令指針寄存器（如EIP）、堆棧指針寄存器（如ESP）等。
• 棧：線程的棧用于保存局部變量、函數調用信息等。在線程切換時，需要保存和恢復當前線程的棧指針，以及相應的棧幀信息。
• 線程上下文信息：線程切換時，需要保存和恢復與線程相關的其他上下文信息，如線程狀態、調度優先級等。

協程和線程什么區別？

• 調度方式：線程的調度是由操作系統內核進行的，而協程的調度是由程序員或者特定的協程調度器進行的。線程的調度是由操作系統內核控制，切換線程需要進行系統調用，涉及用戶態和內核態之間的切換，相對較為耗時。而協程的調度是在用戶程序中完成，切換協程可以在用戶態下快速切換，減少了系統調用的開銷。
• 并發性：線程是操作系統提供的輕量級進程，多個線程之間可以并發執行，但在多核處理器上，線程的并發性是通過操作系統的線程調度實現的。而協程是在單個線程中執行的，多個協程之間通過協程調度器進行切換，實現了更細粒度的并發性。
• 內存消耗：線程的創建和銷毀需要操作系統進行一系列的資源分配和回收，包括線程的棧空間和線程控制塊等。而協程在單個線程中執行，不需要額外的系統資源分配，只需要協程調度器保存和恢復協程的上下文。
• 同步方式：線程之間的通信和同步需要使用鎖、條件變量等機制來進行，這些機制需要進行加鎖和解鎖的操作，容易引發死鎖和競態條件等問題。而協程可以使用更輕量級的方式進行通信和同步，如使用通道（Channel）來實現協程之間的消息傳遞。

網絡

講一下TCP三次握手的過程

• TCP 是面向連接的協議，所以使用 TCP 前必須先建立連接，而建立連接是通過三次握手來進行的。三次握手的過程如下圖：

圖片

• TCP 三次握手

圖片

• 第一個報文 —— SYN 報文

圖片

• 第二個報文 —— SYN + ACK 報文

圖片

• 第三個報文 —— ACK 報文一旦完成三次握手，雙方都處于 ESTABLISHED 狀態，此時連接就已建立完成，客戶端和服務端就可以相互發送數據了。

• 客戶端收到服務端報文后，還要向服務端回應最后一個應答報文，首先該應答報文 TCP 首部 ACK 標志位置為 1 ，其次「確認應答號」字段填入 server_isn + 1 ，最后把報文發送給服務端，這次報文可以攜帶客戶到服務端的數據，之后客戶端處于 ESTABLISHED 狀態。
• 服務端收到客戶端的應答報文后，也進入 ESTABLISHED 狀態。
• 服務端收到客戶端的 SYN 報文后，首先服務端也隨機初始化自己的序號（server_isn），將此序號填入 TCP 首部的「序號」字段中，其次把 TCP 首部的「確認應答號」字段填入 client_isn + 1, 接著把 SYN 和 ACK 標志位置為 1。最后把該報文發給客戶端，該報文也不包含應用層數據，之后服務端處于 SYN-RCVD 狀態。
• 客戶端會隨機初始化序號（client_isn），將此序號置于 TCP 首部的「序號」字段中，同時把 SYN 標志位置為 1，表示 SYN 報文。接著把第一個 SYN 報文發送給服務端，表示向服務端發起連接，該報文不包含應用層數據，之后客戶端處于 SYN-SENT 狀態。
• 一開始，客戶端和服務端都處于 CLOSE 狀態。先是服務端主動監聽某個端口，處于 LISTEN 狀態

TCP擁塞控制具體過程？

擁塞控制主要是四個算法：

• 慢啟動
• 擁塞避免
• 擁塞發生
• 快速恢復

一、慢啟動

慢啟動的算法記住一個規則就行：當發送方每收到一個 ACK，擁塞窗口 cwnd 的大小就會加 1。

這里假定擁塞窗口 cwnd 和發送窗口 swnd 相等，下面舉個栗子：

• 連接建立完成后，一開始初始化 cwnd = 1，表示可以傳一個 MSS 大小的數據。
• 當收到一個 ACK 確認應答后，cwnd 增加 1，于是一次能夠發送 2 個
• 當收到 2 個的 ACK 確認應答后， cwnd 增加 2，于是就可以比之前多發2 個，所以這一次能夠發送 4 個
• 當這 4 個的 ACK 確認到來的時候，每個確認 cwnd 增加 1， 4 個確認 cwnd 增加 4，于是就可以比之前多發 4 個，所以這一次能夠發送 8 個。

慢啟動算法的變化過程如下圖：

慢啟動算法

可以看出慢啟動算法，發包的個數是指數性的增長。

那慢啟動漲到什么時候是個頭呢？

有一個叫慢啟動門限 ssthresh （slow start threshold）狀態變量。

• 當 cwnd < ssthresh 時，使用慢啟動算法。
• 當 cwnd >= ssthresh 時，就會使用「擁塞避免算法」。

二、擁塞避免算法

前面說道，當擁塞窗口 cwnd 「超過」慢啟動門限 ssthresh 就會進入擁塞避免算法。

一般來說 ssthresh 的大小是 65535 字節。那么進入擁塞避免算法后，它的規則是：**每當收到一個 ACK 時，cwnd 增加 1/cwnd。*接上前面的慢啟動的栗子，現假定 ssthresh 為 8：

• 當 8 個 ACK 應答確認到來時，每個確認增加 1/8，8 個 ACK 確認 cwnd 一共增加 1，于是這一次能夠發送 9 個 MSS 大小的數據，變成了線性增長。

擁塞避免算法的變化過程如下圖：

擁塞避免

所以，我們可以發現，擁塞避免算法就是將原本慢啟動算法的指數增長變成了線性增長，還是增長階段，但是增長速度緩慢了一些。

就這么一直增長著后，網絡就會慢慢進入了擁塞的狀況了，于是就會出現丟包現象，這時就需要對丟失的數據包進行重傳。

當觸發了重傳機制，也就進入了「擁塞發生算法」。

三、擁塞發生

當網絡出現擁塞，也就是會發生數據包重傳，重傳機制主要有兩種：

• 超時重傳
• 快速重傳

這兩種使用的擁塞發送算法是不同的，接下來分別來說說。

3.1 當發生了「超時重傳」，則就會使用擁塞發生算法。

這個時候，ssthresh 和 cwnd 的值會發生變化：

• ssthresh 設為 cwnd/2，
• cwnd 重置為 1 （是恢復為 cwnd 初始化值，我這里假定 cwnd 初始化值 1）

擁塞發生算法的變化如下圖：

擁塞發送 —— 超時重傳

接著，就重新開始慢啟動，慢啟動是會突然減少數據流的。這真是一旦「超時重傳」，馬上回到解放前。但是這種方式太激進了，反應也很強烈，會造成網絡卡頓。就好像本來在秋名山高速漂移著，突然來個緊急剎車，輪胎受得了嗎。。。

3.2發生快速重傳的擁塞發生算法

還有更好的方式，前面我們講過「快速重傳算法」。當接收方發現丟了一個中間包的時候，發送三次前一個包的 ACK，于是發送端就會快速地重傳，不必等待超時再重傳。

TCP 認為這種情況不嚴重，因為大部分沒丟，只丟了一小部分，則 ssthresh 和 cwnd 變化如下：

• cwnd = cwnd/2 ，也就是設置為原來的一半;
• ssthresh = cwnd;
• 進入快速恢復算法

四、快速恢復

快速重傳和快速恢復算法一般同時使用，快速恢復算法是認為，你還能收到 3 個重復 ACK 說明網絡也不那么糟糕，所以沒有必要像 RTO 超時那么強烈。

正如前面所說，進入快速恢復之前，cwnd 和 ssthresh 已被更新了：

• cwnd = cwnd/2 ，也就是設置為原來的一半;
• ssthresh = cwnd;

然后，進入快速恢復算法如下：

• 擁塞窗口 cwnd = ssthresh + 3 （ 3 的意思是確認有 3 個數據包被收到了）；
• 重傳丟失的數據包；
• 如果再收到重復的 ACK，那么 cwnd 增加 1；
• 如果收到新數據的 ACK 后，把 cwnd 設置為第一步中的 ssthresh 的值，原因是該 ACK 確認了新的數據，說明從 duplicated ACK 時的數據都已收到，該恢復過程已經結束，可以回到恢復之前的狀態了，也即再次進入擁塞避免狀態；

快速恢復算法的變化過程如下圖：

快速重傳和快速恢復

也就是沒有像「超時重傳」一夜回到解放前，而是還在比較高的值，后續呈線性增長。

http與https的區別？

• HTTP 是超文本傳輸協議，信息是明文傳輸，存在安全風險的問題。HTTPS 則解決 HTTP 不安全的缺陷，在 TCP 和 HTTP 網絡層之間加入了 SSL/TLS 安全協議，使得報文能夠加密傳輸。
• HTTP 連接建立相對簡單， TCP 三次握手之后便可進行 HTTP 的報文傳輸。而 HTTPS 在 TCP 三次握手之后，還需進行 SSL/TLS 的握手過程，才可進入加密報文傳輸。
• 兩者的默認端口不一樣，HTTP 默認端口號是 80，HTTPS 默認端口號是 443。
• HTTPS 協議需要向 CA（證書權威機構）申請數字證書，來保證服務器的身份是可信的。

https加密的過程？

SSL/TLS 協議基本流程：

• 客戶端向服務器索要并驗證服務器的公鑰。
• 雙方協商生產「會話秘鑰」。
• 雙方采用「會話秘鑰」進行加密通信。

前兩步也就是 SSL/TLS 的建立過程，也就是 TLS 握手階段。

基于 RSA 算法的 TLS 握手過程比較容易理解，所以這里先用這個給大家展示 TLS 握手過程，如下圖：

HTTPS 連接建立過程

TLS 協議建立的詳細流程：

1.ClientHello

首先，由客戶端向服務器發起加密通信請求，也就是 ClientHello 請求。

在這一步，客戶端主要向服務器發送以下信息：

（1）客戶端支持的 TLS 協議版本，如 TLS 1.2 版本。

（2）客戶端生產的隨機數（Client Random），后面用于生成「會話秘鑰」條件之一。

（3）客戶端支持的密碼套件列表，如 RSA 加密算法。

2.SeverHello

服務器收到客戶端請求后，向客戶端發出響應，也就是 SeverHello。服務器回應的內容有如下內容：

（1）確認 TLS 協議版本，如果瀏覽器不支持，則關閉加密通信。

（2）服務器生產的隨機數（Server Random），也是后面用于生產「會話秘鑰」條件之一。

（3）確認的密碼套件列表，如 RSA 加密算法。

（4）服務器的數字證書。

3.客戶端回應

客戶端收到服務器的回應之后，首先通過瀏覽器或者操作系統中的 CA 公鑰，確認服務器的數字證書的真實性。

如果證書沒有問題，客戶端會從數字證書中取出服務器的公鑰，然后使用它加密報文，向服務器發送如下信息：

（1）一個隨機數（pre-master key）。該隨機數會被服務器公鑰加密。

（2）加密通信算法改變通知，表示隨后的信息都將用「會話秘鑰」加密通信。

（3）客戶端握手結束通知，表示客戶端的握手階段已經結束。這一項同時把之前所有內容的發生的數據做個摘要，用來供服務端校驗。

上面第一項的隨機數是整個握手階段的第三個隨機數，會發給服務端，所以這個隨機數客戶端和服務端都是一樣的。

服務器和客戶端有了這三個隨機數（Client Random、Server Random、pre-master key），接著就用雙方協商的加密算法，各自生成本次通信的「會話秘鑰」。

4.服務器的最后回應

服務器收到客戶端的第三個隨機數（pre-master key）之后，通過協商的加密算法，計算出本次通信的「會話秘鑰」。

然后，向客戶端發送最后的信息：

（1）加密通信算法改變通知，表示隨后的信息都將用「會話秘鑰」加密通信。

（2）服務器握手結束通知，表示服務器的握手階段已經結束。這一項同時把之前所有內容的發生的數據做個摘要，用來供客戶端校驗。

至此，整個 TLS 的握手階段全部結束。接下來，客戶端與服務器進入加密通信，就完全是使用普通的 HTTP 協議，只不過用「會話秘鑰」加密內容。

Redis

Redis常用數據結構？

Redis 提供了豐富的數據類型，常見的有五種數據類型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

圖片

隨著 Redis 版本的更新，后面又支持了四種數據類型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五種數據類型的應用場景：

• String 類型的應用場景：緩存對象、常規計數、分布式鎖、共享 session 信息等。
• List 類型的應用場景：消息隊列（但是有兩個問題：1. 生產者需要自行實現全局唯一 ID；2. 不能以消費組形式消費數據）等。
• Hash 類型：緩存對象、購物車等。
• Set 類型：聚合計算（并集、交集、差集）場景，比如點贊、共同關注、抽獎活動等。
• Zset 類型：排序場景，比如排行榜、電話和姓名排序等。

Redis 后續版本又支持四種數據類型，它們的應用場景如下：

• BitMap（2.2 版新增）：二值狀態統計的場景，比如簽到、判斷用戶登陸狀態、連續簽到用戶總數等；
• HyperLogLog（2.8 版新增）：海量數據基數統計的場景，比如百萬級網頁 UV 計數等；
• GEO（3.2 版新增）：存儲地理位置信息的場景，比如滴滴叫車；
• Stream（5.0 版新增）：消息隊列，相比于基于 List 類型實現的消息隊列，有這兩個特有的特性：自動生成全局唯一消息ID，支持以消費組形式消費數據。

Zset底層數據結構？

Zset 類型的底層數據結構是由壓縮列表或跳表實現的：

• 如果有序集合的元素個數小于 128 個，并且每個元素的值小于 64 字節時，Redis 會使用壓縮列表作為 Zset 類型的底層數據結構；
• 如果有序集合的元素不滿足上面的條件，Redis 會使用跳表作為 Zset 類型的底層數據結構；

在 Redis 7.0 中，壓縮列表數據結構已經廢棄了，交由 listpack 數據結構來實現了。

MySQL

B+樹有什么特點？

B+ 樹就是對 B 樹做了一個升級，MySQL 中索引的數據結構就是采用了 B+ 樹，B+ 樹結構如下圖：

圖片

B+ 樹與 B 樹差異的點，主要是以下這幾點：

• 葉子節點（最底部的節點）才會存放實際數據（索引+記錄），非葉子節點只會存放索引；
• 所有索引都會在葉子節點出現，葉子節點之間構成一個有序鏈表；
• 非葉子節點的索引也會同時存在在子節點中，并且是在子節點中所有索引的最大（或最小）。
• 非葉子節點中有多少個子節點，就有多少個索引；

MySQL 默認的存儲引擎 InnoDB 采用的是 B+ 作為索引的數據結構，原因有：

• B+ 樹的非葉子節點不存放實際的記錄數據，僅存放索引，因此數據量相同的情況下，相比存儲即存索引又存記錄的 B 樹，B+樹的非葉子節點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節點的磁盤 I/O次數會更少。
• B+ 樹有大量的冗余節點（所有非葉子節點都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，比如刪除根節點的時候，不會像 B 樹那樣會發生復雜的樹的變化；
• B+ 樹葉子節點之間用鏈表連接了起來，有利于范圍查詢，而 B 樹要實現范圍查詢，因此只能通過樹的遍歷來完成范圍查詢，這會涉及多個節點的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。

怎么做能使得查詢不需要3次io？

把節點緩存在內存中，這樣下次查詢數據的時候，直接在內存進行索引查找就可以了。

智力題

• 1000瓶毒藥里面只有1瓶是有毒的，問需要多少只老鼠才能在24小時后試出那瓶有毒。

參考：這是一個經典的二分法或者說是二進制的問題。對于1000瓶藥，可以用二進制表示為從0000000000（0）到1111101000（1000）的范圍，總共需要10位。因此，需要10只老鼠來試出哪一瓶是有毒的。具體的實施方案就是，將每一瓶藥對應到一個二進制的數字，然后讓對應到1的位置的老鼠去試那一瓶藥。這樣，24小時后，只需要看哪些老鼠死了，就能確定哪一瓶藥是有毒的。

算法

• 二分查找（2 題）
• 洗牌算法
• 最大子數組和