目前，物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等智能互聯(lián)技術在各個行業(yè)場景下快速普及應用，導致聯(lián)網(wǎng)傳感器、智能設備數(shù)量急劇增加，隨之而來的海量時序監(jiān)控數(shù)據(jù)存儲、處理問題，也為時序數(shù)據(jù)庫高效壓縮、存儲數(shù)據(jù)能力提出了更高的要求。對于通量愈加龐大的物聯(lián)網(wǎng)時序大數(shù)據(jù)存儲，盡管標準壓縮方法還能發(fā)揮其價值，但某些場景對時序數(shù)據(jù)壓縮解壓技術效率、性能提出了新的需求。本文介紹了現(xiàn)有的時序數(shù)據(jù)壓縮解壓技術，分類介紹了不同算法的特點和優(yōu)劣勢。

[[425748]]

時序數(shù)據(jù)普遍存在于IoT物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等相關場景，物聯(lián)網(wǎng)設備已遍布各種行業(yè)場景應用，從可穿戴設備到工業(yè)生產(chǎn)設備，都會或將會產(chǎn)生大量數(shù)據(jù)。比如，新型波音787客機每次飛行傳感器產(chǎn)生的數(shù)據(jù)量都在500GB左右。在這些場景下，通常具備高并發(fā)寫和高通量數(shù)據(jù)處理特點，選擇時序數(shù)據(jù)壓縮算法需要全方位考慮數(shù)據(jù)采集、存儲、分析的需要。特別需要注意的是業(yè)務應用對時序數(shù)據(jù)當前和歷史數(shù)據(jù)分析的方式，選擇壓縮算法不當將可能導致關鍵信息丟失，從而影響分析結果。對于業(yè)務來說，更直接使用時序數(shù)據(jù)壓縮技術的應用就是時序數(shù)據(jù)庫，對于時序數(shù)據(jù)庫壓縮解壓是關鍵數(shù)據(jù)處理步驟，壓縮算法性能直接影響時序數(shù)據(jù)庫建設投入的ROI。

一、時序數(shù)據(jù)壓縮

對于數(shù)據(jù)壓縮算法，業(yè)界存在更普遍的解釋，通常是針對通用場景和業(yè)務相關場景，比如視頻、音頻、圖像數(shù)據(jù)流壓縮。本文重點介紹時序數(shù)據(jù)庫中常用的面向時序數(shù)據(jù)設計或可用于時序數(shù)據(jù)處理的通用壓縮算法。我們選擇分析的算法具備對更普遍場景下持續(xù)產(chǎn)生時序數(shù)據(jù)壓縮處理的能力，并對IoT物聯(lián)網(wǎng)場景傳感器數(shù)據(jù)壓縮的以下特點做了特殊設計：

• 數(shù)據(jù)冗余(Redundancy)：一些特定模式的時序數(shù)據(jù)經(jīng)常性重復出現(xiàn)在一個或多個時間序列。
• 函數(shù)估算(Approximability)：某些傳感器產(chǎn)生的時序數(shù)據(jù)生成模式可以根據(jù)預定義函數(shù)估算。
• 趨勢預測(Predictability)：某些時序數(shù)據(jù)未來趨勢可以通過算法預測，例如利用回歸、深度神經(jīng)網(wǎng)絡等技術。

圖 時序數(shù)據(jù)壓縮算法分類

本文重點總結了時序數(shù)據(jù)庫和物聯(lián)網(wǎng)IoT傳感器管理常用壓縮算法，并根據(jù)技術方法(dictionary-based, functional approximation, autoencoders, sequential等)和技術屬性(adaptiveness, lossless reconstruction, symmetry, tuneability)對碎片化的壓縮技術進行了分類，詳細參考上圖，并針對主要算法性能進行了對比分析。

二、背景技術介紹

在介紹壓縮算法之前，我們先對時序數(shù)據(jù)、壓縮和品質指數(shù)(quality indices)幾個關鍵的概念進行定義。

1. 時序數(shù)據(jù)(Time Series)

時序數(shù)據(jù)指數(shù)據(jù)元組根據(jù)時間戳(ti)升序排列的數(shù)據(jù)集合，可以被劃分為：

• 單變量時序(Univariate Time Series，UTS)：每次采集的數(shù)據(jù)元組集合為單個實數(shù)變量。
• 多變量時序(Multivariate Time Series ，MTS)：每次采集的數(shù)據(jù)元組集合由多個實數(shù)序列組成，每個組成部分對映時序一個特征。

比如，圖2中股票價格在指定時間窗口的波動可以被定義為單變量時序數(shù)據(jù)，而每天交易信息(如：開盤、收盤價格，交易量等)則可以定義為多變量時序數(shù)據(jù)。

圖 股票交易UTS時序數(shù)據(jù)樣例

用數(shù)學范式表達時序可以被定義為：

2. 數(shù)據(jù)壓縮

數(shù)據(jù)壓縮(又被稱為源編碼，source coding)，根據(jù)David Salmon在《Data Compression: The Complete Reference》一書中的定義，可以簡單描述為“將輸入原始數(shù)據(jù)流轉變?yōu)樽址?bit stream)或壓縮流的體量更小的輸出數(shù)據(jù)流的過程”。這個過程遵循J. G.Wolff提出的Simplicity Power(SP)理論，旨在盡量保持數(shù)據(jù)信息的前提下去除數(shù)據(jù)冗余。

數(shù)據(jù)解壓縮(又被稱為源解碼，source decoding)，執(zhí)行與壓縮相反過程重構數(shù)據(jù)流以適應更高效數(shù)據(jù)應用層對數(shù)據(jù)表述、理解的需要。

現(xiàn)有壓縮算法根據(jù)實現(xiàn)原理的差異，可以被劃分為以下幾類：

• 非適應/自適應(Non-adaptive/ adaptive)：非適應算法不需要針對特殊數(shù)據(jù)流進行訓練以提升效率，而適應算法則需要有訓練過程。
• 松散/非松散(Lossy/Lossless)：松散算法不保障對原始數(shù)據(jù)壓縮后的結果唯一，而非松散算法對同樣原始數(shù)據(jù)的壓縮結果唯一。
• 對稱/非對稱(Symmetric/Asymmetric)：對稱算法對數(shù)據(jù)的壓縮、解壓縮使用相同的算法實現(xiàn)，通過執(zhí)行不同的代碼路徑切換壓縮解壓縮過程;非對稱算法則在數(shù)據(jù)壓縮、解壓縮過程分別使用不同的算法。

對于具體的時序數(shù)據(jù)流壓縮解壓縮過程，一個壓縮算法實例(encoder)輸入s體量的時序數(shù)據(jù)流TS，返回壓縮后的體量s′的時序數(shù)據(jù)流TS′，且s>s′包含一同壓縮的時間戳字段E(TS) = TS′。解壓縮算法實例(decoder)的執(zhí)行過程則是從壓縮數(shù)據(jù)流還源原始的時序數(shù)據(jù)流D(TS′) = TS，若TS = TSs則壓縮算法是非松散的，否則就是松散的。

3. 品質指數(shù)(quality indices)

為了度量時序數(shù)據(jù)壓縮算法的性能，通常需要考慮三點特性：壓縮率、壓縮速度、精確度。

(1) 壓縮率：衡量壓縮算法對原始時序數(shù)據(jù)壓縮比率，可以定義為：

ρ=s's

其中，s′代表時序數(shù)據(jù)壓縮后的體量，s為時序數(shù)據(jù)壓縮前的原始體量。ρ的轉置又被稱為壓縮因數(shù)，而品質指數(shù)(quality indices)則是被用來表述壓縮收益的指標，其定義為：

cg=100loge1ρ

(2) 速度：度量壓縮算法執(zhí)行速度，通常用每字節(jié)壓縮周期的平均執(zhí)行時間(Cycles Per Byte，CPB)。

(3) 精確度：又被稱為失真度量(Distortion Criteria，DC)，衡量被壓縮算法重構后的時序數(shù)據(jù)保留信息可信度。為適應不同場景度量需要，可以用多種度量指標來確定，常用的指標有：

Mean Squared Error：

Root Mean Squared Error：

Signal to Noise Ratio：

Peak Signal to Noise Ratio：

三、壓縮算法

目前常用的時序數(shù)據(jù)壓縮算法主要有以下幾種：

(1) Dictionary-Based (DB)

• TRISTAN1.2. CONRAD1.3. A-LZSS1.4. D-LZW

(2) Functional Approximation (FA)

• Piecewise Polynomial Approximation (PPA)
• Chebyshev Polynomial Transform (CPT)
• Discrete Wavelet Transform (DWT)

(3) Autoencoders:

•  Recurrent Neural Network Autoencoder (RNNA)

(4) Sequential Algorithms (SA)

• Delta encoding, Run-length and Huffman (DRH)
• Sprintz
• Run-Length Binary Encoding (RLBE)
• RAKE

(5) Others:

• Major Extrema Extractor (MEE)
• Segment Merging (SM)
• Continuous Hidden Markov Chain (CHMC)

1. Dictionary-Based (DB)

DB算法實現(xiàn)理念是通過識別時序數(shù)據(jù)都存在的相同片段，并將片段定義為原子片段并以更精簡的標識標記替代，形成字典供使用時以標識作為Key恢復，這種方式能夠在保證較高數(shù)據(jù)壓縮比的同時，降低錯誤率。此技術實現(xiàn)的壓縮可能是無損的，具體取決于實現(xiàn)情況。此架構的主要挑戰(zhàn)是：

• 最大限度地提高搜索速度，以便在字典中查找時間系列片段;
• 使存儲在 dictionary 中的時間串段盡可能一般，以最大限度地縮短壓縮階段的距離。

TRISTAN是基于DB策略實現(xiàn)的一種算法，TRISTAN算法把壓縮劃分為兩個階段處理，第一階段適應性學習，第二階段數(shù)據(jù)壓縮。在學習階段，TRISTAN字典表通過學習訓練數(shù)據(jù)集來生成，或者結合專家經(jīng)驗定義特定模式的原子片段。有了字典表，在壓縮階段TRISTAN算法執(zhí)行從以下公式中檢索w的過程。

s=w·D w ∈ {0,1}k

其中，D是字典表，s為原子片段，K是壓縮后的時序表征數(shù)據(jù)長度。TRISTAN解壓過程則是通字典表D解釋表征數(shù)據(jù)w得到原始時序數(shù)據(jù)的過程。

CORAD算法在TRISTAN基礎之上增加了自動數(shù)據(jù)關聯(lián)信息，對兩兩時序數(shù)據(jù)片斷進行基于Pearson相關系數(shù)的度量，以相鄰矩陣M存儲相關性，通過M與字典表D相結合的計算方式，進一步提升壓縮比和數(shù)據(jù)解壓精確度。

Accelerometer LZSS(A-LZSS)算法是基于LZSS搜索匹配算法的DB策略實現(xiàn)，A-LZSS算法使用Huffman編碼，以離線方式通過統(tǒng)計數(shù)據(jù)概率分布生成。

Differential LZW (D-LZW)算法核心思想是創(chuàng)建一個非常大的字典表，它會隨著時間的推移而增長。一旦字典表被創(chuàng)建，如果在字典表中發(fā)現(xiàn)緩沖區(qū)塊，它就會被相應的索引替換，否則，新方塊將插入字典作為新的條目。增加新的緩存區(qū)塊是在保證非松散壓縮的原則下實現(xiàn)，并不限制增加的數(shù)量，但隨之而來的問題就是字典表有可能無限膨脹，這就導致D-LZW算法只適用于特定場景，比如輸入時序數(shù)據(jù)流為有限詞組或可枚舉字符集組成。

Zstandard(zstd)是一種基于Huffman編碼Entropy coder實現(xiàn)的快速非松散DB壓縮算法，字典表作為一個可選選項支撐參數(shù)控制開啟關閉。算法實現(xiàn)由Facebook開源，支持壓縮速度與壓縮比之間的按需調整，能夠通過犧牲壓縮速度來換取更高壓縮比，反之亦然。相比同類算法，zstd算法性能可參考下表數(shù)據(jù)。

表 zstd算法性能對比

2. Function Approximation (FA)

函數(shù)近似類時序壓縮算法FA的主要設計思想是假設時間序列可以表示為時間函數(shù)。由于難以避免出現(xiàn)無法處理的新值，找出能夠準確描述整個時間序列的函數(shù)是不可行的，因此我們可以將時間序列劃分成多個片段，對每個段找到一個近似時間函數(shù)來描述。

由于找到一個能完整描述時間序列的函數(shù) f:T → X 是不可行的，因此實現(xiàn)上我們需要考慮找出一個函數(shù)簇，以及其對映的參數(shù)來描述分段時序數(shù)據(jù)相對可行，但這也使得壓縮算法為松散的實現(xiàn)。

相比之下，F(xiàn)A類算法優(yōu)點是它不依賴于數(shù)據(jù)取值范圍，因此不需要有基于樣本數(shù)據(jù)集的訓練階段，如果采用回歸算法，我們只需要單獨考慮劃分好的單個時間片段。

Piecewise Polynomial Approximation (PPA)是FA類算法的常用實現(xiàn)，此技術將時間序列分為固定長度或可變長度的多個段，并嘗試找到接近細分的最佳多項式表述。盡管壓縮是有損的，但可以先于原始數(shù)據(jù)的最大偏差進行修復，以實現(xiàn)給定的重建精度。PPA算法應用貪婪的方法和三種不同的在線回歸算法來近似恒定的函數(shù)、直線和多項式。

Chebyshev Polynomial Transform (CPT)實現(xiàn)原理與PPA算法類似，只是改進了支持使用不同類型多項式的能力。Discrete Wavelet Transform (DWT)使用Wavelet小波轉換對時序數(shù)據(jù)進行轉換。Wavelet是描述起止值都為0，中間值在此之間波動的函數(shù)。

3. Autoencoders

Autoencoder是一種特殊的神經(jīng)網(wǎng)絡，被訓練生成用來處理時序數(shù)據(jù)。算法架構由對稱的兩部分組成：編碼器encoder和解碼器decoder。在給定n維時序數(shù)據(jù)輸入的前提下，Autoencoder的編碼器輸出m(m<n)維的輸出。解碼器decoder則可以將m維輸出還原為n維輸入。Recurrent Neural Network Autoencoder (RNNA)是Autoencoder的一種典型實現(xiàn)，通過RNN來實現(xiàn)對時序數(shù)據(jù)的壓縮表述。

圖 Autoencoder算法實現(xiàn)結構

4. 序列化算法Sequential Algorithms(SA)

序列化算法SA實現(xiàn)原理是順序融合多種簡單壓縮技術實現(xiàn)對時序數(shù)據(jù)壓縮，常用技術有：

• Huffman coding：編碼器創(chuàng)建一個字典，將每個符號關聯(lián)到二進制表示，并以相應的表示替換原始數(shù)據(jù)的每個符號。

• Delta encoding：此技術對目標文件進行編碼，以處理一個或多個參考文件。在時間系列的特定情況下，每個元素在 t 被編碼為∆(xt,xt=1)。

• Run-length encoding：在此技術中，每個運行(連續(xù)重復相同值的序列)都與對(vt, o)進行子圖，其中vt是時間t值，o是連續(xù)發(fā)生次數(shù)。

• Fibonacci binary encoding：此編碼技術基于 Fibonacci 序列實現(xiàn)。

Delta encoding, Run-length and Huffman (DRH)算法是一種融合了Delta encoding、Huffman coding、Run-length encoding和Huffman coding四種技術的壓縮算法，算法實現(xiàn)是非松散的且計算復雜度相對較小，適合在邊緣短實現(xiàn)對數(shù)據(jù)的壓縮解壓，也因此適合應用在物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等需要邊緣短采集處理時序數(shù)據(jù)的場景。

Sprintz就是一種專門針對物聯(lián)網(wǎng)場景設計的SA算法，在算法設計中考慮了對物聯(lián)網(wǎng)場景中能源消耗、速度等時序指標波動規(guī)律因素，為以下需求而特別優(yōu)化了算法設計：

• 對較小片段數(shù)據(jù)的快速處理
• 底計算復雜度的壓縮、解壓縮，以適應邊緣端有限的計算資源
• 對實時采集時序數(shù)據(jù)的快速壓縮、解壓縮
• 非松散壓縮

為了在處理IoT物聯(lián)網(wǎng)環(huán)境時序數(shù)據(jù)上取得更好的壓縮效果，Sprintz算法通過預測數(shù)據(jù)生成趨勢的方式來提升算法對數(shù)據(jù)的壓縮性能，其主要實現(xiàn)的算法過程包括以下幾部分：

• 預測：基于delta encoding或FIRE算法通過統(tǒng)計歷史時序數(shù)據(jù)，對新樣本數(shù)據(jù)生成規(guī)律進行預測;
• Bit packing：打包預測錯誤信息數(shù)據(jù)和包頭描述用來解壓數(shù)據(jù)的信息;
• Run-length encoding：如果壓縮過程中通過預測算法未發(fā)現(xiàn)任何錯誤信息，則略過bit packing過程的錯誤信息發(fā)送，并在下次發(fā)生錯誤時在打包預測錯誤信息的包頭中記錄略過的數(shù)據(jù)長度;
• Entropy coding：用Huffman coding對big packing生成的包文件進行編碼。

Run-Length Binary Encoding (RLBE)算法 也是一種為IoT物聯(lián)網(wǎng)場景下數(shù)據(jù)壓縮解壓，適應物聯(lián)網(wǎng)邊緣端有限計算、存儲資源環(huán)境的常用非松散SA時序數(shù)據(jù)壓縮算法，RLBE算法融合了delta encoding，run-length encoding和Fibonacci coding三種技術，其執(zhí)行過程如下圖所示。

圖 Run-Length Binary Encoding (RLBE)算法執(zhí)行過程圖示

RAKE算法原理是通過檢測時序數(shù)據(jù)稀疏性來實現(xiàn)對數(shù)據(jù)的壓縮。RAKE為非松散壓縮，執(zhí)行過程包涵預處理和壓縮兩個主要過程。預處理過程中，RAKE算法設計由字典表來轉換原始數(shù)據(jù)。壓縮過程則對預處理的輸出數(shù)據(jù)進行稀疏性檢測，壓縮相鄰的相同數(shù)據(jù)。

5. 其他類型算法

Major Extrema Extractor (MEE)算法通過統(tǒng)計指定時間段的時序數(shù)據(jù)最大、最小值來對數(shù)據(jù)進行壓縮。Segment Merging (SM)算法則把時序數(shù)據(jù)抽象為時間戳和值及偏差組成的片段，可用元組(t,y,δ)表述，其中t為開始時間，y是數(shù)值常量標識，δ是數(shù)據(jù)片段偏差。Continuous Hidden Markov Chain (CHMC)算法則利用馬爾可夫鏈概率模型來將時序數(shù)據(jù)定義為一系列有限狀態(tài)節(jié)點集合S及鏈接節(jié)點的狀態(tài)遷移概率邊集合A。

四、總結

時序數(shù)據(jù)是物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等場景下生成數(shù)據(jù)總量中占比最高的數(shù)據(jù)類型，有效的壓縮算法不但可以降低數(shù)據(jù)存儲成本，同時可以在邊緣到中心，中心到云的數(shù)據(jù)傳輸過程中節(jié)約網(wǎng)帶寬資源，降低數(shù)據(jù)同步時間。對于作為時序數(shù)據(jù)核心存儲中樞的時序數(shù)據(jù)庫，壓縮算法性能更是至關重要。阿里云多模數(shù)據(jù)庫Lindorm核心數(shù)據(jù)庫引擎之一時序引擎Lindorm TSDB內置的自研、高效數(shù)據(jù)壓縮算法針對物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等智能、互聯(lián)場景針對性優(yōu)化，進一步提升了時序數(shù)據(jù)存儲的ROI，新一代云原生智能互聯(lián)系統(tǒng)提供必要支撐。

【本文為51CTO專欄作者“阿里巴巴官方技術”原創(chuàng)稿件，轉載請聯(lián)系原作者】

戳這里，看該作者更多好文