面向時序數據的兩階段日志結構合并樹文件合并框架

（清華大學軟件學院，北京 100085）

0 引言

日志結構合并樹（Log Structure Merge-tree，LSM）［1］存儲結構在非關系型數據庫（Not only SQL，NoSQL）尤其是時序數據庫中應用廣泛，例如OpenTSDB［2］、LevelDB［3］、KairosDB［4］、InfluxDB［5］等均采用了LSM 結構，從而實現了對海量鍵值（Key-Value，KV）數據有序存儲及低延遲查詢。

LSM 核心思想是通過多次合并數據，將數據集組織成有序的、大塊的文件［6］。對于實時寫操作，LSM 系統只更新內存，再批量將內存中的數據以塊數據的形式刷到磁盤，并通過特定合并策略異步整理數據文件為多層。對于讀操作，LSM系統從內存緩沖區、磁盤文件逐層地查找所需的數據。在傳統的LSM 結構（以RocksDB 的LSM 結構為例［7］）中，通常以C0、C1、…、Ck的多層的方式存儲數據文件，層與層之間保持固定比例M=（Size（Ci+1）/Size（Ci））（Size（Ci）表示Ci層的文件大小閾值）。當Ci層達到閾值時，就將Ci層合并（compaction）到Ci+1層去，每次這樣的合并操作都要讀寫Size（Ci+1）+Size（Ci）字節的數據。該合并流程保證了僅C0、C1層的文件之間存在亂序數據，從C2、C3、…、Ck多層文件中的所有key 都是有序的［8］。時序數據是指數據可以沿時間維度排序的數據。因此，LSM 通過合并帶來的數據排序特性十分適用于時序數據管理。

然而，在寫入負載較高時，異步的LSM 文件合并有可能跟不上數據的入庫速度，造成C0層數據的堆積。由于C0層是最新寫入的數據，這就造成系統對近期寫入的數據（往往為熱數據）的查詢延遲較高。此外，由于LSM 在合并過程中需要占用較多的讀寫（Input Output，IO）資源用于讀寫數據和中央處理器（Central Processing Unit，CPU）資源用于排序，一些系統（如Cassandra）等還限制了LSM 的合并速率，進一步加劇了對近期寫入數據的查詢延遲；但是，時序數據對剛剛寫入的數據的查詢需求最為頻繁，為此，如何在保留LSM 合并后實現數據排序特性、支持歷史數據快速查詢的基礎上，降低LSM對時序數據近期查詢的延遲影響，成為需要解決的關鍵問題。

針對上述問題，本文分析了面向時間序列數據的近期熱數據即席查詢和歷史冷數據分析型查詢這兩類查詢的特點，設計了同時優化這兩類查詢的兩階段LSM 合并策略：在第一階段，僅將亂序文件合并為順序文件，以實現最快速度的近期熱數據整理；在第二階段，將順序小文件合并為大文件，以實現大塊數據的讀取。此外，為了減少第一階段的LSM 工作量，在實時數據寫入時，直接將局部有序的數據寫入C1層，從而減少C0層的數據量。與傳統LSM 合并策略下的系統的讀寫性能對比結果表明，兩階段的LSM 合并能提高數據的合并效率，并且能夠有效提高數據的查詢效率。論文的工作與貢獻如下：

1）研究了主流NoSQL 數據庫合并模塊的設計，發現基于LSM 合并得到的數據塊并不是越大越好，而是與用戶特定查詢習慣有關［9］。為此，調研了時序數據即席熱數據和分析型冷數據查詢的訪問特點。

2）設計并實現了兩階段LSM 兩階段合并框架，并在時序數據庫Apache IoTDB中進行了驗證。

3）在兩階段框架中實現了一些特定的合并策略，并與傳統LSM合并策略下的系統讀寫性能進行對比。

1 研究背景

本章主要從傳統的LSM 出發，分析LevelDB、InfluxDB［10］的變種LSM結構。

1.1 LSM

LSM 樹是專門為鍵值（KV）存儲系統設計的，其思想主要是利用磁盤的順序寫來加速海量數據的存儲和讀寫。傳統的LSM是一個多層結構，上層小下層大，其中C0層保存了所有最近寫入的鍵值數據。這個內存結構是有序的，并且可以隨時原地更新，同時支持隨時查詢。剩下的C1到Ck層都在磁盤上，每一層都是一個在key上有序的結構，如圖1所示。

讀寫放大是LSM 樹合并的主要問題［11］。這里本文以RocksDB 的合并算法（Level Style Compaction）為例，這種合并機制每次會拿Ci層的所有文件和Ci+1層合并，層與層之間的比例M=(Size(Ci+1)/Size(Ci))，這樣子在最壞的情況下（寫入一條數據導致每一層合并），會重復讀寫Size(C1)+Size(C2)+…+Size(Ci)的數據，這也是各類LSM 的變種致力于解決和優化的問題。

圖1 傳統LSMFig.1 Traditional LSM

1.2 LevelDB

LevelDB的合并過程與引言中提到的RocksDB不同，它不選取上一層的所有數據和下一層進行合并，而是當Ci層達到閾值時，就要在Ci層選擇一個文件合并到Ci+1層去，由此保證除了C0層，其他層的key都是全局有序的［12］。

這種合并方式相比RocksDB 來說，大大減少了合并造成的寫放大，對于上文所說的最壞的情況來說，假設一個文件的大小Size(B)=1 MB，那么當系統要寫入一個新數據，只需要重新對C0層和C1層進行合并，讀寫1 MB的數據。

傳統LSM 和LevelDB 的LSM 策略均未面向時間序列數據的查詢進行優化。

1.3 InfluxDB

InfluxDB 基于LSM 自研了TSM（時間結構合并樹），主要采用了LevelCompaction［13］策略，并針對歷史時序數據的管理進行了不同時間序列分離和單時間序列整理兩部分優化。

1）LevelCompaction：InfluxDB 將TSM 文件分為4 個層級（C1C2C3C4），compaction 只會發生在同層級文件內，同層級的文件compaction 后會晉升到下一層級，相當于基于對LSM 固定了合并的最大層數為4。

2）IndexOptimizationCompaction：因為固定了層級，所以C4層文件會越來越大，使查詢效率變低，所以這種合并的主要作用就是將同一時間序列下的數據合并到同一個TSM 文件中，盡量減少不同TSM文件間的時間序列重合度。

3）FullCompaction：InfluxDB在判斷某個Shared（TSM中的一個時間塊）長時間沒有新數據后，會做FullCompaction 對本塊數據進行規整，提高壓縮率。

這種合并方式相比RocksDB、LevelDB 更接近于時間序列數據的存儲，因為限制了總的合并層數和合并次數，寫放大不會因為數據量的不斷增大不斷提高。此外，InfluxDB 通過兩部分優化工作，確保了在大量數據下，訪問歷史數據仍然能夠保持較低延遲。

1.4 Cassandra

Cassandra 基于傳統的LSM 結構開發了四種不同的合并策略，分別適用于不同的場景。

1）STCS（Size Tiered Compaction Strategy）：這是一個典型的Size-Tired Compaction 策略。當有（默認4個）數據塊的大小相似的時候，STCS 便會啟動。壓縮過程將這些數據塊合并成一個大的數據塊。這種策略在寫密集的負載中工作良好，當需要讀數據的時候，需要嘗試讀取多個數據塊來找到一行中的所有的數據。策略無法保證同一行的數據被限制在一小部分的數據塊中。同時可以預測刪除的數據是不均勻的，因為數據塊的數量是觸發壓縮的條件，并且數據塊可能增長的不夠快以便合并舊的數據。

2）TWCS（Time Window Compaction Strategy）：TWCS 通過使用一系列的時間窗口將數據塊進行分組。在compaction 階段，TWCS 在最新的時間窗口內使用STCS 去壓縮數據塊。在一個時間窗口的結束，TWCS 將落在這個時間窗口的所有的數據塊壓縮成一個單獨的數據塊。

3）LCS（Leveled Compaction Strategy）：LCS 用于解決STCS在讀操作上的問題。當數據塊的體積增長到一個不大的體積，它被寫入第0 級。在每個從C1開始的級別，單個級別中所有的數據塊都確保沒有重復數據，在此基礎上，LCS 會分割數據塊以確保文件大小相同，每個級別都是上一個級別大小的固定倍數，以此減少查詢時磁盤的seek次數。

4）DTCS（Date Tiered Compaction Strategy）：DTCS 和STCS很像，但是它不是基于數據塊的大小進行壓縮的，DTCS 通過判斷數據塊的創建時間進行壓縮。使用這種策略壓縮的數據塊可以高效讀取近期數據（上一小時的數據），但會導致過期數據不容易寫入。

2 兩階段合并框架

2.1 時序數據的訪問特點

用戶對于時序數據的訪問一般來說需要返回有序的數據段，并且有以下兩種常用的訪問類型［14］：

1）面向近期寫入數據的即席查詢。時序數據庫的一個重要作用是進行實時監控，在這種場景下，用戶往往讀取最近寫入的一小段時間的數據。例如，讀取最近5 min的數據。因此，這類查詢的特點是：①訪問近期寫入的數據；②訪問的數據時間段較短；③要求較高的系統響應速度。

2）面向歷史數據的分析型查詢。在分析應用中，用戶往往需要獲取一天、一個月甚至一年的數據，才能進行規律性總結、訓練模型等。因此，這類查詢的特點是：①訪問不太熱的歷史數據；②訪問的數據時間段較長。

傳統LSM 通過多層級合并，能夠高效支持第二類查詢。本章通過設計兩階段LSM，解決由于C0層堆積導致的第一類查詢性能下降的問題。

2.2 核心設計

2.2.1C0層拆分

在傳統LSM 中，內存中的數據（即C0層）在到達一定大小后會被刷寫到磁盤上形成C1層。C0層的多次刷寫造成了C1層多個文件之間存在亂序。在時間序列數據庫中，同一條時間序列的數據是以時間戳排序的。因此，通過在內存中記錄每條時間序列的最新時間戳，可以準確判斷出該序列新寫入的數據點與C1層已有的數據相比是順序的（即時間戳更大）還是亂序的（即時間戳更小）。

利用上述特性，本文將LSM 中的C0層內存結構拆分為亂序緩沖區與順序緩沖區。對于C0層順序緩沖區的數據，當其大小達到閾值時，將被直接刷寫入C2層。對于C0層的亂序數據則只能被刷寫入C1層，并等待LSM的文件合并。

在時間序列數據應用中，數據在多數情況下是沿著時間戳維度增序到達的。因此，在上述改造下，C1層僅存在少量的亂序數據。那些近期寫入的在時間維度上順序遞增的數據，則直接在C2層。

對于近期數據的即席查詢來說，其訪問的數據往往來自內存、C1層和C2層。由于C2層的多個文件之間保持有序（從而可以在時間維度上進行剪枝查詢），因此在C2層的近期數據查詢延遲較低。內存中的數據由于不涉及IO 操作，其查詢延遲也較低。因此，如何加速近期數據的即席查詢，其關鍵就在于如何將少量的C1層數據快速合并為C2層的有序數據。

2.2.2 兩階段合并框架

如圖2 所示，本文將合并過程分為兩個階段，亂序文件合并為順序文件和順序小文件合并為大文件。亂序數據為C1層，第一階段會將亂序數據合并為C2層的順序數據。第一階段完成后，第二階段將順序小文件合并為更規整化的順序大文件為C3層或更多的Cn層。C3C4…Cn的寫入和合并由不同的順序文件合并策略決定。

在該設計中，第一階段的文件合并的目的即快速減少亂序數據，從而支持高效的近期數據的即席查詢。顯然地，與傳統LSM 相比，在進行相同多次IO 操作時，第一階段文件合并能比傳統LSM 將更多的亂序數據整理為順序數據。第二階段的文件合并的目的是生成大塊的數據文件，從而減少分析型查詢批量讀取數據時的頻繁磁盤seek操作。

圖2 兩階段的文件合并Fig.2 Two-stage file compaction

在實際應用中，可以根據系統的查詢負載進行兩階段合并的資源分配。例如，當用戶頻繁進行大量近期數據即時查詢時，合并亂序數據的優先級就更高，將小文件合并為大文件就不是很必要，反而會因為占用過多IO 和CPU 資源而阻塞系統的即時查詢和寫入性能。在這種情況下，可以給第一階段較多的線程資源、并增加第一階段的合并觸發頻率，從而加速第一階段的合并，再慢慢運行第二階段文件合并，最終將小文件合并為大文件。

與傳統LSM 相比，兩階段文件合并的一個負面影響是增大了寫放大。為了減少寫放大，本文借鑒MapReduce 計算框架中在Map階段內增加Combiner的思想對兩階段框架進行改造：當系統的CPU 資源較為富裕時，本文可以在第一階段執行亂序文件合并為順序文件時，同時將所涉及的小文件合并成大文件，從而減少第二階段的觸發頻率，由此減小兩階段框架的寫放大。并且，在第一階段的亂序合并過程中，本文會盡可能地保留原文件的數據塊，選擇寫放大最小的目標順序文件寫入方法。

2.3 多種合并策略

兩階段合并框架僅定義了第一階段主要目的是進行亂序數據合并，第二階段進行小文件合并。在每個階段中，可以采用工業界和學術界現有的各種合并策略進行文件的合并。

為了更好地說明核心設計思想，本文在實現兩階段合并模塊的框架下，同時實現了四種文件合并策略。1）INPLACE：該策略用于第一階段文件合并，合并后的亂序數據將被寫入原文件中，其目的是以較少IO 的方式完成文件亂序到順序的合并。2）SQUEEZE：混合合并策略，在完成亂序文件合并的同時完成一部分順序文件合并的工作，合并后的亂序數據將被統一整理到新文件中，其目的是減少寫放大。3）REGULARIZATION：小文件合并策略，其目的是以高效率的方式完成小文件到大文件的合并，并確保文件中每一條時間序列的連續數據塊閾值達到最低標準。4）INDEPENDENCE：小文件合并策略，其目的是在REGULARIZATION 基礎上保證每個文件有且僅有一個設備的數據，方便進行單設備查詢的用戶獲得更快的查詢效率。該策略與InfluxDB的優化類似。

2.4 寫放大評估

上文中提到，兩階段的文件合并策略除了最基礎的C0和C1層，可以將最終的合并結果文件配置成Cn層。在實際時序數據庫中，數據塊并不是越大越好［15］，因此本文采用合并為n=3的結構進行評估。

在兩階段的合并框架中，寫入一條無規律亂序數據最多會造成Size(C0B) +Size(C2B)（其中Size(CiB)為Ci層數據塊的平均大小）的數據重復讀寫，寫入一條有規律亂序數據最多造成(Size(C0B) +N1*Size(C1B) +N2*Size(C2B))/M（其中N1、N2表示有與亂序文件有重疊的順序文件，M表示同時一起進行讀寫的當時亂序數據點數量，N1+N2 ?M）的數據重復讀寫。這與RocksDB 的Size(C0)+Size(C1)+Size(C2)相比，減少了在合并模塊造成的寫放大。

3 實驗與評估

本章首先設計實驗驗證在相同寫放大因子下（即進行相同多次IO 操作后），兩階段框架帶來的近期數據即席查詢的收益。進而，本章設計實驗對比在Apache IoTDB 系統中，傳統LSM（RocksDB 的LSM 實現和合并方法）和兩階段LSM 合并框架在內存占用和數據讀寫性能的差異。

3.1 實驗環境

本實驗使用一臺配置如表1的服務器。

表1 實驗環境配置Tab.1 Configuration of experimental environment

3.2 實驗數據

實驗采用時間序列數據庫性能測試工具IoTDBBenchmark［16］產生數據，然后分別使用兩階段合并以及傳統LSM 合并對數據進行合并操作，直到合并到第n層（n=3）為止，然后再模擬客戶端對以上兩者的合并結果進行查詢測試。測試工具共創建1 000 條時間序列（10 個設備，每個設備100個傳感器），每個序列寫入100 000 個數據點。每個序列的數據均為64 位浮點數，并按照泊松分布以10%、30%、50%的比例生成時間戳亂序的數據。順序數據中，相鄰兩個數據點時間戳相差1 s。

在第一階段本文采用SQUEEZE 策略，在第二階段本文采用REGULARIZATION 策略。對于傳統LSM 合并的參數配置，本文設置C0層為100 個點，層與層之間比例為10，整個LSM樹合并結果也是三層。

3.3 性能測試

3.3.1 相同寫放大時的查詢收益對比

對面向近期寫入數據的即席查詢而言，亂序文件合并比小文件合并更重要。在本次實驗中，本文首先在原始寫入的數據上進行查詢（即在包含10%、30%、50%亂序數據的數據集上進行查詢），其查詢代價作為基準。然后，在相同寫放大下（即在文件合并過程中進行相同次數的IO 操作后）進行傳統LSM 和兩階段LSM 的查詢測試。在實際實驗中，本文以兩階段框架下第一階段完成全部合并時的寫放大值為準，停止傳統LSM 的文件合并進程，此時傳統LSM 僅合并了10%、30%、50%的亂序數據（即還剩下9%、21%、25%的亂序數據）。

測試結果如圖3所示，隨著亂序數據的增多，傳統LSM 對原始查詢的優化比例逐漸提高（從10%亂序時的15%到50%亂序時的110%），而完成了第一階段合并后查詢所需讀數據塊的次數是一個定值（且遠小于原始數據和傳統LSM 合并后所需查詢次數），亂序數據比例越大，這種對即席查詢的優化越明顯。可見，在相同寫放大下，先合并亂序數據顯然優于傳統LSM。

圖3 每次查詢平均讀數據塊次數Fig.3 Average number of read chunks per query

3.3.2 歷史數據分析查詢

接下來，本文對傳統LSM 和兩階段LSM 合并完的結果進行測試，傳統LSM 與兩階段LSM 的結果文件相比原始文件均有了極大的壓縮，LSM 合并后文件壓縮至原來的1/4，兩階段合并后文件壓縮至原來的1/2.5，這是因為傳統LSM最后一層的數據塊大小相比兩階段LSM 大很多，但往往對用戶的查詢來說，不需要這么大的單個數據塊，太大的數據塊提高了數據塊的讀取延遲和解析延遲，造成了更多的讀放大。

對合并后的結果進行讀寫性能測試，寫延遲幾乎沒有變化，兩階段LSM 相比傳統LSM 優化了約10%。讀延遲優化則比較明顯，降低了約20%。這是因為對于兩階段LSM來說，本文可以靈活控制合并后的結果文件數據塊大小，使其既不太大，讀盤次數也不過多，更符合查詢規律，也就提高了查詢性能。

綜合上述結果，相比傳統LSM，兩階段LSM在歷史數據分析查詢方面沒有過大的影響，并能使用戶更加靈活地控制結果數據塊大小，達到貼合查詢規律以提升讀寫性能的目的。

圖4 合并后文件大小Fig.4 File size after compaction

4 結語

本文針對時序數據的查詢需求，對LSM 文件合并流程進行了改進，設計了兩階段文件合并框架。該框架通過分離亂序數據整理和小文件整理這兩個任務目標，使得系統能夠盡快完成亂序數據整理，帶來近期寫入數據查詢的性能優化。

為驗證框架的有效性，本文在Apache IoTDB 中同時實現了RocksDB的傳統LSM文件合并策略和兩階段文件合并框架并進行對比實驗，實驗表明，該框架與傳統LSM 合并相比，顯著提高了即席查詢的效率，并且用戶可以通過靈活配置結果文件大小，提高歷史數據分析查詢效率。

未來，將繼續在以下方面展開工作：

1）優化兩階段合并框架的調度算法，當前的兩階段合并只是默認在固定的時間間隔下每次順序執行，但沒有對冷熱數據及查詢負載進行感知。

2）在內存和C0層之間增加基于last 文件的熱合并算法，避免在內存極端受限場景下C1層文件過小導致的讀寫放大，并提高后續文件合并效率。

3）設計和研發更多動態的合并策略，當前的合并策略只保證了目標文件的寫入、生成和大小控制，這需要數據庫管理員有一定的調參能力，因此接下來本文還會實現更加動態的算法配置策略，盡可能提高算法的易用性。