技术概述

Redis 开源版搜索和查询功能技术概述

摘要

Redis 查询引擎（“RQE”）是一个强大的文本搜索和二级索引引擎，构建在 Redis 开源版之上。

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

RQE 支持持续索引，不会出现性能下降，并能维持查询和索引的并发负载。这使得它非常适合搜索频繁更新的数据库，而无需批量索引和服务中断。

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

所有这一切都利用了 Redis 强大的架构和基础设施。RQE 利用 Redis 的协议、复制、持久化和集群，提供了一个强大但易于管理和维护的搜索和索引引擎，既可以用作独立数据库，也可以通过高级强大的索引功能增强现有的 Redis 数据库。

主要功能

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

索引文档

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

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 获取文档，将每个字段分解成其术语（分词），并通过标记索引中包含此文档的每个术语对应的索引进行索引。因此，产品立即添加到索引中，并且可以在未来的搜索中找到。

搜索

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

FT.SEARCH idx "full hd tv"

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

数据结构

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

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

以下是 Redis 内部使用的数据结构

索引和文档元数据

对于每个搜索*索引*，都有一个根数据结构，包含模式、统计信息等，但最重要的是，包含每个索引文档的紧凑元数据。

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

为此，Redis 保存了两个表，以两种方式映射这两种 ID（一个表使用紧凑的 Trie 树，另一个只是一个数组，其中内部文档 ID 是数组索引）。除此之外，对于每个文档，还会存储用户提供的预设分数，以及一些状态位和用户附加到文档的任何可选负载。

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

倒排索引

对于至少出现在一个文档中的每个术语，都会维护一个倒排索引，它基本上是该术语出现的所有文档的列表。该列表使用增量编码进行压缩，并且文档 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。
  • 前缀匹配（所有以某个前缀开头的术语）用一个 * 跟随一个两个字母或更长的前缀表示。
  • 使用语法 @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 提供了一些非常基本的评分函数来评估文档相关性。它们都基于文档分数和术语频率。这与使用可排序字段（见下文）的能力无关。评分函数通过向搜索请求添加 SCORER {scorer_name} 参数来指定。

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

以下是 Redis 中预先打包的评分函数

  • 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 使用先进的算法进行高亮显示和摘要，使得只有文档的相关部分才会出现在搜索查询的响应中。此功能允许用户立即了解文档与其搜索条件的相关性，通常将匹配的术语以粗体文本高亮显示。语法如下

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

摘要功能将文本分解成更小的片段。每个片段将包含找到的术语以及一些额外的周围上下文。

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

自动完成

Redis 开源版的另一个重要功能是其自动完成引擎。这允许用户创建带权重的术语词典，然后查询这些词典以获取给定用户前缀的完成建议。完成项可以包含负载，即用户提供的数据片段，可用于显示。例如，在完成用户名时，可以添加用户的额外元数据进行显示。

例如，如果用户开始将术语“lcd tv”放入词典，发送前缀“lc”将返回完整术语作为结果。该词典被建模为带有权重的紧凑 Trie 树（前缀树），通过遍历该树来查找前缀的顶级后缀。

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

然而，搜索模糊前缀（尤其是非常短的前缀）将遍历大量的建议。实际上，对于任何单个字母的模糊建议都将遍历整个词典，因此建议在使用此功能时要谨慎，并充分考虑其带来的性能开销。

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

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

搜索引擎内部

Redis 模块 API

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

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

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

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

查询执行引擎

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

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

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

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

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

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

并发更新和搜索

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

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

RQE 利用 Redis 模块 API 的并发功能，避免长时间阻塞服务器。这个想法很简单——虽然 Redis 本身是单线程的，但一个模块可以运行多个线程，其中任何一个线程都可以在需要访问 Redis 数据、对其进行操作并释放时获取全局锁。

Redis 无法并行查询，因为只有一个线程（包括 Redis 主线程）可以获取锁，但会注意确保长时间运行的查询会通过不时释放此锁来给予其他查询运行时间。

为了实现并发性，采用了以下设计原则

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

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

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

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

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

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

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

因此，操作系统的调度程序确保所有查询线程都能获得 CPU 时间来运行。当一个线程运行时，其余线程会空闲等待，但由于执行每秒约让出 5,000 次，这产生了并发的效果。快速查询会一次性完成，无需让出执行，慢速查询则需要多次迭代才能完成，但会允许其他查询并发运行。

索引垃圾回收

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

  1. 删除只是通过在一个全局文档元数据表中使用一个位来标记文档已删除。
  2. 另一方面，更新操作将文档标记为已删除，为其分配一个新的递增文档 ID，并在新的 ID 下重新索引该文档，而不进行更改比较。

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

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

扩展模型

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

目前有两种扩展 API

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

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

虽然 RQE 速度非常快且内存效率高，但如果索引足够大，在某个时候它会变得太慢或消耗太多内存。这时必须将其横向扩展并分区到多台机器上，每台机器都将持有完整搜索索引的一小部分。

传统集群将不同的键映射到不同的分片来实现这一点。然而，对于搜索索引来说，这种方法并不实用。如果每个单词的索引都映射到不同的分片，则对于多词查询，需要对来自不同服务器的记录进行交集操作。

解决这一挑战的方法是采用一种称为索引分区的技术，其核心非常简单

  • 索引按文档 ID 划分到多台机器/分区上。
  • 每个分区都包含映射到其上的所有文档的完整索引。
  • 所有分片并发查询，并将每个分片的结果合并成一个最终结果。

为了方便这一点，在集群中添加了一个称为协调器的新组件。搜索文档时，协调器接收查询并将其发送到 N 个分区，每个分区包含 1/N 文档的子索引。由于我们只关心所有分区的 top K 结果，因此每个分区只返回其自身的 top K 结果。然后，将 N 个 K 元素的列表合并，并从合并后的列表中提取 top K 个元素。

评价本页
返回顶部 ↑