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優化性能。
最後
千萬牢記：不要過早優化。
優化之前，先考慮兩個問題：
- 現在的性能是否已經滿足需求了
- 如果真的要優化，是不是已經定位了瓶頸
在回答清楚這兩個問題之前，不要盲目動手。
閱讀更多 阿里云云棲社區 的文章
