关于前端:Kafka索引设计

前言

其实这篇文章只是从 Kafka 索引动手，来讲述算法在工程上基于场景的灵活运用。单单是因为看源码的时候有感而写之。

索引的重要性

索引对于咱们来说并不生疏，每一本书籍的目录就是索引在现实生活中的利用。通过寥寥几页纸就得以让我等疾速查找须要的内容。冗余了几页纸，缩短了查阅的工夫。空间和工夫上的调换，蕴含着宇宙的哲学。

工程畛域上数据库的索引更是不可或缺，没有索引很难设想如此宏大的数据该如何检索。

明确了索引的重要性，咱再来看看索引在 Kafka 里是如何实现的。

索引在 Kafka 中的实际

首先 Kafka 的索引是 稠密索引 ，这样能够防止索引文件占用过多的内存，从而能够 在内存中保留更多的索引。对应的就是 Broker 端参数log.index.interval.bytes 值，默认 4KB，即 4KB 的音讯建一条索引。

Kafka 中有三大类索引：位移索引、工夫戳索引和已停止事务索引。别离对应了.index、.timeindex、.txnindex 文件。

与之相干的源码如下：

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

2、OffsetIndex.scala：位移索引，保留了位移值和对应磁盘物理地位的关系

3、TimeIndex.scala：工夫戳索引，保留了工夫戳和对应位移值的关系

4、TransactionIndex.scala：事务索引，启用 Kafka 事务之后才会呈现这个索引（本文暂不波及事务相干内容）

<center> 索引类图 </center>

先来看看 AbstractIndex 的定义

image

AbstractIndex 的定义在代码里曾经正文了，成员变量外面还有个entrySize。这个变量其实是每个索引项的大小，每个索引项的大小是固定的。

entrySize

在 OffsetIndex 中是 override def entrySize = 8，8 个字节。
在TimeIndex中是override def entrySize = 12,12 个字节。

为何是 8 和 12？

在 OffsetIndex 中，每个索引项存储了位移值和对应的磁盘物理地位，因而 4 +4=8，然而不对啊，磁盘物理地位是整型没问题，然而 AbstractIndex 的定义 baseOffset 来看，位移值是长整型，不是因为 8 个字节么？

因而 存储的位移值实际上是绝对位移值 ，即 实在位移值 -baseOffset 的值。

绝对位移用整型存储够么？够，因为一个日志段文件大小的参数 log.segment.bytes 是整型，因而同一个日志段对应的 index 文件上的位移值 -baseOffset 的值的差值必定在整型的范畴内。

为什么要这么麻烦，还要存个差值？

1、为了节俭空间，一个索引项节俭了 4 字节，想想那些日音讯解决数万亿的公司。

2、因为内存资源是很贵重的，索引项越短，内存中能存储的索引项就越多，索引项多了间接命中的概率就高了。这其实和 MySQL InnoDB 为何倡议主键不宜过长一样。每个辅助索引都会存储主键的值，主键越长，每条索引项占用的内存就越大，缓存页一次从磁盘获取的索引数就越少，一次查问须要拜访磁盘次数就可能变多。而磁盘拜访咱们都晓得，很慢。

互相转化的源码如下，就这么个简略的操作：

image

上述解释了位移值是 4 字节，因而 TimeIndex 中工夫戳 8 个字节 + 位移值 4 字节 = 12 字节。

_warmEntries

这个是干什么用的？

首先思考下咱们能通过索引项疾速找到日志段中的音讯，然而咱们如何疾速找到咱们想要的索引项呢？一个索引文件默认 10MB，一个索引项 8Byte，因而一个文件可能蕴含 100 多 W 条索引项。

不论是音讯还是索引，其实都是枯燥递增，并且都是追加写入的，因而数据都是有序的。在有序的汇合中疾速查问，脑海中突现的就是二分查找了！

那就来个二分！

二分查找

这和 _warmEntries 有什么关系？首先想想二分有什么问题？

就 Kafka 而言，索引是在文件开端追加的写入的，并且个别写入的数据立马就会被读取。所以数据的热点集中在尾部。并且操作系统基本上都是 用页为单位缓存和治理内存的，内存又是无限的，因而会通过类 LRU 机制淘汰内存。

看起来 LRU 非常适合 Kafka 的场景，然而应用规范的二分查找会有缺页中断的状况，毕竟二分是跳着拜访的。

这里要说一下 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)

翻译下：当咱们查找索引的时候，规范的二分查找对缓存不敌对，可能会造成不必要的缺页中断(线程被阻塞期待从磁盘加载没有被缓存到 page cache 的数据)

正文还敌对的给出了例子

image

简略的来讲，假如某索引占 page cache 13 页，此时数据曾经写到了 12 页。依照 kafka 拜访的个性，此时拜访的数据都在第 12 页，因而二分查找的个性，此时缓存页的拜访程序顺次是 0，6，9，11，12。因为频繁被拜访，所以这几页肯定存在 page cache 中。

当第 12 页一直被填充，满了之后会申请新页第 13 页保留索引项，而依照二分查找的个性，此时缓存页的拜访程序顺次是：0，7，10，12。这 7 和 10 很久没被拜访到了，很可能曾经不再缓存中了，而后须要从磁盘上读取数据。正文说：在他们的测试中，这会导致至多会产生从几毫秒跳到 1 秒的提早。

基于以上问题，Kafka 应用了改进版的二分查找，改的不是二分查找的外部，而且把所有 索引项分为热区和冷区

这个改良能够让 查问热数据局部时，遍历的 Page 永远是固定的，这样能防止缺页中断。

看到这里其实我想到了 一致性 hash，一致性 hash 绝对于一般的 hash 不就是在 node 新增的时候缓存的拜访固定，或者只须要迁徙少部分数据。

好了，让咱们先看看源码是如何做的

image

实现并不难，然而为何是把尾部的 8192 作为热区？

这里就要再提一下源码了，讲的很具体。

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.).

 大抵内容就是当初处理器个别缓存页大小是 4096，那么 8192 能够保障页数小于等 3，用于二分查找的页面都能命中 

1. 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)的音讯数据，足够让大部分在 in-sync 内的节点在热区查问 

以上就解释了什么是_warmEntries，并且为什么须要_warmEntries。

能够看到 奢侈的算法在真正工程上的利用还是须要看具体的业务场景的，不可生吞活剥。并且彻底的了解算法也是很重要的，例如死记硬背二分，怕是看不出来以上的问题。还有底层常识的重要性。不然也是看不出来对缓存不敌对的。

从 Kafka 的索引冷热分区到 MySQL InnoDB 的缓冲池治理

从下面这波冷热分区我又想到了 MySQL 的 buffer pool 治理。MySQL 的将缓冲池分为了新生代和老年代。默认是 37 分，即老年代占 3，新生代占 7。即看作一个链表的尾部 30% 为老年代，后面的 70% 为新生代。替换了规范的 LRU 淘汰机制。

image

MySQL 的缓冲池分区是为了解决 预读生效 和缓存净化 问题。

1、预读生效：因为会预读页，假如预读的页不会用到，那么就白白预读了，因而让预读的页插入的是老年代头部，淘汰也是从老年代尾部淘汰。不会影响新生代数据。

2、缓存净化：在相似 like 全表扫描的时候，会读取很多冷数据。并且有些查问频率其实很少，因而让这些数据仅仅存在老年代，而后疾速淘汰才是正确的抉择，MySQL 为了解决这种问题，仅仅分代是不够的，还设置了一个工夫窗口，默认是 1s，即在老年代被再次拜访并且存在超过 1s，才会降职到新生代，这样就不会净化新生代的热数据。

小结

文章先从索引动手，这就是工夫和空间的调换。而后引出 Kafka 中索引存储应用了绝对位移值，节俭了空间，并且讲述了索引项的拜访是由二分查找实现的，并联合 Kafka 的应用场景解释了 Kafka 中应用的冷热分区实现改进版的二分查找，并顺带提到了下一致性 Hash，再由冷热分区联想到了 MySQL 缓冲池变形的 LRU 治理。

这一步步实际上都体现算法在工程中的灵活运用和变形实现。有些同学认为算法没用，刷算法题只是为了面试，实际上各种中间件和一些底层实现都体现了算法的重要性。

不说了，头有点冷。

7 人点赞

Kafka