1. 前言
ClickHouse 是一個列式存儲資料庫管理系統(DBMS)，在分析型資料庫領域已經嶄露頭角，其在OLAP分析場景下提供的極緻性能被各大小産看中，并被廣泛使用。ClickHouse是一個極速的分布式ROLAP（Relational OLAP）分析引擎。采用C++編寫，自成一套體系，對第三方工具依賴少。支援較完整的DDL和DML，大部分操作可以通過指令行結合SQL就可以完成；分布式叢集依賴Zookeper管理，單節點不用依賴Zookeper，大部配置設定置需要通過修改配置檔案完成。ClickHouse各節點職責對等，各自負責一部分資料的處理（shared nothing），開發了向量化執行引擎，利用日志合并樹、稀疏索引與CPU的SIMD（單指令多資料，Single Instruction Multiple Data）等特性，充分發揮硬體優勢，達到高效計算的目的。是以當ClickHouse面對大資料量計算的場景，通常能達到CPU性能的極限。今天我們就先來深入探索下ClickHouse MergeTree的存儲和索引原理，看其是如何支撐快速OLAP分析。
2. MergeTree 引擎
首先我們先看下資料在Clickhouse内部是如何存儲的，說到存儲就涉及到存儲引擎的說法（類似MYSQL資料庫系統也有Innodb和myisam等存儲引擎），不同的存儲引擎提供了在不同需求場景下的資料存儲和索引的能力。而ClickHouse中也有衆多的不同特性的表引擎可以應對不同的需要，其中 MergeTree 引擎作為 ClickHouse 的核心，憑借其強大的性能與豐富的特性得到了廣泛的使用，并成為其他特性引擎的基礎。後續将基于 MergeTree 引擎進行讨論。
2.1 MergeTree引擎下表檔案結構說明
在 ClickHouse 中，每個表都對應檔案系統中的一個目錄，目錄中不同的檔案儲存了表資料與相關的屬性資訊，例如我們基于MergeTree 引擎建立如下的表，并寫入一些資料：
CREATE TABLE id_test
( `ID` Int64,
`StringID` FixedString(24)
)
ENGINE = MergeTree
ORDER BY (StringID, ID)
SETTINGS min_rows_for_wide_part = 0, min_bytes_for_wide_part = 0；
insert into id_test values(1,'1')(2,'2')--- 在Clickhouse的資料目錄下（在我本機上/var/lib/clickhouse/data/ods/id_test/all_1_1_0）可以看到如下的檔案生成
檔案說明：
- id_test：每個表在檔案系統都對應于一個目錄，以表名命名。
- all_1_1_0：如果對表進行了分區，那麼每個分區的都會有相應的目錄，本例沒有進行分區，是以隻有一個目錄。
- checksums.txt：校驗檔案，二進制存儲了各檔案的大小、哈希等，用于快速校驗存儲的正确性。
- columns.txt：列名以及資料類型
- count.txt：記錄資料的總行數，本例中檔案内容為 2 （隻寫入了兩行資料）。
- primary.idx：主鍵索引檔案，用于存放稀疏索引的資料。通過查詢條件與稀疏索引能夠快速的過濾無用的資料，減少需要加載的資料量。
- {column}.bin：列資料的存儲檔案，以列名+bin為檔案名，預設設定采用 lz4 壓縮格式。每一列都會有單獨的檔案（新版本需要指定 SETTINGS min_rows_for_wide_part = 0, min_bytes_for_wide_part = 0 參數來強制跳過 Compact format）。
- {column}.mrk2：列資料的标記資訊，記錄了資料塊在 bin 檔案中的偏移量。标記檔案首先與列資料的存儲檔案對齊，記錄了某個壓縮塊在 bin 檔案中的相對位置；其次與索引檔案對齊，記錄了稀疏索引對應資料在列存儲檔案中的位置。clickhouse 将首先通過索引檔案定位到标記資訊，再根據标記資訊直接從.bin 資料檔案中讀取資料。
3 索引
3.1 索引概念解釋
這裡講的索引是主鍵索引（也有人把主鍵索引叫做一級索引）。ClickHouse官方開源版沒有所謂一級二級索引的概念，隻有主鍵索引和跳數索引的概念，也沒有二級索引的功能設計，二級索引是某些雲廠商在ClickHouse基礎上做的索引增強（應該是社群版），和官方開源版的索引并不是一個原理，解決的也不是同一類問題。可以看下這裡的文檔 ClickHouse二級索引 - 雲資料庫 ClickHouse - 阿裡雲 （https://help.aliyun.com/document_detail/209170.html）
3.2 主鍵索引原理
ClickHouse 通過将資料排序并建立稀疏索引的方式來加速資料的定位與查詢；ClickHouse 的稀疏索引就像是目錄隻記錄開始位置，一條索引記錄就能标記大量的資料，而且資料量越大這種優勢就會越明顯。例如，MergeTree 預設的索引粒度(index_granularity)為 8192，标記 1 億條資料隻需要 12208 條索引。索引少占用的空間就小，是以對 ClickHouse 而言，primary.idx 中的資料是可以常駐記憶體。
如下圖左邊的稀疏索引記錄了右邊每一份資料的第一天的記錄的位置（右邊每一份資料由8192條資料組成）
3.3 主鍵索引存儲
為了後續更好講解索引過程以及索引檔案的存儲方式，我們修改最初的建表語句如下：
将最後一行的索引粒度設定為3，并插入下面的資料
CREATE TABLE IF NOT EXISTS id_test3
(
`ID` Int64,
`StringID` FixedString(24),
`Score` Int32
)
ENGINE = MergeTree
ORDER BY (StringID, ID)
PRIMARY KEY (StringID)
SETTINGS index_granularity = 3, min_rows_for_wide_part = 0, min_bytes_for_wide_part = 0; insert into id_test values
(1,'607589cdcbc95900017ddf01',1)
(2,'607589cdcbc95900017ddf02',2)
(3,'607589cdcbc95900017ddf03',3)
(4,'607589cdcbc95900017ddf04',4)
(5,'607589cdcbc95900017ddf05',5)
(6,'607589cdcbc95900017ddf06',6)
(7,'607589cdcbc95900017ddf07',7)
(8,'607589cdcbc95900017ddf08',8)
(9,'607589cdcbc95900017ddf09',9) 我們使用 StringID 作為主鍵，為了記錄首尾資訊會固定建立兩條索引，同時根據上述的索引粒度配置，每 3 行會生成一條索引記錄（索引結構見後面一節）：
607589cdcbc95900017ddf01（第一行）
...
607589cdcbc95900017ddf04（第四行）
...
607589cdcbc95900017ddf07（第七行）
...
607589cdcbc95900017ddf09（最後一行 - 第九行） 通過 primary.idx 檔案内容分析，也能得到相同的結論，檔案内容如下：
由于主鍵 StringID 是變長字元串，需要一位元組來儲存字元串的長度，測試資料中 StringID 的長度都是 24（0x18），是以第一位是 0x18，然後是相應的值：607589cdcbc95900017ddf01（紅色兩段16進制加起來轉換），随後緊接着第二個索引：長度+值。稀疏索引的存儲非常緊密不浪費一點空間，ClickHouse 中很多的資料結構都是這種思路，這種極度優化的思路這也是 ClickHouse 高效的原因之一。
3.4 Mark檔案結構與資料存儲
ClickHouse 中列資料的存儲分為兩個檔案：{column}.bin、{column}.mrk2。
- primary.idx檔案：ClickHouse 會根據 index_granularity 的設定将資料分成多個 granule，每個 granule 中索引列的第一個記錄将作為索引寫入到 primary.idx；
- {column}.mrk2檔案：其他非索引列也會用相同的政策生成一條 mark 資料寫入相應的*.mrk2 檔案中，并與主鍵索引一一對應，用于快速定位資料。
- {column}.bin檔案： 檔案内容是壓縮存放的，為了保證讀寫的效率，壓縮的粒度有兩個參數控制：max_compress_block_size（預設 1MB）和 min_compress_block_size（預設 64k），簡單的算法描述如下：
假設每次寫入的資料大小為 x：
- 如果 x<64KB，會等待下一批資料，直到累計的總量>64 的時候，生成一個壓縮塊。
- 如果 64KB
- 如果 x>1MB，則按照 1MB 進行分割，成為多個壓縮塊。
這就導緻一個 granule 的資料也可能存放在多個壓縮塊中，同時一塊壓縮可能存有多個 granule 的資料（如下圖）。
這就需要 mark 記錄既要儲存某個 granlue 與壓縮塊的對應關系，還儲存其在壓縮塊中的相對位置。
3.5 idx和mrk2的使用和資料加載過程
下圖簡單的展示了 primary.idx，*.mrk2，*.bin 之間的對應關系，其中 *.bin 檔案中壓縮快 Block0，Block1 的劃分僅僅隻是為描述概念，實際情況可能不是這樣。（根據上一節描述，可以再對比下圖看下實際的存儲關系，StringID的mark檔案記錄了primary.idx和資料塊的對應關系，Block0.info還記錄了primary.idx在每個塊中的偏移位置）
在 ClickHouse 的查詢過程中，理想的情況下可以通過查詢條件，利用預設的分區資訊，以及主鍵索引和跳數索引，将需要加載的資料 mark 縮至最少，盡可能減少資料掃描的範圍；通過 SQL 分析得到必須的資料列，根據 mark 範圍，将必須的資料加載進記憶體，進行後續的處理。例如我們有如下的 SQL：
select StringID,avg(Score) from id_test
where StringID between '607589cdcbc95900017ddf03' and '607589cdcbc95900017ddf06'
group by StringID; 簡化的 ClickHouse 資料加載過程如下：
- 根據條件 StringID 與一級（主鍵）索引，确定 mark 範圍：
mark0 [607589cdcbc95900017ddf01, 607589cdcbc95900017ddf04)
mark1 [607589cdcbc95900017ddf04, 607589cdcbc95900017ddf07) - 通過 sql 定位到需要加載 StringID 列和 Score 列的資料
- 根據步驟 1 得到的 mark 範圍，需要從 StringID.bin 與 Score.bin 中加載 mark0 和 mark1 的資料。
- 通過分析 Score.mrk2 和 StringID.mrk2 的内容，得到 mark0 和 mark1 對應的壓縮 block 在 *.bin 檔案中的偏移資訊。
- 将 Score.bin 以及 StringID.bin 中相應壓縮 block 的資料讀取出來并解壓；根據 sql 的條件進行精确的過濾。
- 對資料進行後續處理，本例需要根據 StringID 進行聚合并計算 Score 的平均值，這一步基本上全部在記憶體中完成。
4 索引分析和總結
Clickhouse的這種稀疏索引的方式引帶來的好處也是顯而易見的，那就是可以大幅減少索引占用的空間，索引可以常駐記憶體，同時基于索引的資料擷取按索引粒度8192擷取，一次可以擷取大批量資料，如果查詢需求帶來的資料局部性表現比較強（就是8192行資料裡面大多數就是我想要的資料），那這種索引方式講帶來極佳的性能表現。
當然如果局部性不好也會有性能問題，我們引用官方的例子來分析下這種索引方式的性能問題
這裡使用(CounterID,Date)兩個字段作為索引，當需要查詢 CounterID in ('a', 'h')時，伺服器會定位到 mark [0,3) 和 mark [6,8)；當需要查詢 CounterID in ('a', 'h') and Date = 3 時，伺服器會定位到 mark [1,3) 和 mark [7,8)；當需要查詢 Date=3 的時候，伺服器會定位到 mark [1,10]。
稀疏索引無法精确的找到資料，隻能定位到大概範圍，但作為一個旨在處理海量資料的系統而言，這些性能浪費是可以忽略的。
上述分析可知，索引的性能會受到索引字段資料分布的影響，設計表的時候需要充分考慮業務資料的實際情況，避免使用區分度很低的字段做索引。同時索引粒度（index_granularity）也是一個重要的屬性，ClickHouse 預設 8192，這個值在大多數的情況下都能提供良好的性能。
這種索引方式對點查是及其不友好的，是以某些雲廠商也會在開源Clickhouse基礎上增強二級索引能力來應對這種問題 ClickHouse二級索引 - 雲資料庫 ClickHouse - 阿裡雲（https://help.aliyun.com/document_detail/209170.html）
後面再找時間分享在ClickHouse這種索引機制下的查詢加速技術，以及社群版的二級索引原理。