compaction策略
compaction的主要作用是數據的gc和歸併排序，是lsm-tree系統正常運轉必須要做的操作，但是compaction任務運行期間會帶來很大的資源開銷，壓縮/解壓縮、數據拷貝和compare消耗大量cpu，讀寫數據引起disk I/O。compaction策略約束了lsm-tree的形狀，決定哪些文件需要合併、任務的大小和觸發的條件，不同的策略對讀寫放大、空間放大和臨時空間的大小有不同的影響，一般系統會支持不同的策略並配有多個調整參數，可根據不同的應用場景選取更合適的方式。
基礎概念
讀放大
每次讀請求帶來的讀盤次數
寫放大
每寫1byte數據帶來n bytes的數據寫盤，寫放大為n。本質上寫放大需要跟全局有序做權衡，對序要求越高的系統寫放大就會越嚴重，B-Tree系列是隨時有序的代表，寫放大也更為嚴重，而LSM-Tree將序延遲到後臺compaction處理，減少了寫入放大。再近一步優化和權衡，lsm-tree系統下不同的compaction策略也會帶來不同的放大結果。
空間放大
所佔空間大小/實際數據量大小，空間放大主要與未回收的過期數據量(old version/deleted entries)相關。傳統數據庫使用廉價磁盤，空間放大並未作為主要考慮，在以ssd為主流存儲介質的今天，節省成本是不得不做的事情。
臨時空間
compaction任務運行時需要臨時空間，compaction完成後舊數據才可以刪除。與compaction任務的拆分粒度相關。
sstable
ordered string table
有些系統使用了不同的名字，都是類似的含義，這裡介紹策略時統一使用sstable來描述。
Size-tired compaction
size-tired適合write-intensive workload，有較低的寫放大，缺點是讀放大和空間放大較高。簡單看一下這個策略的實現，如下圖所示(圖來自scylla)，memtable週期地刷到sstable，可以看作每層之中有多個ordered runs，最底層是最大的一層，tiered儘量使得相同層的sstable/run大小相近，當一層的數據size達限制後將整層合併並flush到下一層成為一個更大的sstable，一直合併直到某一層數量未達到限制停止。
tired的缺點是空間放大和讀放大:
- 對於讀操作，這裡忽略cache和bloom filter等上層優化，大部分的點讀按數據量來推測是會落在最大一層的，而range查詢需要合併所有層的結果，runs越多，讀放大越嚴重。Dostoevsky這篇論文詳細分析了point lookup(考慮bloom filter)、short和long range lookup的I/O cost，具體可參照下文Dostoevsky部分。
- 如果重複的寫同一批數據，可能是更新或者刪除，假設相鄰level的size比為T，每個level包含的run數達到T時即觸發整層的合併，空間放大為O(T)，實際運行中還要考慮臨時空間的使用，需要預留出這部分空間。在scylla的測試中，T為4的設定中1.2g數據量最大使用空間達到了9.3g，可見tiered策略對空間的要求是比較苛刻的。
leveled compaction
leveled策略可以減小空間放大和讀放大。
LSM-Tree由多個level組成，每個level的size維持上一個level的T倍，當所有相鄰level的size比T是相同值的時候寫放大最小。
如下這張圖所示，leveled每層由多個sstable組成一個有序的的run，sstables之間互相也保持有序的關係，每層的數據size到達上限後與下一層的run merge。這種方式將level的多個run降為一個，減小了讀放大和空間放大，小sstable的方式提供了精細化任務拆分和控制的條件，控制任務大小也就是控制臨時空間的大小。
在相鄰level數據量比設定為10的場景下，在largest level數據量足夠滿的情況下，worst-case:其它level都是update最大層的entries，其它level總數據量/bottom數據量大約是0.11，空間放大為11%。即便在largest level不足夠滿，未能達到數據量比例時，最差也只有1倍的空間放大，相比tiered的T倍(相鄰level size比)空間放大，leveled就比較有優勢了，適合讀多寫少的場景。
leveled策略的問題是寫放大，同樣分析相鄰level數據量比為10的設定下worst-case，level a層的數據與level a+1層的所有數據都有交疊，level a向下合併時涉及level a+1全量的數據，共有原數據11倍大小的數據量被寫盤，寫放大為tired的11倍。這是理論上最差的情況，隨機寫非常多的場景會更接近這個數值。一般情況新寫入的數據短時間再次被更新的概率會比較大，符合時間局部性，這種情況由於舊版本數據被合併掉總數據量幾乎不變，不會觸發向下合併。
Hybrid
tiered和leveled混合的方式。很多系統使用兩者混合的方式以取得讀寫放大、空間放大之間進一步的權衡。相比tiered可以獲得更少的空間放大和讀放大，相比leveled可以有更少的寫放大。
time series
一般time-series數據的特點如下：
- 索引key和寫入時間相關
- 數據按照時間順序寫入，只有少量數據不遵守這個順序
- 數據只能通過TTL或者刪除整個partion來刪除
- 數據寫入的速度幾乎是恆定的
- 數據查詢通常是在一個特定的partition中的，例如"values from the last hour/day/week"
因此針對這些特點，很多系統引入了特定的compaction策略來提升性能，每個sstable有開始和結束時間標記，挑選sstable時按照時間range，相似range的sstable逐漸合併，越老的sstable range越大，sstable之間幾乎沒有時間range交疊，這樣應對特定時間filter的查詢能夠有效地挑選對應的sstables。
key-value stores in industry
每個系統都是圍繞著"how and when"這個主旨來選擇策略和調度機制的，如何挑選文件，由什麼條件觸發。
偏向寫優化的系統，bigtable、hbase、canssdra。偏向空間優化和讀優化的系統，rocksdb。
rocksdb
rocksdb在compaction機制上支持的方式比較多，也做了很多的優化工作，除了經典的tiered和leveled之外，rocksdb在兩者基礎之上可以有兩種混合方式的表現，定義為leveled-N和tiered+leveled。
leveled
rocksdb的leveled compaction實現實際上是結合了tiered，level0是tiered的實現方式，除L0層外其它都是leveled。level0的每個run由一次flush memtables得來，多個run之間範圍有交疊，其它levels由多個sstables組成一個有序的run。這種結合方式的好處一是減小了寫入放大，二是可以在寫入負載較高時快速釋放memtable以緩解內存的壓力。leveled是rocksdb默認的compaction方式。
tiered(Universal)
tiered在最大層維護全量的N份副本會帶來N倍的空間放大，rocksdb增加了參數來限制最差的空間放大，最多隻允許最大層有K個runs，K的範圍是2～N。
tiered在rocksdb中是依賴Universal Compaction來實現的，用戶使用leveled無法應對高寫入的速率時可以嘗試使用Universal Style。
leveled-n
leveled-n是leveled優化了寫放大的實現方式，允許每層有多個有序的runs，compaction時merge L-1層的所有runs和Ln的一個sort run，Dostoevsky中提出的lazying compaction也是類似的思想，本質上是通過調整最大層run的數量和相鄰level的size比T來平衡讀寫放大和空間放大。
tiered+leveled
tiered+leveled屬於Hybrid方式，允許Lk層是tiered方式，Ln層是leveled方式(n > k)，rocksdb在這種方式的表現形式是memtable會保留多個和level0層允許有多個run，可以看作內存層和level0層是tiered，1-n層是leveled，不過內存中不做合併，可能只將level 0標為tiered更合適。
scylla
scylla支持tired、leveled compaction策略，默認為Size-tired compaction，面向寫優化場景。並增加了size-tired優化版本incremental compaction和針對時間特定場景的date-tired compaction。
incremental compaction(IC)
針對size-tired臨時空間放大問題提出的優化版本，原始的size-tired中每個sstable是一個有序的文件，多個sstable合併成為更大的sstable，至少需要預留50%的臨時空間。IC將sstable分為多個分片(默認1G)，以分片為合併單位增量地進行，合併完成的分片可以將舊數據的空間釋放出來，降低了臨時空間放大。
Time-window compaction(TWCS)
scylla最開始支持了date-tiered，最初由canssdra實現並使用，TWCS是date-tiered的替換版本，同一時間窗口的sstables按照tiered策略合併，不同時間窗口的sstable不會在一起合併。都屬於time series，time場景下優化讀性能。
hbase
hbase的compaction類型分為minor和major兩種，與bigtable類似，minor挑選部分store files合併，數據量少而頻繁，不回收多版本數據(避免處理一些相同key的問題)。major將所有store files合併為一個，major涉及數據量比較大，一般很久才會觸發(天級別)或者手動觸發，major會處理過期數據。
hbase的store files與sstable是類似的概念，hbase弱化了層次的概念，每個file是一個有序的run，hbase在0.94和0.96兩個版本中分別提出兩種挑選合併文件的策略:RatioBasedCompactionPolicy，ExploringCompactionPolicy。RatioBased從老到新掃描未在合併隊列中的store files直到滿足合併大小(依賴ratio參數)，總是優先合併老的store files，Exploring會掃描所有的未在合併隊列中的store files，在多個滿足條件(ratio)的集合中選擇總size最小的，以儘可能減少io的消耗。分類上這兩種策略都屬於tiered compaction。hbase也支持date-tiered compaction。
在hbase-2.0.0中，提出了in-memory compaction的新特性。本質上是為了減少flush的頻率進而減少compaction，減少寫放大，適合重複更新熱點數據的場景，過期版本數據可以在內存中就被消除。對於大多都是unique的寫場景反而會帶來性能下降，因為compaction要消耗cpu資源。
挑戰
compaction任務執行對性能造成顯著影響，主要表現在兩方面：compaction過程中對io/cpu資源的消耗，compaction完成時造成批量的cache失效。另外一個在lsm-tree這種結構下存在的比較棘手的問題是需要delete的記錄不能立刻被消除，要消除的記錄可能會存在每一層，需要通過全量的compaction才能消除，這對資源是非常大的消耗。
資源消耗
任務運行時的壓縮/解壓縮、拷貝、compare消耗cpu資源，讀寫數據消耗i/o資源。
cache失效
compaction完成生效時舊數據文件失效，cache中的數據同樣也會失效，compaction任務越大數據越熱，cache失效越嚴重。cache miss率升高引起大量的讀i/o，讀i/o請求與compaction任務執行時讀文件請求之間進一步爭搶資源，加劇讀性能的降低。
delete entries
- 在lsm-tree中，delete/update都是寫一條新的記錄，delete記錄一般使用一位flag來區分，delete記錄堆積會帶來更多的空間放大和寫放大，更為嚴重的是在range delete場景下，讀性能會受到很大影響。而目前系統消除delete的方式需要觸發全量的compaction，帶來過多的資源消耗，這是一種非常貴的解決方式。rocksdb實現了根據delete 記錄的分佈來挑選文件來合併的優化方式，以達到消除delete和相關記錄的目的，這樣可以避免一些多餘的數據合併，是一種優化手段，但是對於delete廣泛分佈在各個文件中的情況依然無法避免全量的compaction。
- 對統計信息的影響，如果是用在關係型數據庫中，例如myrocks，會導致統計信息不準影響sql優化器的決策。
- Lethe論文中還提到帶來侵犯隱私的風險，用戶要求刪除的數據沒有在一定時間內物理刪除，甚至在用戶註銷後數據還存在，會引起法律風險。
學術研究
分佈式kv store的compaction管理
這篇論文(參考1)提出在分佈式kv store中，使用offload compaction到單獨的server和增量cache回填的方式來解決compaction對資源消耗和cache失效的問題。實現和評估基於hbase，hbase是由bigtable衍生，基本架構與bigtable非常相似，使用zookeeper保持一致性，按照key range將數據水平切分到多個region server，數據持久化在hdfs中，region server中維護memstore接收新的數據寫入，block cache緩存hdfs中的數據文件。
offload compaction
在hbase的架構中，增加兩個新的組件：compaction manager，compaction servers集合。compaction server可動態增加或者減少，與region server一樣從hdfs中讀取數據，合併完成再寫入hdfs。compaction manager與hbase master類似，管理compaction server的集合和從region server到compaction server的映射。region server的compaction任務offload到compaction server上，接收合併完的數據用於緩存的預熱。
remote cache
region server中的compaction offload到remote server後，compaction的數據可以同步填充到remote server的內存中，對於這部分數據的訪問請求可以選擇訪問本地的disk和遠程server的內存，其實是disk i/o與網絡i/o之間的比對，測試效果一般，沒有很明顯的改善。
smart cache
訪問遠程cache並沒有達到很好的效果，因此作者又提出使用遠程cache增量預熱本地cache的方式。按照key range增量地填充並淘汰對應key range的舊數據，這樣不會造成大批量的原本在caceh中的數據被淘汰。對於請求的數據，要麼落在舊的cache中，要麼落在新填充的cache中，很小的概率是屬於剛被淘汰而還未被填充的數據範圍。因此這種方式效果測試很好，幾乎沒有cache miss。
分佈式場景下可以從外部方式來解決compaction帶來的問題，這是單機系統做不到的，像smart cache這種解決方式，在單機中無法同時在內存中保存新舊兩份數據，避免不了性能的抖動，而在分佈式場景下，利用遠程的內存保存新的數據並一點點地替換掉本地的cache，而compaction前後的數據對於讀請求返回的是一致的結果，因此這種方式可以保證正確性，也達到了很好的效果。
PebblesDB
這篇論文(參考2)提出了一種LSM Tree的改良結構叫做FLSM，主要目的是通過減少compaction過程中的rewrite來減小寫放大，並使用FLSM構建了高性能kv store，叫做PebblesDB。FLSM的設計思想來源於skip list和lsm-tree的結合，寫放大的本質來源於compaction過程中數據的rewrite，寫放大會減少像SSD這種有擦寫次數限制設備的壽命，增大存儲代價，降低寫吞吐。FLSM通過加入guard將數據分成互不相交的單元，每個單元包含多個range交疊的sstables，在將level i合併到level i+1時，相比於重寫level i+1的sstables，FLSM只是將根據guards新劃分的sstable放到level i+1，並不會與level i+1的sstables做merge。這不僅減小了寫放大，也加快了compaction的速度。但是會對讀產生一定影響，作者也提出了優化讀的方式：Seek-Based Compaction用seek()次數作為觸發compaction的條件，減少熱guard內的sstabels的數量，從而減少read的開銷；Parallel Seeks，使用多個線程並行search sstables，每個線程讀一個sstable，再將結果merge起來。這樣即使在一個guard中有多個sstables，也只需要付出一小部分overhead。
guards的信息保存在內存中，與LSM的元信息一樣，寫wal日誌，crash後可以通過manifest日誌保證數據不丟失。
用guard來分區和seek-based compaction是比較新穎的點，FLSM的確可以減小寫放大，但帶來的read問題我認為並沒有解決，並行seek受限太多。seek-based compaction感覺倒是可以繼續優化的一個點，讀請求很多時候反映了數據的冷熱以及需要合併的緊迫程度，這部分如果能夠更精準的判斷將對於"做有效的合併"帶來很大幫助。
Dostoevsky
這篇論文(參考3)詳細地分析了各種操作在tired和leveled不同策略下的i/o複雜度，使用了level num、相鄰level size比、entry數量、buffer size等一系列相關變量推導出不同操作具體的I/O代價公式和空間放大，對於point read還考慮了bloom filter帶來的影響，range query分了short和long兩種來分析。並且提出了優化策略lazying leveling，是tiering和leveling的結合體，最大一層使用leveling其它層使用tiering，lazying適合包含update、point lookup和long range lookup的混合負載，tiering適合大多為update的負載，leveling適合大多為lookup的負載。通過控制merge頻率在tiering、leveling和lazying leveling幾種不同策略下轉換以適應不同的workload，稱作fluid LSM((類似rocksdb的leveled-n))，並提出Dostoevsky，在執行期間動態計算最優配置以到達最大吞吐。
從作者的分析中可以看出compaction這個機制的複雜程度，要使用一套通用機制在不同場景下消耗最少的資源帶來最好的性能基本是不可能的，實際工業界實現中需要考慮更多的因素(cache、delete、任務拆分粒度、複用技術等)，因此大部分系統使用多種策略多個參數用以適配不同場景。
詳細解析
一點思考
compaction的代價在單機中是不可避免的，但不同的策略會帶來不同的讀寫和空間放大，也是近幾年學術上關於lsm-tree系統研究的一個方向，重點在於如何從策略選擇上優化worst-case。大多數系統支持多種compaction實現策略，通過適配多種不同參數以滿足不同業務場景下的需求，這也是不斷完善的一個過程，遇到問題解決問題，大多數時候可以work，但不可避免的會遇到複雜場景、多種混合負載下的極端問題，依賴調參數或者人工操作compaction來解決總是不那麼優雅和及時。在分佈式場景下可以將策略當作黑盒，很多問題可以依靠外部資源來化解，更多的是依賴調度策略。
在真實應用中，大多數業務負載並不會持續讓系統處於worst-case中，而大費周折去解決worst-case是否不是那麼必要？例如選擇一種"繞"的方式來讓系統處於更平穩的狀態，低峰期承擔更多任務以卸掉低level的重擔，空車以迎接高峰時期的洪荒之力，當然這也只是一種理想狀態，事實總比預想要複雜，總是不會完全按照預期的走向發展，這使得我們沒有辦法按照一些規則或者配置來做預先處理。可以想到需要引入調度控制，重心由合併策略轉向調度策略，根據負載曲線調度不同任務以達到不同時期對資源的需求，這或許是更為複雜的一個話題，也希望會有更多這個方向上的研究和探索出現。