時序數(shù)據(jù)庫關鍵技術綜述

劉 帥 喬 穎 羅雄飛 趙怡婧 王宏安

1 （中國科學院大學計算機科學與技術學院 北京 100049）

2 （人機交互北京市重點實驗室（中國科學院軟件研究所） 北京 100190）

近年來，隨著工業(yè)物聯(lián)網(wǎng)（industrial Internet of things，IIoT）技術的迅猛發(fā)展，工業(yè)制造開始進入數(shù)字化時代，各種設備和傳感器產(chǎn)生的時間序列數(shù)據(jù)（簡稱“時序數(shù)據(jù)”）正在爆炸式地增長，成為數(shù)字經(jīng)濟的核心生產(chǎn)要素.在工業(yè)物聯(lián)網(wǎng)中，時序數(shù)據(jù)通常包括傳感器的測量數(shù)據(jù)、設備狀態(tài)記錄和生產(chǎn)過程參數(shù)，時序數(shù)據(jù)記錄了生產(chǎn)環(huán)境在不同時間點上的變化趨勢，通過采集和分析時序數(shù)據(jù)，可以實時監(jiān)控設備狀態(tài)、預測故障和優(yōu)化生產(chǎn)過程.工業(yè)物聯(lián)網(wǎng)中的時序數(shù)據(jù)具有產(chǎn)生頻率高、數(shù)據(jù)規(guī)模大、數(shù)據(jù)維度復雜的特點，例如，三一重工在生產(chǎn)的每臺重型機械上安裝了多種類型的傳感器以搜集各種參數(shù)，如機械的開關信號、GPS 信息、發(fā)動機參數(shù)等，用以監(jiān)控重型機械的運轉(zhuǎn)情況[1]，這對海量時序數(shù)據(jù)的管理帶來了挑戰(zhàn)，海量時序數(shù)據(jù)管理已經(jīng)成為一個難題.雖然一些數(shù)據(jù)庫管理系統(tǒng)，如關系數(shù)據(jù)庫管理系統(tǒng)（relational database management system，RDBMS）也可以用來管理時序數(shù)據(jù)，但是時序數(shù)據(jù)的工作負載完全不同于關系數(shù)據(jù)，隨著時序數(shù)據(jù)規(guī)模的不斷增長，這些通用的數(shù)據(jù)庫管理系統(tǒng)的性能會急劇下降，無法處理大規(guī)模傳感網(wǎng)絡產(chǎn)生的時序數(shù)據(jù).為了存儲和分析大規(guī)模的時序數(shù)據(jù)，專門的時序數(shù)據(jù)庫（time series database，TSDB）被開發(fā)出來，以克服通用數(shù)據(jù)庫管理系統(tǒng)在時序數(shù)據(jù)管理方面的局限性.在20 世紀90 年代末就已經(jīng)出現(xiàn)了時序數(shù)據(jù)庫RRDtool[2]，用于處理網(wǎng)絡帶寬、溫度監(jiān)測等產(chǎn)生的時序數(shù)據(jù)，但是直到物聯(lián)網(wǎng)開始快速發(fā)展，越來越多的設備被接入到網(wǎng)絡中，時序數(shù)據(jù)庫才進入快速發(fā)展時期，尤其是在最近5 年，根據(jù)DB-Engines[3]排名，從2018 年開始，時序數(shù)據(jù)庫的關注度開始迅速增長.雖然已經(jīng)有一些關于時序數(shù)據(jù)庫的綜述工作，但是這些工作的重點集中在對時序數(shù)據(jù)庫的功能和性能的比較，缺少對時序數(shù)據(jù)庫技術的調(diào)查和研究，且這些綜述工作出現(xiàn)的時間較早，缺少對現(xiàn)代時序數(shù)據(jù)庫的研究.

本文系統(tǒng)地對時序數(shù)據(jù)庫系統(tǒng)現(xiàn)有的工作進行了調(diào)查和綜述.首先，介紹了相關的綜述性工作以及背景知識，并分析了時序數(shù)據(jù)庫在管理工業(yè)物聯(lián)網(wǎng)中的海量時序數(shù)據(jù)時面臨的挑戰(zhàn).其次，根據(jù)存儲架構的不同，將時序數(shù)據(jù)庫分為4 大類，包括：1）內(nèi)存型時序數(shù)據(jù)庫；2）基于關系數(shù)據(jù)庫的時序數(shù)據(jù)庫；3）基于KV（key-value）存儲的時序數(shù)據(jù)庫；4）原生時序數(shù)據(jù)庫.并介紹了每一類的代表系統(tǒng)，比較了不同存儲架構的數(shù)據(jù)模型和管理時序數(shù)據(jù)的優(yōu)缺點.然后，重點研究時序數(shù)據(jù)庫的4 類關鍵技術，包括：1）時間序列索引優(yōu)化技術；2）內(nèi)存數(shù)據(jù)組織技術；3）高吞吐量數(shù)據(jù)攝取和低延遲數(shù)據(jù)查詢技術；4）海量歷史數(shù)據(jù)低成本存儲技術.同時還介紹了時序數(shù)據(jù)庫的評測基準.最后，本文對時序數(shù)據(jù)庫關鍵技術在未來的發(fā)展方向進行了展望，包括面向工作負載的自適應時序數(shù)據(jù)存儲技術、面向新硬件優(yōu)化的時序數(shù)據(jù)存儲技術，以及使用云原生技術和人工智能技術的時序數(shù)據(jù)存儲技術.

本文的關注點是時序數(shù)據(jù)庫關鍵技術，包括時序數(shù)據(jù)緩存、壓縮、存儲、查詢、計算和索引等，不涉及對時序數(shù)據(jù)庫分布式技術的討論.我們調(diào)查了2013—2023 年學術界和工業(yè)界的研究成果，以及一些開源時序數(shù)據(jù)庫.根據(jù)這些要求，我們建立了綜述工作的納入標準和排除標準.

納入標準：

1）這項工作是專門針對時序數(shù)據(jù)管理的；

2）這項工作在管理時序數(shù)據(jù)上有創(chuàng)新性；

3）這項工作必須包含時序數(shù)據(jù)緩存或持久化存儲；

4）這項工作在當前時間正在活躍地進行.

排除標準：

1）這項工作的關注度很低，或者沒有創(chuàng)新性；

2）該數(shù)據(jù)庫是基于其他數(shù)據(jù)庫研發(fā)的，在管理時序數(shù)據(jù)上沒有值得關注的創(chuàng)新點；

3）這項工作是討論時序數(shù)據(jù)庫分布式技術的；

4）這項工作相對久遠，早于2013 年，除非該工作在時序數(shù)據(jù)庫技術中有重要的地位，否則該工作只會用在背景介紹中.

為了高效地研究時序數(shù)據(jù)庫關鍵技術，我們只選擇與研究問題最相關的論文和時序數(shù)據(jù)庫進行調(diào)查綜述，從具有數(shù)據(jù)庫技術、存儲主題的會議和期刊中查找論文，同時還在Google Scholar，ACM，DBLP直接使用關鍵詞搜索論文.在查找時序數(shù)據(jù)庫時，我們使用了DB-Engines[4]提供的服務，在時序數(shù)據(jù)庫管理系統(tǒng)分類Top20 中，找到開源且得分較高或排名在上升的時序數(shù)據(jù)庫.注意，我們的選擇結果截止期為2023 年4 月.

本文不僅調(diào)查了最近10 年學術界和工業(yè)界的時序數(shù)據(jù)庫關鍵技術的研究成果，同時研究了一些關注度高的開源時序數(shù)據(jù)庫，本文的貢獻有3 個方面：1）對現(xiàn)有的時序數(shù)據(jù)庫技術進行了全面的調(diào)查和綜述；2）對時序數(shù)據(jù)庫的4 類關鍵技術進行了詳細的研究，并介紹了時序數(shù)據(jù)庫的評測基準；3）展望了時序數(shù)據(jù)庫關鍵技術在未來的發(fā)展方向，并提出了一些預測和建議.

1 相關工作

在本節(jié)中，我們將介紹一些與時序數(shù)據(jù)庫相關的綜述工作，現(xiàn)有綜述工作側重于不同時序數(shù)據(jù)庫的功能、性能比較或特定場景中對時序數(shù)據(jù)庫的選擇建議.

Jensen 等人[5]對時序數(shù)據(jù)庫管理系統(tǒng)進行了全面的調(diào)查，首先按照存儲架構將這些系統(tǒng)分為3 類：1）內(nèi)置時序數(shù)據(jù)存儲系統(tǒng)，如WearDrive[6]；2）外置時序數(shù)據(jù)存儲系統(tǒng)，如Gorilla[7]；3）通過擴展關系數(shù)據(jù)庫實現(xiàn)時序數(shù)據(jù)存儲，如TimeTravel[8].其次，從功能、架構和性能3 個方面對這些時序數(shù)據(jù)庫進行了全面的介紹.然后，提出了時序數(shù)據(jù)庫在管理時序數(shù)據(jù)時遇到的挑戰(zhàn)，比如數(shù)據(jù)壓縮、索引、查詢.最后討論了時序數(shù)據(jù)庫技術在未來的研究方向，如基于模型的分布式近似查詢處理（approximate query processing，AQP）、面向特殊查詢模式的優(yōu)化技術.文獻[5]完成于2017 年，研究所涉及的時序數(shù)據(jù)庫在現(xiàn)在看來很多都已經(jīng)過時，一些時序數(shù)據(jù)庫不再繼續(xù)開發(fā)或維護，缺少對2017 年以后出現(xiàn)的時序數(shù)據(jù)庫的研究，而2017 年至今是時序數(shù)據(jù)庫發(fā)展最快的時期.

Bader 等人[9]檢索了83 個開源的時序數(shù)據(jù)庫，重點比較了12 個時序數(shù)據(jù)庫，包括InfluxDB[10]，Open-TSDB[11]，TimescaleDB[12]，Apache Cassandra[13]等，從系統(tǒng)架構、數(shù)據(jù)模型、數(shù)據(jù)攝取和查詢性能等方面對每個時序數(shù)據(jù)庫進行了全面評估，還討論了這些開源時序數(shù)據(jù)庫的局限性和未來的發(fā)展趨勢.這是一篇較新的且較全面的時序數(shù)據(jù)庫調(diào)查文獻，但是缺少對時序數(shù)據(jù)庫技術細節(jié)的研究.

Sanaboyina[14]從能源效率的角度對InfluxDB[10]和OpenTSDB[11]進行了比較，首先討論了數(shù)據(jù)中心能源消耗的重要性和對數(shù)據(jù)庫節(jié)能的需求，然后根據(jù)InfluxDB 和OpenTSDB 在負載和空載條件下的能耗來評估它們的性能.

還有一些針對特定領域的時序數(shù)據(jù)庫調(diào)查，F(xiàn)adhel 等人[15]對DB-Engines[4]上排名前8 的可用于存儲和查詢水質(zhì)數(shù)據(jù)的時序數(shù)據(jù)庫（包括InfluxDB[10]，OpenTSDB[11]，Prometheus[16]等）進行了比較分析，評估各種時序數(shù)據(jù)庫納入低成本水質(zhì)監(jiān)測系統(tǒng)的能力.Grzesik 等人[17]在低功耗傳感器網(wǎng)絡邊緣計算背景下對時序數(shù)據(jù)庫進行比較分析，重點研究了TimescaleDB，InfluxDB，Riak TS[18]三個時序數(shù)據(jù)庫以及PostgreSQL[19]和SQLite[20]兩個關系型數(shù)據(jù)庫的性能，并在Raspberry Pi 計算機上進行了性能測試.

可以發(fā)現(xiàn)，以上的綜述工作有2 個特點：1）研究工作集中在5 年前，缺少對最近5 年內(nèi)的時序數(shù)據(jù)庫技術的研究；2）研究內(nèi)容集中在時序數(shù)據(jù)庫的功能和性能的比較，以及在特定領域中對時序數(shù)據(jù)庫的選擇建議，缺少對時序數(shù)據(jù)庫存儲、查詢、計算、索引等技術的研究.然而，過去幾年里時序數(shù)據(jù)庫技術正在迅速發(fā)展，至今為止還沒有一篇涵蓋時序數(shù)據(jù)庫關鍵技術的完整的綜述文章.本文將對時序數(shù)據(jù)庫的關鍵技術，包括時序數(shù)據(jù)庫持久化存儲、查詢、數(shù)據(jù)壓縮、索引與計算技術進行全面的調(diào)查和研究.注意，本文不涉及對時序數(shù)據(jù)庫分布式技術的討論.

2 背景知識

在本節(jié)中，我們首先分析時序數(shù)據(jù)的特點，然后概述時序數(shù)據(jù)庫的基本知識，最后介紹在時序數(shù)據(jù)庫技術中最常使用的2 種數(shù)據(jù)結構.

2.1 時序數(shù)據(jù)

時序數(shù)據(jù)是一組按照時間順序索引的數(shù)據(jù)點，這些數(shù)據(jù)通常由同一來源在一個固定的時間間隔內(nèi)的連續(xù)測量組成，用于跟蹤隨時間而產(chǎn)生的變化[21].時序數(shù)據(jù)由測量指標（metric）、標簽集（tag set）、測量字段集（field set）和時間戳（timestamp）構成.以氣象監(jiān)測數(shù)據(jù)為例，測量指標是每個氣象氣球需要采集的氣象（weather）數(shù)據(jù)，每個氣象氣球有2 個靜態(tài)數(shù)據(jù)：位置（location）和氣球id， 每分鐘采集溫度（temperature,temp）和濕度（humidity）2 個氣象數(shù)據(jù)，如表1 所示.

Table 1 Weather Monitoring Data表1 氣象監(jiān)測數(shù)據(jù)

時序數(shù)據(jù)有4 個特點：

1）數(shù)據(jù)是結構化的，帶有一個時間戳，數(shù)據(jù)在時間上是有序的；

2）數(shù)據(jù)以寫入為主，極少情況下有更新和刪除操作；

3）數(shù)據(jù)規(guī)模巨大，例如，GoldWind 風力發(fā)電公司有超過2 萬個風力發(fā)電機，每個風機上有120～510 個傳感器，數(shù)據(jù)采集頻率可達50 Hz，整個公司每秒產(chǎn)生接近5 億個時序數(shù)據(jù)點[22]；

4）數(shù)據(jù)的查詢與分析通常以時間范圍為基礎，需要多個維度的過濾查詢分析，如t1～t2時間內(nèi)，位置為southeast1、氣球id為1 的氣象氣球監(jiān)測到的最高溫度和最低溫度.

大部分時序數(shù)據(jù)庫使用KV 模型的列式存儲，由時序數(shù)據(jù)的特點可知，時序數(shù)據(jù)是帶有時間戳的特殊的KV 數(shù)據(jù).例如，1 條時序數(shù)據(jù)“weather,location=southeast1,id=1,temp=9.6,humidity=51,timestamp=1672531200”可以被表示為2 條KV 數(shù)據(jù)：

這里的鍵（key1，key2）被稱為序列鍵（series key），用于描述采集值的靜態(tài)屬性，值（value1，value2）由采集值和時間戳組成.

2.2 時序數(shù)據(jù)庫基本知識

時序數(shù)據(jù)庫是用于管理時序數(shù)據(jù)的一類數(shù)據(jù)庫，至少應該具有寫入（write）和查詢（query）操作，有些時序數(shù)據(jù)庫也提供更新（update）和刪除（delete）操作.write 將一個或者一批時序數(shù)據(jù)點寫入時序數(shù)據(jù)庫；query 從時序數(shù)據(jù)庫中查詢數(shù)據(jù)，需要支持基于時間范圍和標簽組合的過濾查詢；update 更新具有相同標簽值和時間戳的時序數(shù)據(jù)；delete 根據(jù)時間范圍、標簽值和字段從數(shù)據(jù)庫中刪除數(shù)據(jù).一些時序數(shù)據(jù)庫還提供了數(shù)據(jù)分析服務，比如InfluxDB 提供了SUM，MIN，MAX，AVG 等聚合計算函數(shù)，以及HOLT_WINTERS等時間序列預測方法[23]，用于預測未來的趨勢和季節(jié)性變化，這些特性在預測和趨勢分析至關重要的金融和投資領域尤其有用.時序數(shù)據(jù)庫需要面對每秒數(shù)百萬數(shù)據(jù)點的寫入，不斷增加的時序數(shù)據(jù)導致存儲成本快速增加，一些時序數(shù)據(jù)庫通過數(shù)據(jù)生命周期管理和數(shù)據(jù)壓縮來減小存儲成本.

值得注意的是，時序數(shù)據(jù)庫通常不需要支持事務，工業(yè)物聯(lián)網(wǎng)應用對傳感數(shù)據(jù)通常沒有強一致性要求，但是在金融行業(yè)如股票交易，需要保證每次操作的原子性和數(shù)據(jù)的強一致性，一些時序數(shù)據(jù)庫，如DolphinDB[24]通過2 階段提交（two-phase commit，2PC）[25-26]和多版本并發(fā)控制（multi version concurrency control，MVCC）[27]實現(xiàn)對事務的支持，被廣泛應用在量化金融交易中.

隨著邊緣計算的興起，時序數(shù)據(jù)庫需要被部署在邊緣設備中，與數(shù)據(jù)中心相比，邊緣計算存在資源受限的問題，而時序數(shù)據(jù)庫通常需要消耗大量的內(nèi)存、CPU 和磁盤資源.為了適應邊緣環(huán)境，一些時序數(shù)據(jù)庫提供了在邊緣側的數(shù)據(jù)同步功能，如InfluxDB的邊緣數(shù)據(jù)復制（edge data replication）[28]，也有一些為充分利用邊緣節(jié)點的資源專門面向邊緣環(huán)境研發(fā)的時序數(shù)據(jù)庫，如EdgeDB[29].

時序數(shù)據(jù)庫有多種實現(xiàn)方式，不同的時序數(shù)據(jù)庫采用了不同的數(shù)據(jù)結構，針對時序數(shù)據(jù)的特點使用各種優(yōu)化方法，其最終目的是實現(xiàn)高吞吐量數(shù)據(jù)攝取和低延遲復雜查詢.時序數(shù)據(jù)是寫密集型，寫入數(shù)據(jù)的頻率遠高于讀取數(shù)據(jù)的頻率，多數(shù)時序數(shù)據(jù)庫使用對寫密集型工作負載友好的數(shù)據(jù)結構，LSMtree[30]是時序數(shù)據(jù)存儲中最常使用的數(shù)據(jù)結構，在2.3 節(jié)中我們將會詳細介紹LSM-tree.在時序數(shù)據(jù)庫中，索引也是重要的數(shù)據(jù)結構，它是一種根據(jù)條件獲取相關信息的方法和結構，索引的作用有2 個：1）對時間序列的元數(shù)據(jù)索引，實現(xiàn)多維度復雜查詢；2）對寫入磁盤文件的時序數(shù)據(jù)索引，以快速定位文件中的歷史數(shù)據(jù).通常情況下，時間序列元數(shù)據(jù)的索引會保留在內(nèi)存中，對磁盤文件中數(shù)據(jù)的索引會部分或者全部保存在磁盤中.隨著時間序列元數(shù)據(jù)的增加，駐留在內(nèi)存中的索引大小會急劇增加，查詢效率也會變慢，如何高效地管理時間序列元數(shù)據(jù)是時序數(shù)據(jù)庫需要解決的一個關鍵問題.為實現(xiàn)高效的復雜查詢，不僅需要對文件中的時序數(shù)據(jù)索引，同時可能需要對多個文件中的數(shù)據(jù)重新整理寫入新的文件，使文件中的數(shù)據(jù)更有序，提高查詢效率.數(shù)據(jù)的重復讀取和寫入所需的額外I/O 導致讀放大[31]和寫放大[32]，寫放大會嚴重影響系統(tǒng)數(shù)據(jù)攝取吞吐量，還可能帶來額外的危害，如導致SSD 壽命降低[33]，寫放大和讀放大已經(jīng)成為時序數(shù)據(jù)庫技術中的重要問題.

2.3 時序數(shù)據(jù)庫中的數(shù)據(jù)結構

時序數(shù)據(jù)庫內(nèi)部使用了多種數(shù)據(jù)結構管理時間序列元數(shù)據(jù)和時序數(shù)據(jù).不同的數(shù)據(jù)結構有不同的優(yōu)缺點，沒有任何一個數(shù)據(jù)結構是最優(yōu)的，時序數(shù)據(jù)庫使用了多種優(yōu)化方法，同時作出權衡，使這些數(shù)據(jù)結構在管理時序數(shù)據(jù)時有更好的表現(xiàn).在本節(jié)中，我們首先概述不同存儲介質(zhì)的特點，然后介紹一些時序數(shù)據(jù)庫中常用到的數(shù)據(jù)結構.

通常情況下，機械硬盤（hard disk drive，HDD）[34]在時序數(shù)據(jù)存儲中占據(jù)主要地位，HDD 由磁頭、盤片等組成，在工作時盤片會以每分鐘幾千轉(zhuǎn)的速度高速旋轉(zhuǎn)，磁頭可以沿著盤片半徑的方向移動，在盤片的指定位置進行數(shù)據(jù)寫入和讀取操作，因此大部分數(shù)據(jù)結構和算法都針對HDD 的這些物理特性進行了優(yōu)化，通過順序?qū)懭牒妥x取[30,35-36]獲取更高的性能.然而，基于閃存（flash）技術的固態(tài)硬盤（solid state drive，SSD）的價格越來越便宜，數(shù)據(jù)中心已經(jīng)開始大范圍使用固態(tài)硬盤，SSD 完全由半導體芯片構成，沒有移動部件，在數(shù)據(jù)寫入和讀取時沒有機械部件的移動，對數(shù)據(jù)訪問模式不敏感，具有數(shù)據(jù)并行處理能力[37]，且SSD 具有有限的生命周期[38]，因此，大多數(shù)面向HDD 的優(yōu)化方法并不適用于SSD.除了SSD，非易失性內(nèi)存（non-volatile memory, NVM）[39]技術的出現(xiàn)對存儲系統(tǒng)提出了新的要求，NVM 在掉電后數(shù)據(jù)不會消失，具有字節(jié)可尋址（byte-addressable）特性，存儲密度比DRAM 更高，相比SSD，讀寫延遲降低到1/100，帶寬提高了5～10 倍[39-40]，這些特性使得NVM成為替代SSD 的合適選擇.

存儲是數(shù)據(jù)庫的核心功能，數(shù)據(jù)的特點、工作負載以及存儲器的固有特性共同決定了數(shù)據(jù)庫在設計存儲引擎時選擇的數(shù)據(jù)結構.為了充分利用磁盤順序?qū)懙奶攸c，數(shù)據(jù)庫通常采用緩存（cache）技術，在主內(nèi)存（RAM）中累積更多的數(shù)據(jù)，然后批量寫入磁盤.查詢時使用近似成員查詢過濾器加速確定某個時間序列的數(shù)據(jù)是否在磁盤文件中，減少昂貴的I/O 操作.在時序數(shù)據(jù)庫持久化存儲中，有一種被廣泛使用的數(shù)據(jù)結構：日志結構合并樹（log structured merge tree，LSM-tree）[30]，LSM-tree 是一種針對寫入密集型工作負載優(yōu)化的數(shù)據(jù)結構，非常適合時序數(shù)據(jù)寫入頻率高、讀取頻率低的場景，大多數(shù)時序數(shù)據(jù)庫使用了LSM-tree，并針對時序數(shù)據(jù)的特點采用了很多優(yōu)化方法.在介紹LSM-tree 之前我們首先介紹可用來提高查詢效率的過濾器（filter）.

2.3.1 近似成員查詢過濾器

近似成員查詢過濾器（approximate membership query filter，AMQ-Filter）用于快速估算一個元素在一個大的數(shù)據(jù)集合中是否存在，減少不必要的I/O 操作[41]，AMQ-Filters 可以幫助減小讀放大.AMQ-Filters 有一個重要特點，它可能導致假陽性（false positives），但是不會導致假陰性（false negatives）.假陽性是指當元素不在集合中時，查找結果為真；假陰性是指集合中存在元素時，查找結果為假.

布隆過濾器（Bloom filter）[42]是最常見的近似成員查詢過濾器，由一個m位的比特數(shù)組和k個哈希函數(shù)組成，每個哈希函數(shù)將元素映射到數(shù)組的一個位置，將該位置的比特位設置為1.查詢時需要計算所有k個哈希函數(shù)，如果比特數(shù)組中所有的對應位置都被設置為1，那么返回真.布隆過濾器需要在存儲空間和誤判率之間權衡，增加比特數(shù)組的位數(shù)和哈希函數(shù)的數(shù)量可以降低誤判率，但這會占用更多的存儲空間.一些時序數(shù)據(jù)庫使用布隆過濾器加速查詢磁盤文件是否存在指定時序的數(shù)據(jù)，減少不必要的磁盤I/O.除了布隆過濾器，還有一些常見的AMQFilters，如cuckoo 過濾器[43]和xor 過濾器[44].

2.3.2 日志結構合并樹

LSM-tree 最初是由O’Neil 等人[30]在1996 年提出，是面向?qū)懨芗凸ぷ髫撦d設計的數(shù)據(jù)結構，其寫入性能比傳統(tǒng)的B tree/B+ tree 以及其他樹型結構更好，被廣泛應用在數(shù)據(jù)庫系統(tǒng)中.LSM-tree 的核心思想是將小的隨機寫轉(zhuǎn)換成大的順序?qū)懀浞掷么疟P順序?qū)懙膬?yōu)勢.2011 年Google 開源了基于LSM-tree 的KV 數(shù)據(jù)庫LevelDB[36]，推動了LSM-tree 在數(shù)據(jù)庫領域的應用，其架構如圖1 所示.

圖1 日志結構合并樹和LevelDB 架構[31]Fig.1 LSM-tree and LevelDB architecture[31]

LSM-tree 由3 部分組成：

1）預寫日志（write ahead log，WAL）.以追加的方式將數(shù)據(jù)寫入日志文件中，用于系統(tǒng)異常重啟后的數(shù)據(jù)恢復.

2）內(nèi)存表（memtable）.分為可變內(nèi)存表（mutable memtable）和不可變內(nèi)存表（immutable memtable），是LSM-tree 的內(nèi)存模型，可以是哈希表（Hash table），也可以使用其他緩存技術，LevelDB 使用跳表（skip list）[45]作為memtable 的數(shù)據(jù)結構.

3）排序字符串表（sorted string table，sstable）.KV數(shù)據(jù)持久化存儲的文件格式，每個sstable 包含了一組鍵值對（key-value pair），按照key 的字典順序排序，允許高效地順序訪問.

我們首先按照數(shù)字順序分析LSM-tree 的數(shù)據(jù)傳播過程：

1）寫入或更新數(shù)據(jù)，每條KV 數(shù)據(jù)以追加的方式寫入WAL，WAL 會保證數(shù)據(jù)的持久性和一致性[46].在數(shù)據(jù)恢復階段，WAL 中的數(shù)據(jù)會被重新寫入內(nèi)存表.

2）數(shù)據(jù)寫入WAL 后，相同的數(shù)據(jù)被再次寫入可變內(nèi)存表中，該內(nèi)存表是KV 數(shù)據(jù)的緩存區(qū)，避免了小的隨機寫.

3）當可變內(nèi)存表的大小達到閾值后，會變成不可變內(nèi)存表，同時創(chuàng)建一個新的可變內(nèi)存表緩存新到來的數(shù)據(jù).

4）當不可變內(nèi)存表生成后，首先對其緩存的數(shù)據(jù)按照key 的字典順序排序，然后將排序后的KV 數(shù)據(jù)以數(shù)據(jù)塊的形式順序?qū)懭氪疟Psstable 文件，當文件大小超過閾值后，將關閉該文件，同時創(chuàng)建一個新的sstable 文件繼續(xù)寫入.

5）每個層級（level）只能容納一定大小的sstable文件，這個大小隨著層級的增加而呈指數(shù)增加，例如，LevelDB 在默認情況下將增長因子維持在10 倍的水平之間[36].由不可變內(nèi)存表寫入磁盤的sstable 文件處于level-0，由于持續(xù)地寫入，level-0 中sstable 文件數(shù)量快速增加，不同文件之間可能存在key 范圍重疊的情況，這時會觸發(fā)合并（compaction）操作，將當前層級中的1 個或者多個sstable 文件與下一層級中存在key范圍重疊的sstable 文件合并寫入一個新的sstable 文件，放入下一層級.合并結束后，刪除參與合并的sstable 文件.sstable 文件會不斷地被合并到下一層級，直到最高層級.

由于合并操作的存在，KV 數(shù)據(jù)會從level-0 不斷向下一層級移動，直到到達最高層級，即相同的數(shù)據(jù)會在不同層級之間重復寫入，這就產(chǎn)生了寫放大[32]，在LevelDB 中寫放大可以達到50 倍[47]，寫放大問題會導致數(shù)據(jù)的攝取吞吐量降低.

在查詢過程中，會從內(nèi)存表和不同層級的sstable 文件中查詢數(shù)據(jù)，當進行大范圍合并操作時，還會導致尾延遲（tail latency），尾延遲也被稱為“高百分比延遲”，是相對較少但是響應時間較長的一小部分請求的延遲，是客戶端很少看到的高延遲.

基于LSM-tree 的時序數(shù)據(jù)存儲，key 是由測量指標、標簽組合、測量字段鍵（field key）構成，value 是由測量字段值（field value）和時間戳構成，與基于LSM-tree 的KV 存儲相比，基于LSM-tree 的時序數(shù)據(jù)存儲需要分別處理測量值和時間戳.時序數(shù)據(jù)通常具有多個標簽組合，當標簽集的基數(shù)增加時，基于標簽組合的key 的數(shù)量會急劇膨脹，而key 通常是在內(nèi)存中索引的，內(nèi)存資源占用也會急劇增加.一些時序數(shù)據(jù)庫將2.3.1 節(jié)提到的AMQ-Filter 與LSM-tree 一起使用，以減小讀放大.沒有任何一個數(shù)據(jù)結構是完美的，有很多優(yōu)化方法被應用在時序數(shù)據(jù)庫中來提高性能，大多是通過在各種性能之間權衡來實現(xiàn)的，也有一些更新穎的方法被提出，例如Pebblesdb[32]提出了FLSM（fragmented log structured merge tree），與RocksDB[48]相比，寫放大從42 減小到17，同時寫入吞吐量提高了6.7 倍.

3 工業(yè)物聯(lián)網(wǎng)海量時序數(shù)據(jù)管理面臨的挑戰(zhàn)

工業(yè)物聯(lián)網(wǎng)中的時序數(shù)據(jù)具有產(chǎn)生頻率高、數(shù)據(jù)規(guī)模大、數(shù)據(jù)維度復雜的特點，同時與工業(yè)物聯(lián)網(wǎng)相關的應用服務在時序數(shù)據(jù)管理上產(chǎn)生了新的工作負載，其中包括3 個方面.

1）高吞吐量數(shù)據(jù)攝取.時序數(shù)據(jù)庫需要24 h×365天全年穩(wěn)定地處理每秒數(shù)百萬時序數(shù)據(jù)點的寫入請求，由于工業(yè)環(huán)境的復雜性，時序數(shù)據(jù)經(jīng)常因為設備故障、網(wǎng)絡擁堵等原因出現(xiàn)數(shù)據(jù)丟失或者無法有序到達，對時序數(shù)據(jù)高速攝取帶來了困難.

2）低延遲多維度復雜查詢.工業(yè)物聯(lián)網(wǎng)通常需要2 種形式的查詢：一是查詢傳感器的最新值實現(xiàn)對設備的實時監(jiān)控；二是基于時間窗口和標簽值過濾的多維度復雜查詢，通過分析多個時間序列的關聯(lián)信息，對設備進行故障診斷和預測分析.

3）大規(guī)模歷史數(shù)據(jù)存儲.工業(yè)物聯(lián)網(wǎng)產(chǎn)生的數(shù)據(jù)量非常大，例如GoldWind 風力發(fā)電公司2 萬個風力發(fā)電機每秒產(chǎn)生接近5 億個時序數(shù)據(jù)點，這些數(shù)據(jù)通常需要長期存儲，甚至永久存儲，以便對生產(chǎn)設備全生命周期管理以及事故追溯.

時序數(shù)據(jù)庫是解決海量時序數(shù)據(jù)高效管理的有效途徑，面對工業(yè)物聯(lián)網(wǎng)中海量的時序數(shù)據(jù)，時序數(shù)據(jù)庫會面臨3 個挑戰(zhàn)，如表2 所示.這3 個挑戰(zhàn)分別是：1）需要高效地管理復雜的時間序列元數(shù)據(jù)；2）需要應對工業(yè)物聯(lián)網(wǎng)特殊的工作負載；3)需要降低海量歷史數(shù)據(jù)存儲的成本.

Table 2 Challenges, Key Technologies and Descriptions of Time Series Databases表2 時序數(shù)據(jù)庫面臨的挑戰(zhàn)、關鍵技術和描述

3.1 時間序列元數(shù)據(jù)管理

工業(yè)物聯(lián)網(wǎng)中的每個傳感器都有多個與之關聯(lián)的標簽，這些標簽表示傳感器的靜態(tài)屬性，如所屬的廠區(qū)、設備、制造商等.在數(shù)據(jù)寫入和查詢時，首先需要獲取數(shù)據(jù)對應的時間序列元數(shù)據(jù)，通過對時間序列建立索引，可以提高定位元數(shù)據(jù)的速度.

但是當時序數(shù)據(jù)集存在大量的標簽集合時，時序數(shù)據(jù)庫會對每一個標簽組合創(chuàng)建一個時間序列，并在內(nèi)存中建立索引，隨著時間的推移，時序數(shù)據(jù)的基數(shù)越高，索引就越大，內(nèi)存占用越大，建立索引以及從索引中查詢會占用更多的CPU 和內(nèi)存資源，在數(shù)據(jù)攝取和查詢時，大量的資源和時間被消耗在對時間序列索引的建立和查找中.

3.2 工業(yè)物聯(lián)網(wǎng)特殊工作負載

工業(yè)物聯(lián)網(wǎng)中的時序數(shù)據(jù)是寫入密集型，數(shù)據(jù)的寫入頻率遠高于讀取頻率，同時具有時間局部性（temporal locality）[49]，數(shù)據(jù)冷熱分明，熱數(shù)據(jù)是最近接入被頻繁訪問的數(shù)據(jù)，冷數(shù)據(jù)是訪問頻次較低的歷史數(shù)據(jù)，熱數(shù)據(jù)的價值遠高于冷數(shù)據(jù)，需要被頻繁訪問和分析.時序數(shù)據(jù)庫需要設計面向?qū)懭朊芗凸ぷ髫撦d的存儲引擎，同時需要使用優(yōu)化方法在內(nèi)存中高效地管理熱數(shù)據(jù).

3.3 海量歷史數(shù)據(jù)存儲

工業(yè)物聯(lián)網(wǎng)持續(xù)產(chǎn)生的海量歷史數(shù)據(jù)最終需要被寫入磁盤持久化存儲，存儲成本隨著數(shù)據(jù)的不斷寫入而持續(xù)增加，時序數(shù)據(jù)庫需要通過各種方法減小海量歷史數(shù)據(jù)存儲的成本.

4 時序數(shù)據(jù)庫的分類和特點

從廣義上來說，任何針對時序數(shù)據(jù)存儲進行優(yōu)化的數(shù)據(jù)庫都應該屬于時序數(shù)據(jù)庫系統(tǒng)的范疇.關系數(shù)據(jù)庫系統(tǒng)也可以用來管理時序數(shù)據(jù)，關系數(shù)據(jù)庫通?；贐+tree，這種數(shù)據(jù)結構在處理單個時間序列的批量數(shù)據(jù)寫入時具有很高的性能，但是在同時處理數(shù)千數(shù)萬個時間序列的批量數(shù)據(jù)寫入請求時，數(shù)據(jù)寫入最終看起來更像是隨機寫入，而不是僅追加寫入，因此隨著時序數(shù)據(jù)規(guī)模的不斷增長，關系數(shù)據(jù)庫性能會急劇下降，不適用于真實世界時序數(shù)據(jù)場景.與關系數(shù)據(jù)庫相比，一些KV 存儲系統(tǒng)更適合管理時序數(shù)據(jù)，特別是基于LSM-tree 的KV 數(shù)據(jù)庫，如LevelDB[36]，InfluxDB 在第1 個版本中使用LevelDB作為持久化存儲引擎[50]，LevelDB 中的key 空間是有序的，在處理時序數(shù)據(jù)時，只有時間戳在key 中，才能夠快速查詢指定時間范圍內(nèi)的數(shù)據(jù).LevelDB 將數(shù)據(jù)分割成許多小文件，隨著時序數(shù)據(jù)規(guī)模的增加，包含時間戳的key 的數(shù)量急劇膨脹，單個進程打開的文件句柄快速增加，最終可能導致操作系統(tǒng)的資源被耗盡，這是基于LSM-tree 的KV 數(shù)據(jù)庫在處理時序數(shù)據(jù)時無法解決的問題，因為LSM-tree 在處理時序數(shù)據(jù)時沒有考慮到時序數(shù)據(jù)的特點（每一個數(shù)據(jù)點都與一個時間戳關聯(lián)）和特殊工作負載（基于時間范圍的數(shù)據(jù)查詢）.

本文的研究范圍是針對時序數(shù)據(jù)存儲進行優(yōu)化的時序數(shù)據(jù)庫，這類數(shù)據(jù)庫不僅能夠高效地存儲大規(guī)模時序數(shù)據(jù)，而且能夠滿足時序數(shù)據(jù)場景下復雜的多維查詢和計算要求.本文按照存儲架構對時序數(shù)據(jù)庫進行了分類，每一類時序數(shù)據(jù)庫的存儲架構如圖2 所示.按照存儲架構，時序數(shù)據(jù)庫可以分為4 類：1）內(nèi)存型時序數(shù)據(jù)庫；2）基于關系數(shù)據(jù)庫的時序數(shù)據(jù)庫；3）基于KV 存儲的時序數(shù)據(jù)庫；4）原生時序數(shù)據(jù)庫.表3 列出了每一類的代表性系統(tǒng)以及數(shù)據(jù)結構，并對時序數(shù)據(jù)讀寫性能分級和歷史數(shù)據(jù)壓縮性能分級，其中每個分級通過高、中、低3 個等級衡量.

圖2 時序數(shù)據(jù)庫的4 類存儲架構圖Fig.2 Four types of storage architecture diagram of time series database

Table 3 Classification and Comparison of Storage Architectures for Time Series Databases表3 時序數(shù)據(jù)庫的存儲架構分類與比較

4.1 內(nèi)存型時序數(shù)據(jù)庫

內(nèi)存型時序數(shù)據(jù)庫使用內(nèi)存作為存儲介質(zhì)，在內(nèi)存中緩存持續(xù)攝取的時序數(shù)據(jù)，與基于磁盤存儲的時序數(shù)據(jù)庫相比，內(nèi)存型時序數(shù)據(jù)庫具有更高的寫入吞吐量和更低的訪問延遲.Gorilla[7]是一個內(nèi)存型時序數(shù)據(jù)庫，在將監(jiān)控數(shù)據(jù)寫入HBase[51]之前，起到高速緩存的作用.Gorilla 在內(nèi)存中使用TSmap（timeseries map）數(shù)據(jù)結構緩存時序數(shù)據(jù)，這些數(shù)據(jù)通過多種編碼方法壓縮以減少存儲空間.為了應對單節(jié)點系統(tǒng)故障，Gorilla 使用了3 種磁盤文件：日志文件（log file）、完整數(shù)據(jù)塊文件（complete block file）和檢查點文件（checkpoint file）.攝取的時序數(shù)據(jù)以追加（append-only）的方式寫入日志文件，用于在系統(tǒng)異常崩潰重啟后恢復內(nèi)存中丟失的數(shù)據(jù)，考慮到不提供事務支持，Gorilla 沒有使用預寫日志文件（WAL），而是當數(shù)據(jù)被緩存到64 KB 后觸發(fā)寫日志操作，在系統(tǒng)因異常崩潰時可能會丟失少量的數(shù)據(jù)，但是與預寫日志相比，這種方式具有更高的寫入吞吐量.每2 h，Gorilla 將緩存的時序數(shù)據(jù)拷貝到磁盤完整數(shù)據(jù)塊文件，一旦1 個文件寫入完成，Gorilla 就會觸發(fā)1 個檢查點文件并刪除相應的日志.為了提高查詢效率，Gorilla 使用了多種壓縮算法壓縮時間戳和浮點數(shù)據(jù)，與傳統(tǒng)的基于HBase 的時序數(shù)據(jù)庫相比，極大地減小了查詢時延，同時提高了寫入吞吐量.

內(nèi)存型時序數(shù)據(jù)庫通常用作時序數(shù)據(jù)高速緩存，在內(nèi)存中實現(xiàn)數(shù)據(jù)的寫入、查詢和聚合，適用于對熱數(shù)據(jù)訪問頻次高的場景.

4.2 基于關系數(shù)據(jù)庫的時序數(shù)據(jù)庫

基于關系數(shù)據(jù)庫研發(fā)的時序數(shù)據(jù)庫，通過擴展關系數(shù)據(jù)庫以優(yōu)化時序數(shù)據(jù)存儲，繼承了關系數(shù)據(jù)庫的生態(tài)，例如原生支持標準SQL.TimescaleDB[12]通過擴展PostgreSQL[19]實現(xiàn)時序數(shù)據(jù)管理，可以在整個PostgreSQL 實例中運行，TimescaleDB 通過在PostgreSQL 的查詢計劃器、數(shù)據(jù)模型和執(zhí)行引擎的深處添加鉤子，高度定制化擴展層，基于該擴展模型，TimescaleDB 可以利用PostgreSQL 的多個屬性，例如可靠性、安全性以及豐富的第三方工具.基于關系數(shù)據(jù)庫的時序數(shù)據(jù)庫提供了全部的SQL 功能，同時支持事務，適用于數(shù)據(jù)分析高度依賴SQL 功能以及對數(shù)據(jù)一致性要求高的場景.但是由于關系數(shù)據(jù)庫使用行存儲模型，數(shù)據(jù)壓縮效率與采用列存儲的時序數(shù)據(jù)庫相比有較大的差距，且部署和運維復雜度更高.

4.3 基于KV 存儲的時序數(shù)據(jù)庫

基于KV 存儲的時序數(shù)據(jù)庫，通過擴展NoSQL數(shù)據(jù)庫實現(xiàn)時序數(shù)據(jù)存儲，將攝取的時序數(shù)據(jù)構建成KV 模型，底層以KV 形式將數(shù)據(jù)持久化在分布式文件系統(tǒng)（distributed file system，DFS）上，由于使用了分布式文件系統(tǒng)，這類時序數(shù)據(jù)庫具有很高的擴展性，但是存在部署復雜、運維困難的問題.

4.4 原生時序數(shù)據(jù)庫

原生時序數(shù)據(jù)庫是面向時序數(shù)據(jù)存儲全新研發(fā)的時序數(shù)據(jù)庫，該類型時序數(shù)據(jù)庫不依賴第三方存儲，使用列存儲模型，提供極致的數(shù)據(jù)攝取、查詢和壓縮能力，部署和運維更加簡單.但是原生時序數(shù)據(jù)庫支持的數(shù)據(jù)模型有限，通常只支持整型、布爾型、浮點型和字符串4 種數(shù)據(jù)類型，數(shù)據(jù)模型豐富度以及對SQL 的支持程度不如基于關系數(shù)據(jù)庫的時序數(shù)據(jù)庫，且通常不支持事務，難以處理對數(shù)據(jù)一致性要求高的任務，更適合工業(yè)物聯(lián)網(wǎng)場景.

5 時序數(shù)據(jù)庫關鍵技術

與其他類型的數(shù)據(jù)相比，時序數(shù)據(jù)的工作負載具有一些截然不同的特性，包括持續(xù)高吞吐量數(shù)據(jù)攝取、多維度復雜元數(shù)據(jù)管理、基于時間范圍和標簽值的多條件復雜查詢、數(shù)據(jù)生命周期管理和歷史數(shù)據(jù)管理.從時序數(shù)據(jù)工作負載的特性中可以凝練出4 類關鍵技術：時間序列索引優(yōu)化技術、內(nèi)存數(shù)據(jù)組織技術、高吞吐量數(shù)據(jù)攝取和低延遲數(shù)據(jù)查詢技術、海量歷史數(shù)據(jù)低成本存儲技術.其中，時間序列索引優(yōu)化技術是與解決時序數(shù)據(jù)高基數(shù)問題相關的技術（見5.1 節(jié)）.內(nèi)存數(shù)據(jù)組織技術是時序數(shù)據(jù)庫面向時序數(shù)據(jù)的特殊工作負載在內(nèi)存中組織管理數(shù)據(jù)的技術（見5.2 節(jié)）.高吞吐量數(shù)據(jù)攝取和低延遲數(shù)據(jù)查詢技術是關于如何減小寫放大和讀放大的技術（見5.3 節(jié)）.海量歷史數(shù)據(jù)低成本存儲技術是關于如何減小海量時序數(shù)據(jù)存儲成本的技術（見5.4 節(jié)）.表4 列出了每一類技術的關鍵技術.

Table 4 Overview of Key Technologies of Time Series Databases表4 時序數(shù)據(jù)庫關鍵技術總覽

5.1 時間序列索引優(yōu)化技術

當時序數(shù)據(jù)的基數(shù)很大時，時序數(shù)據(jù)庫寫入和查詢的性能會急劇降低，因為大量的內(nèi)存和CPU 資源被用在時間序列索引的建立和查找中，時序數(shù)據(jù)高基數(shù)已經(jīng)成為時序數(shù)據(jù)庫不得不面對的難題.時間序列索引優(yōu)化技術是為了解決時序數(shù)據(jù)高基數(shù)問題，主要分為2 類：1）面向索引模型和架構的優(yōu)化技術； 2）面向基數(shù)分析的索引優(yōu)化技術.

5.1.1 高基數(shù)的定義

對于時序數(shù)據(jù)而言，高基數(shù)問題變得更加復雜.時間序列高基數(shù)問題[61]是指時序數(shù)據(jù)庫在處理復雜的時間序列元數(shù)據(jù)時遇到的資源占用以及性能問題.在數(shù)據(jù)庫中，基數(shù)是指存儲在數(shù)據(jù)庫中的唯一數(shù)據(jù)集的數(shù)量，具體來說，它指的是在一個表列中可能的唯一值的總數(shù).時間序列基數(shù)表示了時間序列元數(shù)據(jù)的復雜程度，時序數(shù)據(jù)是和描述這些數(shù)據(jù)的元數(shù)據(jù)相關聯(lián)的，且通常會被索引以提高多維度查詢性能.時序數(shù)據(jù)的基數(shù)是由每個單獨索引列的基數(shù)的叉積來定義.例如，一個省的街區(qū)視頻監(jiān)控與1 000個街道ID（street_id=1, 2, …, 1 000）、5 家供應商ID（vendor_id=1, 2, …, 5）、1 000 臺設備ID（device_id=1,2, …, 1 000）共3 個標簽關聯(lián)，那么總基數(shù)為1 000×5×1 000=5 000 000，通過對每個設備索引，可以快速地找到street_id=5，vendor_id=2，device_id=300 的攝像裝置.當增加了一個新的標簽值時，如vendor_id=6，那么基數(shù)會呈指數(shù)級別的增長變成1 000×6×1 000=6 000 000.因此，時序數(shù)據(jù)的高基數(shù)由2 個原因?qū)е耓62]：1）1 個時間序列有多個索引列；2）每個索引列包含多個唯一值.

高基數(shù)會帶來下面2 個問題：1）高基數(shù)增加了定位唯一值的時間，導致寫入吞吐量降低，查詢性能降低；2）高基數(shù)同時導致在內(nèi)存中索引的唯一列的數(shù)量呈指數(shù)增長，內(nèi)存占用急劇增加.解決時序數(shù)據(jù)的高基數(shù)問題，需要解決2 個具體的問題：1）在內(nèi)存中索引時間序列，提高寫入和查詢性能；2）當增加標簽時，避免數(shù)據(jù)集基數(shù)呈指數(shù)級增長.多種方法被用來解決時序數(shù)據(jù)高基數(shù)問題，包括時序數(shù)據(jù)模型優(yōu)化、索引結構優(yōu)化和元數(shù)據(jù)存儲架構優(yōu)化等.

5.1.2 面向索引模型和架構的優(yōu)化技術

InfluxDB[10]設計了專屬的時間序列索引（time series index，TSI）[55]管理時間序列元數(shù)據(jù)，TSI 使用了基于LSM-tree 的key-value 模型，key 由用于定位唯一時間序列的測量（measurement）指標、標簽組合和測量字段構成.TSI 對key 進行哈希運算，將key 映射成無符號64 b 整數(shù)，將冗長的字節(jié)數(shù)組轉(zhuǎn)換成數(shù)值索引在內(nèi)存中，大大減小了時間序列索引的內(nèi)存占用，TSI 在高基數(shù)情況下的效果更好.通過Bitmap 進行基于標簽值的多條件過濾查詢，并使用了LRU Cache[63]緩存活躍的時間序列ID，將不活躍的時間序列索引存儲在磁盤文件，并動態(tài)更新LRU Cache.TSI 可以支持千萬級別的時間序列，官方給出基數(shù)上限為3 000萬.但是當持續(xù)增加標簽或標簽值時，由測量指標、標簽集和測量字段唯一組合構造的key 的數(shù)量呈指數(shù)級增加，TSI 的寫入和查詢性能開始明顯降低.為了解決時序數(shù)據(jù)高基數(shù)問題，InfluxDB 重新設計了新的存儲引擎IOx[64]，與TSI 將每個時間序列作為一列不同，IOx 引擎將每個標簽（tag）和字段（field）存儲為一個列，這樣大大減少了列的總數(shù)，基數(shù)降低，從而提高了性能.

TimescaleDB[12]是基于PostgreSQL[19]的時序數(shù)據(jù)庫，首先按照時間范圍對數(shù)據(jù)進行分區(qū)（chunk），然后在每個數(shù)據(jù)分區(qū)上默認使用B-tree[65]數(shù)據(jù)結構對時序數(shù)據(jù)標簽建立索引.索引是在分區(qū)級別上，因此索引的大小與該分區(qū)的時間范圍內(nèi)時序數(shù)據(jù)的基數(shù)相同.TimescaleDB 可以根據(jù)工作負載手動添加和刪除索引，在離散或者連續(xù)字段上創(chuàng)建索引，同時支持對多個列創(chuàng)建聯(lián)合索引.與InfluxDB 中基于LSM-tree的TSI 索引不同，TimescaleDB 采用了B-tree 數(shù)據(jù)結構，因此在改變索引時不需要重寫所有的歷史數(shù)據(jù)，且基于B-tree 的索引對關系運算（如＜，＜=，=，＞=，＞）更友好.

QuestDB[57]使用HashMap 索引唯一列，為了解決高基數(shù)問題，QuestDB 對索引列上的HashMap 操作進行了大規(guī)模并行化處理，同時在SQL 引擎中使用SIMD[66]處理繁重的工作，這樣可以盡可能并行地執(zhí)行與索引和HashMap 查找相關的工作.

TDengine 從數(shù)據(jù)模型、元數(shù)據(jù)存儲架構2 個方面來應對時序數(shù)據(jù)高基數(shù)問題[61].首先，TDengine 為每個數(shù)據(jù)源創(chuàng)建一個表，通過一致性哈希將表分布在多個虛擬節(jié)點中，當表的數(shù)量增加時，可以通過創(chuàng)建更多虛擬節(jié)點水平擴展，將存儲和查詢元數(shù)據(jù)的壓力分攤到多個虛擬節(jié)點中，減少定位表的延遲，保證標簽過濾操作具有較小的延遲.其次，TDengine 引入了超級表的概念，超級表將一組標簽集與對應的每個表關聯(lián)，同時將超級表數(shù)據(jù)與時序數(shù)據(jù)分開存儲，使用B-tree[65]來索引標簽存儲元數(shù)據(jù)，在通過標簽值過濾查詢時，從元數(shù)據(jù)存儲中搜索滿足過濾條件的表，然后從時序數(shù)據(jù)存儲中查詢關聯(lián)的數(shù)據(jù)并完成聚合.

5.1.3 面向基數(shù)分析的索引優(yōu)化技術

VictoriaMetrics[58]使用 mergeset 數(shù)據(jù)結構存儲時間序列元數(shù)據(jù)，mergeset 是一種以LSM-tree 為基礎的數(shù)據(jù)結構，為數(shù)據(jù)寫入、查詢做了特殊的優(yōu)化，同時支持按字符串前綴快速進行范圍掃描.為了解決時序數(shù)據(jù)高基數(shù)問題，VictoriaMetrics 提供了基數(shù)分析（cardinality explorer）[67]功能，可以識別并移除高基數(shù)的來源.

DolphinDB[24]發(fā)現(xiàn)在真實世界中存在很多不活躍的時序序列，這些被索引的不活躍的時間序列是導致高基數(shù)的主要原因，與VictoriaMetrics 對高基數(shù)問題的處理方法不同，DolphinDB 允許自定義標簽值組合在索引中的映射關系，可以將多個不活躍的時間線序里的標簽值組合映射到同一個索引列中，大大降低了被索引列的基數(shù).查詢時，將這些被映射到同一個索引列的數(shù)據(jù)全部加載到內(nèi)存中過濾.根據(jù)DolphinDB 的實驗，通過將多個不活躍時間序列映射到一個索引列，可以很好地解決時序數(shù)據(jù)高基數(shù)問題，寫入性能大幅度提升，而點查詢性能僅僅慢了2 ms 左右.

理論上時序數(shù)據(jù)的基數(shù)可能是無限的，例如，當標簽中引入了時間戳，隨著時間的推移，這個數(shù)據(jù)集的最大基數(shù)是無限大的.現(xiàn)有的優(yōu)化方法都是在某些方面作出權衡，如資源占用與查詢效率之間的權衡，將能管理的時序數(shù)據(jù)基數(shù)不斷提高，但是仍然無法解決基數(shù)無限增長的問題，高基數(shù)仍然是時序數(shù)據(jù)庫技術中需要研究的重要問題.

5.2 內(nèi)存數(shù)據(jù)組織技術

時序數(shù)據(jù)具有時間局部性（temporal locality）[49]，數(shù)據(jù)冷熱分明，熱數(shù)據(jù)是最近接入被頻繁訪問的數(shù)據(jù)，冷數(shù)據(jù)是訪問頻次較低的歷史數(shù)據(jù).在時序數(shù)據(jù)場景中，熱數(shù)據(jù)的價值遠高于冷數(shù)據(jù)，需要被頻繁訪問和分析.在內(nèi)存中緩存最近接入的數(shù)據(jù)是處理熱數(shù)據(jù)的重要方法，但是隨著緩存的數(shù)據(jù)量增加，內(nèi)存資源占用會持續(xù)增加，同時時序數(shù)據(jù)高基數(shù)導致需要更多內(nèi)存資源索引時間序列，因此需要采取適應性的內(nèi)存數(shù)據(jù)組織技術.該類技術使用較少的內(nèi)存資源高效地處理高熱度的時序數(shù)據(jù)以應對傾斜的工作負載，以及減少高基數(shù)時間序列索引的內(nèi)存資源占用.本節(jié)將介紹2 類內(nèi)存數(shù)據(jù)組織技術，包括：1）基于內(nèi)存壓縮的數(shù)據(jù)組織技術； 2）對齊時間序列.

5.2.1 基于內(nèi)存壓縮的數(shù)據(jù)組織技術

1）壓縮索引.ByteSeries[59]提出了一種壓縮倒排索引（compressed inverted index），如圖3 所示，該技術可以有效地壓縮元數(shù)據(jù)，元數(shù)據(jù)的內(nèi)存占用減少了60%且保持了多維查詢的高效性.

圖3 壓縮倒排索引[59]Fig.3 Compressed inverted index[59]

壓縮倒排索引分別對索引中的鍵和值進行壓縮.首先根據(jù)標簽組合構建倒排索引，倒排索引由鍵和值2 部分數(shù)據(jù)組成，將所有的值數(shù)組串聯(lián)成一個數(shù)組，然后使用另一個數(shù)組記錄每個倒排索引數(shù)組的值在該串聯(lián)數(shù)組中的起始偏移量，同時將倒排索引中每個鍵對應的值更改為對應的偏移量.最后，用前綴樹[68]壓縮倒排索引的鍵，并將串聯(lián)數(shù)組和記錄偏移量的數(shù)組壓縮成一個數(shù)組（compressed_list）.在標簽過濾查詢時，首先從前綴樹中找到每個標簽鍵對應的偏移量；然后將compressed_list解壓縮為倒排索引數(shù)組和偏移量數(shù)組，從偏移量數(shù)組獲得倒排索引的位置；最后從倒排索引數(shù)組中讀取倒排索引，并對查詢的結果進行聚合，完成查詢.

ByteSeries 在內(nèi)存中對每個時間序列的數(shù)據(jù)點進行了壓縮，同時為了避免數(shù)據(jù)壓縮的開銷影響數(shù)據(jù)攝取吞吐量，使用分段內(nèi)存方法（segmented memory approach）來平滑這種影響，分段內(nèi)存結構如圖4 所示.

圖4 分段內(nèi)存和活躍數(shù)據(jù)段[59]Fig.4 Segment memory and active segment[59]

內(nèi)存中有2 種數(shù)據(jù)結構：活躍緩沖區(qū)（active buffer）和靜態(tài)緩沖區(qū)（static buffer），活躍緩沖區(qū)被劃分為多個數(shù)據(jù)段（segment），數(shù)據(jù)段使用了簡單的數(shù)據(jù)結構來實現(xiàn)高速攝取目標，不執(zhí)行數(shù)據(jù)壓縮.數(shù)據(jù)首先寫入活躍緩沖區(qū)，通過計算序列鍵的哈希值確定寫入的數(shù)據(jù)段.當數(shù)據(jù)段大小達到閾值時，使用Gorilla[7]算法對時序數(shù)據(jù)壓縮，并轉(zhuǎn)換成靜態(tài)緩沖區(qū)的格式，最后對靜態(tài)緩沖區(qū)的數(shù)據(jù)進行合并存儲.通過對靜態(tài)緩沖區(qū)分片（shard），數(shù)據(jù)壓縮和轉(zhuǎn)換操作可以在不同數(shù)據(jù)段上并行執(zhí)行，在數(shù)據(jù)段級別上進行數(shù)據(jù)壓縮和轉(zhuǎn)換，內(nèi)存開銷與參與壓縮和轉(zhuǎn)換的數(shù)據(jù)段的大小相同，小于整個活躍緩沖區(qū)的大小，同時避免了數(shù)據(jù)壓縮和轉(zhuǎn)換操作導致的系統(tǒng)讀寫操作短暫暫停，在保持高壓縮率的同時減小對數(shù)據(jù)攝取吞吐量的影響.

2）壓縮內(nèi)存表.DolphinDB[24]發(fā)現(xiàn)在HDD 中4 KB隨機讀的時延為5～15 ms，SSD 的4 KB 隨機讀時延為100～200 μs，而在內(nèi)存中4 KB 的Snappy[69]算法解壓縮只需要1～2 μs，遠小于HDD 和SSD 的4 KB 隨機讀時延.Dolphin 提出了壓縮內(nèi)存表，對緩沖區(qū)內(nèi)的每列時序數(shù)據(jù)使用Snappy 算法壓縮，將更多的時序數(shù)據(jù)緩存在內(nèi)存中，在相同大小的內(nèi)存中可以多緩存5 倍的數(shù)據(jù).

5.2.2 對齊時間序列

在真實場景中，1 個實體的多個測量值通常被同時采樣，這些測量值會具有相同的時間列，IoTDB 提出了對齊時間序列模型[70]，并將這樣一組時間序列稱為對齊時間序列，如圖5 所示.通過創(chuàng)建對齊時間序列，時間戳列在內(nèi)存中只需要被存儲1 次，減少了內(nèi)存占用.

圖5 時間序列和對齊時間序列Fig.5 Time series and aligned time series

5.3 高吞吐量數(shù)據(jù)攝取和低延遲數(shù)據(jù)查詢技術

物聯(lián)網(wǎng)場景下的工作負載通常是寫密集型，時序數(shù)據(jù)的寫入頻率遠高于讀取頻率，因此多數(shù)時序數(shù)據(jù)庫使用對寫密集型工作負載友好的LSM-tree 數(shù)據(jù)結構.但是LSM-tree 天生具有寫放大和讀放大的問題，寫放大[32]是指存儲系統(tǒng)執(zhí)行的總寫入I/O 相對于用戶總寫入數(shù)量增加的倍數(shù)，寫放大導致器件頻繁磨損，對硬件的壽命產(chǎn)生危害[71]，同時也會降低寫吞吐量[72]，增加系統(tǒng)的讀寫時延，例如，在RocksDB中，寫放大會導致寫吞吐量降低到讀吞吐量的10%[73].讀放大[31]是指在查詢時，實際讀取的數(shù)據(jù)大小大于用戶實際獲得的數(shù)據(jù)大小，與寫放大一樣，讀放大也會增加系統(tǒng)延遲，但是對于寫密集型工作負載，寫放大的危害更大.減小寫放大和讀放大是提高時序數(shù)據(jù)庫寫入吞吐量以及減小查詢延遲的關鍵，在寫密集型工作負載中，減小寫放大比減小讀放大更重要.本節(jié)首先分析寫放大和讀放大產(chǎn)生的原因以及二者的權衡關系，然后介紹減小寫放大和讀放大的技術.

5.3.1 寫放大和讀放大的權衡

持續(xù)攝取的時序數(shù)據(jù)最終會被存儲在磁盤文件中，同一個時間序列的數(shù)據(jù)可能分布在多個文件中，為了提高數(shù)據(jù)的壓縮比和查詢效率，存儲引擎會對多個文件進行合并，盡可能將同一個時間序列的數(shù)據(jù)存儲在同一個文件中，使文件中的數(shù)據(jù)更有序.文件合并時數(shù)據(jù)的重復寫入所需的額外I/O 導致了寫放大，而從多個文件中查詢一個時間序列的數(shù)據(jù)時產(chǎn)生的額外I/O 導致了讀放大.

基于LSM-tree 的時序數(shù)據(jù)存儲，將離散的隨機I/O 轉(zhuǎn)換為批量的順序I/O，充分利用磁盤順序?qū)懙奶攸c，顯著提高了寫性能，但是同時帶來了寫放大和讀放大.3 個原因?qū)е铝藢懛糯螅?）時序數(shù)據(jù)首先寫入WAL，相同的數(shù)據(jù)會被再次寫入緩存，并最終寫入磁盤文件，WAL 導致數(shù)據(jù)重復存儲；2）LSM-tree 會在相鄰層級之間合并文件，相同的數(shù)據(jù)可能會從level-0 到最高層級重復寫入，這是產(chǎn)生寫放大的主要原因；3）1 個實體可能在同一時間點產(chǎn)生多個采集值，如1個智能電表1 次需要采集電流、電壓2 個值，以〈電流，時間戳〉，〈電壓，時間戳〉的形式存儲，每次會重復存儲時間戳.而讀放大的原因有2 個：1）1 個時間序列的數(shù)據(jù)可能分布在多個文件中，查詢數(shù)據(jù)時，需要從level-0 層級中的文件開始查找，直到最高層級，有些文件并不包含目標數(shù)據(jù)，這是產(chǎn)生讀放大的主要原因，雖然可以通過一些技術方案，如布隆過濾器或文件級別的索引降低從無關文件中讀取數(shù)據(jù)的概率，但是無法消除這些不必要的讀取操作；2）從磁盤文件中讀取數(shù)據(jù)時，通常是以數(shù)據(jù)塊(block)為讀取單位，如一個數(shù)據(jù)塊的大小為4 KB，可能會將不需要的數(shù)據(jù)加載到內(nèi)存，這也會導致讀放大.

在以LSM-tree 為基礎的時序數(shù)據(jù)存儲中，寫放大和讀放大是一種典型的權衡.為了提高讀性能，LSM-tree 通過合并操作，將level-i層級與level-i+1 層級中存在時間序列范圍重疊的多個文件合并成有序的文件并放入level-i+1 層級，數(shù)據(jù)的重復寫入導致了寫放大；為了提高寫性能，LSM-tree 通過緩存數(shù)據(jù)，將隨機I/O 轉(zhuǎn)換成順序I/O，使各層級中的文件存在時間序列范圍重疊，查詢時需要從多個層級的文件中讀取數(shù)據(jù)，導致讀放大.

5.3.2 減小寫放大

在LSM-tree 中，每層會存在至少1 組按照key 有序排列的文件，不同文件之間沒有key 范圍重疊，這一組文件被稱為一個sorted run.按照每層sorted run的數(shù)量，LSM-tree 的合并策略分為Leveled 和Tiered兩種，如圖6 所示.對于Leveled 合并策略，每一層級只能有一個sorted run，當觸發(fā)合并操作時，會將當前層級的文件與下一層級存在鍵范圍重疊的文件合并為有序文件，放到下一層級，合并操作涉及2 個層級的文件，Leveled 合并策略對順序?qū)懹泻芎玫膬?yōu)勢，因為順序?qū)懕ＷC了不會有key 范圍重疊的數(shù)據(jù)，那么每個sorted run 中的文件也不會存在key 范圍重疊的問題，但是當多個文件存在key 范圍重疊時，合并操作可能會涉及到當前層級與下一層級的所有文件，導致寫放大問題嚴重影響寫性能.而Tiered 合并策略只會在當前層級內(nèi)將存在key 范圍重疊的文件合并為一個新的有序文件，并放入下一層級，合并操作的范圍不會跨層級，因此寫放大問題小于Leveled 合并策略，寫性能更高.多數(shù)時序數(shù)據(jù)庫，如InfluxDB，IoTDB 采用Tiered 合并策略，減小寫放大問題，同時提高寫性能.

圖6 日志結構合并樹合并策略[74]Fig.6 LSM-tree merge policies[74]

時序數(shù)據(jù)庫通常采用WAL 的方法，在數(shù)據(jù)庫因異常重啟后恢復緩存中丟失的數(shù)據(jù)，當數(shù)據(jù)寫入WAL 后，操作系統(tǒng)并不會直接將數(shù)據(jù)寫入持久性存儲設備中，而是寫入RAM 的頁面緩存（page cache）中，除非使用fsync[75]系統(tǒng)調(diào)用明確告訴操作系統(tǒng)將最近寫入的數(shù)據(jù)從頁面緩存刷新到持久性存儲設備.但是fsync 系統(tǒng)調(diào)用是一個非常慢的過程，頻繁地觸發(fā)fsync 系統(tǒng)調(diào)用會嚴重影響系統(tǒng)性能.WAL 默認是單線程的，且可能會在每次寫入數(shù)據(jù)時觸發(fā)小數(shù)據(jù)塊的落盤操作，這使WAL 成為影響系統(tǒng)寫入性能的主要原因之一.WAL 不僅降低了系統(tǒng)寫入吞吐量，而且?guī)砹藢懛糯髥栴}.VictoriaMetrics 放棄使用WAL，直接在RAM 中緩沖數(shù)據(jù)，定期（硬編碼1 s）將數(shù)據(jù)原子刷新到磁盤文件中持久化存儲[76]，但這樣會存在一個問題，當數(shù)據(jù)庫異常關閉時會丟失最后1 s 沒有存儲的數(shù)據(jù)，VictoriaMetrics 通過放棄嚴格的數(shù)據(jù)安全性來提高寫入性能并減小寫放大問題.

Cassandra[13]是基于LSM-tree 的NoSQL 數(shù)據(jù)庫系統(tǒng)，提出了一種專門面向時序數(shù)據(jù)存儲的時間窗口壓縮策略（time window compaction strategy，TWCS）[60]，通過一系列的時間窗口將SSTables 文件分組，通過SSTable 的最大時間戳決定文件所屬的時間窗口，在觸發(fā)合并操作時，TWCS 會在最新的時間窗口內(nèi)使用基于大小的分層合并策略（sized tiered compaction strategy，STCS）[60]合并該時間窗口內(nèi)的SSTables，在該時間窗口結束時，TWCS 將該時間窗口內(nèi)所有的SSTables 合并成一個SSTable，一旦合并操作完成，這部分數(shù)據(jù)就不會被再次壓縮，一個時間窗口內(nèi)的SSTables 不會與其他時間窗口內(nèi)的SSTables 一起壓縮合并，從而減小寫放大.然而，TWCS 不適用于亂序數(shù)據(jù)的寫入，因為一旦一個時間窗口內(nèi)的SSTables合并完成，就不會再次被壓縮合并.C*DynaConf[77]提出了一種基于Cassandra TWCS 的自動調(diào)優(yōu)數(shù)據(jù)壓縮合并機制，動態(tài)地調(diào)整壓縮合并參數(shù)，最大化吞吐量并最小化響應時間.

TDengine[56]也采用了LSM-tree 架構，使用了WAL、skip list 緩存等技術，但是去掉了LSM-tree 的層級結構，將數(shù)據(jù)按照時間段分區(qū)，然后按表分塊寫入文件.在TDengine 的時序數(shù)據(jù)文件中，1 個數(shù)據(jù)塊只能存儲1 個表的數(shù)據(jù)，每個塊的塊級索引（block range index，BRIN）信息在相關聯(lián)的索引文件中以表為分組，按照時間順序遞增，形成索引塊.查詢時將數(shù)據(jù)文件相關聯(lián)的索引文件加載到內(nèi)存中，直接找到數(shù)據(jù)文件中的時序數(shù)據(jù).通過將標簽數(shù)據(jù)和時序數(shù)據(jù)分離存儲，減少了標簽數(shù)據(jù)的存儲空間，同時去掉了LSM-tree 的層級結構，不需要對文件進行頻繁地合并，減小了寫放大.

在真實場景中，時序數(shù)據(jù)并不總是有序的，它們會因為網(wǎng)絡延遲[78]、時鐘偏差[79]等各種原因產(chǎn)生不同的延遲[80].如果新到達的時序數(shù)據(jù)的時間戳比磁盤中所有時序數(shù)據(jù)的的時間戳都要晚，那么它是有序的數(shù)據(jù)點，否則是無序的數(shù)據(jù)點.在LSM-tree 模型中，當內(nèi)存表大小達到閾值，會將其緩存的數(shù)據(jù)寫入磁盤SSTables 文件，當存在無序時序數(shù)據(jù)時，會導致文件合并時某一時間段的數(shù)據(jù)被多次重寫，增加寫放大.張凌哲等人[81]提出了一種在保持面向大塊數(shù)據(jù)的高效查詢的基礎上實現(xiàn)對最新寫入的時序數(shù)據(jù)的低延遲查詢的2 階段LSM 合并框架，將文件的合并過程分為少量亂序文件快速合并與大量小文件合并這2 個階段，在每個階段內(nèi)提供多種文件合并策略，并在Apache IoTDB 上分別實現(xiàn)傳統(tǒng)的LSM 合并策略以及2 階段LSM 合并框架和測試，實驗結果表明，與傳統(tǒng)的LSM 相比，2 階段的文件合并模塊在提升策略靈活性的情況下使即席查詢讀盤次數(shù)大大降低，并且使歷史數(shù)據(jù)分析查詢性能提升了約20%.Kang等人[82]研究了Apache IoTDB 中的分離策略（separation policy）對寫放大的影響，建立魯棒模型評估不同工作負載以及亂序內(nèi)存表和有序內(nèi)存表的容量對寫放大的影響，在Apache IoTDB 中實現(xiàn)了一個延遲分析器，以選擇更好的策略來減小寫放大，最后在一個真實的工業(yè)案例中使用該模型評估分離策略對減小寫放大的有效性.

IoTDB 通過創(chuàng)建對齊時間序列[70]，實現(xiàn)一個實體的多個測量值的時間戳列在磁盤上只存儲1 次，減少了磁盤空間的占用，同時在文件合并時減小寫放大.

5.3.3 減小讀放大

時序數(shù)據(jù)最終會被持久化到磁盤文件，1 個時間序列的數(shù)據(jù)可能分布在多個文件中，查詢引擎在處理1 個查詢請求時，需要從多個文件中查詢，有些文件并不包含目標數(shù)據(jù)，這是導致讀放大的主要原因.時序數(shù)據(jù)庫使用了多種優(yōu)化方法，如過濾器、更高級別的索引來減小讀放大.

InfluxDB 等使用了文件級別的布隆過濾器，提高查詢命中概率，但是從文件中讀取布隆過濾器以及布隆過濾器導致的假陽性，還是會帶來無效的磁盤I/O.IoTDB 等提供了數(shù)據(jù)塊級別的預聚合信息，在將時序數(shù)據(jù)寫入磁盤文件之前，預先計算數(shù)據(jù)塊中時序數(shù)據(jù)的開始時間、結束時間以及最小值、最大值等聚合計算信息，然后將該預先計算的信息一同寫入文件，在處理聚合計算請求時，通過對數(shù)據(jù)塊聚合信息過濾查詢，直接得到數(shù)據(jù)塊的聚合計算結果，無需將數(shù)據(jù)塊全部加載到內(nèi)存中解壓縮和計算，通過預聚合計算的方式減小讀放大.

黃向東等人[1,83]提出了一種用于分段聚合的高效索引：分段聚合的持久化索引（persistent index for segmented aggregation，PISA），該索引結合了概要表和線段樹，通過計算直接定位出待查詢時間序列的聚合計算信息，減少了大量磁盤I/O，在提高聚合計算性能的同時減小了讀放大.Qiao 等人[84]在文獻[1,83]基礎上提出了Dual-PISA，可以容忍一定程度的亂序時序數(shù)據(jù)聚合.趙東明等人[85]提出了一種面向聚合查詢的Apache IoTDB 物理元數(shù)據(jù)管理方案，該方案按照數(shù)據(jù)文件的物理存儲特性切分數(shù)據(jù)，針對物聯(lián)網(wǎng)應用場景高并發(fā)、亂序的數(shù)據(jù)特點，設計了同步、異步和查詢時計算3 種物理元數(shù)據(jù)的策略，能夠在亂序數(shù)據(jù)攝取場景中維持元數(shù)據(jù)的最終一致性，減小聚合查詢時磁盤I/O 次數(shù).

5.4 海量歷史數(shù)據(jù)低成本存儲技術

有3 種技術可用于降低海量歷史數(shù)據(jù)的存儲成本，包括：1）數(shù)據(jù)生命周期管理；2）數(shù)據(jù)壓縮；3）數(shù)據(jù)分級存儲.下面我們將詳細介紹這3 種技術.

5.4.1 數(shù)據(jù)生命周期管理

不是所有的時序數(shù)據(jù)都需要被永久存儲，不同的場景對數(shù)據(jù)生命周期的要求不同，當數(shù)據(jù)的生命周期結束時需要及時地刪除過期數(shù)據(jù).InfluxDB[10]基于保留策略[86]創(chuàng)建多個數(shù)據(jù)分片組，每個分片組只存儲1 個固定時間范圍內(nèi)的數(shù)據(jù)，攝取的時序數(shù)據(jù)會根據(jù)時間戳被寫入相應的分片組，當一個分片組的生命周期結束后該分片組會被刪除，釋放硬件空間.圖7 展示了一個具有3 天生命周期和分片組持續(xù)時間為1 天的保留策略.

圖7 數(shù)據(jù)分片組與生命周期管理[86]Fig.7 Data shard group and lifecycle management[86]

5.4.2 數(shù)據(jù)壓縮

除了數(shù)據(jù)生命周期管理，數(shù)據(jù)壓縮也是顯著減小存儲成本的方法.幾乎所有的時序數(shù)據(jù)庫都采用列式存儲，將同一類型的數(shù)據(jù)作為一列存儲在文件中，時序數(shù)據(jù)的特性決定了每一列數(shù)據(jù)可以使用不同的壓縮算法，包括無損編碼（lossless encoding）、有損編碼（lossy encoding）以及通用壓縮，近年來學術界將機器學習算法用在時序數(shù)據(jù)壓縮中，取得了可觀的成果.

5.4.2.1 無損編碼

無損編碼是一種不損失數(shù)據(jù)完整性和準確性的數(shù)據(jù)壓縮方法，可以保證原始數(shù)據(jù)在解壓縮后能完整地還原，并且保持原有的質(zhì)量，無損編碼被廣泛應用在時序數(shù)據(jù)壓縮中.

Gorilla[7]發(fā)現(xiàn)絕大多數(shù)時序數(shù)據(jù)點以固定時間間隔到達，少數(shù)數(shù)據(jù)點時間戳可能會提前或延遲1s，即大多數(shù)相鄰數(shù)據(jù)點時間戳之差為0，少數(shù)相鄰數(shù)據(jù)點時間戳之差不為0，基于這些特點，Gorilla 提出了用于時間戳壓縮的2 階差分delta-of-delta 算法，大約96%的時間戳可以被壓縮到1 b； Gorilla 還提出了“XOR”編碼算法對雙精度浮點類型數(shù)據(jù)進行壓縮，大約51%的值可以被壓縮到1 b.這2 種編碼算法適用于波動較小的數(shù)據(jù)，當時間序列發(fā)生劇烈變化時這些方法可能會失敗.

Xiao 等人[87]分析了可能影響編碼性能的時序數(shù)據(jù)特征，包括規(guī)模（scale）、增量（delta）、重復（repeat）和增長（increase），并詳細介紹了Apache IoTDB 中使用的時序數(shù)據(jù)編碼方式：1）用于數(shù)值型數(shù)據(jù)的差分編碼（differential encoding），如TS_2DIFF[88]；游程編碼（run-length encoding，RLE）[89]， 如帶有位壓縮（bitpacking）的游程編碼和PAKE 編碼[90]；差分和游程相結合的編碼算法，如RLBE[91]，SPRINTZ[92].2）用于文本壓縮的字典編碼（DICTIONARY）[93]、霍夫曼編碼（HUFFMAN）[94]，并使用生成數(shù)據(jù)和真實的工業(yè)數(shù)據(jù)集對各種編碼算法進行基準測試，通過壓縮比、插入時間、查詢時間3 個指標評估各種編碼算法的性能.

InfluxDB[10]使用了一種自適應編碼方式進行時間戳編碼，基于被編碼的時間戳的結構，使用不同的編碼方式.在對時間戳編碼時，首先使差分編碼（delta encoding）將值轉(zhuǎn)換為更小的整數(shù)，然后自適應地選擇游程編碼、simple8b[95]編碼或不壓縮.對于整數(shù)類型的數(shù)據(jù)，首先使用zig-zag 編碼，將有符號整數(shù)轉(zhuǎn)換成無符號整數(shù)，然后根據(jù)編碼后值的范圍使用simple8b 編碼或不壓縮，這種方式對于頻繁保持不變的值非常有效.對于布爾類型的數(shù)據(jù)，InfluxDB 使用位壓縮編碼，字符串數(shù)據(jù)使用Snappy[69]壓縮.

5.4.2.2 有損編碼

有損編碼通過丟棄一些不重要的信息實現(xiàn)數(shù)據(jù)壓縮，壓縮后的數(shù)據(jù)不能被重新恢復為原始數(shù)據(jù)，只能重建為原始數(shù)據(jù)的近似值.與無損編碼相比，有損編碼可以得到更高的壓縮比，但會損失部分精度.

PI Server[96]是OSISoft 公司（后被AVEVA 公司收購）研發(fā)的實時數(shù)據(jù)庫系統(tǒng)，用于管理工業(yè)中產(chǎn)生的時序數(shù)據(jù)，PI Server 使用了旋轉(zhuǎn)門壓縮（swinging door trending, SDT）[97]算法，SDT 是一種有損壓縮算法，使用線性擬合的方法壓縮數(shù)據(jù)，計算復雜度較低，誤差可控.Apache IoTDB 也支持SDT 算法，在數(shù)據(jù)寫入磁盤文件之前使用SDT 算法對緩存的數(shù)據(jù)進行壓縮，將壓縮后的數(shù)據(jù)刷新到磁盤.SDT 算法在一定條件下可以用來跟蹤數(shù)據(jù)的變化趨勢，但是當數(shù)據(jù)存在噪聲時，SDT 會對過程趨勢作出錯誤的判斷，壓縮比降低，且SDT 無法判斷和處理異常數(shù)據(jù).Feng 等人[98]對SDT 算法進行了改進，通過使用自適應記錄限制和異常值檢測規(guī)則處理異常值和適應實際數(shù)據(jù)的波動，實現(xiàn)了更高的壓縮比.

5.4.2.3 其他壓縮算法

時序數(shù)據(jù)被編碼之后，還可以使用通用壓縮算法進行2 次壓縮，例如GZIP[99]，LZ4[100]，Snappy[69].TDengine 支持2 階段壓縮[101]，在對時序數(shù)據(jù)編碼后，再次使用通用壓縮算法進行壓縮，獲得更高的壓縮效率.

除了工業(yè)界時序數(shù)據(jù)庫中廣泛使用的成熟的時序數(shù)據(jù)壓縮算法，學術界也提出了一些針對時序數(shù)據(jù)的壓縮算法.ModelarDB[102]提出了一種在線自適應多模型壓縮算法，可以動態(tài)地選擇最佳模型.Eichinger 等人[103]提出了一種基于分段回歸計算的時序數(shù)據(jù)有損壓縮算法，通過自定義最大偏差控制壓縮精度和壓縮比.Chiarot 等人[104]對時序數(shù)據(jù)壓縮算法進行了全面的調(diào)查研究，通過分類的方法分析時序數(shù)據(jù)壓縮的整體方法和特征，并分析了這些算法的性能.

最近幾年，隨著人工智能的發(fā)展，機器學習算法也被應用到數(shù)據(jù)壓縮中，Yu 等人[105]提出了一種2 級壓縮模型，為每個時間序列選擇合適的壓縮算法，通過基于強化學習的方法來自動學習壓縮參數(shù)，有效處理多樣化的數(shù)據(jù)模式，該算法根據(jù)數(shù)據(jù)點周圍局部上下文的情況動態(tài)調(diào)整壓縮參數(shù)，可以有效地壓縮真實世界中模式多變的時序數(shù)據(jù).實驗評估表明，這種基于強化學習的壓縮算法比Snappy，Gorilla，MO[106]具有更高的壓縮比，將壓縮比提高了50%以上，且壓縮效率更高，適合并行計算.

5.4.3 分級存儲

正如5.2 節(jié)所述，時序數(shù)據(jù)具有時間局部性[49]，熱數(shù)據(jù)被訪問的頻次遠高于冷數(shù)據(jù).熱數(shù)據(jù)的價值更高，需要被快速地訪問和計算，而冷數(shù)據(jù)具有規(guī)模大、訪問頻次低的特點，隨著時間的推移，熱數(shù)據(jù)的訪問頻次會逐漸降低，呈現(xiàn)出由熱到冷的變化趨勢，不同時間范圍內(nèi)時序數(shù)據(jù)訪問特性的不一致性對底層存儲的性能要求也不同，一些時序數(shù)據(jù)庫提出了分層存儲架構.TDengine 通過冷熱數(shù)據(jù)自動分級存儲[107]，將不同熱度的數(shù)據(jù)存儲在不同的地方，例如，最新的數(shù)據(jù)存儲在SSD 上，1 周以上的數(shù)據(jù)存儲在HDD 上，4 周以上的數(shù)據(jù)存儲在價格更低的網(wǎng)絡設備上，從而降低了存儲[108]成本，同時保證了數(shù)據(jù)的高效訪問.

我們以InfluxDB 和TimescaleDB 基準測試的部分關鍵指標的對比為例，直觀展示這4 類關鍵技術對時序數(shù)據(jù)庫性能的影響.圖8 是TimescaleDB 官方發(fā)布的TimescaleDB 與InfluxDB 在寫入性能、查詢性能以及磁盤占用3 個指標的基準測試對比[109].

圖8 InfluxDB 與TimescaleDB 的性能比較Fig.8 Performance comparison of InfluxDB and TimescaleDB

測試結果表明，在低基數(shù)的工作負載中，Influx-DB 的插入性能比TimescaleDB 表現(xiàn)更好，但是隨著數(shù)據(jù)基數(shù)的增加，InfluxDB 的性能會急劇降低，高基數(shù)情況下，TimescaleDB 的插入性能是InfluxDB 的3.5倍，這是因為InfluxDB 使用了基于LSM-tree 的時間序列索引，無法高效地管理復雜的時間序列元數(shù)據(jù)，而TimescaleDB 使用 B-tree 數(shù)據(jù)結構對時序數(shù)據(jù)標簽建立索引，同時允許在數(shù)據(jù)集上創(chuàng)建多個索引，這有利于處理高基數(shù)數(shù)據(jù)集.對于查詢而言，Timescale-DB 的查詢性能總體優(yōu)于InfluxDB，在復雜查詢中，TimescaleDB 的性能遠遠超過InfluxDB，InfluxDB 的查詢性能同樣受限于基于LSM-tree 的時間序列索引和時序數(shù)據(jù)存儲，這種限制在時序數(shù)據(jù)高基數(shù)情況下更為明顯.在數(shù)據(jù)壓縮存儲測試中，InfluxDB 通過列式存儲實現(xiàn)了更高的壓縮比，這是TimescaleDB 使用B-tree 數(shù)據(jù)結構的行存儲無法比擬的.

本節(jié)系統(tǒng)地研究了時序數(shù)據(jù)庫的4 類關鍵技術，并詳細分析了每一類技術的代表性工作和優(yōu)缺點.這4 類關鍵技術不是獨立地存在，而是互相作用，共同影響時序數(shù)據(jù)存儲的性能.時間序列索引直接影響內(nèi)存數(shù)據(jù)的組織方法、數(shù)據(jù)攝取和查詢的性能，是時序數(shù)據(jù)庫最核心的關鍵技術.內(nèi)存數(shù)據(jù)的組織方式依賴于時間序列索引，索引性能直接決定了在內(nèi)存中定位唯一時間序列的效率，以及數(shù)據(jù)在內(nèi)存中的模型.基于分片的數(shù)據(jù)生命周期管理可以減小歷史數(shù)據(jù)的存儲成本，但是分片的時間跨度會影響數(shù)據(jù)攝取、查詢的性能以及存儲引擎的資源占用，每一個分片都包含一個獨立的時序數(shù)據(jù)存儲引擎，較小的分片時間跨度能使大批量的數(shù)據(jù)并行寫入到多個分片中，有助于提高寫入吞吐量，同時跨多個分片的歷史數(shù)據(jù)查詢可以并行執(zhí)行，提高查詢效率，但是隨著分片的數(shù)量增加，時序數(shù)據(jù)庫對CPU、磁盤I/O 等資源的消耗成比例地增加，較高的資源占用又會對數(shù)據(jù)寫入吞吐量和查詢效率產(chǎn)生負面影響.通常情況下，數(shù)據(jù)壓縮有助于提高讀寫性能，同時減小寫放大和讀放大，但是數(shù)據(jù)壓縮的效果與數(shù)據(jù)的波動情況密切相關，當數(shù)據(jù)波動較大時，數(shù)據(jù)壓縮比較低，壓縮和解壓縮會占用大量的CPU 資源，影響時序數(shù)據(jù)庫的讀寫性能.因此，在設計時序數(shù)據(jù)存儲時，需要充分考慮到這4 類關鍵技術的互相作用關系，并作出權衡.

6 時序數(shù)據(jù)庫評測基準

數(shù)據(jù)庫基準測試工具是用來測試與衡量數(shù)據(jù)庫系統(tǒng)性能的重要工具，對推動數(shù)據(jù)庫技術的不斷發(fā)展具有重要意義，同時有助于研究人員或開發(fā)人員找到最適合工作負載的數(shù)據(jù)庫系統(tǒng).評測基準對時序數(shù)據(jù)庫技術的發(fā)展也至關重要，近年來，隨著時序數(shù)據(jù)庫技術的快速發(fā)展，出現(xiàn)了一些用于時序數(shù)據(jù)庫基準測試的工具，但是目前可用的標準和工具還存在一些問題，無法系統(tǒng)地測試時序數(shù)據(jù)庫的性能，主要原因是物聯(lián)網(wǎng)以及工業(yè)物聯(lián)網(wǎng)的場景復雜多變，不僅數(shù)據(jù)規(guī)模龐大，而且經(jīng)常因為設備故障、網(wǎng)絡擁堵等原因?qū)е聲r序數(shù)據(jù)異常、亂序到達以及工作負載發(fā)生變化，現(xiàn)有的基準測試工具在模擬真實世界的物聯(lián)網(wǎng)和工業(yè)物聯(lián)網(wǎng)場景時存在不足.本節(jié)將具體介紹3 個接受度較高的時序數(shù)據(jù)庫評測基準.

6.1 TSBS

TSBS（time series benchmark suite）[110]是當前認可度最高、使用范圍最廣泛的時序數(shù)據(jù)庫評測基準，從2018 年開始，已有多個開源時序數(shù)據(jù)庫廠商將TSBS作為基準測試平臺[111-113].該評測基準具有可擴展性，可對多種時序數(shù)據(jù)庫的讀寫性能進行基準測試，支持多種類別的典型查詢，并能自動匯總測試結果.當前TSBS 支持2 種場景：DevOps 和IoT.

在DevOps 場景下，有2 種類型的測試用例：1）完整形式的測試用例用來生成、插入和測量來自9 個系統(tǒng)的數(shù)據(jù)，這些系統(tǒng)可以在真實的開發(fā)環(huán)境中被監(jiān)控（如CPU、內(nèi)存、磁盤等)；2）另一種測試用例只關注CPU 指標，cpu-only 數(shù)據(jù)模型更簡單，每個設備具有10 個測量值.除了監(jiān)測指標數(shù)據(jù)，數(shù)據(jù)集同時包含標簽數(shù)據(jù)，每一個標簽組合用于標識數(shù)據(jù)集中的1 臺主機，不同主機的數(shù)量規(guī)?？梢酝ㄟ^參數(shù)設置.

在IoT 場景下，TSBS 模擬生成卡車公司的一組卡車的數(shù)據(jù)流，測試用例模擬了每輛卡車的診斷數(shù)據(jù)和指標.與DevOps 場景下的測試用例不同，IoT 測試用例引入了真實世界中存在的影響因素，如亂序數(shù)據(jù)、缺失數(shù)據(jù)或空數(shù)據(jù)的攝取，數(shù)據(jù)集同時包含了卡車的元數(shù)據(jù).

使用TSBS 進行基準測試包括3 個過程：

1）數(shù)據(jù)與查詢生成.使用TSBS 進行基準測試，需要預先生成測試數(shù)據(jù)和查詢用例，以避免即時生成數(shù)據(jù)和查詢用例對測試結果產(chǎn)生影響.IoT 數(shù)據(jù)集會模擬生成亂序數(shù)據(jù)、缺失數(shù)據(jù)或空數(shù)據(jù)，查詢用例支持多種聚合計算，如MAX，AVG，LAST，LOW，HIGH，GROUP BY.

2）數(shù)據(jù)加載與寫入.該過程將加載過程1）中預先生成的模擬數(shù)據(jù)，寫入待測試數(shù)據(jù)庫，同時也支持即時模擬和加載數(shù)據(jù).

3）查詢執(zhí)行.該過程用于評估待測數(shù)據(jù)庫的查詢性能，需要先加載過程1）中預先生成的模擬數(shù)據(jù)和查詢用例，可以通過參數(shù)設置并行查詢線程數(shù)量.最后將查詢用例的執(zhí)行結果輸出.

6.2 iot-benchmark

iot-benchmark（原名IoTDB-Benchmark）[108，114]是用來對時序數(shù)據(jù)庫進行基準測試的工具，該工具主要關注工作負載場景更加復雜的工業(yè)場景.Liu 等人[114]詳細介紹了IoTDB-Benchmark 的架構以及數(shù)據(jù)模擬、測試工作負載、系統(tǒng)資源監(jiān)控等過程，并使用該工具對4 個流行的時序數(shù)據(jù)庫InfluxDB[10]，KairosDB[52]，OpenTSDB[11]，TimescaleDB[12]進行基準測試，演示了這些時序數(shù)據(jù)庫在不同工作負載下的性能比較.

iot-benchmark 具有5 個特點：1）可模擬真實場景中的不同應用的數(shù)據(jù)分布，包括但不限于具有可控高斯噪聲的方波、正弦波和鋸齒波，通過多種數(shù)據(jù)分布測試時序數(shù)據(jù)庫存儲引擎中使用的多種數(shù)據(jù)編碼方法；2）可模擬有序數(shù)據(jù)和亂序數(shù)據(jù)；3）可進行混合操作以模擬復雜的現(xiàn)實工作負載；4）可記錄系統(tǒng)資源消耗情況，如CPU 使用情況和內(nèi)存使用情況；5）該工具提供了一種管理基準測試結果數(shù)據(jù)的通用方法，包括持久化測試配置和測試數(shù)據(jù)，以及分析測試結果.

6.3 TPCx-IoT

TPCx-IoT[115]是一個專門設計用于測量物聯(lián)網(wǎng)網(wǎng)關系統(tǒng)性能的物聯(lián)網(wǎng)基準，可以直接比較不同的軟件和硬件系統(tǒng).TPCx-IoT 使用發(fā)電站中200 種不同類型傳感器的數(shù)據(jù)，每條數(shù)據(jù)包含系統(tǒng)ID、傳感器名、采集值和時間戳，并將數(shù)據(jù)填充到1KB 大小，TCPx-IoT 使用3 個指標作為評測基準：

1）性能指標IoTps=SF/T.該指標表示被測系統(tǒng)的有效吞吐能力，其中SF（scale factor）是攝取數(shù)據(jù)的數(shù)量，T是攝取經(jīng)過的時間（單位為s）.

2）性價比指標$/IoTps=P/IoTps.該指標表示被測系統(tǒng)每單位性能（IoTps）的總成本，其中P是被測系統(tǒng)的總成本.

3）可用性指標.該指標反映了價格配置的所有項通常可用的日期，即對任何客戶可用的日期，保證了基準測試系統(tǒng)是可以購買的生產(chǎn)系統(tǒng)，而不是僅為運行基準測試而實現(xiàn)的實驗系統(tǒng).

Poess 等人[116]詳細介紹了 TPCx-IoT，以及該基準評測關鍵要素背后的設計決策，并通過實驗分析TPCx-IoT 如何衡量物聯(lián)網(wǎng)網(wǎng)關系統(tǒng)的性能.TPCx-IoT 自稱是第一個專門面向時間序列場景的評測基準，但是提供的測試場景不適合物聯(lián)網(wǎng)中的實際應用，例如，在真實世界中，數(shù)據(jù)并不總是有序到達，存在亂序數(shù)據(jù)攝取的情況.

還有一些其他評測基準被用于時序數(shù)據(jù)庫性能測試，influxdb-comparisons[117]是使用Go 語言開發(fā)的基準測試工具，用于比較InfluxDB 與其他時序數(shù)據(jù)庫的性能，支持Cassandra，OpenTSDB，TimescaleDB等數(shù)據(jù)庫.Hao 等人[118]提出并開發(fā)了TS-Benchmark，可以模擬真實世界中的時序數(shù)據(jù)庫工作負載，即風力發(fā)電廠中的數(shù)據(jù)管理和運行分析，將工作負載分為2 類：1）與數(shù)據(jù)庫性能無關的上層應用工作負載；2）需要由數(shù)據(jù)庫完成的工作負載.TS-Benchmark 更關注時序數(shù)據(jù)庫本身的數(shù)據(jù)攝入和數(shù)據(jù)讀取性能.表5 列出了上述時序數(shù)據(jù)庫評測基準的對比.

Table 5 Comparison of Benchmark for Time Series Databases表5 時序數(shù)據(jù)庫評測基準比較

時序數(shù)據(jù)庫在不同的數(shù)據(jù)集上可能會表現(xiàn)出較大的性能差異，Shah 等人[120]使用3 種真實數(shù)據(jù)集（包括物聯(lián)網(wǎng)數(shù)據(jù)集、金融數(shù)據(jù)集和分析型數(shù)據(jù)集）以及1 種合成數(shù)據(jù)集，對InfluxDB[10]，TimescaleDB[12]，Druid[121]，Cassandra[13]進行了基準測試，實驗表明時序數(shù)據(jù)庫的寫入性能和查詢性能在不同類型的真實數(shù)據(jù)集以及合成數(shù)據(jù)集上會有很大的差異.時序數(shù)據(jù)庫評測基準都在盡可能地模擬真實場景中的數(shù)據(jù)集和工作負載，以獲得時序數(shù)據(jù)庫在真實世界中的表現(xiàn)，然而當前已存在的基準評測無法覆蓋不同類型的時序數(shù)據(jù)場景，且不能較好地模擬真實場景中復雜多變的數(shù)據(jù)和工作負載，時序數(shù)據(jù)庫評測基準應該提供不同場景的數(shù)據(jù)集，同時重點關注因各種故障、異常導致的時序數(shù)據(jù)缺失、時序數(shù)據(jù)質(zhì)量變化、亂序數(shù)據(jù)以及工作負載突變.

7 時序數(shù)據(jù)庫關鍵技術的未來發(fā)展方向與預測

時序數(shù)據(jù)庫伴隨著物聯(lián)網(wǎng)的快速發(fā)展而進入新的發(fā)展階段，尤其是最近5 年出現(xiàn)了大量新的時序數(shù)據(jù)庫，多種解決方法被提出以應對管理工業(yè)物聯(lián)網(wǎng)海量時序數(shù)據(jù)面臨的技術挑戰(zhàn)，從這些方法中我們可以對時序數(shù)據(jù)庫關鍵技術的發(fā)展方向做一些預測.

7.1 面向工作負載的自適應時序數(shù)據(jù)存儲

不斷提高性能是時序數(shù)據(jù)庫研發(fā)人員在未來需要考慮的首要工作，但是沒有任何一個存儲方法可以同時實現(xiàn)最優(yōu)寫、最優(yōu)讀，每個存儲方法的表現(xiàn)受到實際工作負載的影響，當工作負載變化時，時序數(shù)據(jù)庫可能會出現(xiàn)很大的性能波動.

在大多數(shù)情況下，時序數(shù)據(jù)都是寫密集型，因此大部分時序數(shù)據(jù)庫使用對寫密集型工作負載友好的基于LSM-tree[30]的數(shù)據(jù)結構.然而，工作負載可能會根據(jù)實際場景的變化而變化，從寫密集型變成讀密集型，這時面向?qū)懨芗驮O計的時序數(shù)據(jù)庫會出現(xiàn)性能波動.LSM-tree 的可調(diào)節(jié)性是很值得研究的，可以實現(xiàn)給定工作負載的最佳權衡，根據(jù)不同的工作負載，LSM-tree 可以進一步優(yōu)化，如Pebblesdb[32]提出了FLSM，通過讀放大來換取更低的寫放大，以適應寫密集型工作負載，Mei 等人[122]提出的LSM-Forest也是通過讀放大換取更低的寫放大.Luo 等人[74]詳細研究了基于LSM-tree 的存儲技術，包括寫放大優(yōu)化、合并策略優(yōu)化、2 級索引、面向硬件和工作負載的優(yōu)化.在設計基于LSM-tree 的時序數(shù)據(jù)存儲時可以從這里得到啟發(fā).在LSM-tree 和LSM-Forest[32,122]之間并沒有不可逾越的鴻溝，二者是可以根據(jù)參數(shù)互相轉(zhuǎn)換的，時序數(shù)據(jù)存儲可以設計成根據(jù)工作負載情況自適應地選擇LSM-tree 或者LSM-Forest，以應對不同的工作負載.如果存在特定的訪問模式，如數(shù)據(jù)傾斜，那么需要研究與這些訪問模式相關的優(yōu)化技術，以應對特殊的工作負載.

7.2 面向新硬件的時序數(shù)據(jù)存儲

面向新硬件優(yōu)化的時序數(shù)據(jù)存儲正在成為一個新的趨勢.基于Flash 的SSD 已經(jīng)在消費級產(chǎn)品中取代了HDD，SSD 幾乎占領了個人電腦市場，而且隨著SSD 價格的不斷下降，SSD 在大型數(shù)據(jù)中心所占的比重正在不斷上升.SSD 的硬件特性與HDD 有非常大的差異，SSD 內(nèi)部具有大的并行數(shù)據(jù)處理能力，且對數(shù)據(jù)訪問模式不敏感[37]，Chen 等人[123-124]系統(tǒng)地研究了基于閃存的固態(tài)硬盤的內(nèi)部并行性，揭示了在高速數(shù)據(jù)處理中，充分利用固態(tài)硬盤的內(nèi)部并行性的重要作用.然而，目前時序數(shù)據(jù)存儲的大多數(shù)技術方案都是針對HDD 硬件優(yōu)化的，這些優(yōu)化方法對SSD 無效，甚至會對SSD 造成損害[123]，因此面向SSD硬件優(yōu)化的時序數(shù)據(jù)存儲是一個很重要的研究方向，時序數(shù)據(jù)存儲充分利用SSD 的內(nèi)部并行性，可以顯著提高時序數(shù)據(jù)庫的讀寫性能.在其他類型的數(shù)據(jù)存儲中，面向SSD 的優(yōu)化已經(jīng)成為一個研究熱點，已經(jīng)有一些面向SSD 優(yōu)化的KV 存儲技術被提出，Lu等人[31]提出了WiscKey，這是一個基于LSM-tree 的持久性KV 存儲，具有面向性能的數(shù)據(jù)布局，它將鍵和值分開，以盡量減少寫放大，并在設計時充分考慮了面向SSD 的優(yōu)化，利用了SSD 設備的順序和隨機I/O 性能特性.Doekemeijer 等人[33]詳細地調(diào)查了面向SSD 塊接口（block interface）優(yōu)化的KV 持久化存儲技術，這些技術對設計時序數(shù)據(jù)存儲很有啟發(fā)性，因為采用列式存儲模型的時序數(shù)據(jù)存儲可以被看作是一種特殊的KV 存儲.除了面向SSD 數(shù)據(jù)塊級別接口的KV 存儲研究，還有一些面向Open channel SSD 和非易失性內(nèi)存（non-volatile memory，NVM）優(yōu)化的KV 存儲研究，Wang 等人[125]提出了一種基于Open Channel SSD 的LSM-tree，通過利用SSD 內(nèi)部多個通道（channel）以及優(yōu)化I/O 請求并發(fā)調(diào)度策略，提高數(shù)據(jù)并行處理，將系統(tǒng)的吞吐量提高4 倍以上.Kannan等人[126]提出了可充分利用非易失性內(nèi)存特性基于LSM-tree 的NoveLSM，通過利用NVM 的字節(jié)可尋址性（byte-addressability）來減少讀寫延遲，從而實現(xiàn)更高的吞吐量.游理通等人[127]提出了一種基于日志結構的非易失性內(nèi)存KV 存儲系統(tǒng)TinyKV，該系統(tǒng)通過減少對NVM 的寫入與緩存刷新指令，降低寫入延遲.文獻[31,33,37,123-127]研究對設計面向新硬件優(yōu)化的時序數(shù)據(jù)存儲有很大的參考價值.

7.3 Cloud+AI

工業(yè)物聯(lián)網(wǎng)的快速發(fā)展離不開云計算技術的發(fā)展，越來越多的公司開始將數(shù)據(jù)中心遷移到云平臺，包括公有云和私有云.云基礎設施的虛擬化、彈性分配、高可用等特點，為時序數(shù)據(jù)庫提供了按需分配、高可用、低成本存儲等優(yōu)勢，一些基于云原生技術的時序數(shù)據(jù)庫快速發(fā)展起來，采用計算和存儲分離的架構，實現(xiàn)計算資源和存儲資源的獨立分配和擴展以充分利用云基礎設施彈性伸縮的特點.然而，云原生技術對時序數(shù)據(jù)庫提出了新的要求，時序數(shù)據(jù)庫的數(shù)據(jù)組織、存儲管理、查詢優(yōu)化、故障恢復等都需要為適應云環(huán)境而重新設計和優(yōu)化.云原生技術已經(jīng)在其他類別的數(shù)據(jù)庫中發(fā)展壯大，例如在OLTP和OLAP 數(shù)據(jù)庫，董昊文等人[128]深入分析了云原生數(shù)據(jù)庫系統(tǒng)的架構和技術，探討了云原生OLTP 和云原生OLAP 數(shù)據(jù)庫的架構設計和關鍵技術.云原生技術也適合時序數(shù)據(jù)場景，充分利用云原生技術的時序數(shù)據(jù)庫可以實現(xiàn)更高的寫入吞吐量以及更低的存儲成本.

云計算提供的強大算力同時帶動了人工智能（artificial intelligence，AI）的快速發(fā)展，與云原生技術一樣，人工智能技術與時序數(shù)據(jù)庫技術的結合可能帶來新的發(fā)展方向.例如，Yu 等人[105]使用強化學習技術壓縮時序數(shù)據(jù)，不僅可以應對真實世界中模式多變的時序數(shù)據(jù)，同時可以實現(xiàn)更高的壓縮比.除了時序數(shù)據(jù)壓縮，人工智能技術可以在2 個方面給時序數(shù)據(jù)庫賦能：1）AI 使時序數(shù)據(jù)庫更加智能，通過深度強化學習實現(xiàn)存儲引擎自適應調(diào)優(yōu)，建立AI 驅(qū)動的索引、故障檢測與恢復機制，使時序數(shù)據(jù)庫能夠應對更加復雜的工作負載，實現(xiàn)更高效的時序數(shù)據(jù)存儲和更快的故障恢復.孟小峰等人[129]對機器學習化數(shù)據(jù)庫系統(tǒng)進行了調(diào)查和綜述，包括存儲管理、查詢優(yōu)化的機器學習化研究以及自動化的數(shù)據(jù)庫管理系統(tǒng)，并指出了機器學習化數(shù)據(jù)庫系統(tǒng)的未來研究方向及可能面臨的問題與挑戰(zhàn).2）人工智能為時序數(shù)據(jù)庫提供了更先進的數(shù)據(jù)分析能力，例如，基于海量的歷史數(shù)據(jù)，使用時間序列預測算法來預測一個數(shù)據(jù)集在未來可能的價值，或通過時間序列異常檢測發(fā)現(xiàn)系統(tǒng)中可能存在的異常，對保障系統(tǒng)安全、設備平穩(wěn)運行具有重要的意義.總之，人工智能技術不僅可以使時序數(shù)據(jù)庫更加智能，還可以充分挖掘海量實時、歷史時序數(shù)據(jù)的價值，提供更先進的數(shù)據(jù)分析能力以滿足越來越復雜的分析場景.

8 總 結

本綜述對最近10 年時序數(shù)據(jù)庫關鍵技術進行了完整的調(diào)查、總結、分類和研究.本文分析了時序數(shù)據(jù)庫在管理工業(yè)物聯(lián)網(wǎng)海量時序數(shù)據(jù)時面臨的挑戰(zhàn)，包括：1）如何高效地管理復雜的時間序列元數(shù)據(jù)；2）如何應對工業(yè)物聯(lián)網(wǎng)特殊的工作負載；3）如何降低海量時序數(shù)據(jù)存儲成本.圍繞這3 個挑戰(zhàn)，本文首先對時序數(shù)據(jù)庫進行了分類和比較，然后重點研究了時序數(shù)據(jù)庫的4 類關鍵技術：1）時間序列索引優(yōu)化技術；2）內(nèi)存數(shù)據(jù)組織技術；3）高吞吐量數(shù)據(jù)攝取和低延遲數(shù)據(jù)查詢技術；4）海量歷史數(shù)據(jù)低成本存儲技術.本文總結了每一類技術下具體的關鍵技術，并對每一個關鍵技術進行了詳細的研究.這些關鍵技術決定了時序數(shù)據(jù)庫在管理工業(yè)物聯(lián)網(wǎng)大規(guī)模復雜時序數(shù)據(jù)時的寫入吞吐量、查詢時延、對關鍵數(shù)據(jù)計算響應的實時性以及存儲成本，對提高工業(yè)物聯(lián)網(wǎng)的實時性、安全性和優(yōu)化制造流程具有重要的實際價值，是數(shù)據(jù)庫設計人員需要著重考慮的關鍵技術.

本文還概述了時序數(shù)據(jù)庫的主流評測基準，包括TSBS，iot-benchmark，TPCx-IoT，詳細介紹了這些評測基準的數(shù)據(jù)生成特點、執(zhí)行過程和評價指標.最后，本文展望了時序數(shù)據(jù)庫關鍵技術在未來的發(fā)展方向，并提出了一些預測和建議.

通過調(diào)查和研究可知，工業(yè)物聯(lián)網(wǎng)產(chǎn)生的時序數(shù)據(jù)正在不斷地增加，時序數(shù)據(jù)庫面臨的挑戰(zhàn)也在不斷地增加，隨著時序數(shù)據(jù)規(guī)模的膨脹，現(xiàn)有的解決方案可能會力不從心，迫切需要面向新的場景、新的環(huán)境和新的硬件研究時序數(shù)據(jù)庫關鍵技術.

作者貢獻聲明：劉帥負責調(diào)研并完成論文撰寫；喬穎負責論文審閱，并給出詳細的修改指導意見；羅雄飛、王宏安參與了論文審閱，并提出指導意見；趙怡婧參與了方案討論、技術支持等工作.