Rust in Everything
基于 tantivy-columnar 0.27.0

快速字段

主线位置：磁盘主线的最后一站 .fast。倒排表回答「哪些文档含这个词」，快速字段回答反过来的问题：「这个文档的这个字段值是多少」。查询主线里按字段排序的 TopDocs、范围查询的一种实现、聚合，读的都是它。写入主线里，SegmentWriter 每收一篇文档就把 FAST 字段的值记进内存，段定稿时一次写成 .fast。

flowchart TB
  doc["Document"] --> ffw["FastFieldsWriter"]
  ffw --> cw["ColumnarWriter"]
  cw --> ops["每列一串 NewDoc 与 Value"]
  ops --> card{"推断基数"}
  card --> idx["列索引"]
  ops --> strq{"字符串列"}
  strq -- 是 --> dict["排序字典 sstable"]
  dict --> ords["值换成序号"]
  strq -- 否 --> vals["u64 值"]
  ords --> est["各编码估算"]
  vals --> est
  est --> pick["取最小写入"]
  idx --> fast[".fast"]
  pick --> fast

tantivy 这一侧只有薄薄一层：src/fastfield/ 共 3020 行，FastFieldsWriter 按 schema 把字段名和值交给列存，读的一侧是 FastFieldReaders。真正的格式在工作区里的 tantivy-columnar crate（columnar/src/ 共 14438 行，按 tag 0.27.0 统计，含单元测试，不含 benches），它又依赖 tantivy-bitpacker 和 tantivy-sstable。三者在 0.27.0 的版本号都是 0.27.0；0.26.1 时 columnar 的版本号还是 0.7.0。

实验平台：M2 Max、macOS 27、rustc 1.99.0，tantivy 0.27.0，release 构建。语料是仓库里的 benches/hdfs.json：10 万行 HDFS 日志，每行有一个真实的秒级 timestamp。实验程序给每篇文档写十几个快速字段，用一个线程写成一个段，然后通过 fast_fields().dynamic_column_handle(..) 拿到每一列的原始字节，自己解析出列索引的类型和值的编码。

.fast 文件：一串列加一张目录

ColumnarWriter 按值的类型分六张 ArenaHashMap（数值、日期、布尔、IP、字节、字符串），键是列名。每条记录写成一串 ColumnOperation：换到新文档时写一个 NewDoc(doc)，然后是 Value(v)，都压进 stacker 的内存池（段写入 讲过这个池）。

serialize 把所有列按（列名、类型）排序后依次写出。文件结构由 ColumnarSerializer 决定：

[列 1][列 2]...[列 n][目录 sstable][目录长度 u64][num_rows u32][版本 u32][魔数 2,113,119,66]

目录是一个 RangeSSTable，键是「列名 + \0 + 类型码」（prepare_key），值是这一列在文件里的字节范围。类型码进了键，所以同名的列可以有几种类型并存，JSON 字段里同一路径既有数字又有字符串时就是这样。打开 .fast 只读目录，用到哪列才切哪列。

基数不写在 schema 里

一个文档在某列上可以有一个值、没有值、或多个值，这叫列的基数（cardinality）。0.27.0 的 schema 里不声明它，ColumnWriter::record 边写边推断：

        match delta_with_last_doc(self.last_doc_opt, doc) {
            DocumentStep::Same => {
                // This is the last encounterred document.
                self.cardinality = Cardinality::Multivalued;
            }
            DocumentStep::Next => {
                self.last_doc_opt = Some(doc);
                self.write_symbol::<S>(ColumnOperation::NewDoc(doc), arena);
            }
            DocumentStep::Skipped => {
                self.cardinality = self.cardinality.max(Cardinality::Optional);
                self.last_doc_opt = Some(doc);
                self.write_symbol::<S>(ColumnOperation::NewDoc(doc), arena);
            }
        }

同一个文档出现第二次就是 Multivalued，跳过了文档就至少是 Optional；get_cardinality 再看最后一个有值的文档后面还有没有文档。Cardinality 三档有序，只升不降。推断按段进行：同一个字段，这个段里每篇都有值是 Full，另一个段里漏了一篇就是 Optional，合并时再统一。

每一列的字节是「列索引 + 列值 + 列索引长度（u32）」，读出来是 Column 的两个字段：

pub struct Column<T = u64> {
    pub index: ColumnIndex,
    pub values: Arc<dyn ColumnValues<T>>,
}

列值是一个稠密数组，下标叫 row id；列索引负责把文档号翻译成 row id（ColumnIndex::value_row_ids）：

  • Full：row id 就是文档号，列索引只有开头那 1 个字节的基数码。
  • Optional：列值只存有值的文档，列索引是一个文档号集合，取值时算「它前面有几个有值的文档」（rank）。OptionalIndex 仿照 roaring bitmap：每 65536 个文档一块，块里的值少于 DENSE_BLOCK_THRESHOLD 就存成 u16 列表（稀疏块），否则存成位图，每 64 位后面跟 2 字节的累计计数（稠密块，固定 10240 字节）。阈值是 10240 / 2 = 5120，常量旁的注释也写 5120；同一个文件里结构体的文档注释写的是 6144，是旧值。
  • Multivalued：一个 optional 索引记哪些文档有值，再加一列「每个有值文档的第一个 row id」（start offsets），用 serialize_multivalued_index 写出。

实测两列：opt 只有文档号是 10 的倍数的文档有值，multi 第 i 篇有 i % 3 个值：

opt        U64 optional    codec BlockwiseLinear min 0 gcd 10 amplitude/gcd 9999 rows 10000; total 17320 B (index 17146, values 170)
multi      U64 multivalued codec BlockwiseLinear min 10 gcd 1 amplitude/gcd 999971 rows 99999; total 139169 B (index 78848, values 60317), start offsets codec Linear (58350 B)
...
multi doc 0: []
multi doc 1: [10]
multi doc 2: [20, 21]
multi doc 3: []
opt doc 0 Some(0), doc 1 None, doc 10 Some(10)

opt 的 10000 个值只占 170 字节，列索引却有 17146 字节：第一块（文档 0 到 65535）有 6554 个值，超过 5120，是 10240 字节的稠密块；第二块 3446 个值，是 6892 字节的稀疏块。值很少的列，大头在列索引。

数值列：先统计，再让每种编码报价

所有数值（u64、i64、f64、日期、布尔，以及字符串的序号）都先单调映射成 u64，然后走 serialize_u64_based_column_values：

    for val in vals.boxed_iter() {
        let val_u64 = val.to_u64();
        stats_collector.collect(val_u64);
        for (_, estimator) in &mut estimators {
            estimator.collect(val_u64);
        }
    }
    for (_, estimator) in &mut estimators {
        estimator.finalize();
    }
    let stats = stats_collector.stats();
    let (_, best_codec, best_codec_estimator) = estimators
        .into_iter()
        .flat_map(|(codec_type, estimator)| {
            let num_bytes = estimator.estimate(&stats)?;
            Some((num_bytes, codec_type, estimator))
        })
        .min_by_key(|(num_bytes, _, _)| *num_bytes)
        .ok_or_else(|| {
            io::Error::new(io::ErrorKind::InvalidData, "No available applicable codec.")
        })?;
    best_codec.to_code().serialize(wrt)?;

第一遍扫描同时喂给统计器和每个候选编码的估算器；每个估算器报一个字节数（报 None 表示不适用），取最小的那个，写一个字节的编码号，再扫第二遍真正写。所以列值必须能遍历两遍。

StatsCollector 统计最小值、最大值、行数，以及所有值与第一个值之差的最大公约数（gcd）。这四个数以 VInt 写在每列值的开头（ColumnStats），三种编码共用。gcd 的用处在注释里写着：秒级时间戳被转成纳秒存，差值全是 10⁹ 的倍数，除掉以后就和存秒一样小。

三种编码（CodecType）：

编码存什么每个值的位宽
Bitpacked(v - min) / gcd整列统一：(max - min) / gcd 需要的位数
Linear整列拟合一条直线，存值与直线的差整列统一：最大偏差需要的位数
BlockwiseLinear每 512 个值一段，各拟合一条直线，存差每段各自的位宽，每段另存直线参数和位宽

读的时候都是常数时间。BitpackedReader::get_val 是一次位提取加一次乘加：

    fn get_val(&self, doc: u32) -> u64 {
        self.stats.min_value + self.stats.gcd.get() * self.unpacker().get(doc, &self.data)
    }

bitpacked::load 对 1 到 8、16、20、24、32、64 位这几种位宽各生成一个把位宽写成常量的读取器，其余位宽共用一个通用的。BlockwiseLinearReader::get_val 先用 idx / 512 找到段，在段里算直线值再加上位提取出的差。

直线（Line）是整数运算：斜率用首尾两个值算，是一个 32.32 的定点数；截距取「让所有差都非负」的那个值，于是差可以按无符号数打包。Linear 的直线只用前 LINE_ESTIMATION_BLOCK_LEN（512）个值训练，攒不够 512 个值就训练不出直线，估算报 None。

普通的数值列只有两个候选。 serialize_column_mappable_to_u64 传的是：

    serialize_u64_based_column_values(
        column_values,
        &[CodecType::Bitpacked, CodecType::BlockwiseLinear],
        output,
    )?;

Linear 只出现在另外两处：多值列的 start offsets（候选是 Bitpacked 和 Linear），以及 0.27.0 新增的 tie-breaker 列（serialize_generated_tie_breaker_column，三种都参与）。tie-breaker 的值在段内连续递增，正是一条直线。

真实数据选了什么

实验的十二列，各自的列类型、基数、选中的编码、统计头和字节数：

ts         U64 full        codec Bitpacked       min 1440670432 gcd 1 amplitude/gcd 20032418 rows 100000; total 312519 B (index 1, values 312514)
ts_sorted  U64 full        codec BlockwiseLinear min 1440670432 gcd 1 amplitude/gcd 20032418 rows 100000; total 27790 B (index 1, values 27785)
ts_date    DateTime full        codec BlockwiseLinear min 10664042468854775808 gcd 1000000000 amplitude/gcd 20032418 rows 100000; total 27799 B (index 1, values 27794)
ts_ms      U64 full        codec BlockwiseLinear min 1440670432000 gcd 1000 amplitude/gcd 20032418 rows 100000; total 27792 B (index 1, values 27787)
seq        U64 full        codec BlockwiseLinear min 0 gcd 1 amplitude/gcd 99999 rows 100000; total 1749 B (index 1, values 1744)
rand       U64 full        codec Bitpacked       min 115005805221539 gcd 1 amplitude/gcd 18446297446089869496 rows 100000; total 800027 B (index 1, values 800022)
rand1k     U64 full        codec Bitpacked       min 0 gcd 1 amplitude/gcd 999 rows 100000; total 125013 B (index 1, values 125008)
severity   Str full        codec BlockwiseLinear min 0 gcd 1 amplitude/gcd 1 rows 100000; total 783 B (index 1, values 727, dictionary 47)
blk        Str full        codec Bitpacked       min 0 gcd 1 amplitude/gcd 9 rows 100000; total 50168 B (index 1, values 50007, dictionary 152)
opt        U64 optional    codec BlockwiseLinear min 0 gcd 10 amplitude/gcd 9999 rows 10000; total 17320 B (index 17146, values 170)
multi      U64 multivalued codec BlockwiseLinear min 10 gcd 1 amplitude/gcd 999971 rows 99999; total 139169 B (index 78848, values 60317), start offsets codec Linear (58350 B)
tb         I64 full        codec Linear          min 9223372036706411460 gcd 1 amplitude/gcd 99999 rows 100000; total 37 B (index 1, values 32)

再把同样的值分别只交给一种编码去写，看三种编码各自的报价（字节）：

  ts         n=100000 Bitpacked 312514, Linear 412535, BlockwiseLinear 316419
  ts_sorted  n=100000 Bitpacked 312514, Linear 312524, BlockwiseLinear 27785
  ts_ms      n=100000 Bitpacked 312516, Linear 437529, BlockwiseLinear 27787
  seq        n=100000 Bitpacked 212509, Linear 16, BlockwiseLinear 1744
  rand       n=100000 Bitpacked 800022, Linear 800033, BlockwiseLinear 802281
  rand1k     n=100000 Bitpacked 125008, Linear 200024, BlockwiseLinear 138883
  seq[..511] n=511    Bitpacked 582, Linear n/a (No available applicable codec.), BlockwiseLinear 18
  • ts：日志原样的时间戳。 跨度 20032418 秒（约 232 天），要 25 位；10 万行里有 5613 处后一行比前一行早，不是单调的。分段直线反而多花了每段的参数，Bitpacked 以 312514 对 316419 胜出，每个值 25 位。
  • ts_sorted：同一批时间戳排好序。 这才是「单调递增的时间戳」，每 512 个值一条直线，差只要两三位，27785 字节，是 Bitpacked 的 9%。
  • ts_date：同样的值存成日期字段。 统计头里的 min 是一个巨大的数、gcd 是 10⁹：日期在快速字段里是 i64 纳秒（加 2⁶³ 映射成 u64），gcd 把 10⁹ 除掉，结果和存秒只差统计头的 9 个字节。ts_ms 同理，gcd 是 1000。
  • rand：均匀随机的 u64。 什么也压不了，64 位。rand1k 是 0 到 999 的随机数，10 位，Bitpacked 正好 125000 字节加 8 字节头。
  • seq：0 到 99999。 一条完美的直线，Linear 只要 16 字节，但它不在普通列的候选里，选中的是 BlockwiseLinear 的 1744 字节（196 段，每段只存直线参数，位宽是 0）。tb 是同样形状的 tie-breaker 列，Linear 参与竞争，32 字节。
  • seq[..511]：不到 512 个值，Linear 报不了价。
📝NOTE
冷知识：一段里跳得太猛，残差会被编成 64 位

Line::eval 把「斜率 × 位置」的结果先转成 i32 再加到截距上。compute_slope 在首尾差值太大时放弃，直接给斜率 0。0.26 时这个上限是 1 << 32：首尾差在 2³¹ 到 2³² 之间时，乘出来的线性部分超出 i32、符号翻转，直线偏得离谱，这一段的残差全部要 64 位。PR #2971 把上限改成 1 << 31，提交说明是「new limit prevent an overflow in eval which caused the residual to be 64b when a slop of zero would give a smaller one」，CHANGELOG 记为「Fix overflow in the blockwise linear codec on large jumps」，首次发布在 0.27.0。

用这个 PR 加的测试数据（前 256 个值从 2³² − 257 往上数，后 256 个从 0 往上数），同一段程序链接 tantivy 0.26.1（tantivy-columnar 0.7.0），先让两个候选一起比，再每种编码单独写一次：
both candidates: codec byte 0 (2058 bytes)
Bitpacked: 2058 bytes for 512 values
BlockwiseLinear: 4131 bytes for 512 values
链接 tantivy 0.27.0，每种编码单独写：
Bitpacked: 2058 bytes for 512 values
BlockwiseLinear: 2065 bytes for 512 values

4131 字节就是 512 × 8 再加段参数。估算器训练的是同一条直线，旧版本报价时就按 64 位算，两个候选一起比时选了编码 0（Bitpacked）。所以这个 bug 不会写错数据，影响的是体积：一列里只要有这样的段，分段直线的总报价就虚高，比较可能因此偏向 Bitpacked。这组数据修好以后 BlockwiseLinear 是 2065 字节，仍比 Bitpacked 多 7 字节。

字符串和字节：先建字典，再存序号

STRING | FAST 或 TEXT 加快速字段选项的文本，进快速字段前按 schema 里给快速字段指定的分词器切（默认 raw，整串一个词元，见 Schema 与字段）。每个词元交给这一列自己的 DictionaryBuilder：一张 SharedArenaHashMap，第一次见到的词按出现顺序分配一个临时号 UnorderedId。serialize 时把所有词按字节序排序，写成一个 VoidSSTable（只有键没有值的 sstable），同时得到「临时号 → 排序后的序号」的映射：

        let terms = self.build_sorted_terms(arena);
        // TODO Remove the allocation.
        let mut unordered_to_ord: Vec<OrderedId> = vec![OrderedId(0u32); terms.len()];
        let mut sstable_builder = sstable::VoidSSTable::writer(wrt);
        for (ord, (key, unordered_id)) in terms.into_iter().enumerate() {
            let ordered_id = OrderedId(ord as u32);
            sstable_builder.insert(key, &())?;
            unordered_to_ord[unordered_id.0 as usize] = ordered_id;
        }

serialize_bytes_or_str_column 把列里的临时号换成序号，剩下的就是一个普通的 u64 列，走上一节同样的编码选择。整列的字节是「字典 + 列 + 字典长度（u32）」。

序号按字节序排，所以比较两个文档的序号就是比较字符串，按字符串字段排序不用解出字符串。序号只在一个段里有意义：两个段里的 "WARN" 序号可能不同，合并时要重新映射。实验里的两个字符串列：

severity terms 2, blk terms 10
severity ord 0 = "INFO", ord 1 = "WARN"

severity 10 万篇里只有 2 篇是 WARN，序号几乎全是 0，BlockwiseLinear 的大多数段位宽为 0，727 字节；字典 47 字节。blk 有 10 个不同的词，序号要 4 位，Bitpacked 正好 50000 字节加头。

字典用的是 tantivy-sstable，不是倒排索引词典用的 FST（见 词典）。默认 feature columnar-zstd-compression 打开 sstable 的 zstd：一个 sstable 块超过 2048 字节时用级别 3 压一次，压完没变小就存原样（DeltaWriter::flush_block）。

读：从字段名到值

查询时用 segment_reader.fast_fields() 拿到 FastFieldReaders，再按类型取列：u64、i64、f64、date、str 等。它在列存目录里按「字段名 + 类型码」找到字节范围，读第一个字节决定编码，构造出 Column。之后 Column::first(doc) 或 values_for_doc(doc) 就是「列索引翻译 row id，再按 row id 解码」。.fast 通过 mmap 打开，列不用整列读进内存；排序、聚合这类逐文档读值的循环，每次取值是常数时间。

字段类型和取列用的类型要对上。按类型码找列，找不到就和字段不存在一样处理，u64 字段用 .i64("ts") 去取，报的是 SchemaError("Field `ts` is missing or is not configured as a fast field.")，.u64("ts") 则正常；不确定类型时可以用 u64_lenient，它返回列和实际类型。实验里绕过类型检查读原始字节用的是 dynamic_column_handle，它返回的 DynamicColumnHandle::file_slice() 带着 #[doc(hidden)]，不是给普通用户的接口。

tag 之后，main 上的 6bced0ba0（#3179）给列存加了一种不经字典的字符串列格式和 V3 版本号，提交说明写明「The columnar writer does not produce plain columns yet」。

❗IMPORTANT
动脑筋：一个 u64 快速字段，10 万篇文档依次写入 0、1、2……99999。.fast 里这一列的值部分是多少字节，用的哪种编码？提示：先想想每种编码报多少价，再看哪几种参加比较。答案在文末。

动脑筋答案

seq        U64 full        codec BlockwiseLinear min 0 gcd 1 amplitude/gcd 99999 rows 100000; total 1749 B (index 1, values 1744)
...
  seq        n=100000 Bitpacked 212509, Linear 16, BlockwiseLinear 1744

1744 字节，BlockwiseLinear。Bitpacked 要 17 位一个值，212509 字节；Linear 一条直线就描述完整列，残差全是 0，只要 16 字节，但普通列的候选只有 Bitpacked 和 BlockwiseLinear，它根本没参加比较。BlockwiseLinear 把 10 万个值切成 196 段，每段一条直线、位宽 0，存的全是段参数。同样一列值如果是 tie-breaker 列，Linear 会参与，实验里那一列只要 32 字节。

小结

  • .fast 是 tantivy-columnar 的格式：所有列首尾相接，最后一张 sstable 目录按「列名 + 类型码」记字节范围。
  • 一个文档有几个值不写在 schema 里，按段推断成 Full、Optional、Multivalued；后两者靠一个仿 roaring 的文档号集合（65536 一块，少于 5120 个值存列表，否则存位图）。
  • 数值列先统计 min、max、gcd，再让候选编码估算字节数、取最小。普通列只比 Bitpacked 和 BlockwiseLinear；Linear 只用于多值列的 start offsets 和 tie-breaker 列。
  • 实测：日志原样的时间戳 25 位 Bitpacked；排好序后 BlockwiseLinear 只要它的 9%；日期按纳秒存，gcd 把 10⁹ 除掉；随机 u64 64 位。
  • 字符串列每段一个排好序的 sstable 字典，列里存序号；序号的大小关系就是字符串的大小关系，但只在段内有效。
  • 0.27.0 修了分段直线在大跳变时残差变成 64 位的问题（#2971）；旧版本数据不会错，只是这样的段按 64 位计价，整列可能因此选了更大的编码。

💬 关联讨论

发起讨论
加载中...