大家好，我是小林。

騰訊面試風(fēng)格是比較注重計(jì)算機(jī)基礎(chǔ)的，操作系統(tǒng)和網(wǎng)絡(luò)都會(huì)問的比較多，所以大家針對(duì)不同公司面試的時(shí)候，要有一個(gè)準(zhǔn)備的側(cè)重點(diǎn)。

今天分析一位同學(xué)騰訊校招后端開發(fā)面經(jīng)，足足面了 2 個(gè)小時(shí)，1 小時(shí)手撕算法，1 小時(shí)基礎(chǔ)拷打，最累一場(chǎng)面試，雖然面的很累，但是同學(xué)反饋面試官人很好，會(huì)一直引導(dǎo)。

這次面經(jīng)的考點(diǎn)，我簡(jiǎn)單羅列一下：

• Java：HashMap、垃圾回收算法、線程模型
• 操作系統(tǒng)：用戶態(tài)與內(nèi)核態(tài)、進(jìn)程調(diào)度、進(jìn)程間通信、虛擬內(nèi)存、進(jìn)程&線程&協(xié)程
• 網(wǎng)絡(luò)：TCP三次握手、擁塞控制、https
• Redis：5 種數(shù)據(jù)結(jié)構(gòu)
• MySQL：b+樹
• 算法：4 個(gè)算法題

Java

Java里面的線程和操作系統(tǒng)的線程一樣嗎？

Java 底層會(huì)調(diào)用 pthread_create 來創(chuàng)建線程，所以本質(zhì)上 java 程序創(chuàng)建的線程，就是和操作系統(tǒng)線程是一樣的，是 1 對(duì) 1 的線程模型。

圖片

HashMap的底層原理？

圖片

存儲(chǔ)對(duì)象時(shí)，我們將K/V傳給put方法時(shí)，它調(diào)用hashCode計(jì)算hash從而得到bucket位置，進(jìn)一步存儲(chǔ)，HashMap會(huì)根據(jù)當(dāng)前bucket的占用情況自動(dòng)調(diào)整容量(超過Load Facotr則resize為原來的2倍)。

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

如何判斷一個(gè)對(duì)象是無用對(duì)象？

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

具體判斷一個(gè)對(duì)象是否為無用對(duì)象的方式如下：

1. 引用計(jì)數(shù)法（Reference Counting）：該方法通過在對(duì)象中維護(hù)一個(gè)引用計(jì)數(shù)器，每當(dāng)有一個(gè)引用指向該對(duì)象時(shí)，計(jì)數(shù)器加1，當(dāng)引用指向該對(duì)象的引用被釋放時(shí)，計(jì)數(shù)器減1。當(dāng)計(jì)數(shù)器為0時(shí)，可以判定該對(duì)象為無用對(duì)象。然而，Java的垃圾回收器并不使用引用計(jì)數(shù)法，因?yàn)樗鼰o法解決循環(huán)引用的問題。
2. 可達(dá)性分析法（Reachability Analysis）：Java的垃圾回收器主要使用可達(dá)性分析法來判斷對(duì)象的可達(dá)性。該方法從一組稱為"GC Roots"的根對(duì)象開始，通過遍歷對(duì)象圖，標(biāo)記所有從根對(duì)象可達(dá)的對(duì)象。那些未被標(biāo)記的對(duì)象則被判定為無用對(duì)象。

假設(shè)HashMap里面存放100萬個(gè)對(duì)象，那么gc可能會(huì)有什么問題？

對(duì)象太多，使用可達(dá)性分析法去掃描這些無用對(duì)象的時(shí)候花費(fèi)的時(shí)間比較長(zhǎng)，gc花費(fèi)的時(shí)間就會(huì)變長(zhǎng)。

操作系統(tǒng)

用戶態(tài)和內(nèi)核態(tài)有什么區(qū)別？

用戶態(tài)（User Mode）和內(nèi)核態(tài)（Kernel Mode）是操作系統(tǒng)中的兩種特權(quán)級(jí)別，它們有以下幾個(gè)區(qū)別：

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

進(jìn)程調(diào)度算法說一下

01 先來先服務(wù)調(diào)度算法

最簡(jiǎn)單的一個(gè)調(diào)度算法，就是非搶占式的先來先服務(wù)（*First Come First Serve, FCFS*）算法了。

FCFS 調(diào)度算法

顧名思義，先來后到，每次從就緒隊(duì)列選擇最先進(jìn)入隊(duì)列的進(jìn)程，然后一直運(yùn)行，直到進(jìn)程退出或被阻塞，才會(huì)繼續(xù)從隊(duì)列中選擇第一個(gè)進(jìn)程接著運(yùn)行。

這似乎很公平，但是當(dāng)一個(gè)長(zhǎng)作業(yè)先運(yùn)行了，那么后面的短作業(yè)等待的時(shí)間就會(huì)很長(zhǎng)，不利于短作業(yè)。

FCFS 對(duì)長(zhǎng)作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

02 最短作業(yè)優(yōu)先調(diào)度算法

最短作業(yè)優(yōu)先（*Shortest Job First, SJF*）調(diào)度算法同樣也是顧名思義，它會(huì)優(yōu)先選擇運(yùn)行時(shí)間最短的進(jìn)程來運(yùn)行，這有助于提高系統(tǒng)的吞吐量。

SJF 調(diào)度算法

這顯然對(duì)長(zhǎng)作業(yè)不利，很容易造成一種極端現(xiàn)象。

比如，一個(gè)長(zhǎng)作業(yè)在就緒隊(duì)列等待運(yùn)行，而這個(gè)就緒隊(duì)列有非常多的短作業(yè)，那么就會(huì)使得長(zhǎng)作業(yè)不斷的往后推，周轉(zhuǎn)時(shí)間變長(zhǎng)，致使長(zhǎng)作業(yè)長(zhǎng)期不會(huì)被運(yùn)行。

03 高響應(yīng)比優(yōu)先調(diào)度算法

前面的「先來先服務(wù)調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒有很好的權(quán)衡短作業(yè)和長(zhǎng)作業(yè)。

那么，高響應(yīng)比優(yōu)先 （*Highest Response Ratio Next, HRRN*）調(diào)度算法主要是權(quán)衡了短作業(yè)和長(zhǎng)作業(yè)。

每次進(jìn)行進(jìn)程調(diào)度時(shí)，先計(jì)算「響應(yīng)比優(yōu)先級(jí)」，然后把「響應(yīng)比優(yōu)先級(jí)」最高的進(jìn)程投入運(yùn)行，「響應(yīng)比優(yōu)先級(jí)」的計(jì)算公式：

圖片

從上面的公式，可以發(fā)現(xiàn)：

• 如果兩個(gè)進(jìn)程的「等待時(shí)間」相同時(shí)，「要求的服務(wù)時(shí)間」越短，「響應(yīng)比」就越高，這樣短作業(yè)的進(jìn)程容易被選中運(yùn)行；
• 如果兩個(gè)進(jìn)程「要求的服務(wù)時(shí)間」相同時(shí)，「等待時(shí)間」越長(zhǎng)，「響應(yīng)比」就越高，這就兼顧到了長(zhǎng)作業(yè)進(jìn)程，因?yàn)檫M(jìn)程的響應(yīng)比可以隨時(shí)間等待的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其響應(yīng)比便可以升到很高，從而獲得運(yùn)行的機(jī)會(huì)；

04 時(shí)間片輪轉(zhuǎn)調(diào)度算法

最古老、最簡(jiǎn)單、最公平且使用最廣的算法就是時(shí)間片輪轉(zhuǎn)（*Round Robin, RR*）調(diào)度算法。

RR 調(diào)度算法

每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱為時(shí)間片（*Quantum*），即允許該進(jìn)程在該時(shí)間段中運(yùn)行。

• 如果時(shí)間片用完，進(jìn)程還在運(yùn)行，那么將會(huì)把此進(jìn)程從 CPU 釋放出來，并把 CPU 分配給另外一個(gè)進(jìn)程；
• 如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換；

另外，時(shí)間片的長(zhǎng)度就是一個(gè)很關(guān)鍵的點(diǎn)：

• 如果時(shí)間片設(shè)得太短會(huì)導(dǎo)致過多的進(jìn)程上下文切換，降低了 CPU 效率；
• 如果設(shè)得太長(zhǎng)又可能引起對(duì)短作業(yè)進(jìn)程的響應(yīng)時(shí)間變長(zhǎng)。將

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

05 最高優(yōu)先級(jí)調(diào)度算法

前面的「時(shí)間片輪轉(zhuǎn)算法」做了個(gè)假設(shè)，即讓所有的進(jìn)程同等重要，也不偏袒誰，大家的運(yùn)行時(shí)間都一樣。

但是，對(duì)于多用戶計(jì)算機(jī)系統(tǒng)就有不同的看法了，它們希望調(diào)度是有優(yōu)先級(jí)的，即希望調(diào)度程序能從就緒隊(duì)列中選擇最高優(yōu)先級(jí)的進(jìn)程進(jìn)行運(yùn)行，這稱為最高優(yōu)先級(jí)（*Highest Priority First，HPF*）調(diào)度算法。

進(jìn)程的優(yōu)先級(jí)可以分為，靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)：

• 靜態(tài)優(yōu)先級(jí)：創(chuàng)建進(jìn)程時(shí)候，就已經(jīng)確定了優(yōu)先級(jí)了，然后整個(gè)運(yùn)行時(shí)間優(yōu)先級(jí)都不會(huì)變化；
• 動(dòng)態(tài)優(yōu)先級(jí)：根據(jù)進(jìn)程的動(dòng)態(tài)變化調(diào)整優(yōu)先級(jí)，比如如果進(jìn)程運(yùn)行時(shí)間增加，則降低其優(yōu)先級(jí)，如果進(jìn)程等待時(shí)間（就緒隊(duì)列的等待時(shí)間）增加，則升高其優(yōu)先級(jí)，也就是隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。

該算法也有兩種處理優(yōu)先級(jí)高的方法，非搶占式和搶占式：

• 非搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，運(yùn)行完當(dāng)前進(jìn)程，再選擇優(yōu)先級(jí)高的進(jìn)程。
• 搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級(jí)高的進(jìn)程，當(dāng)前進(jìn)程掛起，調(diào)度優(yōu)先級(jí)高的進(jìn)程運(yùn)行。

但是依然有缺點(diǎn)，可能會(huì)導(dǎo)致低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)不會(huì)運(yùn)行。

06 多級(jí)反饋隊(duì)列調(diào)度算法

多級(jí)反饋隊(duì)列（*Multilevel Feedback Queue*）調(diào)度算法是「時(shí)間片輪轉(zhuǎn)算法」和「最高優(yōu)先級(jí)算法」的綜合和發(fā)展。

顧名思義：

• 「多級(jí)」表示有多個(gè)隊(duì)列，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短。
• 「反饋」表示如果有新的進(jìn)程加入優(yōu)先級(jí)高的隊(duì)列時(shí)，立刻停止當(dāng)前正在運(yùn)行的進(jìn)程，轉(zhuǎn)而去運(yùn)行優(yōu)先級(jí)高的隊(duì)列；

多級(jí)反饋隊(duì)列

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

• 設(shè)置了多個(gè)隊(duì)列，賦予每個(gè)隊(duì)列不同的優(yōu)先級(jí)，每個(gè)隊(duì)列優(yōu)先級(jí)從高到低，同時(shí)優(yōu)先級(jí)越高時(shí)間片越短；
• 新的進(jìn)程會(huì)被放入到第一級(jí)隊(duì)列的末尾，按先來先服務(wù)的原則排隊(duì)等待被調(diào)度，如果在第一級(jí)隊(duì)列規(guī)定的時(shí)間片沒運(yùn)行完成，則將其轉(zhuǎn)入到第二級(jí)隊(duì)列的末尾，以此類推，直至完成；
• 當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程運(yùn)行。如果進(jìn)程運(yùn)行時(shí)，有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則停止當(dāng)前運(yùn)行的進(jìn)程并將其移入到原隊(duì)列末尾，接著讓較高優(yōu)先級(jí)的進(jìn)程運(yùn)行；

可以發(fā)現(xiàn)，對(duì)于短作業(yè)可能可以在第一級(jí)隊(duì)列很快被處理完。對(duì)于長(zhǎng)作業(yè)，如果在第一級(jí)隊(duì)列處理不完，可以移入下次隊(duì)列等待被執(zhí)行，雖然等待的時(shí)間變長(zhǎng)了，但是運(yùn)行時(shí)間也變更長(zhǎng)了，所以該算法很好的兼顧了長(zhǎng)短作業(yè)，同時(shí)有較好的響應(yīng)時(shí)間。

進(jìn)程間的通信機(jī)制？

圖片

由于每個(gè)進(jìn)程的用戶空間都是獨(dú)立的，不能相互訪問，這時(shí)就需要借助內(nèi)核空間來實(shí)現(xiàn)進(jìn)程間通信，原因很簡(jiǎn)單，每個(gè)進(jìn)程都是共享一個(gè)內(nèi)核空間。

Linux 內(nèi)核提供了不少進(jìn)程間通信的方式，其中最簡(jiǎn)單的方式就是管道，管道分為「匿名管道」和「命名管道」。

匿名管道顧名思義，它沒有名字標(biāo)識(shí)，匿名管道是特殊文件只存在于內(nèi)存，沒有存在于文件系統(tǒng)中，shell 命令中的「|」豎線就是匿名管道，通信的數(shù)據(jù)是無格式的流并且大小受限，通信的方式是單向的，數(shù)據(jù)只能在一個(gè)方向上流動(dòng)，如果要雙向通信，需要?jiǎng)?chuàng)建兩個(gè)管道，再來匿名管道是只能用于存在父子關(guān)系的進(jìn)程間通信，匿名管道的生命周期隨著進(jìn)程創(chuàng)建而建立，隨著進(jìn)程終止而消失。

命名管道突破了匿名管道只能在親緣關(guān)系進(jìn)程間的通信限制，因?yàn)槭褂妹艿赖那疤?，需要在文件系統(tǒng)創(chuàng)建一個(gè)類型為 p 的設(shè)備文件，那么毫無關(guān)系的進(jìn)程就可以通過這個(gè)設(shè)備文件進(jìn)行通信。另外，不管是匿名管道還是命名管道，進(jìn)程寫入的數(shù)據(jù)都是緩存在內(nèi)核中，另一個(gè)進(jìn)程讀取數(shù)據(jù)時(shí)候自然也是從內(nèi)核中獲取，同時(shí)通信數(shù)據(jù)都遵循先進(jìn)先出原則，不支持 lseek 之類的文件定位操作。

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

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

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

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

前面說到的通信機(jī)制，都是工作于同一臺(tái)主機(jī)，如果要與不同主機(jī)的進(jìn)程間通信，那么就需要 Socket 通信了。Socket 實(shí)際上不僅用于不同的主機(jī)進(jìn)程間通信，還可以用于本地主機(jī)進(jìn)程間通信，可根據(jù)創(chuàng)建 Socket 的類型不同，分為三種常見的通信方式，一個(gè)是基于 TCP 協(xié)議的通信方式，一個(gè)是基于 UDP 協(xié)議的通信方式，一個(gè)是本地進(jìn)程間通信方式。

IO多路復(fù)用，select、poll、epoll 的區(qū)別？

select 實(shí)現(xiàn)多路復(fù)用的方式是，將已連接的 Socket 都放到一個(gè)文件描述符集合，然后調(diào)用 select 函數(shù)將文件描述符集合拷貝到內(nèi)核里，讓內(nèi)核來檢查是否有網(wǎng)絡(luò)事件產(chǎn)生，檢查的方式很粗暴，就是通過遍歷文件描述符集合的方式，當(dāng)檢查到有事件產(chǎn)生后，將此 Socket 標(biāo)記為可讀或可寫， 接著再把整個(gè)文件描述符集合拷貝回用戶態(tài)里，然后用戶態(tài)還需要再通過遍歷的方法找到可讀或可寫的 Socket，然后再對(duì)其處理。

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

select 使用固定長(zhǎng)度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的個(gè)數(shù)是有限制的，在 Linux 系統(tǒng)中，由內(nèi)核中的 FD_SETSIZE 限制， 默認(rèn)最大值為 1024，只能監(jiān)聽 0~1023 的文件描述符。

poll 不再用 BitsMap 來存儲(chǔ)所關(guān)注的文件描述符，取而代之用動(dòng)態(tài)數(shù)組，以鏈表形式來組織，突破了 select 的文件描述符個(gè)數(shù)限制，當(dāng)然還會(huì)受到系統(tǒng)文件描述符限制。

但是 poll 和 select 并沒有太大的本質(zhì)區(qū)別，都是使用「線性結(jié)構(gòu)」存儲(chǔ)進(jìn)程關(guān)注的 Socket 集合，因此都需要遍歷文件描述符集合來找到可讀或可寫的 Socket，時(shí)間復(fù)雜度為 O(n)，而且也需要在用戶態(tài)與內(nèi)核態(tài)之間拷貝文件描述符集合，這種方式隨著并發(fā)數(shù)上來，性能的損耗會(huì)呈指數(shù)級(jí)增長(zhǎng)。

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

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

從下圖你可以看到 epoll 相關(guān)的接口作用：

圖片

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

為什么操作系統(tǒng)要設(shè)計(jì)虛擬內(nèi)存？

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

圖片

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

這里關(guān)鍵的問題是這兩個(gè)程序都引用了絕對(duì)物理地址，而這正是我們最需要避免的。

進(jìn)程的中間層

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

操作系統(tǒng)會(huì)提供一種機(jī)制，將不同進(jìn)程的虛擬地址和不同內(nèi)存的物理地址映射起來。如果程序要訪問虛擬地址的時(shí)候，由操作系統(tǒng)轉(zhuǎn)換成不同的物理地址，這樣不同的進(jìn)程運(yùn)行的時(shí)候，寫入的是不同的物理地址，這樣就不會(huì)沖突了。

進(jìn)程和線程的區(qū)別？

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

進(jìn)程的地址空間里面有什么？

虛擬內(nèi)存空間劃分

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

• 代碼段，包括二進(jìn)制可執(zhí)行代碼；
• 數(shù)據(jù)段，包括已初始化的靜態(tài)常量和全局變量；
• BSS 段，包括未初始化的靜態(tài)變量和全局變量；
• 堆段，包括動(dòng)態(tài)分配的內(nèi)存，從低地址開始向上增長(zhǎng)；
• 文件映射段，包括動(dòng)態(tài)庫、共享內(nèi)存等；
• 棧段，包括局部變量和函數(shù)調(diào)用的上下文等。棧的大小是固定的，一般是 8 MB。當(dāng)然系統(tǒng)也提供了參數(shù)，以便我們自定義大??；

上圖中的內(nèi)存布局可以看到，代碼段下面還有一段內(nèi)存空間的（灰色部分），這一塊區(qū)域是「保留區(qū)」，之所以要有保留區(qū)這是因?yàn)樵诖蠖鄶?shù)的系統(tǒng)里，我們認(rèn)為比較小數(shù)值的地址不是一個(gè)合法地址，例如，我們通常在 C 的代碼里會(huì)將無效的指針賦值為 NULL。因此，這里會(huì)出現(xiàn)一段不可訪問的內(nèi)存保留區(qū)，防止程序因?yàn)槌霈F(xiàn) bug，導(dǎo)致讀或?qū)懥艘恍┬?nèi)存地址的數(shù)據(jù)，而使得程序跑飛。

在這 7 個(gè)內(nèi)存段中，堆和文件映射段的內(nèi)存是動(dòng)態(tài)分配的。比如說，使用 C 標(biāo)準(zhǔn)庫的 malloc() 或者 mmap() ，就可以分別在堆和文件映射段動(dòng)態(tài)分配內(nèi)存。

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

• 寄存器上下文：線程切換時(shí)需要保存和恢復(fù)線程所使用的寄存器的值，以便切換后能夠繼續(xù)執(zhí)行。常見的寄存器包括通用寄存器（如EAX、EBX、ECX等）、指令指針寄存器（如EIP）、堆棧指針寄存器（如ESP）等。
• 棧：線程的棧用于保存局部變量、函數(shù)調(diào)用信息等。在線程切換時(shí)，需要保存和恢復(fù)當(dāng)前線程的棧指針，以及相應(yīng)的棧幀信息。
• 線程上下文信息：線程切換時(shí)，需要保存和恢復(fù)與線程相關(guān)的其他上下文信息，如線程狀態(tài)、調(diào)度優(yōu)先級(jí)等。

協(xié)程和線程什么區(qū)別？

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

網(wǎng)絡(luò)

講一下TCP三次握手的過程

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

圖片

• TCP 三次握手

圖片

• 第一個(gè)報(bào)文 —— SYN 報(bào)文

圖片

• 第二個(gè)報(bào)文 —— SYN + ACK 報(bào)文

圖片

• 第三個(gè)報(bào)文 —— ACK 報(bào)文一旦完成三次握手，雙方都處于 ESTABLISHED 狀態(tài)，此時(shí)連接就已建立完成，客戶端和服務(wù)端就可以相互發(fā)送數(shù)據(jù)了。

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

TCP擁塞控制具體過程？

擁塞控制主要是四個(gè)算法：

• 慢啟動(dòng)
• 擁塞避免
• 擁塞發(fā)生
• 快速恢復(fù)

一、慢啟動(dòng)

慢啟動(dòng)的算法記住一個(gè)規(guī)則就行：當(dāng)發(fā)送方每收到一個(gè) ACK，擁塞窗口 cwnd 的大小就會(huì)加 1。

這里假定擁塞窗口 cwnd 和發(fā)送窗口 swnd 相等，下面舉個(gè)栗子：

• 連接建立完成后，一開始初始化 cwnd = 1，表示可以傳一個(gè) MSS 大小的數(shù)據(jù)。
• 當(dāng)收到一個(gè) ACK 確認(rèn)應(yīng)答后，cwnd 增加 1，于是一次能夠發(fā)送 2 個(gè)
• 當(dāng)收到 2 個(gè)的 ACK 確認(rèn)應(yīng)答后， cwnd 增加 2，于是就可以比之前多發(fā)2 個(gè)，所以這一次能夠發(fā)送 4 個(gè)
• 當(dāng)這 4 個(gè)的 ACK 確認(rèn)到來的時(shí)候，每個(gè)確認(rèn) cwnd 增加 1， 4 個(gè)確認(rèn) cwnd 增加 4，于是就可以比之前多發(fā) 4 個(gè)，所以這一次能夠發(fā)送 8 個(gè)。

慢啟動(dòng)算法的變化過程如下圖：

慢啟動(dòng)算法

可以看出慢啟動(dòng)算法，發(fā)包的個(gè)數(shù)是指數(shù)性的增長(zhǎng)。

那慢啟動(dòng)漲到什么時(shí)候是個(gè)頭呢？

有一個(gè)叫慢啟動(dòng)門限 ssthresh （slow start threshold）狀態(tài)變量。

• 當(dāng) cwnd < ssthresh 時(shí)，使用慢啟動(dòng)算法。
• 當(dāng) cwnd >= ssthresh 時(shí)，就會(huì)使用「擁塞避免算法」。

二、擁塞避免算法

前面說道，當(dāng)擁塞窗口 cwnd 「超過」慢啟動(dòng)門限 ssthresh 就會(huì)進(jìn)入擁塞避免算法。

一般來說 ssthresh 的大小是 65535 字節(jié)。那么進(jìn)入擁塞避免算法后，它的規(guī)則是：**每當(dāng)收到一個(gè) ACK 時(shí)，cwnd 增加 1/cwnd。*接上前面的慢啟動(dòng)的栗子，現(xiàn)假定 ssthresh 為 8：

• 當(dāng) 8 個(gè) ACK 應(yīng)答確認(rèn)到來時(shí)，每個(gè)確認(rèn)增加 1/8，8 個(gè) ACK 確認(rèn) cwnd 一共增加 1，于是這一次能夠發(fā)送 9 個(gè) MSS 大小的數(shù)據(jù)，變成了線性增長(zhǎng)。

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

擁塞避免

所以，我們可以發(fā)現(xiàn)，擁塞避免算法就是將原本慢啟動(dòng)算法的指數(shù)增長(zhǎng)變成了線性增長(zhǎng)，還是增長(zhǎng)階段，但是增長(zhǎng)速度緩慢了一些。

就這么一直增長(zhǎng)著后，網(wǎng)絡(luò)就會(huì)慢慢進(jìn)入了擁塞的狀況了，于是就會(huì)出現(xiàn)丟包現(xiàn)象，這時(shí)就需要對(duì)丟失的數(shù)據(jù)包進(jìn)行重傳。

當(dāng)觸發(fā)了重傳機(jī)制，也就進(jìn)入了「擁塞發(fā)生算法」。

三、擁塞發(fā)生

當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞，也就是會(huì)發(fā)生數(shù)據(jù)包重傳，重傳機(jī)制主要有兩種：

• 超時(shí)重傳
• 快速重傳

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

3.1 當(dāng)發(fā)生了「超時(shí)重傳」，則就會(huì)使用擁塞發(fā)生算法。

這個(gè)時(shí)候，ssthresh 和 cwnd 的值會(huì)發(fā)生變化：

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

擁塞發(fā)生算法的變化如下圖：

擁塞發(fā)送 —— 超時(shí)重傳

接著，就重新開始慢啟動(dòng)，慢啟動(dòng)是會(huì)突然減少數(shù)據(jù)流的。這真是一旦「超時(shí)重傳」，馬上回到解放前。但是這種方式太激進(jìn)了，反應(yīng)也很強(qiáng)烈，會(huì)造成網(wǎng)絡(luò)卡頓。就好像本來在秋名山高速漂移著，突然來個(gè)緊急剎車，輪胎受得了嗎。。。

3.2發(fā)生快速重傳的擁塞發(fā)生算法

還有更好的方式，前面我們講過「快速重傳算法」。當(dāng)接收方發(fā)現(xiàn)丟了一個(gè)中間包的時(shí)候，發(fā)送三次前一個(gè)包的 ACK，于是發(fā)送端就會(huì)快速地重傳，不必等待超時(shí)再重傳。

TCP 認(rèn)為這種情況不嚴(yán)重，因?yàn)榇蟛糠譀]丟，只丟了一小部分，則 ssthresh 和 cwnd 變化如下：

• cwnd = cwnd/2 ，也就是設(shè)置為原來的一半;
• ssthresh = cwnd;
• 進(jìn)入快速恢復(fù)算法

四、快速恢復(fù)

快速重傳和快速恢復(fù)算法一般同時(shí)使用，快速恢復(fù)算法是認(rèn)為，你還能收到 3 個(gè)重復(fù) ACK 說明網(wǎng)絡(luò)也不那么糟糕，所以沒有必要像 RTO 超時(shí)那么強(qiáng)烈。

正如前面所說，進(jìn)入快速恢復(fù)之前，cwnd 和 ssthresh 已被更新了：

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

然后，進(jìn)入快速恢復(fù)算法如下：

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

快速恢復(fù)算法的變化過程如下圖：

快速重傳和快速恢復(fù)

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

http與https的區(qū)別？

• HTTP 是超文本傳輸協(xié)議，信息是明文傳輸，存在安全風(fēng)險(xiǎn)的問題。HTTPS 則解決 HTTP 不安全的缺陷，在 TCP 和 HTTP 網(wǎng)絡(luò)層之間加入了 SSL/TLS 安全協(xié)議，使得報(bào)文能夠加密傳輸。
• HTTP 連接建立相對(duì)簡(jiǎn)單， TCP 三次握手之后便可進(jìn)行 HTTP 的報(bào)文傳輸。而 HTTPS 在 TCP 三次握手之后，還需進(jìn)行 SSL/TLS 的握手過程，才可進(jìn)入加密報(bào)文傳輸。
• 兩者的默認(rèn)端口不一樣，HTTP 默認(rèn)端口號(hào)是 80，HTTPS 默認(rèn)端口號(hào)是 443。
• HTTPS 協(xié)議需要向 CA（證書權(quán)威機(jī)構(gòu)）申請(qǐng)數(shù)字證書，來保證服務(wù)器的身份是可信的。

https加密的過程？

SSL/TLS 協(xié)議基本流程：

• 客戶端向服務(wù)器索要并驗(yàn)證服務(wù)器的公鑰。
• 雙方協(xié)商生產(chǎn)「會(huì)話秘鑰」。
• 雙方采用「會(huì)話秘鑰」進(jìn)行加密通信。

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

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

HTTPS 連接建立過程

TLS 協(xié)議建立的詳細(xì)流程：

1.ClientHello

首先，由客戶端向服務(wù)器發(fā)起加密通信請(qǐng)求，也就是 ClientHello 請(qǐng)求。

在這一步，客戶端主要向服務(wù)器發(fā)送以下信息：

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

（2）客戶端生產(chǎn)的隨機(jī)數(shù)（Client Random），后面用于生成「會(huì)話秘鑰」條件之一。

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

2.SeverHello

服務(wù)器收到客戶端請(qǐng)求后，向客戶端發(fā)出響應(yīng)，也就是 SeverHello。服務(wù)器回應(yīng)的內(nèi)容有如下內(nèi)容：

（1）確認(rèn) TLS 協(xié)議版本，如果瀏覽器不支持，則關(guān)閉加密通信。

（2）服務(wù)器生產(chǎn)的隨機(jī)數(shù)（Server Random），也是后面用于生產(chǎn)「會(huì)話秘鑰」條件之一。

（3）確認(rèn)的密碼套件列表，如 RSA 加密算法。

（4）服務(wù)器的數(shù)字證書。

3.客戶端回應(yīng)

客戶端收到服務(wù)器的回應(yīng)之后，首先通過瀏覽器或者操作系統(tǒng)中的 CA 公鑰，確認(rèn)服務(wù)器的數(shù)字證書的真實(shí)性。

如果證書沒有問題，客戶端會(huì)從數(shù)字證書中取出服務(wù)器的公鑰，然后使用它加密報(bào)文，向服務(wù)器發(fā)送如下信息：

（1）一個(gè)隨機(jī)數(shù)（pre-master key）。該隨機(jī)數(shù)會(huì)被服務(wù)器公鑰加密。

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

（3）客戶端握手結(jié)束通知，表示客戶端的握手階段已經(jīng)結(jié)束。這一項(xiàng)同時(shí)把之前所有內(nèi)容的發(fā)生的數(shù)據(jù)做個(gè)摘要，用來供服務(wù)端校驗(yàn)。

上面第一項(xiàng)的隨機(jī)數(shù)是整個(gè)握手階段的第三個(gè)隨機(jī)數(shù)，會(huì)發(fā)給服務(wù)端，所以這個(gè)隨機(jī)數(shù)客戶端和服務(wù)端都是一樣的。

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

4.服務(wù)器的最后回應(yīng)

服務(wù)器收到客戶端的第三個(gè)隨機(jī)數(shù)（pre-master key）之后，通過協(xié)商的加密算法，計(jì)算出本次通信的「會(huì)話秘鑰」。

然后，向客戶端發(fā)送最后的信息：

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

（2）服務(wù)器握手結(jié)束通知，表示服務(wù)器的握手階段已經(jīng)結(jié)束。這一項(xiàng)同時(shí)把之前所有內(nèi)容的發(fā)生的數(shù)據(jù)做個(gè)摘要，用來供客戶端校驗(yàn)。

至此，整個(gè) TLS 的握手階段全部結(jié)束。接下來，客戶端與服務(wù)器進(jìn)入加密通信，就完全是使用普通的 HTTP 協(xié)議，只不過用「會(huì)話秘鑰」加密內(nèi)容。

Redis

Redis常用數(shù)據(jù)結(jié)構(gòu)？

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

圖片

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

• String 類型的應(yīng)用場(chǎng)景：緩存對(duì)象、常規(guī)計(jì)數(shù)、分布式鎖、共享 session 信息等。
• List 類型的應(yīng)用場(chǎng)景：消息隊(duì)列（但是有兩個(gè)問題：1. 生產(chǎn)者需要自行實(shí)現(xiàn)全局唯一 ID；2. 不能以消費(fèi)組形式消費(fèi)數(shù)據(jù)）等。
• Hash 類型：緩存對(duì)象、購(gòu)物車等。
• Set 類型：聚合計(jì)算（并集、交集、差集）場(chǎng)景，比如點(diǎn)贊、共同關(guān)注、抽獎(jiǎng)活動(dòng)等。
• Zset 類型：排序場(chǎng)景，比如排行榜、電話和姓名排序等。

Redis 后續(xù)版本又支持四種數(shù)據(jù)類型，它們的應(yīng)用場(chǎng)景如下：

• BitMap（2.2 版新增）：二值狀態(tài)統(tǒng)計(jì)的場(chǎng)景，比如簽到、判斷用戶登陸狀態(tài)、連續(xù)簽到用戶總數(shù)等；
• HyperLogLog（2.8 版新增）：海量數(shù)據(jù)基數(shù)統(tǒng)計(jì)的場(chǎng)景，比如百萬級(jí)網(wǎng)頁 UV 計(jì)數(shù)等；
• GEO（3.2 版新增）：存儲(chǔ)地理位置信息的場(chǎng)景，比如滴滴叫車；
• Stream（5.0 版新增）：消息隊(duì)列，相比于基于 List 類型實(shí)現(xiàn)的消息隊(duì)列，有這兩個(gè)特有的特性：自動(dòng)生成全局唯一消息ID，支持以消費(fèi)組形式消費(fèi)數(shù)據(jù)。

Zset底層數(shù)據(jù)結(jié)構(gòu)？

Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)是由壓縮列表或跳表實(shí)現(xiàn)的：

• 如果有序集合的元素個(gè)數(shù)小于 128 個(gè)，并且每個(gè)元素的值小于 64 字節(jié)時(shí)，Redis 會(huì)使用壓縮列表作為 Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)；
• 如果有序集合的元素不滿足上面的條件，Redis 會(huì)使用跳表作為 Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)；

在 Redis 7.0 中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)了。

MySQL

B+樹有什么特點(diǎn)？

B+ 樹就是對(duì) B 樹做了一個(gè)升級(jí)，MySQL 中索引的數(shù)據(jù)結(jié)構(gòu)就是采用了 B+ 樹，B+ 樹結(jié)構(gòu)如下圖：

圖片

B+ 樹與 B 樹差異的點(diǎn)，主要是以下這幾點(diǎn)：

• 葉子節(jié)點(diǎn)（最底部的節(jié)點(diǎn)）才會(huì)存放實(shí)際數(shù)據(jù)（索引+記錄），非葉子節(jié)點(diǎn)只會(huì)存放索引；
• 所有索引都會(huì)在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)之間構(gòu)成一個(gè)有序鏈表；
• 非葉子節(jié)點(diǎn)的索引也會(huì)同時(shí)存在在子節(jié)點(diǎn)中，并且是在子節(jié)點(diǎn)中所有索引的最大（或最?。?/li>
• 非葉子節(jié)點(diǎn)中有多少個(gè)子節(jié)點(diǎn)，就有多少個(gè)索引；

MySQL 默認(rèn)的存儲(chǔ)引擎 InnoDB 采用的是 B+ 作為索引的數(shù)據(jù)結(jié)構(gòu)，原因有：

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

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

把節(jié)點(diǎn)緩存在內(nèi)存中，這樣下次查詢數(shù)據(jù)的時(shí)候，直接在內(nèi)存進(jìn)行索引查找就可以了。

智力題

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

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

算法

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