技术概述

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

抽象

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

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

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

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

所有这些都是在利用 Redis 强大的架构和基础架构的同时完成的。使用 Redis 的协议、复制、持久性和集群，RediSearch 提供了一个功能强大且易于管理和维护的搜索和索引引擎，该引擎可用作独立数据库，或者使用高级强大的索引功能来增强现有 Redis 数据库。

主要特点

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

为文档编制索引

Redis Stack 需要知道如何为文档编制索引，以便有效地进行搜索。一个文档可以有多个字段，每个字段都有自己的权重。例如，标题通常比文本本身更重要。该引擎还可以使用数字或地理字段进行筛选。因此，第一步是创建索引定义，它告诉 Redis Stack 如何处理将要添加的文档。例如，要定义产品索引，为其 title、description、brand 和 price 字段编制索引，索引创建将如下所示：

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 对象）。

使用专用数据结构可以利用增量编码等压缩技术，实现更快的搜索和更节省内存的索引记录存储。

以下是 Redis Stack 在后台使用的数据结构：

索引和文档元数据

对于每个搜索索引，都有一个包含架构、统计信息等的根数据结构，但最重要的是，包含有关每个索引文档的压缩元数据。

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

为此，Redis Stack 保存了两个表，以两种方式映射两种 ID（一个表使用紧凑的 trie，另一个表只是一个数组，其中内部文档 ID 是数组索引）。最重要的是，对于每个文档，都会存储其用户给定的推定分数，以及一些状态位和用户附加到文档的任何可选有效负载。

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

倒排索引

对于至少一个文档中出现的每个术语，将保留一个倒排索引，该索引基本上是出现该术语的所有文档的列表。该列表使用 delta 编码进行压缩，并且文档 ID 始终递增。

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

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

在 ID 的顶部，将保存每个文档中每个术语的频率、表示术语在文档中出现的字段的位掩码，以及术语出现的位置列表。

默认搜索记录的结构如下。通常，所有条目的长度均为 1 个字节：

+----------------+------------+------------------+-------------+------------------------+
|  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 USD 的所有产品都位于特定列表中，该列表与查询的其余部分相交。有关更多信息，请参阅 查询执行引擎。

但是，为了按价格范围进行筛选，您必须将查询与该范围内的所有不同价格相交，或执行联合查询。如果范围中有许多值，则效率会非常低。

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

标签索引

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

标记字段和全文字段之间的主要区别是：

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

  2. 无法从常规全文搜索中找到标记。如果文档有一个名为 tags 的字段，其值为 foo 和 bar，则搜索不带特殊标签修饰符的 foo 或 bar（见下文）将不会返回此文档。

  3. 索引要简单得多，压缩程度也更高。索引中仅存储文档 ID，通常每个索引条目有 1-2 个字节。

地理位置索引

地理索引利用 Redis 自己的地理索引功能。在查询时，查询的地理部分（半径筛选条件）将发送到 Redis，仅返回该半径内文档的 ID。Longitude 和 latitude 应作为字符串传递lon,lat.例如1.23,4.56.

自动完成

自动完成引擎（有关更完整的描述，请参阅下文）使用紧凑的 trie 或 prefix 树对术语进行编码并按前缀进行搜索。

查询语言

复杂查询支持简单语法，这些查询可以组合在一起以表达复杂的筛选和匹配规则。查询是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}].
  • Geo radius 匹配具有语法的 geo 字段@field:[{lon} {lat} {radius} {m|km|mi|ft}]
  • 使用语法的标记字段过滤器@field:{tag | tag | ...}.请参阅有关标记字段的完整文档。
  • 可选条款或条款：foo ~bar表示 bar 是可选的，但带有 bar 的文档将排名更高。

复杂查询示例

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

lcd tv

这将返回在任何字段中包含这些术语的文档。将搜索限制为特定字段（在本例中仅为 title）表示为：

@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 的。多克诺姆

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

  • BM25 系列

    基本 TF-IDF 评分器的变体。有关更多信息，请参阅此 Wikipedia 文章。

  • DISMAX 系列

    一个简单的评分器，用于汇总匹配词的频率。对于 union 子句，它将提供这些匹配项的最大值。

  • DOCSCORE

    一个评分函数，它只返回文档的推定分数，而不对其应用任何计算。由于文档分数可以更新，因此如果您想使用外部分数而不是其他内容，这可能很有用。

可排序字段

可以绕过评分功能机制，直接按不同文档属性（字段）的值对搜索结果进行排序，即使查询未使用排序字段也是如此。例如，您可以搜索 First name 并按姓氏排序。

使用FT.CREATE中，您可以声明TEXT,TAG,NUMERIC和GEOproperties 设置为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（前缀树），遍历该 trie 以查找前缀的顶部后缀。

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

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

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

有关更多信息和示例，请参阅自动完成页面。

搜索引擎内部

Redis 模块 API

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

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

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

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

查询执行引擎

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

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

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

查询解析器生成这些筛选条件的树。例如，多词搜索将解析为多个文本过滤器的交叉作，每个过滤器遍历不同术语的倒排索引。应用简单的优化，例如删除树中的冗余层。

结果树中的每个筛选器一次评估一个匹配项。这意味着在任何给定时刻，查询处理器都忙于评估和评分一个匹配的文档。这意味着在运行时完成的内存分配非常少，从而获得更高的性能。

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

并发更新和搜索

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

例如，考虑一个与术语 “hello” 和 “world” 相交的全文查询，每个术语都有 100 万个条目和五十万个公共交集点。要在一毫秒内执行该查询，Redis 必须在 1 纳秒内扫描、相交和排名每个结果，这在当前硬件中是不可能的。索引 1,000 字的文档也是如此。它会在查询期间完全阻止 Redis。

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

Redis 不能并行查询，因为只有一个线程可以获取锁，包括 Redis 主线程，但要注意确保长时间运行的查询会通过不时生成此锁来为其他查询提供运行时间。

采用以下设计原则来允许并发：

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

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

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

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

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

  6. 如果已过足够的时间，查询处理器将释放全局锁并立即尝试再次获取它。当锁被释放时，内核将安排另一个线程运行 - 无论是 Redis 的主线程，还是另一个查询线程。

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

因此，作系统的计划程序确保所有查询线程都获得 CPU 时间来运行。当一个运行时，其余的空闲等待，但由于每秒执行大约 5000 次，因此会产生并发效果。快速查询将一次性完成而不会产生执行，慢速查询将需要多次迭代才能完成，但允许其他查询并发运行。

索引垃圾回收

RediSearch 针对高写入、更新和删除吞吐量进行了优化。此目标指示的主要设计选择之一是删除和更新文档实际上不会从索引中删除任何内容：

  1. 删除只是使用单个位在全局文档元数据表中标记已删除的文档。
  2. 另一方面，更新会将文档标记为已删除，为其分配新的增量文档 ID，并在新 ID 下重新为文档编制索引，而无需对更改进行比较。

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

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

扩展模型

RedisSearch 支持扩展机制，就像 Redis 支持模块一样。该 API 目前非常小，并且尚不支持在运行时动态加载扩展。相反，扩展必须用 C 语言（或具有 C 接口的语言）编写，并编译成将在启动时加载的动态库。

目前有两种类型的扩展 API：

  1. 查询扩展器，其作用是扩展查询标记（即词干分析器）。
  2. 评分函数，其作用是在查询时对搜索结果进行排名。

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

虽然 RediSearch 速度非常快且内存效率高，但如果索引足够大，则在某些时候它会太慢或消耗太多内存。然后，必须将其横向扩展并在多台计算机上进行分区，每台计算机将保存完整搜索索引的一小部分。

传统集群将不同的 key 映射到不同的分片来实现这一点。但是，对于搜索索引，此方法不切实际。如果每个单词的索引都映射到不同的分片，则必须将来自不同服务器的记录相交以进行多词查询。

解决此挑战的方法是使用一种称为索引分区的技术，该技术的核心非常简单：

  • 索引按文档 ID 拆分到多台计算机/分区中。
  • 每个分区都有一个映射到它的所有文档的完整索引。
  • 同时查询所有分片，并将每个分片的结果合并为单个结果。

为了实现这一点，将一个名为 coordinator 的新组件添加到集群中。在搜索文档时，协调器接收查询并将其发送到 N 个分区，每个分区都保存着 1/N 个文档的子索引。由于我们只对所有分区的前 K 个结果感兴趣，因此每个分区只返回自己的前 K 个结果。然后，合并 K 个元素的 N 个列表，并从合并的列表中提取前 K 个元素。