内部设计

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

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 主要用于模块中以对置索引进行编码，也用于其他辅助数据结构。

可以使用 DMA 字符串进行通用“缓冲器”实现，请在 buffer.c 中找到。

对置索引编码

对置索引 是所有搜索引擎的核心数据结构。其想法很简单。对于每个单词或搜索词，需要列出它所出现的全部文档。还会保留其他数据，比如词频和词语在文件中出现的偏移量。偏移量用于完全匹配类型的搜索或者对结果进行排名。

执行搜索时，可以遍历单个索引，也可以遍历两个或多个索引的交集或并集。Redis 对搜索引擎的经典实现是使用有序集作为对置索引。这样做可行，但是内存开销相当大，而且也不支持偏移量编码，如上所述。

Redis Stack 使用字符串 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. 读取迭代器，从倒排索引中逐个读取 hits。例如，hello。
  2. 相交迭代器，聚合两个或更多迭代器，只生成它们的相交点。例如，hello AND world。
  3. 精确相交迭代器 - 与上述相同，但仅当相交是准确的短语时才生成结果。例如，hello NEAR world。
  4. 并集迭代器 - 组合两个或更多个迭代器，生成它们的 hits 的并集。例如，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 距离不超过 1 的建议。

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

为了支持unicode模糊匹配，在前缀树中使用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 ↑