最近有位讀者去蝦皮面試?yán)玻越裉旖o大家推薦一篇整理了 15 道蝦皮面試真題答案的文章场梆。

文中比較長墅冷，大家可以收藏慢慢看。

image.png

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

1. 排序鏈表

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

image.png

實例1：

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

實例2：

image.png

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

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

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

完整代碼如下：

class Solution {
    public ListNode sortList(ListNode head) {
        //如果鏈表為空萍桌，或者只有一個節(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 等。

image.png

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

image.png

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查排。

image.png

4.2 非阻塞IO模型

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

image.png

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ù)。

image.png

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

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

IO多路復(fù)用之epoll

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

image.png

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的亮點(diǎn)。

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ù)卧波。

image.png

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í)行完畢。

流程如下：

image.png

5. hystrix 工作原理

Hystrix 工作流程圖如下:

image.png

1. 構(gòu)建命令

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

1. 執(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é)果

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

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

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

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

1. 檢查線程池/信號量/隊列情況 Hystrix 隔離方式有線程池隔離和信號量隔離。當(dāng)使用Hystrix線程池時走哺，Hystrix 默認(rèn)為每個依賴服務(wù)分配10個線程蚯嫌，當(dāng)10個線程都繁忙時，將拒絕執(zhí)行命令,丙躏，而是立即跳到執(zhí)行fallback邏輯择示。
2. 執(zhí)行具體的任務(wù) 通過HystrixObservableCommand.construct() 或者 HystrixCommand.run() 來運(yùn)行用戶真正的任務(wù)。
3. 計算回路健康情況 每次開始執(zhí)行command晒旅、結(jié)束執(zhí)行command以及發(fā)生異常等情況時栅盲，都會記錄執(zhí)行情況，例如：成功废恋、失敗剪菱、拒絕和超時等指標(biāo)情況，會定期處理這些數(shù)據(jù)拴签，再根據(jù)設(shè)定的條件來判斷是否開啟回路器。
4. 命令失敗時執(zhí)行Fallback邏輯 在命令失敗時執(zhí)行用戶指定的 Fallback 邏輯旗们。上圖中的斷路蚓哩、線程池拒絕、信號量拒絕上渴、執(zhí)行執(zhí)行岸梨、執(zhí)行超時都會進(jìn)入Fallback處理。
5. 返回執(zhí)行結(jié)果 原始對象結(jié)果將以O(shè)bservable形式返回稠氮，在返回給用戶之前曹阔，會根據(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ù)版本。

image.png

http請求流程

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í)行的∑直妫可以避免臟讀腾节、不可重復(fù)讀與幻讀所有并發(fā)問題。但是這種事務(wù)隔離級別下荤牍，事務(wù)執(zhí)行很耗性能。

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

image.png

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

image.png

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 =<trx_id< max_limit_id ,需要分3種情況討論

• m_ids trx_id Read View trx_id creator_trx_id
• m_ids trx_id trx_id creator_trx_id Read View
• m_ids trx_id Read View

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í)行流程如下

image.png

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

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

image.png

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

1. A開啟事務(wù)瘸味，首先得到一個事務(wù)ID為100
2. B開啟事務(wù)，得到事務(wù)ID為101

3. 事務(wù)A生成一個Read View够挂，read view對應(yīng)的值如下

   
   
   image.png

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

image.png

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

min_limit_id(100)=<trx_id（100）<102;
creator_trx_id = trx_id =100;

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

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

image.png

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

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

   
   
   image.png

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

image.png

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

min_limit_id(100)=<trx_id（101）<max_limit_id（102);
因為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)=<trx_id（100）< max_limit_id（102);
因為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. 對索引列運(yùn)算（如巧勤，+、-弄匕、*颅悉、/），索引失效迁匠。
• 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)存 這個點(diǎn)：多個虛擬內(nèi)存可以指向同一個物理地址夺英，可以把內(nèi)核空間和用戶空間的虛擬地址映射到同一個物理地址，這樣的話滋捶，就可以減少IO的數(shù)據(jù)拷貝次數(shù)啦痛悯，示意圖如下：

image.png

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

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

• 使用格式如下：

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

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

實現(xiàn)demo如下：

image.png

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) < System.currentTimeMillis()) {

     // 鎖已過期武氓，獲取上一個鎖的過期時間梯皿，并設(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)分布式鎖的忠烛，但是這種方案也有這些缺點(diǎ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底層原理是怎樣的吧：

image.png

只要線程一加鎖成功撮胧，就會啟動一個 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流程

流程圖如下：

image.png

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

image.png

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

image.png

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)卡。使用這個特點(diǎn)搞零拷貝码邻，即還可以多省去 一次CPU拷貝 折剃。

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

image.png

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來搬運(yùn)數(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í)行有ACCSYNCHRONIZED標(biāo)志的方法梧宫，需要獲得monitor鎖接谨。每個對象都與一個monitor相關(guān)聯(lián)摆碉，線程可以占有或者釋放monitor。

14.2 monitor監(jiān)視器

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

image.png

在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)鍵字段的含義如圖所示：

image.png

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

image.png

• 想要獲取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)

image.png

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

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

image.png

重量級鎖欣福，指向互斥量的指針。其實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中l(wèi)ong的最高位是符號位代表正負(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粗俱。

image.png