大數(shù)據(jù)技術已經(jīng)從幾年前的熱門概念落地為實用技術颜懊，為互聯(lián)網(wǎng)貢獻了重要力量。
隨著移動應用發(fā)展吞杭，數(shù)據(jù)緊密包裹用戶，
數(shù)據(jù)分析（OLAP）要求日益提高变丧，數(shù)據(jù)量芽狗、查詢延時都面臨極大挑戰(zhàn)。
這種情況下痒蓬，列存童擎、行列混存數(shù)據(jù)庫技術，在冷門多年后又重新獲得了極大關注攻晒。
我們一起來看個案例顾复，Mark Litwintschik使用十億條的士載客記錄，
在不同的軟硬件平臺上測試了的分析查詢性能：
http://tech.marksblogg.com/benchmarks.html
可以看到炎辨，除了MapD（GPU數(shù)據(jù)分析平臺）遙遙領跑之外捕透，
（跑在8路泰坦、半T內(nèi)存這種怪獸硬件上）
列存數(shù)據(jù)庫ClickHouse僅憑借單機普通硬件碴萧，
就達到了Spark這樣專門的大數(shù)據(jù)平臺的百倍性能乙嘀，非常驚人。
基于此破喻，近期考慮對OLAP架構虎谢，尤其是列存數(shù)據(jù)庫做深入的學習探索，
相關筆記就在此記錄曹质。
一些資料
VLDB婴噩、SIGMOD擎场、ICDE：
數(shù)據(jù)庫技術最重要的期刊會議。
Vertica：
HP的商業(yè)列存數(shù)據(jù)庫几莽，以C-Store為原型迅办，在AWS上有托管分析服務售賣。
在最開始的測試案例中章蚣，可以看到Vertica雖然沒有ClickHouse快站欺，
但也以單機跑出了接近10節(jié)點Spark集群的成績。
Daniel.J.Abadi：
列存數(shù)據(jù)庫C-Store的開發(fā)者纤垂，在各大期刊上發(fā)表過多篇關于列存數(shù)據(jù)庫的Paper矾策。
其09年的“Query Execution in Column-Oriented Database Systems”骗卜，
對列存數(shù)據(jù)庫的各方面都做了詳細敘述愧旦。
何為列存數(shù)據(jù)庫？
我們熟悉的Mysql等數(shù)據(jù)庫析既，是按行存放數(shù)據(jù)的：
+--------+-----+
| name | age |
+--------+-----+
| 孫麗華 | 21 |
| 王永恒 | 23 |
| 張偉朋 | 21 |
+--------+-----+```
這樣的數(shù)據(jù)存儲方式吼鱼，每次增加數(shù)據(jù)可以在末尾增加一行就行蓬豁。
（實際比此復雜）
列存數(shù)據(jù)庫則把行列倒轉，并把不同列分開存放：
+--------+--------+--------+--------+
| name | 孫麗華 | 王永恒 | 張偉朋 |
+--------+--------+--------+--------+
+--------+--------+--------+--------+
| age | 21 | 23 | 21 |
+--------+--------+--------+--------+
列存數(shù)據(jù)庫在增加數(shù)據(jù)時IO不連續(xù)蛉抓，需要在每個列后面追加數(shù)據(jù)庆尘，寫性能不佳，
因此一直沒有成為主流的業(yè)務系統(tǒng)（OLTP）的首選數(shù)據(jù)庫巷送。
如前所述驶忌，大數(shù)據(jù)量下的OLAP是個挑戰(zhàn)，它的用況特征我們可以列舉一下：
- 數(shù)據(jù)是批量導入的笑跛，導入后不修改
- 絕大多數(shù)是讀操作
- 每個表有很多列付魔，分析操作經(jīng)常只涉及小部分列
可以看出，OLAP用況很吻合列存數(shù)據(jù)庫飞蹂，
既避開了列存的細粒度寫性能的劣勢几苍，
又發(fā)揮了讀少數(shù)列時節(jié)省IO、不需要讀無用列的優(yōu)點陈哑。
列存將相似數(shù)據(jù)緊密排列妻坝，對內(nèi)存、CPU和磁盤都很友好惊窖，
這篇筆記的主要關注在（單機下的）列存數(shù)據(jù)在內(nèi)存和CPU的處理刽宪，
磁盤上的存儲布局也是一個較大的話題，會放到另一篇筆記界酒。
# 列存數(shù)據(jù)的SIMD優(yōu)化
數(shù)據(jù)的運算在CPU上進行圣拄，
CPU的數(shù)據(jù)吞吐量（Throughput）越大，計算就越快毁欣，數(shù)據(jù)分析也就越快庇谆。
CPU性能 = 每周期執(zhí)行指令數(shù)（IPC岳掐，Instructions Per Cycle）× 頻率
硬件本身決定了IPC上限和頻率。
90年代饭耳，Intel等CPU廠商設計了MMX串述、SSE等單指令多數(shù)據(jù)（SIMD）的指令集，
顧名思義哥攘，就是一條指令處理一批數(shù)據(jù)剖煌，提高計算能力。
時至如今逝淹，SIMD仍是最重要的優(yōu)化手段之一。
對于列式存放的數(shù)據(jù)桶唐，在內(nèi)存里緊密排列栅葡、大小相同，
可以很容易地進行SIMD處理尤泽，批量地加載進CPU欣簇，由一次CPU指令處理完。
這就在不變的硬件條件下坯约，成倍地提高了數(shù)據(jù)吞吐量熊咽。
緊密數(shù)組的遍歷處理，對CPU流水線很友好闹丐，
即使在代碼中沒有特殊作SIMD處理横殴，
編譯器也可以使用loop-pipelining等手段進行優(yōu)化，達到更高效率卿拴。
# 列存數(shù)據(jù)壓縮
在CPU數(shù)據(jù)吞吐量固定的情況下衫仑，數(shù)據(jù)壓縮是提升處理速度有效途徑。
常見的壓縮算法如lz77堕花、lz78家族文狱，對數(shù)據(jù)都做了變形處理，
然后在一個較大（k級）的數(shù)據(jù)窗口中尋找相同的數(shù)據(jù)達成壓縮缘挽。
這類壓縮的結果與原始數(shù)據(jù)相去甚遠瞄崇，進行計算之前需要解壓，
我們稱為通用壓縮或者重型壓縮（Generic Compression／Heavy Compression）
這類壓縮的特點是壓縮率高壕曼，壓縮慢苏研，解壓較快，消耗CPU資源較多窝稿。
列存數(shù)據(jù)由于相鄰數(shù)據(jù)相似度非常高楣富，
可以進行針對數(shù)據(jù)特征的輕量壓縮（Lightweight Compression）
并可以直接對壓縮處理進行計算。
輕量壓縮消耗CPU資源極少伴榔，壓縮比普遍在1/3-1/4纹蝴，
理想情況下庄萎，可以提升對應倍數(shù)的吞吐量。
# 輕量壓縮的算法框架
###### 輕量壓縮算法有很多種塘安，常用的有：
- 前綴壓縮（Prefix Suppression）：
- 位向量編碼（Bit-Vector Encoding）
- 字典編碼（Dictionary Ecoding）
- 參照系編碼（FOR糠涛，F(xiàn)rame of Reference Encoding）
- 差異編碼（Defferential Encoding／PFOR-DELTA）
###### 下面簡單列一下各個算法的要點。
- 前綴壓縮（Prefix Suppression）：
消除相同前綴兼犯，常用狀況：列中大部分都是小值忍捡，但最大值較大
- 位向量編碼（Bit-Vector Encoding）:
列中大多數(shù)值都相同，比如性別切黔，以1個bit來表達砸脊。
編碼后數(shù)據(jù)還可以再次壓縮。
- 字典編碼（Dictionary Ecoding）：
適用于唯一值（Distinct Values）數(shù)量較少的情況纬霞，例如季度凌埂、國家
預提取預存字典的KV對，數(shù)據(jù)里存K诗芜。
壓縮后數(shù)據(jù)長度為log 2(|D|) bits瞳抓，D是唯一值數(shù)量
- 參照系編碼（FOR，F(xiàn)rame of Reference Encoding）：
選擇參照值伏恐，每個數(shù)據(jù)只存與參照值的差值孩哑，
壓縮后每值占log 2(max ? min + 1) bits
變種FOR： 選擇可以小于0的參照值，使的每個值都為正數(shù)翠桦。
- 差異編碼（Defferential Encoding／PFOR-DELTA）：
和參照系編碼類似横蜒，使用前一個值作為參照值
對于遞增遞減的數(shù)據(jù)性能良好。
例如時間戳秤掌、遞增ID愁铺、有序數(shù)組
- 行程編碼（Run-Length Encoding，RLE）：
將一串連續(xù)的相同數(shù)據(jù)轉化為特定的格式
例如：aaabbc闻鉴，表示為：3個a茵乱，2個b，1個c孟岛，壓縮數(shù)據(jù)3a2b1c
RLE是很基礎的壓縮方式瓶竭，通用壓縮算法中也很多它的影子，
但通用壓縮中經(jīng)常結合多種算法渠羞，例如使用BWT可逆變換提高重復率斤贰。
作為原始的、沒有經(jīng)過數(shù)據(jù)變形的RLE次询，更利于在壓縮數(shù)據(jù)上進行計算荧恍。
###### 這些算法都可以在同一個算法框架下工作：
- 找到數(shù)據(jù)特征，大部分數(shù)據(jù)都應該符合該特征
- 對數(shù)據(jù)逐個進行編碼，達成壓縮送巡，不同的壓縮算法采用不同的編碼方式
- 如果碰到不符合特征的數(shù)據(jù)摹菠，按異常值（Exception Values）處理
- 異常值的處理方式：編碼為“跳出碼（Escape Code）+ 原始數(shù)據(jù)”
- 跳出碼與正常值長度相等，其值為正常值不可能的值骗爆。所對應的原始數(shù)據(jù)可以另外存放
用偽碼來表示編碼過程：
```c
for i = j = 0; i < n; i++:
if in[i] < MAXCODE:
out[i] = CODE(in[i])
else:
out[i] = MAXCODE
exception[j++]) = out[i]```
解碼為逆過程：
```c
for i = j = 0; i < n; i++:
if in[i] < MAXCODE:
out[i] = DECODE(in[i])
else:
out[i] = exception[j++])```
有兩個事情值得注意：
1次氨，exception的數(shù)據(jù)比例對性能的影響。
2摘投，if-else分支引發(fā)的指令預測失敗煮寡，IPC（Instructions Per Cycle）下降的問題。
Marcin Zukowski在引文中測試了不同壓縮算法犀呼、不同exception比例下的性能幸撕，
并且嘗試使用兩輪循環(huán)避免if-else分支，有興趣可以看看圆凰。
在實踐中杈帐，不同的數(shù)據(jù)列可以根據(jù)特征和需求來決定壓縮策略，
工程師們提出過不少策略专钉，以下是其中一種決策樹：
該列有排序查詢的需求嗎
Y => 平均重復行程（Average Run-Length）> 2嗎
Y => RLE壓縮
N => 差異編碼
N => 唯一值（Distinct Values）數(shù)量 < 50000嗎
Y => 該列經(jīng)常出現(xiàn)在選擇謂詞（即SQL where子語句）中嗎
Y => 位向量編碼
N => 字典編碼
N => 是有局部性（某范圍值較多）的數(shù)字類型嗎
Y => 參照系編碼
N => 不壓縮或者重型壓縮
在實際開發(fā)中，列數(shù)據(jù)一般被分成多個等大Block累铅，
每個Block可以有自己的元數(shù)據(jù)（例如參照值）跃须，也可以引用別的Block的，
甚至可以再次對特征采樣娃兽，選擇不同的壓縮策略菇民。
可見落地過程中的優(yōu)化空間還是很大的，需要結合實際數(shù)據(jù)測量效率投储。
# 對于壓縮數(shù)據(jù)的計算
輕量壓縮的結果與原始數(shù)據(jù)成一一映射的關系第练，
幾乎所有的算術運算都可以直接在壓縮結果上計算。
舉例玛荞，原始數(shù)據(jù)[102, 101, 104]娇掏，使用FOR編碼，以100為參考值編碼為[2, 1, 4]勋眯，
那么(if > 101)的運算就被改寫為(if > 1)婴梧，可以直接在編碼后數(shù)據(jù)上計算。
即使我們不使用改寫計算的方法來處理數(shù)據(jù)客蹋，
而是使用解壓后計算的常規(guī)方式塞蹭，上述的輕量壓縮仍舊可以帶來巨大好處：
我們知道，RAM對比CPU來說是很慢的讶坯。
下表是數(shù)據(jù)在各個設備上存取數(shù)據(jù)的大概耗時比例番电，單位是時鐘周期Cycle：
L1-CACHE 4
L2-CACHE 11
L3-CACHE 18
RAM 160```
計算過程：
- 壓縮數(shù)據(jù)從RAM進入CACHE
- 送入CPU解壓
- 進行業(yè)務運算
- 再壓縮，結果留在CACHE
- 寫回RAM
可見最耗時的兩次IO：RAM-CACHE／CACHE-RAM辆琅，傳輸?shù)亩际菈嚎s數(shù)據(jù)漱办，
該技術被稱為RAM-CPU CACHE Compression这刷，
有效減少了RAM-CPU交換，增加了吞吐量洼冻。
以上涉及的都是列數(shù)據(jù)的通用的計算優(yōu)化崭歧，
對于其在關系代數(shù)運算（查詢）中的優(yōu)化，
也是一個較大的話題撞牢，需要另外的篇幅來敘述率碾。
主要參考資料
以下論文可以在各大學術庫下載
- “Query Execution in Column-Oriented Database Systems” Daniel Abadi SIGMOD’09
- “Super-Scalar RAM-CPU Cache Compression” Zukowski, Heman, Nes, Boncz, ICDE’06
- “Weaving relations for cache performance” Ailamaki, DeWitt, Hill, and Skounakis. VLDB’01
- “Integrating Compression and Execution in Column-Oriented Database Systems” Abadi, SIGMOD’06
- “MonetDB/X100: Hyper-Pipelining Query Execution” Peter Boncz, CIDR’05
