概述
目前RDS(X-Engine)主打的優勢是低成本，高成本效益，在MySQL生态下幫助解決使用者的成本問題。使用X-Engine的使用者一般資料量都較大，比如已經在集團大規模部署的交易曆史庫，釘釘曆史庫以及圖檔空間庫等。資料既然存儲到了X-Engine，當然也少不了計算需求，是以如何高效執行查詢是未來X-Engine一定要解決的問題。目前，在MySQL體系下，每個SQL都至多隻能使用一個CPU，由一個線程完成串行掃描行并進行計算。X-Engine引擎需要提供并行掃描能力，這樣讓一個SQL具備利用多核掃描資料能力，整體縮短SQL執行的響應時間。
串行掃描
在具體介紹X-Engine并行掃描之前，先簡單介紹下目前X-Engine串行掃描的邏輯。大家知道資料庫引擎的核心差別在于資料結構，比如InnoDB引擎采用B+Tree結構，而X-Engine則采用LSM-Tree結構，兩者各有特點，B+Tree結構對讀更友好，而LSM-Tree則對寫則更友好。
對于一條SQL，在優化器選擇好了執行計劃以後，掃描資料的方式就确定了，或是走索引覆寫掃描，或是走全表掃描，或者走range掃描等，這點通過執行計劃就可以直覺的看到。無論哪種方式，本質來說就是兩種，一種是點查詢，一種是範圍查詢，查詢的資料要麼來自索引，要麼來自主表。X-Engine的存儲架構是一個類LSM-tree的4層結構，包括memtable，L0，L1和L2，每一個層資料都可能有重疊，是以查詢時(這裡主要讨論範圍查詢)，需要将多層資料進行歸并，并根據快照來确定使用者可見的記錄。
如下圖所示，從存儲的層次上來看，X-Engine存儲架構采用分層思想，包括memtable，L0，L1和L2總共4層，結合分層存儲和冷熱分離等技術，在存儲成本和性能達到一個平衡。資料天然在LSM結構上存在多版本，這種結構對寫非常友好，直接追加寫到記憶體即可；而對讀來說，則需要合并所有層的資料。
并行掃描
X-Engine并行掃描要做的就是，将本來一個大查詢掃描，拆分成若幹小查詢掃描，各個查詢掃描的資料不存在重疊，所有小查詢掃描的并集就是單個大查詢需要掃描的記錄。并行掃描的依據是，上層計算對于掃描記錄的先後順序沒有要求，那麼就可以并行對掃描的記錄做處理，比如count(*)操作，每掃描一條記錄，就對計數累加，多個并發線程可以同時進行。其它類型的聚集操作比如sum，avg等，實際上都符合這個特征，對掃描記錄的先後順序沒有要求，最終歸結到一點都是需要引擎層支援并行掃描。
如下圖所示，X-Engine整個包括4層，其中記憶體資料用memtable表示，磁盤資料用L0，L1和L2表示，memtable這一層是一個簡單的skiplist，每個方框表示一條記錄；L0,L1和L2上的每個方框表示一個extent，extent是X-Engine的概念，表示一個大的有序資料塊，extent内部由若幹個小的block組成，block裡面的記錄按key有序排列。
根據分區算法得到若幹分區後，可以劃分分區，不同顔色代表不同的分區，每個分區作為一個并行task投入到隊列，worker線程從TaskQueue中擷取task掃描，各個worker不需要協同，隻需要互斥的通路TaskQueue即可。每個掃描任務與串行執行時并無二樣，也是需要合并多路資料，差別在于查詢的範圍變小了。
分區算法
将查詢按照邏輯key大小劃分成若幹個分區，各個分區不存在交疊，使用者輸入一個range[start, end)，轉換後輸出若幹[start1,end1),[start2, end2)...[startn,endn)，分區數目與線程數相關，将分區數設定線上程數的倍數(比如2倍，具體倍數可調)，目的是分區數相對于線程數多一點，以均衡各個線程并行執行速度，提升整體響應時間。
資料按冷熱分散存儲在memtable，L0，L1和L2這4層，如果資料量很少，可能沒有L1或者L2，甚至資料在全記憶體中。我們讨論大部分情況下，磁盤都是有資料的，并且memtable中的資料相對于磁盤資料較小，主要以磁盤上資料為分區依據。分區邏輯如下：
1).預估查詢範圍的extent數目
2).根據extent數目與并發線程數比例，預估每個task需要掃描的extent數目
3).對于第一個task，以查詢起始key為start_key，根據每個task要處理的extent數目，以task中最後一個extent的largest_key資訊作為end_key
4).對于其它task，以區間内第一個extent的smallest_key作為start_key，最後一個extent的largest_key作為end_key
5).對于最後一個task，以區間内第一個extent的smallest_key作為start_key，以使用者輸入的end_key作為end_key
至此，我們根據配置并發數，将掃描的資料範圍劃分成了若幹分區。在某些情況下，資料可能在各個層次可能分布不均勻，比如寫入遞增的場景，各層的資料完全沒有交集，導緻分區不均，是以需要二次拆分，将每個task的粒度拆地更小更均勻。同時，對于重IO的場景(掃描的大部分資料都無法cache命中)，X-Engine内部會通過異步IO機制來預讀，将計算和IO并行起來，充分發揮機器IO能力和多核計算能力。
對比InnoDB并行掃描
InnoDB引擎也提供了并行掃描的能力，目前主要支援主索引的count(*)和check table操作，而實際上X-Engine通用性更好，無論是主表，還是二級索引都能支援并行掃描。InnoDB與X-Engine一樣是索引組織表，InnoDB的每個索引是一個B+tree，每個節點是一個固定大小的page(一般為16k)，通過LRU緩存機制實作内外存交換，磁盤上空間通過段/簇/頁三級機制管理。InnoDB的更新是原地更新，是以通路具體某個page時，需要latch保護。X-Engine的每個索引是一個LSM-tree，記憶體中以skiplist存在；外存中資料包括3層L0,L1和L2，按extent劃分，通過copy-on-write多版本中繼資料機制索引extent，每次查詢對應的一組extent都是靜态的，是以通路時，沒有并發沖突，不需要latch保護extent。
存儲結構差異導緻分區和掃描的邏輯也不一樣，InnoDB的分區是基于B+tree實體結構拆分，根據線程數和B+tree的層數來劃分，最小粒度能到block級别。X-Engine的分區分為兩部分，記憶體中memtable粒度是記錄級；外存中資料是extent級，當然也可以做到block級别。兩者最終的目的都是希望充分利用多核CPU資源來進行掃描。下圖是InnoDB的分區圖。
InnoDB和X-Engine都是通過MVCC機制解決讀不上鎖的問題，進行掃描時需要過濾不可見記錄和已删除的記錄。InnoDB的delete記錄有delete-mark，多版本記錄存儲在特殊的undo段中，并通過指針與原始記錄建立關聯，事務的可見性通過活躍事務連結清單判斷。X-Engine是追加寫方式更新，沒有undo機制，多版本資料分布在LSM-tree結構中，delete記錄通過delete-type過濾，事務的可見性通過全局送出版本号判斷。
InnoDB掃描時，根據key搜尋B+tree，定位到葉子節點起始點，通過遊标向前周遊；是以分區後，第一次根據start_key搜尋到葉子節點的指定記錄位置，然後繼續往後周遊直到end_key為止。X-Engine掃描時，會先拿一個事務snapshot，然後再拿一個meta-snapshot(通路extent的索引)，前者用于記錄的可見性判斷，後者用于“鎖定”一組extent，這樣我們有了一個“靜态”的LSM-tree。基于分區的範圍[start_key,end_key]，建構堆進行多路歸并，從start_key開始輸出記錄，到end_key截止。
性能測試
通過配置參數xengine_parallel_read_threads來設定并發線程數，就能開始并行掃描功能，預設這個值為4。我這裡做一個簡單的實驗，通過sysbench導入2億條資料，分别配置xengine_parallel_read_threads為1，2，4，8，16，32，64，測試下并行執行的效果。測試語句為select count(*) from sbtest1;
- 測試環境
硬體：96core，768G記憶體
作業系統：linux centos7
資料庫：MySQL8.0.17
配置：xengine_block_cache_size=200G, innodb_buffer_pool_size=200G
采用純記憶體測試，所有資料都裝載進記憶體，主要測試并發效果。
- 測試結果
橫軸是配置并發線程數，縱軸是語句執行時間，藍色軸是xengine的執行時間，綠色軸是innodb執行的時間，當配置32個并發時，掃描2億條資料隻需要1s左右。
- 結果分析
可以看到X-Engine和Innodb都具有較好的并發掃描能力，X-Engine表現地更好，尤其是在16線程以後，InnoDB随着線程數上升，執行時間并沒有顯著下降。這個主要原因是InnoDB的并行是基于實體Btree的拆分，而X-Engine的并行是基于邏輯key的拆分，是以拆分更均勻，基本能随着線程數增加，響應時間成倍地減少。
總結與展望
目前X-Engine的并行掃描還隻支援簡單count(*)操作，但已經顯示出了充分利用CPU多核的能力。我們将繼續向上改造執行器接口，以支援更多的并行操作。無論是RDS(X-Engine)還是我們的分布式産品PolarDB-X都将在X-Engine的基礎上，讓單條SQL跑地更快。