蝦皮 Java 后端面試 15 連問

前言

大家好，我是 Guide，最近有位讀者去蝦皮面試?yán)?，分享一下面試的真題~

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

1. 排序鏈表

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

實例 1：

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

實例 2：

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

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

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

完整代碼如下：

class?Solution?{
????public?ListNode?sortList(ListNode?head)?{
????????//如果鏈表為空，或者只有一個節(jié)點，直接返回即可，不用排序
????????if?(head?==?null?||?head.next?==?null)
????????????return?head;

????????//快慢指針移動，以尋找到中間節(jié)點
????????ListNode?slow?=?head;
????????ListNode?fast?=?head;
????????while(fast.next!=null?&&?fast.next.next?!=null){
??????????fast?=?fast.next.next;
??????????slow?=?slow.next;
????????}
????????//找到中間節(jié)點，slow節(jié)點的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等。

非對稱加密算法：非對稱加密算法需要兩個密鑰（公開密鑰和私有密鑰）。公鑰與私鑰是成對存在的，如果用公鑰對數(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ù)傳輸不出差錯。
• 再次，TCP 的可靠性，還體現(xiàn)在可控制。它有報文校驗、ACK 應(yīng)答、超時重傳(發(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)備好，可以先返回錯誤信息給用戶進(jìn)程，讓它不需要等待，而是通過輪詢的方式再來請求。這就是非阻塞 IO，流程圖如下：

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

IO 多路復(fù)用之 select

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

select 有幾個缺點：

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

IO 多路復(fù)用之 epoll

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

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

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

信號驅(qū)動 IO 不再用主動詢問的方式去確認(rèn)數(shù)據(jù)是否就緒，而是向內(nèi)核發(fā)送一個信號（調(diào)用 sigaction 的時候建立一個 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 實現(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 提供了兩個命令對象：HystrixCommand 和 HystrixObservableCommand，它將代表你的一個依賴請求任務(wù)，向構(gòu)造函數(shù)中傳入請求依賴所需要的參數(shù)。

2. 執(zhí)行命令

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

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

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

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

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

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

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

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

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

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

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

6. 延時場景處理

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

• JDK 的 DelayQueue 延遲隊列
• 時間輪算法
• 數(shù)據(jù)庫定時任務(wù)（如 Quartz）
• Redis ZSet 實現(xiàn)
• MQ 延時隊列實現(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. 用戶在瀏覽器里輸入一個 https 網(wǎng)址，然后連接到 server 的 443 端口。
2. 服務(wù)器必須要有一套數(shù)字證書，可以自己制作，也可以向組織申請，區(qū)別就是自己頒發(fā)的證書需要客戶端驗證通過。這套證書其實就是一對公鑰和私鑰。
3. 服務(wù)器將自己的數(shù)字證書（含有公鑰）發(fā)送給客戶端。
4. 客戶端收到服務(wù)器端的數(shù)字證書之后，會對其進(jìn)行檢查，如果不通過，則彈出警告框。如果證書沒問題，則生成一個密鑰（對稱加密），用證書的公鑰對它加密。
5. 客戶端會發(fā)起 HTTPS 中的第二個 HTTP 請求，將加密之后的客戶端密鑰發(fā)送給服務(wù)器。
6. 服務(wù)器接收到客戶端發(fā)來的密文之后，會用自己的私鑰對其進(jìn)行非對稱解密，解密之后得到客戶端密鑰，然后用客戶端密鑰對返回數(shù)據(jù)進(jìn)行對稱加密，這樣數(shù)據(jù)就變成了密文。
7. 服務(wù)器將加密后的密文返回給客戶端。
8. 客戶端收到服務(wù)器發(fā)返回的密文，用自己的密鑰（客戶端密鑰）對其進(jìn)行對稱解密，得到服務(wù)器返回的數(shù)據(jù)。

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

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

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

• 讀未提交隔離級別：只限制了兩個數(shù)據(jù)不能同時修改，但是修改數(shù)據(jù)的時候，即使事務(wù)未提交，都是可以被別的事務(wù)讀取到的，這級別的事務(wù)隔離有臟讀、重復(fù)讀、幻讀的問題；
• 讀已提交隔離級別：當(dāng)前事務(wù)只能讀取到其他事務(wù)提交的數(shù)據(jù)，所以這種事務(wù)的隔離級別解決了臟讀問題，但還是會存在重復(fù)讀、幻讀問題；
• 可重復(fù)讀：限制了讀取數(shù)據(jù)的時候，不可以進(jìn)行修改，所以解決了重復(fù)讀的問題，但是讀取范圍數(shù)據(jù)的時候，是可以插入數(shù)據(jù)，所以還會存在幻讀問題；
• 串行化：事務(wù)最高的隔離級別，在該級別下，所有事務(wù)都是進(jìn)行串行化順序執(zhí)行的?？梢员苊馀K讀、不可重復(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)提交(因為事務(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生成時刻，這個事務(wù)還未提交，但是如果數(shù)據(jù)的trx_id等于creator_trx_id的話，表明數(shù)據(jù)是自己生成的，因此是可見的。
• 2）如果m_ids包含trx_id，并且trx_id不等于creator_trx_id，則Read View生成時，事務(wù)未提交，并且不是自己生產(chǎn)的，所以當(dāng)前事務(wù)也是看不見的；
• 3）如果m_ids不包含trx_id，則說明你這個事務(wù)在Read View生成之前就已經(jīng)提交了，修改的結(jié)果，當(dāng)前事務(wù)是能看見的。

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

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

可重復(fù)讀的實現(xiàn)原理就是MVCC 多版本并發(fā)控制。在一個事務(wù)范圍內(nèi)，兩個相同的查詢，讀取同一條記錄，卻返回了不同的數(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 實現(xiàn)MVCC，是通過Read View+ Undo Log實現(xiàn)的，Undo Log保存了歷史快照，Read View可見性規(guī)則幫助判斷當(dāng)前版本的數(shù)據(jù)是否可見。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

min_limit_id(100)=因為m_ids{100,101}包含trx_id（101），
并且creator_trx_id?(100)?不等于trx_id（101）

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

min_limit_id(100)=因為m_ids{100,101}包含trx_id（100），
并且creator_trx_id?(100)?等于trx_id（100）

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

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

1. 查詢條件包含 or，可能導(dǎo)致索引失效
2. 如何字段類型是字符串，where 時一定用引號括起來，否則索引失效
3. like 通配符可能導(dǎo)致索引失效。
4. 聯(lián)合索引，查詢時的條件列不是聯(lián)合索引中的第一個列，索引失效。
5. 在索引列上使用 mysql 的內(nèi)置函數(shù)，索引失效。
6. 對索引列運算（如，+、-、*、/），索引失效。
7. 索引字段上使用（！= 或者 < >，not in）時，可能會導(dǎo)致索引失效。
8. 索引字段上使用 is null， is not null，可能導(dǎo)致索引失效。
9. 左連接查詢或者右連接查詢查詢關(guān)聯(lián)的字段編碼格式不一樣，可能導(dǎo)致索引失效。
10. mysql 估計使用全表掃描要比使用索引快,則不使用索引。

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

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

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

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

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

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

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

• 使用格式如下：

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

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

實現(xiàn) demo 如下：

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

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

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

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

12.1 命令 setnx + expire 分開寫

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

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

12.2 setnx + value 值是過期時間

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

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

//?如果獲取到的過期時間，小于系統(tǒng)當(dāng)前時間，表示已經(jīng)過期
if?(currentValueStr?!=?null?&&?Long.parseLong(currentValueStr)?
?????//?鎖已過期，獲取上一個鎖的過期時間，并設(shè)置現(xiàn)在鎖的過期時間（不了解redis的getSet命令的小伙伴，可以去官網(wǎng)看下哈）
????String?oldValueStr?=?jedis.getSet(key_resource_id,?expiresStr);

????if?(oldValueStr?!=?null?&&?oldValueStr.equals(currentValueStr))?{
?????????//?考慮多線程并發(fā)的情況，只有一個線程的設(shè)置值和當(dāng)前值相同，它才可以加鎖
?????????return?true;
????}
}

//其他情況，均返回加鎖失敗
return?false;
}

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

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

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);?//釋放鎖
????}
}

這個方案可能存在這樣的問題：

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

12.4 set ex px nx + 校驗唯一隨機(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)前線程加的鎖和釋放鎖是不是一個原子操作。如果調(diào)用 jedis.del()釋放鎖的時候，可能這把鎖已經(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;

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

12.5 Redisson

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

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

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

13. 零拷貝

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

• 傳統(tǒng) IO 流程
• 零拷貝實現(xiàn)之 mmap+write
• 零拷貝實現(xiàn)之 sendfile
• 零拷貝實現(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 實現(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)核空間和用戶空間的虛擬地址映射到同一個物理地址，從而減少數(shù)據(jù)拷貝次數(shù)！

mmap+write實現(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實現(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 實現(xiàn)的零拷貝

sendfile是 Linux2.1 內(nèi)核版本后引入的一個系統(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)容的文件描述符，一個 socket 描述符。，
• in_fd:為待讀出內(nèi)容的文件描述符，必須是真實的文件，不能是 socket 和管道。
• offset：指定從讀入文件的哪個位置開始讀，如果為 NULL，表示文件的默認(rèn)起始位置。
• count：指定在 fdout 和 fdin 之間傳輸?shù)淖止?jié)數(shù)。

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

sendfile 實現(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實現(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 實現(xiàn)的零拷貝

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

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

14. synchronized

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

一般面試時?？梢赃@么回答：

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

14.1 monitorenter、monitorexit、ACC_SYNCHRONIZED

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

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

14.2 monitor 監(jiān)視器

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

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

?ObjectMonitor()?{
????_header???????=?NULL;
????_count????????=?0;?//?記錄個數(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 中幾個關(guān)鍵字段的含義如圖所示：

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

• 想要獲取 monitor 的線程,首先會進(jìn)入_EntryList 隊列。
• 當(dāng)某個線程獲取到對象的 monitor 后,進(jìn)入 Owner 區(qū)域，設(shè)置為當(dāng)前線程,同時計數(shù)器 count 加 1。
• 如果線程調(diào)用了 wait()方法，則會進(jìn)入 WaitSet 隊列。它會釋放 monitor 鎖，即將 owner 賦值為 null,count 自減 1,進(jìn)入 WaitSet 隊列阻塞等待。
• 如果其他線程調(diào)用 notify() / notifyAll() ，會喚醒 WaitSet 中的某個線程，該線程再次嘗試獲取 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ù)據(jù)（Instance Data）和對象填充（Padding）。
• 對象頭主要包括兩部分?jǐn)?shù)據(jù)：Mark Word（標(biāo)記字段）、Class Pointer（類型指針）。

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

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

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

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

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

什么是雪花算法？

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

一個 Snowflake ID 有 64 位元。

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