# MoonSearch Tantivy 追赶计划 > 状态：已批准，M8 施工中 > 基线版本：MoonSearch v0.4.0 / M7 > 直接工程参考：Tantivy > 长期语义参考：Apache Lucene ## 1. 计划目的 MoonSearch 已完成全文搜索语义闭环：Schema、Analyzer、倒排索引、positions、 BM25、Query/Weight/Scorer、不可变 Segment、持久化、删除、Merge、Reader 快照、 高亮、CLI、Query-string 和 Browser/Wasm Demo 均已打通。 下一阶段不再以“增加可展示功能数量”为主，而以成熟嵌入式搜索内核的四项核心能力为主： 1. 可扩展的流式查询执行； 2. 紧凑、可按需读取的索引数据结构； 3. 可恢复、可并发约束的索引生命周期； 4. 面向真实应用的字段、排序和聚合能力。 Tantivy 是直接追赶目标，因为它与 MoonSearch 同属嵌入式搜索库，并采用严格 Schema、 不可变 Segment、Searcher 快照、BM25、Collector、Fast Fields 和后台 Merge 等相近边界。 Lucene 用于校验长期语义、Codec、生命周期和查询模型，但不要求 MoonSearch 复制其全部模块。 本文件是 M8–v1.0 的范围与验收来源。后续若调整范围，应修改本文件和 CHANGELOG/README， 不回写一次性项目申报书。 ## 2. 追赶原则 ### 2.1 追赶什么 - 追赶 Tantivy 的抽象边界、复杂度等级、可靠性保证和可测量工程质量； - 为每项优化保留可解释的参考实现或 oracle； - 保持 MoonBit 原生实现与 wasm、wasm-gc、js、native 四目标兼容； - 保持中文 DAG/HMM、Token Graph、Browser/Wasm 等 MoonSearch 差异化能力； - 通过公开 benchmark 记录吞吐、延迟、峰值内存和索引体积，而不是只比较功能名称。 ### 2.2 不追赶什么 - 不复制 Tantivy/Lucene 源码、API 命名或索引格式； - 不把 Elasticsearch/Solr/Quickwit 的分布式能力纳入 v1.0； - 不在 M8–M10 追逐向量、地理或集群功能； - 不为了 benchmark 数字破坏正确性、确定性排序或四目标可移植性； - 不把本机的一次测量声明为跨机器性能承诺。 ## 3. 当前基线与主要差距 | 领域 | v0.4.0 基线 | 目标状态 | | --- | --- | --- | | Term 定位 | `Term[]` 线性查找 | 可替换 `TermDictionary.seek`，先二分、后分块/按需读取 | | Postings | 完整 `Posting[]` 常驻内存 | `PostingCursor` 流式 `next/advance`，后续分块压缩 | | Boolean | `doc_count` 级匹配/分数数组 | 有序 DocSet 的交、并、排除，无稀疏查询全表扫描 | | Phrase | 多次线性搜索 postings | 多 cursor 对齐 docID，再验证 positions | | Top-K | 收集所有命中并全排序 | 容量 K 的有界堆，最终只排序 K 项 | | 统计 | 查询构建时重复扫描 live docs/postings | Searcher 快照级缓存和明确删除语义 | | Segment 格式 | v2 固定宽度整数、整体反序列化 | v3 delta/varint，兼容读取 v1/v2；后续按需读取 | | 生命周期 | 手工 commit/delete/full merge | 原子提交、锁、reload、MergePolicy、GC、故障恢复 | | 字段 | 主要为文本 | typed fields、Fast Fields、range/sort/facet/aggregation | ## 4. 总体版本路线 ```text M8 / v0.5.0 Scalable Execution Core ↓ M9 / v0.6.0 Durable Codec & Index Lifecycle ↓ M10 / v0.7.0 Typed Fields & Collectors ↓ M11 / v0.8.0 Advanced Performance ↓ M12 / v0.9.0 Query & Analysis Completeness ↓ v1.0.0 Stable Embedded Search Kernel ``` 每个里程碑必须满足：接口文档、正确性测试、四目标 check/test、格式兼容说明、benchmark 可构建和 README/CHANGELOG 同步。性能版本还必须给出可复现测量方法。 ## 5. M8 / v0.5.0 — Scalable Execution Core ### 5.1 目标 把当前“先生成完整命中数组、再处理”的执行路径改造成真正流式、按 docID 单调推进的 Query→Weight→Scorer→Collector 链，并建立可替换的词典/postings 边界。 ### 5.2 必须交付 #### A. Term Dictionary - 定义不泄漏底层数组布局的 term lookup 边界； - Segment 完成时按 `(field_id, UTF-8 term)` 建立确定性排序； - `postings_for`/`posting_cursor` 使用二分 seek，不再线性扫描全部 term； - Merge 和持久化 round-trip 保持相同排序不变量； - 重复 term、无序 term 和损坏格式必须被拒绝或规范化。 二分查找只是 M8 实现，不是永久格式承诺；上层 Query 不得依赖数组索引。 #### B. Posting Cursor - 提供当前 `doc_id`、`term_freq`、positions； - `next()`/`advance()` 只前进一个命中； - `seek(target)`/`advance(target)` 前进到 `doc_id >= target` 的第一个文档； - 文档 ID 严格递增；耗尽后保持耗尽；不得回退； - 第一版可包装内存 postings，后续 Codec/mmap 不改变上层执行接口。 #### C. 流式 Scorer - Term Scorer 直接包装 Posting Cursor，不预生成 `ScoredDoc[]`； - Boost Scorer 包装子 Scorer，不复制全部结果； - Boolean `Must` 使用多路交集，`Should` 使用有序并集，`MustNot` 使用排除游标； - Phrase 先对齐各 term 的 docID，再只对共同文档检查 positions； - Scorer 增加 `advance(target)`，所有实现遵守单调推进合同； - 稀疏查询不得分配 `O(segment.doc_count)` 的临时数组。 #### D. 有界 Top-K - Collector 在搜索过程中只保留至多 K 个 SearchHit； - 时间复杂度目标为 `O(matches × log K)`，额外结果内存为 `O(K)`； - 最终排序继续使用：score 降序、segment ordinal 升序、docID 升序； - `K <= 0`、跨 Segment、删除文档和相同 score 必须保持既有语义； - 白盒测试证明堆容量从不超过 K。 #### E. Searcher 统计缓存 - Searcher 构造时生成 snapshot 级 field document count、total field length； - term document frequency 在同一 Searcher 内按需缓存并复用； - 删除文档不计入 live-doc 统计； - 明确定义 Searcher 快照不可变，因此缓存无需随之后 commit 失效； - BM25 结果与 v0.4.0 语义 oracle 保持误差范围内一致。 #### F. Segment v3 基础压缩 - docID 使用递增 delta； - docID delta、term frequency、position count、position delta 使用无符号 varint； - container 继续包含 magic、version、payload length 和 checksum； - 编码器默认写 v3；解码器继续读取 v1、v2； - 拒绝溢出、过长 varint、非递增 docID/position、截断数据和 checksum 错误； - v3 仍可整体解码到内存，mmap/按需 block 读取留给 M9/M11。 #### G. 正确性与性能验证 - 使用参考数组算法作为 oracle，对 Term/Boost/Boolean/Phrase/Top-K 做结果等价测试； - 增加空结果、单 term、极稀疏、极稠密、多 Must/Should/MustNot、删除和多 Segment 测试； - 增加随机小索引 property-style 测试，比较新执行器与朴素集合实现； - benchmark 增加 10 万文档标准场景； - 提供 100 万文档手动规模场景，不进入普通 CI； - 记录查询吞吐/延迟、索引时间、编码体积和可获得时的峰值内存； - 普通 CI 只做 benchmark build-only，不以共享 CI 机器噪声做性能门禁。 ### 5.3 M8 非目标 - mmap、随机磁盘读取； - SIMD bitpacking； - skip blocks、Block-Max WAND； - 多线程索引和后台 Merge； - typed fields、range/facet； - 新 Query-string 语法。 ### 5.4 M8 验收标准（已于 2026-08-24 实现） - [x] Segment term 顺序稳定，term seek 不再线性扫描； - [x] Term/Boost/Boolean/Phrase Scorer 不预物化完整命中数组； - [x] 稀疏 Boolean 不创建 `doc_count` 级匹配数组； - [x] Top-K 堆容量不超过 K； - [x] live-doc BM25 与既有回归结果一致； - [x] v3 round-trip、v1/v2 兼容、损坏输入测试通过； - [x] 10 万文档 benchmark 可运行，100 万场景可手动启用； - [ ] wasm、wasm-gc、js、native 全部 check/test 通过；本轮按加速要求仅执行 Native 全量测试与全目标编译； - [x] README、README.mbt.md、CHANGELOG、接口文件和 benchmark 文档同步。 ## 6. M9 / v0.6.0 — Durable Codec & Index Lifecycle ### 6.1 目标 让已提交索引在崩溃、进程竞争、Reader 长期持有和后台文件回收下仍保持可恢复状态， 并把 Segment 从“整体内存对象”推进到可按需访问的 Codec/Directory 边界。 ### 6.2 必须交付 - Directory v2：临时文件、原子 rename、sync、delete、list、锁和能力检测； - Native `MmapDirectory` 或等价只读映射；不支持 mmap 的目标明确降级； - `prepare_commit`、`commit`、`rollback` 两阶段 Writer 生命周期； - 单 Writer 锁，第二 Writer 明确失败； - 新 manifest 只有在所有 Segment 数据持久化后才原子可见； - 崩溃恢复只能打开旧 generation 或新 generation，不能打开半提交状态； - `IndexReader.reload/open_if_changed`，旧 Searcher 继续持有旧快照； - `update_document(term, document)` 以 delete+add 表达原子更新语义； - MergePolicy、MergeScheduler、I/O 节流的第一版； - orphan/temp/不再被 Reader 引用文件的垃圾回收； - 故障注入覆盖每个 I/O 边界，并提供索引完整性检查工具。 ### 6.3 非目标 - 不承诺未 commit 文档不丢失；因此默认不引入 WAL； - 不实现跨机器复制、分片或副本； - 不要求 wasm 浏览器文件系统具备与 native 完全相同的锁/fsync 语义。 ### 6.4 验收标准（已于 2026-08-24 实现） - [x] 注入每个提交变更故障点后只能打开旧或新快照； - [x] 双 Writer 竞争安全失败，Native OS 锁在进程崩溃后自动释放； - [x] Reader reload 可见新 generation，旧 Searcher 结果不变； - [x] Merge/删除/GC 不破坏已物化的活跃 Reader 快照； - [x] CheckIndex 能发现截断、checksum、manifest 引用并报告孤儿/temp 文件。 ## 7. M10 / v0.7.0 — Typed Fields & Collectors ### 7.1 目标 从“文本相关性搜索库”扩展为能支撑真实筛选、排序、统计和 facet 的嵌入式搜索内核。 ### 7.2 必须交付 - Schema 字段：keyword、i64/u64/f64、bool、date、bytes； - 明确 indexed/stored/fast 的独立选项； - 单值和多值 Fast Fields，按 docID 高效读取； - exact/range/exists 查询和 filter 执行； - 按一个或多个 Fast Field 排序，定义缺失值和稳定 tie-break； - Count、TopDocs、MultiCollector； - terms facet、数值/date range facet； - min/max/sum/avg/histogram 聚合； - Query-string range/date/keyword 绑定； - Codec、Merge、删除和排序/聚合的格式与正确性测试。 ### 7.3 非目标 - JSON 动态字段、IP、地理和向量可以后续评估； - 不在本版本实现分布式 aggregation merge。 ### 7.4 完成状态（2026-08-24） - [x] 类型化 Schema/Document、独立 indexed/stored/fast 与单/多值约束； - [x] docID 寻址的 Fast Field 与 Segment v4，兼容读取 v1/v2/v3； - [x] exact/range/exists/filter、稳定多字段排序与缺失值策略； - [x] Count/TopDocs/MultiCollector、terms/range facet 与数值/date 聚合； - [x] Query-string keyword/date/range 绑定及 M10 聚焦正确性测试。 ## 8. M11 / v0.8.0 — Advanced Performance ### 8.1 目标 在 M8 cursor 和 M9 Codec/Directory 之上加入成熟搜索内核的跳跃、剪枝、并行和块式存储。 ### 8.2 必须交付 - postings/positions 分块编码与 skip metadata； - `advance(target)` 使用 skip blocks，而不是块内逐项扫描； - 有界 Top-K 提供竞争分数； - Block-Max WAND 或等价安全剪枝，结果必须与完整评分 oracle 一致； - stored fields 分块压缩与按需解压； - term dictionary 分块/前缀压缩，评估 FST 或等价结构； - 可配置索引内存预算与自动 flush； - native 多线程索引； - 可用目标上的 Segment 并行搜索； - Merge 并发、节流和 backpressure； - 100 万及更大语料的吞吐、P50/P95/P99、RSS、索引体积回归报告。 ### 8.3 验收标准 - [x] 所有剪枝路径与非剪枝 oracle 结果完全等价； - [x] 稀疏查询 `advance` 能跨 block； - [x] Top-K 不随总命中数线性增长内存； - [ ] 大语料 benchmark 报告同时包含速度、内存和体积，且可复现。 > 0.8.0 收口说明：当前内置 Segment/索引执行计划是确定性的可退化接口， > 在现有 MoonBit 后端报告实际并行度 1；原生线程池和本轮新的百万文档实测报告 > 未在截止前强行宣称完成，转入 v1.0 稳定化清单。 ## 9. M12 / v0.9.0 — Query & Analysis Completeness ### 9.1 查询 - Range、Prefix、Wildcard、Regex、Fuzzy； - Phrase slop、Phrase Prefix； - MatchAll、Exists、TermSet、DisjunctionMax； - explain API、可配置 BM25、field boost/function score； - Query-string 宽松模式、资源限制和结构化错误恢复。 ### 9.2 高亮与分析 - postings/term vectors 持久化 offsets 与 position length； - Query-tree-aware 高亮和 Query-string 高亮； - char filters、Unicode/ICU 风格归一化、同义词图、用户词典； - 生产中文词典/HMM 作为独立、可选、许可证清晰的资源包或下载流程； - Analyzer 配置和资源版本写入索引元数据； - 打开索引时检测 Analyzer 兼容性。 ### 9.3 非目标 - 不把大型语言资源直接塞进核心 Mooncakes 包； - 不承诺与 Lucene/Tantivy analyzer 输出逐 token 相同。 ### 9.4 收口状态 - [x] 多项、复合、slop/phrase-prefix 查询与可配置评分/Explain； - [x] Query-string wildcard/regex/fuzzy/slop、宽松恢复和资源上限； - [x] Segment v5 offsets/position length 与 Query-string-aware 高亮； - [x] char filter 偏移校正、兼容归一化、同义词图和资源版本校验； - [ ] 完整 ICU Unicode 归一化及可再分发的生产级中文词典/HMM 包。 大型语言资源继续由应用注入；核心仅提供许可证/版本指纹描述，不捆绑来源不明或 体积过大的资源。 ## 10. v1.0.0 — Stable Embedded Search Kernel ### 10.1 稳定承诺 - 公开 API 分层并完成稳定性审计； - 索引格式有明确版本、兼容矩阵、迁移/重建工具； - 1.x 内明确读兼容窗口和废弃流程； - 错误类型、资源限制和线程/目标支持矩阵文档化； - fuzz、property、并发、故障注入、损坏索引和长时间 soak 测试； - benchmark 历史和回归判定规则； - 完整教程、API 文档、生产部署边界和升级指南； - Mooncakes、GitHub Release、在线 Demo 和示例版本一致。 ### 10.2 v1.0 不代表 - 不代表 Tantivy/Lucene 全功能兼容； - 不代表索引格式互通； - 不代表分布式搜索平台； - 不代表所有 MoonBit 目标拥有完全相同的 OS 并发和文件系统能力。 ## 11. 跨版本工程规则 ### 11.1 正确性优先 - 每项优化必须保留朴素 oracle 或可独立验证的模型； - 算法替换先做结果等价，再做 benchmark； - score 浮点比较使用明确误差，命中集合和 tie-break 必须确定； - 删除、多 Segment、空字段、多值字段和 UTF-8 必须出现在回归测试中。 ### 11.2 格式演进 - 每次格式升级只增加一个清晰版本； - 编码器只写最新版本，解码器在兼容窗口内读取旧版本； - 不静默改变旧版本语义； - checksum、长度和计数在分配大数组前校验； - 格式不兼容必须在 CHANGELOG 标明是否需要重建索引。 ### 11.3 性能证据 - benchmark 固定 fixture 版本、工具链、target、release 模式和机器信息； - 同时报告速度、峰值内存和索引体积； - CI 运行小型正确性测试和 benchmark build-only； - 重型 benchmark 由手动 workflow 或本地空闲机器执行； - 不提交下载语料和机器特定输出，必要时上传 workflow artifact。 ### 11.4 发布边界 - 完成里程碑实现不自动授权 commit、push、tag、Release、部署或 Mooncakes publish； - 发布前必须同步 README、README.mbt.md、CHANGELOG 和版本号； - 项目申报书保持冻结，只作为已批准功能范围的历史材料。 ## 12. M8 实施顺序 1. 写测试：term 排序/seek、cursor 合同、Boolean/Phrase 等价、Top-K 容量、v3 codec； 2. Segment finish 排序并引入 term seek/cursor； 3. 扩展 Scorer `advance(target)`，实现流式 Term 与 Boost； 4. 实现 Conjunction、Disjunction、Exclude 和 Phrase 对齐； 5. 将 Collector 替换为确定性有界堆； 6. 建立 Searcher snapshot 统计缓存； 7. 编写 varint，升级 Segment v3 并保持 v1/v2 读取； 8. 增加 10 万/100 万 benchmark 场景与文档； 9. 运行 `moon fmt`、`moon info`、四目标 check/test 和 benchmark build-only； 10. 同步 README/CHANGELOG，记录实测结果与剩余边界。 ## 13. 参考资料 - Tantivy repository: - Tantivy architecture: - Tantivy query API: - Tantivy collector API: - Tantivy IndexWriter: - Apache Lucene index API: - Apache Lucene codecs: