TDSQL | DB·洞見回顧|基於LSM-Tree儲存的資料庫效能改進

語言: CN / TW / HK

LSM-Tree(Log Structured Merge Tree)是資料庫領域內較高效的key-value儲存結構,被廣泛應用於工業界資料庫系統,如經典的單機kv資料庫LevelDB、RocksDB,以及被諸多分散式NewSQL作為底層儲存引擎。

本期將由騰訊雲資料庫高階工程師韓碩來為大家分享基於LSM-Tree儲存的資料庫效能改進,重點介紹近年來學術界對LSM-Tree的效能改進工作,並探討這些改進措施在工業界資料庫產品中的應用情況以及落地的可能性。以下是分享實錄:

1. LSM-Tree基本結構

LSM-Tree全稱為“Log Structured Merge Tree”,是一種基於磁碟儲存的資料結構。1996年Patrick O’Neil等人在資訊系統期刊上發表了一篇題名為“Log Structured Merge Tree”的論文,首次提出LSM-Tree結構。相比於傳統的B+樹,LSM-Tree具有更好的寫效能,可以將離散的隨機寫請求轉換成批量的順序寫操作,無論是在RAM、HDD還是在SSD中,LSM-Tree的寫效能都更加優秀。

作為高效的key-value儲存結構,LSM-Tree已被廣泛應用到工業界資料庫系統中,如經典的單機kv資料庫LevelDB、RocksDB,以及被諸多分散式NewSQL作為底層儲存引擎,近日釋出的TDSQL新敏態引擎儲存模組也運用了LSM-Tree結構。LSM-Tree結構有較多優點:寫效能強大、空間利用率高、較高的可調參特性、併發控制簡單、有完備的修復方案等。

LSM-Tree的本質是基於out-place update即不在原地更新。下圖展示了in-place update即原地更新與out-place update即不在原地更新的區別。

在in-place update中,資料更新操作是將資料的新值直接覆蓋舊值,但會帶來隨機讀寫問題。在out-place update中,資料更新操作則是將新值按時間順序追加到檔案末尾,通常會帶有版本號用於標記新值或舊值,一般為順序寫,因此寫效能更好,但缺點是會產生冗餘資料,在讀效能和空間利用率上也無法與in-place update相比。

當前主流的LSM-Tree基本結構如下圖,分為記憶體和磁碟兩部分。記憶體採用MemTable資料結構,可以通過B+樹或跳錶實現。MemTable用於接受最新的資料更新操作,維護內部資料in-tree邏輯上的有序。磁碟中的部分資料儲存物理有序。資料按照層進行堆放,層次越往下,資料寫入的時間就越早。每層內部按是否有序可劃分為一個或多個sorted run。一個sorted run內部的資料必定有序(通常指物理上有序)。sorted run資料可進一步劃分為不同的SSTable。當MemTable中的資料寫滿時,其會向L0進行落盤操作即Flush操作。如果LSM-Tree的某一層也達到容量閾值,就會向下合併,將同樣的key的過期版本清除,即compaction操作。

RocksDB是基於LSM-Tree的儲存引擎,其基本結構如下圖。它與LSM-Tree基本結構在主體上保持一致,不同點在於RocksDB的記憶體中增加了Immutable MemTable部分,這是用於Flush操作的寫快取機制。當MemTable中的資料寫滿時,會先暫存到Immutable MemTable中,再通過後臺的非同步執行緒將Immutable MemTable慢慢落盤到磁碟中的SST基本件。RocksDB中還增加了WAL日誌,用於crash時的資料恢復。

LSM-Tree支援的查詢可分為點查與範圍查詢兩大類,對應的執行方式如下: ● 點查:先查MemTable,再從SST中的Level0、Level1…...一層層向下探查,找到資料就返回。由於上層資料必定比下層資料的版本新,因此返回的都是最新資料。 ● 範圍查詢:每一層都會找到一個匹配資料項的範圍,再將該範圍進行多路歸併,歸併過程中同一key只會保留最新版本。

LSM-Tree效能的衡量主要考慮三類因素:空間放大、讀放大和寫放大。

第一類因素是空間放大。在LSM-Tree中所有寫操作都是順序追加寫,資料的更新操作則是通過建立一個新的空間來儲存新值,即out-place update。與此同時,因為舊值不會立即被刪除,因此會佔用部分空間。實際上這部分冗餘資料佔用空間的大小要遠大於有效資料本身,這種現象被稱為“空間放大”。LSM-Tree會利用compaction操作來清理舊資料從而降低空間放大。

第二類因素是讀放大。在LSM-Tree、B+樹等外存索引結構中,進行讀操作時需要按從上到下的順序一層層去讀取儲存節點,如果想讀一條資料,就會觸發多次操作,即一次讀操作所讀到的資料量實際上要遠大於讀目標資料本身,從而影響讀效能,這種現象被稱為“讀放大”。      第三類因素是寫放大。在LSM-Tree中,compaction操作會將多個SST檔案反覆讀取,合併為新的SSTable檔案後再次寫入磁碟,因此導致一條kv資料的多次反覆寫入操作,由此帶來的IO效能損失即寫放大。

LSM-Tree的初衷是想通過空間放大和讀放大來換取寫放大的降低,從而達到極致的寫效能,但也需要做好三方面因素的權衡。EDBT 2016的一篇論文首先提出RUM猜想(R為read,U為update,M為memory usage,RUM為三者縮寫)。該論文認為,三者之間存在權衡關係,無法使得三個方面的效能都達到最優,因此必須在三者之間進行有效權衡。

以compaction操作為例,其目的是保證資料的區域性有序和清理資料舊值,即一個sorted run內部的多個SST檔案中的資料是有序的,從而降低讀放大。對一個查詢而言,在一個sorted run中至多隻需要讀取一個SST中的一個數據塊。

如果完全不做compaction操作,即一直順序寫,LSM-Tree就會退化為log檔案,這時寫效能達到最佳。因為只需要順序寫log即可,不需要做任何操作。但讀效能將會處於最差狀態,因為在沒有任何索引、無法保證有序性的情況下,每次想讀到固定的資料項,就需要掃描所有的SST件。

如果compaction操作做到極致,實現所有資料全域性有序,此時讀效能最優。查詢時只需要通過索引和二分法即可迅速找到要讀的鍵值的位置,一次IO操作即可完成,但代價是需要頻繁進行compaction操作來維持全域性有序狀態,從而造成嚴重的寫放大,即寫效能變差。

這就延伸出兩種compaction策略:

● Tiering compaction:較少做compaction操作,有序性較弱,每一層允許有多個sorted run。

● Leveling compaction:更頻繁的compaction操作,儘可能增強有序性,限制每一層最多隻有1個sorted run(L0層除外)。

2. Compaction優化策略與分析

Leveling compaction策略中,每層只有一個sorted run,sorted run內部的資料保持物理有序。具體實現上我們以RocksDB為例。一個sorted run可以由多個key不重疊且有序的SSTable files組成。當第L層滿時,L層會選取部分資料即部分SSTable,與L+1層有重疊的SSTable進行合併,該合併操作即compaction操作。

Tiering compaction策略中,每層可以有至多T個sorted run,sorted run內部有序但每層不完全有序。當第L層滿時,L層的T個sorted run會合併為L+1層的1個sorted run。因為每層允許有多個sorted run,因此SST檔案間可能會存在資料範圍的重疊,compaction操作的頻率會更低,寫效能也會更強。

兩種compaction策略各有優劣。Tiering compaction因為compation操作頻率低,過期版本的資料未能得到及時清除,因此空間利用率低,由此帶來的查詢操作的代價比較高。在極端情況log file即完全不做compaction操作時,寫入效能最優。Leveling compaction則會更頻繁地做compaction操作,因此資料趨向更有序。極端情況sorted array即資料達到全域性有序時,此時查詢效能和空間利用率最優。

SIGMOD 2018的一篇論文對上述兩種compaction策略進行了詳細的理論分析,分析結果歸納為下表,其分析結果與前述一致。理論分析過程如下:

先從寫入操作複雜度進行分析。I/O以block為基本單位,一次I/O平均讀寫B條kv,因此一條kv寫一次磁碟的代價可以表示為1/B。在leveling compaction策略中,第i層向第i+1層最多合併T次,在第j層合併到第i層時,其可被後續的資料項反覆進行t-j次合併。由此可得,每條KV在第i層即任意一層被平均IO的讀寫次數為t/2次,即O(T)。從MemTable一直向下合併到最後一層即第L層,會得到平均寫磁碟數即“TL/B”。

以下圖為例,每合併一次,第i層的增量不會超過1/T。第i層通道從空到滿,其最多向下合併t次,因此每條kv在每層平均被合併2/T次。

在Tiering compaction策略中,每條KV在第i層時只會被合併一次,因此從MemTable一直向下合併到最後一層即第L層,會得到平均寫磁碟數即L/B。

在第i-1層向第i層合併時,會在第i層產生一個新的sorted run,平均每條kv在每層只會被合併一次。

再從空間放大率進行分析。space-amplification定義為:過期版本的kv數與有效kv總數之比。在Leveling compaction策略中,最壞的情況為前L-1層的每條資料在最後一層即第L層中都各有一條未被清除的過期版本資料。每層容量為比值為T的等比數列,根據等比數列求和公式, 第L−1層的kv數量佔總kv數的1/T,最後一層則佔 (T−1)/T,因此空間放大為1/T,空間放大率較低。

在Tiering compaction策略中,允許每層最多有T個sorted run,最壞情況下最後一層的T個sorted run之間都是每個kv的不同版本,即一條kv在最後一層的每個sorted run都出現一次,共T個不同版本,因此空間放大為O(T)。

Leveling compaction的空間放大係數為1/T,因此空間利用率較高。Tiering compaction在最壞情況下,最後一層的每個sorted run都是冗餘資料,空間利用率較差。

再從查詢角度進行分析。點查使用Bloom filter進行過濾,將其分成兩類:

● 讀穿透,即查詢資料不存在。

● 假設知道每次發生假陽性的概率,如果判定結果為假陽性,則需要讀一次磁碟。

在Leveling compaction策略中,每層只有一個sorted run,實現完全有序,因此每層只需要查詢一次Bloom過濾器。根據二項分佈期望公式,推匯出的期望讀盤次數為L×e的-m/n次方。

在Tiering compaction策略中,每層最多有T個sorted run,最多可能查詢T次Bloom filter,在前述結構基礎上乘以T的係數,根據推匯出的期望讀磁碟次數,其查詢效能落後於Leveling compaction。

如果查詢資料存在,因為發生假陽性的概率遠小於1,因此大部分情況下,無論是Tiering compaction還是Leveling compaction,都只需要讀一次盤。

再從範圍查詢角度進行分析。該論文將範圍查詢分為短範圍查詢和長範圍查詢。短範圍查詢指返回block數量的大小不超過最大層數範圍的兩倍;反之則為長範圍查詢。

通過統計公式發現,短範圍查詢在歸併前的各版本資料趨向於均勻分佈在各層,因此Leveling compaction和Tiering compaction的查詢複雜度分別為O(L)和O(T×L)。長範圍查詢在歸併前各版本資料大部分來自最後一層,因此上述兩種策略的代價分別為返回block數的大小、返回block數的大小再乘以T,因此Leveling compaction比Tiering compaction的讀效能更好。

通過上述理論分析,可以得到如下結論:

● Tiering compaction的寫放大低,compaction頻率低,其缺陷為空間放大高、查詢效率低,更利於update頻繁的workload;Leveling compaction的寫放大高,compaction操作更頻繁,但空間放大低,查詢效率高。

● 儘管Tiering compaction和Leveling compaction的空間放大不同,但導致空間放大的主要原因相同,即受最下層的過期版本資料影響。

● 越往下的層,做一次compaction的I/O代價越高,但發生的頻率也更低,不同層之間做compaction的期望代價大致相同。

● 點查、空間放大、長範圍查詢的效能瓶頸在LST-tree的最下層,而更新操作則更加均勻地分佈在每一層。因此,減少非最後一層的compaction頻率可以有效降低更新操作的代價,且對點查、空間放大、長範圍查詢的效能影響較小。

3. 降低寫放大

基於上述理論分析,該論文提出混合compaction策略即Lazy Leveling。它將Leveling與Tiering進行結合,在最後一層使用Leveling策略,其他層使用Tiering策略,即最後一層只能存在唯一的sorted run,其他層允許存在多個sorted run,從而有效降低非最後一層做compaction的頻率。

下表是採取Lazy Leveling策略後的效能彙總表,其中,綠色部分表示效果較好,紅色部分表示較差,黃色部分代表適中。從下表可以看出,Lazy Leveling的更新操作(update)效能優於Leveling,接近於Tiering。這是由於在前L-1層維持Tiering策略,做compaction的頻率更低,寫放大低。但Lazy Leveling的空間放大接近於Leveling,遠好於Tiering。這相當於結合了兩種策略的優勢。

對於點查(point lookup),論文中分別分析了查詢不存在kv和kv在最後一層兩種情況,並基於論文Monkey的思路對每層的bloom filter bit進行了優化,可以達到與Leveling+Monkey策略相匹配的點查效能。對於長範圍查詢,Lazy Leveling可以做到與Leveling一致的效能,而短範圍查詢則退化至接近Tiering的水平。

論文對此進行總結:使用一種單一compaction策略,不可能在上述所有操作中做到效能最優。Lazy Leveling本質上是Tiering與Leveling策略的折衷加調優,在側重於更新操作、點查和長範圍查詢的workload上效能較好;Leveling適用於查詢為主的workload;Tiering則適用於更新操作為主的workload。

論文通過建立代價模型將Lazy Leveling進行推廣,將其稱為Fluid LSM-Tree。假設有兩個引數,分別為Z和K。Z表示最後一層允許有最多Z個sorted run;其他層則允許有多個sorted run。K為限制引數,表示每層最多有K個sorted run。當每個sorted run的值達到t/k時會向下做compaction。通過這樣的方式,將Lazy Leveling進行泛化推廣,通過不同的workloads來調節引數Z和K。下表是將引數Z和K新增進去後的Fluid LSM-Tree的代價利用分析結果。

但這在實際操作中會遇到問題,即如何根據workloads來選取引數Z和K。論文采取搜尋方式去找到針對某個workload代價模型最小的引數K和Z。在真正實現時,我們對workload的認知相對有限,想要找到最優的引數K和Z會較為困難,且該模型總體比較複雜,實踐性有限。

RocksDB在某種意義上也採取了混合compaction策略。RocksDB的L0層的SST之間,K允許互相重疊,即允許多個sorted run。這實際上是Tiering策略,因為其落盤的Flush的效能更優。在L1-Ln層中採取Leveling策略,能夠更及時地清理過期資料,提高空間利用率。

RocksDB將每個sorted run切割為多個SST檔案,每個SST檔案都有大小閾值。其優點在於每次發生compaction時,只需要選取一個或者少量的SSTable與下層有KV重疊的SSTable進行合併,涉及到合併的有效資料量處於可控範圍。

SOSP 2017中有一篇名為PebblesDB的論文,提出了compaction Guard概念。每層分割為多個分片,分片間的分割稱之為compaction Guard,即一次compaction操作不會跨越該分界線,每個分界線內部SST之間允許重疊,可理解為Tiering compaction。這種做法最大的好處是可以保證資料項從第i層向第L+1層進行compaction時,寫入只有一次。因為它將原生的LSM-Tree進行分隔,形成FLSM結構。其壞處是讀效能會變差。因為找到對應分片後,分片內部如果存在多個SST,我們就不知道資料的真正存放位置,這時需要藉助Bloom過濾器來對每個SST進行探查,且即使使用Bloom過濾器,其發生假陽性的期望次數也會增加。

在RocksDB實踐過程中,我們發現它實際上提供了一個SST Partitioner的類,通過類可以在程式碼實現上保證分片,但與PebblesDB不同的是,其在分片內部保持SST不重疊,仍然採取Leveling策略。其好處是讀效能不變。雖然寫效能沒有得到提升,但更加適配於擴容場景,便於遷移及遷移後資料的物理刪除操作。

以TDSQL新敏態引擎架構為例。每層的儲存節點稱為TDstore,一個TDstore真實的資料儲存相當於維護一個LSM-Tree結構來儲存KV資料,再將KV資料按照區間劃分成不同Region。需要擴容時,我們會增加若干個儲存節點,再將原來節點上的部分Region遷移過去。Region遷移涉及到Region資料的遷移。如果採用前述的分割策略,將LSM-Tree的每一層基於Region邊界進行分割,將Region從相對完整的SST檔案中撈取出來,並插入到新增的TDstore儲存節點中。因為SST根據邊界進行分割,我們可以相對完整地將Region內部的資料遷移或刪除,因此Region資料遷移的效能會得到提升。

4. 降低讀放大

降低讀放大必須結合布隆過濾器。具體實現為:每層設定一個布隆過濾器,通過布隆過濾器進行過濾,減少無效讀磁碟block的次數。

下圖為前述的結論表。當資料查詢不存在即發生讀穿透時,發生假陽性的概率為e的-m/n次方。只要發生假陽性,就必須去讀資料塊,進行一次讀磁碟操作。在Leveling中,每層只有一個sorted run,查一次Bloom filter的概率為e的-m/n次方,根據期望公式推匯出的期望讀盤次數為L乘以e的-m/n次方。Tiering中則是T乘以L再乘以e的-m/n次方。假設點查時使用布隆過濾器進行過濾,每層都建立一個布隆過濾器即固定的bits團,讀效能就可得到提升。

2017年一篇名為Monkey的論文對布隆過濾器進行優化。在LSM-Tree不同層設定不同的布隆過濾器的bits,可以有效降低IO開銷,從而減少讀穿透的期望次數。其結論分析如下:第i層設定(a+b)×(L-i)的bits。由於最後一層資料量最大,只用一個bit來hash到布隆過濾器中。相比於前述公式,這可以減少一個L係數。因為Bloom filter要在記憶體中持有,而每層的bits不同,因此總體上降低了布隆過濾器的記憶體開銷。其點查的讀效能和整體Bloom filter的空間利用率都會得到提升。

SIGMOD 2021一篇名為Cuckoo的論文,採用布穀鳥過濾器代替布隆過濾器,從而優化讀效能。布隆過濾器的優化方式為:LSM-Tree的每層甚至每個SST檔案都會維護一個Bloom filter,查詢時需要從MemTable L0到Ln一層層向下探查,每次探查時先走一遍相應的布隆過濾器。該論文提出替代方案,不需要每層都維護一個布隆過濾器,而是選擇維護一個全域性的布穀鳥過濾器。先查全域性的布穀鳥過濾器,如果反饋不存在則表示資料不存在,如果反饋存在,考慮到可能發生假陽性,我們再去查資料檔案。

實現原理為:全域性的布穀鳥過濾器裡記錄了Level ID。如果在布穀鳥過濾器中有mash,則不需要繼續向下探查,可以直接找到其對應的Level ID,找到對應層、對應的sorted run去讀磁碟,看資料是否存在。布穀鳥過濾器對接兩部分:其hash map或簽名,再加上位置ID即level ID。

布穀鳥過濾器。我們通過兩次雜湊算出key所要插入的具體位置,所對應的兩個桶稱為b1和b2。b1直接拿key進行擦洗,b2不需要用key的原值,在算出簽名指紋後再做雜湊,因此每個key會有兩個可以存放的位置。

布穀鳥過濾器雜湊的資料插入過程如下:假設要插入item X,通過第一個雜湊計算出其位置是2,即b1等於2,第二個雜湊算出其位置是6。我們先將其放在第一個位置,如果可以放下則放下,如果放不下再看第二個位置即b2,如果b2沒有被佔則直接放下。如果b2也被佔則進行relocate,將原來的物件剔除,新插入的值再放到第二個位置。被剔除的值會放到它的兩個bucket中的另一個。如果另一個bucket也被佔據,被佔的元素會繼續被踢走,直到所有元素都有一個新的空白位置存放,則該過程結束。

Cuckoo論文中還需要記錄其簽名,用於確認key。如果簽名衝突則會造成假陽性。除此之外,還需要記錄其Level ID如下圖中的1、4、5,Level ID的作用是記錄該值位於哪個sorted run。通過Level ID可以在具體的sorted run裡查詢或更新。

5. 降低空間放大

RocksDB預設採用Leveling compaction,但也提供類似Tiering compaction的選項。如果選擇Leveling compaction,它會提供dynamic level size adaptation機制。理論分析表明,在最後一層資料充滿時,Leveling compaction的空間放大率不高,等於1/T。但在實踐中,最後一層的實際資料通常不會達到閾值。

假設每層容量放大比例為T,每層容量是T係數的等比數列。根據等比數列進行求和,我們發現最後一層的資料量佔絕大多數,等於總大小的(T-1)/T,前面所有層只佔總大小的1/T,此時冗餘資料量為前面所有層資料量與最後一層資料量之比,等於1/(T-1)。假設放大比率為10,閾值為1G,L1到L4的閾值分別為10G、100G、1000G。如果L4為最後一層,通過計算可知冗餘率為1.1。

實際情況下,最後一層的資料量一般不會達到閾值。在上述例子中的L4層,如果以靜態閾值為參照,當前L4的資料並沒有寫很多,可能只有200G資料,其放大率會比較差,前面存在大量冗餘資料。

因此RocksDB提出了動態調整每層容量閾值的機制。以下圖為例,當L0充滿時,其資料先不往L1寫,而是先往L5進行合併,這時L1至L4為空。

當L5的實際資料量達到閾值10M時,compaction L0往下落的目標層切到L4,並讓L4的閾值保持最初的閾值即10M,再將L5的閾值乘以放大係數T,L4與L5之間的容量閾值仍保持T倍的關係。假設L5的實際資料量達到11M,則L4的閾值為1.1M。

資料不斷往L4寫,L4再向L5進行compaction,L4會逐漸達到閾值。

L4達到閾值後,以此類推,當L3達到10M後,開啟L2作為L0的合併目標層。L3初始閾值為10M,這時L4擴大為100M,L5擴充為1000M。

在這種動態調整每層空間大小閾值的策略下,可以將資料冗餘量始終保持在1/(T-1)。在T=10時,其空間放大率不會超過1.1,這是比較理想的空間放大率。

降低空間放大還有其他的實踐措施。目前RocksDB已經實現key prefix encoding,可以讓相鄰的key共享一次,只存一次,從而節省10%的空間開銷。sequence ID garbage collection也是較好的優化措施。當一個key的sequence number小於最老的snapshot的sequence number,則它的sequence number可以改寫為0,而不影響資料的正確性。sequence number壓縮率的提高帶來了空間利用率的提高。

加壓縮也可以優化空間放大。目前RocksDB支援多種壓縮方法。第三方壓縮方法有LZ、Snappy等方法。我們還可以以SST檔案作為單元來設定不同的壓縮演算法,從而對KV資料進行壓縮。降低空間消耗的同時會增加讀開銷,壓縮過程中也會消耗一定的CPU資源,讀的過程中還要進行解壓,這就要求我們必須進行權衡。因此實踐的優化策略通常為:L0至L2層不壓縮,L3及以下使用較為輕量級的壓縮演算法,如Snappy、LZ,可以綜合考慮壓縮帶來的空間開銷受益和讀效能受益。最後一層採用壓縮率更大的壓縮演算法,一方面是因為資料較老,讀到的概率較低,另一方面是因為越往下的層的容量閾值越大,儲存的資料也越多,壓縮率高可以節省較大的空間開銷。

RocksDB也在Bloom filter方面進行優化實踐。Bloom filter本身會有相應的記憶體開銷,在記憶體有限的情況下,可以減少Bloom filter對記憶體的佔用。方法之一是最後一層資料不再建立bloom filter。因為最後一層的資料量較大,Bloom filter本身佔用的空間也比較大,會消耗較多記憶體,且考慮到最後一層的資料較老,被訪問的概率較小,因此在最後一層或最後幾層不再建立Bloom filter,在節省記憶體消耗的同時對讀效能影響小。

還有其他的優化方法,比如compaction job 併發。在RocksDB中,compaction在後臺非同步進行執行,執行過程中分為不同compaction job,如果兩個compaction job之間的SST集合互相不重疊,則這兩個compaction job可以實現現場併發。L0層的SST檔案通常互相重疊,RocksDB對此進行優化,提出subcompaction概念,將L0層有SST重疊的情況也做併發。IPDPS 2014的一篇論文還提出,compaction之間可以做流水線。

6. 結語

相比於傳統的B+樹,LSM-Tree結構具有更好的寫效能,可以將離散的隨機寫請求轉換成批量的順序寫操作。其效能衡量主要考慮三類因素:空間放大、讀放大和寫放大。LSM-Tree最初的設計理念是想通過空間放大和讀放大來換取寫放大的降低,從而達到極致的寫效能,但也需要做好三方面因素的權衡,可以從降低寫放大、降低讀放大、降低空間放大三方面來對LSM-Tree結構進行優化,從而提升資料庫效能。