1.6.4 LSM 查找机制

先前提到，Kafka 中的消息消费是通过offset进行查找的，那么具体要怎么从一个offset查找到对应的message呢？

简单易懂的流程图：

《简单易懂》

这个流程图中蕴含了以下几点：

1. 每个segment的最大大小固定一致，但其中存放着的消息数量不是一致的

2. segment对应的文件命名是有专门的命名规则的：分区的第一个segment固定命名为000...00，此后的segment以上一个segment中存储的最后一条消息的offset为自己的文件名

现在考虑有一个offset要查询，Kafka的查询流程：

1. 在文件名列表中二分查找到对应的 .index 和 .log 文件 （按照刚才提到的规则，文件名应该是有序的offset列表，二分查找在有序列表中性能很高）

2. 依据找到的 index 文件，查找到 offset 具体对应的 log 文件中 message 的物理地址，从而找到数据

这里我对 index文件的理解类似是一个稀疏 hash 表：

index文件具体内容，图源网络

可以看到，index文件中实际存放的是offset与物理位置的对应关系，并且由于整体存储方式是有序的，所以并不需要存储每一个offset对应的position，相比传统hash表有节省空间的优势。

Cache-friendly binary search

在我阅读的 1.1 版本的 Kafka 代码中，有关先前提到的二分查找的代码是这样完成的：

朴实无华的二分

注意到这里就是一个很正常的二分，没有什么特别的地方。

然而，在实际使用中，人们发现由于实际查找往往位于序列末尾，在两次不同的二分查找之间会导致频繁的缺页异常发生：

两次二分所带来的缺页异常

于是，Kafka 的工程师们为了防止物理页在内存和磁盘里换来换去，提出了热区（warmEntries）这一概念。简单来说，序列末尾一定大小的区域被划分为热区（这个经验值一般为 8KB ），查找时对处于热区和不处于热区的offset进行单独查找：

查找逻辑，图源自CSDN

热区的设计使得大部分查找避免了页替换的过程，从而进一步提升了其搜索效率，也是Kafka利用操作系统底层实现来优化自身性能的又一体现。