SSTable

tantivy-sstable crate 是另一个sstable crate。

它被设计用于在 quickwit 中使用

• 作为默认的 tantivy fst 字典的替代方案。
• 作为存储动态快速字段的列索引的方法。

与 fst crate 相比的优势是局部性。在 fst crate 中搜索键需要下载整个字典。

一旦下载了 sstable 索引，在 sstable crate 中运行 get 只需要一次获取。

目前，已为 quickwit 设计了块索引和默认块大小，但 get 的性能非常差。

排序字符串？

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

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

• 它使得获取键和键的范围流式传输成为可能。
• 它允许增量编码键
• 前压缩被利用以优化与自动机的交集

磁盘格式

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

SSTable

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

• Block(SSTBlock): 独立块的列表，以单个空块结束。
• Footer(SSTFooter)

SSTBlock

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

• BlockLen(u32): 块的长度，包括压缩字节。
• Compress(u8): 指示块是否压缩。如果不压缩则为0，如果压缩则为1。
• Values：一个应用程序定义的格式，用于存储一系列值，可以确定自己的长度。
• Delta

Delta

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

• KeepAdd
• Suffix：保留Add字节的键后缀。

KeepAdd

KeepAdd可以表示为两种不同的表示形式，一种非常紧凑的1字节表示形式，对于大多数使用情况来说足够了，当需要时，还有更长的一些可变长度表示形式。

当保留 < 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的块。