内部设计

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

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”实现，使用DMA字符串可以在buffer.c中找到。当容量需要增长时，它会自动调整其用作原始内存的Redis字符串的大小。

倒排索引编码

一个倒排索引是所有搜索引擎核心的数据结构。其理念很简单。对于每个单词或搜索词，都会保留一个包含该词的所有文档的列表。同时还会保留其他数据，例如词频以及该词在文档中出现的位置偏移量。偏移量用于精确匹配类型的搜索或结果的排名。

当执行搜索时，要么遍历单个索引，要么遍历两个或多个索引的交集或并集。经典的Redis搜索引擎实现使用有序集合作为倒排索引。这种方法有效，但会带来显著的内存开销，并且如上所述，它也不允许编码偏移量。

Redis Stack 使用字符串 DMA（见上文）来高效编码倒排索引。它结合了delta encoding和varint encoding来编码条目，最小化索引使用的空间，同时保持解压缩和遍历的高效性。

对于每个命中（文档/词条），以下项目被编码：

  • 文档ID作为与前一个文档的增量。
  • 术语频率，由文档的排名加权（见下文）。
  • 标志，可用于仅过滤特定字段或其他用户定义的属性。
  • 单词的所有文档偏移量的偏移向量。
注意：
用户输入的文档ID会被转换为内部递增的文档ID，这使得增量编码更加高效，并允许倒排索引按文档ID排序。

这允许单个索引命中条目以最少6字节进行编码。注意：这是最佳情况。根据单词在文档中出现的次数，这个值可能会更高。

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

  1. 跳过索引：一个包含索引条目1/50偏移量的表。这允许在交叉倒排索引时更快地进行查找，因为不需要遍历整个列表。
  2. 评分索引：在简单的单字搜索中，实际上不需要遍历所有结果，只需遍历用户感兴趣的前N个结果。因此，为每个术语存储了一个包含前20个左右条目的辅助索引，这些索引在适用时使用。

文档和结果排名

输入到引擎中的每个文档都有一个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键中的索引规范，并且只有出现在此规范中的字段才会被索引。

查询执行引擎

查询执行中使用了一种基于链式迭代器的方法，这在概念上类似于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版本发布以来，该实现使用了一个多级范围树，在多个分辨率下保存范围，以实现高效的范围扫描。如果数字范围相对于过滤字段的整个跨度较小，添加数字过滤器可以加速慢查询。例如，在多年的数据中专注于几天的日期过滤器可以将繁重的查询速度提高一个数量级。

自动完成和模糊建议

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

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

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

为了支持Unicode模糊匹配，trie内部使用16位符文而不是字节。如果文本是纯ASCII的，这会增加内存消耗，但允许以相同的支持水平完成所有现代语言的匹配。这是通过以下方式实现的：

  1. 假设所有输入到FT.SUG*命令的内容都是有效的UTF-8编码。
  2. 输入字符串被转换为32位Unicode，可选地在转换过程中进行规范化、大小写折叠和去除重音符号。如果转换失败，那是因为输入不是有效的UTF-8。
  3. 32位的符文被修剪为16位的符文，使用较低的16位。这些可以用于插入、删除和搜索。
  4. 搜索的输出被转换回UTF-8。
RATE THIS PAGE
Back to top ↑