15道蝦皮伺服器端面試真題，你能全答對嗎？（附解析）

1. 排序連結串列

給你連結串列的頭結點head ，請將其按升序排列並返回排序後的連結串列 。

範例1：

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

範例2：

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

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

　1. 快慢指標法，遍歷連結串列找到中間節點

　2. 中間節點切斷連結串列

　3. 分別用歸併排序排左右子連結串列

　4. 合併子連結串列

完整程式碼如下：

class Solution {
    public ListNode sortList(ListNode head) {
        //如果連結串列為空，或者只有一個節點，直接返回即可，不用排序
        if (head == null || head.next == null)
            return head;
        
        //快慢指標移動，以尋找到中間節點
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next !=null){
          fast = fast.next.next;
          slow = slow.next;
        }
        //找到中間節點，slow節點的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.對稱與非對稱加密演演算法的區別

先複習一下相關概念：

• 明文：指沒有經過加密的資訊/資料。

• 密文：明文被加密演演算法加密之後，會變成密文，以確保資料安全。

• 金鑰：是一種引數，它是在明文轉換為密文或將密文轉換為明文的演演算法中輸入的引數。金鑰分為對稱金鑰與非對稱金鑰。

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

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

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

非對稱加密演演算法：非對稱加密演演算法需要兩個金鑰（公開金鑰和私有金鑰）。公鑰與私鑰是成對存在的，如果用公鑰對資料進行加密，只有對應的私鑰才能解密。主要的非對稱加密演演算法有：RSA、Elgamal、DSA、D-H、ECC。

3. TCP如何保證可靠性

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

• 其次，TCP的可靠性，還體現在有狀態;TCP會記錄哪些資料傳送了，哪些資料被接受了，哪些沒有被接受，並且保證封包按序到達，保證資料傳輸不出差錯。

• 再次，TCP的可靠性，還體現在可控制。它有報文校驗、ACK應答、超時重傳(傳送方)、失序資料重傳（接收方）、丟棄重複資料、流量控制（滑動視窗）和擁塞控制等機制。

4. 聊聊五種IO模型

4.1 阻塞IO 模型

假設應用程式的程序發起IO呼叫，但是如果核心的資料還沒準備好的話，那應用程式程序就一直在阻塞等待，一直等到核心資料準備好了，從核心拷貝到使用者空間，才返回成功提示，此次IO操作，稱之為阻塞IO。

4.2 非阻塞IO模型

如果核心資料還沒準備好，可以先返回錯誤資訊給使用者程序，讓它不需要等待，而是通過輪詢的方式再來請求。這就是非阻塞IO，流程圖如下：

4.3 IO多路複用模型

IO多路複用之select

應用程序通過呼叫select函數，可以同時監控多個fd，在select函數監控的fd中，只要有任何一個資料狀態準備就緒了，select函數就會返回可讀狀態，這時應用程序再發起recvfrom請求去讀取資料。

select有幾個缺點：

• 最大連線數有限，在Linux系統上一般為1024。

• select函數返回後，是通過遍歷fdset，找到就緒的描述符fd。

IO多路複用之epoll

為了解決select存在的問題，多路複用模型epoll誕生，它採用事件驅動來實現，流程圖如下：

epoll先通過epoll_ctl()來註冊一個fd（檔案描述符），一旦基於某個fd就緒時，核心會採用回撥機制，迅速啟用這個fd，當程序呼叫epoll_wait()時便得到通知。這裡去掉了遍歷檔案描述符的坑爹操作，而是採用監聽事件回撥的機制。這就是epoll的亮點。

4.4 IO模型之訊號驅動模型

訊號驅動IO不再用主動詢問的方式去確認資料是否就緒，而是向核心傳送一個訊號（呼叫sigaction的時候建立一個SIGIO的訊號），然後應用使用者程序可以去做別的事，不用阻塞。當核心資料準備好後，再通過SIGIO訊號通知應用程序，資料準備好後的可讀狀態。應用使用者程序收到訊號之後，立即呼叫recvfrom，去讀取資料。

4.5 IO 模型之非同步IO(AIO)

AIO實現了IO全流程的非阻塞，就是應用程序發出系統呼叫後，是立即返回的，但是立即返回的不是處理結果，而是表示提交成功類似的意思。等核心資料準備好，將資料拷貝到使用者程序緩衝區，傳送訊號通知使用者程序IO操作執行完畢。

流程如下：

5. hystrix 工作原理

Hystrix 工作流程圖如下:

1、構建命令

Hystrix 提供了兩個命令物件：HystrixCommand和HystrixObservableCommand，它將代表你的一個依賴請求任務，向建構函式中傳入請求依賴所需要的引數。

2、執行命令

有四種方式執行Hystrix命令。分別是：

• R execute()：同步阻塞執行的，從依賴請求中接收到單個響應。

• Future queue()：非同步執行，返回一個包含單個響應的Future物件。

• Observable observe()：建立Observable後會訂閱Observable，從依賴請求中返回代表響應的Observable物件

• Observable toObservable()：cold observable，返回一個Observable，只有訂閱時才會執行Hystrix命令，可以返回多個結果

3、檢查響應是否被快取

如果啟用了 Hystrix快取，任務執行前將先判斷是否有相同命令執行的快取。如果有則直接返回包含快取響應的Observable；如果沒有快取的結果，但啟動了快取，將快取本次執行結果以供後續使用。

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

如果迴路器被開啟，Hystrix將不會執行命令，直接進入Fallback處理邏輯。

5、檢查執行緒池/號誌/佇列情況 Hystrix 隔離方式有執行緒池隔離和號誌隔離。當使用Hystrix執行緒池時，Hystrix 預設為每個依賴服務分配10個執行緒，當10個執行緒都繁忙時，將拒絕執行命令,，而是立即跳到執行fallback邏輯。

6、執行具體的任務 通過HystrixObservableCommand.construct() 或者 HystrixCommand.run() 來執行使用者真正的任務。

7、計算迴路健康情況 每次開始執行command、結束執行command以及發生異常等情況時，都會記錄執行情況，例如：成功、失敗、拒絕和超時等指標情況，會定期處理這些資料，再根據設定的條件來判斷是否開啟迴路器。

8、命令失敗時執行Fallback邏輯 在命令失敗時執行使用者指定的 Fallback 邏輯。上圖中的斷路、執行緒池拒絕、號誌拒絕、執行執行、執行超時都會進入Fallback處理。

9、返回執行結果 原始物件結果將以Observable形式返回，在返回給使用者之前，會根據呼叫方式的不同做一些處理。

6. 延時場景處理

日常開發中，我們經常遇到這種業務場景，如：外賣訂單超30分鐘未支付，則自動取消訂單；使用者註冊成功15分鐘後，傳簡訊訊息通知使用者等等。這就是延時任務處理場景。針對此類場景我們主要有以下幾種處理方案：

• JDK的DelayQueue延遲佇列

• 時間輪演演算法

• 資料庫定時任務（如Quartz）

• Redis ZSet 實現

• MQ 延時佇列實現

7.https請求過程

• HTTPS = HTTP + SSL/TLS，即用SSL/TLS對資料進行加密和解密，Http進行傳輸。

• SSL，即Secure Sockets Layer（安全通訊協定協定），是網路通訊提供安全及資料完整性的一種安全協定。

• TLS，即Transport Layer Security(安全傳輸層協定)，它是SSL 3.0的後續版本。

http請求流程

1、使用者在瀏覽器裡輸入一個https網址，然後連線到server的443埠。

2、伺服器必須要有一套數位憑證，可以自己製作，也可以向組織申請，區別就是自己頒發的證書需要使用者端驗證通過。這套證書其實就是一對公鑰和私鑰。

3、伺服器將自己的數位憑證（含有公鑰）傳送給使用者端。

4、使用者端收到伺服器端的數位憑證之後，會對其進行檢查，如果不通過，則彈出警告框。如果證書沒問題，則生成一個金鑰（對稱加密），用證書的公鑰對它加密。

5、使用者端會發起HTTPS中的第二個HTTP請求，將加密之後的使用者端金鑰傳送給伺服器。

6、伺服器接收到使用者端發來的密文之後，會用自己的私鑰對其進行非對稱解密，解密之後得到使用者端金鑰，然後用使用者端金鑰對返回資料進行對稱加密，這樣資料就變成了密文。

7、伺服器將加密後的密文返回給使用者端。

8、使用者端收到伺服器發返回的密文，用自己的金鑰（使用者端金鑰）對其進行對稱解密，得到伺服器返回的資料。

8. 聊聊事務隔離級別，以及可重複讀實現原理

8.1 資料庫四大隔離級別

為了解決並行事務存在的髒讀、不可重複讀、幻讀等問題，資料庫大叔設計了四種隔離級別。分別是讀未提交，讀已提交，可重複讀，序列化（Serializable）。

• 讀未提交隔離級別：只限制了兩個資料不能同時修改，但是修改資料的時候，即使事務未提交，都是可以被別的事務讀取到的，這級別的事務隔離有髒讀、重複讀、幻讀的問題；

• 讀已提交隔離級別：當前事務只能讀取到其他事務提交的資料，所以這種事務的隔離級別解決了髒讀問題，但還是會存在重複讀、幻讀問題；

• 可重複讀：限制了讀取資料的時候，不可以進行修改，所以解決了重複讀的問題，但是讀取範圍資料的時候，是可以插入資料，所以還會存在幻讀問題；

• 序列化：事務最高的隔離級別，在該級別下，所有事務都是進行序列化順序執行的。可以避免髒讀、不可重複讀與幻讀所有並行問題。但是這種事務隔離級別下，事務執行很耗效能。

四大隔離級別，都會存在哪些並行問題呢

8.2 Read View可見性規則

Read View的可見性規則如下：

• 如果資料事務ID trx_id < min_limit_id，表明生成該版本的事務在生成Read View前，已經提交(因為事務ID是遞增的)，所以該版本可以被當前事務存取。

• 如果trx_id>= max_limit_id，表明生成該版本的事務在生成Read View後才生成，所以該版本不可以被當前事務存取。

• 如果 min_limit_id =<trx_id< max_limit_id，需要分3種情況討論

1）如果m_ids包含trx_id,則代表Read View生成時刻，這個事務還未提交，但是如果資料的trx_id等於creator_trx_id的話，表明資料是自己生成的，因此是可見的。

2）如果m_ids包含trx_id，並且trx_id不等於creator_trx_id，則Read View生成時，事務未提交，並且不是自己生產的，所以當前事務也是看不見的；

3）如果m_ids不包含trx_id，則說明你這個事務在Read View生成之前就已經提交了，修改的結果，當前事務是能看見的。

8.3 可重複讀實現原理

資料庫是通過加鎖實現隔離級別的，比如，你想一個人靜靜，不被別人打擾，你可以把自己關在房子，並在房門上加上一把鎖！序列化隔離級別就是加鎖實現的。但是如果頻繁加鎖，效能會下降。因此設計資料庫的大叔想到了MVCC。

可重複讀的實現原理就是MVCC多版本並行控制。在一個事務範圍內，兩個相同的查詢，讀取同一條記錄，卻返回了不同的資料，這就是不可重複讀。可重複讀隔離級別，就是為了解決不可重複讀問題。

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

• 獲取事務自己的版本號，即事務ID

• 獲取Read View

• 查詢得到的資料，然後Read View中的事務版本號進行比較。

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

• 最後返回符合規則的資料

InnoDB 實現MVCC，是通過Read View+ Undo Log實現的，Undo Log儲存了歷史快照，Read View可見性規則幫助判斷當前版本的資料是否可見。

可重複讀（RR）隔離級別，是如何解決不可重複讀問題的？

假設存在事務A和B，SQL執行流程如下

在可重複讀（RR）隔離級別下，一個事務裡只會獲取一次read view，都是副本共用的，從而保證每次查詢的資料都是一樣的。

假設當前有一張core_user表，插入一條初始化資料,如下：

基於MVCC，我們來看看執行流程

1、A開啟事務，首先得到一個事務ID為100

2、B開啟事務，得到事務ID為101

3、事務A生成一個Read View，read view對應的值如下

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

由圖可以看出，最新版本的列name的內容是孫權，該版本的trx_id值為100。開始執行read view可見性規則校驗：

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

由此可得，trx_id=100的這個記錄，當前事務是可見的。所以查到是name為孫權的記錄。

4、事務B進行修改操作，把名字改為曹操。把原資料拷貝到undo log,然後對資料進行修改，標記事務ID和上一個資料版本在undo log的地址。

5、事務B提交事務

6、事務A再次執行查詢操作，因為是RR（可重複讀）隔離級別，因此會複用老的Read View副本，Read View對應的值如下

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

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

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這個記錄，對於當前事務是不可見的。這時候呢，版本鏈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這個記錄，對於當前事務是可見的，所以兩次查詢結果，都是name=孫權的那個記錄。即在可重複讀（RR）隔離級別下，複用老的Read View副本，解決了不可重複讀的問題。

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

1. 查詢條件包含or，可能導致索引失效

2. 如何欄位型別是字串，where時一定用引號括起來，否則索引失效

3. like萬用字元可能導致索引失效。

4. 聯合索引，查詢時的條件列不是聯合索引中的第一個列，索引失效。

5. 在索引列上使用mysql的內建函數，索引失效。

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

7. 索引欄位上使用（！= 或者 < >，not in）時，可能會導致索引失效。

8. 索引欄位上使用is null， is not null，可能導致索引失效。

9. 左連線查詢或者右連線查詢查詢關聯的欄位編碼格式不一樣，可能導致索引失效。

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

10. 什麼是虛擬記憶體

虛擬記憶體，是虛擬出來的記憶體，它的核心思想就是確保每個程式擁有自己的地址空間，地址空間被分成多個塊，每一塊都有連續的地址空間。同時物理空間也分成多個塊，塊大小和虛擬地址空間的塊大小一致，作業系統會自動將虛擬地址空間對映到實體地址空間，程式只需關注虛擬記憶體，請求的也是虛擬記憶體，真正使用卻是實體記憶體。

現代作業系統使用虛擬記憶體，即虛擬地址取代實體地址，使用虛擬記憶體可以有2個好處：

• 虛擬記憶體空間可以遠遠大於實體記憶體空間

• 多個虛擬記憶體可以指向同一個實體地址

零拷貝實現思想，就利用了虛擬記憶體這個點：多個虛擬記憶體可以指向同一個實體地址，可以把核心空間和使用者空間的虛擬地址對映到同一個實體地址，這樣的話，就可以減少IO的資料拷貝次數啦，示意圖如下：

11. 排行榜的實現，比如高考成績排序

排行版的實現，一般使用redis的zset資料型別。

使用格式如下：

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

• 層內部編碼：ziplist（壓縮列表）、skiplist（跳躍表）

• 使用場景如排行榜，社交需求（如使用者點贊）

實現demo如下：

12.分散式鎖實現

分散式鎖，是控制分散式系統不同程序共同存取共用資源的一種鎖的實現。秒殺下單、搶紅包等等業務場景，都需要用到分散式鎖，我們專案中經常使用Redis作為分散式鎖。

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

• 命令setnx + expire分開寫

• setnx + value值是過期時間

• set的擴充套件命令（set ex px nx）

• set ex px nx + 校驗唯一隨機值,再刪除

• Redisson

12.1 命令setnx + expire分開寫

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

如果執行完setnx加鎖，正要執行expire設定過期時間時，程序crash掉或者要重新啟動維護了，那這個鎖就「長生不老」了，別的執行緒永遠獲取不到鎖啦，所以分散式鎖不能這麼實現。

12.2 setnx + value值是過期時間

long expires = System.currentTimeMillis() + expireTime; //系統時間+設定的過期時間
String expiresStr = String.valueOf(expires);

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

// 如果獲取到的過期時間，小於系統當前時間，表示已經過期
if (currentValueStr != null && Long.parseLong(currentValueStr) < System.currentTimeMillis()) {

     // 鎖已過期，獲取上一個鎖的過期時間，並設定現在鎖的過期時間（不瞭解redis的getSet命令的小夥伴，可以去官網看下哈）
    String oldValueStr = jedis.getSet(key_resource_id, expiresStr);
    
    if (oldValueStr != null && oldValueStr.equals(currentValueStr)) {
         // 考慮多執行緒並行的情況，只有一個執行緒的設定值和當前值相同，它才可以加鎖
         return true;
    }
}
        
//其他情況，均返回加鎖失敗
return false;
}

筆者看過有開發小夥伴就是這麼實現分散式鎖的，但是這種方案也有這些缺點：

• 過期時間是使用者端自己生成的，分散式環境下，每個使用者端的時間必須同步。

• 沒有儲存持有者的唯一標識，可能被別的使用者端釋放/解鎖。

• 鎖過期的時候，並行多個使用者端同時請求過來，都執行了jedis.getSet()，最終只能有一個使用者端加鎖成功，但是該使用者端鎖的過期時間，可能被別的使用者端覆蓋。

12.3 set的擴充套件命令（set ex px nx）（注意可能存在的問題）

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

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

• 鎖過期釋放了，業務還沒執行完。

• 鎖被別的執行緒誤刪。

12.4 set ex px nx + 校驗唯一隨機值,再刪除

if（jedis.set(key, uni_request_id, "NX", "EX", 100s) == 1）{ //加鎖
    try {
        do something  //業務處理
    }catch(){
  }
  finally {
       //判斷是不是當前執行緒加的鎖,是才釋放
       if (uni_request_id.equals(jedis.get(key))) {
        jedis.del(key); //釋放鎖
        }
    }
}

在這裡，判斷當前執行緒加的鎖和釋放鎖是不是一個原子操作。如果呼叫jedis.del()釋放鎖的時候，可能這把鎖已經不屬於當前使用者端，會解除他人加的鎖。

一般也是用lua指令碼代替。lua指令碼如下：

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

這種方式比較不錯了，一般情況下，已經可以使用這種實現方式。但是存在鎖過期釋放了，業務還沒執行完的問題（實際上，估算個業務處理的時間，一般沒啥問題了）。

12.5 Redisson

分散式鎖可能存在鎖過期釋放，業務沒執行完的問題。有些小夥伴認為，稍微把鎖過期時間設定長一些就可以啦。其實我們設想一下，是否可以給獲得鎖的執行緒，開啟一個定時守護執行緒，每隔一段時間檢查鎖是否還存在，存在則對鎖的過期時間延長，防止鎖過期提前釋放。

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

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

13. 零拷貝

零拷貝就是不需要將資料從一個儲存區域複製到另一個儲存區域。它是指在傳統IO模型中，指CPU拷貝的次數為0。它是IO的優化方案

傳統IO流程

• 零拷貝實現之mmap+write

• 零拷貝實現之sendfile

• 零拷貝實現之帶有DMA收集拷貝功能的sendfile

13.1 傳統IO流程

流程圖如下：

• 使用者應用程序呼叫read函數，向作業系統發起IO呼叫，上下文從使用者態轉為核心態（切換1）

• DMA控制器把資料從磁碟中，讀取到核心緩衝區。

• CPU把核心緩衝區資料，拷貝到使用者應用緩衝區，上下文從核心態轉為使用者態（切換2），read函數返回

• 使用者應用程序通過write函數，發起IO呼叫，上下文從使用者態轉為核心態（切換3）

• CPU將應用緩衝區中的資料，拷貝到socket緩衝區

• DMA控制器把資料從socket緩衝區，拷貝到網路卡裝置，上下文從核心態切換回使用者態（切換4），write函數返回

從流程圖可以看出，傳統IO的讀寫流程，包括了4次上下文切換（4次使用者態和核心態的切換），4次資料拷貝（兩次CPU拷貝以及兩次的DMA拷貝)。

13.2 mmap+write實現的零拷貝

mmap 的函數原型如下：

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

• addr：指定對映的虛擬記憶體地址

• length：對映的長度

• prot：對映記憶體的保護模式

• flags：指定對映的型別

• fd:進行對映的檔案控制程式碼

• offset:檔案偏移量

• mmap使用了虛擬記憶體，可以把核心空間和使用者空間的虛擬地址對映到同一個實體地址，從而減少資料拷貝次數！

mmap+write實現的零拷貝流程如下：

• 使用者程序通過mmap方法向作業系統核心發起IO呼叫，上下文從使用者態切換為核心態。

• CPU利用DMA控制器，把資料從硬碟中拷貝到核心緩衝區。

• 上下文從核心態切換回使用者態，mmap方法返回。

• 使用者程序通過write方法向作業系統核心發起IO呼叫，上下文從使用者態切換為核心態。

• CPU將核心緩衝區的資料拷貝到的socket緩衝區。

• CPU利用DMA控制器，把資料從socket緩衝區拷貝到網路卡，上下文從核心態切換回使用者態，write呼叫返回。

可以發現，mmap+write實現的零拷貝，I/O發生了4次使用者空間與核心空間的上下文切換，以及3次資料拷貝。其中3次資料拷貝中，包括了2次DMA拷貝和1次CPU拷貝。

mmap是將讀緩衝區的地址和使用者緩衝區的地址進行對映，核心緩衝區和應用緩衝區共用，所以節省了一次CPU拷貝‘’並且使用者程序記憶體是虛擬的，只是對映到核心的讀緩衝區，可以節省一半的記憶體空間。

sendfile實現的零拷貝

sendfile是Linux2.1核心版本後引入的一個系統呼叫函數，API如下：

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

• out_fd:為待寫入內容的檔案描述符，一個socket描述符。，

• in_fd:為待讀出內容的檔案描述符，必須是真實的檔案，不能是socket和管道。

• offset：指定從讀入檔案的哪個位置開始讀，如果為NULL，表示檔案的預設起始位置。

• count：指定在fdout和fdin之間傳輸的位元組數。

• sendfile表示在兩個檔案描述符之間傳輸資料，它是在作業系統核心中操作的，避免了資料從核心緩衝區和使用者緩衝區之間的拷貝操作，因此可以使用它來實現零拷貝。

sendfile實現的零拷貝流程如下：

sendfile實現的零拷貝

• 使用者程序發起sendfile系統呼叫，上下文（切換1）從使用者態轉向核心態

• DMA控制器，把資料從硬碟中拷貝到核心緩衝區。

• CPU將讀緩衝區中資料拷貝到socket緩衝區

• DMA控制器，非同步把資料從socket緩衝區拷貝到網路卡，

• 上下文（切換2）從核心態切換回使用者態，sendfile呼叫返回。

可以發現，sendfile實現的零拷貝，I/O發生了2次使用者空間與核心空間的上下文切換，以及3次資料拷貝。其中3次資料拷貝中，包括了2次DMA拷貝和1次CPU拷貝。那能不能把CPU拷貝的次數減少到0次呢？有的，即帶有DMA收集拷貝功能的sendfile！

sendfile+DMA scatter/gather實現的零拷貝

linux 2.4版本之後，對sendfile做了優化升級，引入SG-DMA技術，其實就是對DMA拷貝加入了scatter/gather操作，它可以直接從核心空間緩衝區中將資料讀取到網路卡。使用這個特點搞零拷貝，即還可以多省去一次CPU拷貝。

sendfile+DMA scatter/gather實現的零拷貝流程如下：

• 使用者程序發起sendfile系統呼叫，上下文（切換1）從使用者態轉向核心態

• DMA控制器，把資料從硬碟中拷貝到核心緩衝區。

• CPU把核心緩衝區中的檔案描述符資訊（包括核心緩衝區的記憶體地址和偏移量）傳送到socket緩衝區

• DMA控制器根據檔案描述符資訊，直接把資料從核心緩衝區拷貝到網路卡

• 上下文（切換2）從核心態切換回使用者態，sendfile呼叫返回。

可以發現，sendfile+DMA scatter/gather實現的零拷貝，I/O發生了2次使用者空間與核心空間的上下文切換，以及2次資料拷貝。其中2次資料拷貝都是包DMA拷貝。這就是真正的 零拷貝（Zero-copy) 技術，全程都沒有通過CPU來搬運資料，所有的資料都是通過DMA來進行傳輸的。

14. synchronized

synchronized是Java中的關鍵字，是一種同步鎖。synchronized關鍵字可以作用於方法或者程式碼塊。

一般面試時。可以這麼回答：

• 反編譯後，monitorenter、monitorexit、ACC_SYNCHRONIZED

• monitor監視器

• Java Monitor 的工作機理

• 物件與monitor關聯

14.1 monitorenter、monitorexit、ACC_SYNCHRONIZED

如果synchronized作用於程式碼塊，反編譯可以看到兩個指令：monitorenter、monitorexit，JVM使用monitorenter和monitorexit兩個指令實現同步；如果作用synchronized作用於方法,反編譯可以看到ACCSYNCHRONIZED標記，JVM通過在方法存取識別符號(flags)中加入ACCSYNCHRONIZED來實現同步功能。

• 同步程式碼塊是通過monitorenter和monitorexit來實現，當執行緒執行到monitorenter的時候要先獲得monitor鎖，才能執行後面的方法。當執行緒執行到monitorexit的時候則要釋放鎖。

• 同步方法是通過中設定ACCSYNCHRONIZED標誌來實現，當執行緒執行有ACCSYNCHRONIZED標誌的方法，需要獲得monitor鎖。每個物件都與一個monitor相關聯，執行緒可以佔有或者釋放monitor。

14.2 monitor監視器

monitor是什麼呢？作業系統的管程（monitors）是概念原理，ObjectMonitor是它的原理實現。

在Java虛擬機器器（HotSpot）中，Monitor（管程）是由ObjectMonitor實現的，其主要資料結構如下：

 ObjectMonitor() {
    _header       = NULL;
    _count        = 0; // 記錄個數
    _waiters      = 0,
    _recursions   = 0;
    _object       = NULL;
    _owner        = NULL;
    _WaitSet      = NULL;  // 處於wait狀態的執行緒，會被加入到_WaitSet
    _WaitSetLock  = 0 ;
    _Responsible  = NULL ;
    _succ         = NULL ;
    _cxq          = NULL ;
    FreeNext      = NULL ;
    _EntryList    = NULL ;  // 處於等待鎖block狀態的執行緒，會被加入到該列表
    _SpinFreq     = 0 ;
    _SpinClock    = 0 ;
    OwnerIsThread = 0 ;
  }

ObjectMonitor中幾個關鍵欄位的含義如圖所示：

14.3 Java Monitor 的工作機理

• 想要獲取monitor的執行緒,首先會進入_EntryList佇列。

• 當某個執行緒獲取到物件的monitor後,進入Owner區域，設定為當前執行緒,同時計數器count加1。

• 如果執行緒呼叫了wait()方法，則會進入WaitSet佇列。它會釋放monitor鎖，即將owner賦值為null,count自減1,進入WaitSet佇列阻塞等待。

• 如果其他執行緒呼叫 notify() / notifyAll() ，會喚醒WaitSet中的某個執行緒，該執行緒再次嘗試獲取monitor鎖，成功即進入Owner區域。

• 同步方法執行完畢了，執行緒退出臨界區，會將monitor的owner設為null，並釋放監視鎖。

14.4 物件與monitor關聯

• 在HotSpot虛擬機器器中,物件在記憶體中儲存的佈局可以分為3塊區域：物件頭（Header），範例資料（Instance Data）和物件填充（Padding）。

• 物件頭主要包括兩部分資料：Mark Word（標記欄位）、Class Pointer（型別指標）。

Mark Word 是用於儲存物件自身的執行時資料，如雜湊碼（HashCode）、GC分代年齡、鎖狀態標誌、執行緒持有的鎖、偏向執行緒 ID、偏向時間戳等。

重量級鎖，指向互斥量的指標。其實synchronized是重量級鎖，也就是說Synchronized的物件鎖，Mark Word鎖標識位為10，其中指標指向的是Monitor物件的起始地址。

15. 分散式id生成方案有哪些？什麼是雪花演演算法？

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

• UUID

• 資料庫自增ID

• 基於雪花演演算法（Snowflake）實現

• 百度 （Uidgenerator）

• 美團（Leaf）

什麼是雪花演演算法？

雪花演演算法是一種生成分散式全域性唯一ID的演演算法，生成的ID稱為Snowflake IDs。這種演演算法由Twitter建立，並用於推文的ID。

一個Snowflake ID有64位元。

• 第1位：Java中long的最高位是符號位代表正負，正數是0，負數是1，一般生成ID都為正數，所以預設為0。

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

• 接下來的10位代表計算機ID，防止衝突。

• 其餘12位元代表每臺機器上生成ID的序列號，這允許在同一毫秒內建立多個Snowflake ID。

雪花演演算法

最後PHP中文網祝大家找到一份滿意的工作！！！

【面試題專題】

前端：【】【 】【 】【】【】

資料庫：【】【】【】

後端：【】【】【】【】【】