X-Engine是阿裡雲RDS MySQL 的存儲引擎之一，基于Log-structured Merge Tree (LSM-tree)，較基于 B-tree 一族的其它存儲引擎而言年輕很多，是以在實踐中遇到問題也更多，對研究的需求也更大。
LSM-tree是1996 年美國計算機科學家 Patrick O'Neil 等人提出的一種資料結構，和 B-tree 相比，它擁有更快的寫入性能和階層化的存儲結構，能夠同時利用好 DRAM 記憶體的高性能和持久化存儲的高容量。尤其是 LSM-tree 的分層存儲結構，可以天然地利用資料局部性将熱資料和冷資料差別開，友善壓縮算法有的放矢，有機會在降低整體成本的情況下，實作同樣優秀的性能。但是，與幾乎所有的計算機資料結構和系統設計一樣，有得必有失。LSM-tree 難以避免的在讀性能、I/O 寫放大和空間效率上面對挑戰。
01、寫路徑上的羅生門
首先，LSM-tree 使用了能夠支援快速寫入的 copy-on-write （CoW）方式來存儲新增資料。顧名思義，假如要使用 CoW 來更新一條記錄，不需要定位存儲引擎中該條記錄的位址并将它讀取出來，隻需要直接将我要更新的内容（例如，key = 100, value = value +100）寫入記憶體和日志（直接寫磁盤）即可。
這樣整個寫入操作就像記日記一樣，我隻需要在日記本的最後一個空白頁上新增内容即可，至于這個日記本已經寫了多少頁，或者以前的某頁裡面寫了什麼，我都不需要管。
是以，LSM-tree 的寫入操作代價很低，而且與資料庫中的已存資料關系不大，無論這個資料庫已經存了多少資料，運作了多少天，寫一條記錄在理想狀态下都可以被執行得非常快。同理，如果我需要删除一條記錄，我隻需要新插入一條反記錄即可。
那麼問題來了，讀記錄的時候我難免要去檢查一下這條記錄的原始資料在哪裡，是什麼，它有沒有更新.....然後把所有這樣的碎片合并在一起，我才知道這條記錄到底是什麼（例如，key == 100， value = 0 + 100 + 200 - 300 = 0）。這個過程顯然是比較費時的，不如我直接根據索引讀一條記錄來得快。
而且，絕大部分的資料庫是需要服務大量查詢的，幫使用者查資料才是資料庫的主要工作，使用者存資料就是為了有朝一日要讀取它，而 LSM-tree 卻在寫性能上大做文章，涉嫌揀了芝麻，丢了西瓜，老老實實優化讀操作不香嗎？為什麼非要玩高難度呢？
我們也想輕松啊……可是，各位敬愛的淘寶剁手黨、天貓爸爸會員、釘釘校友們，你們知道你們給資料庫帶來了多大的寫入流量嗎？那可是摧枯拉朽，天崩地裂，滄海桑田！比如雙 11 零點那一秒，阿裡雲資料庫要面對 100 多倍的寫入流量海嘯（詳見我們的 SIGMOD'19 論文），臣妾要是不加班加點，那根本是做不到的……
問題還不止于此。資料庫所有資料最終都要落盤實作持久化。記憶體新寫入的記錄就需要時不時地刷入到磁盤。刷盤時，反正都要做 I/O 寫，我們可以把新資料與舊資料直接合并到位，這樣就減少了碎片的數量，同時保持了磁盤上資料的有序，友善讀取。
可是，當盤上資料越來越多時，這樣的合并會越來越昂貴，在不能按位元組尋址的存儲器件上（注意這個限定詞，NVM 正在熱身，等待上場），我們必須讀入所有需要參與合并的頁，完成合并，并将這些頁寫回。
這些頁裡面的很多資料其實是躺槍的，純粹是被鄰居帶下水。随着資料增多，我們要讀的頁也會越來越多，整體代價也就越來越大。我們稱這個問題為『寫放大』。除了對性能的影響外，寫放大也會給 SSD 盤本身的 endurance 帶來壓力，如果寫放大過高，會提高雲廠商的服務成本。而雲計算的最最最精華的精髓，就是『低成本、幹大事』。
為了解決寫放大問題，LSM-tree 在磁盤上已經進化出了一種分層存儲結構。新資料先寫在『零層』，零層我們給他一個非常小的容量，隻存剛剛刷下來的資料。因為資料局部性的緣故，零層的資料有很大機率會被通路到，還是熱乎的，那麼通過限制容量，無論怎麼通路，點讀也好，掃描也罷，它總共就這麼大點地方，不會慢到哪裡去。
當零層容量飽和時，我們将它的内容與『壹層』中的資料合并。壹層比零層更大，比如大10倍。那麼理論上，這次合并中最多需要讀取和寫回壹層大概十分之一左右的資料，不會更大了。寫放大，也就被限制住了。當『壹層』也滿了的時候，我們使用同樣的方法繼續往下刷，刷出『貳層』、『叁層』等等等等，以此類推。
每一層的容量，比上一層大 10 倍，整個存儲中每層的大小呈指數級增長。有了階層化的存儲，配合這樣的合并操作，寫放大就被控制住了。對于資料庫系統中的很多問題，我們往往不太可能把它徹底解決掉，而是将其控制在一定的可接受的界限内即可。成年人的世界就是這麼殘酷，沒有歲月靜好，沒有美麗童話，隻有負重前行。
分層控制住了寫放大，但是新的問題又來了，合并算法本身是一種資料密集型算法，它需要讀取多路資料，然後進行相對簡單的合并計算，再将合并結果寫回去，整個過程本質上讀寫很多，對存儲帶寬的消耗非常大，也會給 CPU 流水線帶來很多的 I/O 等待、記憶體等待等氣泡，降低 CPU 流水線的執行效率，拖慢整個系統。
單次跑一下還好，如果頻繁跑，會對系統性能有很大影響。而且它即不處理查詢，也不處理新增資料，完全是個看起來不必要的背景操作。這種合并操作，我們叫他『Compaction』。在 LSM-tree 引擎中，compaction 不僅肩負着層與層之間合并資料的任務，還肩負着為了删除操作将反記錄與真實記錄合并進而實作删除的任務等等，是一種多功能的重要操作，是 LSM-tree 中的『消防隊員』兼『警察叔叔』兼『快遞小哥』兼『醫生』兼……
到此為止，LSM-tree 在寫路徑上的各個部分都已經悉數登場了，而這片江湖上的恩恩怨怨才剛剛開始。為了服務好寫流量越來越多的 workload，LSM-tree 為了加速寫可謂是不遺餘力，基本上所有的設計都向寫路徑的性能做了傾斜，讓寫入看上去十分美好，實際上也開了一扇羅生門，門後慘象環生。具體怎麼慘，下文詳述。
02、讀路徑上帶着鐐铐的舞蹈
LSM-tree讀路徑，從出生就帶着鐐铐。因為 CoW 的使用，讀一條記錄實際上需要把這條記錄所有的增量碎片都找到。橫跨記憶體和磁盤兩種媒體和有階層化的存儲，讓碎片可能藏在各種犄角旮旯裡面。更慘的是，如果是讀一個範圍内的記錄，俗稱 range scan，因為 LSM-tree 的每一層的 key range 是交疊的，那麼一個 range 内的資料就很有可能會落在所有的層次上，為了把他們都找到，我們就需要每層都去讀，這個工作量也不小。
為了解決這個問題，目前的 LSM-tree 引擎把各種經典技術都用上了：各種索引、各種 cache。但是為了提高索引和 cache 的效率，讓他們一直發揮比較好的作用，難度不小。以 cache 為例，X-Engine 中使用了兩種經典的 cache，一種是 row cache，緩存記錄級别的熱資料，一種是 block cache，緩存資料塊級别的熱資料。
Row cache 可以加速點查詢，block cache 可以加速 range scan，一切看上去都是很完美的芭蕾舞。然而，當 compaction 被大王叫來巡山的時候，危險就發生了。因為 compaction 會重新組織資料塊裡面的内容，幹掉一些老的 block，生成一些新的 block，傳統的 cache 替換政策對老的 block 做的通路統計會失效，而新的 block 它不認識，沒統計資訊。此外，compaction 還會移動資料。這兩點加起來，隻要 compaction 巡了一次山，cache 裡面緩存的記錄就有很大可能出現大面積失效，導緻原本可以命中 cache 的查詢，不得不去通路磁盤，造成嚴重的延遲尖刺。
熱資料的麻煩還不僅僅來源于 cache，因為熱資料經常會被大量更新，而 X-Engine 為了實作一個 OLTP 資料庫的 ACID 特性，使用了 MVCC 的并發控制方法，會為一條熱資料上存上非常多的版本，這樣的設計實際上造成了一條邏輯記錄可能會有特别多的實體分身。這個現實無論是對承接新寫入資料的 memtable（經常被實作為跳躍連結清單），還是索引，還是 compaction，都是一個很煩人的刺頭，硬生生地通過放大資料的體量來造成各種各樣的問題。
除了上述由于 LSM-tree 或者資料庫的機制帶來的問題以外，這些涉及到的資料結構本身的設計和實作也有很大的挑戰，比如 cache 的分桶政策、鎖的管理、跳躍連結清單和索引的查詢效率、資料結構針對多核處理器的并行優化等等等等，都是風景秀麗的坑、大坑、天坑。坑夠大，填坑才有樂趣。除了讀路徑的問題，LSM-tree 上還有删除效率的問題、空間效率的問題等等，此處不再詳述，詳見相關論文。
03、學術成果與産學研互動
X-Engine 團隊聯合其他合作夥伴，為了解決上述問題做出了很多優化，申請了大量專利，其中的很多技術也作為學術成果在資料庫和存儲領域的頂會内完成了發表。
X-Engine團隊合作夥伴們
2019年，我們在 ACM SIGMOD 的 industrial track 中發表了一篇介紹 X-Engine 來龍去脈的論文X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing。在這篇文章中，我們介紹了 X-Engine 這種面向寫入優化的存儲引擎為什麼在工業界人氣飙升，為什麼阿裡巴巴的電商場景需要這樣的引擎，主要原因就是每次電商促銷所帶來的富含新增資料的高流量海嘯。
面對這樣的挑戰，我們首先将問題拆解為了具體的資料庫技術問題，如處理高流量所需的并行寫入流水線、資料量海嘯快速填滿記憶體對刷盤帶來的壓力、促銷導緻的資料熱點範圍頻繁變化帶來的讀性能的挑戰等等。為了解決這些實際的技術問題，我們介紹了 X-Engine 做了怎麼樣的技術選型，采取了哪些優化，以及每項優化所帶來的實際效果。這篇論文是中國大陸公司首次在 SIGMOD 上發表資料庫核心上的工作。詳情請見論文（在 ACM DL 中可免費下載下傳）。
2020年，與 AIS 軟硬體結合開發團隊合作，我們在存儲領域的頂會 USENIX FAST 2020 上發表了利用 FPGA 異構計算技術來加速 X-Engine 中很多問題的罪魁禍首—— compaction 的工作FPGA-Accelerated Compactions for LSM-based Key-Value Store。
在這項工作中，我們首先系統研究了 compaction 對 LSM-tree 存儲引擎在 CPU、記憶體、磁盤等資源的消耗上有什麼特征，分析了 compaction 的算法，發現 compaction 算法在合并較短的記錄的時候竟然是受限于 CPU 的。
其原因一方面是因為 compaction 對計算的需求，另一方面也是因為這些年來磁盤帶寬有了顯著的增長。是以，我們提出将 compaction 算法 offload 到 FPGA 加速卡上，并在 FPGA 上設計和實作了一套高效的流水線，和 CPU host 實作了快速的互動，也實作了 compaction 算法的加速。這項工作所做的探索讓我們看到了計算型存儲技術的紅利。
近年來，随着 SSD 的不斷發展和處理器的微小型化，市場上出現了類似 SmartSSD 這樣的計算型儲存設備，其核心優勢是把較小的 ARM CPU 處理器或者 FPGA 晶片直接嵌入 SSD 内部，讓部分計算任務不需要離開 SSD 就能完成，省去了 I/O 和 CPU 的開銷。因為 SSD 内部的訪存帶寬比外部的 I/O 快幾十倍，計算型存儲特别适合處理類似 compaction、scan 等相對而言更加訪存密集的操作。
今年阿裡雲資料庫團隊在 FAST 上收獲了大豐收，投稿的 3 篇論文全部被錄用，而 FAST 是個比較小而專的會議，今年一共也僅有 23 篇論文。
FAST'20現場，X-Engine分享
除了上述已經發表的成果，我們還探索了使用機器學習技術來預測 compaction 前後的資料通路趨勢，以解決傳統 cache 替換政策被幹擾的問題；我們也探索了在 X-Engine 内部應用細粒度、自适應的排程算法，來改善 compaction 的執行時機，進而提高系統性能的穩定性；我們也優化了記憶體配置設定政策、cache 結構和通路方式等等底層細節，旨在從根本上顯著提高 X-Engine 的性能與穩定性。目前，這些工作還在進一步的研發中。
X-Engine 自 2019 年進入資料庫界國際頂級學術圈以來，通過向學術界介紹阿裡巴巴的應用場景以及技術挑戰，尤其是 X-Engine 引擎本身所面對的技術挑戰，已經吸引了很多專家學者的目光。我們所抛出的 LSM-tree 删除性能差的問題，已經吸引了來自波士頓大學和哈佛大學的研究者提出了新的優化技術，相應學術成果将發表在最近的學術會議中。
在國内，X-Engine 團隊與阿裡自家的達摩院資料庫存儲與實驗室、浙江大學 AZFT 實驗室孫建伶教授、中科院計算所陳世敏教授等學者和研究人員長期合作，共同研究 LSM-tree 相關的技術問題，并且不斷産出優質的學術成果。通過學術合作，目前已經發表了 FAST 一篇（FPGA 加速），VLDB 一篇（NVM 索引）。除此以外，我們追求将學術研究探索出來的新技術真正落地在 X-Engine 系統核心中，為提高 X-Engine 産品力貢獻力量。
04、未來研究方向
未來，X-Engine 團隊會針對生産實踐中遇到的各項技術難題展開公關，也會緊跟新的技術趨勢，探索新型硬體（如 NVM，FPGA 等）在 X-Engine 上的應用。
首先，分布式是資料庫産品的潮流。在未來，使用者不需要再操心資料庫擴充性上的麻煩，而是買一份分布式資料庫 PolarDB-X，把所有任務都交給它後就可以高枕無憂了。我們目前正緻力于 PolarDB-X 的研發，旨在為使用者提供一款高性能、低成本、伸縮性好的分布式資料庫産品，将阿裡多年來積累的資料庫技術紅利分享給阿裡雲上的客戶們。在這個方向上，我們會着力于分布式SQL引擎、私有協定、分布式事務處理、分布式負載均衡、故障恢複等重要技術問題。
其次，我們認為，X-Engine 的記憶體部分可以看成一個記憶體資料庫，應該與處理器、DRAM 記憶體等硬體深度融合，突破性能瓶頸。具體的研究方向包括 cache-conscious 的高性能記憶體索引、利用 SIMD 技術（Single Instruction Multiple Data）來加速記憶體資料結構通路、降低記憶體鎖開銷等。
最後，對于時下的熱點人工智能，我們也不會放過。目前，我們已經探索了機器學習技術在 cache 替換上的應用，未來我們會探索智能調參、智能 compaction 排程、智能索引等 AI for DB 技術。我們希望利用人工智能技術，将複雜的資料庫運維轉換為十分傻瓜的簡單操作，降低使用者使用和維護資料庫的難度，同時改善資料庫的性能。
作為一款重量級的資料庫基礎軟體，X-Engine 雖然看上去隻是負責資料增、删、改、查這樣平淡無奇的操作，但正是因為這些操作足夠基礎，X-Engine 才會被內建于 MySQL 核心和分布式資料庫 PolarDB-X 中，我們的每一項優化也獲得了更大的影響力，直接決定着所有上層應用的安全、穩定和性能。歡迎有志于從事國産自研資料庫研發的同學加入我們。
阿裡雲分布式資料庫PolarDB-X團隊招人啦！
面向人群：2021 屆海内外院校應屆畢業生（畢業時間為 2020 年 11 月 - 2021 年 10 月）
應聘方式：請将履歷投遞至[email protected]