（清華大學(xué)軟件學(xué)院，北京 100085）

0 引言

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

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

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

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

1）研究了主流NoSQL 數(shù)據(jù)庫合并模塊的設(shè)計(jì)，發(fā)現(xiàn)基于LSM 合并得到的數(shù)據(jù)塊并不是越大越好，而是與用戶特定查詢習(xí)慣有關(guān)［9］。為此，調(diào)研了時序數(shù)據(jù)即席熱數(shù)據(jù)和分析型冷數(shù)據(jù)查詢的訪問特點(diǎn)。

2）設(shè)計(jì)并實(shí)現(xiàn)了兩階段LSM 兩階段合并框架，并在時序數(shù)據(jù)庫Apache IoTDB中進(jìn)行了驗(yàn)證。

3）在兩階段框架中實(shí)現(xiàn)了一些特定的合并策略，并與傳統(tǒng)LSM合并策略下的系統(tǒng)讀寫性能進(jìn)行對比。

1 研究背景

本章主要從傳統(tǒng)的LSM 出發(fā)，分析LevelDB、InfluxDB［10］的變種LSM結(jié)構(gòu)。

1.1 LSM

LSM 樹是專門為鍵值（KV）存儲系統(tǒng)設(shè)計(jì)的，其思想主要是利用磁盤的順序?qū)憗砑铀俸Ａ繑?shù)據(jù)的存儲和讀寫。傳統(tǒng)的LSM是一個多層結(jié)構(gòu)，上層小下層大，其中C0層保存了所有最近寫入的鍵值數(shù)據(jù)。這個內(nèi)存結(jié)構(gòu)是有序的，并且可以隨時原地更新，同時支持隨時查詢。剩下的C1到Ck層都在磁盤上，每一層都是一個在key上有序的結(jié)構(gòu)，如圖1所示。

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

圖1 傳統(tǒng)LSMFig.1 Traditional LSM

1.2 LevelDB

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

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

傳統(tǒng)LSM 和LevelDB 的LSM 策略均未面向時間序列數(shù)據(jù)的查詢進(jìn)行優(yōu)化。

1.3 InfluxDB

InfluxDB 基于LSM 自研了TSM（時間結(jié)構(gòu)合并樹），主要采用了LevelCompaction［13］策略，并針對歷史時序數(shù)據(jù)的管理進(jìn)行了不同時間序列分離和單時間序列整理兩部分優(yōu)化。

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

2）IndexOptimizationCompaction：因?yàn)楣潭藢蛹?，所以C4層文件會越來越大，使查詢效率變低，所以這種合并的主要作用就是將同一時間序列下的數(shù)據(jù)合并到同一個TSM 文件中，盡量減少不同TSM文件間的時間序列重合度。

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

這種合并方式相比RocksDB、LevelDB 更接近于時間序列數(shù)據(jù)的存儲，因?yàn)橄拗屏丝偟暮喜訑?shù)和合并次數(shù)，寫放大不會因?yàn)閿?shù)據(jù)量的不斷增大不斷提高。此外，InfluxDB 通過兩部分優(yōu)化工作，確保了在大量數(shù)據(jù)下，訪問歷史數(shù)據(jù)仍然能夠保持較低延遲。

1.4 Cassandra

Cassandra 基于傳統(tǒng)的LSM 結(jié)構(gòu)開發(fā)了四種不同的合并策略，分別適用于不同的場景。

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

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

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

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

2 兩階段合并框架

2.1 時序數(shù)據(jù)的訪問特點(diǎn)

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

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

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

傳統(tǒng)LSM 通過多層級合并，能夠高效支持第二類查詢。本章通過設(shè)計(jì)兩階段LSM，解決由于C0層堆積導(dǎo)致的第一類查詢性能下降的問題。

2.2 核心設(shè)計(jì)

2.2.1C0層拆分

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

利用上述特性，本文將LSM 中的C0層內(nèi)存結(jié)構(gòu)拆分為亂序緩沖區(qū)與順序緩沖區(qū)。對于C0層順序緩沖區(qū)的數(shù)據(jù)，當(dāng)其大小達(dá)到閾值時，將被直接刷寫入C2層。對于C0層的亂序數(shù)據(jù)則只能被刷寫入C1層，并等待LSM的文件合并。

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

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

2.2.2 兩階段合并框架

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

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

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

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

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

2.3 多種合并策略

兩階段合并框架僅定義了第一階段主要目的是進(jìn)行亂序數(shù)據(jù)合并，第二階段進(jìn)行小文件合并。在每個階段中，可以采用工業(yè)界和學(xué)術(shù)界現(xiàn)有的各種合并策略進(jìn)行文件的合并。

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

2.4 寫放大評估

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

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

3 實(shí)驗(yàn)與評估

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

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)使用一臺配置如表1的服務(wù)器。

表1 實(shí)驗(yàn)環(huán)境配置Tab.1 Configuration of experimental environment

3.2 實(shí)驗(yàn)數(shù)據(jù)

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

在第一階段本文采用SQUEEZE 策略，在第二階段本文采用REGULARIZATION 策略。對于傳統(tǒng)LSM 合并的參數(shù)配置，本文設(shè)置C0層為100 個點(diǎn)，層與層之間比例為10，整個LSM樹合并結(jié)果也是三層。

3.3 性能測試

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

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

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

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

3.3.2 歷史數(shù)據(jù)分析查詢

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

對合并后的結(jié)果進(jìn)行讀寫性能測試，寫延遲幾乎沒有變化，兩階段LSM 相比傳統(tǒng)LSM 優(yōu)化了約10%。讀延遲優(yōu)化則比較明顯，降低了約20%。這是因?yàn)閷τ趦呻A段LSM來說，本文可以靈活控制合并后的結(jié)果文件數(shù)據(jù)塊大小，使其既不太大，讀盤次數(shù)也不過多，更符合查詢規(guī)律，也就提高了查詢性能。

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

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

4 結(jié)語

本文針對時序數(shù)據(jù)的查詢需求，對LSM 文件合并流程進(jìn)行了改進(jìn)，設(shè)計(jì)了兩階段文件合并框架。該框架通過分離亂序數(shù)據(jù)整理和小文件整理這兩個任務(wù)目標(biāo)，使得系統(tǒng)能夠盡快完成亂序數(shù)據(jù)整理，帶來近期寫入數(shù)據(jù)查詢的性能優(yōu)化。

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

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

1）優(yōu)化兩階段合并框架的調(diào)度算法，當(dāng)前的兩階段合并只是默認(rèn)在固定的時間間隔下每次順序執(zhí)行，但沒有對冷熱數(shù)據(jù)及查詢負(fù)載進(jìn)行感知。

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

3）設(shè)計(jì)和研發(fā)更多動態(tài)的合并策略，當(dāng)前的合并策略只保證了目標(biāo)文件的寫入、生成和大小控制，這需要數(shù)據(jù)庫管理員有一定的調(diào)參能力，因此接下來本文還會實(shí)現(xiàn)更加動態(tài)的算法配置策略，盡可能提高算法的易用性。