面試必備：蝦皮服務(wù)端15連問

前言

大家好，我是程序員田螺，最近有位讀者去蝦皮面試?yán)玻窒硪幌旅嬖嚨恼骖}~

1. 排序鏈表
2. 對稱與非對稱加密算法的區(qū)別
3. TCP如何保證可靠性
4. 聊聊五種IO模型
5. hystrix 工作原理
6. 延時(shí)場景處理
7. https請求過程
8. 聊聊事務(wù)隔離級別，以及可重復(fù)讀實(shí)現(xiàn)原理
9. 聊聊索引在哪些場景下會失效？
10. 什么是虛擬內(nèi)存
11. 排行榜的實(shí)現(xiàn)，比如高考成績排序
12. 分布式鎖實(shí)現(xiàn)
13. 聊聊零拷貝
14. 聊聊synchronized
15. 分布式ID生成方案

1. 排序鏈表

給你鏈表的頭結(jié)點(diǎn)head ，請將其按升序排列并返回排序后的鏈表 。

實(shí)例1：

輸入：head =?[4,2,1,3]
輸出：[1,2,3,4]

實(shí)例2：

輸入：head =?[-1,5,3,4,0]
輸出：[-1,0,3,4,5]

這道題可以用雙指針+歸并排序算法解決，主要以下四個(gè)步驟

1. 快慢指針法，遍歷鏈表找到中間節(jié)點(diǎn)
2. 中間節(jié)點(diǎn)切斷鏈表
3. 分別用歸并排序排左右子鏈表
4. 合并子鏈表

完整代碼如下：

class?Solution?{
????public?ListNode?sortList(ListNode?head)?{
????????//如果鏈表為空，或者只有一個(gè)節(jié)點(diǎn)，直接返回即可，不用排序
????????if?(head?==?null?||?head.next?==?null)
????????????return?head;
????????
????????//快慢指針移動，以尋找到中間節(jié)點(diǎn)
????????ListNode?slow?=?head;
????????ListNode?fast?=?head;
????????while(fast.next!=null?&&?fast.next.next?!=null){
??????????fast?=?fast.next.next;
??????????slow?=?slow.next;
????????}
????????//找到中間節(jié)點(diǎn)，slow節(jié)點(diǎn)的next指針，指向mid
????????ListNode?mid?=?slow.next;
????????//切斷鏈表
????????slow.next?=?null;
????????
????????//排序左子鏈表
????????ListNode?left?=?sortList(head);
????????//排序左子鏈表
????????ListNode?right?=?sortList(mid);
????????
????????//合并鏈表
????????return?merge(left,right);
????}
????
????public?ListNode?merge(ListNode?left,?ListNode?right)?{
???????ListNode?head?=?new?ListNode(0);
???????ListNode?temp?=?head;
???????while?(left?!=?null?&&?right?!=?null)?{
???????????if?(left.val?<=?right.val)?{
????????????????temp.next?=?left;
????????????????left?=?left.next;
????????????}?else?{
????????????????temp.next?=?right;
????????????????right?=?right.next;
????????????}
????????????temp?=?temp.next;
????????}
????????if?(left?!=?null)?{
????????????temp.next?=?left;
????????}?else?if?(right?!=?null)?{
????????????temp.next?=?right;
????????}
????????return?head.next;
????}
}

2.對稱與非對稱加密算法的區(qū)別

先復(fù)習(xí)一下相關(guān)概念：

• 明文：指沒有經(jīng)過加密的信息/數(shù)據(jù)。
• 密文：明文被加密算法加密之后，會變成密文，以確保數(shù)據(jù)安全。
• 密鑰：是一種參數(shù)，它是在明文轉(zhuǎn)換為密文或?qū)⒚芪霓D(zhuǎn)換為明文的算法中輸入的參數(shù)。密鑰分為對稱密鑰與非對稱密鑰。
• 加密：將明文變成密文的過程。
• 解密：將密文還原為明文的過程。

對稱加密算法:加密和解密使用相同密鑰的加密算法。常見的對稱加密算法有AES、3DES、DES、RC5、RC6等。

非對稱加密算法：非對稱加密算法需要兩個(gè)密鑰（公開密鑰和私有密鑰）。公鑰與私鑰是成對存在的，如果用公鑰對數(shù)據(jù)進(jìn)行加密，只有對應(yīng)的私鑰才能解密。主要的非對稱加密算法有：RSA、Elgamal、DSA、D-H、ECC。

3. TCP如何保證可靠性

• 首先，TCP的連接是基于三次握手，而斷開則是四次揮手。確保連接和斷開的可靠性。
• 其次，TCP的可靠性，還體現(xiàn)在有狀態(tài);TCP會記錄哪些數(shù)據(jù)發(fā)送了，哪些數(shù)據(jù)被接受了，哪些沒有被接受，并且保證數(shù)據(jù)包按序到達(dá)，保證數(shù)據(jù)傳輸不出差錯(cuò)。
• 再次，TCP的可靠性，還體現(xiàn)在可控制。它有報(bào)文校驗(yàn)、ACK應(yīng)答、超時(shí)重傳(發(fā)送方)、失序數(shù)據(jù)重傳（接收方）、丟棄重復(fù)數(shù)據(jù)、流量控制（滑動窗口）和擁塞控制等機(jī)制。

4. 聊聊五種IO模型

4.1 阻塞IO 模型

假設(shè)應(yīng)用程序的進(jìn)程發(fā)起IO調(diào)用，但是如果內(nèi)核的數(shù)據(jù)還沒準(zhǔn)備好的話，那應(yīng)用程序進(jìn)程就一直在阻塞等待，一直等到內(nèi)核數(shù)據(jù)準(zhǔn)備好了，從內(nèi)核拷貝到用戶空間，才返回成功提示，此次IO操作，稱之為阻塞IO。

4.2 非阻塞IO模型

如果內(nèi)核數(shù)據(jù)還沒準(zhǔn)備好，可以先返回錯(cuò)誤信息給用戶進(jìn)程，讓它不需要等待，而是通過輪詢的方式再來請求。這就是非阻塞IO，流程圖如下：

4.3 IO多路復(fù)用模型

IO多路復(fù)用之select

應(yīng)用進(jìn)程通過調(diào)用select函數(shù)，可以同時(shí)監(jiān)控多個(gè)fd，在select函數(shù)監(jiān)控的fd中，只要有任何一個(gè)數(shù)據(jù)狀態(tài)準(zhǔn)備就緒了，select函數(shù)就會返回可讀狀態(tài)，這時(shí)應(yīng)用進(jìn)程再發(fā)起recvfrom請求去讀取數(shù)據(jù)。

select有幾個(gè)缺點(diǎn)：

• 最大連接數(shù)有限，在Linux系統(tǒng)上一般為1024。
• select函數(shù)返回后，是通過遍歷fdset，找到就緒的描述符fd。

IO多路復(fù)用之epoll

為了解決select存在的問題，多路復(fù)用模型epoll誕生，它采用事件驅(qū)動來實(shí)現(xiàn)，流程圖如下：

epoll先通過epoll_ctl()來注冊一個(gè)fd（文件描述符），一旦基于某個(gè)fd就緒時(shí)，內(nèi)核會采用回調(diào)機(jī)制，迅速激活這個(gè)fd，當(dāng)進(jìn)程調(diào)用epoll_wait()時(shí)便得到通知。這里去掉了遍歷文件描述符的坑爹操作，而是采用監(jiān)聽事件回調(diào)的機(jī)制。這就是epoll的亮點(diǎn)。

4.4 IO模型之信號驅(qū)動模型

信號驅(qū)動IO不再用主動詢問的方式去確認(rèn)數(shù)據(jù)是否就緒，而是向內(nèi)核發(fā)送一個(gè)信號（調(diào)用sigaction的時(shí)候建立一個(gè)SIGIO的信號），然后應(yīng)用用戶進(jìn)程可以去做別的事，不用阻塞。當(dāng)內(nèi)核數(shù)據(jù)準(zhǔn)備好后，再通過SIGIO信號通知應(yīng)用進(jìn)程，數(shù)據(jù)準(zhǔn)備好后的可讀狀態(tài)。應(yīng)用用戶進(jìn)程收到信號之后，立即調(diào)用recvfrom，去讀取數(shù)據(jù)。

4.5 IO 模型之異步IO(AIO)

AIO實(shí)現(xiàn)了IO全流程的非阻塞，就是應(yīng)用進(jìn)程發(fā)出系統(tǒng)調(diào)用后，是立即返回的，但是立即返回的不是處理結(jié)果，而是表示提交成功類似的意思。等內(nèi)核數(shù)據(jù)準(zhǔn)備好，將數(shù)據(jù)拷貝到用戶進(jìn)程緩沖區(qū)，發(fā)送信號通知用戶進(jìn)程IO操作執(zhí)行完畢。

流程如下：

5. hystrix 工作原理

Hystrix 工作流程圖如下:

1. 構(gòu)建命令

Hystrix 提供了兩個(gè)命令對象：HystrixCommand和HystrixObservableCommand，它將代表你的一個(gè)依賴請求任務(wù)，向構(gòu)造函數(shù)中傳入請求依賴所需要的參數(shù)。

2. 執(zhí)行命令

有四種方式執(zhí)行Hystrix命令。分別是：

• R execute()：同步阻塞執(zhí)行的，從依賴請求中接收到單個(gè)響應(yīng)。
• Future queue()：異步執(zhí)行，返回一個(gè)包含單個(gè)響應(yīng)的Future對象。
• Observable observe()：創(chuàng)建Observable后會訂閱Observable，從依賴請求中返回代表響應(yīng)的Observable對象
• Observable toObservable()：cold observable，返回一個(gè)Observable，只有訂閱時(shí)才會執(zhí)行Hystrix命令，可以返回多個(gè)結(jié)果

3. 檢查響應(yīng)是否被緩存

如果啟用了 Hystrix緩存，任務(wù)執(zhí)行前將先判斷是否有相同命令執(zhí)行的緩存。如果有則直接返回包含緩存響應(yīng)的Observable；如果沒有緩存的結(jié)果，但啟動了緩存，將緩存本次執(zhí)行結(jié)果以供后續(xù)使用。

4. 檢查回路器是否打開 回路器(circuit-breaker)和保險(xiǎn)絲類似，保險(xiǎn)絲在發(fā)生危險(xiǎn)時(shí)將會燒斷以保護(hù)電路，而回路器可以在達(dá)到我們設(shè)定的閥值時(shí)觸發(fā)短路(比如請求失敗率達(dá)到50%)，拒絕執(zhí)行任何請求。

如果回路器被打開，Hystrix將不會執(zhí)行命令，直接進(jìn)入Fallback處理邏輯。

5. 檢查線程池/信號量/隊(duì)列情況 Hystrix 隔離方式有線程池隔離和信號量隔離。當(dāng)使用Hystrix線程池時(shí)，Hystrix 默認(rèn)為每個(gè)依賴服務(wù)分配10個(gè)線程，當(dāng)10個(gè)線程都繁忙時(shí)，將拒絕執(zhí)行命令,，而是立即跳到執(zhí)行fallback邏輯。

6. 執(zhí)行具體的任務(wù) 通過HystrixObservableCommand.construct() 或者 HystrixCommand.run() 來運(yùn)行用戶真正的任務(wù)。

7. 計(jì)算回路健康情況 每次開始執(zhí)行command、結(jié)束執(zhí)行command以及發(fā)生異常等情況時(shí)，都會記錄執(zhí)行情況，例如：成功、失敗、拒絕和超時(shí)等指標(biāo)情況，會定期處理這些數(shù)據(jù)，再根據(jù)設(shè)定的條件來判斷是否開啟回路器。

8. 命令失敗時(shí)執(zhí)行Fallback邏輯 在命令失敗時(shí)執(zhí)行用戶指定的 Fallback 邏輯。上圖中的斷路、線程池拒絕、信號量拒絕、執(zhí)行執(zhí)行、執(zhí)行超時(shí)都會進(jìn)入Fallback處理。

9. 返回執(zhí)行結(jié)果 原始對象結(jié)果將以O(shè)bservable形式返回，在返回給用戶之前，會根據(jù)調(diào)用方式的不同做一些處理。

6. 延時(shí)場景處理

日常開發(fā)中，我們經(jīng)常遇到這種業(yè)務(wù)場景，如：外賣訂單超30分鐘未支付，則自動取消訂單；用戶注冊成功15分鐘后，發(fā)短信消息通知用戶等等。這就是延時(shí)任務(wù)處理場景。針對此類場景我們主要有以下幾種處理方案：

• JDK的DelayQueue延遲隊(duì)列
• 時(shí)間輪算法
• 數(shù)據(jù)庫定時(shí)任務(wù)（如Quartz）
• Redis ZSet 實(shí)現(xiàn)
• MQ 延時(shí)隊(duì)列實(shí)現(xiàn)

7.https請求過程

• HTTPS = HTTP + SSL/TLS，即用SSL/TLS對數(shù)據(jù)進(jìn)行加密和解密，Http進(jìn)行傳輸。
• SSL，即Secure Sockets Layer（安全套接層協(xié)議），是網(wǎng)絡(luò)通信提供安全及數(shù)據(jù)完整性的一種安全協(xié)議。
• TLS，即Transport Layer Security(安全傳輸層協(xié)議)，它是SSL 3.0的后續(xù)版本。

1. 用戶在瀏覽器里輸入一個(gè)https網(wǎng)址，然后連接到server的443端口。
2. 服務(wù)器必須要有一套數(shù)字證書，可以自己制作，也可以向組織申請，區(qū)別就是自己頒發(fā)的證書需要客戶端驗(yàn)證通過。這套證書其實(shí)就是一對公鑰和私鑰。
3. 服務(wù)器將自己的數(shù)字證書（含有公鑰）發(fā)送給客戶端。
4. 客戶端收到服務(wù)器端的數(shù)字證書之后，會對其進(jìn)行檢查，如果不通過，則彈出警告框。如果證書沒問題，則生成一個(gè)密鑰（對稱加密），用證書的公鑰對它加密。
5. 客戶端會發(fā)起HTTPS中的第二個(gè)HTTP請求，將加密之后的客戶端密鑰發(fā)送給服務(wù)器。
6. 服務(wù)器接收到客戶端發(fā)來的密文之后，會用自己的私鑰對其進(jìn)行非對稱解密，解密之后得到客戶端密鑰，然后用客戶端密鑰對返回?cái)?shù)據(jù)進(jìn)行對稱加密，這樣數(shù)據(jù)就變成了密文。
7. 服務(wù)器將加密后的密文返回給客戶端。
8. 客戶端收到服務(wù)器發(fā)返回的密文，用自己的密鑰（客戶端密鑰）對其進(jìn)行對稱解密，得到服務(wù)器返回的數(shù)據(jù)。

8. 聊聊事務(wù)隔離級別，以及可重復(fù)讀實(shí)現(xiàn)原理

8.1 數(shù)據(jù)庫四大隔離級別

為了解決并發(fā)事務(wù)存在的臟讀、不可重復(fù)讀、幻讀等問題，數(shù)據(jù)庫大叔設(shè)計(jì)了四種隔離級別。分別是讀未提交，讀已提交，可重復(fù)讀，串行化（Serializable）。

• 讀未提交隔離級別：只限制了兩個(gè)數(shù)據(jù)不能同時(shí)修改，但是修改數(shù)據(jù)的時(shí)候，即使事務(wù)未提交，都是可以被別的事務(wù)讀取到的，這級別的事務(wù)隔離有臟讀、重復(fù)讀、幻讀的問題；
• 讀已提交隔離級別：當(dāng)前事務(wù)只能讀取到其他事務(wù)提交的數(shù)據(jù)，所以這種事務(wù)的隔離級別解決了臟讀問題，但還是會存在重復(fù)讀、幻讀問題；
• 可重復(fù)讀：限制了讀取數(shù)據(jù)的時(shí)候，不可以進(jìn)行修改，所以解決了重復(fù)讀的問題，但是讀取范圍數(shù)據(jù)的時(shí)候，是可以插入數(shù)據(jù)，所以還會存在幻讀問題；
• 串行化：事務(wù)最高的隔離級別，在該級別下，所有事務(wù)都是進(jìn)行串行化順序執(zhí)行的。可以避免臟讀、不可重復(fù)讀與幻讀所有并發(fā)問題。但是這種事務(wù)隔離級別下，事務(wù)執(zhí)行很耗性能。

四大隔離級別，都會存在哪些并發(fā)問題呢

8.2 Read View可見性規(guī)則

Read View的可見性規(guī)則如下：

1. 如果數(shù)據(jù)事務(wù)ID trx_id < min_limit_id，表明生成該版本的事務(wù)在生成Read View前，已經(jīng)提交(因?yàn)槭聞?wù)ID是遞增的)，所以該版本可以被當(dāng)前事務(wù)訪問。
2. 如果trx_id>= max_limit_id，表明生成該版本的事務(wù)在生成Read View后才生成，所以該版本不可以被當(dāng)前事務(wù)訪問。
3. 如果 min_limit_id =,需要分3種情況討論

• 1）如果m_ids包含trx_id,則代表Read View生成時(shí)刻，這個(gè)事務(wù)還未提交，但是如果數(shù)據(jù)的trx_id等于creator_trx_id的話，表明數(shù)據(jù)是自己生成的，因此是可見的。
• 2）如果m_ids包含trx_id，并且trx_id不等于creator_trx_id，則Read View生成時(shí)，事務(wù)未提交，并且不是自己生產(chǎn)的，所以當(dāng)前事務(wù)也是看不見的；
• 3）如果m_ids不包含trx_id，則說明你這個(gè)事務(wù)在Read View生成之前就已經(jīng)提交了，修改的結(jié)果，當(dāng)前事務(wù)是能看見的。

8.3 可重復(fù)讀實(shí)現(xiàn)原理

數(shù)據(jù)庫是通過加鎖實(shí)現(xiàn)隔離級別的，比如，你想一個(gè)人靜靜，不被別人打擾，你可以把自己關(guān)在房子，并在房門上加上一把鎖！串行化隔離級別就是加鎖實(shí)現(xiàn)的。但是如果頻繁加鎖，性能會下降。因此設(shè)計(jì)數(shù)據(jù)庫的大叔想到了MVCC。

可重復(fù)讀的實(shí)現(xiàn)原理就是MVCC多版本并發(fā)控制。在一個(gè)事務(wù)范圍內(nèi)，兩個(gè)相同的查詢，讀取同一條記錄，卻返回了不同的數(shù)據(jù)，這就是不可重復(fù)讀。可重復(fù)讀隔離級別，就是為了解決不可重復(fù)讀問題。

查詢一條記錄，基于MVCC，是怎樣的流程呢？

1. 獲取事務(wù)自己的版本號，即事務(wù)ID
2. 獲取Read View
3. 查詢得到的數(shù)據(jù)，然后Read View中的事務(wù)版本號進(jìn)行比較。
4. 如果不符合Read View的可見性規(guī)則， 即就需要Undo log中歷史快照;
5. 最后返回符合規(guī)則的數(shù)據(jù)

InnoDB 實(shí)現(xiàn)MVCC，是通過Read View+ Undo Log實(shí)現(xiàn)的，Undo Log保存了歷史快照，Read View可見性規(guī)則幫助判斷當(dāng)前版本的數(shù)據(jù)是否可見。

可重復(fù)讀（RR）隔離級別，是如何解決不可重復(fù)讀問題的？

假設(shè)存在事務(wù)A和B，SQL執(zhí)行流程如下

在可重復(fù)讀（RR）隔離級別下，一個(gè)事務(wù)里只會獲取一次read view，都是副本共用的，從而保證每次查詢的數(shù)據(jù)都是一樣的。

假設(shè)當(dāng)前有一張core_user表，插入一條初始化數(shù)據(jù),如下：

基于MVCC，我們來看看執(zhí)行流程

1. A開啟事務(wù)，首先得到一個(gè)事務(wù)ID為100
2. B開啟事務(wù)，得到事務(wù)ID為101
3. 事務(wù)A生成一個(gè)Read View，read view對應(yīng)的值如下

然后回到版本鏈：開始從版本鏈中挑選可見的記錄：

由圖可以看出，最新版本的列name的內(nèi)容是孫權(quán)，該版本的trx_id值為100。開始執(zhí)行read view可見性規(guī)則校驗(yàn)：

min_limit_id(100)=creator_trx_id?=?trx_id?=100;

由此可得，trx_id=100的這個(gè)記錄，當(dāng)前事務(wù)是可見的。所以查到是name為孫權(quán)的記錄。

4. 事務(wù)B進(jìn)行修改操作，把名字改為曹操。把原數(shù)據(jù)拷貝到undo log,然后對數(shù)據(jù)進(jìn)行修改，標(biāo)記事務(wù)ID和上一個(gè)數(shù)據(jù)版本在undo log的地址。

5. 事務(wù)B提交事務(wù)

6. 事務(wù)A再次執(zhí)行查詢操作，因?yàn)槭荝R（可重復(fù)讀）隔離級別，因此會復(fù)用老的Read View副本，Read View對應(yīng)的值如下

然后再次回到版本鏈：從版本鏈中挑選可見的記錄：

從圖可得，最新版本的列name的內(nèi)容是曹操，該版本的trx_id值為101。開始執(zhí)行read view可見性規(guī)則校驗(yàn)：

min_limit_id(100)=因?yàn)閙_ids{100,101}包含trx_id（101），
并且creator_trx_id?(100)?不等于trx_id（101）

所以，trx_id=101這個(gè)記錄，對于當(dāng)前事務(wù)是不可見的。這時(shí)候呢，版本鏈roll_pointer跳到下一個(gè)版本，trx_id=100這個(gè)記錄，再次校驗(yàn)是否可見：

min_limit_id(100)=因?yàn)閙_ids{100,101}包含trx_id（100），
并且creator_trx_id?(100)?等于trx_id（100）

所以，trx_id=100這個(gè)記錄，對于當(dāng)前事務(wù)是可見的，所以兩次查詢結(jié)果，都是name=孫權(quán)的那個(gè)記錄。即在可重復(fù)讀（RR）隔離級別下，復(fù)用老的Read View副本，解決了不可重復(fù)讀的問題。

9. 聊聊索引在哪些場景下會失效？

1. 查詢條件包含or，可能導(dǎo)致索引失效
2. 如何字段類型是字符串，where時(shí)一定用引號括起來，否則索引失效

3. like通配符可能導(dǎo)致索引失效。

4. 聯(lián)合索引，查詢時(shí)的條件列不是聯(lián)合索引中的第一個(gè)列，索引失效。

5. 在索引列上使用mysql的內(nèi)置函數(shù)，索引失效。

6. 對索引列運(yùn)算（如，+、-、*、/），索引失效。

7. 索引字段上使用（！= 或者 < >，not in）時(shí)，可能會導(dǎo)致索引失效。

8. 索引字段上使用is null， is not null，可能導(dǎo)致索引失效。

9. 左連接查詢或者右連接查詢查詢關(guān)聯(lián)的字段編碼格式不一樣，可能導(dǎo)致索引失效。

10. mysql估計(jì)使用全表掃描要比使用索引快,則不使用索引。


10. 什么是虛擬內(nèi)存

虛擬內(nèi)存，是虛擬出來的內(nèi)存，它的核心思想就是確保每個(gè)程序擁有自己的地址空間，地址空間被分成多個(gè)塊，每一塊都有連續(xù)的地址空間。同時(shí)物理空間也分成多個(gè)塊，塊大小和虛擬地址空間的塊大小一致，操作系統(tǒng)會自動將虛擬地址空間映射到物理地址空間，程序只需關(guān)注虛擬內(nèi)存，請求的也是虛擬內(nèi)存，真正使用卻是物理內(nèi)存。

現(xiàn)代操作系統(tǒng)使用虛擬內(nèi)存，即虛擬地址取代物理地址，使用虛擬內(nèi)存可以有2個(gè)好處：

• 虛擬內(nèi)存空間可以遠(yuǎn)遠(yuǎn)大于物理內(nèi)存空間
• 多個(gè)虛擬內(nèi)存可以指向同一個(gè)物理地址

零拷貝實(shí)現(xiàn)思想，就利用了虛擬內(nèi)存這個(gè)點(diǎn)：多個(gè)虛擬內(nèi)存可以指向同一個(gè)物理地址，可以把內(nèi)核空間和用戶空間的虛擬地址映射到同一個(gè)物理地址，這樣的話，就可以減少IO的數(shù)據(jù)拷貝次數(shù)啦，示意圖如下：

11. 排行榜的實(shí)現(xiàn)，比如高考成績排序

排行版的實(shí)現(xiàn)，一般使用redis的zset數(shù)據(jù)類型。

• 使用格式如下：

zadd?key?score?member?[score?member?...]，zrank?key?member

• 層內(nèi)部編碼：ziplist（壓縮列表）、skiplist（跳躍表）
• 使用場景如排行榜，社交需求（如用戶點(diǎn)贊）

實(shí)現(xiàn)demo如下：

12.分布式鎖實(shí)現(xiàn)

分布式鎖，是控制分布式系統(tǒng)不同進(jìn)程共同訪問共享資源的一種鎖的實(shí)現(xiàn)。秒殺下單、搶紅包等等業(yè)務(wù)場景，都需要用到分布式鎖，我們項(xiàng)目中經(jīng)常使用Redis作為分布式鎖。

選了Redis分布式鎖的幾種實(shí)現(xiàn)方法，大家來討論下，看有沒有啥問題哈。

• 命令setnx + expire分開寫
• setnx + value值是過期時(shí)間
• set的擴(kuò)展命令（set ex px nx）
• set ex px nx + 校驗(yàn)唯一隨機(jī)值,再刪除
• Redisson

12.1 命令setnx + expire分開寫

if（jedis.setnx(key,lock_value)?==?1）{?//加鎖
????expire（key，100）;?//設(shè)置過期時(shí)間
????try?{
????????do?something??//業(yè)務(wù)請求
????}catch(){
??}
??finally?{
???????jedis.del(key);?//釋放鎖
????}
}

如果執(zhí)行完setnx加鎖，正要執(zhí)行expire設(shè)置過期時(shí)間時(shí)，進(jìn)程crash掉或者要重啟維護(hù)了，那這個(gè)鎖就“長生不老”了，別的線程永遠(yuǎn)獲取不到鎖啦，所以分布式鎖不能這么實(shí)現(xiàn)。

12.2 setnx + value值是過期時(shí)間

long?expires?=?System.currentTimeMillis()?+?expireTime;?//系統(tǒng)時(shí)間+設(shè)置的過期時(shí)間
String?expiresStr?=?String.valueOf(expires);

//?如果當(dāng)前鎖不存在，返回加鎖成功
if?(jedis.setnx(key,?expiresStr)?==?1)?{
????????return?true;
}?
//?如果鎖已經(jīng)存在，獲取鎖的過期時(shí)間
String?currentValueStr?=?jedis.get(key);

//?如果獲取到的過期時(shí)間，小于系統(tǒng)當(dāng)前時(shí)間，表示已經(jīng)過期
if?(currentValueStr?!=?null?&&?Long.parseLong(currentValueStr)?
?????//?鎖已過期，獲取上一個(gè)鎖的過期時(shí)間，并設(shè)置現(xiàn)在鎖的過期時(shí)間（不了解redis的getSet命令的小伙伴，可以去官網(wǎng)看下哈）
????String?oldValueStr?=?jedis.getSet(key_resource_id,?expiresStr);
????
????if?(oldValueStr?!=?null?&&?oldValueStr.equals(currentValueStr))?{
?????????//?考慮多線程并發(fā)的情況，只有一個(gè)線程的設(shè)置值和當(dāng)前值相同，它才可以加鎖
?????????return?true;
????}
}
????????
//其他情況，均返回加鎖失敗
return?false;
}

筆者看過有開發(fā)小伙伴就是這么實(shí)現(xiàn)分布式鎖的，但是這種方案也有這些缺點(diǎn)：

• 過期時(shí)間是客戶端自己生成的，分布式環(huán)境下，每個(gè)客戶端的時(shí)間必須同步。
• 沒有保存持有者的唯一標(biāo)識，可能被別的客戶端釋放/解鎖。
• 鎖過期的時(shí)候，并發(fā)多個(gè)客戶端同時(shí)請求過來，都執(zhí)行了jedis.getSet()，最終只能有一個(gè)客戶端加鎖成功，但是該客戶端鎖的過期時(shí)間，可能被別的客戶端覆蓋。

12.3 set的擴(kuò)展命令（set ex px nx）（注意可能存在的問題）

if（jedis.set(key,?lock_value,?"NX",?"EX",?100s)?==?1）{?//加鎖
????try?{
????????do?something??//業(yè)務(wù)處理
????}catch(){
??}
??finally?{
???????jedis.del(key);?//釋放鎖
????}
}

這個(gè)方案可能存在這樣的問題：

• 鎖過期釋放了，業(yè)務(wù)還沒執(zhí)行完。
• 鎖被別的線程誤刪。

12.4 set ex px nx + 校驗(yàn)唯一隨機(jī)值,再刪除

if（jedis.set(key,?uni_request_id,?"NX",?"EX",?100s)?==?1）{?//加鎖
????try?{
????????do?something??//業(yè)務(wù)處理
????}catch(){
??}
??finally?{
???????//判斷是不是當(dāng)前線程加的鎖,是才釋放
???????if?(uni_request_id.equals(jedis.get(key)))?{
????????jedis.del(key);?//釋放鎖
????????}
????}
}

在這里，判斷當(dāng)前線程加的鎖和釋放鎖是不是一個(gè)原子操作。如果調(diào)用jedis.del()釋放鎖的時(shí)候，可能這把鎖已經(jīng)不屬于當(dāng)前客戶端，會解除他人加的鎖。

一般也是用lua腳本代替。lua腳本如下：

if?redis.call('get',KEYS[1])?==?ARGV[1]?then?
???return?redis.call('del',KEYS[1])?
else
???return?0
end;

這種方式比較不錯(cuò)了，一般情況下，已經(jīng)可以使用這種實(shí)現(xiàn)方式。但是存在鎖過期釋放了，業(yè)務(wù)還沒執(zhí)行完的問題（實(shí)際上，估算個(gè)業(yè)務(wù)處理的時(shí)間，一般沒啥問題了）。

12.5 Redisson

分布式鎖可能存在鎖過期釋放，業(yè)務(wù)沒執(zhí)行完的問題。有些小伙伴認(rèn)為，稍微把鎖過期時(shí)間設(shè)置長一些就可以啦。其實(shí)我們設(shè)想一下，是否可以給獲得鎖的線程，開啟一個(gè)定時(shí)守護(hù)線程，每隔一段時(shí)間檢查鎖是否還存在，存在則對鎖的過期時(shí)間延長，防止鎖過期提前釋放。

當(dāng)前開源框架Redisson就解決了這個(gè)分布式鎖問題。我們一起來看下Redisson底層原理是怎樣的吧：

只要線程一加鎖成功，就會啟動一個(gè)watch dog看門狗，它是一個(gè)后臺線程，會每隔10秒檢查一下，如果線程1還持有鎖，那么就會不斷的延長鎖key的生存時(shí)間。因此，Redisson就是使用Redisson解決了鎖過期釋放，業(yè)務(wù)沒執(zhí)行完問題。

13. 零拷貝

零拷貝就是不需要將數(shù)據(jù)從一個(gè)存儲區(qū)域復(fù)制到另一個(gè)存儲區(qū)域。它是指在傳統(tǒng)IO模型中，指CPU拷貝的次數(shù)為0。它是IO的優(yōu)化方案

• 傳統(tǒng)IO流程
• 零拷貝實(shí)現(xiàn)之mmap+write
• 零拷貝實(shí)現(xiàn)之sendfile
• 零拷貝實(shí)現(xiàn)之帶有DMA收集拷貝功能的sendfile

13.1 傳統(tǒng)IO流程

流程圖如下：

• 用戶應(yīng)用進(jìn)程調(diào)用read函數(shù)，向操作系統(tǒng)發(fā)起IO調(diào)用，上下文從用戶態(tài)轉(zhuǎn)為內(nèi)核態(tài)（切換1）
• DMA控制器把數(shù)據(jù)從磁盤中，讀取到內(nèi)核緩沖區(qū)。
• CPU把內(nèi)核緩沖區(qū)數(shù)據(jù)，拷貝到用戶應(yīng)用緩沖區(qū)，上下文從內(nèi)核態(tài)轉(zhuǎn)為用戶態(tài)（切換2），read函數(shù)返回
• 用戶應(yīng)用進(jìn)程通過write函數(shù)，發(fā)起IO調(diào)用，上下文從用戶態(tài)轉(zhuǎn)為內(nèi)核態(tài)（切換3）
• CPU將應(yīng)用緩沖區(qū)中的數(shù)據(jù)，拷貝到socket緩沖區(qū)
• DMA控制器把數(shù)據(jù)從socket緩沖區(qū)，拷貝到網(wǎng)卡設(shè)備，上下文從內(nèi)核態(tài)切換回用戶態(tài)（切換4），write函數(shù)返回

從流程圖可以看出，傳統(tǒng)IO的讀寫流程，包括了4次上下文切換（4次用戶態(tài)和內(nèi)核態(tài)的切換），4次數(shù)據(jù)拷貝（兩次CPU拷貝以及兩次的DMA拷貝)。

13.2 mmap+write實(shí)現(xiàn)的零拷貝

mmap 的函數(shù)原型如下：

void?*mmap(void?*addr,?size_t?length,?int?prot,?int?flags,?int?fd,?off_t?offset);

• addr：指定映射的虛擬內(nèi)存地址
• length：映射的長度
• prot：映射內(nèi)存的保護(hù)模式
• flags：指定映射的類型
• fd:進(jìn)行映射的文件句柄
• offset:文件偏移量

mmap使用了虛擬內(nèi)存，可以把內(nèi)核空間和用戶空間的虛擬地址映射到同一個(gè)物理地址，從而減少數(shù)據(jù)拷貝次數(shù)！

mmap+write實(shí)現(xiàn)的零拷貝流程如下：

• 用戶進(jìn)程通過mmap方法向操作系統(tǒng)內(nèi)核發(fā)起IO調(diào)用，上下文從用戶態(tài)切換為內(nèi)核態(tài)。
• CPU利用DMA控制器，把數(shù)據(jù)從硬盤中拷貝到內(nèi)核緩沖區(qū)。
• 上下文從內(nèi)核態(tài)切換回用戶態(tài)，mmap方法返回。
• 用戶進(jìn)程通過write方法向操作系統(tǒng)內(nèi)核發(fā)起IO調(diào)用，上下文從用戶態(tài)切換為內(nèi)核態(tài)。
• CPU將內(nèi)核緩沖區(qū)的數(shù)據(jù)拷貝到的socket緩沖區(qū)。
• CPU利用DMA控制器，把數(shù)據(jù)從socket緩沖區(qū)拷貝到網(wǎng)卡，上下文從內(nèi)核態(tài)切換回用戶態(tài)，write調(diào)用返回。

可以發(fā)現(xiàn)，mmap+write實(shí)現(xiàn)的零拷貝，I/O發(fā)生了4次用戶空間與內(nèi)核空間的上下文切換，以及3次數(shù)據(jù)拷貝。其中3次數(shù)據(jù)拷貝中，包括了2次DMA拷貝和1次CPU拷貝。

mmap是將讀緩沖區(qū)的地址和用戶緩沖區(qū)的地址進(jìn)行映射，內(nèi)核緩沖區(qū)和應(yīng)用緩沖區(qū)共享，所以節(jié)省了一次CPU拷貝‘’并且用戶進(jìn)程內(nèi)存是虛擬的，只是映射到內(nèi)核的讀緩沖區(qū)，可以節(jié)省一半的內(nèi)存空間。

sendfile實(shí)現(xiàn)的零拷貝

sendfile是Linux2.1內(nèi)核版本后引入的一個(gè)系統(tǒng)調(diào)用函數(shù)，API如下：

ssize_t?sendfile(int?out_fd,?int?in_fd,?off_t?*offset,?size_t?count);

• out_fd:為待寫入內(nèi)容的文件描述符，一個(gè)socket描述符。，
• in_fd:為待讀出內(nèi)容的文件描述符，必須是真實(shí)的文件，不能是socket和管道。
• offset：指定從讀入文件的哪個(gè)位置開始讀，如果為NULL，表示文件的默認(rèn)起始位置。
• count：指定在fdout和fdin之間傳輸?shù)淖止?jié)數(shù)。

sendfile表示在兩個(gè)文件描述符之間傳輸數(shù)據(jù)，它是在操作系統(tǒng)內(nèi)核中操作的，避免了數(shù)據(jù)從內(nèi)核緩沖區(qū)和用戶緩沖區(qū)之間的拷貝操作，因此可以使用它來實(shí)現(xiàn)零拷貝。

sendfile實(shí)現(xiàn)的零拷貝流程如下：

1. 用戶進(jìn)程發(fā)起sendfile系統(tǒng)調(diào)用，上下文（切換1）從用戶態(tài)轉(zhuǎn)向內(nèi)核態(tài)
2. DMA控制器，把數(shù)據(jù)從硬盤中拷貝到內(nèi)核緩沖區(qū)。
3. CPU將讀緩沖區(qū)中數(shù)據(jù)拷貝到socket緩沖區(qū)
4. DMA控制器，異步把數(shù)據(jù)從socket緩沖區(qū)拷貝到網(wǎng)卡，
5. 上下文（切換2）從內(nèi)核態(tài)切換回用戶態(tài)，sendfile調(diào)用返回。

可以發(fā)現(xiàn)，sendfile實(shí)現(xiàn)的零拷貝，I/O發(fā)生了2次用戶空間與內(nèi)核空間的上下文切換，以及3次數(shù)據(jù)拷貝。其中3次數(shù)據(jù)拷貝中，包括了2次DMA拷貝和1次CPU拷貝。那能不能把CPU拷貝的次數(shù)減少到0次呢？有的，即帶有DMA收集拷貝功能的sendfile！

sendfile+DMA scatter/gather實(shí)現(xiàn)的零拷貝

linux 2.4版本之后，對sendfile做了優(yōu)化升級，引入SG-DMA技術(shù)，其實(shí)就是對DMA拷貝加入了scatter/gather操作，它可以直接從內(nèi)核空間緩沖區(qū)中將數(shù)據(jù)讀取到網(wǎng)卡。使用這個(gè)特點(diǎn)搞零拷貝，即還可以多省去一次CPU拷貝。

sendfile+DMA scatter/gather實(shí)現(xiàn)的零拷貝流程如下：

1. 用戶進(jìn)程發(fā)起sendfile系統(tǒng)調(diào)用，上下文（切換1）從用戶態(tài)轉(zhuǎn)向內(nèi)核態(tài)
2. DMA控制器，把數(shù)據(jù)從硬盤中拷貝到內(nèi)核緩沖區(qū)。
3. CPU把內(nèi)核緩沖區(qū)中的文件描述符信息（包括內(nèi)核緩沖區(qū)的內(nèi)存地址和偏移量）發(fā)送到socket緩沖區(qū)
4. DMA控制器根據(jù)文件描述符信息，直接把數(shù)據(jù)從內(nèi)核緩沖區(qū)拷貝到網(wǎng)卡
5. 上下文（切換2）從內(nèi)核態(tài)切換回用戶態(tài)，sendfile調(diào)用返回。

可以發(fā)現(xiàn)，sendfile+DMA scatter/gather實(shí)現(xiàn)的零拷貝，I/O發(fā)生了2次用戶空間與內(nèi)核空間的上下文切換，以及2次數(shù)據(jù)拷貝。其中2次數(shù)據(jù)拷貝都是包DMA拷貝。這就是真正的 零拷貝（Zero-copy) 技術(shù)，全程都沒有通過CPU來搬運(yùn)數(shù)據(jù)，所有的數(shù)據(jù)都是通過DMA來進(jìn)行傳輸?shù)摹?/p>

14. synchronized

synchronized是Java中的關(guān)鍵字，是一種同步鎖。synchronized關(guān)鍵字可以作用于方法或者代碼塊。

一般面試時(shí)。可以這么回答：

• 反編譯后，monitorenter、monitorexit、ACC_SYNCHRONIZED
• monitor監(jiān)視器
• Java Monitor 的工作機(jī)理
• 對象與monitor關(guān)聯(lián)

14.1 monitorenter、monitorexit、ACC_SYNCHRONIZED

如果synchronized作用于代碼塊，反編譯可以看到兩個(gè)指令：monitorenter、monitorexit，JVM使用monitorenter和monitorexit兩個(gè)指令實(shí)現(xiàn)同步；如果作用synchronized作用于方法,反編譯可以看到ACCSYNCHRONIZED標(biāo)記，JVM通過在方法訪問標(biāo)識符(flags)中加入ACCSYNCHRONIZED來實(shí)現(xiàn)同步功能。

• 同步代碼塊是通過monitorenter和monitorexit來實(shí)現(xiàn)，當(dāng)線程執(zhí)行到monitorenter的時(shí)候要先獲得monitor鎖，才能執(zhí)行后面的方法。當(dāng)線程執(zhí)行到monitorexit的時(shí)候則要釋放鎖。
• 同步方法是通過中設(shè)置ACCSYNCHRONIZED標(biāo)志來實(shí)現(xiàn)，當(dāng)線程執(zhí)行有ACCSYNCHRONIZED標(biāo)志的方法，需要獲得monitor鎖。每個(gè)對象都與一個(gè)monitor相關(guān)聯(lián)，線程可以占有或者釋放monitor。

14.2 monitor監(jiān)視器

monitor是什么呢？操作系統(tǒng)的管程（monitors）是概念原理，ObjectMonitor是它的原理實(shí)現(xiàn)。

在Java虛擬機(jī)（HotSpot）中，Monitor（管程）是由ObjectMonitor實(shí)現(xiàn)的，其主要數(shù)據(jù)結(jié)構(gòu)如下：

?ObjectMonitor()?{
????_header???????=?NULL;
????_count????????=?0;?//?記錄個(gè)數(shù)
????_waiters??????=?0,
????_recursions???=?0;
????_object???????=?NULL;
????_owner????????=?NULL;
????_WaitSet??????=?NULL;??//?處于wait狀態(tài)的線程，會被加入到_WaitSet
????_WaitSetLock??=?0?;
????_Responsible??=?NULL?;
????_succ?????????=?NULL?;
????_cxq??????????=?NULL?;
????FreeNext??????=?NULL?;
????_EntryList????=?NULL?;??//?處于等待鎖block狀態(tài)的線程，會被加入到該列表
????_SpinFreq?????=?0?;
????_SpinClock????=?0?;
????OwnerIsThread?=?0?;
??}

ObjectMonitor中幾個(gè)關(guān)鍵字段的含義如圖所示：

14.3 Java Monitor 的工作機(jī)理

• 想要獲取monitor的線程,首先會進(jìn)入_EntryList隊(duì)列。
• 當(dāng)某個(gè)線程獲取到對象的monitor后,進(jìn)入Owner區(qū)域，設(shè)置為當(dāng)前線程,同時(shí)計(jì)數(shù)器count加1。
• 如果線程調(diào)用了wait()方法，則會進(jìn)入WaitSet隊(duì)列。它會釋放monitor鎖，即將owner賦值為null,count自減1,進(jìn)入WaitSet隊(duì)列阻塞等待。
• 如果其他線程調(diào)用 notify() / notifyAll() ，會喚醒WaitSet中的某個(gè)線程，該線程再次嘗試獲取monitor鎖，成功即進(jìn)入Owner區(qū)域。
• 同步方法執(zhí)行完畢了，線程退出臨界區(qū)，會將monitor的owner設(shè)為null，并釋放監(jiān)視鎖。

14.4 對象與monitor關(guān)聯(lián)

• 在HotSpot虛擬機(jī)中,對象在內(nèi)存中存儲的布局可以分為3塊區(qū)域：對象頭（Header），實(shí)例數(shù)據(jù)（Instance Data）和對象填充（Padding）。
• 對象頭主要包括兩部分?jǐn)?shù)據(jù)：Mark Word（標(biāo)記字段）、Class Pointer（類型指針）。

Mark Word 是用于存儲對象自身的運(yùn)行時(shí)數(shù)據(jù)，如哈希碼（HashCode）、GC分代年齡、鎖狀態(tài)標(biāo)志、線程持有的鎖、偏向線程 ID、偏向時(shí)間戳等。

重量級鎖，指向互斥量的指針。其實(shí)synchronized是重量級鎖，也就是說Synchronized的對象鎖，Mark Word鎖標(biāo)識位為10，其中指針指向的是Monitor對象的起始地址。

15. 分布式id生成方案有哪些？什么是雪花算法？

分布式id生成方案主要有：

• UUID
• 數(shù)據(jù)庫自增ID
• 基于雪花算法（Snowflake）實(shí)現(xiàn)
• 百度 （Uidgenerator）
• 美團(tuán)（Leaf）

什么是雪花算法？

雪花算法是一種生成分布式全局唯一ID的算法，生成的ID稱為Snowflake IDs。這種算法由Twitter創(chuàng)建，并用于推文的ID。

一個(gè)Snowflake ID有64位。

• 第1位：Java中l(wèi)ong的最高位是符號位代表正負(fù)，正數(shù)是0，負(fù)數(shù)是1，一般生成ID都為正數(shù)，所以默認(rèn)為0。
• 接下來前41位是時(shí)間戳，表示了自選定的時(shí)期以來的毫秒數(shù)。
• 接下來的10位代表計(jì)算機(jī)ID，防止沖突。
• 其余12位代表每臺機(jī)器上生成ID的序列號，這允許在同一毫秒內(nèi)創(chuàng)建多個(gè)Snowflake ID。

推薦閱讀：

常見消息中間件大 PK

為什么CTO不寫代碼，還這么牛逼？

歡迎關(guān)注微信公眾號：互聯(lián)網(wǎng)全棧架構(gòu)，收取更多有價(jià)值的信息。