作者 | 李琿

編輯 | 爾悅

小 T 導(dǎo)讀：眾所周知，壓縮算法的目的主要是為了減少存儲空間或傳輸帶寬，通過把原始數(shù)據(jù)轉(zhuǎn)換成比原始格式更緊湊的形式，來提高數(shù)據(jù)的傳輸、存儲和處理效率。我們熟悉的很多壓縮軟件都是借助非常復(fù)雜的算法才得以實(shí)現(xiàn)，像一些時序數(shù)據(jù)庫（Time-Series Database），比如 TDengine，也是通過內(nèi)置壓縮功能，才能實(shí)現(xiàn)對時序數(shù)據(jù)的高比例壓縮。那具體來說，數(shù)據(jù)壓縮的流程是怎樣的？時序數(shù)據(jù)庫中常見的數(shù)據(jù)編碼和壓縮算法又有哪些呢？本篇文章將會從具體實(shí)踐出發(fā)進(jìn)行經(jīng)驗(yàn)分享。

數(shù)據(jù)壓縮/解壓縮的流程

壓縮：輸入原始數(shù)據(jù)，經(jīng)過壓縮器編碼后，輸出壓縮后的數(shù)據(jù)。

input data —-> compressor —-> coded data

解壓縮：輸入壓縮過的數(shù)據(jù)，經(jīng)過解壓縮器解碼/重建后，輸出原始數(shù)據(jù)。

coded data —-> decompressor —-> output data

如果輸出數(shù)據(jù)和輸入數(shù)據(jù)始終完全相同，那么這個壓縮方案被稱為可逆壓縮，也稱無損編碼器。否則，它就是一個非可逆壓縮，也稱有損編碼器。

• 可逆壓縮：能夠無失真地從壓縮后的數(shù)據(jù)重構(gòu)，準(zhǔn)確地還原原始數(shù)據(jù)?？捎糜趯?shù)據(jù)準(zhǔn)確性要求嚴(yán)格的場合，如可執(zhí)行文件和普通文件的壓縮、磁盤的壓縮，也可用于多媒體數(shù)據(jù)的壓縮。該方法的壓縮比較小，如差分編碼、RLE、Huffman 編碼、LZW 編碼、算術(shù)編碼。
• 非可逆壓縮：有失真，不能完全準(zhǔn)確地恢復(fù)原始數(shù)據(jù)，重構(gòu)的數(shù)據(jù)只是原始數(shù)據(jù)的一個近似?？捎糜趯?shù)據(jù)的準(zhǔn)確性要求不高的場合，如多媒體數(shù)據(jù)的壓縮。該方法的壓縮率比較高，例如預(yù)測編碼、音感編碼、分形壓縮、小波壓縮、JPEG/MPEG。

我們都知道，數(shù)據(jù)在計(jì)算機(jī)內(nèi)部是以二進(jìn)制方式表示和存儲的，因此，通俗地講，數(shù)據(jù)壓縮就是以最少的比特?cái)?shù)表示數(shù)據(jù)對象。數(shù)據(jù)壓縮的本質(zhì)是用計(jì)算時間換取存儲空間，不同數(shù)據(jù)類型對應(yīng)不同的數(shù)據(jù)壓縮算法，不存在某個壓縮算法能夠壓縮任意數(shù)據(jù)。數(shù)據(jù)壓縮說到底是對數(shù)據(jù)趨勢性、規(guī)律性的總結(jié)，這個數(shù)據(jù)規(guī)律性可分為基于內(nèi)容（比如視頻的幀與幀之間、圖像的像素與像素之間的相似）、基于表示（比如變換編碼、熵編碼）和基于碼流（比如差量壓縮、深度壓縮）等多種級別。

舉一個數(shù)據(jù)壓縮的簡單例子：給定一個字符串”this is a example”，正常情況下，每個字符占用 8 個比特位，假設(shè)該字符串含有 17 個字符（包含空格），每一個字符出現(xiàn)的頻率分別是a(2),e(2),h(1),i(2),m(1),p(1), t(1),s(2),x(1),l(1),空格(3). 現(xiàn)在我們按照字母出現(xiàn)的頻率進(jìn)行編碼，用 111 表示“空格”，001 表示“a”，110 表示“e”，011 表示“i”，000 表示“s”，0101 表示“h”，1011 表示“m”，1000 表示“p”，0100 表示“t”，1010 表示“x”，1001 表示“l(fā)”。最后”this is a example”被編碼成 010001010110001110110001110011101010001101110001001110，共 54 個比特。相比未壓縮前的 136 比特，存儲空間縮小了 2.5 倍。

時序數(shù)據(jù)是如何被壓縮的？

時序數(shù)據(jù)庫（Time-Series Database）中常見的數(shù)據(jù)編碼和壓縮算法有如下幾種：

• 霍夫曼編碼

上面例子中提到的就是霍夫曼編碼。這是一個流傳最為廣泛的壓縮方案，19 世紀(jì) 50 年代，David Huffman 在他的論文“一種構(gòu)建極小多余編碼的方法”中第一次描述了這種方法。霍夫曼編碼通過得到給定字母表的最優(yōu)前綴碼進(jìn)行工作。

要注意的是，這里的一個前綴碼代表一個數(shù)值，并要保證字母表中的每個符號的前綴碼不會成為另一個符號前綴碼的前綴。例如，如果 0 是我們第一個符號 A 的前綴碼，那么字母表中的其他符號都不能以 0 開始。由于前綴碼使比特流解碼變得清晰明確，因此這種機(jī)制還是很有用的。

• 游程編碼（英語：run-length encoding，縮寫RLE）

一種與數(shù)據(jù)性質(zhì)無關(guān)的無損數(shù)據(jù)壓縮技術(shù)，基于“使用變動長度的碼來取代連續(xù)重復(fù)出現(xiàn)的原始數(shù)據(jù)”來實(shí)現(xiàn)壓縮。舉例來說，一組字符串“AAAABBBCCDEEEE” ，由 4 個 A、3 個 B、2 個 C、1 個 D、4 個 E組成，經(jīng)過 RLE 可將字符串壓縮為 4A3B2C1D4E。其優(yōu)點(diǎn)是簡單、速度快，能將連續(xù)且重復(fù)性高的數(shù)據(jù)壓縮成小單位。缺點(diǎn)也是很明顯的，重復(fù)性低的數(shù)據(jù)壓縮效果不好。

• XOR

該算法是結(jié)合遵循 IEEE754 標(biāo)準(zhǔn)浮點(diǎn)數(shù)存儲格式的數(shù)據(jù)特征設(shè)計(jì)的特定算法，第一個值不壓縮， 后面的值是跟第一個值計(jì)算 XOR（異或）的結(jié)果，如果結(jié)果相同，僅存儲一個 0，如果結(jié)果不同，存儲 XOR 后的結(jié)果。該算法受數(shù)據(jù)波動影響較大，波動越劇烈，壓縮效果越差。

• Delta

差分編碼又稱增量編碼，編碼時第一個數(shù)據(jù)不變，其他數(shù)據(jù)轉(zhuǎn)換為上一個數(shù)據(jù)的 delta。其原理與 XOR 類似，都是計(jì)算相鄰兩個數(shù)據(jù)的差異。該算法應(yīng)用廣泛，如需要查看文件的歷史更改記錄（版本控制、Git 等）。但在時序數(shù)據(jù)庫中這種算法很少單獨(dú)使用，一般會搭配 RLE、Simple8b 或者 Zig-zag 一起使用，壓縮效果更好。

• Delta-of-Delta

又名二階差分編碼，是在 Delta 編碼的基礎(chǔ)上再一次使用 Delta 編碼，比較適合編碼單調(diào)遞增或者遞減的序列數(shù)據(jù)。例如 2,4,4,6,8 , Delta編碼后為 2,2,0,2,2 ，再 Delta 編碼后為 2,0,-2,2,0。通常其也會搭配 RLE、Simple8b 或者 Zig-zag 一起使用。

• Zig-zag

Zig-zag 的出現(xiàn)是為了解決 varint 算法對負(fù)數(shù)編碼效率低的問題，它的原理非常簡單，是將標(biāo)志位后移至末尾，并去掉編碼中多余的 0，從而達(dá)到壓縮的效果。對于比較小的數(shù)值壓縮效率很高，但是對于大的數(shù)據(jù)效率不但沒有提升可能還會有所下降。因此，Zig-zag 通常和 Delta 編碼搭配，Delta 可以很好地將大數(shù)值數(shù)據(jù)變?yōu)檩^小的數(shù)值。

• Snappy

Snappy 壓縮算法借鑒了 LZ77 算法的思路，由于 LZ77 算法中模式匹配過程有較高的時間復(fù)雜度，Google 對其做了許多優(yōu)化，并于 2011 年對外開源。其原理是假設(shè)我們有一個序列 S=[9,1,2,3,4,5,1,2,3,4]，匹配發(fā)現(xiàn)子序列 S~2,5~=[1,2,3,4] 與 S~7,10~=[1,2,3,4] 是相同的，于是將該序列編碼為 S=[9,1,2,3,4,5,6,(2,4)]，2 表示開始位置，4 表示位數(shù)。Snappy 的優(yōu)點(diǎn)是速度快，壓縮率合理，在眾多開源項(xiàng)目中使用較為廣泛，比如 Cassandra、Hadoop、MongoDB、RocksDB、Spark、InfluxDB 等。

• LZ4

LZ4 數(shù)據(jù)壓縮算法屬于面向字節(jié)的 LZ77 壓縮方案家族，壓縮比并不高，它的特點(diǎn)是解碼速度極快。據(jù)官方測試基準(zhǔn) lzbench 的測試結(jié)果，默認(rèn)配置下其解壓速度高達(dá) 4970MB/s。

• Simple8b

Simple8b 是 64 位算法，實(shí)現(xiàn)將多個整形數(shù)據(jù)（在 0 和 1<<60 -1 之間）壓縮到一個 64 位的存儲結(jié)構(gòu)中。其中前 4 位表示選擇器，后面 60 位用于存儲數(shù)據(jù)。優(yōu)點(diǎn)是簡單高效，定長編碼保證了解壓效率，但對于大整數(shù)或者浮動較大的值來說壓縮率較低，該算法適用于范圍較小的無符號整數(shù)。

• LZO

LZO 是塊壓縮算法，同樣屬于 LZ77 壓縮方案家族，該算法的目標(biāo)是快速壓縮和解壓縮，并非壓縮比。相比之下，LZ4 的解壓速度更快。由于塊中存放的數(shù)據(jù)類型可能多種多樣，整體的壓縮效果遠(yuǎn)沒有針對某一種數(shù)據(jù)類型進(jìn)行壓縮的算法好。

• DEFLATE

DEFLATE 是同時使用了 LZ77 算法與霍夫曼編碼（Huffman Coding）的一個經(jīng)典無損數(shù)據(jù)壓縮算法。實(shí)際上 DEFLATE 只是一種壓縮數(shù)據(jù)流的算法，該算法是 zip 文件壓縮的默認(rèn)算法，在 gzip、zlib 等算法中都有封裝。

• Zstandard

Zstandard(Zstd) 的設(shè)計(jì)目的是提供一個類似于 DEFLATE 算法的壓縮比，但效果要更快，特別是解壓縮。它的壓縮級別從負(fù) 5 級（最快）到 22 級（壓縮速度最慢，但是壓縮比最高）間可以調(diào)節(jié)。在文本日志壓縮場景中，其壓縮性能與 LZ4、Snappy 相當(dāng)甚至更好。Linux 內(nèi)核、HTTP 協(xié)議、Hadoop、HBase等都已經(jīng)加入對 Zstd 的支持，可以預(yù)見，Zstd 將是未來幾年里被廣泛關(guān)注的壓縮算法。

• Bit-packing

Bit-packing（位壓縮）壓縮算法基于不是所有的整型都需要 32 位或者 64 位來存儲這一前提，從我們要壓縮的數(shù)據(jù)中刪除不必要的位。比如一個 32 位的整型數(shù)據(jù)，其值的范圍在【0,100】之間，則可以用 7 位表示。

最后以 TDengine Database 為例，我們來看一下時序數(shù)據(jù)庫在具體實(shí)現(xiàn)上會如何運(yùn)用壓縮算法。TDengine Database 提供了三種壓縮選項(xiàng)：無壓縮、一階段壓縮和兩階段壓縮。

一階段壓縮根據(jù)數(shù)據(jù)的類型進(jìn)行了相應(yīng)的壓縮，壓縮算法包括 delta-delta 編碼、simple 8B 方法、zig-zag 編碼、LZ4 等算法，這些算法在上文中我們也都簡單介紹過了。二階段壓縮是在一階段壓縮的基礎(chǔ)上，再用通用壓縮算法進(jìn)行了壓縮，以此來保證壓縮率更高。

綜上，我們可以看到壓縮算法的選擇還是非常多的，具體的程序可以根據(jù)壓縮效果和成本綜合選擇。