知识卡片
按时间查找经过两级索引
要找时间不早于目标值的消息,书中 Kafka 2.0.0 的路径先逐段比较日志分段的最大时间戳,选择第一个最大值不小于目标的分段;时间索引不能像位移那样用 baseOffset 的跳跃表直接选段。进入该段后,在 .timeindex 二分找时间不大于目标的最大项,取得相对位移;再在 .index 二分找不大于这个位移的最大项,取得 .log 物理位置;最后从那里顺序扫描,找出时间满足条件的消息。
图 5-12 的目标时间为 1526384718288:时间索引先返回 [1526384718283, 28],偏移量索引再返回 [26, 838],于是从日志文件字节位置 838 开始扫描。前两次定位只给出安全起点,不能将索引项的时间或位移误认为最终命中的消息。
结构图:
flowchart LR
T[目标时间] --> S[逐段比较最大时间戳]
S --> TI[时间索引二分:时间到相对位移]
TI --> OI[偏移量索引二分:位移到字节位置]
OI --> L[顺序扫描日志至时间满足条件]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入理解Kafka:核心设计与实践原理 2019》第5章 5.3.2 节(源文件:`_epub-src/OEBPS/Text/chapter6.xhtml`;正文归一化字符位 15012–16426;图 5-12 `197_2.jpg`)
- 结论依据:原文按四步列出选段、时间索引、偏移量索引与日志扫描,给出目标时间及 `[1526384718283,28]`、`[26,838]` 两级索引项;图 5-12 已回读。
- 原始内容:将targetTimeStamp和每个日志分段中的最大时间戳largestTimeStamp逐一对比……在时间戳索引文件中使用二分查找算法查找到不大于targetTimeStamp的最大索引项,即[1526384718283,28]……在偏移量索引文件中使用二分算法查找到不大于28的最大索引项,即[26,838]……从……838的物理位置开始查找不小于targetTimeStamp的消息。