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

[[425748]]

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

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

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

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

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

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

二、背景技術(shù)介紹

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

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ù)學(xué)范式表達(dá)時序可以被定義為：

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

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

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

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

• 非適應(yīng)/自適應(yīng)(Non-adaptive/ adaptive)：非適應(yīng)算法不需要針對特殊數(shù)據(jù)流進(jìn)行訓(xùn)練以提升效率，而適應(yīng)算法則需要有訓(xùn)練過程。
• 松散/非松散(Lossy/Lossless)：松散算法不保障對原始數(shù)據(jù)壓縮后的結(jié)果唯一，而非松散算法對同樣原始數(shù)據(jù)的壓縮結(jié)果唯一。
• 對稱/非對稱(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. 品質(zhì)指數(shù)(quality indices)

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

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

ρ=s's

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

cg=100loge1ρ

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

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

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ù)都存在的相同片段，并將片段定義為原子片段并以更精簡的標(biāo)識標(biāo)記替代，形成字典供使用時以標(biāo)識作為Key恢復(fù)，這種方式能夠在保證較高數(shù)據(jù)壓縮比的同時，降低錯誤率。此技術(shù)實現(xiàn)的壓縮可能是無損的，具體取決于實現(xiàn)情況。此架構(gòu)的主要挑戰(zhàn)是：

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

TRISTAN是基于DB策略實現(xiàn)的一種算法，TRISTAN算法把壓縮劃分為兩個階段處理，第一階段適應(yīng)性學(xué)習(xí)，第二階段數(shù)據(jù)壓縮。在學(xué)習(xí)階段，TRISTAN字典表通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)集來生成，或者結(jié)合專家經(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基礎(chǔ)之上增加了自動數(shù)據(jù)關(guān)聯(lián)信息，對兩兩時序數(shù)據(jù)片斷進(jìn)行基于Pearson相關(guān)系數(shù)的度量，以相鄰矩陣M存儲相關(guān)性，通過M與字典表D相結(jié)合的計算方式，進(jìn)一步提升壓縮比和數(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ū)塊，它就會被相應(yīng)的索引替換，否則，新方塊將插入字典作為新的條目。增加新的緩存區(qū)塊是在保證非松散壓縮的原則下實現(xiàn)，并不限制增加的數(shù)量，但隨之而來的問題就是字典表有可能無限膨脹，這就導(dǎo)致D-LZW算法只適用于特定場景，比如輸入時序數(shù)據(jù)流為有限詞組或可枚舉字符集組成。

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

表 zstd算法性能對比

2. Function Approximation (FA)

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

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

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

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

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

3. Autoencoders

Autoencoder是一種特殊的神經(jīng)網(wǎng)絡(luò)，被訓(xùn)練生成用來處理時序數(shù)據(jù)。算法架構(gòu)由對稱的兩部分組成：編碼器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)結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. 其他類型算法

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

四、總結(jié)

時序數(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ù)庫，壓縮算法性能更是至關(guān)重要。阿里云多模數(shù)據(jù)庫Lindorm核心數(shù)據(jù)庫引擎之一時序引擎Lindorm TSDB內(nèi)置的自研、高效數(shù)據(jù)壓縮算法針對物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等智能、互聯(lián)場景針對性優(yōu)化，進(jìn)一步提升了時序數(shù)據(jù)存儲的ROI，新一代云原生智能互聯(lián)系統(tǒng)提供必要支撐。

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

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