04 | 索引（上）：改进的二分查找算法在Kafka索引的应用
为什么要阅读索引源码？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
Kafka索引源码中应用了改进版的二分查找算法，具有值得深入学习的技术特点。文章介绍了Kafka索引的组成结构，包括AbstractIndex、LazyIndex、OffsetIndex、TimeIndex和TransactionIndex等类的关系。其中，OffsetIndex、TimeIndex和TransactionIndex继承了AbstractIndex类，而LazyIndex是对AbstractIndex的包装类，用于延迟加载以提升性能。AbstractIndex类定义了索引文件、起始位移值、索引文件最大字节数和索引文件打开方式等属性字段，以及一个抽象方法entrySize。具体的索引实现类中，OffsetIndex的索引项是<位移值，物理磁盘位置>对，TimeIndex的索引项是<时间戳，位移值>对。文章还详细介绍了AbstractIndex中的MappedByteBuffer的创建过程以及OffsetIndex的append方法的执行流程。总之，对于想要深入了解Kafka索引源码及二分查找算法应用的读者来说，这篇文章是一篇值得阅读的文章。文章还介绍了二分查找算法的原版实现和改进版，改进版算法提供了一个重要的保证：它能保证那些经常需要被访问的Page组合是固定的，从而避免无意义的Page Fault。
《Kafka 核心源码解读》，新⼈⾸单¥59
全部留言(23)
- 最新
- 精选
胡夕置顶你好，我是胡夕。我来公布上节课的“课后讨论”题答案啦～ 上节课，咱们重点了解了日志对象的常见操作，课后我让你思考下能否为Log源码添加一个简便方法，统计介于高水位值和LEO值之间的消息总数。以下是我的答案： private[log] def messageCountBetweenHWAndLEO: Long = { logEndOffset - highWatermarkMetadata.messageOffset } okay，你是怎么考虑的呢？我们可以一起讨论下。2020-04-232
Jonah置顶按照注释讲的分析，主要是为了保证热区的页数小于3个，另外保证in-sync 的查找都能命中作者回复: 👍👍
2020-04-214
小虞仔课后作业：1. 主流的处理器架构中4096一般是最小的页面大小，这样可以保证页数小于三，在二分查找时，可以命中所有的页面。 2. 8KB的索引，可以覆盖4M数据（offset index）或者2.7M数据（time index）足够保证in-sync的查找的内容都在热区作者回复: 👍
2020-05-216
小崔冷热分离如何生效的，刚开始看文章没看懂，又翻了源码注释，才明白了。这里梳理一下我觉得更易懂的说法：大部分查询集中在索引项尾部->把尾部的8192字节设置为热区，永远保存在缓存中->如果查询target在热区索引项范围，直接查热区，避免页中断。作者回复: 嗯，是这个意思👍
2020-05-015
ByteFeng胡夕老师，你能不能出个kafka视频课程呀???文字专栏理论性比较强，视频课程的实战性比较强。。。。。作者回复: 嗯嗯，之前确实有过对照着IDEA直接讲源码的想法。因为觉得直接演示怎么搭建环境、怎么修改源码、怎么写测试用例可能比文字来的有冲击力。后续我会认真考虑看看的。谢谢您的建议：）
2020-04-225
lei日志段有个参数indexIntervalBytes， 可以理解为插了多少条消息之后再建一个索引，由此看出kafka的索引其实是稀疏索引。那也就是说二分查找之后，还有一个顺序遍历查找目标文件的过程。我这样理解对吗？作者回复: 嗯嗯，会有的
2020-07-053- Geek_14e7f8而 Broker 端参数 log.segment.bytes 是整型，这说明，Kafka 中每个日志段文件的大小不会超过 2^32，即 4GB，这就说明同一个日志段文件上的位移值减去 baseOffset 的差值一定在整数范围内。 你好， 关于这里日志大小有点疑问，java中整形最大值是 2^31 - 1 ，所以单个日志最大应该是2G吧？
作者回复: 单个日志段是2GB，日志当然可以无限大小
2020-11-192 
yic老师，我想问2个问题： 1. 为什么8K index offset可以覆盖4M的数据？ 2. 8K其实是一个经验值吧？考虑的点主要是non-lagging consumer的性能和占用的缓存空间。作者回复: 1. 8KB = 8092B, 每个位移索引项大小是8B，所以这个热区能够保存1024个索引项。由于默认每4KB写入一个索引项，因此8KB的热区能够覆盖1024 * 4KB = 4MB的日志数据 2. 同意~
2020-08-0422
曾轼麟我对8192的理解是这样的： broker默认的索引文件大小segment.index.bytes = 10 MB，8192刚好大约是10MB的80%，根据2/8定律，最新的20%的数据可能会是热点数据所以设置为8192切分冷区和热区。 但是这里也有两个问题希望能得到老师的看法： 1、如果我修改了segment.index.bytes大小或者修改了Linux的页缓存大小设置，会不会导致冷热区查询性能失去了，毕竟代码是写死的8196. 2、如果我频繁范围冷区，当页缓存满的时候，热区本身也会失效假入有两个consumer-group，一共消费能力强的在消息发送出来后能立即消费，另一个消费能力弱，还在消费昨天的数据，的情况下应该还是会出现这种页缓存带来的性能问题吧作者回复: 1. 所以不要贸然修改这个默认值：） 2. 这个算法保证主要保证non-lagging consumer的性能。lagging consumer确实享受不到，甚至是拖累其他consumer，因为它会“污染”页缓存
2020-04-2551- 曾轼麟老师，TransactionIndex好像已经没有继承于，AbstractIndex了。TransactionIndex好像变成了一种特殊的索引了，是独立的，TimeIndex 和 OffsetIndex 是作为泛型给 LazyIndex 使用的
作者回复: 嗯嗯，源码的确在不断演进中。现在的优化思路是朝着延迟初始化索引，期望快速缩短broker启动时间
2020-11-08
