内部设计

有关设计选择和实现的详细信息

内部设计

Redis Stack 在 Redis 之上实现了反向索引，但与之前的 Redis 反向索引实现不同，它使用自定义数据编码，该编码允许更省内存和 CPU 的搜索以及更高级的搜索功能。

本文档详细介绍了一些设计选择以及如何实现这些功能。

简介：Redis 字符串 DMA

此模块利用的主要功能是 Redis 模块字符串直接内存访问 (DMA)。

此功能简单，但非常强大。它允许模块在 Redis 字符串键上分配数据，然后获取分配给键的数据的直接指针，而无需复制或序列化。

这允许非常快速地访问大量内存。从模块的角度来看，字符串值简单地显示为 char *，这意味着它可以转换为任何数据结构。

您只需调用 RedisModule_StringTruncate 将内存块调整为所需的大小。然后，您调用 RedisModule_StringDMA 以直接访问该键中的内存。请参阅 https://github.com/RedisLabs/RedisModulesSDK/blob/master/FUNCTIONS.md#redismodule_stringdma

此 API 主要在模块中用于对倒排索引进行编码，也用于其他辅助数据结构。

可以在 buffer.c 中找到使用 DMA 字符串的通用“缓冲区”实现。当容量需要增长时，它会自动调整其用作原始内存的 Redis 字符串的大小。

倒排索引编码

倒排索引 是所有搜索引擎的核心数据结构。这个想法很简单。对于每个单词或搜索词，都会保留它出现的所有文档的列表。还会保留其他数据，例如词频以及术语在文档中出现的偏移量。偏移量用于完全匹配类型搜索或对结果进行排名。

执行搜索时，要么遍历单个索引，要么遍历两个或更多个索引的交集或并集。搜索引擎的经典 Redis 实现使用有序集合作为倒排索引。这样做可行，但内存开销很大，而且如上所述，它也不允许对偏移量进行编码。

Redis Stack 使用字符串 DMA（见上文）来有效地对倒排索引进行编码。它结合了增量编码和可变长整数编码来对条目进行编码，最大程度地减少了用于索引的空间，同时保持解压缩和遍历的效率。

对于每个命中（文档/单词条目），将对以下项目进行编码

  • 文档 ID，作为与前一个文档的增量。
  • 词频，由文档的排名决定（见下文）。
  • 标志，可用于仅过滤特定字段或其他用户定义的属性。
  • 单词的所有文档偏移量的偏移量向量。
注意

用户输入的文档 ID 会转换为内部递增文档 ID，这样可以提高增量编码的效率，并按文档 ID 对倒排索引进行排序。

这样一来，只需 6 个字节即可对单个索引命中条目进行编码。注意：这是最佳情况。根据文档中单词出现的次数，这个数字可能会高得多。

为了优化搜索，在不同的 DMA 字符串键中保留了两个额外的辅助数据结构

  1. 跳过索引：1/50 索引条目的索引偏移量表。在交叉倒排索引时，这可以加快查找速度，因为无需遍历整个列表。
  2. 评分索引：在简单的单字搜索中，无需遍历所有结果，只需遍历用户感兴趣的前 N 个结果即可。因此，为每个术语存储了一个前 20 个条目的辅助索引，并在适用时使用。

文档和结果排名

使用 FT.ADD 输入到引擎的每个文档都具有用户分配的 0.0 到 1.0 之间的排名。这与 TF-IDF 对每个单词的评分结合使用，对结果进行排名。

作为优化，每个倒排索引命中都使用 TF * Document_rank 作为其评分进行编码，并且仅在搜索期间应用 IDF。这可能会在未来发生变化。

最重要的是，在交叉查询的情况下，查询中术语之间的最小距离会被考虑在排名中。术语之间的距离越近，结果就越好。

在搜索时，会维护请求的前 N 个结果的优先级队列，最终按排名返回这些结果。

索引规格和字段权重

在使用 FT.CREATE 创建“索引”时，用户指定要编入索引的字段及其各自的权重。这可用于为某些文档字段（如标题）在排名结果中赋予更高的权重。

例如

FT.CREATE my_index title 10.0 body 1.0 url 2.0

将在名为 title、body 和 url 的字段上创建一个索引，其评分分别为 10、1 和 2。

在对文档编制索引时，权重取自存储在特殊 Redis 键中的已保存索引规范，并且仅编制此规范中出现的字段的索引。

文档数据存储

在对文档编制索引时，不必保存文档数据。为 FT.ADD 指定 NOSAVE 将导致对文档编制索引，但不保存文档。

如果用户确实保存了文档，则会在 Redis 中创建一个 HASH 键，其中包含所有字段（包括未编入索引的字段），并且在搜索时，对每个检索到的文档执行 HGETALL 查询以检索其所有数据。

TODO：文档片段应在未来实现。

查询执行引擎

查询执行使用基于链式迭代器的方法，在概念上类似于 Python 生成器。

产生索引命中结果的迭代器链接在一起。它们可以是

  1. 读取迭代器，从倒排索引中逐个读取命中结果。例如，hello。
  2. 相交迭代器，聚合两个或更多迭代器，仅产生它们的交集点。例如，hello AND world。
  3. 精确相交迭代器 - 与上述相同，但仅在交集是确切短语时产生结果。例如，hello NEAR world。
  4. 并集迭代器 - 组合两个或更多迭代器，并产生它们的命中结果的并集。例如，hello OR world。

这些基于查询组合为执行计划，该计划将被惰性求值。例如

hello ==> read("hello")

hello world ==> intersect( read("hello"), read("world") )

"hello world" ==> exact_intersect( read("hello"), read("world") )

"hello world" foo ==> intersect(
                            exact_intersect(
                                read("hello"),
                                read("world")
                            ),
                            read("foo")
                      )

所有这些迭代器都是惰性求值的，逐项进行，具有恒定内存开销。

根迭代器由查询执行引擎读取，并针对其中包含的 N 个最高结果进行筛选。

数字筛选器

可以在索引架构中将字段定义为 NUMERIC，这意味着你将能够将搜索结果限制为仅包含给定值落在特定范围内的那些结果。通过向查询添加 FILTER 谓词（支持多个）来完成筛选。例如

FT.SEARCH products "hd tv" FILTER price 100 (300

筛选器语法遵循 Redis 的 ZRANGEBYSCORE 语义，这意味着支持 -inf 和 +inf，并且在数字前面加上 ( 表示一个排他范围。

从 0.6 版本开始，该实现使用多级范围树，以多种分辨率保存范围，从而实现高效的范围扫描。如果数字范围相对于筛选字段的整个跨度较小，则添加数字筛选器可以加速慢查询。例如，针对几年数据中的几天进行的日期筛选可以将繁重的查询速度提高一个数量级。

自动完成和模糊建议

搜索和查询的另一个重要功能是自动完成或建议。它允许你创建加权术语词典，然后针对给定的用户前缀查询它们以获取完成建议。例如，如果你将术语“液晶电视”放入词典中，则发送前缀“lc”将返回它作为结果。该词典被建模为具有权重的压缩前缀树（前缀树），它被遍历以找到前缀的顶部后缀。

Redis Stack 还允许模糊建议，这意味着即使用户在前缀中输入了错别字，你也可以获得用户前缀的建议。这是使用 Levenshtein 自动机实现的，它允许在词典中高效搜索所有术语或前缀的最大 Levenshtein 距离内的术语。建议的权重基于它们的原始分数和它们与用户键入的前缀的距离。出于性能原因，仅支持前缀距离键入前缀的 Levenshtein 距离不超过一个的建议。

但是，由于搜索模糊前缀（尤其是非常短的前缀）将遍历海量的建议（事实上，任何单个字母的模糊建议都将遍历整个词典！），因此建议您谨慎使用此功能，并且仅在考虑其带来的性能损失时使用。由于 Redis 是单线程的，因此在任何时间段内阻塞它意味着在该时间段内无法处理其他查询。

为了支持 unicode 模糊匹配，在 trie 中使用 16 位 rune 而不是字节。如果文本是纯 ASCII，这会增加内存消耗，但允许以相同级别的支持完成所有现代语言。这以以下方式完成

  1. 假设所有输入到 FT.SUG* 命令都是有效的 UTF-8。
  2. 输入字符串被转换为 32 位 Unicode，可以选择在过程中进行规范化、折叠大小写和去除重音符号。如果转换失败，则是因为输入不是有效的 UTF-8。
  3. 使用低 16 位将 32 位 rune 修剪为 16 位 rune。这些可用于插入、删除和搜索。
  4. 搜索的输出被转换回 UTF-8。
对本页评分