内部设计

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

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

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

简介：Redis String DMA

该模块利用的主要功能是 Redis Modules Strings Direct Memory Access （DMA）。

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

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

您只需调用RedisModule_StringTruncate将内存块的大小调整为所需的大小。然后你调用RedisModule_StringDMA直接访问该密钥中的内存。查看 https://github.com/RedisLabs/RedisModulesSDK/blob/master/FUNCTIONS.md#redismodule_stringdma

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

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

倒排索引编码

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

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

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

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

文档 ID 作为上一个文档的增量。
术语 frequency，由文档的排名考虑（见下文）。
标志，可用于仅筛选特定字段或其他用户定义的属性。
单词的所有文档偏移量的偏移量向量。

注意：

用户输入的文档 ID 将转换为内部增量文档 ID，从而允许 delta 编码高效，并允许按文档 ID 对倒排索引进行排序。

这允许将单个索引命中条目编码为低至 6 个字节。注意：这是最好的情况。根据单词在文档中出现的次数，这可能会高得多。

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

Skip index：索引 1/50 的索引偏移量表。这允许在与倒排索引相交时更快地查找，因为不需要遍历整个列表。
分数索引：在简单的单词搜索中，不需要遍历所有结果，只需遍历用户感兴趣的前 N 个结果即可。因此，将为每个术语存储前 20 个左右条目的辅助索引，并在适用时使用。

文档和结果排名

输入到引擎的每个文档都有每个单词的 TF-IDF 评分，以对结果进行排名。

作为优化，每个倒排索引命中都使用TF * Document_rank作为它的分数，并且在搜索过程中仅应用 IDF。这将来可能会改变。

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

搜索时，将保留请求的前 N 个结果的优先级队列，最终返回并按排名排序。

索引 ppec 和字段权重

使用FT.CREATE中，用户指定要编制索引的字段及其各自的权重。这可用于在排名结果中为某些文档字段（如标题）提供更大的权重。

例如：

FT.CREATE my_index title 10.0 body 1.0 url 2.0

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

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

查询执行引擎

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

生成索引命中的迭代器链接在一起。这些可以是：

读取迭代器，从倒排索引中逐个读取命中。例如hello.
Intersect Iterators，聚合两个或多个迭代器，仅生成它们的交点。例如hello AND world.
Exact Intersect Iterators - 同上，但仅当交集是精确短语时才会产生结果。例如hello NEAR world.
联合迭代器 - 组合两个或多个迭代器，并产生其点击的联合。例如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，这意味着您只能将搜索结果限制为给定值位于特定范围内的搜索结果。过滤是通过添加FILTERpredicates （支持多个）添加到您的查询中。例如：

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

filter 语法遵循 Redis 的 ZRANGEBYSCORE 语义，这意味着-inf和+inf受支持，并且前缀为数字表示独占范围。(

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

自动完成和模糊建议

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

Redis Stack 还允许模糊建议，这意味着即使用户的前缀中有拼写错误，您也可以获得对用户前缀的建议。这是使用 Levenshtein 自动机实现的，允许在词典中有效地搜索术语或前缀的最大 Levenshtein 距离内的所有术语。建议根据其原始分数和与用户键入的前缀的距离进行加权。出于性能原因，仅支持前缀与键入的前缀相距最多一个 Levenshtein 距离的建议。

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

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

假设所有输入FT.SUG*命令是有效的 UTF-8。
输入字符串转换为 32 位 Unicode，可选择规范化、大小写折叠和删除重音符号。如果转换失败，那是因为输入不是有效的 UTF-8。
32 位符文使用较低的 16 位符文修剪为 16 位符文。这些可用于插入、删除和搜索。
搜索的输出将转换回 UTF-8。