大賽背景

第四屆阿里中間件性能挑戰賽是由阿里巴巴集團發起，阿里巴巴中間(Aliware)、阿里雲天池聯合舉辦，是集團唯一的工程性品牌賽事。大賽的初衷是為熱愛技術的年輕人提供一個挑戰世界級技術問題的舞台，希望選手在追求性能極致的同時，能深刻體會技術人的匠心精神，用技術為全社會創造更大的價值。

本文是亞軍選手「做作業」的解題思路，來自南京理工大學的95後開發者。

初賽部分

一、賽題重述及理解

初賽主要的考察點是實現一個高性能的http伺服器，一套優秀的負載均衡演算法。而協議轉換僅需要對協議進行詳細了解即可實現，屬於基本技能考察。而服務的註冊和發現參考demo中的實現即可，屬於比較常用的處理邏輯。

針對高性能的http伺服器，想要在競賽環境下取得較好的成績，使用常用通用http框架是較難取得高分的，因為consumer agent和consumer共享一個docker運行環境，在512連接測試環境下，系統資源就已經很緊張了，需要在捨棄一部分http特性的情況下才能將consumer性能發揮到極致。所以自己造輪子是一個比較合適的方案。Consumeragent的總體結構(所有邏輯基本集中在這)如圖1所示。

圖1 Consumer Agent結構

二、網路編程模型的選擇

高並發網路模型首選epoll，在連接數增多的情況下，其性能不會像select和poll一樣明顯下降，是由於內核對其進行了特殊優化，不是線性遍歷所有連接。實際測試中發現，因為請求是在收到響應後才會繼續發出，所以不僅要求高並發，同時要求低延遲，因為延遲疊加的原因也會導致QPS下降。

而我們使用的常見的非同步網路庫libuv、libevent等都是one loop per thread的，即一個線程一個事件循環，這種設計具有較高的吞吐量，但請求只能綁定到一個事件循環上，一旦請求不均勻，則會導致一核有難眾核圍觀的情況，對於動態均衡線程負載很不適合。

基於此原因我決定自己造輪子，讓多個線程處理一個epoll循環，讓操作系統的線程調度均衡請求，同時所有連接均綁定到一個事件循環上，也便於處理。最終我選擇使用多線程的et模式的epoll模型，整體框架代碼如圖2所示。

圖2 多線程epoll框架

整體框架非常簡潔，所有網路處理類僅需繼承CepollCallback完成網路數據的讀取和寫入即可。

圖3 epoll回調抽象類

三、程序整體流程

Consumer端agent負責解析http請求轉換為dubbo請求，以udp形式發給provider agent處理，provider agent收到udp後直接傳給provider dubbo服務處理，將結果以udp形式回傳，consumer agent處理後返回http形式結果。

圖4、5 CA/PA處理流程

程序初始化的時候provider agent調用etcd介面將自己的服務註冊，consumer agent調用etcd介面獲取到註冊的provider agent地址，由於採用udp協議通信，故不用提前建立連接。Provider agent端也僅在第一個請求到達時建立到provider的tcp連接，保證provider已經啟動完畢可以接受請求。

四、中間協議設計

考慮到高吞吐量，低延遲，採用了udp協議，請求為單包單請求，數據格式為dubbo請求格式，相應包為單包多相應，數據格式為dubbo響應。即consumer agent端實現協議轉換，provider agent端實現udp轉tcp。

由於請求僅存在於一個包中，所以無需考慮亂序情況，直接將收到的數據包進行重組發到dubbo的tcp連接上，提供最大的吞吐量和最低的延遲。具體處理操作如圖3。

圖3 udp重組轉發tcp

同時為了減少系統調用，可以一直取udp包，當緩衝滿後一次性寫入tcp的緩衝中。同理在tcp轉udp時，可以將數據湊成接近MTU，減少網路壓力。如圖4所示。

圖4 udp單包多相應

還有很多工程上的技巧，比如調整緩衝區大小等，保證每次非同步調用都能成功，減少系統調用次數。

五、負載均衡演算法

負載均衡採用計數方法實現，每次請求發送到和配置負載比例差距最大的Provider上，如果3台都超出200負載，則進行請求排隊，當有請求返回時，優先調度排隊請求。整體如圖5所示。

圖5 負載均衡演算法

六、創新點及工程價值

1、consumer agent實現負載均衡和請求控制，能夠有效在consumer使用排隊機制端遏制過載，不把過載傳遞到網路傳輸上。

2、兩個agent間使用udp傳輸，利用udp的低損耗，因為是單包單請求，即使亂序也能隨意合併重組，丟包不會造成協議出錯，僅造成超時出錯，非常適合這種實時性和吞吐量要求高的情況。

3、在請求id中存儲了調用者和時間戳，能正確相應合適的http調用者的同時，能夠統計性能數據，作為調參依據。

4、多線程等待epoll的et模式，能夠充分挖掘網卡通信潛力，不存在單線程拷貝速度比網路傳輸慢的情況，同時省去了任務隊列，每個處理線程具備一定的CPU計算處理能力，也能最小化響應時間，使用自旋鎖後保證一個連接的消息不會被多個線程處理，健壯性有保障。

5、設置合適的tcp緩衝區大小，在不阻塞情況下保證每次write調用都會成功。

複賽部分

一、 賽題重述及理解

複賽的主要考察點是單機實現100W規模的隊列信息存儲與讀取，具體考察如何在單進程空間中的實現1M個隊列的信息存儲，如何設計合理的數據存儲及索引結構，在特定硬碟的情況下完成高性能的順序寫、隨機讀和順序讀功能。同時由於測評環境是4C8G的，如何合理分配利用系統資源也是很重要的（任何對隊列存儲的東西都會放大100W倍，同時維護這麼多數據需要佔用更多的系統資源）。

針對上述考察點，本隊提出了一套完整的隊列消息數據存儲方案，稀疏索引存儲方案。程序開發迭代中的總共提出了3套寫入方案，2套讀方案，分別在Java和C++平台上進行了實現。

二、 整體系統架構

系統的整體結構較為簡單和清晰，主要分為以下幾個部分：每個隊列對應一個對象，用於維護buffer等必要結構；一個容器負責將隊列名映射到隊列對象；文件管理對象負責維護讀寫文件；負責整體讀寫狀態切換和管理的控制模塊。如圖6所示。

圖6 複賽系統整體架構

三、 消息存儲方案

考慮到順序寫、隨機讀、順序讀的使用場景，參考文件系統以簇為單位的文件存儲方式，設計了以塊為單位的隊列消息存儲方式。

圖7 隊列消息存儲方式

考慮到不定長消息及超長消息的情況，設計了變長整形+消息體的結構記錄單條消息，同時支持跨塊的消息。

圖8 消息數據存儲方式

每個塊開頭都是變長整形，每個VarInt存儲的都是目前還剩的消息體長度（便於快速跳過或判斷消息是否繼續跨塊），這種結構支持任意長度的消息，如果塊剩餘空間不足寫VarInt，則padding。

考慮到節省磁碟空間，在CPU充足的情況下，可以採用消息數據壓縮，但是線上CPU緊張，考慮到通用性並未使用特化壓縮演算法。實際測試中由於消息生成性能及CPU性能的問題，未開啟壓縮功能，但在程序中預留了壓縮介面，以適應各種場合。圖9所示為預留的壓縮介面。

圖9 預留的壓縮介面

四、 隊列寫入方案

設計好了消息存儲方案，剩下的就是合適的消息讀寫方案了，由於讀取方案比較固定，而寫入由於系統資源的匱乏(4C8G)，需要合理設計。

1、mmap方案(Java實現)（淘汰）

本方案使用引用計數機制控制mmap生命周期，同時mmap的塊存儲在hash cache（定長slot基於hash衝突淘汰的cache演算法）中，cache也會增加引用計數，這樣在連續寫文件時保證了較好cache命中率。實現結構如圖10所示。

圖10 mmap方案

優點：完全不用flush操作，因為讀寫都是引用mmap實現的。

缺點：由於page cache臟超過20%會block寫入線程，為了不阻塞線程，隊列塊的大小必須非常小(512bytes，1M隊列512MB)，性能較差。

2、整體內存引用方案(Java實現)（淘汰）

考慮到mmap直接作用在page cache上，受臟頁比例影響，難以提升緩衝大小，故考慮使用整體內存方案，機制和mmap類似。同樣使用引用計數機制控制寫入緩衝區內存塊的生命周期，額外使用獨立線程負責將緩衝區刷盤。該方法能夠等待新緩衝區內存塊有效保障不寫入過載，同時使用環形緩衝實現內存塊及等待對象復用。使用2K大小block的java程序線上成績為167w。方案整體流程如圖11所示。

圖11整體內存引用方案

優點：沒有額外拷貝，非同步寫入不會阻塞。

缺點：由於內存限制，存在寫入線程等待刷盤數據釋放，block大小受限制(2K，如果使用4K則會存在寫入等待內存交換出來，寫入有波動，性能不是最優)。

3、分片內存池方案(C++實現)（最優成績）

綜合前2種方案後，提出採用分片內存池+iovec內存重組寫入的方案。具體實現為將block分為更小的slice，每次緩衝區申請一個slice，寫滿一個block後用iovec提交。

寫入線程將提交的slice用iovec拼接成更大的part，整體寫入磁碟。寫入後將slice釋放回內存池便於後續隊列緩衝使用。雖然均勻寫入是一種糟糕的寫入方式，存在緩衝申請激增的情況，但由於分片機制的存在，每次激增為1M*slice的大小，可以通過slice大小控制。具體流程如圖12，13所示。

圖12分片內存池方案

優點：更細粒度的內存分配和釋放，4K大小block情況下緩衝區能均勻移動，不會阻塞，寫入和落盤同步進行；能在有限內存中實現更大的block。

圖13 分片內存方案細節

內部使用的ring buffer方案及代碼如圖14所示，所有對象均實現了復用。

圖14 ring buffer實現細節

五、 索引方案

由於內存空間限制，索引記錄所有消息的偏移並不是個好方案。本系統方案採用了稀疏索引，因為設計的消息存儲結構保證塊內消息能夠自行區分，僅記錄塊信息即可。只要能知道消息所在的塊的位置和消息是該塊的第幾個即可定位到該消息。

每個消息塊僅需要記錄3個信息：塊所在文件偏移(塊號)；塊內消息數；上個塊消息是否跨塊。通過索引定位到具體消息數據的方法也十分簡單。

1、通過從前往後累加每個塊的消息數量，快速定位到消息所在塊；

2、通過索引查找到塊所在文件偏移，並完整讀出塊(4K讀)；

3、通過是否跨塊信息和目標消息ID，確定需要跳過的消息數，快速跳過無用消息。

4、讀取目標消息。具體流程如圖15所示。

圖15 消息數據定位流程

定位完成後可以連續讀，一旦發現長度超出當前塊，則說明讀到跨塊消息，繼續切到下一塊讀取即可。

六、 隨機讀與連續讀

隨機讀取的消息落到一個塊內有較大的概率，故即使是讀一個小範圍的數據，大部分情況能一次IO讀取完成。針對連續讀，記錄每次讀取到的位置，如果下次訪問是從0或上次讀取的位置，則認為是連續消費，對隊列的下一個塊發起readahead操作，將其讀入到page cache中，實測可以提升40%性能。由於塊的大小是4K，連續讀時不會讀入任何無效數據，操作系統的page cache能提供非常高的讀取性能。

七、 Map容器優化

由於消息寫入介面是以隊列名對隊列進行區分的，隊列名到隊列對象的映射也是系統的瓶頸所在。針對數字後綴隊列名進行特殊hash計算處理，可以降低衝突概率。對於後綴計算hash衝突的情況，使用正常哈希計算，離散到32個加鎖的unordered map中進行存儲，保證魯棒性和性能。由於後綴的區分度高，spin lock基本沒有衝突，100W插入比傳統map快幾百ms，100W查找快幾十ms。Suffix map結構如圖16所示。

圖16 suffix map結構

八、 讀寫狀態切換

程序一開始就設計有內存和磁碟協同工作的代碼，但由於緩衝佔用內存過大，使得後續隨機讀和連續讀（依賴page cache）存在性能下降的問題，採用了讀之前將緩衝全部落盤的策略。

在第一次讀的時候，block所有讀線程，落盤，釋放所有緩衝內存（~5.5G）然後開始讀取操作。由於空餘緩衝是全部填充padding的，即使再寫入隊列，數據也不會出錯。同時整體狀態可以切換回寫狀態(需重新申請緩衝內存)。

九、 創新性與工程價值

1、針對內存不足使用內存分片+iovec重組寫技術，達到在小內存的情況下寫內存和寫硬碟同時進行的目的，極大提升了寫磁碟性能。線上測試寫時存在CPU idle>0現象，說明生產已大於寫盤速度。

2、針對隊列名稱改進了map，提出suffix map，針對後綴進行hash（現實情況下也大量存在編號結尾的隊列名），極大降低了hash碰撞幾率（測評數據中沒有碰撞），同時用自旋鎖和多個細粒度的unordered_map處理了碰撞情況，提升性能的時候保證了map的正確性魯棒性。

3、先寫緩衝，緩衝滿了排隊，最後填滿一個大block後刷盤，極大利用了SSD順序寫入性能，同時在隊列不均勻時也能提供同樣的高性能。

4、變長整形+消息存儲，及跨塊消息，超長消息的處理機制保證任意長度消息都能正確處理，並有同樣的高性能。

5、稀疏索引，只對塊的偏移和消息數量做記錄，整個索引大小僅29*（4（blockId）+2（number））*1000000≈166MB，完全可以存儲在內存中。

6、使用ring buffer，分散寫入和等待對象，採用引用機制（最後釋放引用的線程負責提交該塊到寫入隊列中），工作期間沒有任何對象創建和銷毀，建立在數組上，充分利用cpu cache，提升了性能。

7、整體內存分配，然後分片，使用完成後整體釋放，降低了內存管理的cpu消耗。

8、設計時考慮了緩衝和磁碟協同工作讀，不用將緩衝刷盤僅僅只用等待當前io完成，正確性可以保證，但由於佔用太多內存，性能不好，故後期改為全刷盤操作。

9、設計時候考慮了隊列索引自增漲演算法，但由於tcmalloc分配內存不釋放，後面改為定長的了（有宏控制開關）。

10、所有長度，池大小等參數都可以拿宏修改，可以修改適應大內存等各種情況。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！