您是如何在支持对长达数百MB的智能体追踪数据进行全文搜索与JSON过滤的同时，将中位数（P50）延迟控制在400ms以内的？本文深入解析了我们如何为SmithDB从头构建自定义倒排索引。https://t.co/QwSu0JqRg5 —

SmithDB中的全文搜索：为对象存储设计倒排索引

来源：https://www.langchain.com/blog/full-text-search-in-smithdb-designing-an-inverted-index-for-object-storage

概述

SmithDB支持对智能体追踪数据进行全文搜索和JSON过滤，中位数（P50）延迟为400 ms，尽管底层数据是存储在对象存储中的大型、深度嵌套的JSON文档。全文搜索并非新问题——Lucene已有二十年历史；Tantivy（https://github.com/quickwit-oss/tantivy）和Quickwit（https://quickwit.io/blog/quickwit-101）已经将搜索和索引推向了对象存储。然而，在将文本搜索构建到SmithDB中时，我们决定从第一性原理出发，因为为搜索工作负载索引智能体追踪数据面临着独特的挑战。

SmithDB需要不同的搜索方法

挑战1：智能体追踪数据的独特特征

每个LangSmith事件将inputs和outputs字段编码为其总字节数的绝大多数。inputs和outputs的负载大小超过1 MB很常见，其中一些甚至达到数百MB（未压缩）。这些内容列在量级上远超标识、时间戳和其他元数据列。此外，正如原始SmithDB博文（https://www.langchain.com/blog/introducing-smithdb#agents-present-a-new-data-problem）所述，与智能体追踪相关的负载大小随时间不断增长。这直接归因于LLM上下文窗口越来越大，以及智能体运行时间更长，导致LLM积累更多上下文。

这些特征颠覆了搜索索引的常规经济性。传统的日志引擎索引数十亿个小文档，因此索引相对于每个文档来说很小。我们索引的是数十亿个巨大文档，其中一个文档产生的索引数据可能比许多小日志行还要多。通常（https://aws.amazon.com/blogs/big-data/amazon-opensearch-service-101-how-many-shards-do-i-need/）日志的源文件与索引比约为1:1.25。然而，对于LangSmith中的智能体追踪，我们观察到平均比率接近1:1.9。由此产生三个后果：

• 没有索引的内容过滤速度极慢。 “查找工具输出中提到超时的运行“无法扫描候选范围内的每个负载，否则将扫描数GB数据才能返回三行。
• 词频遵循齐夫分布。 自然语言和JSON负载遵循幂律：少数词元（"agents"、"import"、"role"、"type"、通用键）几乎出现在每个文档中，而长尾词出现一次或两次。索引必须保持紧凑且可在同一文件内跨多个数量级的词频进行修剪。
• 多种查询模式很重要。 用户通过路径查询（“此运行是否有inputs.content.messages？”）、通过值查询（“…其中提到Alex”）以及通过自由文本查询（“…任何地方提到延迟回归”）。倒排索引阻止内容查询执行完整的负载扫描，并且必须吸收繁重、偏斜、半结构化的负载。

挑战2：对象存储

SmithDB将所有持久数据保存在对象存储中，因此计算相对无状态，系统通过添加节点进行扩展，无需管理本地磁盘。查询成本大致与**（向对象存储发出的请求数）×（每次请求读取的字节数）**成正比。

在对象存储上：

• 每次对象存储请求会带来几十到几百毫秒的延迟。
• 每次请求的吞吐量有限，因此在需要之前获取一个长的倒排列表或位置列表会主导查询时间。

SmithDB倒排索引的每个方面——从存储布局到查询执行——都基于这些约束进行设计。

SmithDB搜索查询形态

在深入探讨倒排索引的存储布局之前，我们先回顾索引需要回答的主要查询模式。SmithDB的查询面归结为三类谓词，它们在匹配对象和接受的模式语法上有所不同。

• 第一类是路径存在性（json_key）：文档是否包含键K？例如json_key(inputs, "author.name")询问哪些文档提到了author.name。路径存在性还支持键路径本身的LIKE：json_key(inputs, "author.%")或json_key(inputs, "%.user_id")是一等查询。模式可以出现在路径的任何位置（前缀、后缀、中缀）。
• 第二类是键值匹配（json_key_search）：键K的值是否匹配V？json_key_search(inputs, "author.name", "Jane")是标准形式。查询可以是单个词元或多个词元的短语（json_key_search(inputs, "title", "latency regression")），短语变体增加了相邻要求："latency regression"仅匹配这些单词连续出现的文档，而不是值中的任意位置。
• 第三类是全文搜索（search）：是否有任何索引值匹配Q？search(error, "timeout")直接搜索文本列；search(inputs, "latency regression")搜索每个JSON值，不论路径。

总结如下：

后续章节均引用此表：当我们说“仅路径查询”时指json_key，“键值”指json_key_search，“全文”指search。

倒排索引概述

倒排索引是支撑每个搜索库（从Lucene（https://lucene.apache.org/）到Tantivy（https://github.com/quickwit-oss/tantivy））的数据结构。它就像教材末尾的索引：查找一次术语，直接跳转到提及该术语的页面，而不是阅读每一页。SmithDB在此基础上进行构建，并针对存储在对象存储中的大型智能体跟踪负载专门设计了存储布局。

术语、倒排记录、位置

倒排索引结构基于三个概念：

• 术语是索引的基本单元：JSON路径、键值或文本词元。
• 倒排记录是包含该术语的文档ID的有序集合。
• 位置是该术语在文档中出现的位置，这使得短语搜索成为可能。

以五个索引文本的追踪为例：

doc 0: "langchain agents emit traces"
doc 1: "langsmith engine runs deep agents"
doc 2: "langchain deep agents workflow"
doc 3: "agents emit deep langsmith traces"
doc 4: "deep langsmith powers the engine"

索引为每个术语保留一个条目，指向提及它的文档：

每个术语是一个字典条目：查找值，读取其倒排列表，即可准确知道要获取哪些文档。像search("deep agents")这样的查询会求deep（[1, 2, 3, 4]）和agents（[0, 1, 2, 3]）的倒排列表交集，得到[1, 2, 3]，无需负载扫描。positions列记录每个文档中术语出现的标记偏移量，例如1:[0]表示文档1位置0。这使短语搜索成为可能：search("langsmith engine")匹配文档1，因为langsmith在偏移0，engine在偏移1（0+1==1），但不匹配文档4，因为powers和the位于它们之间（langsmith在1，engine在4）。

为何选择Vortex而非Tantivy

Tantivy（https://github.com/quickwit-oss/tantivy）是一个优秀的搜索索引库，也是Rust中Lucene风格搜索的明显参考点。我们最初询问是否能直接采用它。我们最终的设计深受Tantivy启发，但一些约束使其直接用于我们的用例并不理想：

1. 对象存储，而非本地磁盘。 Tantivy基于mmap构建；每个字节微秒可达，随机I/O几乎免费。我们使用的是对象存储，往返延迟约100 ms，布局和合并决定了查询延迟，而非CPU。
2. 嵌入列式引擎。 SmithDB查询通过Apache DataFusion（https://datafusion.apache.org/）和Vortex（https://vortex.dev/）运行。我们希望搜索能像其他谓词一样，通过相同的扫描管道下推，而不是运行具有自己的段模型和I/O假设的并行查询栈。
3. 文档ID与Vortex行对齐。 Tantivy的写入器按插入顺序分配自己的段本地文档ID，并在每次合并时重新编号。SmithDB需要索引直接指向相应Vortex数据文件（我们使用Vortex作为核心事件数据文件）中的行位置，因此文档ID就是行索引——没有转换表，查询时无需协调第二身份，并且遵循数据文件行顺序的合并无需重新映射。 此外，我们的压缩会重新映射行位置，这与Tantivy的索引合并配合不佳，我们将在本博文的第二部分详述。

我们开发SmithDB倒排索引的过程

Vortex快速入门

Vortex（https://vortex.dev/）是一种可扩展的列式文件格式，SmithDB用于对象存储。与Parquet等固定格式不同，Vortex允许可插拔编码和自定义文件布局，使我们能够针对工作负载定制压缩和I/O访问模式，而无需派生文件格式。每次读取使用统计信息**剪枝整个行组，将剩余行过滤为掩码，并投影查询实际需要的列。Vortex（https://docs.vortex.dev/developer-guide/internals/io）文件中的I/O单元是一个**段：**一个连续的物理字节范围。在对象存储上，一次往返花费大约100 ms，因此查询延迟的主要杠杆是最小化请求数。Vortex的I/O调度器将相邻的段读取合并为单个请求，将1 MB间隙内的读取合并为一次，最大窗口为16 MB，因此索引中的顺序访问模式映射到非常少的对象存储GET请求。

我们的（失败）首次尝试

第一个版本是教科书式倒排索引的近乎直接翻译。两列（term_key用于路径，term_value用于词元）使一种布局能满足所有三种查询形态：路径存在性读取term_key，键值搜索对两列求倒排列表交集，全文仅对term_value求交集。倒排记录存储为List单元格，位置存储为List>。我们依赖Vortex的默认值：对术语列使用FSST编码，对倒排记录和位置使用bitpacked编码，并使用分区存储布局以实现查询时剪枝。单是位置（短语搜索所需）就比其他所有列大一个数量级，因此我们将索引保存在一个独立于核心运行数据的文件中。这使得我们可以将索引构建和合并与核心写入路径解耦。Vortex的API基于行索引和掩码，因此将索引过滤委托给一个同级文件很自然。

但在大规模下出现了三个问题：

• 没有针对每个术语的编码控制。 Vortex为整个列选择编码，而不是每个术语，因此一个常见词元（agent、langchain）会强制整个块中的所有术语使用更大的位宽，导致bitpacking效率低下。列的其他部分因缓存行为变差和读取量增加而付出代价，而且我们无法选择性地对高频术语应用更激进的bitpacking。
• 固定大小的行组对术语偏斜不敏感。 我们按固定数量的术语批处理行组，这意味着一个高频术语可能将一个行组推至超过100 MB压缩大小，而另一个行组只有几MB。查询时这变成一个大型对象存储GET操作；合并时变成大型内存解码。
• 合并必须重塑位置。 合并两个段需要解码完整的位置List>，将内部列表重新排列成新的文档顺序，并重新计算每个外部偏移量。压缩时CPU时间和内存分配都会激增。对于一个70%以上字节是位置的索引，这是主要的压缩成本。

第二次尝试：V2倒排索引存储布局

我们的V2布局通过将组织单位从“每个行组N个术语”更改为字节预算行组，并通过自己控制每列的字节布局而不是直接依赖Vortex默认值，解决了V1的所有三个问题。本节其余部分将介绍新的组织单位、其中包含的内容，以及赢得字节预算的编码选择。

行组，以字节为单位

由于行组是剪枝和I/O的单位，我们使用固定的独立字节预算来确定行组大小，而不是固定的行数。

• **32 MB的倒排记录字节：**当查询读取某个行组的倒排记录时，限制了最坏情况下的对象存储GET大小。
• **64 MB的原始术语字符串字节：**限制了每个行组的原始字节数。

以字节而非术语数量来设定大小，解决了V1的第三个问题。术语偏斜使得术语数量成为I/O大小的糟糕代理，因为V1行组中的一个高频术语可能将其推到甚至超过500 MB（压缩后）。字节预算为每个行组提供了从对象存储读取的字节量或执行查询时的内存占用量的上界。通过对术语列采用分区存储布局，每个行组的最小/最大/计数信息允许查询计划器在触及FST之前跳过整个行组。对于针对特定前缀的路径查询，这是最大的节省：大多数行组根本不包含谓词范围内的任何内容。

一个行组内部

每个行组包含四列（term_key列有三列，因为它省略了位置）：

• term——一个二进制布局，其字节是一个FST（有限状态转移器）（https://burntsushi.net/transducers/），将每个术语映射到一个序号（该术语在此行组内的行索引）。我们对FST的使用受Tantivy启发。
• term_info——术语元数据：文档计数加上postings和positions的偏移量。
• postings——二进制大对象。每个术语的列表被分割成128个文档的块，使用bitpacked增量编码，尾部使用VInt处理剩余 < 128个文档。
• positions——二进制大对象，编码相同。仅出现在term_value上；路径存在性是一个文档级别的问题，因此term_key完全跳过此列。

一次查找就是一次字典遍历、一次偏移表读取和一次字节范围获取。FST将术语解析为序号。序号索引到term_info，后者给出postings中的偏移量和（对于短语查询）positions中的偏移量。查询直接读取这些字节范围。没有负载扫描，没有嵌套列表解码，并且由于每列是其自己的分块布局，非短语查询仅获取term+term_info+postings，从不打开positions列。

编码选择

我们使用FST作为术语词典。 我们将FST与明显的替代方案（Vortex的默认FSST字符串编码、前缀共享keep_add和普通zstd）在一个具有279万术语出现次数的代表性行组上进行了比较。获胜的形状取决于基数：