内部设计

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

Redis 开源版在 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 主要用于模块中，以编码倒排索引以及其他辅助数据结构。

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

倒排索引编码

一个 倒排索引 是所有搜索引擎核心的数据结构。其思想很简单。对于每个词或搜索词，都保存着它出现的文档列表。还保存其他数据，例如词频，以及词在文档中出现的位置偏移量。偏移量用于精确匹配类型搜索或结果排序。

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

Redis 开源版使用字符串 DMA（见上文）来高效地编码倒排索引。它结合了差分编码和变长整数编码来编码条目，最大限度地减少索引占用的空间，同时保持解压缩和遍历的高效性。

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

  • 文档 ID，表示与前一个文档的差值。
  • 词频，乘以文档排名（见下文）。
  • 标志，可用于仅过滤特定字段或其他用户定义的属性。
  • 该词在文档中所有偏移量的偏移向量。
注意
用户输入的文档 ID 会被转换为内部增量文档 ID，这使得差分编码高效，并让倒排索引按文档 ID 排序。

这使得单个索引命中条目最小只需 6 字节即可编码。注意：这是最佳情况。根据词在文档中出现的次数，占用的空间可能会大大增加。

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

  1. 跳跃索引：一个表，记录了索引条目中每 1/50 个条目的索引偏移量。这使得在倒排索引求交集时查找更快，因为无需遍历整个列表。
  2. 得分索引：在简单的单词搜索中，实际上不需要遍历所有结果，只需用户感兴趣的前 N 个结果。因此，对于每个词，都存储了一个辅助索引，记录了前 20 个左右的条目，并在适用时使用。

文档和结果排名

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

作为一项优化，每个倒排索引命中都将其分数编码为 TF * 文档排名，并且在搜索期间仅应用 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 个结果。

数值过滤器

可以在索引 schema 中将字段定义为 NUMERIC，这意味着您只能将搜索结果限制在给定值落在特定范围内的文档。过滤通过向查询添加 FILTER 谓词（支持多个）来完成。例如

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

过滤器语法遵循 Redis 的 ZRANGEBYSCORE 语义，这意味着支持 -inf 和 +inf，并且在数字前加上 ( 表示一个开区间。

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

自动补全和模糊建议

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

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

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

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

  1. 假设所有 FT.SUG* 命令的输入都是有效的 UTF-8。
  2. 输入字符串被转换为 32 位 Unicode，可选地进行规范化、大小写折叠以及去除重音。如果转换失败，则说明输入不是有效的 UTF-8。
  3. 32 位 rune 使用低 16 位被截断为 16 位 rune。这些可以用于插入、删除和搜索。
  4. 搜索的输出被转换回 UTF-8。
评价此页
返回顶部 ↑