TSDB時序資料庫時序資料壓縮解壓技術淺析
摘要：目前，物聯網、工業網際網路、車聯網等智能互聯技術在各個行業場景下快速普及應用，導緻聯網傳感器、智能裝置數量急劇增加，随之而來的海量時序監控資料存儲、處理問題，也為時序資料庫高效壓縮、存儲資料能力提出了更高的要求。對于通量愈加龐大的物聯網時序大資料存儲，盡管标準壓縮方法還能發揮其價值，但某些場景對時序資料壓縮解壓技術效率、性能提出了新的需求。本文介紹了現有的時序資料壓縮解壓技術，分類介紹了不同算法的特點和優劣勢。
時序資料普遍存在于IoT物聯網、工業網際網路、車聯網等相關場景，物聯網裝置已遍布各種行業場景應用，從可穿戴裝置到工業生産裝置，都會或将會産生大量資料。比如，新型波音787客機每次飛行傳感器産生的資料量都在500GB左右。在這些場景下，通常具備高并發寫和高通量資料處理特點，選擇時序資料壓縮算法需要全方位考慮資料采集、存儲、分析的需要。特别需要注意的是業務應用對時序資料目前和曆史資料分析的方式，選擇壓縮算法不當将可能導緻關鍵資訊丢失，進而影響分析結果。對于業務來說，更直接使用時序資料壓縮技術的應用就是時序資料庫，對于時序資料庫壓縮解壓是關鍵資料處理步驟，壓縮算法性能直接影響時序資料庫建設投入的ROI。
1 時序資料壓縮
對于資料壓縮算法，業界存在更普遍的解釋，通常是針對通用場景和業務相關場景，比如視訊、音頻、圖像資料流壓縮。本文重點介紹時序資料庫中常用的面向時序資料設計或可用于時序資料處理的通用壓縮算法。我們選擇分析的算法具備對更普遍場景下持續産生時序資料壓縮處理的能力，并對IoT物聯網場景傳感器資料壓縮的以下特點做了特殊設計：
- 資料備援（Redundancy）：一些特定模式的時序資料經常性重複出現在一個或多個時間序列。
- 函數估算（Approximability）：某些傳感器産生的時序資料生成模式可以根據預定義函數估算。
- 趨勢預測（Predictability）：某些時序資料未來趨勢可以通過算法預測，例如利用回歸、深度神經網絡等技術。
圖 時序資料壓縮算法分類
本文重點總結了時序資料庫和物聯網IoT傳感器管理常用壓縮算法，并根據技術方法（dictionary-based, functional approximation, autoencoders, sequential等）和技術屬性（adaptiveness, lossless reconstruction, symmetry, tuneability）對碎片化的壓縮技術進行了分類，詳細參考上圖，并針對主要算法性能進行了對比分析。
2 背景技術介紹
在介紹壓縮算法之前，我們先對時序資料、壓縮和品質指數（quality indices）幾個關鍵的概念進行定義。
2.1 時序資料（Time Series）
時序資料指資料元組根據時間戳（ti）升序排列的資料集合，可以被劃分為：
- 單變量時序（Univariate Time Series，UTS）：每次采集的資料元組集合為單個實數變量。
- 多變量時序（Multivariate Time Series，MTS）：每次采集的資料元組集合由多個實數序列組成，每個組成部分對映時序一個特征。
比如，圖2中股票價格在指定時間視窗的波動可以被定義為單變量時序資料，而每天交易資訊（如：開盤、收盤價格，交易量等）則可以定義為多變量時序資料。
圖 股票交易UTS時序資料樣例
用數學範式表達時序可以被定義為：
2.2 資料壓縮
資料壓縮（又被稱為源編碼，source coding），跟據David Salmon在《Data Compression: The Complete Reference》一書中的定義，可以簡單描述為“将輸入原始資料流轉變為字元流（bit stream）或壓縮流的體量更小的輸出資料流的過程”。這個過程遵循J. G.Wolff提出的Simplicity Power（SP）理論，旨在盡量保持資料資訊的前提下去除資料備援。
資料解壓縮（又被稱為源解碼，source decoding），執行與壓縮相反過程重構資料流以适應更高效資料應用層對資料表述、了解的需要。
現有壓縮算法根據實作原理的差異，可以被劃分為以下幾類：
- 非适應/自适應（Non-adaptive/ adaptive）：非适應算法不需要針對特殊資料流進行訓練以提升效率，而适應算法則需要有訓練過程。
- 松散/非松散（Lossy/Lossless）：松散算法不保障對原始資料壓縮後的結果唯一，而非松散算法對同樣原始資料的壓縮結果唯一。
- 對稱/非對稱（Symmetric/Asymmetric）：對稱算法對資料的壓縮、解壓縮使用相同的算法實作，通過執行不同的代碼路徑切換壓縮解壓縮過程；非對稱算法則在資料壓縮、解壓縮過程分别使用不同的算法。
對于具體的時序資料流壓縮解壓縮過程，一個壓縮算法執行個體（encoder）輸入s體量的時序資料流TS，傳回壓縮後的體量s′的時序資料流TS′，且s>s′包涵一同壓縮的時間戳字段E(TS) = TS′。解壓縮算法執行個體（decoder）的執行過程則是從壓縮資料流還源原始的時序資料流D(TS′) = TS，若TS = TSs則壓縮算法是非松散的，否則就是松散的。
2.3 品質指數（quality indices）
為了度量時序資料壓縮算法的性能，通常需要考慮三點特性：壓縮率、壓縮速度、精确度。
- 壓縮率：衡量壓縮算法對原始時序資料壓縮比率，可以定義為：
其中，s′代表時序資料壓縮後的體量，s為時序資料壓縮前的原始體量。的轉置又被稱為壓縮因數，而品質指數（quality indices）則是被用來表述壓縮收益的名額，其定義為：
- 速度：度量壓縮算法執行速度，通常用每位元組壓縮周期的平均執行時間（Cycles Per Byte，CPB）。
- 精确度：又被稱為失真度量（Distortion Criteria，DC），衡量被壓縮算法重構後的時序資料保留資訊可信度。為适應不同場景度量需要，可以用多種度量名額來确定，常用的名額有：
Mean Squared Error：
Root Mean Squared Error:
Signal to Noise Ratio:
Peak Signal to Noise Ratio:
3 壓縮算法
目前常用的時序資料壓縮算法主要有以下幾種：
1) Dictionary-Based (DB)
1.1. TRISTAN
1.2. CONRAD
1.3. A-LZSS
1.4. D-LZW
2) Functional Approximation (FA)
2.1. Piecewise Polynomial Approximation (PPA)
2.2. Chebyshev Polynomial Transform (CPT)
2.3. Discrete Wavelet Transform (DWT)
3) Autoencoders:
3.1. Recurrent Neural Network Autoencoder (RNNA)
4) Sequential Algorithms (SA)
4.1. Delta encoding, Run-length and Huffman (DRH)
4.2. Sprintz
4.3. Run-Length Binary Encoding (RLBE)
4.4. RAKE
5) Others:
5.1. Major Extrema Extractor (MEE)
5.2. Segment Merging (SM)
5.3. Continuous Hidden Markov Chain (CHMC)
3.1 Dictionary-Based (DB)
DB算法實作理念是通過識别時序資料都存在的相同片段，并将片段定義為原子片段并以更精簡的辨別标記替代，形成字典供使用時以辨別作為Key恢複，這種方式能夠在保證較高資料壓縮比的同時，降低錯誤率。此技術實作的壓縮可能是無損的，具體取決于實作情況。此架構的主要挑戰是：
• 最大限度地提高搜尋速度，以便在字典中查找時間系列片段；
• 使存儲在 dictionary 中的時間串段盡可能一般，以最大限度地縮短壓縮階段的距離。
TRISTAN是基于DB政策實作的一種算法，TRISTAN算法把壓縮劃分為兩個階段處理，第一階段适應性學習，第二階段資料壓縮。在學習階段，TRISTAN字典表通過學習訓練資料集來生成，或者結合專家經驗定義特定模式的原子片段。有了字典表，在壓縮階段TRISTAN算法執行從以下公式中檢索w的過程。
s=w·D w ∈ {0,1}k
其中，D是字典表，s為原子片段，K是壓縮後的時序表征資料長度。TRISTAN解壓過程則是通字典表D解釋表征資料w得到原始時序資料的過程。
CORAD算法在TRISTAN基礎之上增加了自動資料關聯資訊，對兩兩時序資料片斷進行基于Pearson相關系數的度量，以相鄰矩陣M存儲相關性，通過M與字典表D相結合的計算方式，進一步提升壓縮比和資料解壓精确度。
Accelerometer LZSS（A-LZSS）算法是基于LZSS搜尋比對算法的DB政策實作，A-LZSS算法使用Huffman編碼，以離線方式通過統計資料機率分布生成。
Differential LZW (D-LZW)算法核心思想是建立一個非常大的字典表，它會随着時間的推移而增長。一旦字典表被建立，如果在字典表中發現緩沖區塊，它就會被相應的索引替換，否則，新方塊将插入字典作為新的條目。增加新的緩存區塊是在保證非松散壓縮的原則下實作，并不限制增加的數量，但随之而來的問題就是字典表有可能無限膨脹，這就導緻D-LZW算法隻适用于特定場景，比如輸入時序資料流為有限詞組或可枚舉字元集組成。
Zstandard（zstd）是一種基于Huffman編碼Entropy coder實作的快速非松散DB壓縮算法，字典表作為一個可選選項支撐參數控制開啟關閉。算法實作由Facebook開源，支援壓縮速度與壓縮比之間的按需調整，能夠通過犧牲壓縮速度來換取更高壓縮比，反之亦然。相比同類算法，zstd算法性能可參考下表資料。
| 算法類型 | 壓縮比 | 壓縮速度 | 解壓速度 |
| zstd 1.4.5-1 | 2.884 | 500 MB/s | 1660 MB/s |
| zlib 1.2.11 -1 | 2.743 | 90 MB/s | 400 MB/s |
| brotli 1.0.7 -0 | 2.703 | 450 MB/s | |
| zstd 1.4.5 --fast=1 | 2.434 | 570 MB/s | 2200 MB/s |
| zstd 1.4.5 --fast=3 | 2.312 | 640 MB/s | 2300 MB/s |
| quicklz 1.5.0 -1 | 2.238 | 560 MB/s | 710 MB/s |
| zstd 1.4.5 --fast=5 | 2.178 | 700 MB/s | 2420 MB/s |
| lzo1x 2.10 -1 | 2.106 | 690 MB/s | 820 MB/s |
| lz4 1.9.2 | 2.101 | 740 MB/s | 4530 MB/s |
| lzf 3.6 -1 | 2.077 | 410 MB/s | 860 MB/s |
| snappy 1.1.8 | 2.073 | 1790 MB/s |
表 zstd算法性能對比
3.2 Function Approximation (FA)
函數近似類時序壓縮算法FA的主要設計思想是假設時間序列可以表示為時間函數。由于難以避免出現無法處理的新值，找出能夠準确描述整個時間序列的函數是不可行的，是以我們可以将時間序列劃分成多個片段，對每個段找到一個近似時間函數來描述。
由于找到一個能完整描述時間序列的函數 f:T → X 是不可行的，是以實作上我們需要考慮找出一個函數簇，以及其對映的參數來描述分段時序資料相對可行，但這也使得壓縮算法為松散的實作。
相比之下，FA類算法優點是它不依賴于資料取值範圍，是以不需要有基于樣本資料集的訓練階段，如果采用回歸算法，我們隻需要單獨考慮劃分好的單個時間片段。
Piecewise Polynomial Approximation (PPA)是FA類算法的常用實作，此技術将時間序列分為固定長度或可變長度的多個段，并嘗試找到接近細分的最佳多項式表述。盡管壓縮是有損的，但可以先于原始資料的最大偏差進行修複，以實作給定的重建精度。PPA算法應用貪婪的方法和三種不同的線上回歸算法來近似恒定的函數、直線和多項式。Chebyshev Polynomial Transform (CPT)實作原理與PPA算法類似，隻是改進了支援使用不同類型多項式的能力。Discrete Wavelet Transform (DWT)使用Wavelet小波轉換對時序資料進行轉換。Wavelet是描述起止值都為0，中間值在此之間波動的函數，
3.3 Autoencoders
Autoencoder是一種特殊的神經網絡，被訓練生成用來處理時序資料。算法架構由對稱的兩部分組成：編碼器encoder和解碼器decoder。在給定n維時序資料輸入的前提下，Autoencoder的編碼器輸出m（m<n）維的輸出。解碼器decoder則可以将m維輸出還原為n維輸入。Recurrent Neural Network Autoencoder (RNNA)是Autoencoder的一種典型實作，通過RNN來實作對時序資料的壓縮表述。
圖 Autoencoder算法實作結構
3.4 序列化算法Sequential Algorithms（SA）
序列化算法SA實作原理是順序融合多種簡單壓縮技術實作對時序資料壓縮，常用技術有：
• Huffman coding：編碼器建立一個字典，将每個符号關聯到二進制表示，并以相應的表示替換原始資料的每個符号。
• Delta encoding：此技術對目标檔案進行編碼，以處理一個或多個參考檔案。在時間系列的特定情況下，每個元素在 t 被編碼為∆（xt,xt=1）。
• Run-length encoding：在此技術中，每個運作（連續重複相同值的序列）都與對（vt, o）進行子圖，其中vt是時間t值，o是連續發生次數。
• Fibonacci binary encoding：此編碼技術基于 Fibonacci 序列實作。
Delta encoding, Run-length and Huffman (DRH)算法是一種融合了Delta encoding、Huffman coding、Run-length encoding和Huffman coding四種技術的壓縮算法，算法實作是非松散的且計算複雜度相對較小，适合在邊緣短實作對資料的壓縮解壓，也是以适合應用在物聯網、工業網際網路、車聯網等需要邊緣短采集處理時序資料的場景。
Sprintz就是一種專門針對物聯網場景設計的SA算法，在算法設計中考慮了對物聯網場景中能源消耗、速度等時序名額波動規律因素，為以下需求而特别優化了算法設計：
- 對較小片段資料的快速處理
- 底計算複雜度的壓縮、解壓縮，以适應邊緣端有限的計算資源
- 對實時采集時序資料的快速壓縮、解壓縮
- 非松散壓縮
為了在處理IoT物聯網環境時序資料上取得更好的壓縮效果，Sprintz算法通過預測資料生成趨勢的方式來提升算法對資料的壓縮性能，其主要實作的算法過程包括以下幾部分：
- 預測：基于delta encoding或FIRE算法通過統計曆史時序資料，對新樣本資料生成規律進行預測；
- Bit packing：打包預測錯誤資訊資料和標頭描述用來解壓資料的資訊；
- Run-length encoding：如果壓縮過程中通過預測算法未發現任何錯誤資訊，則略過bit packing過程的錯誤資訊發送，并在下次發生錯誤時在打包預測錯誤資訊的標頭中記錄略過的資料長度；
- Entropy coding：用Huffman coding對big packing生成的封包件進行編碼。
Run-Length Binary Encoding (RLBE)算法 也是一種為IoT物聯網場景下資料壓縮解壓，适應物聯網邊緣端有限計算、存儲資源環境的常用非松散SA時序資料壓縮算法，RLBE算法融合了delta encoding，run-length encoding和Fibonacci coding三種技術，其執行過程如下圖所示。
圖 Run-Length Binary Encoding (RLBE)算法執行過程圖示
RAKE算法原理是通過檢測時序資料稀疏性來實作對資料的壓縮。RAKE為非松散壓縮，執行過程包涵預處理和壓縮兩個主要過程。預處理過程中，RAKE算法設計由字典表來轉換原始資料。壓縮過程則對預處理的輸出資料進行稀疏性檢測，壓縮相鄰的相同資料。
3.5 其他類型算法
Major Extrema Extractor (MEE)算法通過統計指定時間段的時序資料最大、最小值來對資料進行壓縮。Segment Merging (SM)算法則把時序資料抽象為時間戳和值及偏差組成的片段，可用元組(t,y,δ)表述，其中t為開始時間，y是數值常量辨別，δ是資料片段偏差。Continuous Hidden Markov Chain (CHMC)算法則利用馬爾可夫鍊機率模型來将時序資料定義為一系列有限狀态節點集合S及連結節點的狀态遷移機率邊集合A。
4 總結
時序資料是物聯網、工業網際網路、車聯網等場景下生成資料總量中占比最高的資料類型，有效的壓縮算法不但可以降低資料存儲成本，同時可以在邊緣到中心，中心到雲的資料傳輸過程中節約網帶寬資源，降低資料同步時間。對于作為時序資料核心存儲中樞的時序資料庫，壓縮算法性能更是至關重要。阿裡雲多模資料庫Lindorm核心資料庫引擎之一時序引擎Lindorm TSDB内置的自研、高效資料壓縮算法針對物聯網、工業網際網路、車聯網等智能、互聯場景針對性優化，進一步提升了時序資料存儲的ROI，新一代雲原生智能互聯系統提供必要支撐。