中年|做开发的到底要不要掌握算法？需要掌握到什么程度？( 二 )
不论是消息还是索引 ， 其实都是单调递增 ， 并且都是追加写入的 ， 因此数据都是有序的 。 在有序的集合中快速查询 ， 脑海中突现的就是二分查找了！
那就来个二分！
本文插图
二分查找
这和_warmEntries有什么关系？首先想想二分有什么问题？
就Kafka而言 ， 索引是在文件末尾追加的写入的 ， 并且一般写入的数据立马就会被读取 。 所以数据的热点集中在尾部 。 并且操作系统基本上都是用页为单位缓存和管理内存的 ， 内存又是有限的 ， 因此会通过类LRU机制淘汰内存 。
看起来LRU非常适合Kafka的场景 ， 但是使用标准的二分查找会有缺页中断的情况 ， 毕竟二分是跳着访问的 。
这里要说一下kafka的注释写的是真的清晰 ， 咱们来看看注释怎么说的
when looking up index, the standard binary search algorithm is not cache friendly, and can cause unnecessarypage faults (the thread is blocked to wait for reading some index entries from hard disk, as those entries are notcached in the page cache)
翻译下：当我们查找索引的时候 ， 标准的二分查找对缓存不友好 ， 可能会造成不必要的缺页中断(线程被阻塞等待从磁盘加载没有被缓存到page cache 的数据)
注释还友好的给出了例子
本文插图
简单的来讲 ， 假设某索引占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新增的时候缓存的访问固定 ， 或者只需要迁移少部分数据 。
好了 ， 让我们先看看源码是如何做的
本文插图
实现并不难 ， 但是为何是把尾部的8192作为热区？
这里就要再提一下源码了 ， 讲的很详细 。
This number is small enough to guarantee all the pages of the "warm" section is touched in every warm-sectionlookup. 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 wetouch 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 ， 用于二分查找的页面都能命中
This number is large enough to guarantee most of the in-sync lookups are in the warm-section. With default Kafkasettings, 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内的节点在热区查询
推荐阅读
- 中子|中子的寿命到底有多长？多种方法试错，谜题亟待解决！
- 帐户|苹果发布声明：确定 Epic Games 开发账户被终止
- 人工智能|商汤科技林达华：OpenMMLab助开发者缩短AI项目路径
- 中年|北斗“一张网”可实现全天候、高精度、自主可控服务
- 中年|Python编程语言有什么独特的优势呢?
- NOFAKE无假|一天到晚说我不配套，这鞋盒到底哪里不配套？
- 中年|谈一谈我的十年机械工作经历
- 中年|弹无虚发的背后，国产弹药质量把关人，精密机床都要自叹不如
- 中年|宿迁深圳招商再结硕果，签约项目19个，协议总投资158亿元
- 拼多多|越补越疯狂！拼多多瞄准文教领域，一招要让学生党省钱到底