技术概述

Redis Stack 搜索和查询功能的技术概述

摘要

RediSearch 是一个强大的文本搜索和二级索引引擎，它作为 Redis 模块构建在 Redis 之上。

与其他 Redis 搜索库不同，它不使用 Redis 的内部数据结构，例如排序集。它使用自己的高度优化的数据结构和算法，允许高级搜索功能、高性能和低内存占用。它可以执行简单的文本搜索以及复杂的结构化查询，根据数字属性和地理距离进行过滤。

RediSearch 支持连续索引，不会降低性能，并保持查询和索引的并发负载。这使其成为搜索频繁更新的数据库的理想选择，无需批量索引和服务中断。

RediSearch 的企业版支持跨多个服务器扩展搜索引擎，使其能够轻松扩展到数百台服务器上的数十亿个文档。

所有这些操作都充分利用了 Redis 的强大架构和基础设施。利用 Redis 的协议、复制、持久化和集群，RediSearch 提供了一个强大且易于管理和维护的搜索和索引引擎，可以作为独立数据库使用，也可以增强现有的 Redis 数据库，使其具备强大的高级索引功能。

主要功能

  • 对文档中多个字段进行全文索引，包括
    • 精确短语匹配。
    • 多种语言的词干提取。
    • 支持中文分词。
    • 前缀查询。
    • 可选、否定和联合查询。
  • 对数十亿个文档进行分布式搜索。
  • 数值属性索引。
  • 地理索引和半径过滤器。
  • 增量索引，不会降低性能。
  • 用于高级查询的结构化查询语言
    • 并集和交集
    • 可选和否定查询
    • 标签过滤
    • 前缀匹配
  • 强大的自动完成引擎，支持模糊匹配。
  • 多种评分模型，并按值排序。
  • 并发、低延迟的文档插入和更新。
  • 并发搜索，允许长时间运行的查询，不会阻塞 Redis。
  • 扩展机制，允许自定义评分模型和查询扩展。
  • 支持对 Redis 数据库中的现有 Hash 对象进行索引。

索引文档

Redis Stack 需要知道如何索引文档才能有效搜索。一个文档可能有多个字段，每个字段都有自己的权重。例如，标题通常比文本本身更重要。引擎还可以使用数值或地理字段进行过滤。因此，第一步是创建索引定义，它告诉 Redis Stack 如何处理要添加的文档。例如，要定义一个产品的索引，索引其标题、描述、品牌和价格字段，索引创建将如下所示：

FT.CREATE idx PREFIX 1 doc: SCHEMA 
    title TEXT WEIGHT 5
    description TEXT 
    brand TEXT 
    PRICE numeric

当一个文档被添加到这个索引中时，就像下面的例子一样，文档的每个字段都被分解成它的词语（分词），并通过标记索引中每个词语的索引来进行索引。这样，产品就会立即添加到索引中，并且可以在将来的搜索中找到。

HSET doc:1 
    title "Acme 42 inch LCD TV"
    description "42 inch brand new Full-HD tv with smart tv capabilities"
    brand "Acme"
    price 300

这告诉 Redis Stack 获取文档，将每个字段分解成它的词语（分词），并通过标记索引中每个词语的索引来进行索引，这些索引包含在这个文档中。因此，产品会立即添加到索引中，并且可以在将来的搜索中找到。

搜索

现在产品已经添加到我们的索引中，搜索非常简单

FT.SEARCH idx "full hd tv"

这将告诉 Redis Stack 对每个词语的文档列表进行交集，并返回包含这三个词语的所有文档。当然，可以执行更复杂的查询，查询语言的完整语法将在下面详细介绍。

数据结构

Redis Stack 使用它自己的自定义数据结构，并且只使用 Redis 的原生结构来存储实际的文档内容（使用 Hash 对象）。

使用专门的数据结构可以加快搜索速度，并更有效地利用内存存储索引记录，利用像 delta 编码这样的压缩技术。

以下是 Redis Stack 在幕后使用的各种数据结构

索引和文档元数据

对于每个搜索索引，都存在一个根数据结构，其中包含模式、统计信息等，但最重要的是，它包含关于每个索引文档的简洁元数据。

在内部，在索引中，Redis Stack 使用增量式 32 位文档 ID 的 delta 编码列表。这意味着用户提供的文档键或 ID 需要在索引时替换为内部 ID，并在搜索时恢复为原始 ID。

为此，Redis Stack 保存了两个表，以两种方式映射两种 ID（一个表使用简洁的 Trie，另一个只是一个数组，其中内部文档 ID 是数组索引）。除此之外，对于每个文档，它的用户给定的假定分数都会被保存，以及一些状态位和用户附加到文档的任何可选有效负载。

访问文档元数据表的速度比访问实际保存文档的 hash 对象要快一个数量级，因此需要访问文档元数据的评分函数可以足够快地运行。

倒排索引

对于出现在至少一个文档中的每个词语，都会保留一个倒排索引，它基本上是所有包含这个词语的文档的列表。该列表使用 delta 编码压缩，文档 ID 始终是递增的。

例如，当用户索引文档 "foo"、"bar" 和 "baz" 时，它们会被分配递增的 ID，例如 1025, 1045, 1080。当将它们编码到索引中时，只编码第一个 ID，然后是每个条目与前一个条目之间的增量，例如 1025, 20, 35。

使用可变宽度编码，一个字节用于表示 255 以内的数字，两个字节用于表示 256 到 16,383 之间的数字，依此类推。这可以将索引压缩高达 75%。

除了 ID 之外，还保存了每个词语在每个文档中的频率、表示词语出现在文档中的哪些字段的位掩码以及词语出现在文档中的位置列表。

默认搜索记录的结构如下。通常，所有条目都是一个字节长

+----------------+------------+------------------+-------------+------------------------+
|  docId_delta   |  frequency | field mask       | offsets len | offset, offset, ....   |
|  (1-4 bytes)   | (1-2 bytes)| (1-16 bytes)     |  (1-2 bytes)| (1-2 bytes per offset) |
+----------------+------------+------------------+-------------+------------------------+

可以选择不保存这些属性中的任何一个，除了 ID 之外，这会降低引擎可用的功能。

数值索引

数值属性被索引在一个特殊的数据结构中，该结构允许以高效的方式按数值范围进行过滤。可以将数值视为类似于倒排索引的词语。例如，所有价格为 100 美元的商品都在一个特定的列表中，该列表与查询的其余部分进行交集。有关更多信息，请参阅 查询执行引擎。

但是，为了按价格范围进行过滤，您将不得不将查询与该范围内所有不同的价格进行交集，或者执行并集查询。如果该范围包含许多值，则这会变得非常低效。

为了避免这种情况，数值条目被分组，相近的值放在一起，在一个范围节点中。这些节点存储在二叉范围树中，该树允许引擎选择相关的节点并将它们并集在一起。范围节点中的每个条目包含一个文档 ID 和该文档的实际数值。为了进一步优化，该树使用自适应算法，尝试将尽可能多的节点合并到同一个范围节点中。

标签索引

标签索引类似于全文索引，但使用更简单的分词和索引编码。这些字段中的值不能通过一般的无字段搜索访问，只能使用特殊的语法访问。

标签字段和全文字段之间的主要区别在于

  1. 分词更简单。用户可以确定多个标签的分隔符（默认为逗号）。空格修剪只在标签的末尾进行。因此，标签可以包含空格、标点符号、重音符号等。唯一执行的两个转换是转换为小写（目前仅限拉丁语系）和空格修剪。

  2. 标签无法通过一般的全文搜索找到。如果一个文档有一个名为 tags 的字段，其值为 foo 和 bar，在没有特殊标签修饰符（见下文）的情况下搜索 foo 或 bar 不会返回该文档。

  3. 索引更简单，压缩更多。索引中只存储文档 ID，通常每个索引条目只有 1-2 个字节。

地理索引

地理索引利用了 Redis 自己的地理索引功能。在查询时，查询的地理部分（半径过滤器）被发送到 Redis，只返回在该半径内的文档的 ID。经度和纬度应该以字符串 lon,lat 的形式传递。例如，1.23,4.56。

自动完成

自动完成引擎（有关更完整的描述，请参见下文）使用简洁的 Trie 或前缀树来编码词语并按前缀搜索它们。

查询语言

支持简单的语法，用于复杂的查询，这些查询可以组合在一起，以表达复杂的过滤和匹配规则。查询是 FT.SEARCH 请求中的文本字符串，它使用复杂的查询处理器进行解析。

  • 多词短语是词语列表，例如 foo bar baz，表示词语的交集（逻辑 AND）。
  • 精确短语用引号括起来，例如 "hello world"。
  • OR 并集（例如 word1 OR word2）使用管道（|）字符表示。例如，hello|hallo|shalom|hola。
  • NOT 否定（例如 word1 NOT word2）表达式或子查询使用减号（-）字符。例如，hello -world。
  • 前缀匹配（所有以前缀开头的词语）使用 * 后跟 2 个字母或更长的前缀表示。
  • 使用语法 @field:hello world 选择特定字段。
  • 使用语法 @field:[{min} {max}] 对数值字段进行数值范围匹配。
  • 使用语法 @field:[{lon} {lat} {radius} {m|km|mi|ft}] 对地理字段进行地理半径匹配。
  • 使用语法 @field:{tag | tag | ...} 对标签字段进行过滤。请参阅 有关标签字段的完整文档。
  • 可选词语或子句：foo ~bar 表示 bar 是可选的，但包含 bar 的文档排名更高。

复杂查询示例

表达式可以组合在一起以表达复杂的规则。例如，给定一个产品的数据库，其中每个实体都有 title、brand、tags 和 price 字段，表达一个通用搜索将是

lcd tv

这将返回包含这些词语的文档，这些词语位于任何字段中。将搜索限制到特定字段（本例中仅限标题）的表达式为

@title:(lcd tv)

数值过滤器可以组合在一起，以在给定价格范围内过滤价格

    @title:(lcd tv) 
    @price:[100 500.2]

多个文本字段可以在不同的查询子句中访问。例如，要选择多个品牌的商品

    @title:(lcd tv)
    @brand:(sony | samsung | lg)
    @price:[100 500.2]

标签字段可以用来索引多词属性，而无需实际的全文分词

    @title:(lcd tv) 
    @brand:(sony | samsung | lg) 
    @tags:{42 inch | smart tv} 
    @price:[100 500.2]

还可以添加否定子句来过滤掉等离子电视和 CRT 电视

    @title:(lcd tv) 
    @brand:(sony | samsung | lg) 
    @tags:{42 inch | smart tv} 
    @price:[100 500.2]

    -@tags:{plasma | crt}

评分模型

Redis Stack 附带了一些非常基本的评分函数来评估文档的相关性。它们都基于文档分数和词语频率。这与使用可排序字段无关（见下文）。评分函数通过在搜索请求中添加 SCORER {scorer_name} 参数来指定。

如果您更喜欢自定义评分函数，可以使用 扩展 API 添加更多函数。

以下是 Redis Stack 中提供的预捆绑评分函数

  • TFIDF（默认）

    基本的 TF-IDF 评分，其中考虑了文档分数和邻近度提升。

  • TFIDF.DOCNORM

  • 与默认的 TFIDF 评分器相同，但有一个重要的区别

  • BM25

    对基本 TF-IDF 评分器的一种变体。有关更多信息，请参阅 维基百科文章。

  • DISMAX

    一个简单的评分器，它将匹配词语的频率加起来。在并集子句的情况下，它将给出这些匹配的最大值。

  • DOCSCORE

    一个评分函数，它只返回文档的假定分数，而不对其进行任何计算。由于文档分数可以更新，因此如果您想使用外部分数，而无需进一步操作，这将非常有用。

可排序字段

即使排序字段没有被查询使用，也可以绕过评分函数机制，直接根据不同文档属性（字段）的值对搜索结果进行排序。例如，您可以搜索名字，然后按姓氏排序。

在使用 FT.CREATE 创建索引时，您可以将 TEXT、TAG、NUMERIC 和 GEO 属性声明为 SORTABLE。当属性可排序时，您可以稍后决定按其值对结果进行排序，延迟相对较低。当属性不可排序时，它仍然可以按其值排序，但可能会增加延迟。例如，以下模式

FT.CREATE users SCHEMA first_name TEXT last_name TEXT SORTABLE age NUMERIC SORTABLE

将允许以下查询

FT.SEARCH users "john lennon" SORTBY age DESC

结果高亮和摘要

Redis Stack 使用高级算法进行高亮和摘要，这使得只有文档的相关部分才会出现在搜索查询的响应中。此功能使用户能够立即了解文档与其搜索条件的相关性，通常会以粗体突出显示匹配的词语。语法如下

FT.SEARCH ...
    SUMMARIZE [FIELDS {num} {field}] [FRAGS {numFrags}] [LEN {fragLen}] [SEPARATOR {separator}]
    HIGHLIGHT [FIELDS {num} {field}] [TAGS {openTag} {closeTag}]

摘要会将文本片段化成更小的片段。每个片段将包含找到的词语和一些额外的上下文。

高亮将使用用户定义的标签突出显示找到的词语及其变体。这可以用来使用标记语言以不同的字体显示匹配的文本，或者以其他方式使文本显示不同。

自动完成

Redis Stack 的另一个重要功能是其自动完成引擎。这使用户能够创建加权词语字典，然后查询这些字典以获取对给定用户前缀的完成建议。完成可以有有效负载，这是用户提供的可以用于显示的数据。例如，完成用户姓名，可以添加有关用户的额外元数据以供显示。

例如，如果用户开始在字典中输入词语“lcd tv”，发送前缀“lc”将返回完整的词语作为结果。字典被建模为一个带有权重的紧凑 trie（前缀树），它被遍历以查找前缀的顶级后缀。

Redis Stack 还允许模糊建议，这意味着即使用户在其前缀中输入了错误，您也可以获取对前缀的建议。这是通过使用 Levenshtein 自动机实现的，允许有效地搜索字典以查找与词语或前缀的最大 Levenshtein 距离内的所有词语。然后，根据建议的原始分数及其与用户输入的前缀的距离对建议进行加权。

但是，搜索模糊前缀（尤其是非常短的前缀）将遍历大量的建议。事实上，对任何单个字母的模糊建议都将遍历整个字典，因此建议谨慎使用此功能，并充分考虑它带来的性能损失。

Redis Stack 的自动完成器支持 Unicode，允许在非拉丁语言中进行模糊匹配。

搜索引擎内部机制

Redis 模块 API

RediSearch 使用 Redis 模块 API 实现，并在启动时作为扩展模块加载到 Redis 中。

Redis 模块使扩展 Redis 的核心功能成为可能，使用与原生核心 Redis 相似的性能实现新的 Redis 命令、数据结构和功能。Redis 模块是动态库，可以在启动时加载到 Redis 中，也可以使用 MODULE LOAD 命令在运行时加载。Redis 导出一个 C API，以单个 C 头文件 redismodule.h 的形式。

虽然 RediSearch 的逻辑及其算法大多是独立的，并且可以非常容易地移植到作为独立服务器运行，但它仍然利用 Redis 作为数据库服务器的强大基础设施。建立在 Redis 之上意味着，默认情况下，模块将被赋予

  • 高性能网络协议服务器
  • 强大的复制
  • 高度耐用的持久性，作为快照或事务日志
  • 集群模式

查询执行引擎

Redis Stack 使用一个高性能的灵活查询处理引擎，可以实时地评估非常复杂的查询。

上述查询语言被编译成一个执行计划，该计划由索引迭代器或过滤器的树组成。这些可以是任何一种

  • 数值过滤器
  • 标签过滤器
  • 文本过滤器
  • 地理过滤器
  • 交集操作（组合 2 个或更多过滤器）
  • 并集操作（组合 2 个或更多过滤器）
  • 非操作（否定底层过滤器的结果）
  • 可选操作（将底层过滤器包装在可选匹配过滤器中）

查询解析器生成这些过滤器的树。例如，多词搜索将被解析成多个文本过滤器的交集操作，每个文本过滤器都遍历不同词语的倒排索引。会应用简单的优化，例如从树中移除冗余层。

结果树中的每个过滤器都一次评估一个匹配。这意味着在任何给定的时刻，查询处理器都在忙于评估和评分一个匹配的文档。这意味着在运行时几乎没有内存分配，从而提高了性能。

然后，生成的匹配文档被馈送到结果处理器的后处理链中，这些处理器负责对它们进行评分，提取前 N 个结果，从存储中加载文档，并将它们发送到客户端。该链也是动态的，它根据查询的属性进行调整。例如，仅需要返回文档 ID 的查询不会包含从存储中加载文档的阶段。

并发更新和搜索

虽然 RediSearch 非常快，并且使用高度优化的数据结构和算法，但它在并发方面面临着同样的问题。根据数据集的大小和搜索查询的基数，查询可能需要几微秒到几百毫秒，甚至在极端情况下需要几秒钟。发生这种情况时，整个 Redis 服务器进程会被阻塞。

例如，考虑一个全文查询，它将“hello”和“world”两个词语进行交集，每个词语都有 100 万个条目，并且有 50 万个共同的交集点。为了在毫秒内执行该查询，Redis 必须在一纳秒内扫描、交集和排序每个结果，这在当前硬件中是不可能的。对 1,000 个词的文档进行索引也是如此。它会阻塞 Redis 在整个查询过程中。

RediSearch 使用 Redis 模块 API 的并发功能来避免长时间停顿服务器。这个想法很简单 - 虽然 Redis 本身是单线程的，但模块可以运行多个线程，任何一个线程都可以获取 **全局锁**，当它需要访问 Redis 数据，对其进行操作并释放它时。

Redis 不能并行查询，因为只有一个线程可以获取锁，包括 Redis 主线程，但会小心地确保长时间运行的查询会通过不时地释放此锁，让其他查询有时间运行。

为了允许并发，采用了以下设计原则

  1. RediSearch 拥有一个线程池，用于运行并发搜索查询。

  2. 当搜索请求到达时，它被传递给处理程序，在主线程上进行解析，然后通过队列将请求对象传递到线程池。

  3. 线程池在其自己的线程中运行查询处理函数。

  4. 该函数锁定 Redis 全局锁并开始执行查询。

  5. 由于搜索执行基本上是循环运行的迭代器，因此每隔几次迭代就会对经过时间进行采样（每次迭代都进行采样会降低速度，因为它本身有成本）。

  6. 如果经过了足够的时间，查询处理器就会释放全局锁，并立即尝试重新获取它。当锁被释放时，内核将调度另一个线程运行 - 无论是 Redis 的主线程，还是另一个查询线程。

  7. 当锁被重新获取时，所有在释放锁之前持有的 Redis 资源都会重新打开（在线程休眠期间，键可能已被删除），并且工作会从先前状态恢复。

因此，操作系统的调度器确保所有查询线程都获得 CPU 时间来运行。当一个线程在运行时，其他线程处于空闲等待状态，但由于执行每秒被释放大约 5,000 次，因此它创造了并发效果。快速查询将一次性完成，而不会释放执行，而慢速查询将需要多次迭代才能完成，但会允许其他查询并发运行。

索引垃圾回收

RediSearch 针对高写入、更新和删除吞吐量进行了优化。这个目标的其中一项主要设计选择是，删除和更新文档实际上不会从索引中删除任何东西

  1. 删除仅仅使用单个位在全局文档元数据表中标记文档已删除。
  2. 另一方面，更新会标记文档已删除，为它分配一个新的增量文档 ID，并在新的 ID 下重新索引文档，而不会执行更改的比较。

这意味着，属于已删除文档的索引条目不会从索引中移除，并且可以被视为垃圾。随着时间的推移，一个有许多删除和更新的索引将主要包含垃圾，这既会降低速度，又会消耗不必要的内存。

为了克服这个问题，RediSearch 采用了一个后台垃圾回收（GC）机制。在索引的正常操作过程中，一个特殊的线程会随机对索引进行采样，遍历它们，并查找垃圾。包含垃圾的索引部分会被清理，并且内存会被回收。这以一种非侵入性的方式完成，每次扫描只处理非常少的数据，并且利用 Redis 的并发机制（见上文）来避免中断搜索和索引。该算法还会尝试适应索引的状态，如果索引包含大量垃圾，则会增加 GC 的频率，如果索引不包含垃圾，则会降低 GC 的频率，甚至在索引不包含垃圾的情况下几乎不进行扫描。

扩展模型

RedisSearch 支持扩展机制，与 Redis 支持模块类似。目前 API 非常简单，并且还不支持在运行时动态加载扩展。相反，扩展必须用 C 语言（或具有 C 接口的语言）编写，并编译成动态库，这些库将在启动时加载。

目前有两种类型的扩展 API

  1. **查询扩展器**，其作用是扩展查询词语（即词干提取器）。
  2. **评分函数**，其作用是在查询时对搜索结果进行排序。

扩展被编译成动态库，并在模块初始化时加载到 RediSearch 中。该机制基于 Redis 自己的模块系统的代码，但要简单得多。

虽然 RediSearch 非常快，并且内存效率很高，但如果索引足够大，它在某些时候会变得太慢或消耗太多内存。然后，它必须扩展出去，并分布在多台机器上，每台机器将持有完整搜索索引的一小部分。

传统的集群将不同的键映射到不同的分片来实现这一点。但是，对于搜索索引，这种方法不切实际。如果每个词的索引都映射到不同的分片，则需要从不同的服务器中交集记录，才能执行多词查询。

解决这一挑战的方法是采用一种称为索引分区技术，它在本质上非常简单

  • 索引通过文档 ID 分布在多台机器/分区上。
  • 每个分区都具有映射到它的所有文档的完整索引。
  • 所有分片都并发查询，并将每个分片的结果合并成单个结果。

为了方便这一点，在集群中添加了一个名为协调器的新组件。当搜索文档时，协调器会接收查询，并将其发送到 N 个分区，每个分区都持有一个包含 1/N 个文档的子索引。由于我们只对所有分区的 top K 个结果感兴趣，因此每个分区只返回它自己的 top K 个结果。然后，N 个包含 K 个元素的列表被合并，并且 top K 个元素从合并后的列表中提取出来。

RATE THIS PAGE
Back to top ↑