背景
雖然同為LSM-tree架構，X-Engine的設計哲學與傳統基於LSM-tree架構的Rocksdb等引擎並不完全一致，如下圖所示：
設計關鍵點1：X-Engine磁盤上的數據，在常態下只有兩層（L1/L2），L0層是MemTable在compaction來不及的情況下暫存到磁盤上緩解內存壓力時才啟用的，正常情況下被凍結的MemTable可以直接和磁盤上的L1合併。
設計關鍵點2：在L1/L2之間的compaction合併過程中，X-Engine的冷熱合並算法傾向於將熱點數據保留在L1層(基於訪問頻度），將訪問較少的數據下刷到L2層並進行壓縮存儲。這是一個對數據在物理上進行冷熱分離的過程， 其結果是L1存儲的都是熱點數據，L2存儲的都是冷數據。對L1進行緩存時會有更高的內存利用率。
按照設計初衷，X-Engine正常運行時，Memtable中緩存了最近寫入還未刷盤的數據，L1中保存了磁盤訪問頻度最高的數據，也大部分被內存緩存，分層之後X-Engine的讀性能優化被分解為兩個獨立子問題：
- 內存MemTable部分和L1層數據讀操作是CPU bound的，手段主要是優化CPU指令的執行效率和訪問主存的速度。
- L2層的讀性能依賴於磁盤的隨機讀能力，對此部分的優化手段是更精準的冷熱識別，其目標是最大化IOPS利用率。
考慮到Memtable部分數據量較少，在冷熱識別算法精準並且內存足夠緩存熱點數據的前提下，X-Engine的性能整體上取決於對L1部分數據的內存查找效率，這也是今天這篇文章探討的主題: 如何最大化命中內存時的讀取性能。
讀取路徑存在的問題
在數據集小於可用內存時，X-Engine的讀性能受限於CPU資源。分析一個CPU bound程序的性能問題時，我們需要看CPU在哪些地方繁忙。按照CPU使用率的定義，CPU在執行指令時或者在等待數據時(stall) 都會處於busy狀態，存儲引擎的讀性能優化最後都會落到兩個點上：
- 提升CPU Cache命中率，主要靠執行線程在時間上和空間上訪存的局部性。
- 提升CPU指令的執行效率，這一方面需要精簡實現代碼，減少不必要的執行路徑，另一方面需要減少不同線程之間的狀態同步，保證指令流水線順暢執行。
L1層數據組織和讀取過程：X-Engine將數據劃分成2MB大小的Extent，Extent內部會記錄編碼成16KB的Block，每個Extent內部包含一個IndexBlock以輔助定位DataBlock。整體看X-Engine中L1/L2層的數據組織是一個類似B+樹的索引結構。如果所有操作都能命中內存，在Extent中讀取一條key=X的記錄，操作會按如下四個步驟執行：
- ExtentMeta數組是這棵B+樹的根節點，在其中二分查找定位出X所屬的Extent.
- Extent可以理解為一棵子樹，首先需要通過一次Hash查找（查詢緩存）獲取到該Extent的IndexBlock。
- 從IndexBlock中定位出X所屬的DataBlock的Key， 並通過一次Hash查找定位到X所屬的DataBlock。
- 在內存中的DataBlock中查找到該記錄的實際內容，並返回對應的Value.
結合上述讀路徑的實現邏輯，同時對X-Engine全內存命中讀過程進行Perf分析之後。我們在如下三個方面進行改進嘗試（1）數據頁的編碼及查找指令優化 (2) 降低BufferPool的管理開銷（3）優化多核上的多線程運行的Cache沖刷問題，最終獲得了整體124%的讀性能提升。
接下來我們將詳述這三個問題的根源以及我們的優化方法，最後通過實驗對每一步優化手段的收益進行了評估。考慮到這三個問題在數據庫存儲引擎中的普遍性，這些優化方法對於InnoDB, Rocksdb等引擎也是適用的。
Block編碼及SIMD
數據頁編碼及其問題
與Rockdb/InnoDB數據頁格式類似，X-Engine索引頁和數據頁具有相同的格式。每個Block順序存儲KV pairs，並對key進行分段前綴壓縮（每個段稱為restart interval），KV pairs之後有一個restart array，存儲每個restart interval在Block中的offset。搜索時首先會在restart array中進行二分查找，定位到可能包含target key的最小的restart interval（下圖1、2、3、4），再從這個restart interval開始順序比較（下圖5），如下圖所示：
查找過程本質上就是指針數組中的二分查找，restart array中存儲的restart interval的offset可以理解為指向restart interval的指針，perf分析顯示，該過程存在如下兩點問題：
1.內存訪問在前面的KVs和restart array之間跳躍。restart array中僅存儲restart interval的offset，在查找時需要根據offset訪問BlockContent的相應位置獲得key，這樣跳躍的內存訪問沒有規律（每次restart array和實際key的距離隨機）且間隔多個cache line，無法充分利用CPU cache，帶來一定的訪存開銷。
2.前後兩次比較無法利用CPU cache。除了最後一次比較之外，每次比較的index key和前一次比較的index key間隔都可能超過一個cache line，因此無法利用前一次的CPU cache，導致訪存開銷很大。
Cache友好的Block編碼
針對指針數組中二分查找CPU cache不友好的問題，嘗試將頻繁訪問的數據頁轉換成CPU cache友好的兩層B+樹結構，將訪問時序上前後相鄰的記錄在物理空間上聚簇在一起，其邏輯存儲形式如下：
物理存儲形式如下：
構建時按物理存儲形式順序構建每個node，查找時使用類似B+樹的查找方式。CPU cache友好的兩層B+樹從三個角度提升CPU cache利用效率：
- 使內存組織的空間局部性和訪問順序的時間局部性一致。使用B+樹作為索引結構，直接在B+樹中存儲kv的內容，並在節點內採用順序查找。B+樹中訪問順序相鄰的節點存儲在同一個node中，kv內容直接存儲在node中避免了訪存地址跳躍的問題，順序查找進一步保證了時間局部性和空間局部性的一致，並且訪問順序和prefetch的順序一致，儘可能地保證了prefetch在恰當的時機進行。計算開銷方面，B+樹查找算法的時間複雜度和二分查找相同，因為node內key的數量較少，順序查找和二分查找計算開銷接近。
- 提升cache size與數據量的比值：壓縮存儲元信息。例如使用2Byte存儲offset而不是存儲leaf node的指針。
- 選擇合適的B+樹層數：B+樹層數為2，fanout為N開根號。每層節點至少會產生一次cache miss，過多的層數會帶來更多的cache miss，而1層的B+樹node過大，計算開銷和CPU cache效率實際上和restart array差不多，當層數為2時，CPU cache對in-flight的load請求和prefetch的支持可以讓每層node訪問僅產生1-2次cache miss，是CPU cache效率最佳的選擇。
這種編碼格式對range查詢也能完好的支持，對range查詢的第一次seek操作，能起到和點查類似的加速效果，而對於後續的scan迭代，也無負面影響。此部分優化更詳細的新可以參見公眾號前一篇文章：數據庫存儲引擎如何利用好CPU緩存
SIMD指令加速長Key比較
解決了數據頁中記錄查找的cache訪問問題之後，繼續往下perf分析，會發現查找路徑中的compare比較函數消耗了較多的CPU cycle數，在查找長key場景時，計算開銷的問題會更加明顯。考慮到我們新的數據頁編碼結構中，每次讀取會將多個需要先後比較的index key同時load進CPU cache， 引入SIMD指令集可以實現在一個CPU cycle內並行檢索完在cache中的多個index key。
為了使用SIMD指令集，我們需要對X-Engine的數據頁編碼繼續進行調整，如下圖所示：
對key進行lossy compression：由於SIMD寄存器的處理單位segment最長為64bit（AVX-512指令集），簡單地分段並行比較長key會因為額外邏輯抹去並行計算帶來的性能提升。因此這裡將key拆分為common prefix+significant Nbits+suffix，避免了分段並行比較在prefix上的多餘操作，而significant Nbits（N取決於SIMD寄存器的segment大小）邏輯上具有很高的區分度，在大多數情況下都僅需要一次SIMD比較就能得到結果，如果出現相等的情況，也只需要順序比較一部分的index key的suffix。
選擇固定的fanout並使用padding補齊：SIMD指令的處理帶寬（即SIMD寄存器中segment的數量）均為2的指數，如果fanout仍然是N開根號，prepare過程會增加很多額外的操作。同時考慮對CPU cache友好的node長度和對SIMD指令處理帶寬的適配，以及DataBlock中restart key的數量的範圍，leaf node的fanout固定為8，root node的fanout固定為16，實際key的數量不足node的fanout，則用node中最大的key padding補齊，這樣可以直接在代碼中將SIMD指令寫死，減少分支預測開銷。
對索引頁和數據頁進行重新編碼再配合SIMD指令加速，在不同行長下測試最大能提升20%左右的點查性能。在TP系統中，單個請求讀寫的數據量非常少，在我們的測試場景一次只操作一條記錄，因此數據頁編碼和SIMD指令優化一起對端到端的性能提升達到20%，已經非常可觀.
BP的代價及PointSwizzling
BufferPool管理成本
面向全內存的數據庫和麵向磁盤的數據庫具有不同的設計原則。一個典型的差異是：當訪問一個數據頁時，全內存數據庫傾向於使用指針直接訪問，而面向磁盤的數據庫一般則通過PageID在一個數據結構中間接地獲得該數據頁的內存地址（當該數據頁沒有被緩存時需要先讀盤）， 然後才能訪問到該數據頁。這樣的間接訪問會帶來額外的查找開銷，已有研究顯示在數據集能夠完全裝載進內存時，BufferPool管理結構會消耗超過30%的CPU資源。
由於OS的虛擬內存地址空間相對於DB的數據集大小來講是足夠的，一個可能的解決辦法是對面向磁盤的數據庫引擎也使用指針直接訪問，當內存空間不足時，則依靠OS的Swap機制來進行內存頁的汰換，這樣在數據集小於可用內存時，由於消除了PageID映射查找的開銷，存儲引擎會具有與In-Memory數據庫一樣的性能。
但這種方法有一個缺陷，在數據集大於系統可用物理內存時，由於OS的的Swap機制不能準確的感知DB中的數據訪問特徵，它有可能將一個非常關鍵的內存對象Swap到到磁盤上，導致性能波動。
X-Engine是一個通用存儲引擎，其裝載的數據集大部分時候都超出了可用內存的大小，因此也必須引入一個BufferPool來管理對數據頁的訪問。但是在我們的設計中，冷熱分離精準且用戶負載存在明顯的局部性特徵時，大部分訪問都是命中內存的，這個時候BP的30%的CPU資源消耗顯得非常浪費，需要找到辦法消除。
X-Engine中的Extent信息/索引頁/數據頁都是通過BufferPool的Cache管理。其中的Cache使用哈希表和雙向鏈表管理數據，通過哈希查找獲取數據，命中後還要維護LRU鏈表的順序信息。開銷主要來源於三個方面：
- 哈希查找算法本身的計算開銷：包括計算hash值和在hashtable中的某個slot進行鏈表的順序查找，鏈表的順序查找具有CPU cache不友好的問題。
- 維護LRU信息的計算開銷：命中後需要調整entry在雙向鏈表中的位置，還可能需要維護old pool和high priority pool的指針。
- 鎖競爭的開銷：Cache除了用於查找之外，還需要Insert和Evict，因此查找和維護LRU信息時需要對分片加鎖，當併發度很高、訪問流量很大時，鎖的競爭非常激烈。
PointSwizzling
優化BufferPool的間接引用導致的CPU資源開銷有一個方法，叫做PointSwizzling，即使用直接指針代替使用PageID+HashMap查找的方法，針對X-Engine中Cache中哈希查找計算開銷大的問題，我們引入直連指針進行數據訪問，Cache僅用於數據管理，具體方案如下：
目標索引頁/數據頁/ExtentMeta在第一次裝載進內存之後，我們增加一個直連指針指向目標對象(PointSwizzling), 這樣可在下一次訪問使用直連指針，而不必通過一次HashMap的計算。
目標內存對象併發訪問和回收：多線程訪問時，可能出現一個線程正在使用一個內存對象，而另一個線程觸發了Cache淘汰，需要淘汰這個內存對象並回收這個內存對象的空間。這個問題有兩種解決方案：基於Epoch的內存回收或者基於引用計數的內存回收，我們對兩種方案都進行了測試，結論是基於Epoch的方式優於基於引用計數的方式（基於Epoch的具體實現見附錄)。原因是引用計數雖然是一個原子變量，但是多核環境下計數器的高頻更新和讀取依然存在因cache一致性導致的cache失效問題，導致性能不佳。
通過PointSwzzling，X-Engine在內存部分的數據訪問形態就和全內存數據庫一樣具有非常高的CPU使用效率。而當存在數據汰換時，可以繼續使用BufferPool保持內存數據的命中率。PointSwizzling引入之後，X-Engine在KV接口上全內存命中場景的點查性能提升了近60%。
多核CPU上的Cache訪問
數據頁編碼以及PointSwizzling都是著眼於單線程運行過程中的優化方法，其中數據頁的新編碼提升了CPU 的Cache命中率，而SIMD和PointSwizzling都是提升了CPU指令的執行效率，即提升了程序的IPC。
分析X-Engine的整體執行框架，我們發現另一個導致CPU Cache利用率低問題：
多線程併發問題
X-Engine作為RDS MySQL以及PolarDB MySQL中的一個存儲引擎，其執行框架與MySQL類似，使用One-thread-per-client或者採用線程池模式。特點就是任何線程均可以訪問所有表中的數據，在現今動輒32/64/128core的服務器上，執行線程的高度併發導致如下一些問題：
- CPU cache的低效率。例如在128core的服務器上，我們併發訪問1000張表，則同一內存數據會同時在多個CPU core的L1/L2 cache中被加載，導致cache利用率較低。同時如果存在更新，在多核上的cache一致性也會帶來較大的開銷。線程在不同的core上調度發生context switch，同樣會造成CPU cache頻繁大量的失效。
- 線程同步的開銷較大。內存數據都是共享的，訪問和修改（例如上面提到的Cache查找、插入和淘汰）需要鎖的保護，鎖競爭的開銷很大。對於使用原子操作進行的線程同步，原子變量在多個CPU core的L1/L2中同步狀態需要進行數據傳輸和跨核通信，開銷也很大。
針對此類問題，業界先驅如H-Store,VoltDB給出了一條可供參考的優化方法
多核Shared-nothing架構
我們對X-Engine的執行框架做如下改造：
限制讀數據的執行線程數為可用CPU core數目，並進行綁core處理，特定線程只能在特定的core上執行，避免頻繁的線程調度。
對X-Engine中的所有Subtable進行分表，特定的分表只能在被特定Core上執行的線程所訪問到，避免Cache中出現同一數據的多個副本以及同一數據在不同core的cache間傳輸。
這樣Per-core-level Shared-nothing的架構有如下優勢：
CPU cache效率高：同一份數據只可能緩存在一個CPU core的L1/L2 cache中，也避免了實現cache一致性的開銷。線程不會發生context switch而導致Cache失效。
大大減少線程同步的開銷：數據在前臺線程間不共享，不需要鎖或原子操作等進行線程間同步，例如Cache的鎖競爭和pointer swizzling的swizzle/unswizzle以及內存回收都同時可以解決。
目前該方法對只讀性能的提升達到30%左右。此項優化工作還未完全完成，進一步的我們需要優化對熱點Subtable的訪問問題, 另一方面在事務引擎中，跨表訪問是非常常見的，如果一個線程執行一個需要訪問到多張表的事務，則如何調度該事務是一個很有挑戰性的問題。
實驗驗證
測試環境
64threads，2Socket.
L1-Cache：32KB Data Cache / 32KB Instruction Cache
L2 Cache：256KB
L3 Cache：32MB
RAM：512GB，使用numactl --interleave=all關閉NUMA
測試場景
key 16Byte，value 8Byte，32張表，每張表2000W條記錄，寫入數據之後下壓到L1層，執行一輪預讀預熱到緩存中，然後執行readrandom測試。
測試結果
我們以X-Engine原始架構的隨機讀性能做baseline，然後依次疊加上前述的優化手段。
第一步增加了新的數據頁編碼方法以及數據頁上的SIMD指令查找算法，獲得了13.8%的性能提升。
第二步，我們在代碼中增加了PointSwizzling優化，性能提升相比BaseLine達到了90%。最後我們重構了X-Engine的執行框架，引入多核無共享執行架構。
最終整體性能相對比BaseLine的提升達到了123%. 測試中也分析了這測試過程中CPU L1 Data Cache miss率的變化以及程序運行的IPC的變化。
為了確定我們的優化手段在哪些路徑上產生了最關鍵的作用，我們對每一步優化手段產生的性能提升進行了breakdown測試並製作瞭如下的表格. 從這裡可以看出對性能提升最大的一步是對DataBlock的間接應用改Direct引用，考慮到DataBlock的數目較多，其原始實現中的Hash查找表比較大，Cache效率較低，產生這樣的效果在預期之中。而Index和ExentMeta對象相對數目較少(大概為DataBlock的1/128), 本身具有較好的查找效率，因此對性能的影響也較小。