Linux高性能伺服器設計

C10K和C10M

計算機領域的很多技術都是需求推動的，上世紀90年代，由于網際網路的飛速發展，網絡伺服器無法支撐快速增長的使用者規模。1999年，Dan Kegel提出了著名的C10問題：一台伺服器上同時處理10000個客戶網絡連接配接。10000個網絡連接配接并不會發送請求到伺服器，有些連接配接并不活躍，同一時刻，隻有極少的部分連接配接發送請求。不同的服務類型，每個連接配接發送請求的頻率也不相同，遊戲伺服器的連接配接會頻繁的發送請求，而Web伺服器的連接配接發送請求的頻率就低很多。無論如何，根據經驗法則，對于特定的服務類型，連接配接越多，同一時刻發送請求的連接配接也越多。

時至今日，C10K問題當然早已解決，不僅如此，一台機器能支撐的連接配接越來越多，後來提出了C10M問題，在一台機器上支撐1000萬的連接配接，2015年，MigratoryData在單機承載12M的連接配接，解決了C10M問題。

本文先回顧C10問題的解決方案，再探讨如何建構支撐C10M的應用程式，聊聊其中涉及的各種技術。

C10K問題的解決

時間退回到1999年，當時要實作一個網絡伺服器，大概有這樣幾種模式

簡單程序/線程模型

這是一種非常簡單的模式，伺服器啟動後監聽端口，阻塞在accept上，當新網絡連接配接建立後，accept傳回新連接配接，伺服器啟動一個新的程序/線程專門負責這個連接配接。從性能和伸縮性來說，這種模式是非常糟糕的，原因在于

程序/線程建立和銷毀的時間，作業系統建立一個程序/線程顯然需要時間，在一個繁忙的伺服器上，如果每秒都有大量的連接配接建立和斷開，采用每個程序/線程處理一個客戶連接配接的模式，每個新連接配接都要建立建立一個程序/線程，當連接配接斷開時，銷毀對應的線程/程序。建立和銷毀程序/線程的操作消耗了大量的CPU資源。使用程序池和線程池可以緩解這個問題。
記憶體占用。主要包含兩方面，一個是核心資料結構所占用的記憶體空間，另外一個是Stack所占用的記憶體。有些應用的調用棧很深，比如Java應用，經常能看到幾十上百層的調用棧。
上下文切換的開銷。上下文切換時，作業系統的排程器中斷目前線程，選擇另外一個可運作的線程在CPU上繼續運作。排程器需要儲存目前線程的現場資訊，然後選擇一個可運作的線程，再将新線程的狀态恢複到寄存器中。儲存和恢複現場所需要的時間和CPU型号有關，選擇一個可運作的線程則完全是軟體操作，Linux 2.6才開始使用常量時間的排程算法。以上是上下文切換的直接開銷。除此之外還有一些間接開銷，上下文切換導緻相關的緩存失效，比如L1/L2 Cache，TLB等，這些也會影響程式的性能，但是間接開銷很難衡量。

有意思的是，這種模式雖然性能極差，但卻依然是我們今天最常見到的模式，很多Web程式都是這樣的方式在運作。

select/poll

另外一種方式是使用select/poll，在一個線程内處理多個客戶連接配接。select和poll能夠監控多個socket檔案描述符，當某個檔案描述符就緒，select/soll從阻塞狀态傳回，通知應用程式可以處理使用者連接配接了。使用這種方式，我們隻需要一個線程就可以處理大量的連接配接，避免了多程序/線程的開銷。之是以把select和poll放在一起說，原因在于兩者非常相似，性能上基本沒有差別，唯一的差別在于poll突破了select 1024個檔案描述符的限制，然而當檔案描述符數量增加時，poll性能急劇下降，是以所謂突破1024個檔案描述符實際上毫無意義。select/poll并不完美，依然存在很多問題：

每次調用select/poll，都要把檔案描述符的集合從使用者位址空間複制到核心位址空間
select/poll傳回後，調用方必須周遊所有的檔案描述符，逐一判斷檔案描述符是否可讀/可寫。

這兩個限制讓select/poll完全失去了伸縮性。連接配接數越多，檔案描述符就越多，檔案描述符越多，每次調用select/poll所帶來的使用者空間到核心空間的複制開銷越大。最嚴重的是當封包達到，select/poll傳回之後，必須周遊所有的檔案描述符。假設現在有1萬個連接配接，其中隻一個連接配接發送了請求，但是select/poll就要把1萬個連接配接全部檢查一遍。

epoll

FreeBSD 4.1引入了kqueue，此時是2000年7月，而在Linux上，還要等待2年後的2002年才開始引入kqueue的類似實作: epoll。epoll最初于 2.5.44進入Linux kernel mainline，此時已經是2002年，距離C10K問題提出已經過了3年。

epoll是如何提供一個高性能可伸縮的IO多路複用機制呢？首先，epoll引入了epoll instance這個概念，epoll instance在核心中關聯了一組要監聽的檔案描述符配置：interest list，這樣的好處在于，每次要增加一個要監聽的檔案描述符，不需要把所有的檔案描述符都配置一次，然後從使用者位址空間複制到核心位址空間，隻需要把單個檔案描述符複制到核心位址空間，複制開銷從O(n)降到了O(1)。

注冊完檔案描述符後，調用epoll_wait開始等待檔案描述符事件。epoll_wait可以隻傳回已經ready的檔案描述符，是以，在epoll_wait傳回之後，程式隻需要處理真正需要處理的檔案描述符，而不用把所有的檔案描述符全部周遊一遍。假設在全部N個檔案描述符中，隻有一個檔案描述符Ready，select/poll要執行N次循環，epoll隻需要一次。

epoll出現之後，Linux上才真正有了一個可伸縮的IO多路複用機制。基于epoll，能夠支撐的網絡連接配接數取決于硬體資源的配置，而不再受限于核心的實作機制。CPU越強，記憶體越大，能支撐的連接配接數越多。

程式設計模型

Reactor和proactor

不同的作業系統上提供了不同的IO多路複用實作，Linux上有epoll，FreeBSD有kqueue，Windows有IOCP。對于需要跨平台的程式，必然需要一個抽象層，提供一個統一的IO多路複用接口，屏蔽各個系統接口的差異性。

Reactor是實作這個目标的一次嘗試，最早出現在Douglas C. Schmidt的論文"The Reactor An Object-Oriented Wrapper for Event-Driven Port Monitoring and Service Demultiplexing"中。從論文的名字可以看出，Reactor是poll這種程式設計模式的一個面向對象包裝。考慮到論文的時間，當時正是面向對象概念正火熱的時候，什麼東西都要蹭蹭面向對象的熱度。論文中，DC Schmidt描述了為什麼要做這樣的一個Wrapper，給出了下面幾個原因

作業系統提供的接口太複雜，容易出錯。select和poll都是通用接口，因為通用，增加了學習和正确使用的複雜度。
接口抽象層次太低，涉及太多底層的細節。
不能跨平台移植。
難以擴充。

實際上除了第三條跨平台，其他幾個理由實在難以站得住腳。select/poll這類接口複雜嗎，使用起來容易出錯嗎，寫出來的程式難以擴充嗎？不過不這麼說怎麼展現Reactor的價值呢。正如論文名稱所說的，Reactor本質是對作業系統IO多路複用機制的一個面向對象包裝，為了證明Reactor的價值，DC Schmidt還用C++面向對象的特性實作了一個程式設計架構：ACE，實際上使用ACE比直接使用poll或者epoll複雜多了。

後來DC Schmidt寫了一本書《面向模式的軟體架構》，再次提到了Reactor，并重新命名為Reactor Pattern，現在網絡上能找到的Reactor資料，基本上都是基于Reactor Pattern，而不是早期的面向Object-Orientend Wrapper。

《面向模式的軟體》架構中還提到了另外一種叫做Proactor的模式，和Reactor非常類似，Reactor針對同步IO，Proactor則針對異步IO。

Callback，Future和纖程

Reactor看上去并不複雜，但是想編寫一個完整的應用程式時候就會發現其實沒那麼簡單。為了避免Reactor主邏輯阻塞，所有可能會導緻阻塞的操作必須注冊到epoll上，帶來的問題就是處理邏輯的支離破碎，大量使用callback，産生的代碼複雜難懂。如果應用程式中還有非網絡IO的阻塞操作，問題更嚴重，比如在程式中讀寫檔案。Linux中檔案系統操作都是阻塞的，雖然也有Linux AIO，但是一直不夠成熟，難堪大用。很多軟體采用線程池來解決這個問題，不能通過epoll解決的阻塞操作，扔到一個線程池執行。這又産生了多線程記憶體開銷和上下文切換的問題。

Future機制是對Callback的簡單優化，本質上還是Callback，但是提供了一緻的接口，代碼相對來說簡單一些，不過在實際使用中還是比較複雜的。Seastar是一個非常徹底的future風格的架構，從它的代碼可以看到這種程式設計風格真的非常複雜，阻塞式程式設計中一個函數幾行代碼就能搞定的事情，在Seastar裡需要上百行代碼，幾十個labmda (在Seastar裡叫做continuation)。

纖程是一種使用者态排程的線程，比如Go語言中的goroutine，有些人可能會把這種機制成為coroutine，不過我認為coroutine和纖程還是有很大差別的，coroutine是泛化的子程序，具有多個進入和退出點，用來一些一些互相協作的程式，典型的例子就是Python中的generator。纖程則是一種運作和排程機制。

纖程真正做到了高性能和易用，在Go語言中，使用goroutine實作的高性能伺服器是一件輕松愉快的事情，完全不用考慮線程數、epoll、回調之類的複雜操作，和編寫阻塞式程式完全一樣。

網絡優化

Kernel bypass

網絡子系統是Linux核心中一個非常龐大的元件，提供了各種通用的網絡能力。通用通常意味在在某些場景下并不是最佳選擇。實際上業界的共識是Linux核心網絡不支援超大并發的網絡能力。根據我過去的經驗，Linux最大隻能處理1MPPS，而現在的10Gbps網卡通常可以處理10MPPS。随着更高性能的25Gbps，40Gbps網卡出現，Linux核心網絡能力越發捉襟見肘。

為什麼Linux不能充分發揮網卡的處理能力？原因在于：

大多數網卡收發使用中斷方式，每次中斷處理時間大約100us，另外要考慮cache miss帶來的開銷。部分網卡使用NAPI，輪詢+中斷結合的方式處理封包，當封包放進隊列之後，依然要觸發軟中斷。
資料從核心位址空間複制到使用者位址空間。
收發包都有系統調用。
網卡到應用程序的鍊路太長，包含了很多不必要的操作。

Linux高性能網絡一個方向就是繞過核心的網絡棧(kernel bypass)，業界有不少嘗試

PF_RING 高效的資料包捕獲技術，比libpcap性能更好。需要自己安裝核心子產品，啟用ZC Driver，設定transparent_mode=2的情況下，封包直接投遞到用戶端程式，繞過核心網絡棧。
Snabbswitch 一個Lua寫的網絡架構。完全接管網卡，使用UIO(Userspace IO)技術在使用者态實作了網卡驅動。
Intel DPDK，直接在使用者态處理封包。非常成熟，性能強大，限制是隻能用在Intel的網卡上。根據DPDK的資料，3GHz的CPU Core上，平均每個封包的處理時間隻要60ns（一次記憶體的通路時間）。
Netmap 一個高性能收發原始資料包的架構，包含了核心子產品以及使用者态庫函數，需要網卡驅動程式配合，是以目前隻支援特定的幾種網卡類型，使用者也可以自己修改網卡驅動。
XDP，使用Linux eBPF機制，将封包處理邏輯下放到網卡驅動程式中。一般用于封包過濾、轉發的場景。

kernel bypass技術最大的問題在于不支援POSIX接口，使用者沒辦法不修改代碼直接移植到一種kernel bypass技術上。對于大多數程式來說，還要要運作在标準的核心網絡棧上，通過調整核心參數提升網絡性能。

網卡多隊列

封包到達網卡之後，在一個CPU上觸發中斷，CPU執行網卡驅動程式從網卡硬體緩沖區讀取封包内容，解析後放到CPU接收隊列上。這裡所有的操作都在一個特定的CPU上完成，高性能場景下，單個CPU處理不了所有的封包。對于支援多隊列的網卡，封包可以分散到多個隊列上，每個隊列對應一個CPU處理，解決了單個CPU處理瓶頸。

為了充分發揮多隊列網卡的價值，我們還得做一些額外的設定：把每個隊列的中斷号綁定到特定CPU上。這樣做的目的，一方面確定網卡中斷的負載能配置設定到不同的CPU上，另外一方面可以将負責網卡中斷的CPU和負責應用程式的CPU區分開，避免互相幹擾。

在Linux中，/sys/class/net/${interface}/device/msi_irqs下儲存了每個隊列的中斷号，有了中斷号之後，我們就可以設定中斷和CPU的對應關系了。網上有很多文章可以參考。

網卡Offloading

回憶下TCP資料的發送過程：應用程式将資料寫到套接字緩沖區，核心将緩沖區資料切分成不大于MSS的片段，附加上TCP Header和IP Header，計算Checksum，然後将資料推到網卡發送隊列。這個過程中需要CPU全程參與，随着網卡的速度越來越快，CPU逐漸成為瓶頸，CPU處理資料的速度已經趕不上網卡發送資料的速度。經驗法則，發送或者接收1bit/s TCP資料，需要1Hz的CPU，1Gbps需要1GHz的CPU，10Gbps需要10GHz的CPU，已經遠超單核CPU的能力，即使能完全使用多核，假設單個CPU Core是2.5GHz，依然需要4個CPU Core。

為了優化性能，現代網卡都在硬體層面內建了TCP分段、添加IP Header、計算Checksum等功能，這些操作不再需要CPU參與。這個功能叫做tcp segment offloading，簡稱tso。使用ethtool -k 可以檢查網卡是否開啟了tso

除了tso，還有其他幾種offloading，比如支援udp分片的ufo，不依賴驅動的gso，優化接收鍊路的lro

充分利用多核

随着摩爾定律失效，CPU已經從追求高主頻轉向追求更多的核數，現在的伺服器大都是96核甚至更高。建構一個支撐C10M的應用程式，必須充分利用所有的CPU，最重要的是程式要具備水準伸縮的能力：随着CPU數量的增多程式能夠支撐更多的連接配接。

很多人都有一個誤解，認為程式裡使用了多線程就能利用多核，考慮下CPython程式，你可以建立多個線程，但是由于GIL的存在，程式最多隻能使用單個CPU。實際上多線程和并行本身就是不同的概念，多線程表示程式内部多個任務并發執行，每個線程内的任務可以完全不一樣，線程數和CPU核數沒有直接關系，單核機器上可以跑幾百個線程。并行則是為了充分利用計算資源，将一個大的任務拆解成小規模的任務，配置設定到每個CPU上運作。并行可以通過多線程實作，系統上有幾個CPU就啟動幾個線程，每個線程完成一部分任務。

并行程式設計的難點在于如何正确處理共享資源。并發通路共享資源，最簡單的方式就加鎖，然而使用鎖又帶來性能問題，擷取鎖和釋放鎖本身有性能開銷，鎖保護的臨界區代碼不能隻能順序執行，就像CPython的GIL，沒能充分利用CPU。

Thread Local和Per-CPU變量

這兩種方式的思路是一樣的，都是建立變量的多個副本，使用變量時隻通路本地副本，是以不需要任何同步。現代程式設計語言基本上都支援Thread Local，使用起來也很簡單，C/C++裡也可以使用__thread标記聲明ThreadLocal變量。

Per-CPU則依賴作業系統，當我們提到Per-CPU的時候，通常是指Linux的Per-CPU機制。Linux核心代碼中大量使用Per-CPU變量，但應用代碼中并不常見，如果應用程式中工作線程數等于CPU數量，且每個線程Pin到一個CPU上，此時才可以使用。

原子變量

如果共享資源是int之類的簡單類型，通路模式也比較簡單，此時可以使用原子變量。相比使用鎖，原子變量性能更好。在競争不激烈的情況下，原子變量的操作性能基本上和加鎖的性能一緻，但是在并發比較激烈的時候，等待鎖的線程要進入等待隊列等待重新排程，這裡的挂起和重新排程過程需要上下文切換，浪費了更多的時間。

大部分程式設計語言都提供了基本變量對應的原子類型，一般提供set, get, compareAndSet等操作。

lock-free

lock-free這個概念來自

An algorithm is called non‐blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; an algorithm is called lock‐free if, at each step, some thread can make progress.

non-blocking算法任何線程失敗或者挂起，不會導緻其他線程失敗或者挂起，lock-free則進一步保證線程間無依賴。這個表述比較抽象，具體來說，non-blocking要求不存在互斥，存在互斥的情況下，線程必須先擷取鎖再進入臨界區，如果目前持有鎖的線程被挂起，等待鎖的線程必然需要一直等待下去。對于活鎖或者饑餓的場景，線程失敗或者挂起的時候，其他線程完全不僅能正常運作，說不定還解決了活鎖和饑餓的問題，是以活鎖和饑餓符合non-blocking，但是不符合lock-free。

實作一個lock-free資料結構并不容易，好在已經有了幾種常見資料結構的的lock-free實作：buffer, list, stack, queue, map, deque，我們直接拿來使用就行了。

優化對鎖的使用

有時候沒有條件使用lock-free，還是得用鎖，對于這種情況，還是有一些優化手段的。首先使用盡量減少臨界區的大小，使用細粒度的鎖，鎖粒度越細，并行執行的效果越好。其次選擇适合的鎖，比如考慮選擇讀寫鎖。

CPU affinity

使用CPU affinity機制合理規劃線程和CPU的綁定關系。前面提到使用CPU affinity機制，将多隊列網卡的中斷處理分散到多個CPU上。不僅是中斷處理，線程也可以綁定，綁定之後，線程隻會運作在綁定的CPU上。為什麼要将線程綁定到CPU上呢？綁定CPU有這樣幾個好處

為線程保留CPU，確定線程有足夠的資源運作
提高CPU cache的命中率，某些對cache敏感的線程必須綁定到CPU上才行。
更精細的資源控制。可以預先需要靜态劃分各個工作線程的資源，例如為每個請求處理線程配置設定一個CPU，其他背景線程共享一個CPU，工作線程和中斷處理程式工作在不同的CPU上。
NUMA架構中，每個CPU有自己的記憶體控制器和記憶體插槽，CPU通路本地記憶體别通路遠端記憶體快3倍左右。使用affinity将線程綁定在CPU上，相關的資料也配置設定到CPU對應的本地記憶體上。

Linux上設定CPU affinity很簡單，可以使用指令行工具taskset，也可以在程式内直接調用API

sched_getaffinity

和

sched_setaffinity

其他優化技術

使用Hugepage

Linux中，程式内使用的記憶體位址是虛拟位址，并不是記憶體的實體位址。為了簡化虛拟位址到實體位址的映射，虛拟位址到實體位址的映射最小機關是“Page”，預設情況下，每個頁大小為4KB。CPU指令中出現的虛拟位址，為了讀取記憶體中的資料，指令執行前要把虛拟位址轉換成記憶體實體位址。Linux為每個程序維護了一張虛拟位址到實體位址的映射表，CPU先查表找到虛拟位址對應的實體位址，再執行指令。由于映射表維護在記憶體中，CPU查表就要通路記憶體。相對CPU的速度來說，記憶體其實是相當慢的，一般來說，CPU L1 Cache的通路速度在1ns左右，而一次記憶體通路需要60-100ns，比CPU執行一條指令要慢得多。如果每個指令都要通路記憶體，比如嚴重拖慢CPU速度，為了解決這個問題，CPU引入了TLB(translation lookaside buffer)，一個高性能緩存，緩存映射表中一部分條目。轉換位址時，先從TLB查找，沒找到再讀記憶體。

顯然，最理想的情況是映射表能夠完全緩存到TLB中，位址轉換完全不需要通路記憶體。為了減少映射表大小，我們可以使用“HugePages”：大于4KB的記憶體頁。預設HugePages是2MB，最大可以到1GB。

避免動态配置設定記憶體

記憶體配置設定是個複雜且耗時的操作，涉及空閑記憶體管理、配置設定政策的權衡（配置設定效率，碎片），尤其是在并發環境中，還要保證記憶體配置設定的線程安全。如果記憶體配置設定成為了應用瓶頸，可以嘗試一些優化政策。比如記憶體複用i：不要重複配置設定記憶體，而是複用已經配置設定過的記憶體，在C++/Java裡則考慮複用已有對象，這個技巧在Java裡尤其重要，不僅能降低對象建立的開銷，還避免了大量建立對象導緻的GC開銷。另外一個技巧是預先配置設定記憶體，實際上相當于在應用内實作了一套簡單的記憶體管理，比如Memcached的Slab。

Zero Copy

對于一個Web伺服器來說，響應一個靜态檔案請求需要先将檔案從磁盤讀取到記憶體中，再發送到用戶端。如果自信分析這個過程，會發現資料首先從磁盤讀取到核心的頁緩沖區，再從頁緩沖區複制到Web伺服器緩沖區，接着從Web伺服器緩沖區發送到TCP發送緩沖區，最後經網卡發送出去。這個過程中，資料先從核心複制到程序内，再從程序内回到核心，這兩次複制完全是多餘的。Zero Copy就是類似情況的優化方案，資料直接在核心中完成處理，不需要額外的複制。

Linux中提供了幾種ZeroCopy相關的技術，包括

sendfile

splice

copy_file_range

,Web伺服器中經常使用

sendfile

優化性能。

最後

千萬牢記：不要過早優化。

優化之前，先考慮兩個問題：

現在的性能是否已經滿足需求了
如果真的要優化，是不是已經定位了瓶頸

在回答清楚這兩個問題之前，不要盲目動手。