429
流著碼農的血，為突破理論極限值而生 | 阿裏中間件性能挑戰賽內部賽全記錄
近日，第三屆阿裏中間件性能挑戰賽內部總決賽在西溪園區舉行，經過前期線上比賽和現場解題思路答辯，來自阿裏雲數據庫技術團隊的資深專家曹偉（鳴嵩）獲得本次比賽總冠軍並攬得大獎。
線上比賽階段得分屢創新高，現場解題思路答辯交流活躍，氣氛熱烈，精彩紛呈的內部賽為今年的中間件性能挑戰賽開了一個好頭，期待在接下來的外部賽上湧現出更多好成績和令人耳目一新的工程創新。
作為阿裏中間件（Aliware）舉辦的曆史最悠久的工程視角賽事，自舉辦以來，受到業界工程師和高校技術愛好者的一貫支持和好評。2014年中間件性能挑戰賽作為初創賽事，主要麵向集團內部；2015和2016年又連續舉辦了兩屆，麵向群體擴充到高校學生和社會參賽選手。今年單獨設置了內部賽，單獨出題和比賽，並最終和外部賽的同學在總決賽前的極客挑戰賽上一決高低。據悉本次內部賽報名參賽的規模創曆年新高。
真實場景再現，賽題貼近實戰接地氣
本次挑戰賽的主題為“挑戰雙十一萬億級消息引擎”，比賽場景當然離不開大家最熟悉的阿裏雙11，海量業務場景下的技術需求模擬，賽題本身具有非常強的實戰意義。本次內部賽題目主要解決的是NewSQL領域中使用最頻繁的一個場景--分頁排序，其對應的SQL執行為order by id limit k,n。
主要的技術挑戰為"分布式"的策略，賽題中使用多個文件模擬多個數據分片。簡單來說，就是通過10個文件模擬了數據的分片，每個分片1GB的數據大小，給定的機器配置是24核，JVM堆內存限製2.5G，磁盤讀寫為490-500MB/s左右。在這樣給定資源限製的情況下，如何快速建索引支持分頁查詢top(k,n)場景。
看似一個簡單的問題，但要取得好成績則需要多方麵的綜合實力，首先選手要了解硬件，需要考慮IO和內存優化，畢竟10GB文件順序讀取理論值可能就在20秒左右，內存上的一些約束也促使選手需要考慮更好的數據壓縮。
同時選手也需要在數據結構和算法上有一個比較好的設計思路，構建類似的索引信息來滿足多次的top(k,n)的查詢。綜合來看，需要選手具有比較強的係統優化和算法設計能力，另外賽題基本是參考了NewSQL領域的一個真實業務場景，整個比賽的優化思路也對真實業務有一定的借鑒性。
時隔兩年衛冕，阿裏老司機有話說
本次大賽冠軍獲得者鳴嵩同學，在阿裏內部也是一位技術大神，他的座右銘就是Linux創始人Linus Torvalds在郵件列表裏說過的那句名言：“Talk is cheap. Show me the code. ”，在公司內部各種安全、算法、文件係統方麵的比賽總是名列前茅。
說來也巧，鳴嵩同學還是第一屆中間件性能挑戰賽的冠軍獲得者，這次奪冠是時隔兩年後的衛冕。作為一名中間件性能挑戰賽的老司機，鳴嵩同學表示和評委都很熟，但比賽成績還是靠實力說話！
鳴嵩同學計算機體係架構方麵科班出身，但畢業後就直接投身軟件行業，先是從事搜索技術研發，2001年加入阿裏做數據庫研發和支持工作，長期在一線解決出現的各種工程問題和BUG，累計了大量的實戰經驗。正是這樣的學習和工作經曆，鍛煉了他的技術功底和綜合的實力，在麵對上述的問題，能夠拿出更好更加全麵考慮的解決方案。下麵是他的解題思路分享。
成績綜述：
先說一下成績：最終線上跑分的成績在22.9s，去掉評測方法引入的1.1s，5次查詢含建索引總時間21.8s，因為讀10GB文件就需要21.5s時間，所以這個成績還是很接近底線的，跑到這個分數需要綜合利用java GC、操作係統的page cache和髒頁回寫機製、ext4文件係統原理、以及SSD的一些知識，整體來理解和分析係統瓶頸在哪裏、對係統建立模型、並找到規避的方法。
算法設計：
問題本身用很多種數據結構都可以實現，搞數據庫和搞ACM的同學對這道題的第一反應是不一樣的。我之前做過五年的搜索引擎，分布式和本地的索引框架都寫過，所以第一反應是借鑒Lucene的方法，skip list + sequence file。
具體算法是這樣：原始文件切割成小分片，喂給24個worker；每個worker讀數據，處理數據，定期批量寫索引出去；最後查詢會去讀每個worker生成的所有索引文件，通過跳表快速seek。
本地索引的格式如下：每個分片的隨機數通過Array.sort排序成一個有序數組，直接寫入一個順序文件裏，采用delta encoding和變長整數方法壓縮，long型隨機數可以從8字節壓到6字節。為了提高查詢效率，還加了一個skip list支持索引文件裏隨機seek。
IO上的優化：
這套算法實現完後，第一次跑花了30s時間，主要原因是一旦開始寫盤時，SSD的讀能力就下降的很厲害，我就開始想方法去壓製寫盤。首先是要搞清楚為什麼會寫盤，這台機器的內存應該是蠻大的，我們阿裏的內核一般配置的髒頁回寫超時時間是30s，理論上page cache能buffer住所有的髒頁，那為什麼程序運行過程中還會寫盤呢？
最後找到原因了，和ext4文件係統的掛載參數有關，從ext3開始起，文件係統開始支持日誌（journal），文件的inode被修改後，需要刷到journal裏，這樣係統crash了文件係統能恢複過來，阿裏內核配置默認5s刷一次journal，ext4還有一個配置項叫掛載方式，有ordered和writeback兩個選項，區別是ordered在把inode刷到journal裏之前，會把inode的所有髒頁先回寫到磁盤裏。不錯，我們的評測機器就是配的ordered，這樣髒頁寫入page cache，5s後就被回寫到SSD裏，從而影響了SSD讀性能。
在搞清楚IO機製後，問題就簡化為如何利用這個機製規避寫盤。一個簡單的方法就是控製程序流程，倒數5s才開始寫文件。
結果耗時分析：
程序啟動後開始預讀，把10GB數據加載到page cache裏，從12.2s開始起處理數據，要寫文件的中間結果先緩存在jvm堆內存裏，直到17.0s才開始第一次寫文件，這樣21.8s程序結束的時候，操作係統還沒有真正開始寫SSD過程，這樣讀盤性能就不會受到幹擾。
總結：
可以看到，用page cache來做IO還是蠻不靠譜的，所以在開發重IO的服務器，比如數據庫時，我們一般都不依賴於page cache，更多使用DIO來寫文件，自己管理buffer，java裏可以多看看堆外內存。IO發起也建議用AIO來代替堵塞IO模型，甚至我們現在在操作NVMe盤時都旁路掉Linux kernel，直接使用用戶態驅動和用戶態文件係統。
應用服務器的文件係統掛載選項可以考慮換成writeback，小文件讀訪問比較多的話，加上noatime，對提升IO性能是有好處的。
通過內部賽冠軍鳴嵩同學的解題思路和經曆的分享，期待能夠給更多的同學和參數選手帶來思想上的突破，在接下來的比賽中取得更好的成績！
對於這次時隔兩年後的衛冕，鳴嵩同學表示有點小確幸。他認為參加每一次編程比賽都是一場馬拉鬆，跑到終點除了好的idea之外最需要的是毅力。比賽過程中最有意思的事情是，你會看到事先被預測出的一個個“理論極限值”，先是被逼近，然後被突破，最後被踏平，選手們的技術手段整體上在不斷提高，這也體現著競技的精神：“更高、更快、更強”。在獲獎感言環節，他還總結了以下三方麵的感悟：
1、 從工程師角度，這種比賽的精髓就是以成為傑出工程師的標準來要求自己，不斷突破大家和自己認為不可能的數字（理論極限）；通過比賽可以看到眾多熱血的技術新人，清晰地看到人才梯隊越來越壯大；
2、 從比賽角度出發，作為一個軟件工程師，能夠從係統底層，比如操作係統、編譯器、JVM、分布式係統和文件係統等方麵來綜合考慮，最終給出一個解決方案，是本次比賽獲勝的關鍵，希望業務和應用開發的工程師們能夠在這方麵多涉獵一些，這些才能在工程師的道路上走得更好更遠；
3、 從賽事角度出發，阿裏中間件（Aliware）作為阿裏技術的“科普”名片，傳遞給集團其他BU的工程師和外部同行，阿裏巴巴作為技術公司，一直以來都在踐行技術驅動商業的模式，讓更多的技術人在我們的技術平台上迸發他們的創意和想法，改變現在塑造未來。
技術大牛寄語，期待更好的你
為了更好地促進現場交流，阿裏中間件技術部負責人蔣江偉（小邪）、業務平台事業部負責人牆輝（玄難）和數據技術及產品部總監朋新宇（小芃）作為評委嘉賓到場，和現場同學共赴代碼和算法的盛宴，體驗性能優化的極致挑戰之路。在獲獎同學分享解題思路和心得經驗的間歇，各位嘉賓也發表了對選手分享內容的點評和對大賽的期待：
小邪：“首先，我被這樣的氣氛和熱情所感染，大家經常說，生活不僅是眼前的苟且（工作），還有詩和遠方，今天晚上這樣的比賽就是我們工程師的很容易看到的詩和遠方。在工作之餘放鬆自己，追求極致自我。
我每次來到決賽現場，還有一個特別切身的感受就是---突破和驚喜，可以看到和學到其他人是如何來寫程序，如何來優化程序，如何來突破各種不可能的。從我經曆的這幾屆來說，每次同學們的比賽成績都能突破我們組委會所預料成績的理論值，看到我們同學的各種奇思妙想。不瞞大家說，我和多隆同學（阿裏傳奇程序員，阿裏巴巴合夥人）都曾經參加過類似的比賽，但都沒有進入前十名，所以同學們的表現還是非常棒的！”
小芃：“第一次參加這樣的活動，聽的我熱血沸騰。不難看出，現場的各位同學和我一樣，身上都流著碼農的血，在最近的各種會海中，這是我感覺最酣暢淋漓的幾小時。外麵很多人在關注我們是一家什麼樣的技術公司，我們阿裏內部的技術人，是如何使用這些技術的？在使用和實踐過程中是否不斷反哺來提升這些技術？這些都值得我們去考慮。
另外，作為一家大數據公司，難得有這樣的比賽，公司內部開放這麼好的數據給大家，讓大家在最真實的環境中來驗證自己的算法和技術方案，我覺得這是一個非常難得的機會。所以對於本次大賽來說，比賽名次並不是最重要的，真正的那種想贏和極客的精神才應該是我們所珍視的。”
玄難：“首先這個比賽非常好玩，我去年就參加過，但是很不幸成績墊底。今天來參加這個現場總決賽，看到各位獲獎同學來分享他們的解題思路，看到非常多有意思和有價值的技術思考；另外，基礎中間件性能的突破，對我們整體的技術體係幫助非常大，看到大家今天玩的這麼好，並且能找到接下來技術工作的突破點，我覺的還是非常不錯的。”
阿裏中間件（Aliware）作為國內頂級的中間件技術團隊，一直在致力於推動中間件行業和生態的發展，舉辦中間件性能挑戰賽是具體措施之一。期望這樣的技術工程類賽事和所有競技賽事一樣，追求“更高、更快、更強”；通過比賽實戰，讓大家感受到技術工匠精神的真實存在，激勵參賽選手在各自技術領域不斷精益求精，大膽突破以前的不可能，整體提升中間件行業的理論和工程實踐水平；不過還有最重要的一點，通過比賽讓大家玩的開心：）
欲了解本次大賽的詳情及賽事最新動態，可訪問官方網站：https://tianchi.aliyun.com/
最後更新：2017-05-11 11:01:02