Please enable Javascript to view the contents

ES原理和实践:底层lucene

 ·  ☕ 6 分钟  ·  🪶 VictorHong · 👀... 阅读

ES 和 lucene 的关系

  • lucene: lucene 是一个 Java 信息检索程序库。可以类比为封装的底层 API,程序引用这个库之后可以使用其中的一些功能。
  • ES: ES 是基于 lucene 这个包基础上进行构建的一个满足高可用、高性能、高可拓展的分布式存储中间件。

ES和lucene关系

Lucene 的底层数据结构设计

Lucene 是一个高效的,基于 Java 的全文检索库。主要包括下面的一些核心操作:
lucene核心操作

倒排索引

为什么使用倒排索引呢?倒排索引最后不也是拿到文档 id 进行查询文档,使用正排索引不是也能满足需求吗?

搜索引擎通常用于搜索网页内容,而网页内容多为文章。我们通常使用关键字来查询相关文章。由于文章内容较长,若使用 MySQL 数据库进行查询,需采用类似like %关键字%的方式,这种方式会导致全表扫描,查询性能极低。即便尝试构建索引,对文章内容进行索引也是不切实际的。

使用 Elasticsearch(ES)可以先对文章进行分词,然后将每个词项对应的倒排列表存入 ES 的倒排索引中。这样,通过关键字查找相关网页文章的速度就像哈希查找一样快,避免了线性全表扫描。ES 的倒排索引将非结构化的文章内容分词整理,转换成结构化的倒排列表存储,从而在进行关键字的全文索引时能达到极佳的效果。

电商搜索系统通常需要快速的查询响应速度,以确保良好的用户体验和较高的商品销量。通常,电商搜索系统,例如淘宝、京东、咸鱼、拼多多等,在进行商品搜索的时候,可以按照商品的名称进行模糊搜索,除此之外,还能对商品进行各种各样的筛选:分类、品牌、价格、特征、尺码、包装形式、是否折扣、发货地……

首先,为了保证搜索速度,是否应在 MySQL 中为各种筛选项添加索引是一个问题。如果添加索引,MySQL 的索引可能会过度膨胀,影响写入性能。相比之下,Elasticsearch(ES)默认所有字段都是索引,更适合处理多条件查询。此外,商品名称的模糊查询也不适合使用 MySQL。(MySQL 对于模糊查询最多做到前缀匹配)

在上述两个案例中,我们了解到在实际业务中,最终都需要获取文档 ID。关键在于如何高效地获取这些 ID,以及采用何种数据结构。MySQL 通过全表扫描来获取 ID,而 Elasticsearch(ES)则利用倒排索引快速检索 ID。两者的优劣显而易见。

这也说明了使用正排索引的局限:模糊查询和多条件筛选查询能力的欠缺。而这两个正是 ES 的强项。

简单描述下倒排索引,下面是一个倒排索引进行构建的例子:
左图是一个正排索引,记录文档 id 到文档内容的映射;右图是倒排索引,记录了单词(由文档内容分词而成)到文档 id 的映射,每个单词有自己的单词 id,另外,倒排索引不仅记录了单词所在的文档 id,还记录了单词在文档出现的频率和出现在文档的单词次序(文档内容的第几个单词)

image alt
倒排索引: 以单词“谷歌”为例子,文档频率为5表示在五个文档都出现了这个单词,对应其中的两个倒排列表为{(1;1;<1>),(2;1;<1>)},表示在文档1和文档2出现了这个单词,单词频率都为1,都在两个文档中的出现位置都是1

词典-FST

很多人仅仅知道 ES 中的底层是倒排索引,其实 ES 的索引构建由词典倒排表构成,其中词典结构尤为重要。
参考各种词典结构的优点和缺点(参考:Lucene 底层原理):

数据结构 优缺点
排序列表 Array/List 优点:实现简单
缺点:不平衡;性能差,且依赖数据的顺序性
HashMap/TreeMap 优点:性能高,查询快
缺点:内存消耗大,几乎是原始数据的三倍
Skip List(跳跃表) 优点:可快速查找词语(在 lucene、redis、Hbase 等均有实现),相对于 TreeMap 等结构,特别适合高并发场景(Skip List 介绍)、占用内存小且可调
缺点:模糊查询支持不好。一般作为等值查询的索引
Trie 优点:适合英文词典,如果系统中存在大量字符串且这些字符串基本没有公共前缀,则相应的 trie 树将非常消耗内存
缺点:对于后缀搜索不友好
Finite State Transducers (FST) 一种有限状态转移机,Lucene 4 有开源实现,并大量使用。共享前缀,内存消耗少,但要求输入有序,更新不易

上面列出的一些词典的结构,最简单如排序数组,可以通过二分查找来检索数据;更快的有在内存直接使用的哈希表;磁盘查找有 B 树、B+树,其中 MySQL 是使用 B+树作为词典;而 Redis 使用跳跃表和哈希表等。

但一个能支持 TB 级数据的倒排索引结构需要在时间和空间上有个平衡,主要有如下的三种主要实现方式提供 ES 进行选择:

结构 优点 缺点
B+树 nvyLAG 外存索引(在磁盘上)、可更新(在原来数据的基础上更新 占用空间大、速度不够快
跳跃表 BT3RIA 结构简单、跳跃间隔、级数可控。

Lucene3.0 之前使用的也是跳跃表结构,后换成了 FST,但跳跃表在 Lucene 其他地方还有应用如倒排表合并和文档号索引。
模糊查询支持不好
FST 8BYAbR 节省内存,查询快,支持前缀和后缀查询 更新难,构建复杂

lucene 从 4.x 开始大量使用的数据结构是 FST(Finite State Transducer,有限状态转换器)。FST 有两个优点:

  1. 空间占用小。通过对词典中单词前缀和后缀的重复利用,压缩了存储空间。
  2. 查询速度快。O(len(str))的查询时间复杂度。(str 是输入的查询字符串长度)

ES 倒排索引实现细节

通过结合 FST 和倒排索引,我们可以得到下面这张 Lucene 对于倒排索引实现的大概结构:
假设查询 Allen,查询过程会先从 Term-Index 查询这个词在 Term Dictonary 的大概位置,及从 Ada 开始遍历查询,然后精确的查询到 Allen 的具体位置,得到倒排列表。

hvbCpe

FST 相当于是倒排索引的一个二级缓存索引树。

建立 FST 这个二级索引,可以实现倒排索引的快速定位,不需要经过多次的磁盘 IO,搜索效率大大提高了。不过需要注意的是 FST 是存储在堆内存中的,而且是常驻内存,大概占用 50%-70%的堆内存,因此这里也是我们在生产中可以进行堆内存优化的地方。

lKVDak

这个时候我们分析下“为什么 Elasticsearch/Lucene 检索可以比 mysql 快”(注意,这里说的是检索,并不是写入)

Mysql 只有 term dictionary 这一层,是以 B+树 排序的方式存储在磁盘上的。检索一个 term 需要若干次的 random access 的磁盘操作。而 Lucene 在 term dictionary 的基础上添加了 term index 来加速检索,term index 以 FST 的形式缓存在内存中(并且能够压缩)。从 term index 查到对应的 term dictionary 的 block 位置之后,再去磁盘上找 term,大大减少了磁盘的随机访问次数。

(实际上,ES 的写入因为需要构建许多结构化的数据,如倒排表、docValue 等,提供后续进行查找,并且还需要考虑分布式同步等操作,写入应该是会比 MySQL 慢 的,所以 ES 比较适合 OLAP)


VictorHong
作者
VictorHong
📚Learner🤓Nerd🌐Developer 努力做有价值的事情