新一代實時存儲引擎，如何做到低延時的資料寫入和更新？
背景
AnalyticDB MySQL作為一款實時數倉産品，在傳統數倉的能力基礎上為了支援低延遲的寫入、更新場景，架構上設計了實時存儲引擎；使用者的寫入、更新會以append_only的方式寫入實時存儲引擎，經過compact之後建構索引以支援複雜的計算場景。
從架構上看，很慶幸SAP HANA、SingleStore有着類似的設計。
線上上服務大客戶的同時，實時存儲引擎也遇到了一些設計、性能上的瓶頸。
在一些大寬表場景下，單行的更新帶來了嚴重的寫放大問題實時存儲引擎記憶體高頻換入換出，cache miss高的同時，大量的壓縮、解壓縮帶來cpu瓶頸
針對以上的幾類問題，我們設計了新一代的實時存儲引擎：
- 存儲格式上，在确定的IO機關上設計行列混存格式，使得單行的IO大小可控
- 學習學術界、工業界對Memory-centric架構的研究，在記憶體控制上實作了基于Anti-Caching的BufferPool
存儲格式
AnalyticDB MySQL實時存儲引擎在最初的設計上仍然是一個列存實作，在寬表的更新（遊戲業務中留存率計算、零售業務中訂單統計等）場景下，IO放大導緻的latency問題尤為明顯。
RowGroup作為行列混存的一個典型設計，在列存的基礎上以行數對齊的方式使得一個group内邏輯行号對齊；這樣的設計在寬表場景下出現了比較嚴重的弊端，當通路一行資料時，磁盤的IO機關變得不可控（列數*block_size）。
針對IO的優化，我們在固定大小的Page上以PAX layout組織資料格式，page頭部維護列數、目前記錄數以及空閑大小；其次記錄每個列起始offset和行粒度的bitmap資訊。
每個列會在各個定長minipage中維護（變長的組織在下個小節介紹），同時每個F-minipage的配置設定上保證cacheline對齊。
基于PAX layout的設計，能夠確定每個page的刷盤落到磁盤上都是确定的IO機關；同時同一個列的資料仍然保持在一個minipage上的連續布局，在順序掃描的場景上仍然能夠充分利用cache的能力。
VarlenEntry的設計
針對變長字段的存儲，AnalyticDB MySQL用16-byte來存儲和表示；前4個位元組存儲字元串長度，對于超過12個位元組的字段會記錄4個位元組的prefix之後，記錄指向V-minipage中對應記錄的起始位址。
記憶體控制
在記憶體控制的演進上，AnalyticDB MySQL實時存儲引擎從最初的LRU-based Cache逐漸走向以記憶體為中心的架構。
與傳統資料庫的Caching機制不同，AnalyticDB MySQL基于Anti-Caching的設計，将記憶體作為主存，僅将冷資料淘汰到磁盤上，磁盤的角色更像一個“backup”。學術界對于Anti-Caching的研究也是層出不窮，從H-Store孵化出的商業資料庫VoltDB到微軟的Siberia in Hekaton都提出了各自的解決方案。
Anti-Caching
Caching和Anti-Caching設計上都是為了解決記憶體和磁盤速度和容量上的gap。Caching為了加速資料的通路速度緩存了磁盤資料到記憶體中；Anti-Caching則是為了容量将記憶體資料“anti-cache”到磁盤上。
Anti-Caching的實作上可以分為以下三類：
- User-space 在User-space上實作Anti-Caching目前是比較廣泛的，同時能夠基于應用語義實作Ad-hoc的優化；另一方面從User-space實作Anti-Caching需要繞過OS，帶來了一定的overhead。 最早提出Anti-Caching的H-Store，是面向高性能的行存記憶體資料庫，它去掉了傳統面向磁盤資料庫裡的Lock、Buffer Management這類比較重的元件，同時基于LRU來做冷資料的Anti-Caching。H-Store維護了tuple級别的LRU通路，同時淘汰粒度上為了減少overhead，将tuple聚合到block級别。為了維護tuple的狀态（磁盤還是記憶體）H-Store用了一張記憶體的evict table來存儲這些meta資訊，整體上來看，為了維護LRU對性能不可避免地帶來了一定程度上的overhead。 Siberia項目也在Hekaton中采用了Anti-Caching的技術，與H-Store維護LRU不同的是，Siberia采用離線分析logging的方式來為tuple的冷熱做分類；同時維護了bloom filter來篩選需要通路磁盤的tuple。Siberia的實作在性能上避免了LRU的開銷，但是實時性存在一定欠缺，對于記憶體并不能做到完全精準的控制上界。
- Kernel-space Virtual memory management(VMM)是大部分OS都支援的功能，可以作為Anti-Caching的一種簡單實作手段，但是缺乏了應用層面的語義，Kernel-space的淘汰可能并不能很準确。 大體上有兩種實作OS Paging的方式，一個是提前配置好swap分區，OS自動做Paging的換入換出應用程式不需要感覺。另一種方式是使用memory-mapped檔案，這個在MongoDB、MonetDB中廣泛使用。
- Hybrid of user- and kernel-space User-space的方式能夠使用應用層的語義優化Ad-hoc的性能；Kernel-space能夠針對I/O進行排程同時充分利用硬體特性。AnalyticDB MySQL采用了将user-和kernel-space結合到一起的實作方式。
AnalyticDB MySQL的BufferManager在檔案系統之上，通過mmap維護了一個buffer pool，不同大小的page都可以加載到buffer manager中。當一個page被淘汰出buffer manager時，首先保證該page被寫回磁盤成功，随後通過madvise中的MADV_DONTNEED标記來通知核心立刻重用相關的實體記憶體。
Swizzling Pointer
當page被序列化到磁盤後，系統需要通過邏輯ID (PID)來再次通路對應的page。業界通常的設計是用全局的hashtable來維護PID的映射關系，老版本的AnalyticDB MySQL也不例外。
然而這類設計在資料規模較大時，存在明顯的性能瓶頸；同時早在08年Harizopoulos在SIGMOD發表的paper中就指出TPC-C場景下BufferManager在指令集層面的開銷就占用了34.6%。
為了避免Hash的開銷，AnalyticDB MySQL采用了Swizzling Pointer的實作方案，以64bit來存儲page的唯一辨別；當page在記憶體中時，頭部第一個bit标記為0，其餘bit用來表征page的實體位址；當page在磁盤中時，頭部第一bit标記為1，後6個bit記錄page的size class來計算具體的page大小，剩餘的57個bit記錄page的PID。
Swizzling Pointer技術上本身帶有一定的去中心化屬性，避免了全局Hash的開銷；同時在新版本的實時存儲引擎中，page寫盤沒有采用傳統的lz4、zstd等壓縮算法，使得在cpu密集的場景下，性能有大幅的提升。
實時存儲引擎性能對比
針對點查以及更新場景，我們選擇YCSB測試集來做性能的測試對比。
相比列存版本的實作，新版本的實時引擎存儲格式的優化上對IO的控制有着明顯的優勢；同時記憶體控制的優化上大大減少了Cache Miss帶來的CPU開銷。
AnalyticDB MySQL湖倉版已正式開放公測，對于低成本離線處理ETL有需求，同時又需要使用高性能線上分析支撐BI報表/互動式查詢/APP應用的使用者，歡迎通過此連結進行公測申請：https://survey.aliyun.com/apps/zhiliao/pLg_D88Cj
引用：
[1] OLTP Through the Looking Glass, and What We Found There
[2] Weaving Relations for Cache Performance
[3] In-Memory Performance for Big Data
[4] Cloud-Native Transactions and Analytics in SingleStore
作者：陳希（兮塵）