LSM-Tree的儲存引擎的Compact機制

LSM-Tree

LSM-Tree透過追加寫替代覆蓋寫的方式提高了寫入效率，對於OLTP型別的資料庫產品非常友好，在資料庫的單機儲存引擎中LSM-Tree應用廣泛。

採用追加寫的儲存引擎天然的優勢在於：

充分利用磁碟順序寫比隨機寫效率高的優勢

天然的多版本機制，使得快照等多版本機制變得簡單

更容易對資料進行改造：壓縮/EC/冷熱分離。。。

資料保護更容易

。。。

追加寫的劣勢在於

儲存系統會產生垃圾，需要額外的邏輯去回收垃圾

需要預留OP空間，降低了售賣比例

回收空間會帶來額外的資源佔用和資源爭搶

LSM-Tree可以說是優劣分明的資料組織結構，相比較原地寫儲存系統，LSM的追加寫能夠為儲存系統帶來更多的想象空間，而這些想象空間正是compact過程的神秘之處。

在儲存系統中寫的最佳化通常是需要從系統架構上開刀，而讀最佳化則可以從cache等策略上提高效率，這也是為什麼LSM-Tree比較流行的另一個原因。LSM-Tree basic

Compact

最初compact的目標是為了提高讀效能，因為追加寫的方式對寫入效能是有明顯優勢的，但是由於存在歷史版本資料，讀可能需要多次的查詢檔案才能完成，因此讀的放大非常嚴重，而透過compact資料，將連續有效資料聚集在少數檔案中，讀需要查詢的檔案資料量大大減少，從而提高了讀效能。

而Compact本身又會對儲存引擎的寫放大、吞吐、範圍查詢、空間放大、單機售賣能力等方面有非常重要的影響，所以對於不同的業務型別，需要的compact策略偏重各不相同。

因此，LSM-Tree的comapct設計彈性非常大，目前也沒有量化的方式去衡量compact，［Constructing and Analyzing the LSM Compaction Design Space］ 這篇論文中對compact進行了量化，將compact抽象為4個環節：

compact觸發時機

compact後資料佈局

compact粒度

哪些資料需要compact

compact機制的tradeoff

compact是透過犧牲寫放大的方式來解決系統的讀放大和空間放大，在compact時所涉及到的所有IO操作都是系統內部的非使用者IO，這部分IO會佔用網絡卡流量、CPU、SSD儲存空間，所以compact需要在寫放大、讀放大、空間放大這三個指標間進行權衡。

SA & RA & WA

Space Amplification（SA）

空間放大指的是使用者實際的資料量S，在儲存系統中真正佔用的物理儲存空間P，P/S即為空間放大。

由於追加寫，使用者資料在底層會存在多個版本，歷史版本佔用儲存空間，造成了空間放大。

SA is defined as the ratio between the size of logically invalidated entries and the size of the unique entries in the tree。

Read Amplification（RA）

讀放大是使用者為了讀取大小為S的資料時，真正從儲存系統中讀取的資料量P，P/S即為讀放大。

由於底層多檔案儲存使用者資料，且追加寫的模式會導致資料有新舊版本同時存在，為了讀取最新的有效資料，讀請求需要查詢多個檔案，找最新的資料。

RA is the ratio between the total number of disk pages read for point lookups and the pages that should be read ideally

Write Amplification（WA）

使用者資料在儲存系統中被搬移的次數。

the number of times an entry is （re-）written without any modifications to disk during its lifetime。

tradeoff

在compact過程中往往無法使SA、RA、WA都達到最優值，至少需要在一個指標上讓步才能滿足其他指標達到較優狀態。

舉個例子：為了使SA和RA達到最小，我們需要不停的進行compact，compact會增加資料寫入頻率，使用者側寫入的資料一直被重寫到儲存系統，WA會很高。

通常compact會幫助系統回收儲存空間，降低系統儲存水位，騰出空間給使用者，但是頻繁的compact需要佔用機器頻寬、CPU等資源，同樣會影響到系統的售賣能力，所以選擇合適的compact策略對於系統至關重要，不僅影響系統性能，同樣也會影響到系統的售賣能力。

在探討compact機制之前，先看下LSM-Tree的兩種實現機制：KV融合與KV分離。

LSM-Tree的KV融合與分離

所謂KV融合與分離具體指的是在LSM-Tree儲存引擎中儲存資料的key與value是儲存在一起，還是分開儲存。

KV融合

典型的儲存引擎是LevelDB & RocksDB

儲存引擎將資料的索引key及value儲存在一個檔案中，且每個為了保證查詢效率，每個持久化檔案的資料是按照key進行排序的，典型的持久化資料組織結構是SSTable（sorted string table）。

這種資料組織方式下，索引排序和垃圾回收是繫結在一起的。

KV分離

典型的儲存引擎是Wisckey和tikv的titan，僅對索引使用LSM-Tree的組織方式，將索引排序和垃圾回收兩個邏輯拆分。

KV融合的場景需要消耗較大的頻寬來對資料進行compact，獲取連續的資料，方便順序讀。這種場景在HDD背景下比較實用，HDD的順序讀寫比隨機讀寫的效能好很多。但是在SSD場景下，隨機讀和順序讀的效能差異並沒有那麼大，所以沒有必要消耗磁碟讀寫頻寬做compact重新組織資料，compact的頻率降低了，也就是對應的WA降低了，可以把更多頻寬放給業務，實現利益最大化。

另外一方面，SSD相比較HDD其壽命與NAND的擦寫頻率有很大關係，如果頻繁的進行compact，會導致SSD的壽命縮短。

KV分離帶來的劣勢在於小隨機寫大順序讀場景，由於value不會頻繁compact，導致其效能不如KV融合時頻繁compact的方式，但是這種讀寫模型在真實場景中還是比較少的。

WiscKey是LSM儲存引擎KV分離的代表，透過將key和value分開儲存的方式，實現只對key的LSM組織方式，value就儲存在appendlog中，這樣就可以只對key進行compact即可，對於value log的垃圾，在合適的時間進行垃圾回收。

key的組織方式有多種型別可以選，LSM-Tree或者BTree都是一種選擇，LSM-Tree可以更方便的進行快照等處理。

KV融合儲存引擎Compact策略

前面已經提到，一個compact策略可以抽象為4個環節，每個環節可以有不同的策略，然後不同的環節不同的策略組合出不同的compact機制。在不同場景不同業務需求下如何選取每個環節的策略呢？

comapct觸發機制（trigger）

在什麼情況下可以觸發一個comapct任務，在KV融合的儲存引擎中，通常是按照層級劃分資料，就像levelDB，這種儲存引擎通常會給每個level設定一個容量閾值或者檔案數量閾值，當達到閾值後會觸發向下一層的compact。或者會按照某一層儲存的runs數量確定是否向下comapct。對於KV儲存引擎，通常還會根據SA閾值來觸發。

compact後的資料組織方式（data layout）

在KV融合的儲存引擎中，主要有兩種型別的layout：tiering 和 leveling，以及這兩種結合的layout，而對於KV分離的儲存引擎中通常是普通的flatlogfile。

leveling指的是每一層只有一個大的runs，每次都會對一整個層進行compact

tiering則是對每層的runs進行了切分，這樣comapct可以只在部分runs進行，降低了寫放大。

通常KV融合的儲存引擎會有明確的層級概念，對於KV分離的儲存引擎其value是沒有明確的層級概念，其compact的目標也主要是回收空間，排序則是隻針對其key。

compact粒度（compact granularity）

在compact粒度選擇上可以有檔案粒度的，KV分離通常都是檔案粒度，對於KV融合的引擎也有按照層級粒度。最小的粒度可以是runs級別。粒度越大需要的吞吐也就越大，但是compact結束之後垃圾也少，空間放大較小。工業實現中無論是KV分離還是KV融合，通常的compact粒度都不會太大，通常長期不斷的進行compact來回收垃圾，這種方式對於使用者延時也更友好。

compact目標資料選取策略（data movement）

對於非全量compact模式，我們要面臨的一個問題是，如何選取需要進行compact的資料。典型的按照檔案粒度的compact方式中，哪些檔案需要被選取用來compact是compact非常重要的一個環節。比如為了降低叢集的空間放大，那麼選取較多垃圾的檔案通常收益最大，又或者當前資料碎片嚴重，那麼選取碎片較嚴重的檔案進行compact，對於碎片整理的收益最大。對於有冷熱資料要求的場景，按照檔案冷熱程度來確定目標檔案收益更大。

對於一個儲存引擎，上面四個步驟構成了一整個compact任務，只要其中一個環節有變化，整個compact的效果也會隨之變化，在不同的效能需求下，compact策略如何選擇，［1］中做了一組實驗。

上述表格中10中不同型別的compact策略在效能上的不同表現，在不同效能緯度下的優劣： 因為LSM-Tree的寫都是追加，所以不同的compact策略對寫效能幾乎沒有影響，效能基本一致。

可以看出：

寫效能由於都是追加寫，所以基本不受compact影響，但是compact對CPU和網路頻寬資源的使用，會影響到寫長尾延時，tier和full compact策略的長尾寫延時方面不夠好。

Full compact策略在空間放大、讀放大以及讀效能方面都是比較有優勢的，但是頻繁的compact使寫放大非常高，另外頻繁compact也佔用了很多的網路頻寬，且compact延時較高，同樣會時系統的長尾延時不夠好。

Tier策略有較好的寫放大控制能力，但是讀放大和長尾寫延時方面不夠好，同時compact的latency波動範圍較大。

除了Tier和Full兩種策略外，其他幾種compact策略在各個方面表現相對中庸。

KV分離儲存引擎Compact策略

與KV融合的儲存引擎區別在於KV分離的儲存引擎只需要對以LSM組織的key進行compact，對應value並不需要進行排序。同時，由於key相比較value。其資料量通常差多個量級，因此在key這個維度的compact帶來的空間放大或者寫放大可以暫且忽略不計。

KV分離後對於寫放大有直接性的最佳化，但是value中的垃圾仍然需要回收，所以，對於kv分離的儲存引擎，需要進行垃圾回收來降低空間放大，垃圾回收過程肯定會帶來寫放大的增加，所以，在kv分離的儲存系統中，理想的compact演算法應該是在考慮寫放大和空間放大的基礎上，用最少的流量來回收最多的垃圾。

titan

wisckey2016年在fast會議上發表論文，提出KV分離的儲存引擎。目前在工業實現中，pingcap的titan借鑑了wisckey的理論實現了kv分離儲存引擎。

titan儲存引擎同wisckey一樣使用的線上gc valuelog的方式，gc和儲存引擎在同一個程序中，其value的compact策略細分如下，透過適當的放開空間放大的方式來減少寫流量。

compact觸發機制

當檔案的垃圾比例超出閾值

當檔案的垃圾資料量總和超出閾值

compact後資料組織方式

資料寫入flag log file（Blobfile），無嚴格的層級概念

compact粒度

檔案粒度

compact的目標資料選取策略

會記錄每個blobfile的垃圾比，垃圾回收時會按照垃圾比例大小排序回收對應的blobfile。

titan使用的是線上compact策略，一臺機器的網路頻寬、CPU資源如何在使用者和後臺compact分配這個資訊還不得而知，同時，titan的compact觸發與叢集水位、空間放大的關係目前沒有相關介紹。

總結

LSM-Tree的kv分離模式在wisckey16年發表論文後，在工業界已經開始有實踐，這種KV分離方式對於原來的kv融合模式的compact有較大的差異，專注於value的gc既可以在減少寫放大的同時專注於對value的最佳化，比如冷熱分離、壓縮、EC等。從compact角度來看，需要結合儲存整叢集緯度（頻寬配比、儲存水位、整體垃圾比）來判斷如何用更少的流量回收更多的空間仍然有很大的研究空間。

reference：

Constructing and Analyzing the LSM Compaction Design Space

WiscKey： Separating Keys from Values in SSD-conscious Storage

https：//

pingcap。com/zh/blog/tit

an-design-and-implementation