目前,物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等智能互聯(lián)技術(shù)在各個(gè)行業(yè)場(chǎng)景下快速普及應(yīng)用,導(dǎo)致聯(lián)網(wǎng)傳感器、智能設(shè)備數(shù)量急劇增加,隨之而來的海量時(shí)序監(jiān)控?cái)?shù)據(jù)存儲(chǔ)、處理問題,也為時(shí)序數(shù)據(jù)庫(kù)高效壓縮、存儲(chǔ)數(shù)據(jù)能力提出了更高的要求。對(duì)于通量愈加龐大的物聯(lián)網(wǎng)時(shí)序大數(shù)據(jù)存儲(chǔ),盡管標(biāo)準(zhǔn)壓縮方法還能發(fā)揮其價(jià)值,但某些場(chǎng)景對(duì)時(shí)序數(shù)據(jù)壓縮解壓技術(shù)效率、性能提出了新的需求。本文介紹了現(xiàn)有的時(shí)序數(shù)據(jù)壓縮解壓技術(shù),分類介紹了不同算法的特點(diǎn)和優(yōu)劣勢(shì)。
時(shí)序數(shù)據(jù)普遍存在于IoT物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等相關(guān)場(chǎng)景,物聯(lián)網(wǎng)設(shè)備已遍布各種行業(yè)場(chǎng)景應(yīng)用,從可穿戴設(shè)備到工業(yè)生產(chǎn)設(shè)備,都會(huì)或?qū)?huì)產(chǎn)生大量數(shù)據(jù)。比如,新型波音787客機(jī)每次飛行傳感器產(chǎn)生的數(shù)據(jù)量都在500GB左右。在這些場(chǎng)景下,通常具備高并發(fā)寫和高通量數(shù)據(jù)處理特點(diǎn),選擇時(shí)序數(shù)據(jù)壓縮算法需要全方位考慮數(shù)據(jù)采集、存儲(chǔ)、分析的需要。特別需要注意的是業(yè)務(wù)應(yīng)用對(duì)時(shí)序數(shù)據(jù)當(dāng)前和歷史數(shù)據(jù)分析的方式,選擇壓縮算法不當(dāng)將可能導(dǎo)致關(guān)鍵信息丟失,從而影響分析結(jié)果。對(duì)于業(yè)務(wù)來說,更直接使用時(shí)序數(shù)據(jù)壓縮技術(shù)的應(yīng)用就是時(shí)序數(shù)據(jù)庫(kù),對(duì)于時(shí)序數(shù)據(jù)庫(kù)壓縮解壓是關(guān)鍵數(shù)據(jù)處理步驟,壓縮算法性能直接影響時(shí)序數(shù)據(jù)庫(kù)建設(shè)投入的ROI。
一、時(shí)序數(shù)據(jù)壓縮
對(duì)于數(shù)據(jù)壓縮算法,業(yè)界存在更普遍的解釋,通常是針對(duì)通用場(chǎng)景和業(yè)務(wù)相關(guān)場(chǎng)景,比如視頻、音頻、圖像數(shù)據(jù)流壓縮。本文重點(diǎn)介紹時(shí)序數(shù)據(jù)庫(kù)中常用的面向時(shí)序數(shù)據(jù)設(shè)計(jì)或可用于時(shí)序數(shù)據(jù)處理的通用壓縮算法。我們選擇分析的算法具備對(duì)更普遍場(chǎng)景下持續(xù)產(chǎn)生時(shí)序數(shù)據(jù)壓縮處理的能力,并對(duì)IoT物聯(lián)網(wǎng)場(chǎng)景傳感器數(shù)據(jù)壓縮的以下特點(diǎn)做了特殊設(shè)計(jì):
- 數(shù)據(jù)冗余(Redundancy):一些特定模式的時(shí)序數(shù)據(jù)經(jīng)常性重復(fù)出現(xiàn)在一個(gè)或多個(gè)時(shí)間序列。
- 函數(shù)估算(Approximability):某些傳感器產(chǎn)生的時(shí)序數(shù)據(jù)生成模式可以根據(jù)預(yù)定義函數(shù)估算。
- 趨勢(shì)預(yù)測(cè)(Predictability):某些時(shí)序數(shù)據(jù)未來趨勢(shì)可以通過算法預(yù)測(cè),例如利用回歸、深度神經(jīng)網(wǎng)絡(luò)等技術(shù)。
圖 時(shí)序數(shù)據(jù)壓縮算法分類
本文重點(diǎn)總結(jié)了時(shí)序數(shù)據(jù)庫(kù)和物聯(lián)網(wǎng)IoT傳感器管理常用壓縮算法,并根據(jù)技術(shù)方法(dictionary-based, functional approximation, autoencoders, sequential等)和技術(shù)屬性(adaptiveness, lossless reconstruction, symmetry, tuneability)對(duì)碎片化的壓縮技術(shù)進(jìn)行了分類,詳細(xì)參考上圖,并針對(duì)主要算法性能進(jìn)行了對(duì)比分析。
二、背景技術(shù)介紹
在介紹壓縮算法之前,我們先對(duì)時(shí)序數(shù)據(jù)、壓縮和品質(zhì)指數(shù)(quality indices)幾個(gè)關(guān)鍵的概念進(jìn)行定義。
1. 時(shí)序數(shù)據(jù)(Time Series)
時(shí)序數(shù)據(jù)指數(shù)據(jù)元組根據(jù)時(shí)間戳(ti)升序排列的數(shù)據(jù)集合,可以被劃分為:
- 單變量時(shí)序(Univariate Time Series,UTS):每次采集的數(shù)據(jù)元組集合為單個(gè)實(shí)數(shù)變量。
- 多變量時(shí)序(Multivariate Time Series ,MTS):每次采集的數(shù)據(jù)元組集合由多個(gè)實(shí)數(shù)序列組成,每個(gè)組成部分對(duì)映時(shí)序一個(gè)特征。
比如,圖2中股票價(jià)格在指定時(shí)間窗口的波動(dòng)可以被定義為單變量時(shí)序數(shù)據(jù),而每天交易信息(如:開盤、收盤價(jià)格,交易量等)則可以定義為多變量時(shí)序數(shù)據(jù)。
圖 股票交易UTS時(shí)序數(shù)據(jù)樣例
用數(shù)學(xué)范式表達(dá)時(shí)序可以被定義為:
2. 數(shù)據(jù)壓縮
數(shù)據(jù)壓縮(又被稱為源編碼,source coding),根據(jù)David Salmon在《Data Compression: The Complete Reference》一書中的定義,可以簡(jiǎn)單描述為“將輸入原始數(shù)據(jù)流轉(zhuǎn)變?yōu)樽址?bit stream)或壓縮流的體量更小的輸出數(shù)據(jù)流的過程”。這個(gè)過程遵循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)用層對(duì)數(shù)據(jù)表述、理解的需要。
現(xiàn)有壓縮算法根據(jù)實(shí)現(xiàn)原理的差異,可以被劃分為以下幾類:
- 非適應(yīng)/自適應(yīng)(Non-adaptive/ adaptive):非適應(yīng)算法不需要針對(duì)特殊數(shù)據(jù)流進(jìn)行訓(xùn)練以提升效率,而適應(yīng)算法則需要有訓(xùn)練過程。
- 松散/非松散(Lossy/Lossless):松散算法不保障對(duì)原始數(shù)據(jù)壓縮后的結(jié)果唯一,而非松散算法對(duì)同樣原始數(shù)據(jù)的壓縮結(jié)果唯一。
- 對(duì)稱/非對(duì)稱(Symmetric/Asymmetric):對(duì)稱算法對(duì)數(shù)據(jù)的壓縮、解壓縮使用相同的算法實(shí)現(xiàn),通過執(zhí)行不同的代碼路徑切換壓縮解壓縮過程;非對(duì)稱算法則在數(shù)據(jù)壓縮、解壓縮過程分別使用不同的算法。
對(duì)于具體的時(shí)序數(shù)據(jù)流壓縮解壓縮過程,一個(gè)壓縮算法實(shí)例(encoder)輸入s體量的時(shí)序數(shù)據(jù)流TS,返回壓縮后的體量s′的時(shí)序數(shù)據(jù)流TS′,且s>s′包含一同壓縮的時(shí)間戳字段E(TS) = TS′。解壓縮算法實(shí)例(decoder)的執(zhí)行過程則是從壓縮數(shù)據(jù)流還源原始的時(shí)序數(shù)據(jù)流D(TS′) = TS,若TS = TSs則壓縮算法是非松散的,否則就是松散的。
3. 品質(zhì)指數(shù)(quality indices)
為了度量時(shí)序數(shù)據(jù)壓縮算法的性能,通常需要考慮三點(diǎn)特性:壓縮率、壓縮速度、精確度。
(1) 壓縮率:衡量壓縮算法對(duì)原始時(shí)序數(shù)據(jù)壓縮比率,可以定義為:
ρ=s's
其中,s′代表時(shí)序數(shù)據(jù)壓縮后的體量,s為時(shí)序數(shù)據(jù)壓縮前的原始體量。ρ的轉(zhuǎn)置又被稱為壓縮因數(shù),而品質(zhì)指數(shù)(quality indices)則是被用來表述壓縮收益的指標(biāo),其定義為:
cg=100loge1ρ
(2) 速度:度量壓縮算法執(zhí)行速度,通常用每字節(jié)壓縮周期的平均執(zhí)行時(shí)間(Cycles Per Byte,CPB)。
(3) 精確度:又被稱為失真度量(Distortion Criteria,DC),衡量被壓縮算法重構(gòu)后的時(shí)序數(shù)據(jù)保留信息可信度。為適應(yīng)不同場(chǎng)景度量需要,可以用多種度量指標(biāo)來確定,常用的指標(biāo)有:
Mean Squared Error:
Root Mean Squared Error:
Signal to Noise Ratio:
Peak Signal to Noise Ratio:
三、壓縮算法
目前常用的時(shí)序數(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算法實(shí)現(xiàn)理念是通過識(shí)別時(shí)序數(shù)據(jù)都存在的相同片段,并將片段定義為原子片段并以更精簡(jiǎn)的標(biāo)識(shí)標(biāo)記替代,形成字典供使用時(shí)以標(biāo)識(shí)作為Key恢復(fù),這種方式能夠在保證較高數(shù)據(jù)壓縮比的同時(shí),降低錯(cuò)誤率。此技術(shù)實(shí)現(xiàn)的壓縮可能是無損的,具體取決于實(shí)現(xiàn)情況。此架構(gòu)的主要挑戰(zhàn)是:
- 最大限度地提高搜索速度,以便在字典中查找時(shí)間系列片段;
- 使存儲(chǔ)在 dictionary 中的時(shí)間串段盡可能一般,以最大限度地縮短壓縮階段的距離。
TRISTAN是基于DB策略實(shí)現(xiàn)的一種算法,TRISTAN算法把壓縮劃分為兩個(gè)階段處理,第一階段適應(yīng)性學(xué)習(xí),第二階段數(shù)據(jù)壓縮。在學(xué)習(xí)階段,TRISTAN字典表通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)集來生成,或者結(jié)合專家經(jīng)驗(yàn)定義特定模式的原子片段。有了字典表,在壓縮階段TRISTAN算法執(zhí)行從以下公式中檢索w的過程。
s=w·D w ∈ {0,1}k
其中,D是字典表,s為原子片段,K是壓縮后的時(shí)序表征數(shù)據(jù)長(zhǎng)度。TRISTAN解壓過程則是通字典表D解釋表征數(shù)據(jù)w得到原始時(shí)序數(shù)據(jù)的過程。
CORAD算法在TRISTAN基礎(chǔ)之上增加了自動(dòng)數(shù)據(jù)關(guān)聯(lián)信息,對(duì)兩兩時(shí)序數(shù)據(jù)片斷進(jìn)行基于Pearson相關(guān)系數(shù)的度量,以相鄰矩陣M存儲(chǔ)相關(guān)性,通過M與字典表D相結(jié)合的計(jì)算方式,進(jìn)一步提升壓縮比和數(shù)據(jù)解壓精確度。
Accelerometer LZSS(A-LZSS)算法是基于LZSS搜索匹配算法的DB策略實(shí)現(xiàn),A-LZSS算法使用Huffman編碼,以離線方式通過統(tǒng)計(jì)數(shù)據(jù)概率分布生成。
Differential LZW (D-LZW)算法核心思想是創(chuàng)建一個(gè)非常大的字典表,它會(huì)隨著時(shí)間的推移而增長(zhǎng)。一旦字典表被創(chuàng)建,如果在字典表中發(fā)現(xiàn)緩沖區(qū)塊,它就會(huì)被相應(yīng)的索引替換,否則,新方塊將插入字典作為新的條目。增加新的緩存區(qū)塊是在保證非松散壓縮的原則下實(shí)現(xiàn),并不限制增加的數(shù)量,但隨之而來的問題就是字典表有可能無限膨脹,這就導(dǎo)致D-LZW算法只適用于特定場(chǎng)景,比如輸入時(shí)序數(shù)據(jù)流為有限詞組或可枚舉字符集組成。
Zstandard(zstd)是一種基于Huffman編碼Entropy coder實(shí)現(xiàn)的快速非松散DB壓縮算法,字典表作為一個(gè)可選選項(xiàng)支撐參數(shù)控制開啟關(guān)閉。算法實(shí)現(xiàn)由Facebook開源,支持壓縮速度與壓縮比之間的按需調(diào)整,能夠通過犧牲壓縮速度來?yè)Q取更高壓縮比,反之亦然。相比同類算法,zstd算法性能可參考下表數(shù)據(jù)。
表 zstd算法性能對(duì)比
2. Function Approximation (FA)
函數(shù)近似類時(shí)序壓縮算法FA的主要設(shè)計(jì)思想是假設(shè)時(shí)間序列可以表示為時(shí)間函數(shù)。由于難以避免出現(xiàn)無法處理的新值,找出能夠準(zhǔn)確描述整個(gè)時(shí)間序列的函數(shù)是不可行的,因此我們可以將時(shí)間序列劃分成多個(gè)片段,對(duì)每個(gè)段找到一個(gè)近似時(shí)間函數(shù)來描述。
由于找到一個(gè)能完整描述時(shí)間序列的函數(shù) f:T → X 是不可行的,因此實(shí)現(xiàn)上我們需要考慮找出一個(gè)函數(shù)簇,以及其對(duì)映的參數(shù)來描述分段時(shí)序數(shù)據(jù)相對(duì)可行,但這也使得壓縮算法為松散的實(shí)現(xiàn)。
相比之下,F(xiàn)A類算法優(yōu)點(diǎn)是它不依賴于數(shù)據(jù)取值范圍,因此不需要有基于樣本數(shù)據(jù)集的訓(xùn)練階段,如果采用回歸算法,我們只需要單獨(dú)考慮劃分好的單個(gè)時(shí)間片段。
Piecewise Polynomial Approximation (PPA)是FA類算法的常用實(shí)現(xiàn),此技術(shù)將時(shí)間序列分為固定長(zhǎng)度或可變長(zhǎng)度的多個(gè)段,并嘗試找到接近細(xì)分的最佳多項(xiàng)式表述。盡管壓縮是有損的,但可以先于原始數(shù)據(jù)的最大偏差進(jìn)行修復(fù),以實(shí)現(xiàn)給定的重建精度。PPA算法應(yīng)用貪婪的方法和三種不同的在線回歸算法來近似恒定的函數(shù)、直線和多項(xiàng)式。
Chebyshev Polynomial Transform (CPT)實(shí)現(xiàn)原理與PPA算法類似,只是改進(jìn)了支持使用不同類型多項(xiàng)式的能力。Discrete Wavelet Transform (DWT)使用Wavelet小波轉(zhuǎn)換對(duì)時(shí)序數(shù)據(jù)進(jìn)行轉(zhuǎn)換。Wavelet是描述起止值都為0,中間值在此之間波動(dòng)的函數(shù)。
3. Autoencoders
Autoencoder是一種特殊的神經(jīng)網(wǎng)絡(luò),被訓(xùn)練生成用來處理時(shí)序數(shù)據(jù)。算法架構(gòu)由對(duì)稱的兩部分組成:編碼器encoder和解碼器decoder。在給定n維時(shí)序數(shù)據(jù)輸入的前提下,Autoencoder的編碼器輸出m(m
圖 Autoencoder算法實(shí)現(xiàn)結(jié)構(gòu)
序列化算法SA實(shí)現(xiàn)原理是順序融合多種簡(jiǎn)單壓縮技術(shù)實(shí)現(xiàn)對(duì)時(shí)序數(shù)據(jù)壓縮,常用技術(shù)有:
? Huffman coding:編碼器創(chuàng)建一個(gè)字典,將每個(gè)符號(hào)關(guān)聯(lián)到二進(jìn)制表示,并以相應(yīng)的表示替換原始數(shù)據(jù)的每個(gè)符號(hào)。
? Delta encoding:此技術(shù)對(duì)目標(biāo)文件進(jìn)行編碼,以處理一個(gè)或多個(gè)參考文件。在時(shí)間系列的特定情況下,每個(gè)元素在 t 被編碼為?(xt,xt=1)。
? Run-length encoding:在此技術(shù)中,每個(gè)運(yùn)行(連續(xù)重復(fù)相同值的序列)都與對(duì)(vt, o)進(jìn)行子圖,其中vt是時(shí)間t值,o是連續(xù)發(fā)生次數(shù)。
? Fibonacci binary encoding:此編碼技術(shù)基于 Fibonacci 序列實(shí)現(xiàn)。
Delta encoding, Run-length and Huffman (DRH)算法是一種融合了Delta encoding、Huffman coding、Run-length encoding和Huffman coding四種技術(shù)的壓縮算法,算法實(shí)現(xiàn)是非松散的且計(jì)算復(fù)雜度相對(duì)較小,適合在邊緣短實(shí)現(xiàn)對(duì)數(shù)據(jù)的壓縮解壓,也因此適合應(yīng)用在物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等需要邊緣短采集處理時(shí)序數(shù)據(jù)的場(chǎng)景。
Sprintz就是一種專門針對(duì)物聯(lián)網(wǎng)場(chǎng)景設(shè)計(jì)的SA算法,在算法設(shè)計(jì)中考慮了對(duì)物聯(lián)網(wǎng)場(chǎng)景中能源消耗、速度等時(shí)序指標(biāo)波動(dòng)規(guī)律因素,為以下需求而特別優(yōu)化了算法設(shè)計(jì):
為了在處理IoT物聯(lián)網(wǎng)環(huán)境時(shí)序數(shù)據(jù)上取得更好的壓縮效果,Sprintz算法通過預(yù)測(cè)數(shù)據(jù)生成趨勢(shì)的方式來提升算法對(duì)數(shù)據(jù)的壓縮性能,其主要實(shí)現(xiàn)的算法過程包括以下幾部分:
Run-Length Binary Encoding (RLBE)算法 也是一種為IoT物聯(lián)網(wǎng)場(chǎng)景下數(shù)據(jù)壓縮解壓,適應(yīng)物聯(lián)網(wǎng)邊緣端有限計(jì)算、存儲(chǔ)資源環(huán)境的常用非松散SA時(shí)序數(shù)據(jù)壓縮算法,RLBE算法融合了delta encoding,run-length encoding和Fibonacci coding三種技術(shù),其執(zhí)行過程如下圖所示。
圖 Run-Length Binary Encoding (RLBE)算法執(zhí)行過程圖示
RAKE算法原理是通過檢測(cè)時(shí)序數(shù)據(jù)稀疏性來實(shí)現(xiàn)對(duì)數(shù)據(jù)的壓縮。RAKE為非松散壓縮,執(zhí)行過程包涵預(yù)處理和壓縮兩個(gè)主要過程。預(yù)處理過程中,RAKE算法設(shè)計(jì)由字典表來轉(zhuǎn)換原始數(shù)據(jù)。壓縮過程則對(duì)預(yù)處理的輸出數(shù)據(jù)進(jìn)行稀疏性檢測(cè),壓縮相鄰的相同數(shù)據(jù)。
Major Extrema Extractor (MEE)算法通過統(tǒng)計(jì)指定時(shí)間段的時(shí)序數(shù)據(jù)最大、最小值來對(duì)數(shù)據(jù)進(jìn)行壓縮。Segment Merging (SM)算法則把時(shí)序數(shù)據(jù)抽象為時(shí)間戳和值及偏差組成的片段,可用元組(t,y,δ)表述,其中t為開始時(shí)間,y是數(shù)值常量標(biāo)識(shí),δ是數(shù)據(jù)片段偏差。Continuous Hidden Markov Chain (CHMC)算法則利用馬爾可夫鏈概率模型來將時(shí)序數(shù)據(jù)定義為一系列有限狀態(tài)節(jié)點(diǎn)集合S及鏈接節(jié)點(diǎn)的狀態(tài)遷移概率邊集合A。
時(shí)序數(shù)據(jù)是物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等場(chǎng)景下生成數(shù)據(jù)總量中占比最高的數(shù)據(jù)類型,有效的壓縮算法不但可以降低數(shù)據(jù)存儲(chǔ)成本,同時(shí)可以在邊緣到中心,中心到云的數(shù)據(jù)傳輸過程中節(jié)約網(wǎng)帶寬資源,降低數(shù)據(jù)同步時(shí)間。對(duì)于作為時(shí)序數(shù)據(jù)核心存儲(chǔ)中樞的時(shí)序數(shù)據(jù)庫(kù),壓縮算法性能更是至關(guān)重要。阿里云多模數(shù)據(jù)庫(kù)Lindorm核心數(shù)據(jù)庫(kù)引擎之一時(shí)序引擎Lindorm TSDB內(nèi)置的自研、高效數(shù)據(jù)壓縮算法針對(duì)物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)等智能、互聯(lián)場(chǎng)景針對(duì)性優(yōu)化,進(jìn)一步提升了時(shí)序數(shù)據(jù)存儲(chǔ)的ROI,新一代云原生智能互聯(lián)系統(tǒng)提供必要支撐。
原文地址:https://zhuanlan.51cto.com/art/202109/683526.htm
4. 序列化算法Sequential Algorithms(SA)
5. 其他類型算法
四、總結(jié)