Kafka 日志存储 — 日志索引

每个日志分段文件对应两个索引文件：偏移量索引文件用来建立消息偏移量到物理地址之间的映射；时间戳索引文件根据指定的时间戳来查找对应的偏移量信息。

1 日志索引

Kafka的索引文件以稀疏索引的方式构造消息的索引。它并不保证每个消息在索引文件中都有对应的索引项。每当写入一定量的消息时，偏移量索引文件和时间戳索引文件分别增加一个索引项。

使用二分查找法来快速定位偏移量的位置。

1.1 日志分段切分的条件

日志分段文件达到一定添加时需要进行切分，其对应的索引文件也需要进行切分。满足以下一项条件即触发切分：

1. 日志分段文件的大小超过了broker端参数log.segment.bytes配置的值。默认为1GB。
2. 当前日志分段中消息的最大时间戳与当前系统的时间戳的差值大于log.roll.ms 或log.roll.hourse参数配置的值。log.roll.ms的优先级高，默认值为7天。
3. 偏移索引文件或时间戳文件的大小达到broker端参数log.index.size.max.bytes配置的值。默认值为10MB。
4. 追加的消息偏移量与当前日志分段的偏移量之间的差值大于Integer.MAX_VALUE。

1.2 索引文件的创建

对应非活跃的日志分段，其对应的日志及索引文件已经固定，不需要再写入，所以被设定为只读。而当前获取的日志分段，被设定为读写。

索引文件切分时，会关闭当前正在写入的索引文件，并设置为只读模式，同时以可读写模式创建新的索引文件。

在创建索引文件时，会为其预分配log.index.size.max.bytes大小的空间，只有当索引文件进行切分时，才把索引文件裁减到实际的数据大小。

1.3 偏移量索引

每个索引项占用8个字节（8B），分为两部分：

relativeOffset（4B）:相对偏移量，消息相对于baseOffset的偏移量。当前索引文件的文件名即为baseOffset的值。

position（4B）:消息在日志分段文件中对应的物理地址。

消息偏移量（offset）占用8个字节，而Integer 占用4个字节。上面提到追加的消息偏移量与当前日志分段的偏移量之间的差值大于Integer.MAX_VALUE就触发日志分段切分，因为relativeOffset不能用4个字节表示了。

1.3.1 跳跃表

Skip List，简称跳表。本质是一种可以进行二分查找的有序链表。在原有的有序链表上增加了多级索引。提高了搜索、插入及删除性能。

图 跳跃表结构示意图

采用随机技术决定链表中哪些节点应增加向前指针及在该节点应增加多少个指针。头节点需要足够的指针来满足可能构造最大级数的需要，而尾节点不需要指针域。

查找算法：首先在最高级索引查找最好一个小于目标元素的位置，然后在跳到次高级索引继续查找，直到跳到最底层为止。

1.3.2 查找算法

Kafka的每个日志对象中使用来ConcurrentSkipListMap来保存各个日志分段，每个日志分段的baseOffset作为key。查找算法如下：

1. 根据跳跃表来确定目标偏移量所在的日志分段及索引文件。
2. 计算出相对偏移量： 目标偏移量 - 日志分段偏移量。
3. 在索引文件中找到最大的不大于相对偏移量的索引项。
4. 根据索引项中的position定位到具体的日志分段文件位置，开始顺序查找目标的最终位置。

Kafka强制要求索引文件的大小必须是索引项大小的整数倍。

1.4 时间戳索引

根据指定的时间戳来查找对应的偏移量信息。

每个索引项占用12个字节，分为两部分：

timestamp（8B）：消息对应的时间戳。

relativeOffset（4B）：时间戳所对应的消息的相对偏移量。

1.4.1 保证时间戳单调递增

每个追加的时间戳索引项中的timestamp必须大于之前追加的，否则不予追加。如果时间戳类型为LogAppendTime，那么消息的时间戳必定能够保持单调递增。

如果是CreateTime 类型则无法保证。如果两个不同时钟的生产者同时往一个分区中插入消息，则可能会造成当前分区的时间戳乱序。

1.4.2 查找算法

每当写入一定量的消息时，就会在偏移索引文件和时间戳索引文件中分别增加一个索引项。两个文件增加索引操作是同时进行的，但并不意味着两者指向同一个值。

时间戳索引不是通过跳跃表来定位相应的日志片段。步骤如下：

1. 查找日志分段，将目标时间戳和每个日志分段中的最大时间戳逐一对比，直到找到不小于目标时间戳的对应日志分段。（日志分段的最大时间戳是先查询该日志所对应的时间戳索引文件，找到最好一条索引项，若时间戳字段大于0，则取其值，否则取该日志分段的最近修改时间）
2. 查找相对偏移量。在时间戳索引中使用二分查找找到不大于目标时间戳的最大索引项，来找到一个相对偏移量。
3. 在偏移量索引文件中根据这个相对偏移量来查找到其物理位置。
4. 从物理位置开始顺序查找最大的不小于目标时间戳的消息。