Sparse Index
在以數(shù)據(jù)庫為代表的存儲(chǔ)系統(tǒng)中惨恭，索引（index）是一種附加于原始數(shù)據(jù)之上的數(shù)據(jù)結(jié)構(gòu)，能夠通過減少磁盤訪問來提升查詢速度耙旦，與現(xiàn)實(shí)中的書籍目錄異曲同工脱羡。索引通常包含兩部分，即索引鍵（≈章節(jié)）與指向原始數(shù)據(jù)的指針（≈頁碼）免都，如下圖所示锉罐。
索引的組織形式多種多樣，本文要介紹的稀疏索引（sparse index）是一種簡(jiǎn)單而常用的有序索引形式——即在數(shù)據(jù)主鍵有序的基礎(chǔ)上绕娘，只為部分（通常是較少一部分）原始數(shù)據(jù)建立索引脓规，從而在查詢時(shí)能夠圈定出大致的范圍，再在范圍內(nèi)利用適當(dāng)?shù)牟檎宜惴ㄕ业侥繕?biāo)數(shù)據(jù)业舍。如下圖所示，為3條原始數(shù)據(jù)建立了稀疏索引升酣。
相對(duì)地舷暮，如果為所有原始數(shù)據(jù)建立索引，就稱為稠密索引（dense index）噩茄，如下圖下面。
稠密索引和稀疏索引其實(shí)就是空間和時(shí)間的trade-off。在數(shù)據(jù)量巨大時(shí)绩聘，為每條數(shù)據(jù)都建立索引也會(huì)耗費(fèi)大量空間沥割，所以稀疏索引在特定場(chǎng)景非常好用。以下舉兩個(gè)例子凿菩。
Sparse Index in Kafka
我們知道机杜，單個(gè)Kafka的TopicPartition中，消息數(shù)據(jù)會(huì)被切分成段（segment）來存儲(chǔ)衅谷，擴(kuò)展名為.log椒拗。log文件的切分時(shí)機(jī)由大小參數(shù)log.segment.bytes（默認(rèn)值1G）和時(shí)間參數(shù)log.roll.hours（默認(rèn)值7天）共同決定。數(shù)據(jù)目錄中存儲(chǔ)的部分文件如下。
.
├── 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位整形蚀苛，表示這個(gè)log文件內(nèi)存儲(chǔ)的第一條消息的offset值減去1（也就是上一個(gè)log文件最后一條消息的offset值）在验。每個(gè)log文件都會(huì)配備兩個(gè)索引文件——index和timeindex，分別對(duì)應(yīng)偏移量索引和時(shí)間戳索引堵未，且均為稀疏索引腋舌。
可以通過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文件中存儲(chǔ)的是offset值與對(duì)應(yīng)數(shù)據(jù)在log文件中存儲(chǔ)位置的映射块饺，而timeindex文件中存儲(chǔ)的是時(shí)間戳與對(duì)應(yīng)數(shù)據(jù)offset值的映射。有了它們拙徽，就可以快速地通過offset值或時(shí)間戳定位到消息的具體位置了刨沦。并且由于索引文件的size都不大，因此很容易將它們做內(nèi)存映射（mmap）膘怕，存取效率很高想诅。
以index文件為例，如果我們想要找到offset=197971577的消息岛心，流程是：
- 通過二分查找来破，在index文件序列中，找到包含該offset的文件（00000000000197971543.index）忘古；
- 通過二分查找徘禁，在上一步定位到的index文件中，找到該offset所在區(qū)間的起點(diǎn)（197971592）髓堪；
- 從上一步的起點(diǎn)開始順序查找送朱，直到找到目標(biāo)offset。
最后干旁，稀疏索引的粒度由log.index.interval.bytes參數(shù)來決定驶沼，默認(rèn)為4KB，即每隔log文件中4KB的數(shù)據(jù)量生成一條索引數(shù)據(jù)争群。調(diào)大這個(gè)參數(shù)會(huì)使得索引更加稀疏回怜，反之則會(huì)更稠密。
Sparse Index in ClickHouse
在ClickHouse中换薄，MergeTree引擎表的索引列在建表時(shí)使用ORDER BY語法來指定玉雾。而在官方文檔中，用了下面一幅圖來說明轻要。
這張圖示出了以CounterID复旬、Date兩列為索引列的情況，即先以CounterID為主要關(guān)鍵字排序冲泥，再以Date為次要關(guān)鍵字排序赢底，最后用兩列的組合作為索引鍵。marks與mark numbers就是索引標(biāo)記，且marks之間的間隔就由建表時(shí)的索引粒度參數(shù)index_granularity來指定幸冻，默認(rèn)值為8192粹庞。
ClickHouse MergeTree引擎表中，每個(gè)part的數(shù)據(jù)大致以下面的結(jié)構(gòu)存儲(chǔ)洽损。
.
├── 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文件存儲(chǔ)的是每一列的原始數(shù)據(jù)（壓縮存儲(chǔ)），mrk2文件存儲(chǔ)的是圖中的mark numbers與bin文件中數(shù)據(jù)位置的映射關(guān)系碑定。另外流码，還有一個(gè)primary.idx文件存儲(chǔ)被索引列的具體數(shù)據(jù)。每個(gè)part的數(shù)據(jù)都存儲(chǔ)在單獨(dú)的目錄中延刘，目錄名形如20200708_92_121_7漫试，即包含了分區(qū)鍵、起始mark number和結(jié)束mark number碘赖，方便定位驾荣。
在ClickHouse之父Alexey Milovidov分享的PPT中，有更加詳細(xì)的圖示普泡。
這樣播掷，每一列都通過ORDER BY列進(jìn)行了索引。查詢時(shí)撼班，先查找到數(shù)據(jù)所在的parts歧匈，再通過mrk2文件確定bin文件中數(shù)據(jù)的范圍即可。
不過砰嘁，ClickHouse的稀疏索引與Kafka的稀疏索引不同件炉，可以由用戶自由組合多列，因此也要格外注意不要加入太多索引列矮湘，防止索引數(shù)據(jù)過于稀疏斟冕，增大存儲(chǔ)和查找成本。另外板祝，基數(shù)太泄病（即區(qū)分度太低）的列不適合做索引列走净，因?yàn)楹芸赡軝M跨多個(gè)mark的值仍然相同券时，沒有索引的意義了。
The End
準(zhǔn)備凌晨上線伏伯，民那晚安橘洞。
