在面試之前多看看有關(guān)公司的面試資料，對(duì)之后的面試會(huì)很有幫助。今天就給大家分享15道蝦皮服務(wù)端的面試真題（附答案解析），快來看看自己的水平到底如何吧，希望能幫助到大家！

1. 排序鏈表

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

實(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;                  //快慢指針移動(dòng)，以尋找到中間節(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.對(duì)稱與非對(duì)稱加密算法的區(qū)別

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

• 明文：指沒有經(jīng)過加密的信息/數(shù)據(jù)。

• 密文：明文被加密算法加密之后，會(huì)變成密文，以確保數(shù)據(jù)安全。

• 密鑰：是一種參數(shù)，它是在明文轉(zhuǎn)換為密文或?qū)⒚芪霓D(zhuǎn)換為明文的算法中輸入的參數(shù)。密鑰分為對(duì)稱密鑰與非對(duì)稱密鑰。

• 加密：將明文變成密文的過程。

• 解密：將密文還原為明文的過程。

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

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

3. TCP如何保證可靠性

• 首先，TCP的連接是基于三次握手，而斷開則是四次揮手。確保連接和斷開的可靠性。

• 其次，TCP的可靠性，還體現(xiàn)在有狀態(tài);TCP會(huì)記錄哪些數(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ù)、流量控制（滑動(dòng)窗口）和擁塞控制等機(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)程，讓它不需要等待，而是通過輪詢的方式再來請(qǐng)求。這就是非阻塞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ù)就會(huì)返回可讀狀態(tài)，這時(shí)應(yīng)用進(jìn)程再發(fā)起recvfrom請(qǐng)求去讀取數(shù)據(jù)。

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

• 最大連接數(shù)有限，在Linux系統(tǒng)上一般為1024。

• select函數(shù)返回后，是通過遍歷fdset，找到就緒的描述符fd。

IO多路復(fù)用之epoll

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

epoll先通過epoll_ctl()來注冊(cè)一個(gè)fd（文件描述符），一旦基于某個(gè)fd就緒時(shí)，內(nèi)核會(huì)采用回調(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模型之信號(hào)驅(qū)動(dòng)模型

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

流程如下：

5. hystrix 工作原理

Hystrix 工作流程圖如下:

1、構(gòu)建命令

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

2、執(zhí)行命令

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

• R execute()：同步阻塞執(zhí)行的，從依賴請(qǐng)求中接收到單個(gè)響應(yīng)。

• Future queue()：異步執(zhí)行，返回一個(gè)包含單個(gè)響應(yīng)的Future對(duì)象。

• Observable observe()：創(chuàng)建Observable后會(huì)訂閱Observable，從依賴請(qǐng)求中返回代表響應(yīng)的Observable對(duì)象

• Observable toObservable()：cold observable，返回一個(gè)Observable，只有訂閱時(shí)才會(huì)執(zhí)行Hystrix命令，可以返回多個(gè)結(jié)果

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

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

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

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

5、檢查線程池/信號(hào)量/隊(duì)列情況 Hystrix 隔離方式有線程池隔離和信號(hào)量隔離。當(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í)，都會(huì)記錄執(zhí)行情況，例如：成功、失敗、拒絕和超時(shí)等指標(biāo)情況，會(huì)定期處理這些數(shù)據(jù)，再根據(jù)設(shè)定的條件來判斷是否開啟回路器。

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

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

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

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

• JDK的DelayQueue延遲隊(duì)列

• 時(shí)間輪算法

• 數(shù)據(jù)庫定時(shí)任務(wù)（如Quartz）

• Redis ZSet 實(shí)現(xiàn)

• MQ 延時(shí)隊(duì)列實(shí)現(xiàn)

7.https請(qǐng)求過程

• HTTPS = HTTP + SSL/TLS，即用SSL/TLS對(duì)數(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ù)版本。

http請(qǐng)求流程

1、用戶在瀏覽器里輸入一個(gè)https網(wǎng)址，然后連接到server的443端口。

2、服務(wù)器必須要有一套數(shù)字證書，可以自己制作，也可以向組織申請(qǐng)，區(qū)別就是自己頒發(fā)的證書需要客戶端驗(yàn)證通過。這套證書其實(shí)就是一對(duì)公鑰和私鑰。

3、服務(wù)器將自己的數(shù)字證書（含有公鑰）發(fā)送給客戶端。

4、客戶端收到服務(wù)器端的數(shù)字證書之后，會(huì)對(duì)其進(jìn)行檢查，如果不通過，則彈出警告框。如果證書沒問題，則生成一個(gè)密鑰（對(duì)稱加密），用證書的公鑰對(duì)它加密。

5、客戶端會(huì)發(fā)起HTTPS中的第二個(gè)HTTP請(qǐng)求，將加密之后的客戶端密鑰發(fā)送給服務(wù)器。

6、服務(wù)器接收到客戶端發(fā)來的密文之后，會(huì)用自己的私鑰對(duì)其進(jìn)行非對(duì)稱解密，解密之后得到客戶端密鑰，然后用客戶端密鑰對(duì)返回?cái)?shù)據(jù)進(jìn)行對(duì)稱加密，這樣數(shù)據(jù)就變成了密文。

7、服務(wù)器將加密后的密文返回給客戶端。

8、客戶端收到服務(wù)器發(fā)返回的密文，用自己的密鑰（客戶端密鑰）對(duì)其進(jìn)行對(duì)稱解密，得到服務(wù)器返回的數(shù)據(jù)。

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

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

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

• 讀未提交隔離級(jí)別：只限制了兩個(gè)數(shù)據(jù)不能同時(shí)修改，但是修改數(shù)據(jù)的時(shí)候，即使事務(wù)未提交，都是可以被別的事務(wù)讀取到的，這級(jí)別的事務(wù)隔離有臟讀、重復(fù)讀、幻讀的問題；

• 讀已提交隔離級(jí)別：當(dāng)前事務(wù)只能讀取到其他事務(wù)提交的數(shù)據(jù)，所以這種事務(wù)的隔離級(jí)別解決了臟讀問題，但還是會(huì)存在重復(fù)讀、幻讀問題；

• 可重復(fù)讀：限制了讀取數(shù)據(jù)的時(shí)候，不可以進(jìn)行修改，所以解決了重復(fù)讀的問題，但是讀取范圍數(shù)據(jù)的時(shí)候，是可以插入數(shù)據(jù)，所以還會(huì)存在幻讀問題；

• 串行化：事務(wù)最高的隔離級(jí)別，在該級(jí)別下，所有事務(wù)都是進(jìn)行串行化順序執(zhí)行的?？梢员苊馀K讀、不可重復(fù)讀與幻讀所有并發(fā)問題。但是這種事務(wù)隔離級(jí)別下，事務(wù)執(zhí)行很耗性能。

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

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

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

• 如果數(shù)據(jù)事務(wù)ID trx_id < min_limit_id，表明生成該版本的事務(wù)在生成Read View前，已經(jīng)提交(因?yàn)槭聞?wù)ID是遞增的)，所以該版本可以被當(dāng)前事務(wù)訪問。

• 如果trx_id>= max_limit_id，表明生成該版本的事務(wù)在生成Read View后才生成，所以該版本不可以被當(dāng)前事務(wù)訪問。

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

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

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

• 獲取事務(wù)自己的版本號(hào)，即事務(wù)ID

• 獲取Read View

• 查詢得到的數(shù)據(jù)，然后Read View中的事務(wù)版本號(hào)進(jìn)行比較。

• 如果不符合Read View的可見性規(guī)則， 即就需要Undo log中歷史快照;

• 最后返回符合規(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）隔離級(jí)別，是如何解決不可重復(fù)讀問題的？

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

在可重復(fù)讀（RR）隔離級(jí)別下，一個(gè)事務(wù)里只會(huì)獲取一次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對(duì)應(yīng)的值如下

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

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

min_limit_id(100)=<trx_id（100）<102; 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,然后對(duì)數(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ù)讀）隔離級(jí)別，因此會(huì)復(fù)用老的Read View副本，Read View對(duì)應(yīng)的值如下

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

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

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

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

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

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

9. 聊聊索引在哪些場(chǎng)景下會(huì)失效？

1. 查詢條件包含or，可能導(dǎo)致索引失效

2. 如何字段類型是字符串，where時(shí)一定用引號(hào)括起來，否則索引失效

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

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

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

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

7. 索引字段上使用（！= 或者 < >，not in）時(shí)，可能會(huì)導(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)會(huì)自動(dòng)將虛擬地址空間映射到物理地址空間，程序只需關(guān)注虛擬內(nèi)存，請(qǐng)求的也是虛擬內(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)，比如高考成績(jī)排序

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

使用格式如下：

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

• 層內(nèi)部編碼：ziplist（壓縮列表）、skiplist（跳躍表）

• 使用場(chǎng)景如排行榜，社交需求（如用戶點(diǎn)贊）

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

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

分布式鎖，是控制分布式系統(tǒng)不同進(jìn)程共同訪問共享資源的一種鎖的實(shí)現(xiàn)。秒殺下單、搶紅包等等業(yè)務(wù)場(chǎng)景，都需要用到分布式鎖，我們項(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ù)請(qǐng)求     }catch(){   }   finally {        jedis.del(key); //釋放鎖     } }

如果執(zhí)行完setnx加鎖，正要執(zhí)行expire設(shè)置過期時(shí)間時(shí)，進(jìn)程crash掉或者要重啟維護(hù)了，那這個(gè)鎖就“長(zhǎng)生不老”了，別的線程永遠(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) < System.currentTimeMillis()) {       // 鎖已過期，獲取上一個(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í)，可能被別的客戶端釋放/解鎖。

• 鎖過期的時(shí)候，并發(fā)多個(gè)客戶端同時(shí)請(qǐng)求過來，都執(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)前客戶端，會(huì)解除他人加的鎖。

一般也是用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è)置長(zhǎng)一些就可以啦。其實(shí)我們?cè)O(shè)想一下，是否可以給獲得鎖的線程，開啟一個(gè)定時(shí)守護(hù)線程，每隔一段時(shí)間檢查鎖是否還存在，存在則對(duì)鎖的過期時(shí)間延長(zhǎng)，防止鎖過期提前釋放。

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

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

13. 零拷貝

零拷貝就是不需要將數(shù)據(jù)從一個(gè)存儲(chǔ)區(qū)域復(fù)制到另一個(gè)存儲(chǔ)區(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：映射的長(zhǎng)度

• 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)的零拷貝流程如下：

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

• 用戶進(jìn)程發(fā)起sendfile系統(tǒng)調(diào)用，上下文（切換1）從用戶態(tài)轉(zhuǎn)向內(nèi)核態(tài)

• DMA控制器，把數(shù)據(jù)從硬盤中拷貝到內(nèi)核緩沖區(qū)。

• CPU將讀緩沖區(qū)中數(shù)據(jù)拷貝到socket緩沖區(qū)

• DMA控制器，異步把數(shù)據(jù)從socket緩沖區(qū)拷貝到網(wǎng)卡，

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

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

• 用戶進(jìn)程發(fā)起sendfile系統(tǒng)調(diào)用，上下文（切換1）從用戶態(tài)轉(zhuǎn)向內(nèi)核態(tài)

• DMA控制器，把數(shù)據(jù)從硬盤中拷貝到內(nèi)核緩沖區(qū)。

• CPU把內(nèi)核緩沖區(qū)中的文件描述符信息（包括內(nèi)核緩沖區(qū)的內(nèi)存地址和偏移量）發(fā)送到socket緩沖區(qū)

• DMA控制器根據(jù)文件描述符信息，直接把數(shù)據(jù)從內(nèi)核緩沖區(qū)拷貝到網(wǎng)卡

• 上下文（切換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ī)理

• 對(duì)象與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)識(shí)符(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è)對(duì)象都與一個(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)的線程，會(huì)被加入到_WaitSet     _WaitSetLock  = 0 ;     _Responsible  = NULL ;     _succ         = NULL ;     _cxq          = NULL ;     FreeNext      = NULL ;     _EntryList    = NULL ;  // 處于等待鎖block狀態(tài)的線程，會(huì)被加入到該列表     _SpinFreq     = 0 ;     _SpinClock    = 0 ;     OwnerIsThread = 0 ;   }

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

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

• 想要獲取monitor的線程,首先會(huì)進(jìn)入_EntryList隊(duì)列。

• 當(dāng)某個(gè)線程獲取到對(duì)象的monitor后,進(jìn)入Owner區(qū)域，設(shè)置為當(dāng)前線程,同時(shí)計(jì)數(shù)器count加1。

• 如果線程調(diào)用了wait()方法，則會(huì)進(jìn)入WaitSet隊(duì)列。它會(huì)釋放monitor鎖，即將owner賦值為null,count自減1,進(jìn)入WaitSet隊(duì)列阻塞等待。

• 如果其他線程調(diào)用 notify() / notifyAll() ，會(huì)喚醒WaitSet中的某個(gè)線程，該線程再次嘗試獲取monitor鎖，成功即進(jìn)入Owner區(qū)域。

• 同步方法執(zhí)行完畢了，線程退出臨界區(qū)，會(huì)將monitor的owner設(shè)為null，并釋放監(jiān)視鎖。

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

• 在HotSpot虛擬機(jī)中,對(duì)象在內(nèi)存中存儲(chǔ)的布局可以分為3塊區(qū)域：對(duì)象頭（Header），實(shí)例數(shù)據(jù)（Instance Data）和對(duì)象填充（Padding）。

• 對(duì)象頭主要包括兩部分?jǐn)?shù)據(jù)：Mark Word（標(biāo)記字段）、Class Pointer（類型指針）。

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

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

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的最高位是符號(hào)位代表正負(fù)，正數(shù)是0，負(fù)數(shù)是1，一般生成ID都為正數(shù)，所以默認(rèn)為0。

• 接下來前41位是時(shí)間戳，表示了自選定的時(shí)期以來的毫秒數(shù)。

• 接下來的10位代表計(jì)算機(jī)ID，防止沖突。

• 其余12位代表每臺(tái)機(jī)器上生成ID的序列號(hào)，這允許在同一毫秒內(nèi)創(chuàng)建多個(gè)Snowflake ID。

雪花算法

最后PHP中文網(wǎng)祝大家找到一份滿意的工作?。。?/p>

【面試題專題】

前端：【前端面試題】【js面試題 】【 vue面試題】【ajax面試題】【react面試題】

數(shù)據(jù)庫：【mysql面試題】【redis面試題】【oracle面試題】

后端：【PHP面試題】【thinkphp面試題】【python面試題】【java面試題】【android面試題】

聲明：本文轉(zhuǎn)載于：微信公眾號(hào)，如有侵犯，請(qǐng)聯(lián)系admin@php.cn刪除