帶你全面瞭解compaction 的13個問題

語言: CN / TW / HK

作者: h5n1 原文來源:https://tidb.net/blog/eedf77ff

1 概述

       TiKV 底層儲存引擎使用 RocksDB ,RocksDB 是一個基於 LSM tree 的單機嵌入式資料庫, 對於LSM Tree 來說compaction是個非常重要的操作,本文對TiKV中涉及的compaction相關內容進行了整理總結。

2 為什麼需要 compaction ?

                                     ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656491850788.png) 

       LSM Tree 通過將所有的資料修改操作轉換為追加寫方式:對於  insert  直接寫入新的kv,對於 update 則寫入修改後的kv,對於 delete 則寫入一條 tombstone 標記刪除的記錄。通過這種方式將磁碟的隨機寫入轉換為順序寫從而提高了寫入效能,但不能進行 in-place 更新,由此帶來了以下問題:

1、 大量的冗餘和無效資料佔用磁碟空間,造成空間放大。

2、 讀取資料時如果記憶體中沒有的話,需要從L0層開始進行查詢sst file,造成讀放大。

       因此通過 compaction 操作將資料下層進行合併、清理已標記刪除的資料降低空間放大、讀放大的影響。但是compaction 又帶來了寫放大的問題,因此不同的資料庫根據需要使用不同的compact 策略,以達到讀、寫、空間最優的平衡。Compaction屬於資源密集型操作,需要讀寫大量的資料並進行排序,消耗較多的IO、CPU資源。

3 Compaction做什麼?

       RocksDB的compaction 包含2方面:一是memtable寫滿後flush到磁碟,這是一種特殊的compacttion,也稱為minor compaction。二是從L0 層開始往下層合併資料,也被稱為major compaction,也是常說的compaction。

       Compaction 實際上就是一個歸併排序的過程,將Ln層寫入Ln+1層,過濾掉已經delete的資料,實現資料物理刪除。其主要過程:

       1、 準備:根據一定條件和優先順序等從Ln/Ln+1層選擇需要合併的sst檔案,確定需要處理的key範圍。

    2、處理:將讀到key value資料,進行合併、排序,處理不同型別的key的操作。

       3、寫入:將排序好的資料寫入到Ln+1層sst檔案,更新元資料資訊。

4 Compaction有哪些常見演算法?

       以下幾種演算法是學術性的理論演算法,不同的資料庫在具體實現時會有優化調整

  • Classic Leveled

       由O'Neil 在  LSM tree 論文中第一次提出,該演算法中每層只有一個Sorted-Run(每個sorted-run 是一組有序的資料集合) , 以分割槽方式包含在多個檔案內,每一層大小是上一層的固定倍數(叫fanout)。合併時使用all-to-all方式, 每次都將Ln的所有資料合併到Ln+1層,並將Ln+1層重寫,會讀取Ln+1層所有資料。 RocskDB使用some-to-some方式每次合併時只讀寫部分資料。

  • Leveled-N

       和上面Classic Leveled 類似,不過每層可以有N個Rorted-Run,每層的資料不是完全有序的。

  • Tiered

       Tiered 方式同樣每層可以包含多個Sorted-Run ,Ln 層所有的資料向下合併到Ln+1層新的Sorted-Run,不需要讀取Ln+1層原有的資料。Tiered方式能夠最大的減少寫放大,提升寫入效能。

  • FIFO

       只有1層,寫放大最小,每次compaction刪除最老的檔案,適合於帶時間序列的資料。

       RocksDB中compaction 演算法支援Leveled compaction、Universal compaction、FIFO compaction。 對於Leveled compaction實際上是 tiered+leveled組合方式(後續描述均為此方式),Universal compaction 即 tiered compaction。

       RocksDB的leveled compaction中 level 0包含有多個sorted-run,有多個sst檔案,之間存在資料重疊,在compaction時將所有L0檔案合併到L1層。對於L1-Lmax 層,每一層都是一個有序的Rorted-Run,包含有多個sst file。在進行讀取時首先使用二分查詢可能包含資料的檔案,然後在檔案內使用二分查詢需要的資料。

                        ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656491883663.png)

       在TiKV 內可使用compaction-style引數修改每個CF的compaction 演算法,支援的選項值包括0- level compaction(預設)、1-universal compaction 、2- FIFO,而Level總層數可通過引數num-levels控制,預設為7層。

5 ColumnFamily和SST file的關係?

       RocksDB內使用Column Family(CF) 來進行資料的邏輯隔離,CF內可以使用不同的key,每個CF使用不同的memtable和sst檔案,所有的 CF 共享WAL、Manifest。每個 CF 的memtable flush時都會切換WAL,其他的CF也開始使用新的WAL,舊的WAL要保證裡面所有CF的資料都被flush後才能刪除。   

       在RocskDB內每個Column Family都分配了一個ID,在SST檔案有Column Family ID,預設L1層sst file的大小由引數target-file-size-base決定,L2-Lmax的sst檔案大小為target-file-size-base*target_file_size_multiplier (預設為1), TiDB內支援引數target-file-size-base,預設為8M。

       經過CF的邏輯劃分後類似結構如下:

                                ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656491897779.png)

       在TiDB中存在2個rocksdb例項,一個用於儲存實際的使用者資料,稱為kv db,另一個用於儲存raft log,叫做raft db(6.1.0版本開始raft db 預設被raft egine取代)。kv db 有4個CF:default、write、lock、raft ,raft db只有一個default CF。

6 什麼時候觸發compaction ?

       RocksDB的 compaction 由後臺執行緒 BGWorkCompaction 進行排程。該執行緒的觸發一般有手動觸發和自動觸發兩種情況:

  • 手動觸發

       RocksDB 提供CompactRange、CompactFiles等介面允許使用者手動compaction,從而使使用者能根據自己的場景觸發compaction。

  • 自動觸發

       當WAL切換或memtable被寫滿後會呼叫檢查是否需要進行compaction,具體如下:

1、 Memtable達到write-buffer-size(TiKV內預設128M)引數大小時會轉換為immtuable memtable 等待flush到磁碟,並開啟一個新的memtable用於寫入。

2、 Memtable flush 時會導致WAL 切換,同時當 WAL 大小達到max-total-wal-size(TiKV預設4G) 時也會進行切換。

3、 當達到如下條件時則排程compaction執行緒執行compact操作。

(1)    sst檔案設定以下標記時:達到ttl時間、達到定期compaction時間、已被標記為compaction等。

(2)    遍歷所有level,計算每層的score,如果score>1,則需要compaction,當有多個level都達到觸發條件時,會選擇score最大的level先進行compact。score計算方法如下:

L0層:當前L0 sst檔案數和level0-file-num-compaction-trigger引數比例。

L1層:Ln層總大小(不包含正在compact的檔案)和max-bytes-for-level-base*max-bytes-for-level-multiplier^(N-1)的比例。

       除了上面的條件觸發方式外,RocksDB使用BottomMost Recompaction對最底層的delete記錄進行再次檢查和清理:當某個操作執行時其快照引用的檔案位於最底層時,如果包含很多delete則這些delete的資料不能通過正常的compact方式清理掉,因此在操作執行完後release snapshot時重新檢查bottommost level ,確定哪些檔案可以被compact,comapct後生成的檔案仍位於最底層。

       自動compaction可通過disable-auto-compactions 引數關閉,從而可以讓使用者只使用自定義的compaction 策略,TiKV內同樣支援該引數設定。Compaction 的觸發原因可通過監控TiKV Detail –> RocksDB KV/ RocksDB raft -> Compaction reason檢視。

                        ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656491922713.png)

 

7 Compaction時選擇那些檔案?

       當選定需要compaction的Ln層後便需要決定需要向下層合併哪些檔案,在選擇需要合併的檔案時主要考慮2方面:檔案優先順序和範圍邊界。

  • 檔案優先順序

       選擇優先順序最高的檔案進行合併,如果該檔案正被其他執行緒進行合併,則按照優先順序依次往下選擇。目前有4種優先順序策略,在tikv內可通過引數compaction-pri設定,可選值

0 (ByCompensatedSize),1 (OldestLargestSeqFirst),2 (OldestSmallestSeqFirst),3 (MinOverlappingRatio)。

1、 ByCompensatedSize

        優先選擇包含delete做多的檔案,越早刪除的資料就越早compact,減少空間放大和讀放大

2、 OldestLargestSeqFirst

       優先選擇最後更新時間最早的檔案,將檔案上的冷資料合併到下一層,相對熱資料留在上一層,減少讀放大。 TiKV 的 lockcf預設使用該策略。

3、 OldestSmallestSeqFirst

        優先選擇包含最老資料的檔案,通常有較大key範圍資料長時間未向下合併,與下層的key重疊較少,減少寫放大。

4、 MinOverlappingRatio

        優先選擇和下層key重疊率最小的檔案,TiKV 的 defaultcf 、writecf 的預設使用策略。

  • 範圍邊界

       通過檔案優先順序選定檔案後還要考慮檔案的key範圍,擴大需要compact的檔案範圍,如下5個檔案,如果在f3優先順序最高,則在compact時同時將{f2,f3,f4} 3個檔案向下合併,因為f2、f4中key範圍與f3有重疊,因此compact的key範圍由[k4,k6]擴充套件到了[k3,k8]。如果選擇的檔案中有任何檔案在被compact則會終止compact檔案選擇過程。

                           ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656491982904.png)

       對於Ln+1層需要按照上述方式對與Ln層有重疊key範圍的檔案進行擴充套件,然後將Ln、Ln+1選擇的檔案內的key作為input資料進行歸併排序、清理冗餘資料後寫入Ln+1 層。如果Ln 層要compact的檔案與下層無重疊,則直接將該檔案移動到Ln+1層。

       為了限制每次compaction的量大小,RocksDB支援通過max_compaction_bytes引數限制每輪compact的大小,該引數僅限制input level的大小,TiKV內支援該引數配置

8 L0 層檔案堆積後如何處理?

       當有大量資料寫入時,如果L0 到 L1 的compaction速度來不及處理會導致L0層檔案逐漸累積增多,通過subcompact並行方式可提升L0層compact速度。當L0層檔案數量達到一定數量後則會引起write stall,檔案數量達到level0-slowdown-writes-trigger 後 會降低寫入速度,當達到level0-stop-writes-trigger後則完全停止寫入。

       當L0 向L1 層合併時,如果L1層的sst file正在往 L2層合併被鎖住,將導致本次L0 -> L1層的compact不能執行,因此造成L0層檔案不能及時清理。基於此RocksDB引入了intra-L0 compaction,即在發生上述情況時在L0層內部進行compact,將多個sst file合併為1個大的sst file,以此減少L0層檔案數量,在一定程度上能夠提升L0層的讀效能和減少write stall的發生。

9 如何設定compaction併發執行緒數?

  • Flush & Compaction

       Flush執行緒和Compaction執行緒是RocksDB的2類後臺執行緒 ,使用執行緒池方式管理,在memtable寫滿或WAL切換時檢查是否需要flush或compaction,如果需要則從執行緒池裡排程執行緒完成flush或compaction。

       預設情況下RocksDB(5.6.1版本)對flush 和 compaction執行緒池統一進行管理,通過Options::max_background_jobs選項可設定後臺執行緒最大數量,RocksDB會自動調整flush和compaction執行緒數量。仍可以通過Options::max_background_flushes和Options::max_background_compactions選項設定flush和compact執行緒的數量。flush執行緒由於其關鍵性會放入HighPriority執行緒池,而compact執行緒放入LowPriority執行緒池。

    TiKV內提供了引數max-background-jobs、max-background-flushes可用於調整Options::max_background_jobs和Options::max_background_flushes,TiKV 會根據上述引數值計算compact執行緒數量。TiKV內執行緒數預設計算如下:

       max_background_jobs = MAX(2, max-background-jobs引數)

       max_flushs = MIN(max_background_jobs+ 3) / 4, max_background_flushes)

       max_compactions =  max_background_jobs - max_flushs

  • SubCompaction

       由於L0層檔案由memtable flush生成檔案之間存在重疊,不能以sst file為最小分組單位進行併發compaction,因此通過單執行緒將L0所有檔案都合併到L1層。L0 to  L1的併發合併使用subcompaction方式:

(1)    首先獲取L0層和L1層涉及的每個sst檔案的smallest key/largest key

(2)    將這些Key去重排序,每2個key分為一組作為一個range,預估key範圍覆蓋的sst檔案的總大小sum。

(3)    根據引數max_subcompaction、range的數量、sum/4.0/5/max_file_size中的最小值決定subcompaction執行緒數量。

(4)    將range分配給每個執行緒,每個執行緒只處理檔案的一部分key的compact,最後compact主執行緒將subcompact執行緒的結果進行合併整理。

                                    ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656492000424.png)

       在TiKV內可通過引數max-sub-compactions設定subcompaction的最大併發執行緒數,kv db預設為3,raft db預設為2。SubCompact執行緒數量不受max-background-jobs限制,但TiKV內設定的預設數量受max_compaction執行緒數影響,計算方式為:max_sub_compactions =MAX(1,MIN(max_sub_compactions引數, (max_compactions - 1)))。

      除了L0 -> L1 compact時可使用subcompaction外,在manual compaction(leveled compction)時L1+層也使用subcompaction以加快速度。

10 SST檔案什麼時候刪除?

       RocksDB使用version來表示資料庫的當前狀態(即某一時刻sst檔案的集合),每當增加或刪除一個sst file時都會對Manifest增加一條version edit記錄。當執行查詢或修改時會引用當前version,同時會對該version下的sst file設定reference count。

       Compact完成後會在output level生成新的檔案,同時需要刪除舊的Input 檔案,如果仍有其他操作在compact後仍未執行完成,則在compact後不能立即將需要的檔案刪除,等到sst file的reference count降為0後才能將檔案真正的刪除。

11 Compaction Guard

       如前面介紹,在compact選擇檔案時由於key範圍重疊,因此會擴充套件選定的sst 檔案,以包含進所有需要的Key,由此會造成的問題是需要額外讀寫一些多餘的key,同時由於一個sst file裡可能包含有多個不同的key,在對某段範圍key刪除後不方便直接刪除sst file。

Comapction Guard 是根據key將sst檔案分隔成一個個具有指定邊界的小檔案,從而降低compaction時讀寫key數量和方便物理刪除sst file。

       TiKV利用RocksDB的 SST Partitioner介面實現compaction guard,在compact時將sst file 按照region的 end key進行切分,實現了大部分的region和sst file對應,只對kv db的default CF、write CF有效,通過按region 切分sst file後可以實現sst file的快速刪除,也能提升region遷移速度。

       該功能預設啟用通過引數enable_compaction_guard設定,當啟用後 使用compaction-guard-max-output-file-size覆蓋target-file-size-base的引數值。如果sst file大小小於compaction-guard-min-output-file-size(預設8M)或大於compaction-guard-maxt-output-file-size時都不會觸發compaction guard進行切分。

                        ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656492018114.png)

12 TiDB內有哪些場景觸發Compaction?

       和RocksDB類似TiDB內也有自動和手動compaction,不過無論是自動還手動都是通過呼叫RockDB的manual compaction函式在RocksDB內產生一次手動compact。

  • 自動compaction

       對於wirte/default cf,每隔region-compact-check-interval(預設5分鐘)時間,就會檢查是否需要觸發手動RocskDB 的compact,如果一個region中tombstone key數量超過region-compact-min-tombstones (預設10000)並且tombstone key數量超過Key數量的region-compact-tombstones-percent(預設30%),則會觸發tikv的自動compaction,每次會檢查region-compact-check-step(預設100)個region,tikv會呼叫RockDB的manual compaction函式CompactRange 在RocksDB內產生一次手動compact。

       對於lockcf 每隔lock-cf-compact-threshold(預設10分鐘),如果lockcf的資料量達到lock-cf-compact-threshold則會呼叫RockDB的manual compaction函式。

  • 手動compaction

       手動compaction是指使用tikv-ctl 命令執行的compact。具體可參考TiDB官方文件tikv-ctl工具介紹。

tikv-ctl  --host  tikv_ip:port  compact -d kv -c default
tikv-ctl  --host  tikv_ip:port compact -d kv -c write --bottommost force

 

13 WriteStall有哪些觸發場景

       當RocksDB的flush或compact 速度落後於資料寫入速度就會增加空間放大和讀放大,可能導致磁碟空間被撐滿或嚴重的讀效能下降,為此則需要限制資料寫入速度或者完全停止寫入,這個限制就是write  stall, write stall觸發原因有:1、 memtable數量過多 2、L0檔案數量過多 3、 待compact的資料量過多。

  • memtable數量過多

       當memtable數量達到min-write-buffer-number-to-merge(預設值為1)

引數個時會觸發flsush,Flush慢主要由於磁碟效能問題引起,當等待flush的memetable數量>=引數max-write-buffer-number時會完全停止寫入。當max-write-buffer-number>3且等待flush的memetable數量>=引數max-write-buffer-number-1時會降低寫入速度。

       當由於memtable數量引起write stall時,記憶體充足的情況下可嘗試調大max-write-buffer-number、max_background_jobs 、write_buffer_size 進行緩解。

  • L0數量過多

       當L0 sst檔案數達到level0_slowdown_writes_trigger後會觸發write stall 降低寫入速度,當達到level0_stop_writes_trigger則完全停止寫入。

       當由於memtable數量引起write stall時,記憶體充足的情況下可嘗試調大max_background_jobs 、write_buffer_size、min-write-buffer-number-to-merge進行緩解。

  • 待compact的資料量過多

       當需要compact的檔案數量達到soft_pending_compaction_byte引數值時會觸發write stall,降低寫入速度,當達到hard_pending_compaction_byte時會完全停止寫入.

       TiKV內提供了相關監控用於觀察compact的相關活動,可通過TiKV Detail -> RockDB KV/rfat 中相關面板檢視。

       觸發write stall的原因可通過Write Stall Reason面板檢視。

                         ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656492053959.png)

       等待compact的檔案大小:

                           ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656492070370.png)

       Compact的讀寫速度:

                           ![image.png](https://tidb-blog.oss-cn-beijing.aliyuncs.com/media/image-1656492085210.png)

       5.2版本開始,tidb優化流控機制,在scheduler層進行流控代替rocksdb的wrtie stall機制,可以避免 write stall 機制卡住 Raftstore 或 Apply 執行緒導致的次生問題,該功能通過storage.flow-control控制是否開啟流量控制機制。開啟後,TiKV 會自動關閉 KV DB 的 write stall 機制,還會關閉 RaftDB 中除 memtable 以外的 write stall 機制,除此之外還可以使用memtables-threshold、l0-files-threshold、soft-pending-compaction-bytes-limit、hard-pending-compaction-bytes-limit等引數來進行控制。

14 GC 和 Compaction有哪些關聯?

       為防止系統中存在大量歷史版本資料影響系統性能,TiKV會定期進行GC清理已經過期的歷史版本,每隔tidb_gc_run_interval時間就發起一次GC,GC過程主要清理3個步驟,1、resolve lock 清理鎖,實際呼叫使用RockDB的 delete將記錄設定為tombstone 。2、truncate/drop table或Index後的sst檔案清理,直接使用物理刪除sst檔案方式。 3、MVCC版本清理,使用RockDB的delete將記錄設定為tombstone  ,(GC相關原理可參考 :TiDB GC 之原理淺析https://tidb.net/blog/ed740c2c)。

       從GC原理可以看出雖然在TiKV層執行的資料清理但在底層RocksDB儲存引擎資料是仍然存在的,只是增加了一個被設定了刪除標記tombstone記錄,對於tombstone記錄要等到compact到最底層bottom level時才能真正的刪除。

       GC屬於資源密集型操作,需要較多的IO和CPU消耗,TiDB在5.0版本引入了GC in Compaction Filter功能,在RocksDB compact時進行GC,以降低每次定期GC時處理的資料量,加快GC處理速度,從而減少讀操作和降低CPU。CompactionFilter是RocksDB的提供的一個介面,允許使用者根據自定義的邏輯去修改或刪除 KV,從而實現自定義的垃圾回收。

       當RocksDB執行compact時會呼叫TiKV的CompactionFilter邏輯,獲取當前safepoint時間,然後對比WriteCF中的commit_ts,對於safepoint前的記錄則不會保留,之後採用非同步的方式清理DefaultCF中的對應資料。由於非同步清理defaultCF會導致在WriteCF中版本記錄已經清理但DefaultCF中的記錄卻沒有清理,產生orphan version,為此TiKV增加了DefaultCF中orphan version記錄的清理功能,官方對應GC in Compaction Filter功能也在不斷的增強和完善。

       GC時CPU監控可通過TiKV Detail -> Thread CPU  -> GC Worker CPU面板檢視,GC執行的相關監控可通過 TiKV Detail -> GC 相關面板檢視。

15 總結

       對於TiKV和RockDB都在不斷完善compaction機制,以期降低LSM Tree帶來的讀放大、寫放大以及空間放大問題,進一步提升系統性能。同時TiKV中提供了豐富的監控指標用於監控GC 、Compaction等,方便使用者掌握相關執行情況、排查write stall等問題原因。

 ----------------------------------------------------------------

參考資料:

https://github.com/tikv/tikv

https://github.com/facebook/rocksdb/wiki

https://www.jianshu.com/p/88f286142fb7

http://mysql.taobao.org/monthly/2018/10/08/

https://blog.csdn.net/Z_Stand/article/details/107592966

https://kernelmaker.github.io/Rocksdb_Study_5

https://github.com/xieyu/blog/blob/master/src/rocksdb/flush-and-compact.md

https://rocksdb.org/blog/2017/06/26/17-level-based-changes.html

https://github.com/tikv/tikv/pull/8115

https://github.com/facebook/rocksdb/issues/9106