前言
ClickHouse在近年來增加了很多壓縮算法，最主要的改進還是為了更好的适應時序場景，提高壓縮率，節省存儲空間。本期就給大家帶來ClickHouse的壓縮算法介紹。
算法分類
ClickHouse的壓縮/解壓代碼相對比較清晰，抽象做的很好，這樣對于後續增加、變更某種壓縮算法會非常的友善。這裡就不給大家介紹代碼結構，直接從比較核心的算法講起。目前ClickHouse中提供的壓縮算法非常豐富，總體上可以劃分為三類：
- 通用壓縮算法：适用于所有資料的壓縮，包括：None、LZ4、ZSTD。
- 列/時序壓縮算法：适合按列存儲資料，尤其适合時序場景，需要知道每列的特性來選擇，包括：T64、Delta、DoubleDelta、Gorilla。
- 組合壓縮算法：這種壓縮本身并不包含任何壓縮算法，實際上是将以上算法組合使用，使綜合壓縮率進一步提升。
None
Clickhouse是支援完全不壓縮的，帶來的好處就是讀取不消耗CPU，但是相對存儲量會大很多，IO也會有巨大的開銷，一般不建議使用這種模式。
- 注：為了相容壓縮邏輯，内部實作為memcpy。
LZ4
非常高效的壓縮算法，在SLS内部大量使用，壓縮和解壓性能都極強，尤其是解壓性能可達到單核4GB/s。缺點是壓縮率有點低（但是在日志場景可以達到5-15倍的壓縮率，還是非常适用的）。
LZ4的壓縮原理是按照4位元組視窗掃描，查找與之前的值是否比對，如果比對按照貪心算法比對最長值，壓縮格式的示例如下。LZ4的格式非常簡單，是以解壓隻需要順序掃描一遍，做一些memcpy即可完成，是以解壓速度極快。具體的細節可以參考
https://github.com/lz4/lz4。
raw：abcde_bcdefgh_abcdefghxxxxxxx
compressed：abcde_(5,4)fgh_(14,5)fghxxxxxxx lz4裡面和壓縮性能息息相關的是Hash函數，官網是用了xxHash，性能也是非常棒，SLS内部很多和Hash有關的代碼都是用xxHash。實作可以參考：
https://github.com/lz4/lz4/blob/dev/lib/xxhash.hZSTD
雖然壓縮/解壓效率不如LZ4，但是也可以達到單核400M/s的壓縮和1G/s左右的解壓（具體需要看資料特性以及機器規格）。和LZ4相比最好的是壓縮率，我們測試了實際的線上資料，壓縮率相比LZ4可以提升30%，也就是說可以節省30%的存儲空間。而SLS目前的機器CPU使用率比較低，但是存儲水位比較高，是以我們将部分資料改為了ZSTD以節省磁盤。相比LZ4它可以根據參數調整壓縮速度（速度提升帶來的效果就是壓縮率會變低）。
基準測試可以參考：
https://github.com/facebook/zstd。ZSTD背後的男人其實是一個熵編碼器（論文：
https://arxiv.org/abs/1311.2540，代碼：
https://github.com/Cyan4973/FiniteStateEntropy），作者叫他FSE（Finite State Entropy）（有限狀态熵）。
T64
2019年新引入的編碼方式，T64隻支援int/uint類型的壓縮。首先壓縮前拿到資料類型，然後會計算資料的Max Min，根據Max Min獲得有效的bit位，然後把資料映射到64*bit位的空間，由于64是固定的，是以叫做T64（transpose 64 bit matrix）。這種壓縮方式對于變化不大或很小的資料有很高的壓縮率，但是因為隻去掉了頭部的bit位，剩下的可能還有很多重複的部分，是以大部分場景下還是嵌套一個LZ4/ZSTD來使用（嵌套的壓縮方式下面會介紹）。
T64壓縮中有個選項是控制轉換的粒度，預設是按照位元組來轉換（及滿1個位元組的直接按照1個位元組來拷貝，位元組内的bit不做轉換），如果是bit模式的話每個位元組還會做一個轉換，這樣的情況下每個位元組都會多一次反轉，還是很耗費性能的，但是搭配ZSTD會具有較高的壓縮率（如果搭配LZ4的效果反而會差）。之是以是這樣還是因為LZ4和ZSTD實作機制的不同，額外做一輪Bit的轉換，是讓相同的bit能夠更加集中，熵編碼的效果會更好，但是帶來的後果就是位元組之間的連貫性會變差，LZ4是查找Byte的相同點，轉換後基本都不一樣了，是以效果會變差。
Delta
Delta編碼存儲一個基礎值以及後續相鄰兩個資料的內插補點，對于有恒定/變化特别小內插補點的情況下效果比較好，一般情況下Delta編碼需要配合LZ4或者ZSTD來吧後面的插值部分進一步壓縮。
raw : 5 6 7 8 9 10 11 12 13 ....
Delta : 5(Base) 1 1 1 1 1 1 1 1 .... Double Delta
最早出現于Facebook的Gorilla中（
http://www.vldb.org/pvldb/vol8/p1816-teller.pdf），存儲的是Delta後的Delta，對于恒定增加/減小的值，Delta一般是一個固定值，但是這個值可大可小，存儲起來還是占用比較大的空間，如果再次對Delta計算Delta，則大多數情況下為0。對于大資料場景，尤其是監控場景中，這一類資料非常常見，比如時間列通常都是固定的N秒一個點；自增列每次都是加1；請求次數/流量等累加值，通常變化也會比較平均。對于Delta of Delta的編碼細節還是很多的，主要的目的還是減少存儲的資料量，增大資訊熵，有興趣的同學可以看看論文。
raw : 1589636543 1589636553 1589636563 1589636573 1589636583 1589636594 1589636603...
Delta of Delta : 1589636543(Base) 10(Delta) 0 0 0 1 -1 ... - 注意：Double Delta還一個特性是支援Compressed read（也就是不解壓出原始的資料，直接在壓縮的block上讀取想要的資料），但由于ClickHouse把壓縮做了一層抽象，是以隻能解壓後再讀。
Gorilla
Double Delta主要适應于int類型的壓縮，而對于Double Gorilla中也提出一個專門的壓縮算法，但沒有起一個特性的名稱，最後大家都叫它Gorilla算法。
| 符号位 | 指數位 | 尾數位 |
|---|---|---|
| 1 bit | 11 bits | 52 bits |
對于一個64位float，有1個符号位，11個指數位和52個尾數位，純粹從每個部分來看變化都很小，但float通常用來表示某個實際意義的值（比如GPS、溫度、請求成功率），直接按照每個部分計算Double Delta再編碼效果會很差。而Gorilla算法是通過異或的形式來計算前後的Delta，然後再看異或值的前後0個數，最後隻儲存前後0個數、中間有效位。而Delta之間則先比較異或值前後0個數，如果相同則隻需要寫中間的有效位。
具體的結構可以參考：
- 注意：ClickHose的Gorilla算法也一樣不支援Compressed read。
Multiple
Multiple其實并不是一個壓縮算法，而是一個包裝類，能夠組合N個前種算法。例如組合T64、ZSTD，這個Multiple就會在壓縮的時候先調用T64，然後調用ZSTD，解壓的時候調用LZ4解壓然後再調用T64解壓。
compress : T64 -> ZSTD
uncompress : ZSTD -> T64 多種壓縮算法搭配使用的情況也非常常見，SLS内部有很多就是用了類似的算法，SLS中很多索引的編碼都是用了2-3套壓縮算法組合，像在時序引擎上面的壓縮算法種類更多，有些會用4-5種算法組合。
總結
ClickHouse新增的T64、Delta、Double Delta、Gorilla算法其實主要還是針對時序場景，這些算法基本上都是針對前後變化不大的資料設計，是以在時序場景中會獲得非常高的壓縮比。
唯一的缺憾是：由于ClickHouse對壓縮/解壓做了一層抽象，一些能夠支援壓縮讀的算法還是需要解壓讀，效率上會有所損失。
此外還有一些比較常用的Prefix編碼、RLE等其實也非常好用，且性能極高，也支援壓縮讀，希望ClickHouse也會支援。