SSTable

《tantivy-sstable》是一个sstable库。

它被设计用来在 quickwit 中使用，作为 tantivy 默认 fst 字典的替代品。

• 作为存储动态快速字段的列索引的一种方式。
• 与 fst 库相比，其优点在于局部性。在 fst 库中搜索键需要下载整个字典。

一旦下载了 sstable 索引，在 sstable 库中执行 get 操作只需要一次获取。

目前，块索引和默认块大小是为 quickwit 设计的，get 操作的性能非常差。

排序字符串？

SSTable 代表有序字符串表。字符串必须按照排序顺序插入。

这种排序顺序以不同的方式使用

它使得获取键和键的流式范围成为可能。

• 它允许键的增量编码
• 前压缩被用来优化与自动机的交集
• 磁盘格式

SSTable 格式的概述。除非另有说明，否则数字都是小端格式。

块(SSTBlock)：独立块的列表，以一个空块结束。

SSTable

+-------+-------+-----+--------+
| Block | Block | ... | Footer |
+-------+-------+-----+--------+
|----( # of blocks)---|

• Footer(SSTFooter)
• SSTBlock

SSTBlock

+----------+----------+--------+-------+-------+-----+
| BlockLen | Compress | Values | Delta | Delta | ... |
+----------+----------+--------+-------+-------+-----+
                      |        |----( # of deltas)---|
                      |------(maybe compressed)------|

• BlockLen(u32)：块长度，包括压缩字节。
• Compress(u8)：指示块是否压缩。未压缩为 0，压缩为 1。
• Values：一个应用程序定义的格式，用于存储一系列值，能够确定其自身长度。
• Delta

Delta

+---------+--------+
| KeepAdd | Suffix |
+---------+--------+

• KeepAdd
• Suffix：键后缀的 KeepAdd.add 字节

KeepAdd

KeepAdd 可以表示为两种不同的形式，一种是极其紧凑的 1 字节形式，适用于大多数情况，另一种是更长的可变长度形式，在需要时使用。

当 keep < 16 且 add < 16 时

+-----+------+
| Add | Keep |
+-----+------+

• Add(u4)：要推送的字节数
• Keep(u4)：要弹出的字节数

否则

+------+------+-----+
| 0x01 | Keep | Add |
+------+------+-----+

• Add(VInt)：要推送的字节数
• Keep(VInt)：要弹出的字节数

注意：由于 SSTable 不支持冗余键，这两种表示之间没有歧义。Add 总是保证非零，除了 SSTable 的第一个键，那里的 Keep 保证为零。

SSTFooter

+-----+----------------+-------------+-------------+---------+---------+
| Fst | BlockAddrStore | StoreOffset | IndexOffset | NumTerm | Version |
+-----+----------------+-------------+-------------+---------+---------+

• Fst(Fst)：有限状态转换器，将键映射到块号
• BlockAddrStore(BlockAddrStore)：将块号映射到其 BlockAddr 存储
• StoreOffset(u64)：BlockAddrStore 起始偏移量。如果为零，请参阅 SingleBlockSStable 部分
• IndexOffset(u64)：SSTFooter 起始偏移量
• NumTerm(u64)：sstable 中的项数
• Version(u32)：目前等于 3

Fst

Fst 的格式为 tantivy_fst

BlockAddrStore

+---------+-----------+-----------+-----+-----------+-----------+-----+ | MetaLen | BlockMeta | BlockMeta | ... | BlockData | BlockData | ... | +---------+-----------+-----------+-----+-----------+-----------+-----+ |---------(N blocks)----------|---------(N blocks)----------|

• MetaLen(u64)：BlockMeta 部分的长度
• BlockMeta(BlockAddrBlockMetadata)：用于通过 BlockData 查找的元数据
• BlockData(CompactedBlockAddr)：每个块元数据的位打包

BlockAddrBlockMetadata

+--------+------------+--------------+------------+--------------+-------------------+-----------------+----------+ | Offset | RangeStart | FirstOrdinal | RangeSlope | OrdinalSlope | FirstOrdinalNBits | RangeStartNBits | BlockLen | +--------+------------+--------------+------------+--------------+-------------------+-----------------+----------+

• Offset(u64)：数据流中对应 BlockData 的偏移量
• RangeStart(u64)：第一个块的起始位置
• FirstOrdinal(u64)：第一个块的第一个序号
• RangeSlope(u32)：预测的起始范围进化斜率（参见 BlockData 中的计算）
• OrdinalSlope(u64)：预测的第一个序号进化斜率（参见 BlockData 中的计算）
• FirstOrdinalNBits(u8)：数据流中每个序号的位数（参见 BlockData 中的计算）
• RangeStartNBits(u8)：数据流中每个范围起始的位数（参见 BlockData 中的计算）

BlockData

+-----------------+-------------------+---------------+ | RangeStartDelta | FirstOrdinalDelta | FinalRangeEnd | +-----------------+-------------------+---------------+ |------(BlockLen repetitions)---------|

• RangeStartDelta(var)：RangeStartNBits 位的小端数。下面进行解码
• FirstOrdinalDelta(var)：FirstOrdinalNBits 位的小端数。下面进行解码
• FinalRangeEnd(var)：RangeStartNBits 位的整数。下面进行解码

将索引 Index 的 BlockData 和 BlockAddrBlockMetadata 转换为实际块地址的方法如下：range_prediction := RangeStart + Index * RangeSlop; range_derivation := RangeStartDelta - (1 << (RangeStartNBits-1)); range_start := range_prediction + range_derivation

可以对序号进行相同的计算。

注意，range_derivation 可以取负值。RangeStartDelta 只是将其转换为正范围。

SingleBlockSStable

用于索引的格式旨在紧凑，但它有一个约为 70 字节的常数成本，这对于包含很少键的表来说不是微不足道的。为了限制这个常数成本的影响，单个块 sstable 在其索引中省略了 Fst 和 BlockAddrStore。相反，对于每个操作，隐式使用一个块，其第一个序号为 0，范围起始为 0，范围结束为 IndexOffset。