I/O 多路複用：select/poll/epoll#
我們可以從 TCP Socket 編程模型裡看出 TCP Socket 調用機制是簡單的一對一調用機制，使用的是同步阻塞的方式，那麼如何改進 IO 模型，使用相同資源服務更多用戶呢？
多進程模型#
一個比較傳統的方式，就是使用多進程模型，也就是為每個客戶端分配一個進程來處理請求。
伺服器的主進程負責監聽客戶的連接，一旦與客戶端連接完成，accept () 函數就會返回一個「已連接 Socket」，這時就通過 fork () 函數創建一個子進程，實際上就把父進程所有相關的東西都複製一份，包括文件描述符、內存地址空間、程序計數器、執行的代碼等。
這兩個進程剛複製完的時候，幾乎一模一樣。不過，會根據返回值來區分是父進程還是子進程，如果返回值是 0，則是子進程；如果返回值是其他的整數，就是父進程。
正因為子進程會複製父進程的文件描述符，於是就可以直接使用「已連接 Socket 」和客戶端通信了，
可以發現，子進程不需要關心「監聽 Socket」，只需要關心「已連接 Socket」；父進程則相反，將客戶服務交給子進程來處理，因此父進程不需要關心「已連接 Socket」，只需要關心「監聽 Socket」。
下面這張圖描述了從連接請求到連接建立，父進程創建生子進程為客戶服務。
另外，當「子進程」退出時，實際上內核裡還會保留該進程的一些信息，也是會佔用內存的，如果不做好 “回收” 工作，就會變成殭屍進程，隨著殭屍進程越多，會慢慢耗尽我們的系統資源。
因此，父進程要 “善後” 好自己的孩子，怎麼善後呢？那麼有兩種方式可以在子進程退出後回收資源，分別是調用 wait () 和 waitpid () 函數。
這種用多個進程來應付多個客戶端的方式，在應對 100 個客戶端還是可行的，但是當客戶端數量高達一萬時，肯定扛不住的，因為每產生一個進程，必會佔據一定的系統資源，而且進程間上下文切換的 “包袱” 是很重的，性能會大打折扣。
進程的上下文切換不僅包含了虛擬內存、棧、全局變量等用戶空間的資源，還包括了內核堆棧、寄存器等內核空間的資源。
多線程模型#
既然進程間上下文切換的 “包袱” 很重，那我們就搞個比較輕量級的模型來應對多用戶的請求 —— 多線程模型。
線程是運行在進程中的一個 “邏輯流”，單進程中可以運行多個線程，同進程裡的線程可以共享進程的部分資源，比如文件描述符列表、進程空間、代碼、全局數據、堆、共享庫等，這些共享資源在上下文切換時不需要切換，而只需要切換線程的私有數據、寄存器等不共享的數據，因此同一個進程下的線程上下文切換的開銷要比進程小得多。
當伺服器與客戶端 TCP 完成連接後，通過 pthread_create () 函數創建線程，然後將「已連接 Socket」的文件描述符傳遞給線程函數，接著在線程裡和客戶端進行通信，從而達到並發處理的目的。
如果每來一個連接就創建一個線程，線程運行完後，還得操作系統還得銷毀線程，雖說線程切換的開銷不大，但是如果頻繁創建和銷毀線程，系統開銷也是不小的。
那麼，我們可以使用線程池的方式來避免線程的頻繁創建和銷毀，所謂的線程池，就是提前創建若干個線程，這樣當由新連接建立時，將這個已連接的 Socket 放入到一個隊列裡，然後線程池裡的線程負責從隊列中取出「已連接 Socket 」進行處理。
需要注意的是，這個隊列是全局的，每個線程都會操作，為了避免多線程競爭，線程在操作這個隊列前要加鎖。
上面基於進程或者線程模型的，其實還是有問題的。新到來一個 TCP 連接，就需要分配一個進程或者線程，那麼如果要達到 C10K，意味著要一台機器維護 1 萬個連接，相當於要維護 1 萬個進程 / 線程，操作系統就算死扛也是扛不住的。
I/O 多路複用#
既然為每個請求分配一個進程 / 線程的方式不合適，那有沒有可能只使用一個進程來維護多個 Socket 呢？答案是有的，那就是I/O 多路複用技術。
一個進程雖然任一時刻只能處理一個請求，但是處理每個請求的事件時，耗時控制在 1 毫秒以內，這樣 1 秒內就可以處理上千個請求，把時間拉長來看，多個請求複用了同一個進程，這就是多路複用，這種思想很類似一個 CPU 並發多個進程，所以也叫做時分多路複用。
我們熟悉的 select/poll/epoll 內核提供給用戶態的多路複用系統調用，進程可以通過一個系統調用函數從內核中獲取多個事件。
select/poll/epoll 是如何獲取網絡事件的呢？在獲取事件時，先把所有連接（文件描述符）傳給內核，再由內核返回產生了事件的連接，然後在用戶態中再處理這些連接對應的請求即可。
select/poll/epoll 這是三個多路複用接口，都能實現 C10K 嗎？接下來，我們分別說說它們。
select/poll#
select 實現多路複用的方式是，將已連接的 Socket 都放到一個文件描述符集合，然後調用 select 函數將文件描述符集合拷貝到內核裡，讓內核來檢查是否有網絡事件產生，檢查的方式很粗暴，就是通過遍歷文件描述符集合的方式，當檢查到有事件產生後，將此 Socket 標記為可讀或可寫，接著再把整個文件描述符集合拷貝回用戶態裡，然後用戶態還需要再通過遍歷的方法找到可讀或可寫的 Socket，然後再對其處理。
所以，對於 select 這種方式，需要進行2 次「遍歷」文件描述符集合，一次是在內核態裡，一次是在用戶態裡，而且還會發生2 次「拷貝」文件描述符集合，先從用戶空間傳入內核空間，由內核修改後，再傳出到用戶空間中。
select 使用固定長度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的個數是有限制的，在 Linux 系統中，由內核中的 FD_SETSIZE 限制， 默認最大值為 1024，只能監聽 0~1023 的文件描述符。
poll 不再用 BitsMap 來存儲所關注的文件描述符，取而代之用動態數組，以鏈表形式來組織，突破了 select 的文件描述符個數限制，當然還會受到系統文件描述符限制。
但是 poll 和 select 並沒有太大的本質區別，都是使用「線性結構」存儲進程關注的 Socket 集合，因此都需要遍歷文件描述符集合來找到可讀或可寫的 Socket，時間複雜度為 O (n)，而且也需要在用戶態與內核態之間拷貝文件描述符集合，這種方式隨著並發數上來，性能的損耗會呈指數級增長。
epoll#
epoll 通過兩個方面，很好解決了 select/poll 的問題。
第一點，epoll 在內核裡使用紅黑樹來跟蹤進程所有待檢測的文件描述字，把需要監控的 socket 通過 epoll_ctl () 函數加入內核中的紅黑樹裡，紅黑樹是個高效的數據結構，增刪改一般時間複雜度是 O (logn)。而 select/poll 內核裡沒有類似 epoll 紅黑樹這種保存所有待檢測的 socket 的數據結構，所以 select/poll 每次操作時都傳入整個 socket 集合給內核，而 epoll 因為在內核維護了紅黑樹，可以保存所有待檢測的 socket ，所以只需要傳入一個待檢測的 socket，減少了內核和用戶空間大量的數據拷貝和內存分配。
第二點，epoll 使用事件驅動的機制，內核裡維護了一個鏈表來記錄就緒事件，當某個 socket 有事件發生時，通過回調函數內核會將其加入到這個就緒事件列表中，當用戶調用 epoll_wait () 函數時，只會返回有事件發生的文件描述符的個數，不需要像 select/poll 那樣輪詢掃描整個 socket 集合，大大提高了檢測的效率。
從下圖你可以看到 epoll 相關的接口作用：
epoll 的方式即使監聽的 Socket 數量越多的時候，效率不會大幅度降低，能夠同時監聽的 Socket 的數目也非常的多了，上限就為系統定義的進程打開的最大文件描述符個數。因此，epoll 被稱為解決 C10K 問題的利器。
邊緣觸發和水平觸發#
epoll 支持兩種事件觸發模式，分別是邊緣觸發（edge-triggered，ET）和水平觸發（level-triggered，LT）。
- 使用邊緣觸發模式時，當被監控的 Socket 描述符上有可讀事件發生時，伺服器端只會從 epoll_wait 中蘇醒一次，即使進程沒有調用 read 函數從內核讀取數據，也依然只蘇醒一次，因此我們程序要保證一次性將內核緩衝區的數據讀取完；
- 使用水平觸發模式時，當被監控的 Socket 上有可讀事件發生時，伺服器端不斷地從 epoll_wait 中蘇醒，直到內核緩衝區數據被 read 函數讀完才結束，目的是告訴我們有數據需要讀取；
水平觸發的意思是只要滿足事件的條件，比如內核中有數據需要讀，就一直不斷地把這個事件傳遞給用戶；而邊緣觸發的意思是只有第一次滿足條件的時候才觸發，之後就不會再傳遞同樣的事件了。
如果使用水平觸發模式，當內核通知文件描述符可讀寫時，接下來還可以繼續去檢測它的狀態，看它是否依然可讀或可寫。所以在收到通知後，沒必要一次執行盡可能多的讀寫操作。
如果使用邊緣觸發模式，I/O 事件發生時只會通知一次，而且我們不知道到底能讀寫多少數據，所以在收到通知後應盡可能地讀寫數據，以免錯失讀寫的機會。因此，我們會循環從文件描述符讀寫數據，那麼如果文件描述符是阻塞的，沒有數據可讀寫時，進程會阻塞在讀寫函數那裡，程序就沒辦法繼續往下執行。所以，邊緣觸發模式一般和非阻塞 I/O 搭配使用，程序會一直執行 I/O 操作，直到系統調用（如 read 和 write）返回錯誤，錯誤類型為 EAGAIN 或 EWOULDBLOCK。
一般來說，邊緣觸發的效率比水平觸發的效率要高，因為邊緣觸發可以減少 epoll_wait 的系統調用次數，系統調用也是有一定的開銷的，畢竟也存在上下文的切換。
select/poll 只有水平觸發模式，epoll 默認的觸發模式是水平觸發，但是可以根據應用場景設置為邊緣觸發模式。
另外，使用 I/O 多路複用時，最好搭配非阻塞 I/O 一起使用，多路複用 API 返回的事件並不一定可讀寫的，如果使用阻塞 I/O， 那麼在調用 read/write 時則會發生程序阻塞，因此最好搭配非阻塞 I/O，以便應對極少數的特殊情況。
高性能網絡模式：Reactor 和 Proactor#
Reactor#
剛剛我們說了通過 IO 多路複用可以達成網絡高性能，但是真正的 I/O 多路複用接口寫網絡程是面向過程的方式寫代碼的，這樣的開發的效率不高。
於是，大佬們基於面向對象的思想，對 I/O 多路複用作了一層封裝，讓使用者不用考慮底層網絡 API 的細節，只需要關注應用代碼的編寫，這個底層模式就是Reactor 模式。
Reactor 模式也叫 Dispatcher 模式，即 I/O 多路複用監聽事件，收到事件後，根據事件類型分配（Dispatch）給某個進程 / 線程。
Reactor 模式主要由 Reactor 和處理資源池這兩個核心部分組成，它倆負責的事情如下：
- Reactor 負責監聽和分發事件，事件類型包含連接事件、讀寫事件；
- 處理資源池負責處理事件，如 read -> 業務邏輯 -> send；
Reactor 模式是靈活多變的，可以應對不同的業務場景，靈活在於：
- Reactor 的數量可以只有一個，也可以有多個；
- 處理資源池可以是單個進程 / 線程，也可以是多個進程 / 線程；
接下來，分別介紹三個經典的 Reactor 方案。
單 Reactor 單進程 / 線程#
可以看到進程裡有 Reactor、Acceptor、Handler 這三個對象：
- Reactor 對象的作用是監聽和分發事件；
- Acceptor 對象的作用是獲取連接；
- Handler 對象的作用是處理業務；
對象裡的 select、accept、read、send 是系統調用函數，dispatch 和 「業務處理」是需要完成的操作，其中 dispatch 是分發事件操作。
接下來，介紹下「單 Reactor 單進程」這個方案：
- Reactor 對象通過 select （IO 多路複用接口） 監聽事件，收到事件後通過 dispatch 進行分發，具體分發給 Acceptor 對象還是 Handler 對象，還要看收到的事件類型；
- 如果是連接建立的事件，則交由 Acceptor 對象進行處理，Acceptor 對象會通過 accept 方法 獲取連接，並創建一個 Handler 對象來處理後續的響應事件；
- 如果不是連接建立事件，則交由當前連接對應的 Handler 對象來進行響應；
Handler 對象通過 read -> 業務處理 -> send 的流程來完成完整的業務流程。
單 Reactor 單進程的方案因為全部工作都在同一個進程內完成，所以實現起來比較簡單，不需要考慮進程間通信，也不用擔心多進程競爭。
但是，這種方案存在 2 個缺點：
- 第一个缺點，因為只有一個進程，無法充分利用 多核 CPU 的性能；
- 第二個缺點，Handler 對象在業務處理時，整個進程是無法處理其他連接的事件的，如果業務處理耗時比較長，那麼就造成響應的延遲；
所以，單 Reactor 單進程的方案不適用計算機密集型的場景，只適用於業務處理非常快速的場景。
Redis 是由 C 語言實現的，在 Redis 6.0 版本之前採用的正是「單 Reactor 單進程」的方案，因為 Redis 業務處理主要是在內存中完成，操作的速度是很快的，性能瓶頸不在 CPU 上，所以 Redis 對於命令的處理是單進程的方案。
單 Reactor 多線程 / 多進程#
如果要克服「單 Reactor 單線程 / 進程」方案的缺點，那麼就需要引入多線程 / 多進程，這樣就產生了單 Reactor 多線程 / 多進程的方案。
聞其名不如看其圖，先來看看「單 Reactor 多線程」方案的示意圖如下：
詳細說一下這個方案：
- Reactor 對象通過 select （IO 多路複用接口） 監聽事件，收到事件後通過 dispatch 進行分發，具體分發給 Acceptor 對象還是 Handler 對象，還要看收到的事件類型；
- 如果是連接建立的事件，則交由 Acceptor 對象進行處理，Acceptor 對象會通過 accept 方法 獲取連接，並創建一個 Handler 對象來處理後續的響應事件；
- 如果不是連接建立事件，則交由當前連接對應的 Handler 對象來進行響應；
上面的三個步驟和單 Reactor 單線程方案是相同的，接下來的步驟就開始不一樣了：
- Handler 對象不再負責業務處理，只負責數據的接收和發送，Handler 對象通過 read 讀取到數據後，會將數據發給子線程裡的 Processor 對象進行業務處理；
- 子線程裡的 Processor 對象就進行業務處理，處理完後，將結果發給主線程中的 Handler 對象，接著由 Handler 通過 send 方法將響應結果發送給 client；
- 單 Reator 多線程的方案優勢在於能夠充分利用多核 CPU 的能，那既然引入多線程，那麼自然就帶來了多線程競爭資源的問題。
例如，子線程完成業務處理後，要把結果傳遞給主線程的 Handler 進行發送，這裡涉及共享數據的競爭。
要避免多線程由於競爭共享資源而導致數據錯亂的問題，就需要在操作共享資源前加上互斥鎖，以保證任意時間裡只有一個線程在操作共享資源，待該線程操作完釋放互斥鎖後，其他線程才有機會操作共享數據。
聊完單 Reactor 多線程的方案，接著來看看單 Reactor 多進程的方案。
事實上，單 Reactor 多進程相比單 Reactor 多線程實現起來很麻煩，主要因為要考慮子進程 <-> 父進程的雙向通信，並且父進程還得知道子進程要將數據發送給哪個客戶端。
而多線程間可以共享數據，雖然要額外考慮並發問題，但是這遠比進程間通信的複雜度低得多，因此實際應用中也看不到單 Reactor 多進程的模式。
另外，「單 Reactor」的模式還有個問題，因為一個 Reactor 對象承擔所有事件的監聽和響應，而且只在主線程中運行，在面對瞬間高並發的場景時，容易成為性能的瓶頸的地方。
多 Reactor 多進程 / 線程#
要解決「單 Reactor」的問題，就是將「單 Reactor」實現成「多 Reactor」，這樣就產生了第 多 Reactor 多進程 / 線程的方案。
老規矩，聞其名不如看其圖。多 Reactor 多進程 / 線程方案的示意圖如下（以線程為例）：
方案詳細說明如下：
- 主線程中的 MainReactor 對象通過 select 監控連接建立事件，收到事件後通過 Acceptor 對象中的 accept 獲取連接，將新的連接分配給某個子線程；
- 子線程中的 SubReactor 對象將 MainReactor 對象分配的連接加入 select 繼續進行監聽，並創建一個 Handler 用於處理連接的響應事件。
- 如果有新的事件發生時，SubReactor 對象會調用當前連接對應的 Handler 對象來進行響應。
- Handler 對象通過 read -> 業務處理 -> send 的流程來完成完整的業務流程。
多 Reactor 多線程的方案雖然看起來複雜的，但是實際實現時比單 Reactor 多線程的方案要簡單的多，原因如下：
- 主線程和子線程分工明確，主線程只負責接收新連接，子線程負責完成後續的業務處理。
- 主線程和子線程的交互很簡單，主線程只需要把新連接傳給子線程，子線程無須返回數據，直接就可以在子線程將處理結果發送給客戶端。
大名鼎鼎的兩個開源軟件 Netty 和 Memcache 都採用了「多 Reactor 多線程」的方案。
採用了「多 Reactor 多進程」方案的開源軟件是 Nginx，不過方案與標準的多 Reactor 多進程有些差異。
具體差異表現在主進程中僅僅用來初始化 socket，並沒有創建 mainReactor 來 accept 連接，而是由子進程的 Reactor 來 accept 連接，通過鎖來控制一次只有一個子進程進行 accept（防止出現驚群現象），子進程 accept 新連接後就放到自己的 Reactor 進行處理，不會再分配給其他子進程。
Proactor#
Reactor 是非阻塞同步網絡模式，而 Proactor 是異步網絡模式。
Reactor 可以理解為「來了事件操作系統通知應用進程，讓應用進程來處理」，而 Proactor 可以理解為「來了事件操作系統來處理，處理完再通知應用進程」。這裡的「事件」就是有新連接、有數據可讀、有數據可寫的這些 I/O 事件這裡的「處理」包含從驅動讀取到內核以及從內核讀取到用戶空間。
區別在於 Reactor 模式是基於「待完成」的 I/O 事件，而 Proactor 模式則是基於「已完成」的 I/O 事件。
介紹一下 Proactor 模式的工作流程：
- Proactor Initiator 負責創建 Proactor 和 Handler 對象，並將 Proactor 和 Handler 都通過 Asynchronous Operation Processor 註冊到內核；
- Asynchronous Operation Processor 負責處理註冊請求，並處理 I/O 操作；
- Asynchronous Operation Processor 完成 I/O 操作後通知 Proactor；
- Proactor 根據不同的事件類型回調不同的 Handler 進行業務處理；
- Handler 完成業務處理；
可惜的是，在 Linux 下的異步 I/O 是不完善的， aio 系列函數是由 POSIX 定義的異步操作接口，不是真正的操作系統級別支持的，而是在用戶空間模擬出來的異步，並且僅僅支持基於本地文件的 aio 異步操作，網絡編程中的 socket 是不支持的，這也使得基於 Linux 的高性能網絡程序都是使用 Reactor 方案。
而 Windows 裡實現了一套完整的支持 socket 的異步編程接口，這套接口就是 IOCP，是由操作系統級別實現的異步 I/O，真正意義上異步 I/O，因此在 Windows 裡實現高性能網絡程序可以使用效率更高的 Proactor 方案。
一致性哈希#
在分佈式系統裡如何正確分配請求？#
當我們想提高系統的容量，就會將數據水平切分到不同的節點來存儲，也就是將數據分布到了不同的節點。比如一個分佈式 KV（key-valu） 緩存系統，某個 key 應該到哪個或者哪些節點上獲得，應該是確定的，不是說任意訪問一個節點都可以得到緩存結果的。
因此，我們要想一個能應對分佈式系統的負載均衡算法。
哈希算法#
哈希算法最簡單的做法就是進行取模運算，比如分佈式系統中有 3 個節點，基於 hash (key) % 3 公式對數據進行了映射。
但是有一個很致命的問題，如果節點數量發生了變化，也就是在對系統做擴容或者縮容時，必須遷移改變了映射關係的數據，最壞情況下所有數據都需要遷移，所以它的數據遷移規模是 O (M)，否則會出現查詢不到數據的問題。
一致性哈希算法#
一致哈希算法也用了取模運算，但與哈希算法不同的是，哈希算法是對節點的數量進行取模運算，而一致哈希算法是對 2^32 進行取模運算，是一個固定的值。
我們可以把一致哈希算法是對 2^32 進行取模運算的結果值組織成一個圓環，就像鐘表一樣，鐘表的圓可以理解成由 60 個點組成的圓，而此處我們把這個圓想像成由 2^32 個點組成的圓，這個圓環被稱為哈希環，如下圖：
一致性哈希要進行兩步哈希：
- 第一步：對存儲節點進行哈希計算，也就是對存儲節點做哈希映射，比如根據節點的 IP 地址進行哈希；
- 第二步：當對數據進行存儲或訪問時，對數據進行哈希映射；
所以，一致性哈希是指將「存儲節點」和「數據」都映射到一個首尾相連的哈希環上。
問題來了，對「數據」進行哈希映射得到一個結果要怎麼找到存儲該數據的節點呢？
答案是，映射的結果值往順時針的方向的找到第一個節點，就是存儲該數據的節點。
如果我們要把節點 D 刪除，只需要把 D 遷移到 B 就可以了。因此，在一致哈希算法中，如果增加或者移除一個節點，僅影響該節點在哈希環上順時針相鄰的後繼節點，其它數據也不會受到影響。
但是一致性哈希算法並不保證節點能夠在哈希環上分布均勻，這樣就會帶來一個問題，會有大量的請求集中在一個節點上。
如何通過虛擬節點提高均衡度？#
要想解決節點能在哈希環上分配不均勻的問題，就是要有大量的節點，節點數越多，哈希環上的節點分布的就越均勻。所以這個時候我們就加入虛擬節點，也就是對一個真實節點做多個副本。
具體做法是，不再將真實節點映射到哈希環上，而是將虛擬節點映射到哈希環上，並將虛擬節點映射到實際節點，所以這裡有「兩層」映射關係。
另外，虛擬節點除了會提高節點的均衡度，還會提高系統的穩定性。當節點變化時，會有不同的節點共同分擔系統的變化，因此穩定性更高。
比如，當某個節點被移除時，對應該節點的多個虛擬節點均會移除，而這些虛擬節點按順時針方向的下一個虛擬節點，可能會對應不同的真實節點，即這些不同的真實節點共同分擔了節點變化導致的壓力。
而且，有了虛擬節點後，還可以為硬件配置更好的節點增加權重，比如對權重更高的節點增加更多的虛擬機節點即可。
因此，帶虛擬節點的一致性哈希方法不僅適合硬件配置不同的節點的場景，而且適合節點規模會發生變化的場景。