天天看點

X-Engine并行掃描

概述

目前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并行掃描

并行掃描

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即可。每個掃描任務與串行執行時并無二樣,也是需要合并多路資料,差別在于查詢的範圍變小了。

X-Engine并行掃描

分區算法

将查詢按照邏輯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的分區圖。

X-Engine并行掃描

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;

  1. 測試環境

硬體:96core,768G記憶體

作業系統:linux centos7

資料庫:MySQL8.0.17

配置:xengine_block_cache_size=200G, innodb_buffer_pool_size=200G

采用純記憶體測試,所有資料都裝載進記憶體,主要測試并發效果。

  1. 測試結果
X-Engine并行掃描

橫軸是配置并發線程數,縱軸是語句執行時間,藍色軸是xengine的執行時間,綠色軸是innodb執行的時間,當配置32個并發時,掃描2億條資料隻需要1s左右。

  1. 結果分析

可以看到X-Engine和Innodb都具有較好的并發掃描能力,X-Engine表現地更好,尤其是在16線程以後,InnoDB随着線程數上升,執行時間并沒有顯著下降。這個主要原因是InnoDB的并行是基于實體Btree的拆分,而X-Engine的并行是基于邏輯key的拆分,是以拆分更均勻,基本能随着線程數增加,響應時間成倍地減少。

總結與展望

目前X-Engine的并行掃描還隻支援簡單count(*)操作,但已經顯示出了充分利用CPU多核的能力。我們将繼續向上改造執行器接口,以支援更多的并行操作。無論是RDS(X-Engine)還是我們的分布式産品PolarDB-X都将在X-Engine的基礎上,讓單條SQL跑地更快。