開發(fā)崗位 | 小紅書是給的真多，我想沖了...

舉個例子，你的快遞被放到了一個快遞箱里，如果快遞箱只會通過短信通知你一次，即使你一直沒有去取，它也不會再發(fā)送第二條短信提醒你，這個方式就是邊緣觸發(fā)；如果快遞箱發(fā)現(xiàn)你的快遞沒有被取出，它就會不停地發(fā)短信通知你，直到你取出了快遞，它才消停，這個就是水平觸發(fā)的方式。

這就是兩者的區(qū)別，水平觸發(fā)的意思是只要滿足事件的條件，比如內(nèi)核中有數(shù)據(jù)需要讀，就一直不斷地把這個事件傳遞給用戶；而邊緣觸發(fā)的意思是只有第一次滿足條件的時候才觸發(fā)，之后就不會再傳遞同樣的事件了。

如果使用水平觸發(fā)模式，當內(nèi)核通知文件描述符可讀寫時，接下來還可以繼續(xù)去檢測它的狀態(tài)，看它是否依然可讀或可寫。所以在收到通知后，沒必要一次執(zhí)行盡可能多的讀寫操作。

如果使用邊緣觸發(fā)模式，I/O 事件發(fā)生時只會通知一次，而且我們不知道到底能讀寫多少數(shù)據(jù)，所以在收到通知后應盡可能地讀寫數(shù)據(jù)，以免錯失讀寫的機會。因此，我們會循環(huán)從文件描述符讀寫數(shù)據(jù)，那么如果文件描述符是阻塞的，沒有數(shù)據(jù)可讀寫時，進程會阻塞在讀寫函數(shù)那里，程序就沒辦法繼續(xù)往下執(zhí)行。所以，邊緣觸發(fā)模式一般和非阻塞 I/O 搭配使用，程序會一直執(zhí)行 I/O 操作，直到系統(tǒng)調(diào)用（如 read 和 write）返回錯誤，錯誤類型為 EAGAIN 或 EWOULDBLOCK。

一般來說，邊緣觸發(fā)的效率比水平觸發(fā)的效率要高，因為邊緣觸發(fā)可以減少 epoll_wait 的系統(tǒng)調(diào)用次數(shù)，系統(tǒng)調(diào)用也是有一定的開銷的的，畢竟也存在上下文的切換。

Redis

Redis怎么實現(xiàn)的io多路復用？

為什么 Redis 中要使用 I/O 多路復用這種技術呢？

因為 Redis 是跑在「單線程」中的，所有的操作都是按照順序線性執(zhí)行的，但是由于讀寫操作等待用戶輸入 或 輸出都是阻塞的，所以 I/O 操作在一般情況下往往不能直接返回，這會導致某一文件的 I/O 阻塞導，致整個進程無法對其它客戶提供服務。而 I/O 多路復用就是為了解決這個問題而出現(xiàn)的。為了讓單線程(進程)的服務端應用同時處理多個客戶端的事件，Redis 采用了 IO 多路復用機制。

這里“多路”指的是多個網(wǎng)絡連接客戶端，“復用”指的是復用同一個線程(單進程)。I/O 多路復用其實是使用一個線程來檢查多個 Socket 的就緒狀態(tài)，在單個線程中通過記錄跟蹤每一個 socket（I/O流）的狀態(tài)來管理處理多個 I/O 流。如下圖是 Redis 的 I/O 多路復用模型：

如上圖對 Redis 的 I/O 多路復用模型進行一下描述說明：

一個 socket 客戶端與服務端連接時，會生成對應一個套接字描述符(套接字描述符是文件描述符的一種)，每一個 socket 網(wǎng)絡連接其實都對應一個文件描述符。多個客戶端與服務端連接時，Redis 使用 I/O 多路復用程序 將客戶端 socket 對應的 FD 注冊到監(jiān)聽列表(一個隊列)中。當客服端執(zhí)行 read、write 等操作命令時，I/O 多路復用程序會將命令封裝成一個事件，并綁定到對應的 FD 上。文件事件處理器使用 I/O 多路復用模塊同時監(jiān)控多個文件描述符（fd）的讀寫情況，當 accept、read、write 和 close 文件事件產(chǎn)生時，文件事件處理器就會回調(diào) FD 綁定的事件處理器進行處理相關命令操作。

例如：以 Redis 的 I/O 多路復用程序 epoll 函數(shù)為例。多個客戶端連接服務端時，Redis 會將客戶端 socket 對應的 fd 注冊進 epoll，然后 epoll 同時監(jiān)聽多個文件描述符(FD)是否有數(shù)據(jù)到來，如果有數(shù)據(jù)來了就通知事件處理器趕緊處理，這樣就不會存在服務端一直等待某個客戶端給數(shù)據(jù)的情形。

整個文件事件處理器是在單線程上運行的，但是通過 I/O 多路復用模塊的引入，實現(xiàn)了同時對多個 FD 讀寫的監(jiān)控，當其中一個 client 端達到寫或讀的狀態(tài)，文件事件處理器就馬上執(zhí)行，從而就不會出現(xiàn) I/O 堵塞的問題，提高了網(wǎng)絡通信的性能。Redis 的 I/O 多路復用模式使用的是 Reactor 設置模式的方式來實現(xiàn)。

Redis的網(wǎng)絡模型是怎樣的？

Redis 6.0 版本之前，是用的是單Reactor單線程的模式

單 Reactor 單進程的方案因為全部工作都在同一個進程內(nèi)完成，所以實現(xiàn)起來比較簡單，不需要考慮進程間通信，也不用擔心多進程競爭。

但是，這種方案存在 2 個缺點：

• • 第一個缺點，因為只有一個進程，

  無法充分利用 多核 CPU 的性能；

• • 第二個缺點，Handler 對象在業(yè)務處理時，整個進程是無法處理其他連接的事件的，

  如果業(yè)務處理耗時比較長，那么就造成響應的延遲；

所以，單 Reactor 單進程的方案不適用計算機密集型的場景，只適用于業(yè)務處理非常快速的場景。

Redis 是由 C 語言實現(xiàn)的，在 Redis 6.0 版本之前采用的正是「單 Reactor 單進程」的方案，因為 Redis 業(yè)務處理主要是在內(nèi)存中完成，操作的速度是很快的，性能瓶頸不在 CPU 上，所以 Redis 對于命令的處理是單進程的方案。

到 Redis 6.0 之后，就將網(wǎng)絡IO的處理改成多線程的方式了，目的是為了這是因為隨著網(wǎng)絡硬件的性能提升，Redis 的性能瓶頸有時會出現(xiàn)在網(wǎng)絡 I/O 的處理上。

所以為了提高網(wǎng)絡 I/O 的并行度，Redis 6.0 對于網(wǎng)絡 I/O 采用多線程來處理。但是對于命令的執(zhí)行，Redis 仍然使用單線程來處理，所以大家不要誤解 Redis 有多線程同時執(zhí)行命令。

Redis為什么快

官方使用基準測試的結果是，單線程的 Redis 吞吐量可以達到 10W/每秒，如下圖所示：

之所以 Redis 采用單線程（網(wǎng)絡 I/O 和執(zhí)行命令）那么快，有如下幾個原因：

• • Redis 的大部分操作

  都在內(nèi)存中完成

• • ，并且采用了高效的數(shù)據(jù)結構，因此 Redis 瓶頸可能是機器的內(nèi)存或者網(wǎng)絡帶寬，而并非 CPU，既然 CPU 不是瓶頸，那么自然就采用單線程的解決方案了；Redis 采用單線程模型可以

  避免了多線程之間的競爭

• • ，省去了多線程切換帶來的時間和性能上的開銷，而且也不會導致死鎖問題。Redis 采用了

  I/O 多路復用機制

處理大量的客戶端 Socket 請求，IO 多路復用機制是指一個線程處理多個 IO 流，就是我們經(jīng)常聽到的 select/epoll 機制。簡單來說，在 Redis 只運行單線程的情況下，該機制允許內(nèi)核中，同時存在多個監(jiān)聽 Socket 和已連接 Socket。內(nèi)核會一直監(jiān)聽這些 Socket 上的連接請求或數(shù)據(jù)請求。一旦有請求到達，就會交給 Redis 線程處理，這就實現(xiàn)了一個 Redis 線程處理多個 IO 流的效果。

Redis哪些地方使用了多線程

edis 單線程指的是「接收客戶端請求->解析請求 ->進行數(shù)據(jù)讀寫等操作->發(fā)送數(shù)據(jù)給客戶端」這個過程是由一個線程（主線程）來完成的，這也是我們常說 Redis 是單線程的原因。
但是，Redis 程序并不是單線程的，Redis 在啟動的時候，是會啟動后臺線程（BIO）的：

Redis 在 2.6 版本，會啟動 2 個后臺線程，分別處理關閉文件、AOF 刷盤這兩個任務；

Redis 在 4.0 版本之后，新增了一個新的后臺線程，用來異步釋放 Redis 內(nèi)存，也就是 lazyfree 線程。例如執(zhí)行 unlink key / flushdb async / flushall async 等命令，會把這些刪除操作交給后臺線程來執(zhí)行，好處是不會導致 Redis 主線程卡頓。因此，當我們要刪除一個大 key 的時候，不要使用 del 命令刪除，因為 del 是在主線程處理的，這樣會導致 Redis 主線程卡頓，因此我們應該使用 unlink 命令來異步刪除大key。

之所以 Redis 為「關閉文件、AOF 刷盤、釋放內(nèi)存」這些任務創(chuàng)建單獨的線程來處理，是因為這些任務的操作都是很耗時的，如果把這些任務都放在主線程來處理，那么 Redis 主線程就很容易發(fā)生阻塞，這樣就無法處理后續(xù)的請求了。

后臺線程相當于一個消費者，生產(chǎn)者把耗時任務丟到任務隊列中，消費者（BIO）不停輪詢這個隊列，拿出任務就去執(zhí)行對應的方法即可。

雖然 Redis 的主要工作（網(wǎng)絡 I/O 和執(zhí)行命令）一直是單線程模型，但是在 Redis 6.0 版本之后，也采用了多個 I/O 線程來處理網(wǎng)絡請求，這是因為隨著網(wǎng)絡硬件的性能提升，Redis 的性能瓶頸有時會出現(xiàn)在網(wǎng)絡 I/O 的處理上。

所以為了提高網(wǎng)絡 I/O 的并行度，Redis 6.0 對于網(wǎng)絡 I/O 采用多線程來處理。但是對于命令的執(zhí)行，Redis 仍然使用單線程來處理，所以大家不要誤解 Redis 有多線程同時執(zhí)行命令。

Redis 官方表示，Redis 6.0 版本引入的多線程 I/O 特性對性能提升至少是一倍以上。

Redis 6.0 版本支持的 I/O 多線程特性，默認情況下 I/O 多線程只針對發(fā)送響應數(shù)據(jù)（write client socket），并不會以多線程的方式處理讀請求（read client socket）。要想開啟多線程處理客戶端讀請求，就需要把 Redis.conf 配置文件中的 io-threads-do-reads 配置項設為 yes。

//讀請求也使用io多線程
io-threads-do-reads?yes

同時， Redis.conf 配置文件中提供了 IO 多線程個數(shù)的配置項。

//?io-threads?N，表示啟用?N-1?個?I/O?多線程（主線程也算一個?I/O?線程）
io-threads?4

關于線程數(shù)的設置，官方的建議是如果為 4 核的 CPU，建議線程數(shù)設置為 2 或 3，如果為 8 核 CPU 建議線程數(shù)設置為 6，線程數(shù)一定要小于機器核數(shù)，線程數(shù)并不是越大越好。
因此， Redis 6.0 版本之后，Redis 在啟動的時候，默認情況下會額外創(chuàng)建 6 個線程（_這里的線程數(shù)不包括主線程_）：

Redis-server ： Redis的主線程，主要負責執(zhí)行命令；bio_close_file、bio_aof_fsync、bio_lazy_free：三個后臺線程，分別異步處理關閉文件任務、AOF刷盤任務、釋放內(nèi)存任務；io_thd_1、io_thd_2、io_thd_3：三個 I/O 線程，io-threads 默認是 4 ，所以會啟動 3（4-1）個 I/O 多線程，用來分擔 Redis 網(wǎng)絡 I/O 的壓力。

講一下Redis底層的數(shù)據(jù)結構

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ù)類型的應用場景：

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

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

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

跳表和壓縮列表是怎么實現(xiàn)的？

跳表

Redis 只有 Zset 對象的底層實現(xiàn)用到了跳表，跳表的優(yōu)勢是能支持平均 O(logN) 復雜度的節(jié)點查找。

鏈表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間復雜度是O(N)，于是就出現(xiàn)了跳表。跳表是在鏈表基礎上改進過來的，實現(xiàn)了一種「多層」的有序鏈表，這樣的好處是能快讀定位數(shù)據(jù)。

那跳表長什么樣呢？我這里舉個例子，下圖展示了一個層級為 3 的跳表。

圖中頭節(jié)點有 L0~L2 三個頭指針，分別指向了不同層級的節(jié)點，然后每個層級的節(jié)點都通過指針連接起來：

L0 層級共有 5 個節(jié)點，分別是節(jié)點1、2、3、4、5；L1 層級共有 3 個節(jié)點，分別是節(jié)點 2、3、5；L2 層級只有 1 個節(jié)點，也就是節(jié)點 3 。

如果我們要在鏈表中查找節(jié)點 4 這個元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節(jié)點 4，因為可以在頭節(jié)點直接從 L2 層級跳到節(jié)點 3，然后再往前遍歷找到節(jié)點 4。

可以看到，這個查找過程就是在多個層級上跳來跳去，最后定位到元素。當數(shù)據(jù)量很大時，跳表的查找復雜度就是 O(logN)。

那跳表節(jié)點是怎么實現(xiàn)多層級的呢？這就需要看「跳表節(jié)點」的數(shù)據(jù)結構了，如下：

typedef?struct?zskiplistNode?{
????//Zset?對象的元素值
????sds?ele;
????//元素權重值
????double?score;
????//后向指針
????struct?zskiplistNode?*backward;
??
????//節(jié)點的level數(shù)組，保存每層上的前向指針和跨度
????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
}?zskiplistNode;

Zset 對象要同時保存「元素」和「元素的權重」，對應到跳表節(jié)點結構里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節(jié)點都有一個后向指針（struct zskiplistNode *backward），指向前一個節(jié)點，目的是為了方便從跳表的尾節(jié)點開始訪問節(jié)點，這樣倒序查找時很方便。

跳表是一個帶有層級關系的鏈表，而且每一層級可以包含多個節(jié)點，每一個節(jié)點通過指針連接起來，實現(xiàn)這一特性就是靠跳表節(jié)點結構體中的zskiplistLevel 結構體類型的 level 數(shù)組。

level 數(shù)組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結構體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結構體里定義了「指向下一個跳表節(jié)點的指針」和「跨度」，跨度時用來記錄兩個節(jié)點之間的距離。

比如，下面這張圖，展示了各個節(jié)點的跨度。

第一眼看到跨度的時候，以為是遍歷操作有關，實際上并沒有任何關系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。

Redis 跳表在創(chuàng)建節(jié)點的時候，隨機生成每個節(jié)點的層數(shù)，并沒有嚴格維持相鄰兩層的節(jié)點數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點時候，會生成范圍為[0-1]的一個隨機數(shù)，如果這個隨機數(shù)小于 0.25（相當于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個隨機數(shù)，直到隨機數(shù)的結果大于 0.25 結束，最終確定該節(jié)點的層數(shù)。

這樣的做法，相當于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。

雖然我前面講解跳表的時候，圖中的跳表的「頭節(jié)點」都是 3 層高，但是其實如果層高最大限制是 64，那么在創(chuàng)建跳表「頭節(jié)點」的時候，就會直接創(chuàng)建 64 層高的頭節(jié)點。

壓縮列表

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結構，有點類似于數(shù)組。

壓縮列表在表頭有三個字段：

zlbytes，記錄整個壓縮列表占用對內(nèi)存字節(jié)數(shù)；_

zltail，記錄壓縮列表「尾部」節(jié)點距離起始地址由多少字節(jié)，也就是列表尾的偏移量；_

zllen，記錄壓縮列表包含的節(jié)點數(shù)量；_

zlend，標記壓縮列表的結束點，固定值 0xFF（十進制255）。

在壓縮列表中，如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段（zllen）的長度直接定位，復雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復雜度就是 O(N) 了，因此壓縮列表不適合保存過多的元素。

另外，壓縮列表節(jié)點（entry）的構成如下：

壓縮列表節(jié)點包含三部分內(nèi)容：

prevlen，記錄了「前一個節(jié)點」的長度，目的是為了實現(xiàn)從后向前遍歷；_

encoding，記錄了當前節(jié)點實際數(shù)據(jù)的「類型和長度」，類型主要有兩種：字符串和整數(shù)。_

data，記錄了當前節(jié)點的實際數(shù)據(jù)，類型和長度都由 encoding 決定；

當我們往壓縮列表中插入數(shù)據(jù)時，壓縮列表就會根據(jù)數(shù)據(jù)類型是字符串還是整數(shù)，以及數(shù)據(jù)的大小，會使用不同空間大小的 prevlen 和 encoding 這兩個元素里保存的信息，這種根據(jù)數(shù)據(jù)大小和類型進行不同的空間大小分配的設計思想，正是 Redis 為了節(jié)省內(nèi)存而采用的。

壓縮列表的缺點是會發(fā)生連鎖更新的問題，因此連鎖更新一旦發(fā)生，就會導致壓縮列表占用的內(nèi)存空間要多次重新分配，這就會直接影響到壓縮列表的訪問性能。

所以說，雖然壓縮列表緊湊型的內(nèi)存布局能節(jié)省內(nèi)存開銷，但是如果保存的元素數(shù)量增加了，或是元素變大了，會導致內(nèi)存重新分配，最糟糕的是會有「連鎖更新」的問題。

因此，壓縮列表只會用于保存的節(jié)點數(shù)量不多的場景，只要節(jié)點數(shù)量足夠小，即使發(fā)生連鎖更新，也是能接受的。

雖說如此，Redis 針對壓縮列表在設計上的不足，在后來的版本中，新增設計了兩種數(shù)據(jù)結構：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種數(shù)據(jù)結構的設計目標，就是盡可能地保持壓縮列表節(jié)省內(nèi)存的優(yōu)勢，同時解決壓縮列表的「連鎖更新」的問題。

如何保證緩存的一致性？

緩存是通過犧牲強一致性來提高性能的。這是由CAP理論決定的。緩存系統(tǒng)適用的場景就是非強一致性的場景，它屬于CAP中的AP。所以，如果需要數(shù)據(jù)庫和緩存數(shù)據(jù)保持強一致，就不適合使用緩存。

所以使用緩存提升性能，就是會有數(shù)據(jù)更新的延遲。這需要我們在設計時結合業(yè)務仔細思考是否適合用緩存。然后緩存一定要設置過期時間，這個時間太短、或者太長都不好：

太短的話請求可能會比較多的落到數(shù)據(jù)庫上，這也意味著失去了緩存的優(yōu)勢。太長的話緩存中的臟數(shù)據(jù)會使系統(tǒng)長時間處于一個延遲的狀態(tài)，而且系統(tǒng)中長時間沒有人訪問的數(shù)據(jù)一直存在內(nèi)存中不過期，浪費內(nèi)存。

但是，通過一些方案優(yōu)化處理，是可以最終一致性的。

針對刪除緩存異常的情況，可以使用 2 個方案避免：

刪除緩存重試策略（消息隊列）訂閱 binlog，再刪除緩存（Canal+消息隊列）

消息隊列方案

我們可以引入消息隊列，將第二個操作（刪除緩存）要操作的數(shù)據(jù)加入到消息隊列，由消費者來操作數(shù)據(jù)。

• • 如果應用

  刪除緩存失敗

• • ，可以從消息隊列中重新讀取數(shù)據(jù)，然后再次刪除緩存，這個就是

  重試機制

• • 。當然，如果重試超過的一定次數(shù)，還是沒有成功，我們就需要向業(yè)務層發(fā)送報錯信息了。如果

  刪除緩存成功

，就要把數(shù)據(jù)從消息隊列中移除，避免重復操作，否則就繼續(xù)重試。

舉個例子，來說明重試機制的過程。

重試刪除緩存機制還可以，就是會造成好多業(yè)務代碼入侵。

訂閱 MySQL binlog，再操作緩存

「先更新數(shù)據(jù)庫，再刪緩存」的策略的第一步是更新數(shù)據(jù)庫，那么更新數(shù)據(jù)庫成功，就會產(chǎn)生一條變更日志，記錄在 binlog 里。

于是我們就可以通過訂閱 binlog 日志，拿到具體要操作的數(shù)據(jù)，然后再執(zhí)行緩存刪除，阿里巴巴開源的 Canal 中間件就是基于這個實現(xiàn)的。

Canal 模擬 MySQL 主從復制的交互協(xié)議，把自己偽裝成一個 MySQL 的從節(jié)點，向 MySQL 主節(jié)點發(fā)送 dump 請求，MySQL 收到請求后，就會開始推送 Binlog 給 Canal，Canal 解析 Binlog 字節(jié)流之后，轉換為便于讀取的結構化數(shù)據(jù)，供下游程序訂閱使用。

下圖是 Canal 的工作原理：

將binlog日志采集發(fā)送到MQ隊列里面，然后編寫一個簡單的緩存刪除消息者訂閱binlog日志，根據(jù)更新log刪除緩存，并且通過ACK機制確認處理這條更新log，保證數(shù)據(jù)緩存一致性

Java

ConcurrentHashMap為什么是線程安全的？

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實現(xiàn)的，而數(shù)組又分為：大數(shù)組 Segment 和小數(shù)組 HashEntry。

Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲鍵值對數(shù)據(jù)。一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組，一個 Segment 里包含一個 HashEntry 數(shù)組，每個 HashEntry 是一個鏈表結構的元素。

JDK 1.7 ConcurrentHashMap 分段鎖技術將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 雖然是線程安全的，但因為它的底層實現(xiàn)是數(shù)組 + 鏈表的形式，所以在數(shù)據(jù)比較多的情況下訪問是很慢的，因為要遍歷整個鏈表，而 JDK 1.8 則使用了數(shù)組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實現(xiàn)，具體實現(xiàn)結構如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實現(xiàn)的線程安全的。添加元素時首先會判斷容器是否為空：

如果為空則使用 ?volatile ?加 ?CAS ?來初始化如果容器不為空，則根據(jù)存儲的元素計算該位置是否為空。
• 如果根據(jù)存儲的元素計算結果為空，則利用 ?CAS ?設置該節(jié)點；如果根據(jù)存儲的元素計算結果不為空，則使用 synchronized ?，然后，遍歷桶中的數(shù)據(jù)，并替換或新增節(jié)點到桶中，最后再判斷是否需要轉為紅黑樹，這樣就能保證并發(fā)訪問時的線程安全了。

如果把上面的執(zhí)行用一句話歸納的話，就相當于是ConcurrentHashMap通過對頭結點加鎖來保證線程安全的，鎖的粒度相比 Segment 來說更小了，發(fā)生沖突和加鎖的頻率降低了，并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表，那么當數(shù)據(jù)量比較大的時候，查詢性能也得到了很大的提升，從之前的 O(n) 優(yōu)化到了 O(logn) 的時間復雜度。

OS

講一下銀行家算法

系統(tǒng)發(fā)生死鎖是很正常的，我們需要主動去預防死鎖，即進行有序的資源分配，使用銀行家算法。銀行家算法是最有代表性的避免死鎖的算法。
為什么叫銀行家算法呢？就是這個算法的邏輯很像銀行放貸的邏輯，也就是盡可能避免壞賬的出現(xiàn)。
銀行家算法的業(yè)務邏輯如下。

不負荷執(zhí)行：一個進程的最大需求量不超過系統(tǒng)擁有的總資源數(shù)，才會被接納執(zhí)行。

可分期：一個進程可以分期請求資源，但總請求書不可超過最大需求量。

推遲分配：當系統(tǒng)現(xiàn)有資源數(shù)小于進程需求時，對進程的需求可以延遲分配，但總讓進程在有限時間內(nèi)獲取資源。

聽起來有點繞，我們還是舉個例子來說明。

假如系統(tǒng)中有三類互斥資源 R1、R2、R3，可用資源數(shù)分別是 9、8、5，在指定時刻有 P1、P2、P3、P4 和 P5 這五個進程，這些進程的對三類互斥資源的最大需求量和已分配資源數(shù)如下表所示，那么系統(tǒng)如何先后運行這五個進程，不會發(fā)生死鎖問題？

第一步：分析

首先分析首次需求的資源，系統(tǒng)剩余可用資源數(shù)分別是 2、1、0，各進程需要的資源數(shù)如下表所示。

資源 R1 的剩余可用資源數(shù) = 9 - 1 - 2 - 2 - 1 - 1 = 2。
資源 R2 的剩余可用資源數(shù) = 8 - 2 - 1 - 1 - 2 - 1 = 1。
資源 R3 的剩余可用資源數(shù) = 5 - 1 - 1 - 0 - 0 - 3 = 0。

根據(jù)銀行家算法不負荷原則【一個進程的最大需求量不超過系統(tǒng)擁有的總資源數(shù)，才會被接納執(zhí)行】，優(yōu)先給進程 P2 執(zhí)行，因為剩余的 0 1 0 資源夠讓 P2 執(zhí)行。

第二步：執(zhí)行 P2

P2 執(zhí)行之后，釋放了剛剛放入的 2 1 0 資源，而且可以釋放已分配的 2 1 1 資源，所以此時的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 2 - 0 +（2 + 0） = 4。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 1 - 1 + （1 + 1） = 2。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 0 - 0 +（0 + 1） = 1。

執(zhí)行完成 P2 后，操作系統(tǒng)剩余可用資源數(shù)為 4 2 1。

第三步：執(zhí)行 P4

此時操作系統(tǒng)剩余可用資源數(shù)為 4 2 1，只能執(zhí)行進程 P4，因為其他進程資源不夠。

P4 執(zhí)行之后，釋放了剛剛放入的 0 0 1 資源，而且可以釋放已分配的 1 2 1 資源，所以此時的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 4 - 0 +（1 + 0） = 5。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 2 - 0 + （2 + 0） = 4。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 1 - 1 +（1 + 1） = 2。

執(zhí)行完成 P4 后，操作系統(tǒng)剩余可用資源數(shù)為 5 4 2。

第四步：執(zhí)行 P5

此時操作系統(tǒng)剩余可用資源數(shù)為 5 4 2，只能執(zhí)行進程 P5，因為其他進程資源不夠。

P5 執(zhí)行之后，釋放了剛剛放入的 2 3 1 資源，而且可以釋放已分配的 1 1 3 資源，所以此時的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 5 - 2 +（1 + 2） = 6。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 4 - 3 + （1 + 3） = 5。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 2 - 1 +（3 + 1） = 5。

執(zhí)行完成 P5 后，操作系統(tǒng)剩余可用資源數(shù)為 6 5 5。

第五步：執(zhí)行 P1 或者 P3

此時操作系統(tǒng)剩余可用資源數(shù)為 6 5 5，可以執(zhí)行 P1 或 P3。

所以安全執(zhí)行順序為 p2 => p4 => p5 => p1 => p3 或 p2 => p4 => p5 => p3 => p1。

在這里插入圖片描述或在這里插入圖片描述

銀行家算法總結

銀行家算法的核心思想，就是在分配給進程資源前，首先判斷這個進程的安全性，也就是預執(zhí)行，判斷分配后是否產(chǎn)生死鎖現(xiàn)象。如果系統(tǒng)當前資源能滿足其執(zhí)行，則嘗試分配，如果不滿足則讓該進程等待。通過不斷檢查剩余可用資源是否滿足某個進程的最大需求，如果可以則加入安全序列，并把該進程當前持有的資源回收；不斷重復這個過程，看最后能否實現(xiàn)讓所有進程都加入安全序列。安全序列一定不會發(fā)生死鎖，但沒有死鎖不一定是安全序列。

講一下頁表

分頁是把整個虛擬和物理內(nèi)存空間切成一段段固定尺寸的大小。這樣一個連續(xù)并且尺寸固定的內(nèi)存空間，我們叫頁（_Page_）。在 Linux 下，每一頁的大小為 4KB。
虛擬地址與物理地址之間通過頁表來映射，如下圖：

頁表是存儲在內(nèi)存里的，內(nèi)存管理單元 （_MMU_）就做將虛擬內(nèi)存地址轉換成物理地址的工作。

而當進程訪問的虛擬地址在頁表中查不到時，系統(tǒng)會產(chǎn)生一個缺頁異常，進入系統(tǒng)內(nèi)核空間分配物理內(nèi)存、更新進程頁表，最后再返回用戶空間，恢復進程的運行。

內(nèi)存分頁由于內(nèi)存空間都是預先劃分好的，也就不會像內(nèi)存分段一樣，在段與段之間會產(chǎn)生間隙非常小的內(nèi)存，這正是分段會產(chǎn)生外部內(nèi)存碎片的原因。而采用了分頁，頁與頁之間是緊密排列的，所以不會有外部碎片。

但是，因為內(nèi)存分頁機制分配內(nèi)存的最小單位是一頁，即使程序不足一頁大小，我們最少只能分配一個頁，所以頁內(nèi)會出現(xiàn)內(nèi)存浪費，所以針對內(nèi)存分頁機制會有內(nèi)部內(nèi)存碎片的現(xiàn)象。

在分頁機制下，虛擬地址分為兩部分，頁號和頁內(nèi)偏移。頁號作為頁表的索引，頁表包含物理頁每頁所在物理內(nèi)存的基地址，這個基地址與頁內(nèi)偏移的組合就形成了物理內(nèi)存地址，見下圖。

總結一下，對于一個內(nèi)存地址轉換，其實就是這樣三個步驟：

把虛擬內(nèi)存地址，切分成頁號和偏移量；根據(jù)頁號，從頁表里面，查詢對應的物理頁號；直接拿物理頁號，加上前面的偏移量，就得到了物理內(nèi)存地址。

下面舉個例子，虛擬內(nèi)存中的頁通過頁表映射為了物理內(nèi)存中的頁，如下圖：

講下為什么進程之下還要設計線程，線程之間怎么通信的

為什么要設計線程

我們舉個例子，假設你要編寫一個視頻播放器軟件，那么該軟件功能的核心模塊有三個：

從視頻文件當中讀取數(shù)據(jù)；對讀取的數(shù)據(jù)進行解壓縮；把解壓縮后的視頻數(shù)據(jù)播放出來；

對于單進程的實現(xiàn)方式，我想大家都會是以下這個方式：對于單進程的這種方式，存在以下問題：

播放出來的畫面和聲音會不連貫，因為當 CPU 能力不夠強的時候，Read 的時候可能進程就等在這了，這樣就會導致等半天才進行數(shù)據(jù)解壓和播放；各個函數(shù)之間不是并發(fā)執(zhí)行，影響資源的使用效率；

那改進成多進程的方式：

對于多進程的這種方式，依然會存在問題：

進程之間如何通信，共享數(shù)據(jù)？維護進程的系統(tǒng)開銷較大，如創(chuàng)建進程時，分配資源、建立 PCB；終止進程時，回收資源、撤銷 PCB；進程切換時，保存當前進程的狀態(tài)信息；

那到底如何解決呢？需要有一種新的實體，滿足以下特性：

實體之間可以并發(fā)運行；實體之間共享相同的地址空間；

這個新的實體，就是**線程( Thread )**，線程之間可以并發(fā)運行且共享相同的地址空間。

線程間的通信方式

Linux系統(tǒng)提供了五種用于線程通信的方式：互斥鎖、讀寫鎖、條件變量、自旋鎖和信號量。

互斥鎖（Mutex）：互斥量(mutex)從本質(zhì)上說是一把鎖，在訪問共享資源前對互斥量進行加鎖，在訪問完成后釋放互斥量上的鎖。對互斥量進行加鎖以后，任何其他試圖再次對互斥鎖加鎖的線程將會阻塞直到當前線程釋放該互斥鎖。如果釋放互斥鎖時有多個線程阻塞，所有在該互斥鎖上的阻塞線程都會變成可運行狀態(tài)，第一個變?yōu)檫\行狀態(tài)的線程可以對互斥鎖加鎖，其他線程將會看到互斥鎖依然被鎖住，只能回去再次等待它重新變?yōu)榭捎谩?/p>

條件變量（Condition Variables）：條件變量(cond)是在多線程程序中用來實現(xiàn)"等待--》喚醒"邏輯常用的方法。條件變量利用線程間共享的全局變量進行同步的一種機制，主要包括兩個動作：一個線程等待"條件變量的條件成立"而掛起；另一個線程使“條件成立”。為了防止競爭，條件變量的使用總是和一個互斥鎖結合在一起。線程在改變條件狀態(tài)前必須首先鎖住互斥量，函數(shù)pthread_cond_wait把自己放到等待條件的線程列表上，然后對互斥鎖解鎖(這兩個操作是原子操作)。在函數(shù)返回時，互斥量再次被鎖住。

自旋鎖（Spinlock）：自旋鎖通過 CPU 提供的 CAS 函數(shù)（_Compare And Swap_），在「用戶態(tài)」完成加鎖和解鎖操作，不會主動產(chǎn)生線程上下文切換，所以相比互斥鎖來說，會快一些，開銷也小一些。一般加鎖的過程，包含兩個步驟：第一步，查看鎖的狀態(tài)，如果鎖是空閑的，則執(zhí)行第二步；第二步，將鎖設置為當前線程持有；使用自旋鎖的時候，當發(fā)生多線程競爭鎖的情況，加鎖失敗的線程會「忙等待」，直到它拿到鎖。CAS 函數(shù)就把這兩個步驟合并成一條硬件級指令，形成

原子指令，這樣就保證了這兩個步驟是不可分割的，要么一次性執(zhí)行完兩個步驟，要么兩個步驟都不執(zhí)行。這里的「忙等待」可以用 while 循環(huán)等待實現(xiàn)，不過最好是使用 CPU 提供的 PAUSE 指令來實現(xiàn)「忙等待」，因為可以減少循環(huán)等待時的耗電量。

信號量（Semaphores）：信號量可以是命名的（有名信號量）或無名的（僅限于當前進程內(nèi)的線程），用于控制對資源的訪問次數(shù)。通常

信號量表示資源的數(shù)量，對應的變量是一個整型（sem）變量。另外，還有兩個原子操作的系統(tǒng)調(diào)用函數(shù)來控制信號量的

• ，分別是：_P 操作_：將 sem 減 1，相減后，如果 sem < 0，則進程/線程進入阻塞等待，否則繼續(xù)，表明 P 操作可能會阻塞；_V 操作_：將 sem 加 1，相加后，如果 sem <= 0，喚醒一個等待中的進程/線程，表明 V 操作不會阻塞；

讀寫鎖（Read-Write Locks）：讀寫鎖從字面意思我們也可以知道，它由「讀鎖」和「寫鎖」兩部分構成，如果只讀取共享資源用「讀鎖」加鎖，如果要修改共享資源則用「寫鎖」加鎖。所以，讀寫鎖適用于能明確區(qū)分讀操作和寫操作的場景。

• • 讀寫鎖的工作原理是：當「寫鎖」沒有被線程持有時，多個線程能夠并發(fā)地持有讀鎖，這大大提高了共享資源的訪問效率，因為「讀鎖」是用于讀取共享資源的場景，所以多個線程同時持有讀鎖也不會破壞共享資源的數(shù)據(jù)。但是，一旦「寫鎖」被線程持有后，讀線程的獲取讀鎖的操作會被阻塞，而且其他寫線程的獲取寫鎖的操作也會被阻塞。所以說，寫鎖是獨占鎖，因為任何時刻只能有一個線程持有寫鎖，類似互斥鎖和自旋鎖，而讀鎖是共享鎖，因為讀鎖可以被多個線程同時持有。知道了讀寫鎖的工作原理后，我們可以發(fā)現(xiàn)，

  讀寫鎖在讀多寫少的場景，能發(fā)揮出優(yōu)勢。

MySQL

講一講mysql的引擎吧，你有什么了解？

MySQL中常用的存儲引擎分別是：MyISAM存儲引擎、innoDB存儲引擎，他們的區(qū)別在于：

事務：InnoDB 支持事務，MyISAM 不支持事務，這是 MySQL 將默認存儲引擎從 MyISAM 變成 InnoDB 的重要原因之一。索引結構：InnoDB 是聚簇索引，MyISAM 是非聚簇索引。聚簇索引的文件存放在主鍵索引的葉子節(jié)點上，因此 InnoDB 必須要有主鍵，通過主鍵索引效率很高。但是輔助索引需要兩次查詢，先查詢到主鍵，然后再通過主鍵查詢到數(shù)據(jù)。因此，主鍵不應該過大，因為主鍵太大，其他索引也都會很大。而 MyISAM 是非聚簇索引，數(shù)據(jù)文件是分離的，索引保存的是數(shù)據(jù)文件的指針。主鍵索引和輔助索引是獨立的。鎖粒度：InnoDB 最小的鎖粒度是行鎖，MyISAM 最小的鎖粒度是表鎖。一個更新語句會鎖住整張表，導致其他查詢和更新都會被阻塞，因此并發(fā)訪問受限。count 的效率：InnoDB 不保存表的具體行數(shù)，執(zhí)行 select count(*) from table 時需要全表掃描。而MyISAM 用一個變量保存了整個表的行數(shù)，執(zhí)行上述語句時只需要讀出該變量即可，速度很快。

講一下mysql里的鎖？

在 MySQL 里，根據(jù)加鎖的范圍，可以分為全局鎖、表級鎖和行鎖三類。

全局鎖：通過flush tables with read lock 語句會將整個數(shù)據(jù)庫就處于只讀狀態(tài)了，這時其他線程執(zhí)行以下操作，增刪改或者表結構修改都會阻塞。全局鎖主要應用于做

全庫邏輯備份，這樣在備份數(shù)據(jù)庫期間，不會因為數(shù)據(jù)或表結構的更新，而出現(xiàn)備份文件的數(shù)據(jù)與預期的不一樣。

表級鎖：MySQL 里面表級別的鎖有這幾種：

• • 表鎖：通過lock tables 語句可以對表加表鎖，表鎖除了會限制別的線程的讀寫外，也會限制本線程接下來的讀寫操作。元數(shù)據(jù)鎖：當我們對數(shù)據(jù)庫表進行操作時，會自動給這個表加上 MDL，對一張表進行 CRUD 操作時，加的是

MDL 讀鎖；對一張表做結構變更操作的時候，加的是MDL 寫鎖

• • ；MDL 是為了保證當用戶對表執(zhí)行 CRUD 操作時，防止其他線程對這個表結構做了變更。意向鎖：當執(zhí)行插入、更新、刪除操作，需要先對表加上「意向獨占鎖」，然后對該記錄加獨占鎖。

意向鎖的目的是為了快速判斷表里是否有記錄被加鎖。

行級鎖：InnoDB 引擎是支持行級鎖的，而 MyISAM 引擎并不支持行級鎖。

• 記錄鎖，鎖住的是一條記錄。而且記錄鎖是有 S 鎖和 X 鎖之分的，滿足讀寫互斥，寫寫互斥間隙鎖，只存在于可重復讀隔離級別，目的是為了解決可重復讀隔離級別下幻讀的現(xiàn)象。Next-Key Lock 稱為臨鍵鎖，是 Record Lock + Gap Lock 的組合，鎖定一個范圍，并且鎖定記錄本身。

MySQL主從復制了解嗎

MySQL 的主從復制依賴于 binlog ，也就是記錄 MySQL 上的所有變化并以二進制形式保存在磁盤上。復制的過程就是將 binlog 中的數(shù)據(jù)從主庫傳輸?shù)綇膸焐稀?br /> 這個過程一般是異步的，也就是主庫上執(zhí)行事務操作的線程不會等待復制 binlog 的線程同步完成。

MySQL 集群的主從復制過程梳理成 3 個階段：

寫入 Binlog：主庫寫 binlog 日志，提交事務，并更新本地存儲數(shù)據(jù)。

同步 Binlog：把 binlog 復制到所有從庫上，每個從庫把 binlog 寫到暫存日志中。

回放 Binlog：回放 binlog，并更新存儲引擎中的數(shù)據(jù)。

具體詳細過程如下：

MySQL 主庫在收到客戶端提交事務的請求之后，會先寫入 binlog，再提交事務，更新存儲引擎中的數(shù)據(jù)，事務提交完成后，返回給客戶端“操作成功”的響應。從庫會創(chuàng)建一個專門的 I/O 線程，連接主庫的 log dump 線程，來接收主庫的 binlog 日志，再把 binlog 信息寫入 relay log 的中繼日志里，再返回給主庫“復制成功”的響應。從庫會創(chuàng)建一個用于回放 binlog 的線程，去讀 relay log 中繼日志，然后回放 binlog 更新存儲引擎中的數(shù)據(jù)，最終實現(xiàn)主從的數(shù)據(jù)一致性。

在完成主從復制之后，你就可以在寫數(shù)據(jù)時只寫主庫，在讀數(shù)據(jù)時只讀從庫，這樣即使寫請求會鎖表或者鎖記錄，也不會影響讀請求的執(zhí)行。

主從延遲都有什么處理方法？

強制走主庫方案：對于大事務或資源密集型操作，直接在主庫上執(zhí)行，避免從庫的額外延遲。

B+樹的特點是什么？

B+樹是一種自平衡的多路查找樹，所有葉節(jié)點都位于同一層，保證了樹的平衡，使得搜索、插入和刪除操作的時間復雜度為對數(shù)級別的。非葉節(jié)點僅包含索引信息，不存儲具體的數(shù)據(jù)記錄，它們只用來引導搜索到正確的葉節(jié)點。非葉節(jié)點的子樹指針與關鍵字數(shù)量相同，每個子樹指針指向一個子樹，子樹中的所有鍵值都在某個區(qū)間內(nèi)。所有數(shù)據(jù)記錄都存儲在葉節(jié)點中，且葉節(jié)點中的數(shù)據(jù)是按關鍵字排序的。葉節(jié)點包含實際的數(shù)據(jù)和關鍵字，它們是數(shù)據(jù)存儲和檢索的實體單元。葉節(jié)點之間通過指針相互鏈接，形成一個鏈表，便于范圍查詢和順序遍歷。