技术概览

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

使用专门的数据结构可以实现更快的搜索和更高效的内存存储索引记录，利用如差分编码等压缩技术。

这些是Redis Stack在底层使用的数据结构：

索引和文档元数据

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

在内部，索引中，Redis Stack 使用增量编码的数值、递增的32位文档ID列表。这意味着用户在索引时需要将给定的文档键或ID替换为内部ID，并在搜索时将其转换回原始ID。

为此，Redis Stack 保存了两个表，以两种方式映射这两种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。

自动完成

自动补全引擎（详见下文更详细的描述）利用紧凑的字典树或前缀树来编码术语并通过前缀进行搜索。

查询语言

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

  • 多词短语是标记的列表，例如 foo bar baz，并且意味着这些术语的交集（逻辑与）。
  • 精确短语用引号括起来，例如 "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”将返回完整术语作为结果。字典被建模为一个带有权重的紧凑字典树（前缀树），通过遍历该树可以找到前缀的顶级后缀。

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

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

Redis Stack 的自动补全功能支持 Unicode，允许在非拉丁语言中进行模糊匹配。

搜索引擎内部机制

Redis 模块 API

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

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

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

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

查询执行引擎

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

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

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

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

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

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

并发更新和搜索

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

例如，考虑一个全文查询，它交叉了“hello”和“world”这两个词，每个词有一百万个条目，以及五十万个共同的交叉点。要在毫秒内执行该查询，Redis 必须在一纳秒内扫描、交叉和排名每个结果，这在当前硬件上是不可能的。同样，索引一个1000字的文档也是如此。在查询期间，它会完全阻塞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 的频率，如果不包含垃圾，则减少频率，甚至在不包含垃圾时几乎不进行扫描。

扩展模型

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

目前有两种扩展API：

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

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

虽然RediSearch非常快速且内存高效，但如果索引足够大，在某些时候它会变得太慢或消耗太多内存。此时必须进行扩展和分区，将其分布在多台机器上，每台机器将保存完整搜索索引的一小部分。

传统集群通过将不同的键映射到不同的分片来实现这一点。然而，对于搜索索引来说，这种方法并不实用。如果每个单词的索引被映射到不同的分片，那么对于多词查询，就需要从不同的服务器中交叉记录。

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

  • 索引根据文档ID分布在多台机器/分区上。
  • 每个分区都有一个完整的索引，映射到它的所有文档。
  • 所有分片都会被同时查询，并且每个分片的结果会被合并成一个单一的结果。

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

RATE THIS PAGE
Back to top ↑