注：以下分析基于開源 v19.15.2.2-stable 版本進行
引言
ClickHouse是最近比較火的一款開源列式存儲分析型資料庫，它最核心的特點就是極緻存儲壓縮率和查詢性能，本人最近正在學習ClickHouse這款産品中。從我個人的視角來看存儲是決定一款資料庫核心競争力、适用場景的關鍵所在，是以接下來我會陸續推出一系列文章來分析ClickHouse中最重要的MergeTree存儲核心。本文主旨在于介紹MergeTree的存儲格式，并且徹底剖析MergeTree存儲的極緻檢索性能。
MergeTree存儲
MergeTree思想
提到MergeTree這個詞，可能大家都會聯想到LSM-Tree這個資料結構，我們常用它來解決随機寫磁盤的性能問題，MergeTree的核心思想和LSM-Tree相同。MergeTree存儲結構需要對使用者寫入的資料做排序然後進行有序存儲，資料有序存儲帶來兩大核心優勢：
• 列存檔案在按塊做壓縮時，排序鍵中的列值是連續或者重複的，使得列存塊的資料壓縮可以獲得極緻的壓縮比。
• 存儲有序性本身就是一種可以加速查詢的索引結構，根據排序鍵中列的等值條件或者range條件我們可以快速找到目标行所在的近似位置區間(下文會展開詳細介紹)，而且這種索引結構是不會産生額外存儲開銷的。
大家可以從ClickHouse的官方文檔上找到一系列的MergeTree表引擎，包括基礎的MergeTree，擁有資料去重能力的ReplacingMergeTree、CollapsingMergeTree、VersionedCollapsingMergeTree，擁有資料聚合能力的SummingMergeTree、AggregatingMergeTree等。但這些擁有“特殊能力”的MergeTree表引擎在存儲上和基礎的MergeTree其實沒有任何差異，它們都是在資料Merge的過程中加入了“額外的合并邏輯”，這部分會在後續介紹MergeTree異步Merge機制的文章中詳細展開介紹。
MergeTree存儲結構
為了友善大家了解表的存儲結構，下面列舉了某個POC使用者的測試表DDL，我們将從這個表入手來分析MergeTree存儲的核心設計。從DDL的PARTITION BY申明中我們可以看出使用者按每個區服每小時粒度建立了資料分區，而每個資料分區内部的資料又是按照(action_id, scene_id, time_ts, level, uid)作為排序鍵進行有序存儲。
CREATE TABLE user_action_log (
`time` DateTime DEFAULT CAST('1970-01-01 08:00:00', 'DateTime') COMMENT '日志時間',
`action_id` UInt16 DEFAULT CAST(0, 'UInt16') COMMENT '日志行為類型id',
`action_name` String DEFAULT '' COMMENT '日志行為類型名',
`region_name` String DEFAULT '' COMMENT '區服名稱',
`uid` UInt64 DEFAULT CAST(0, 'UInt64') COMMENT '使用者id',
`level` UInt32 DEFAULT CAST(0, 'UInt32') COMMENT '目前等級',
`trans_no` String DEFAULT '' COMMENT '事務流水号',
`ext_head` String DEFAULT '' COMMENT '擴充日志head',
`avatar_id` UInt32 DEFAULT CAST(0, 'UInt32') COMMENT '角色id',
`scene_id` UInt32 DEFAULT CAST(0, 'UInt32') COMMENT '場景id',
`time_ts` UInt64 DEFAULT CAST(0, 'UInt64') COMMENT '秒機關時間戳',
index avatar_id_minmax (avatar_id) type minmax granularity 3
) ENGINE = MergeTree()
PARTITION BY (toYYYYMMDD(time), toHour(time), region_name)
ORDER BY (action_id, scene_id, time_ts, level, uid)
PRIMARY KEY (action_id, scene_id, time_ts, level); 該表的MergeTree存儲結構邏輯示意圖如下：
MergeTree表的存儲結構中，每個資料分區互相獨立，邏輯上沒有關聯。單個資料分區内部存在着多個MergeTree Data Part。這些Data Part一旦生成就是Immutable的狀态，Data Part的生成和銷毀主要與寫入和異步Merge有關。MergeTree表的寫傳入連結路是一個極端的batch load過程，Data Part不支援單條的append insert。每次batch insert都會生成一個新的MergeTree Data Part。如果使用者單次insert一條記錄，那就會為那一條記錄生成一個獨立的Data Part，這必然是無法接受的。一般我們使用MergeTree表引擎的時候，需要在用戶端做聚合進行batch寫入或者在MergeTree表的基礎上建立Distributed表來代理MergeTree表的寫入和查詢，Distributed表預設會緩存使用者的寫入資料，超過一定時間或者資料量再異步轉發給MergeTree表。MergeTree存儲引擎對資料實時可見要求非常高的場景是不太友好的。
上圖展示了單個MergeTree Data Part裡最核心的一部分磁盤檔案(隻畫了action_id和avatar_id列其關的存儲檔案)，從功能上分主要有三個類：
1 資料檔案：action_id.bin、avatar_id.bin等都是單個列按塊壓縮後的列存檔案。ClickHouse采用了非常極端的列存模式，這裡展開一些細節，單個列資料可能會對應多個列存檔案，例如申明一個Nullable字段時會多一個nullable辨別的列存檔案，申明一個Array字段時會多一個array size的列存檔案, 采用字典壓縮時字典Key也會單獨變成一個列存檔案。有一點小Tips：當使用者不需要Null值特殊辨別時，最好不要去申明Nullable，這是ClickHouse的極簡化設計思路。
2 Mark辨別檔案：action_id.mrk2、avatar_id.mrk2等都是列存檔案中的Mark标記，Mark标記和MergeTree列存中的兩個重要概念相關：Granule和Block。
- Granule是資料按行劃分時用到的邏輯概念。關于多少行是一個Granule這個問題，在老版本中這是用參數index_granularity設定的一個常量，也就是每隔确定行就是一個Granule。在目前版本中有另一個參數index_granularity_bytes會影響Granule的行數，它的意義是讓每個Granule中所有列的sum size盡量不要超過設定值。老版本中的定長Granule設定主要的問題是MergeTree中的資料是按Granule粒度進行索引的，這種粗糙的索引粒度在分析超級大寬表的場景中，從存儲讀取的data size會膨脹得非常厲害，需要使用者非常謹慎得設定參數。
- Block是列存檔案中的壓縮單元。每個列存檔案的Block都會包含若幹個Granule，具體多少個Granule是由參數min_compress_block_size控制，每次列的Block中寫完一個Granule的資料時，它會檢查目前Block Size有沒有達到設定值，如果達到則會把目前Block進行壓縮然後寫磁盤。
- 從以上兩點可以看出MergeTree的Block既不是定data size也不是定行數的，Granule也不是一個定長的邏輯概念。是以我們需要額外資訊快速找到某一個Granule。這就是Mark辨別檔案的作用，它記錄了每個Granule的行數，以及它所在的Block在列存壓縮檔案中的偏移，同時還有Granule在解壓後的Block中的偏移位置。
3主鍵索引：primary.idx是表的主鍵索引。ClickHouse對主鍵索引的定義和傳統資料庫的定義稍有不同，它的主鍵索引沒用主鍵去重的含義，但仍然有快速查找主鍵行的能力。ClickHouse的主鍵索引存儲的是每一個Granule中起始行的主鍵值，而MergeTree存儲中的資料是按照主鍵嚴格排序的。是以當查詢給定主鍵條件時，我們可以根據主鍵索引确定資料可能存在的Granule Range，再結合上面介紹的Mark辨別，我們可以進一步确定資料在列存檔案中的位置區間。ClickHoue的主鍵索引是一種在索引建構成本和索引效率上相對平衡的粗糙索引。MergeTree的主鍵序列預設是和Order By序列儲存一緻的，但是使用者可以把主鍵序列定義成Order By序列的部分字首。
4分區鍵索引：minmax_time.idx、minmax_region_name.idx是表的分區鍵索引。MergeTree存儲會把統計每個Data Part中分區鍵的最大值和最小值，當使用者查詢中包含分區鍵條件時，就可以直接排除掉不相關的Data Part，這是一種OLAP場景下常用的分區裁剪技術。
5Skipping索引：skp_idx_avatar_id_minmax.idx是使用者在avatar_id列上定義的MinMax索引。Merge Tree中 的Skipping Index是一類局部聚合的粗糙索引。使用者在定義skipping index的時候需要設定granularity參數，這裡的granularity參數指定的是在多少個Granule的資料上做聚合生成索引資訊。使用者還需要設定索引對應的聚合函數，常用的有minmax、set、bloom_filter、ngrambf_v1等，聚合函數會統計連續若幹個Granule中的列值生成索引資訊。Skipping索引的思想和主鍵索引是類似的，因為資料是按主鍵排序的，主鍵索引統計的其實就是每個Granule粒度的主鍵序列MinMax值，而Skipping索引提供的聚合函數種類更加豐富，是主鍵索引的一種補充能力。另外這兩種索引都是需要使用者在了解索引原理的基礎上貼合自己的業務場景來進行設計的。
MergeTree查詢
這一章主要會結合ClickHouse的源碼為大家分析MergeTree表引擎上的資料查詢過程，我大緻把這個過程分為兩塊：索引檢索和資料掃描。索引檢索部分對每個MergeTree Data Part是串行執行，但Data Part之間的檢索沒有任何關聯。而在資料掃描部分中最底層的列存掃描是多所有Data Part并行執行，各Data Part的列存掃描之間也沒有任何關聯。
索引檢索
MergeTree存儲在收到一個select查詢時會先抽取出查詢中的分區鍵和主鍵條件的KeyCondition，KeyCondition類上實作了以下三個方法，用于判斷過濾條件可能滿足的Mark Range。上一章講過MergeTree Data Part中的列存資料是以Granule為粒度被Mark辨別數組索引起來的，而Mark Range就表示Mark辨別數組裡滿足查詢條件的下标區間。
/// Whether the condition is feasible in the key range.
/// left_key and right_key must contain all fields in the sort_descr in the appropriate order.
/// data_types - the types of the key columns.
bool mayBeTrueInRange(size_t used_key_size, const Field * left_key, const Field * right_key, const DataTypes & data_types) const;
/// Whether the condition is feasible in the direct product of single column ranges specified by `parallelogram`.
bool mayBeTrueInParallelogram(const std::vector<Range> & parallelogram, const DataTypes & data_types) const;
/// Is the condition valid in a semi-infinite (not limited to the right) key range.
/// left_key must contain all the fields in the sort_descr in the appropriate order.
bool mayBeTrueAfter(size_t used_key_size, const Field * left_key, const DataTypes & data_types) const; 索引檢索的過程中首先會用分區鍵KeyCondition裁剪掉不相關的資料分區，然後用主鍵索引挑選出粗糙的Mark Range，最後再用Skipping Index過濾主鍵索引産生的Mark Range。用主鍵索引挑選出粗糙的Mark Range的算法是一個不斷分裂Mark Range的過程，傳回結果是一個Mark Range的集合。起始的Mark Range是覆寫整個MergeTree Data Part區間的，每次分裂都會把上次分裂後的Mark Range取出來按一定粒度步長分裂成更細粒度的Mark Range，然後排除掉分裂結果中一定不滿足條件的Mark Range，最後Mark Range到一定粒度時停止分裂。這是一個簡單高效的粗糙過濾算法。
使用Skipping Index過濾主鍵索引傳回的Mark Range之前，需要構造出每個Skipping Index的IndexCondition，不同的Skipping Index聚合函數有不同的IndexCondition實作，但判斷Mark Range是否滿足條件的接口和KeyCondition是類似的。
資料Sampling
經過上一小節的索引過濾之後，我們已經得到了需要掃描的Mark Range集合，接下來就應該是資料掃描部分了。這一小節插入簡單講一下MergeTree裡的資料Sampling是如何實作的。它并不是在資料掃描過程中實作的，而是在索引檢索的過程中就已經完成，這種做法是為了極緻的sample效率。使用者在建表的時候可以指定主鍵中的某個列或者表達式作為Sampling鍵，ClickHouse在這裡用了簡單粗暴的做法：Sampling鍵的值必須是數值類型的，并且系統假定它的值是随機均勻分布的一個狀态。如果Sampling鍵的值類型是Uint32，當我們設定sample比率是0.1的時候，索引檢索過程中會把sample轉換成一個filter條件：Sampling鍵的值 < Uint32::max * 0.1。使用者在使用Sampling功能時必須清楚這個細節，不然容易出現采樣偏差。一般我們推薦Sampling鍵是列值加一個Hash函數進行随機打散。
資料掃描
MergeTree的資料掃描部分提供了三種不同的模式：
- Final模式：該模式對CollapsingMergeTree、SummingMergeTree等表引擎提供一個最終Merge後的資料視圖。前文已經提到過MergeTree基礎上的進階MergeTree表引擎都是對MergeTree Data Part采用了特定的Merge邏輯。它帶來的問題是由于MergeTree Data Part是異步Merge的過程，在沒有最終Merge成一個Data Part的情況下，使用者無法看到最終的資料結果。是以ClickHouse在查詢是提供了一個final模式，它會在各個Data Part的多條BlockInputStream基礎上套上一些進階的Merge Stream，例如DistinctSortedBlockInputStream、SummingSortedBlockInputStream等，這部分邏輯和異步Merge時的邏輯保持一緻，這樣使用者就可以提前看到“最終”的資料結果了。
- Sorted模式：sort模式可以認為是一種order by下推存儲的查詢加速優化手段。因為每個MergeTree Data Part内部的資料是有序的，是以當使用者查詢中包括排序鍵order by條件時隻需要在各個Data Part的BlockInputStream上套一個做資料有序歸并的InputStream就可以實作全局有序的能力。
- Normal模式：這是基礎MergeTree表最常用的資料掃描模式，多個Data Part之間進行并行資料掃描，對于單查詢可以達到非常高吞吐的資料讀取。
接下來展開介紹下Normal模式中幾個關鍵的性能優化點：
- 并行掃描：傳統的計算引擎在資料掃描部分的并發度大多和存儲檔案數綁定在一起，是以MergeTree Data Part并行掃描是一個基礎能力。但是MergeTree的存儲結構要求資料不斷mege，最終合并成一個Data Part，這樣對索引和資料壓縮才是最高效的。是以ClickHouse在MergeTree Data Part并行的基礎上還增加了Mark Range并行。使用者可以任意設定資料掃描過程中的并行度，每個掃描線程配置設定到的是Mark Range In Data Part粒度的任務，同時多個掃描線程之間還共享了Mark Range Task Pool，這樣可以避免在存儲掃描中的長尾問題。
- 資料Cache：MergeTree的查詢鍊路中涉及到的資料有不同級别的緩存設計。主鍵索引和分區鍵索引在load Data Part的過程中被加載到記憶體，Mark檔案和列存檔案有對應的MarkCache和UncompressedCache，MarkCache直接緩存了Mark檔案中的binary内容，而UncompressedCache中緩存的是解壓後的Block資料。
- SIMD反序列化：部分列類型的反序列化過程中采用了手寫的sse指令加速，在資料命中UncompressedCache的情況下會有一些效果。
- PreWhere過濾：ClickHouse的文法支援了額外的PreWhere過濾條件，它會先于Where條件進行判斷。當使用者在sql的filter條件中加上PreWhere過濾條件時，存儲掃描會分兩階段進行，先讀取PreWhere條件中依賴的列值，然後計算每一行是否符合條件。相當于在Mark Range的基礎上進一步縮小掃描範圍，PreWhere列掃描計算過後，ClickHouse會調整每個Mark對應的Granule中具體要掃描的行數，相當于可以丢棄Granule頭尾的一部分行。
結語
随着閱讀ClickHouse源碼深入了解它的核心實作，我認為ClickHouse目前還不是一個特别完美的分析型資料庫。但它仍然有許多極緻的性能優化設計，這些設計都是源于Yandex公司真實的分析場景，并且确實可以解決海量資料下的一些業務問題。我相信在一部分适合ClickHouse的業務場景中，它就是可以給使用者帶來最極緻性能體驗的資料庫。
Clickhouse産品連結:
https://www.aliyun.com/product/clickhouse 後續會陸續推出更多的分析文章，有興趣的同學可以多多交流和follow，先為後面的文章取個名字：
MergeTree的Merge和Mutation機制
MergeTree寫傳入連結路全解析
MergeTree的Table管理設計：Alter、TTL和分層存儲