4. Offset 索引原理：索引条目结构、二分查找算法、索引稀疏性设计

Offset 索引是 Kafka 实现 O(1) 消息定位的核心数据结构。它解决了“给定一个逻辑偏移量，如何快速找到其在物理日志文件中的位置”这一关键问题。本章深入剖析索引条目的二进制结构、二分查找的工程实现细节以及稀疏索引的设计权衡。

4.1 索引条目结构

每个 Offset 索引文件（.index）由固定大小的条目组成，每个条目仅占 8 字节，分为两个字段：

索引文件在磁盘上的二进制布局如下：

+----------------+----------------+----------------+----------------+
| relativeOffset |    position    | relativeOffset |    position    |
|    (4 bytes)   |   (4 bytes)    |    (4 bytes)   |   (4 bytes)    |
+----------------+----------------+----------------+----------------+
| <--- Entry 0 ---> | <--- Entry 1 ---> | ... 直到文件末尾

4.2 二分查找算法

Kafka 在索引文件上执行的是 改进的二分查找，而非标准二分。核心差异在于：索引条目是稀疏的，且查找目标是一个“不大于目标 offset 的最大索引条目”。

算法步骤：

1. 确定搜索区间：以索引文件的总条目数计算 low=0，high=numEntries-1。
2. 计算中间条目：mid = (low + high + 1) / 2（上取整，避免死循环）。
3. 比较 relativeOffset：读取 mid 条目的 relativeOffset，与目标 relativeOffset 比较。
   • 若 midOffset <= targetOffset：low = mid（保留 mid 作为候选）。
   • 若 midOffset > targetOffset：high = mid - 1。
4. 终止条件：当 low == high 时，low 即为不大于目标 offset 的最大索引条目。
5. 获取 position：从 low 条目中读取 position，然后从该位置开始在 .log 文件中顺序扫描找到精确消息。

4.3 索引稀疏性设计

Kafka 的索引并非为每条消息都建立条目，而是采用 稀疏索引 策略。稀疏参数由 log.index.interval.bytes（默认 4096 字节）控制。

稀疏索引的写入触发条件：

• 当累积写入的字节数达到 log.index.interval.bytes（默认 4KB）时，追加一条索引条目。
• 如果消息批次（batch）跨越了该边界，则只记录边界处的第一条消息。

稀疏性带来的权衡：

4.4 Offset 索引整体架构

下图展示了 Offset 索引、日志文件与二分查找之间的协作关系：

4.5 索引文件管理与清理

Kafka 通过以下机制管理索引文件的生命周期：

• Segment 滚动：当 .log 文件达到 log.segment.bytes 或 log.segment.ms 时，同时关闭当前 .index 文件并创建新的 Segment。
• 索引截断：当发生 Leader 切换或日志截断时，索引文件必须与日志文件保持精确一致。Kafka 通过 truncateTo 操作同时截断 .log 和 .index。
• 过期删除：基于 log.retention.hours 或 log.retention.bytes 策略，删除过期 Segment 时一并删除对应的索引文件。