由于X-Engine資料頁編碼格式和查找算法與很多資料庫引擎(如InnoDB)是類似的，是以文中提出的方法對使用類似資料頁格式的存儲引擎都是普适的。
1、X-Engine資料頁格式和頁内查找算法
X-Engine是LSM-tree架構的存儲引擎。查找一條記錄，首先從記憶體表Memtable中查找，未命中，則從磁盤中查找。磁盤上的資料，通過索引定位到目标DataBlock，并裝載進記憶體查找目标記錄。查詢完成後DataBlock被放入緩存，等待下次查詢。
X-Engine KV接口單點查詢，結果全部緩存命中的場景，通過perf分析表明：在DataBlock中定位seek()及順序next()操作，消耗了35%的CPU資源，是單一最大的CPU消耗點。
X-Engine資料頁格式
X-Engine的DataBlock中記錄編碼格式如下圖所示：
此格式的幾個基本特點：
DataBlock預設定長16KB(可配置調整)，且DataBlock支援原地做單條記錄的更新操作，即一個DataBlock隻能完整的生效或者被廢棄。
記錄按key從小到大順序排列，key和value連續存儲在一起。在一段連續存儲(預設為16條)的記錄段上，使用字首編碼。每個字首編碼段的第一條記錄稱為一個restart點，在每個restart點之後的記錄，key隻需要存儲相對restart點的key的delta部分。
DataBlock末尾是restart offset數組，它的每個元素存儲了restart點相對DataBlock起始位址的偏移。由于offset都是4位元組，在此數組中可直接二分查找，快速定位到目标restart點在DataBlock中的偏移位置。
DataBlock頁内查找算法
在一個存儲N條記錄的DataBlock中，查找一條key=X的記錄。查找算法如下圖所示的1~5步執行：
1.在restart數組二分查找，定位到最後一個小于或等于X的記錄的offset。
2.從offset開始，依次向後讀取每條記錄，與X做比較，直到找到大于等于X的第一條記錄，并傳回偏移位置。
3.該過程涉及對字首編碼的解碼。在一個字首編碼段中，除第一條記錄外，後續key隻儲存了相對于第一條記錄的delta部分。需要首先拿到字首編碼段的第一條key（如111100，前4位為字首），再與本key記錄的delta（如01，後兩位為delta）做拼接，才能獲得完整的key（111101）内容。最後用完整key，與X作比較，以判定是否已經達到搜尋目标位置。
現有查找算法的問題
分析DataBlock格式及二分查找算法的執行過程，可以發現兩個主要問題：
restart數組隻存儲記錄的偏移而不存儲key的實際内容，每次二分查找中選中的pivot點指向的offset位置，與restart數組自身所在的記憶體位置存在較大的偏移（最大接近8KB，即第一次二分時,DataBlock大小的一半)。查找中，CPU訪存位址在restart數組和DataBlock中實際記錄存儲位置之間跳躍。
DataBlock搜尋過程所通路到的key的offset，也是在DataBlock的大小（16KB）範圍内跳躍。雖然二分搜尋每次能将需要搜尋的記憶體空間減少一半，但想要達到前後相鄰的兩次查找比較，第二次比較利用前一次的CPU cache，則前後兩次通路的位址之差要限定在一個CPU cache line大小之内。在這個過程之前，二分搜尋過程需要疊代多次，每次必然會發生訪存的cache Miss.
按照CPU cache友好的程式設計原則，在通路時序上相近的資料，在記憶體實體位址上最好相鄰，如此可以充分發揮CPU prefetcher的效用，減少CPU cache miss。DataBlock的二分查找算法，無論是restart數組的記憶體位址和key的記憶體位址之間，還是前後兩次二分搜尋通路的key的記憶體位址之間，都在計算時序上相鄰，記憶體位址不相鄰。此格式和查找過程是CPU cache友好性原則的極端反例。
2、Cache-Conscious Block Layout
CPU層級Cache
現代CPU的運算頻率相較于伺服器主記憶體的通路速度存在較大的差異，為了解決通路主存速度過慢的問題，現代CPU中一般會增加多個層次的cache，CPU cache使用SRAM制造且離CPU計算單元的距離更近，是以有着更快的通路速度。
有了CPU cache之後，CPU處理資料時首先嘗試從cache中讀取，如果找到就可以立即送入CPU處理，如果未找到，則會從下一層級的cache或者主存中讀取，同時把讀取的資料放入cache以便下一次使用. 現代CPU的一般使用三層cache(L1/L2/L3)，其中L1又分為指令cache和資料cache，其架構大緻如下圖所示：
從L1 cach 到 L2 cache 到 L3 cache，容量越來越大，離CPU計算核心越來越遠，而速度則越來越慢。
由于資料在不同層級cache以及主寸之間的轉移是以cache line(64Bytes)為機關, 而從不同層級cache的速度差異可以看出，為了達到更快的資料通路速度，我們需要盡量發揮cache的局部性特征，将計算時序上相鄰的資料在記憶體位址上安排在一起，目标是實作一次讀取到高層次cache的資料即可供後續的多次運算使用。任何想達到最優計算性能的記憶體資料結構都需要遵循這個設計思想。
2層B+樹索引
針對前面的分析，要提升資料頁上的查找效率，需要重排X-Engine DataBlock格式，并達到如下兩個效果：
key内容和索引資訊在記憶體實體位址上相鄰。
搜尋路徑上，通路時序上相鄰的key，記憶體實體位址上也相鄰。
要解決第一個問題，最直接的方法就是改變key的存儲位置，将key的内容提取出來，并儲存在DataBlock尾部的restart數組中。這樣隻需在儲存有restart數組和key内容的記憶體範圍内執行二分查找，由于去除了長度較大的value的影響，此搜尋區域更小，cpu cache效率更高。
要解決第二個問題，更改二分搜尋算法，前後相鄰的比較過程中的key儲存在一起。一個很容易想到的解決辦法是：将二分查找過程中相鄰的節點，在記憶體儲存在一個連續位址上，作為第一次篩選的界标，大幅縮小搜尋範圍（想象一下B樹）。
綜合上面的分析，B+樹可以滿足需求，對DataBlock内部的索引和查找過程做出如下簡單的修改：
1.去除全局restart數組，提取出restart數組中元素所對應的key内容與restart偏移儲存在一起，如此可以避免二分查找時跳躍到DataBlock中間位置進行通路。
2.将原有一維的restart數組，改造為兩層的B+樹索引結構。非葉子節點為restart數組二分搜尋算法中，邏輯比較上前後相鄰的key組成。節點内部的key依然從小到大排列。這樣可以保證邏輯前後響鈴被通路的key，在記憶體實體位址上也儲存在一起。
上圖是該2層B+樹查找結構的邏輯布局圖(實體上他們是順序存儲)。實際存儲方式是按層數周遊算法順序儲存每個節點，指向子節點的指針使用相對記憶體首位址的offset而不是指針，因為考慮到最大16KB的DataBlock大小，offset可以用更少的位元組數來表示，代價是多了一步計算過程。
采用兩層B+樹的原因有兩個：
1.如果采用一層，則root節點會非常大，特别是在key比較長時，其搜尋效率與原有DataBlock的類似。
2.采用更多層次的B+樹也不合适，一方面層次增加，搜尋每一層的節點都會導緻cache miss. 另一方面X-Engine 16KB的DataBlock大小儲存的記錄有限, 不需要太深層次的樹結構，而且我們的目标CPU平台L1 Data Cache大小在幾十KB級别，L2 Cache在MB級别，這允許我們使用較大的節點大小。
索引查找效率分析
除了使用2層B+樹索引替換原有的restart數組+key偏移的索引結構, 為了進一步提升效率，在代碼實作上做如下設計：
在一個有N個條記錄的的DataBlock上，建構的索引B+樹的節點中key的數目為N的平方根。這樣可以保證在B+樹的第一層和第二層每個節點有均等的大小。
在通路每一層B+樹節點前, 手動執行調用prefetch指令。将整個節點預取到CPU cache中，由于一個B+樹節點必然比CPU的cache line(64B)大，此步會觸發數個in flight的讀記憶體請求。
實際運作中最優的節點大小取決于多個因素，key的長度，DataBlock中記錄的數目N，運作時的線程并發度以及L1/L2 Cache等對最優節點大小都有影響。
同時如果我們對一個節點的preload速度太快，而CPU在此節點上的搜尋時間過長，則preload進cach中的資料可能被其他線程線程所淘汰（在L1/L2/L3的每一層都是如此）。而如果preload太慢，比在CPU在此節點上的搜尋速度慢，則可能發生發生cache miss， CPU陷入stall，也對速度不利。
為了簡化測試複雜度，我們設定了固定的節點内key數目為N的平方根。
3、測試評估
測試環境及測試方法
伺服器配置：
CPU配置:Intel(R) Xeon(R) Platinum 8163 CPU @ 2.50GHz， 24core48threads， 2Socket.
L1-Cache:32KB Data Cache , 32KB Instruction Cache
L2 Cache:1MB, L3 Cache 32MB
RAM:768GB，關閉NUMA
測試機及統計采樣方法:
建立32張表，每張表插入100W條記錄，然後執行一次全表順序讀，将所有資料預熱緩存到記憶體，并為每個DataBlock建構好Cache-Consicious的頁内索引結構。
使用不同的線程數測試ReadOnly OPS(operation per second)，共7組，線程數分别為2,4,8,16,32,64,128。每組測試20S. 測試啟動5S後統計CPU各層級cache的的狀态以及IPC等名額，采樣時間5S。
測試結果及分析
通過X-Engine的KV接口測試點查場景的性能，以檢驗DataBlock格式重構之後執行查詢時的性能以及cache命中率表現，測試僅驗證readonly，unique key distribution場景。
最終吞吐及CPU cache miss率：
1.在所有并發下，新的Block排布方式均有有性能優勢，在32線程時，點查吞吐最大提升17%。
2.Last Level Cache的miss率，在新的Block排布方式下下降非常明顯，在32線程時，LLC miss比率從27%下降到15%。不過，有一個疑問點是性能的提升沒有LLC miss的變化顯著。
IPC(instrunction per cycle)及instruction cache miss率對比：
1.在所有的并發下，新的DataBlock排布方式IPC都有提升。
2.新DataBlock排布方式，CPU的 L1 instrunction cache miss數值更高。因為相較于之前的記錄排布方式，新格式的邏輯更複雜。同時為了節省空間，使用計算偏移的方式替代直接指針。最終導緻l1-icache的miss上升。另一個有趣的現象是，随着并發增加，l1-icache的miss次數是下降的，考慮到并發執行的線程可以複用instruction cache, 這個結果是符合邏輯的。
而一個反常的結果是，所有并發場景，新的DataBlock排布方式CPU L1 Data Cache的miss率反而是上升的，如下圖所示：
猜測原因是新的2層B+數索引結構下，處理每一層節點都有顯式的prefetch操作，由于l1-data-cache比較小，此時不同線程通路的data在l1-data-cache中會産生擠占效應，在代碼中disable顯式的prefetch操作驗證了這個結論。
對比LLC的miss率和l1-data-cache的miss率，我們可以判定進一步提升性能的關鍵在提升l1-data-cache的命中率，即需要尋找到一個時間平衡點，讓prefetch到l1-data-cache的資料在被擠占出cache之前剛好處理完。
以上是一個驗證性測試(key長度8Byte,value長度8Byte)，從Perf的結果看，使用新的Block排布方式，點查場景DataBlock内查找的CPU消耗隻是從35下降到30%左右，是以還有更多的潛力需要挖掘。
4、未來要解決的問題
本文驗證了X-Engine中DataBlock内部索引格式一個優化實作，其有着更好的CPU cache友好性，由于隻進行幾個簡單的對比測試，是以還有一些未明确的問題需要進一步的分析：
1.驗證不同key-value長度場景下，此優化對性能的提升效果。
2.從perf結果看，LLC的命中率大幅增加，但是離CPU最近的L1-Data-Cache的cache miss有上升，L1 Data Cache的cache miss上升可能是導緻性能提升幅度不大的原因，需要進一步的測試對比。
3.對于2層B+樹的索引節點，需要尋找到一個最優的節點大小，此大小與key-value長度，并發數線程數，L1 Cache/L2 Cache/L3 Cache大小等因素相關。理論上可以對關系建立數學模型。
4.短key-value場景，新的編碼格式，記憶體增加幅度可能較大(需要進一步量化)，此時一個方法是可以動态将部分熱點DataBlock改造成cache友好但記憶體使用稍多的索引結構。而這裡挑選哪些DataBlock需要精準的熱點識别算法(我們可以利用LRU，在DataBlock LRU連結清單頭部的資料頁會更熱),如何在兩種DataBlock格式之間安全的轉換也是需要探索的工程問題。
5、相關知識：InnoDB資料頁格式及查找分析
InnoDB的資料頁(Page)與X-Engine的DataBlock内部的查找算法類似。也包含尾部的restart 數組以及Page内部的記錄記憶體堆。差别之處在于：InnoDB為了支援原地更新，其資料Page通常不會填滿。記錄在Page中并不是總是有序緊湊排列，而是通過記錄之間的指針保持前後索引關系。
從記錄查找過程看，針對X-Engine DataBlock記錄排布方式的優化方法對InnoDB的Page也是适用的。
但是一個比較關鍵的問題是InnoDB的資料Page是需要原地更新的，維護一個支援快速查找的索引結構會在更新有着較低的效率。根據已有的學術界研究結果，在索引中儲存一定數量的空餘slot用作後續更新及插入用，是一個可行的方法。
目前，MySQL(X-Engine) RDS已在阿裡雲上線，如何使用請點
這裡。
相關閱讀：前沿幹貨 | X-Engine:RDS MySQL的新存儲引擎
直播預告
3月26日 15:00-16:00
邀您一同見證
雲資料庫SQL Server 2019版重磅釋出
全面提升成本效益及資料庫能力
點這裡即可預約觀看直播