作者 | 李琿

編輯 | 爾悅

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

數據壓縮/解壓縮的流程

壓縮：輸入原始數據，經過壓縮器編碼后，輸出壓縮后的數據。

input data —-> compressor —-> coded data

解壓縮：輸入壓縮過的數據，經過解壓縮器解碼/重建后，輸出原始數據。

coded data —-> decompressor —-> output data

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

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

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

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

時序數據是如何被壓縮的？

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

• 霍夫曼編碼

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

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

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

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

• XOR

該算法是結合遵循 IEEE754 標準浮點數存儲格式的數據特征設計的特定算法，第一個值不壓縮， 后面的值是跟第一個值計算 XOR（異或）的結果，如果結果相同，僅存儲一個 0，如果結果不同，存儲 XOR 后的結果。該算法受數據波動影響較大，波動越劇烈，壓縮效果越差。

• Delta

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

• Delta-of-Delta

又名二階差分編碼，是在 Delta 編碼的基礎上再一次使用 Delta 編碼，比較適合編碼單調遞增或者遞減的序列數據。例如 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 的出現是為了解決 varint 算法對負數編碼效率低的問題，它的原理非常簡單，是將標志位后移至末尾，并去掉編碼中多余的 0，從而達到壓縮的效果。對于比較小的數值壓縮效率很高，但是對于大的數據效率不但沒有提升可能還會有所下降。因此，Zig-zag 通常和 Delta 編碼搭配，Delta 可以很好地將大數值數據變為較小的數值。

• Snappy

Snappy 壓縮算法借鑒了 LZ77 算法的思路，由于 LZ77 算法中模式匹配過程有較高的時間復雜度，Google 對其做了許多優化，并于 2011 年對外開源。其原理是假設我們有一個序列 S=[9,1,2,3,4,5,1,2,3,4]，匹配發現子序列 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 表示位數。Snappy 的優點是速度快，壓縮率合理，在眾多開源項目中使用較為廣泛，比如 Cassandra、Hadoop、MongoDB、RocksDB、Spark、InfluxDB 等。

• LZ4

LZ4 數據壓縮算法屬于面向字節的 LZ77 壓縮方案家族，壓縮比并不高，它的特點是解碼速度極快。據官方測試基準 lzbench 的測試結果，默認配置下其解壓速度高達 4970MB/s。

• Simple8b

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

• LZO

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

• DEFLATE

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

• Zstandard

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

• Bit-packing

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

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

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

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