最近有学习些Kafak的源码，想给咱们共享下Kafak中改善的二分查找算法。二分查找，是每个程序员都应把握的根底算法，而Kafka是怎么改善二分查找来应用于自己的场景中，这很值得咱们了解学习。

因为Kafak把二分查找应用于索引查找的场景中，所以本文会先对Kafka的日志结构和索引进行简略的介绍。在Kafak中，音讯以日志的办法保存，每个日志其实便是一个文件夹，且存有多个日志段，一个日志段指的是文件名(开始偏移)相同的音讯日志文件和4个索引文件，如下图所示。

在音讯日志文件中以追加的办法存储着音讯，每条音讯都有着仅有的偏移量。在查找音讯时，会凭借索引文件进行查找。假如依据偏移量来查询，则会凭借位移索引文件来定位音讯的方位。为了便于评论索引查询，下文都将依据位移索引这一布景。位移索引的实质是一个字节数组，其间存储着偏移量和相应的磁盘物理方位，这儿偏移量和磁盘物理方位都固定用4个字节，能够看做是每8个字节一个key-value对，如下图：

索引的结构现已清楚了，下面就能正式进入本文的主题“二分查找”。给定索引项的数组和target偏移量，可写出如下代码：

privatedefindexSlotRangeFor(idx:ByteBuffer,target:Long,searchEntity:IndexSearchEntity):(Int,Int)={
//_entries表明索引项的数量
//1.假如当时索引为空，直接回来(-1,-1)表明没找到
if(_entries==0)
return(-1,-1)
//2.确保查找的偏移量不小于当时最小偏移量
if(compareIndexEntry(parseEntry(idx,0),target,searchEntity)>0)
return(-1,0)
//3.履行二分查找算法，找出target
varlo=0
varhi=_entries-1
while(lo<hi){
valmid=ceil(hi/2.0+lo/2.0).toInt
valfound=parseEntry(idx,mid)
valcompareResult=compareIndexEntry(found,target,searchEntity)
if(compareResult>0)
hi=mid-1
elseif(compareResult<0)
lo=mid
else
return(mid,mid)
}
(lo,if(lo==_entries-1)-1elselo+1)
}

上述代码运用了一般的二分查找，下面咱们看下这样会存在什么问题。尽管每个索引项的巨细是4B，但操作系统拜访内存时的最小单元是页，一般是4KB，即4096B，会包括了512个索引项。而找出在索引中的指定偏移量，关于操作系统拜访内存时则变成了找出指定偏移量地点的页。假定索引的巨细有13个页，如下图所示：

因为Kafka读取音讯，一般都是读取最新的偏移量，所以要查询的页就会集在尾部，即第12号页上。下面咱们结合上述的代码，看下查询最新偏移量，会拜访哪些页。依据二分查找，将顺次拜访6、9、11、12号页。

当跟着Kafka接纳音讯的添加，索引文件也会添加至第13号页，这时依据二分查找，将顺次拜访7、10、12、13号页。

能够看出拜访的页和上一次的页彻底不同。之前在只要12号页的时分，Kafak读取索引时会频频拜访6、9、11、12号页，而因为Kafka运用了mmap来进步速度，即读写操作都将经过操作系统的page cache，所以6、9、11、12号页会被缓存到page cache中，防止磁盘加载。可是当增至13号页时，则需求拜访7、10、12、13号页，而因为7、10号页长期没有被拜访(现代操作系统都是运用LRU或其变体来办理page cache)，很或许现已不在page cache中了，那么就会形成缺页中止(线程被堵塞等候从磁盘加载没有被缓存到page cache的数据)。在Kafka的官方测验中，这种状况会形成几毫秒至1秒的推迟。

鉴于以上状况，Kafka对二分查找进行了改善。已然一般读取数据会集在索引的尾部。那么将索引中最终的8192B(8KB)划分为“热区”，其余部分划分为“冷区”，别离进行二分查找。代码完成如下：

privatedefindexSlotRangeFor(idx:ByteBuffer,target:Long,searchEntity:IndexSearchType):(Int,Int)={
//1.假如当时索引为空，直接回来(-1,-1)表明没找到
if(_entries==0)
return(-1,-1)
//二分查找封装成办法
defbinarySearch(begin:Int,end:Int):(Int,Int)={
varlo=begin
varhi=end
while(lo<hi){
valmid=(lo+hi+1)>>>1
valfound=parseEntry(idx,mid)
valcompareResult=compareIndexEntry(found,target,searchEntity)
if(compareResult>0)
hi=mid-1
elseif(compareResult<0)
lo=mid
else
return(mid,mid)
}
(lo,if(lo==_entries-1)-1elselo+1)
}
/**
*2.承认热区首个索引项位。_warmEntries便是所谓的分割线，现在固定为8192字节处
*关于OffsetIndex，_warmEntries=8192/8=1024，即第1024个索引项
*大部分查询会集在索引项的尾部，所以把尾部的8192字节设置为热区
*假如查询target在热区索引项规模，直接查热区，防止页中止
*/
valfirstHotEntry=Math.max(0,_entries-1-_warmEntries)
//3.判别target偏移值在热区仍是冷区
if(compareIndexEntry(parseEntry(idx,firstHotEntry),target,searchEntity)<0){
//假如在热区，查找热区
returnbinarySearch(firstHotEntry,_entries-1)
}
//4.确保要查找的位移值不能小于当时最小位移值
if(compareIndexEntry(parseEntry(idx,0),target,searchEntity)>0)
return(-1,0)
//5.假如在冷区，查找冷区
binarySearch(0,firstHotEntry)
}

这样做的优点是，在频频查询尾部的状况下，尾部的页根本都能在page cahce中，然后防止缺页中止。

下面咱们仍是用之前的比如来看下。因为每个页最多包括512个索引项，而最终的1024个索引项地点页会被认为是热区。那么当12号页未满时，则10、11、12会被判定是热区;而当12号页刚好满了的时分，则11、12被判定为热区;当增至13号页且未满时，11、12、13被判定为热区。假定咱们读取的是最新的音讯，则在热区中进行二分查找的状况如下：

当12号页未满时，顺次拜访11、12号页，当12号页满时，拜访页的状况相同。当13号页呈现的时分，顺次拜访12、13号页，不会呈现拜访长期未拜访的页，则能有用防止缺页中止。

关于为什么设置热区巨细为8192字节，官方给出的解说，这是一个适宜的值：

满足小，能确保热区的页数小于等于3，那么当二分查找时的页面都很大或许在page cache中。也便是说假如设置的太大了，那么或许呈现热区中的页不在page cache中的状况。

满足大，8192个字节，关于位移索引，则为1024个索引项，能够掩盖4MB的音讯数据，满足让大部分在in-sync内的节点在热区查询。

最终一句话总结下：在Kafka索引中运用一般二分查找会呈现缺页中止的现象，形成推迟，且结合查询大多会集在尾部的状况，经过将索引区域划分为热区和冷区，别离查找，将尽或许确保热区中的页在page cache中，然后防止缺页中止。