前言

其實這篇文章只是從Kafka索引入手，來講述算法在工程上基于場景的靈活運用。單單是因為看源碼的時候有感而寫之。

索引的重要性

索引對于我們來說并不陌生，每一本書籍的目錄就是索引在現(xiàn)實生活中的應(yīng)用。通過寥寥幾頁紙就得以讓我等快速查找需要的內(nèi)容。冗余了幾頁紙，縮短了查閱的時間。空間和時間上的互換，包含著宇宙的哲學(xué)。

工程領(lǐng)域上數(shù)據(jù)庫的索引更是不可或缺，沒有索引很難想象如此龐大的數(shù)據(jù)該如何檢索。

明確了索引的重要性，咱再來看看索引在Kafka里是如何實現(xiàn)的。

索引在Kafka中的實踐

首先Kafka的索引是稀疏索引，這樣可以避免索引文件占用過多的內(nèi)存，從而可以在內(nèi)存中保存更多的索引。對應(yīng)的就是Broker 端參數(shù)log.index.interval.bytes 值，默認(rèn)4KB，即4KB的消息建一條索引。

Kafka中有三大類索引：位移索引、時間戳索引和已中止事務(wù)索引。分別對應(yīng)了.index、.timeindex、.txnindex文件。

與之相關(guān)的源碼如下：

1、AbstractIndex.scala：抽象類，封裝了所有索引的公共操作

2、OffsetIndex.scala：位移索引，保存了位移值和對應(yīng)磁盤物理位置的關(guān)系

3、TimeIndex.scala：時間戳索引，保存了時間戳和對應(yīng)位移值的關(guān)系

4、TransactionIndex.scala：事務(wù)索引，啟用Kafka事務(wù)之后才會出現(xiàn)這個索引（本文暫不涉及事務(wù)相關(guān)內(nèi)容）

索引類圖

先來看看AbstractIndex的定義

image

AbstractIndex的定義在代碼里已經(jīng)注釋了，成員變量里面還有個entrySize。這個變量其實是每個索引項的大小，每個索引項的大小是固定的。

entrySize

在OffsetIndex中是override def entrySize = 8，8個字節(jié)。
在TimeIndex中是override def entrySize = 12,12個字節(jié)。

為何是8 和12？

在OffsetIndex中，每個索引項存儲了位移值和對應(yīng)的磁盤物理位置，因此4+4=8，但是不對啊，磁盤物理位置是整型沒問題，但是AbstractIndex的定義baseOffset來看，位移值是長整型，不是因為8個字節(jié)么？

因此存儲的位移值實際上是相對位移值，即真實位移值-baseOffset的值。

相對位移用整型存儲夠么？夠，因為一個日志段文件大小的參數(shù)log.segment.bytes是整型，因此同一個日志段對應(yīng)的index文件上的位移值-baseOffset的值的差值肯定在整型的范圍內(nèi)。

為什么要這么麻煩，還要存?zhèn)€差值？

1、為了節(jié)省空間，一個索引項節(jié)省了4字節(jié)，想想那些日消息處理數(shù)萬億的公司。

2、因為內(nèi)存資源是很寶貴的，索引項越短，內(nèi)存中能存儲的索引項就越多，索引項多了直接命中的概率就高了。這其實和MySQL InnoDB 為何建議主鍵不宜過長一樣。每個輔助索引都會存儲主鍵的值，主鍵越長，每條索引項占用的內(nèi)存就越大，緩存頁一次從磁盤獲取的索引數(shù)就越少，一次查詢需要訪問磁盤次數(shù)就可能變多。而磁盤訪問我們都知道，很慢。

互相轉(zhuǎn)化的源碼如下，就這么個簡單的操作：

image

上述解釋了位移值是4字節(jié)，因此TimeIndex中時間戳8個字節(jié) + 位移值4字節(jié) = 12字節(jié)。

_warmEntries

這個是干什么用的？

首先思考下我們能通過索引項快速找到日志段中的消息，但是我們?nèi)绾慰焖僬业轿覀兿胍乃饕椖?？一個索引文件默認(rèn)10MB，一個索引項8Byte，因此一個文件可能包含100多W條索引項。

不論是消息還是索引，其實都是單調(diào)遞增，并且都是追加寫入的，因此數(shù)據(jù)都是有序的。在有序的集合中快速查詢，腦海中突現(xiàn)的就是二分查找了！

那就來個二分！

二分查找

這和_warmEntries有什么關(guān)系？首先想想二分有什么問題？

就Kafka而言，索引是在文件末尾追加的寫入的，并且一般寫入的數(shù)據(jù)立馬就會被讀取。所以數(shù)據(jù)的熱點集中在尾部。并且操作系統(tǒng)基本上都是用頁為單位緩存和管理內(nèi)存的，內(nèi)存又是有限的，因此會通過類LRU機(jī)制淘汰內(nèi)存。

看起來LRU非常適合Kafka的場景，但是使用標(biāo)準(zhǔn)的二分查找會有缺頁中斷的情況，畢竟二分是跳著訪問的。

這里要說一下kafka的注釋寫的是真的清晰，咱們來看看注釋怎么說的

when looking up index, the standard binary search algorithm is not cache friendly, and can cause unnecessary
page faults (the thread is blocked to wait for reading some index entries from hard disk, as those entries are not
cached in the page cache)

翻譯下：當(dāng)我們查找索引的時候，標(biāo)準(zhǔn)的二分查找對緩存不友好，可能會造成不必要的缺頁中斷(線程被阻塞等待從磁盤加載沒有被緩存到page cache 的數(shù)據(jù))

注釋還友好的給出了例子

image

簡單的來講，假設(shè)某索引占page cache 13頁，此時數(shù)據(jù)已經(jīng)寫到了12頁。按照kafka訪問的特性，此時訪問的數(shù)據(jù)都在第12頁，因此二分查找的特性，此時緩存頁的訪問順序依次是0，6，9，11，12。因為頻繁被訪問，所以這幾頁一定存在page cache中。

當(dāng)?shù)?2頁不斷被填充，滿了之后會申請新頁第13頁保存索引項，而按照二分查找的特性，此時緩存頁的訪問順序依次是：0，7，10，12。這7和10很久沒被訪問到了，很可能已經(jīng)不再緩存中了，然后需要從磁盤上讀取數(shù)據(jù)。注釋說：在他們的測試中，這會導(dǎo)致至少會產(chǎn)生從幾毫秒跳到1秒的延遲。

基于以上問題，Kafka使用了改進(jìn)版的二分查找，改的不是二分查找的內(nèi)部，而且把所有索引項分為熱區(qū)和冷區(qū)

這個改進(jìn)可以讓查詢熱數(shù)據(jù)部分時，遍歷的Page永遠(yuǎn)是固定的，這樣能避免缺頁中斷。

看到這里其實我想到了一致性hash，一致性hash相對于普通的hash不就是在node新增的時候緩存的訪問固定，或者只需要遷移少部分?jǐn)?shù)據(jù)。

好了，讓我們先看看源碼是如何做的

image

實現(xiàn)并不難，但是為何是把尾部的8192作為熱區(qū)？

這里就要再提一下源碼了，講的很詳細(xì)。

1. This number is small enough to guarantee all the pages of the "warm" section is touched in every warm-section lookup. So that, the entire warm section is really "warm".
   When doing warm-section lookup, following 3 entries are always touched: indexEntry(end), indexEntry(end-N), and indexEntry((end*2 -N)/2). If page size >= 4096, all the warm-section pages (3 or fewer) are touched, when we
   touch those 3 entries. As of 2018, 4096 is the smallest page size for all the processors (x86-32, x86-64, MIPS, SPARC, Power, ARM etc.).

 大致內(nèi)容就是現(xiàn)在處理器一般緩存頁大小是4096，那么8192可以保證頁數(shù)小于等3，用于二分查找的頁面都能命中

2. This number is large enough to guarantee most of the in-sync lookups are in the warm-section. With default Kafka settings, 8KB index corresponds to about 4MB (offset index) or 2.7MB (time index) log messages.

 8KB的索引可以覆蓋 4MB (offset index) or 2.7MB (time index)的消息數(shù)據(jù)，足夠讓大部分在in-sync內(nèi)的節(jié)點在熱區(qū)查詢

以上就解釋了什么是_warmEntries，并且為什么需要_warmEntries。

可以看到樸素的算法在真正工程上的應(yīng)用還是需要看具體的業(yè)務(wù)場景的，不可生搬硬套。并且徹底的理解算法也是很重要的，例如死記硬背二分，怕是看不出來以上的問題。還有底層知識的重要性。不然也是看不出來對緩存不友好的。

從Kafka的索引冷熱分區(qū)到MySQL InnoDB的緩沖池管理

從上面這波冷熱分區(qū)我又想到了MySQL的buffer pool管理。MySQL的將緩沖池分為了新生代和老年代。默認(rèn)是37分，即老年代占3，新生代占7。即看作一個鏈表的尾部30%為老年代，前面的70%為新生代。替換了標(biāo)準(zhǔn)的LRU淘汰機(jī)制。

image

MySQL的緩沖池分區(qū)是為了解決預(yù)讀失效和緩存污染問題。

1、預(yù)讀失效：因為會預(yù)讀頁，假設(shè)預(yù)讀的頁不會用到，那么就白白預(yù)讀了，因此讓預(yù)讀的頁插入的是老年代頭部，淘汰也是從老年代尾部淘汰。不會影響新生代數(shù)據(jù)。

2、緩存污染：在類似like全表掃描的時候，會讀取很多冷數(shù)據(jù)。并且有些查詢頻率其實很少，因此讓這些數(shù)據(jù)僅僅存在老年代，然后快速淘汰才是正確的選擇，MySQL為了解決這種問題，僅僅分代是不夠的，還設(shè)置了一個時間窗口，默認(rèn)是1s，即在老年代被再次訪問并且存在超過1s，才會晉升到新生代，這樣就不會污染新生代的熱數(shù)據(jù)。

小結(jié)

文章先從索引入手，這就是時間和空間的互換。然后引出Kafka中索引存儲使用了相對位移值，節(jié)省了空間，并且講述了索引項的訪問是由二分查找實現(xiàn)的，并結(jié)合Kafka的使用場景解釋了Kafka中使用的冷熱分區(qū)實現(xiàn)改進(jìn)版的二分查找，并順帶提到了下一致性Hash，再由冷熱分區(qū)聯(lián)想到了MySQL緩沖池變形的LRU管理。

這一步步實際上都體現(xiàn)算法在工程中的靈活運用和變形實現(xiàn)。有些同學(xué)認(rèn)為算法沒用，刷算法題只是為了面試，實際上各種中間件和一些底層實現(xiàn)都體現(xiàn)了算法的重要性。

不說了，頭有點冷。