211
MySQL · 實現分析 · HybridDB for MySQL 數據壓縮
概述
數據壓縮是一個把輸入數據集按照一定的算法變換成更小的數據集的過程，解壓是壓縮的逆過程。如果算法對數據本身的語義了解得越多，則越可能利用語義信息進行針對性的處理，獲得更好的壓縮效果。數據庫係統中用得比較多的壓縮算法可以分為兩大類：基於塊的壓縮、基於值的壓縮。前者更為常見一些，在 OLTP 以及 OLAP 係統中都會用到，例如 InnoDB、TokuDB、HybridDB 中的塊壓縮；後者更多的用在 OLAP 的列存引擎內，例如 HybridDB for MySQL 中的列壓縮。為了區別它們，這裏把塊壓縮簡稱為壓縮（Compression）、而把基於值的壓縮稱為編碼（Encoding）。此外，在存儲係統中比較常見的重複數據刪除功能也可以被視為一種特殊形式的壓縮。不過它不屬於本文要考慮的範圍。
通常來說，列存格式對壓縮要更友好。大概而言，行存的數據壓縮率一般為3:1(采用通用壓縮算法）；列存的數據壓縮率為10:1（采用編碼以及通用的壓縮算法）。
無論是哪種形式的壓縮，衡量算法本身是否適用的指標主要有：
1. 壓縮率，也就是壓縮前後數據大小的比率。
2. 吞吐量，也就是壓縮和解壓的速度。典型單位為 GB/s。
3. 資源消耗，壓縮解壓一般是計算密集型的算法，因此主要考慮的是 CPU 消耗。
壓縮
壓縮算法可以說是無處不在。常見的例子如各種文件壓縮工具背後的壓縮算法，包括 zip、rar 等等；各種圖片格式對應的壓縮算法，包括 png、jpeg 等等。數據庫係統中用的都是無損壓縮，圖片壓縮則可以采用有損壓縮。很多算法都屬於 lz 係列，例如：lz、lzo、quicklz 等等。多年以前 Google 推出的 Snappy ，雖然壓縮率不是特別出眾，但是吞吐量比較大、資源消耗比較小，因此獲得了廣泛的應用。最近幾年 Facebook 推出的 zstd 算法具有類似的特征，也獲得了很多應用。zstd 的主頁上有一些測試的數據，可以作為參考：
編碼
編碼則是利用數據的語義信息進行更加有針對性的壓縮。當然，很多算法也在通用的壓縮算法中被采用了。常見的編碼算法有：行程編碼（Run Length Encoding）、字典編碼（Dictionary）、差值編碼（Delta）、變長整數編碼（Varint）、位變換（Bit Shuffle）、前綴編碼（Prefix）、異或（XOR）等等。甚至可以說有多少種數據的規律就可以發明出多少種編碼算法。例如：InfoBright 就可以對一係列的數字除以最大公約數，獲得更小的數字，從而達到數據壓縮的目的。
產品
下麵讓我們來看一看典型的幾個 OLAP 產品對壓縮算法的支持。
Apache Kudu
Apache Kudu 是一個比較有意思的項目，它支持多副本、列存，試圖解決實時分析的需求。下圖是它支持的編碼/壓縮方法：
相對其他係統而言，Kudu 編碼中比較特殊的一種是 BitShuffle 編碼。假設輸入的是類型 T 的一個數組，該編碼的算法是：先保存每個值的 MSB 位（最高位），然後下一個 bit 位，一直到最後的 LSB（最低位）；然後對數據進行 LZ4 壓縮。該編碼適合與重複值較多的列或者列值變化不大的情況。除了上述的編碼之外，Kudu 也支持通用壓縮算法，例如：lz4、snappy、zlib。默認情況下，列是不壓縮的。而且 Bitshuffle 編碼後的列總是自動采用 lz4 壓縮。
Amazon RedShift
Amazon RedShift 支持的編碼/壓縮算法如下：
從圖中可以看出，RedShift 支持 Delta、字典、RLE、Mostly、Text255 等編碼。比較特別的是 Text255 和 text32k，它們適合與單詞重複出現的 VARCHAR 列。實際上，它就是對每個 1MB 塊中的單詞創建了一個字典。字典容納 245 個唯一的單詞，數據實際存儲的時候用一個字節的索引代替對應的單詞。
Pivotal GPDB
Pivotal GPDB 的 Append Only Table 也支持壓縮算法 。
相對而言，GPDB 支持的編碼和壓縮種類要稍少一些。但是它允許設置算法的壓縮級別以及塊的大小。
總結
不同的通用壓縮算法在壓縮率和速度以及資源消耗之間做了不同程度的權衡，有些算法（例如 zlib）還提供了一些壓縮級別的參數可供調整。針對不同的數據集合，壓縮率也存在較大的區別。例如：在采用某個特定數據集的測試中，snappy 的壓縮率接近 3，而 zlib 和 zstd 的壓縮率大約為 4。編碼算法的壓縮率對數據集的類型和取值更為敏感，例如 delta 算法對整數類型，並且相鄰數據之間差別較小的情況下（例如自增列），壓縮比就很好。對於浮點數而言，提高要縮率更為困難，Facebook 等曾經做過一些針對性的優化。
如果想要了解數據壓縮的基本背景，請參考：Data compression tutorial 。如果想要獲得對列存係統的更多知識（包括列存對數據壓縮的優化），則建議移步：Column store tutorial 。
參考資料
1.Snappy
2.Zstd
3.Apache Kudu
4.Amazon RedShift
5.GreenPlum Database
6.Gorilla
7.Data compression tutorial
8.Column store tutorial
最後更新：2017-07-21 09:03:12