稀疏索引與其在Kafka和ClickHouse中的應(yīng)用

在以數(shù)據(jù)庫為代表的存儲系統(tǒng)中，索引（index）是一種附加于原始數(shù)據(jù)之上的數(shù)據(jù)結(jié)構(gòu)，能夠通過減少磁盤訪問來提升查詢速度，與現(xiàn)實中的書籍目錄異曲同工。索引通常包含兩部分，即索引鍵（≈章節(jié)）與指向原始數(shù)據(jù)的指針（≈頁碼），如下圖所示。

https://www.geeksforgeeks.org/indexing-in-databases-set-1/

索引的組織形式多種多樣，本文要介紹的稀疏索引（sparse index）是一種簡單而常用的有序索引形式——即在數(shù)據(jù)主鍵有序的基礎(chǔ)上，只為部分（通常是較少一部分）原始數(shù)據(jù)建立索引，從而在查詢時能夠圈定出大致的范圍，再在范圍內(nèi)利用適當(dāng)?shù)牟檎宜惴ㄕ业侥繕?biāo)數(shù)據(jù)。如下圖所示，為3條原始數(shù)據(jù)建立了稀疏索引。

https://www2.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter11/node5.html

相對地，如果為所有原始數(shù)據(jù)建立索引，就稱為稠密索引（dense index），如下圖。

稠密索引和稀疏索引其實就是空間和時間的trade-off。在數(shù)據(jù)量巨大時，為每條數(shù)據(jù)都建立索引也會耗費大量空間，所以稀疏索引在特定場景非常好用。以下舉兩個例子。

Sparse Index in Kafka

我們知道，單個Kafka的TopicPartition中，消息數(shù)據(jù)會被切分成段（segment）來存儲，擴(kuò)展名為.log。log文件的切分時機(jī)由大小參數(shù)log.segment.bytes（默認(rèn)值1G）和時間參數(shù)log.roll.hours（默認(rèn)值7天）共同決定。數(shù)據(jù)目錄中存儲的部分文件如下。

.
├── 00000000000190089251.index
├── 00000000000190089251.log
├── 00000000000190089251.timeindex
├── 00000000000191671269.index
├── 00000000000191671269.log
├── 00000000000191671269.timeindex
├── 00000000000193246592.index
├── 00000000000193246592.log
├── 00000000000193246592.timeindex
├── 00000000000194821538.index
├── 00000000000194821538.log
├── 00000000000194821538.timeindex
├── 00000000000196397456.index
├── 00000000000196397456.log
├── 00000000000196397456.timeindex
├── 00000000000197971543.index
├── 00000000000197971543.log
├── 00000000000197971543.timeindex
......

log文件的文件名都是64位整形，表示這個log文件內(nèi)存儲的第一條消息的offset值減去1（也就是上一個log文件最后一條消息的offset值）。每個log文件都會配備兩個索引文件——index和timeindex，分別對應(yīng)偏移量索引和時間戳索引，且均為稀疏索引。

可以通過Kafka提供的DumpLogSegments小工具來查看索引文件中的信息。

~ kafka-run-class kafka.tools.DumpLogSegments --files /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.index
Dumping /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.index
offset: 197971551 position: 5207
offset: 197971558 position: 9927
offset: 197971565 position: 14624
offset: 197971572 position: 19338
offset: 197971578 position: 23509
offset: 197971585 position: 28392
offset: 197971592 position: 33174
offset: 197971599 position: 38036
offset: 197971606 position: 42732
......

~ kafka-run-class kafka.tools.DumpLogSegments --files /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.timeindex
Dumping /data4/kafka/data/ods_analytics_access_log-3/00000000000197971543.timeindex
timestamp: 1593230317565 offset: 197971551
timestamp: 1593230317642 offset: 197971558
timestamp: 1593230317979 offset: 197971564
timestamp: 1593230318346 offset: 197971572
timestamp: 1593230318558 offset: 197971578
timestamp: 1593230318579 offset: 197971582
timestamp: 1593230318765 offset: 197971592
timestamp: 1593230319117 offset: 197971599
timestamp: 1593230319442 offset: 197971606
......

可見，index文件中存儲的是offset值與對應(yīng)數(shù)據(jù)在log文件中存儲位置的映射，而timeindex文件中存儲的是時間戳與對應(yīng)數(shù)據(jù)offset值的映射。有了它們，就可以快速地通過offset值或時間戳定位到消息的具體位置了。并且由于索引文件的size都不大，因此很容易將它們做內(nèi)存映射（mmap），存取效率很高。

以index文件為例，如果我們想要找到offset=197971577的消息，流程是：

• 通過二分查找，在index文件序列中，找到包含該offset的文件（00000000000197971543.index）；

• 通過二分查找，在上一步定位到的index文件中，找到該offset所在區(qū)間的起點（197971592）；

• 從上一步的起點開始順序查找，直到找到目標(biāo)offset。

最后，稀疏索引的粒度由log.index.interval.bytes參數(shù)來決定，默認(rèn)為4KB，即每隔log文件中4KB的數(shù)據(jù)量生成一條索引數(shù)據(jù)。調(diào)大這個參數(shù)會使得索引更加稀疏，反之則會更稠密。

Sparse Index in ClickHouse

在ClickHouse中，MergeTree引擎表的索引列在建表時使用ORDER BY語法來指定。而在官方文檔中，用了下面一幅圖來說明。

這張圖示出了以CounterID、Date兩列為索引列的情況，即先以CounterID為主要關(guān)鍵字排序，再以Date為次要關(guān)鍵字排序，最后用兩列的組合作為索引鍵。marks與mark numbers就是索引標(biāo)記，且marks之間的間隔就由建表時的索引粒度參數(shù)index_granularity來指定，默認(rèn)值為8192。

ClickHouse MergeTree引擎表中，每個part的數(shù)據(jù)大致以下面的結(jié)構(gòu)存儲。

.
├── business_area_id.bin
├── business_area_id.mrk2
├── coupon_money.bin
├── coupon_money.mrk2
├── groupon_id.bin
├── groupon_id.mrk2
├── is_new_order.bin
├── is_new_order.mrk2
......
├── primary.idx
......

其中，bin文件存儲的是每一列的原始數(shù)據(jù)（可能被壓縮存儲），mrk2文件存儲的是圖中的mark numbers與bin文件中數(shù)據(jù)位置的映射關(guān)系。另外，還有一個primary.idx文件存儲被索引列的具體數(shù)據(jù)。另外，每個part的數(shù)據(jù)都存儲在單獨的目錄中，目錄名形如20200708_92_121_7，即包含了分區(qū)鍵、起始mark number和結(jié)束mark number，方便定位。

這樣，每一列都通過ORDER BY列進(jìn)行了索引。查詢時，先查找到數(shù)據(jù)所在的parts，再通過mrk2文件確定bin文件中數(shù)據(jù)的范圍即可。

不過，ClickHouse的稀疏索引與Kafka的稀疏索引不同，可以由用戶自由組合多列，因此也要格外注意不要加入太多索引列，防止索引數(shù)據(jù)過于稀疏，增大存儲和查找成本。另外，基數(shù)太?。磪^(qū)分度太低）的列不適合做索引列，因為很可能橫跨多個mark的值仍然相同，沒有索引的意義了。