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]
