[RIP-65] Support efficient random index for massive messages

[lizhimins]

Before Creating the Enhancement Request

• I have confirmed that this should be classified as an enhancement rather than a bug/feature.

Docs Author: @bareheadtom @lizhimins

Summary

在云原生场景下，对象存储能够为用户提供弹性和按量付费的能力，有效降低存储成本，但对随机读写的支持不够友好。RocketMQ 的队列模型中写入的数据是按时间近似有序的，对于随机索引的构建也是近似有序的，我们希望对于索引模块实现non-stop write 的特性，同时支持冷热分离，而现有的分级存储索引的设计在部分高并发情况下可能会出现消息索引丢失，宕机时可能出现文件无法写入，死循环，代码的封装和可读性较低等问题。因此提出本设计进行改进。

Motivation

现有的分级存储索引的设计在部分高并发情况下可能会出现消息索引丢失，宕机时可能出现文件无法写入，死循环，代码的封装和可读性较低等问题。例如，原有设计在流量突发时会产生索引放入失败。

Describe the Solution You'd Like

@bareheadtom 和我对原来的设计进行了重构，在解决上述问题的基础上，新的实现做到了

1. 存储格式完全向下兼容以支持原地升级。
2. 新的实现上提供了 100% 的方法覆盖率以及性能的提升。

Describe Alternatives You've Considered

在RocketMQ中，由于索引模块是一个写多读极少零更新的结构，因此为了降低系统整体的平均操作代价，单次读有一些读放大的开销是可以接受的。假设消息索引写入时间开销需要 t1 ，平均每条消息索引在经过 t2 之后被查询，格式转换时间开销为 t_compact，通常 t_compact 远远小于 t2，因此 t_compact 可以在 t2 时间内异步完成，格式转换前消息索引查询时间为 t_before ，格式转换后的消息索引平均查询时间开销为 t_after，格式转换后消息索引平均查询时间开销小于格式转换后查询时间开销 t_before < t_after, 那么不进行格式转换数据存储查询时间开销大于进行了格式转换后存储查询时间开销 。
t1 + t2 + t_before > t1 + t2 + t_after。

RocketMQ索引文件使用基于头插法实现的开链的HashTable，在索引写入时可以顺序写入。然而，在进行指定key查询时，由于使用的是单向链表，对key进行hash到指定slot并获取到链表头节点，然后根据链表头节点遍历单向链表属于随机IO查询，对象存储类似于机械硬盘的特性，读取 20 Bytes 和读取数 KB 时间几乎相同，多次随机IO会造成较大的时间开销，因此在较多Hash冲突时可能存在严重的数据读放大问题。为了减少对象存储文件的随机查询访问次数，多级存储异步对索引文件数据格式转换，格式转换后的索引文件可以一次性取回大块数据，可以极大的减少对对象存储文件的IO访问次数。
具体地，随机索引异步重排机制包括以下步骤：

1. 将本地索引文件按照映射后的slot槽为单位进行分组，每组包含一定数量的索引项；
2. 对相同的组按照顺序写入新的索引文件，同一个槽对应的组的索引项在物理地址空间上是连续的数组。
3. 在需要查询时，根据要查询的key的hash值，映射到指定的槽，然后槽的位置存储了数组的首地址，通过遍历数组，确定需要查询索引；
   通过这种方式，可以大大减少在对象存储中进行的随机查询操作，从而提高查询效率，降低时间开销。同时，由于本地索引文件需要进行格式转换和分组，因此也需要一定的计算和存储资源。

Additional Context

No response