一、序言

前段时间碰触的两个工程项目都采用到了 Elasticsearch (下列全称 ES ) 来储存统计数据和对统计数据展开搜寻预测,就对 ES 展开了许多自学。责任编辑重新整理人格他们的一场控制技术撷取。

责任编辑不能高度关注 ES 里头的分布式系统控制技术、有关 API 的采用,而要著眼撷取下ES 怎样加速索引那个主轴下面。那个也是我在自学以后对 ES 最钟爱的部份。

责任编辑大体主要包括附注:

  • 有关搜寻

  • 现代亲密关系型统计资料库和 ES 的差异

  • 浏览器基本原理

  • 深究征迁索引

  • 征迁索引具体内容是个甚么模样的(posting list -> term dic -> term index)

  • 有关 postings list 的许多巧技 (FOR、Roaring Bitmaps)

  • 怎样加速做联合查询?

二、有关搜寻

先设想一个有关搜寻的场景,假设我们要搜寻一首诗句内容中带前字的古诗,

搜索引擎的概念(搜索引擎的概念组成和分类)-第1张

用 现代亲密关系型统计资料库和 ES 实现会有甚么差异?

如果用像 MySQL 这样的 RDBMS 来储存古诗的话,我们应该会去采用这样的 SQL 去查询

select name from poems where content like "%前%";

这种我们称为顺序扫描法,需要遍历所有的记录展开匹配。

不但效率低,而且不符合我们搜寻时的期望,比如我们在搜寻ABCD"这样的关键词时,通常还希望看到"A","AB","CD",ABC的搜寻结果。

于是乎就有了专业的浏览器,比如我们今天的主角 -- ES。

浏览器基本原理

浏览器的搜寻基本原理简单概括的话可以分为这么几步,

搜索引擎的概念(搜索引擎的概念组成和分类)-第2张
  • 内容爬取,停顿词过滤,比如许多无用的像"的",了之类的语气词/连接词

  • 内容分词,提取关键词

  • 根据关键词建立征迁索引

  • 用户输入关键词展开搜寻

这里我们就引出了一个基本概念,也是我们今天的要剖析的重点 -征迁索引。也是 ES 的核心知识点。

如果你了解 ES 应该知道,ES 可以说是对 Lucene 的一个封装,里头有关征迁索引的实现就是通过 lucene 那个 jar 包提供的 API 实现的,所下列面讲的有关征迁索引的内容实际上都是 lucene 里头的内容。

三、征迁索引

首先我们还不能忘了我们以后提的搜寻需求,先看下建立征迁索引之后,我们上述的查询需求会变成甚么模样,

搜索引擎的概念(搜索引擎的概念组成和分类)-第3张

这样我们一输入前,借助征迁索引就可以直接定位到符合查询条件的古诗。

当然这只是一个很大白话的形式来描述征迁索引的简要工作基本原理。在 ES 中,那个征迁索引是具体内容是个甚么样的,怎么储存的等等,这些才是征迁索引的精华内容。

1. 两个基本概念

在进入下文以后,先描述两个前置基本概念。

term

关键词那个东西是我他们的讲法,在 ES 中,关键词被称为term

postings list

还是用下面的例子,{静夜思, 望庐山瀑布}是 "前" 那个 term 所对应列表。在 ES 中,这些被描述为所有包含特定 term 文档的 id 的集合。由于整型数字 integer 可以被高效压缩的特质,integer 是最适合放在 postings list 作为文档的唯一标识的,ES 会对这些存入的文档展开处理,转化成一个唯一的整型 id。

再说下那个 id 的范围,在储存统计数据的时候,在每一个 shard 里头,ES 会将统计数据存入不同的 segment,这是一个比 shard 更小的分片单位,这些 segment 会定期合并。在每一个 segment 里头都会保存最多 2^31 个文档,每个文档被分配一个唯一的 id,从0(2^31)-1

搜索引擎的概念(搜索引擎的概念组成和分类)-第4张

有关的名词都是 ES 官方文档给的描述,后面参考材料中都可以找到出处。

2. 索引内部结构

下面所描述的征迁索引,仅仅是一个很粗糙的模型。真的要在实际生产中采用,当然还差的很远。

在实际生产场景中,比如 ES 最常用的日志预测,日志内容展开分词之后,可以得到多少的 term?

那么怎样加速的在海量 term 中查询到对应的 term 呢?遍历一遍显然是不现实的。

term dictionary

于是乎就有了term dictionary,ES 为了能加速查找到 term,将所有的 term 排了一个序,二分法查找。是不是感觉有点眼熟,这不就是 MySQL 的索引方式的,直接用 B+树建立索引词典指向被索引的统计数据。

term index

但是问题又来了,你觉得 Term Dictionary 应该放在哪里?肯定是放在内存里头吧?磁盘 io 那么慢。就像 MySQL 索引就是存在内存里头了。

但是如果把整个 term dictionary 放在内存里头会有甚么后果呢?

内存爆了...

别忘了,ES 默认可是会对全部 text 字段展开索引,必然会消耗巨大的内存,为此 ES 针对索引展开了深度的优化。在保证执行效率的同时,尽量缩减内存空间的占用。

于是乎就有了term index

Term index 从统计数据结构上进行分类算是一个Trie 树,也就是我们常说的字典树。这是一种专门处理字符串匹配的统计数据结构,用来解决在一组字符串集合中加速查找某个字符串的问题。

这棵树不能包含所有的 term,它包含的是 term 的许多前缀(这也是字典树的采用场景,公共前缀)。通过 term index 可以加速地定位到 term dictionary 的某个 offset,然后从那个位置再往后顺序查找。就想右边那个图所表示的。(怎么样,像不像我们查英文字典,我们定位 S 开头的第一个单词,或者定位到 Sh 开头的第一个单词,然后再往后顺序查询)

lucene 在这里还做了两点优化,一是 term dictionary 在磁盘下面是分 block 保存的,一个 block 内部利用公共前缀压缩,比如都是 Ab 开头的单词就可以把 Ab 省去。二是 term index 在内存中是以 FST(finite state transducers)的统计数据结构保存的。

FST 有两个优点:

空间占用小。 通过对词典中单词前缀和后缀的重复利用,压缩了储存空间

查询速度快。 O(len(str)) 的查询时间复杂度。

FST 的理论比较复杂,责任编辑不细讲

延伸阅读:https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

OK,现在我们能得到 lucene 征迁索引大体是个甚么模样的了。

搜索引擎的概念(搜索引擎的概念组成和分类)-第5张

四、有关 postings list 的许多巧技

在实际采用中,postings list 还需要解决两个痛点,

  • postings list 如果不展开压缩,会非常占用磁盘空间,

  • 联合查询下,怎样加速求交并集(intersections and unions)

对于怎样压缩,可能会有人觉得没有必要,posting list 不是已经只储存文档 id 了吗?还需要压缩?,但是如果在 posting list 有百万个 doc id 的情况,压缩就显得很有必要了。(比如按照朝代查询古诗?),至于为啥需要求交并集,ES 是专门用来搜寻的,肯定会有很多联合查询的需求吧 (AND、OR)。

按照下面的思路,我们先将怎样压缩。

1. 压缩

Frame of Reference

在 lucene 中,要求 postings lists 都要是有序的整形数组。这样就带来了一个很好的好处,可以通过 增量编码(delta-encode)这种方式展开压缩。

比如现在有 id 列表[73, 300, 302, 332, 343, 372],转化成每一个 id 相对于前一个 id 的增量值(第一个 id 的前一个 id 默认是 0,增量就是它他们)列表是[73, 227, 2, 30, 11, 29]在那个新的列表里头,所有的 id 都是小于 255 的,所以每个 id 只需要一个字节储存

实际上 ES 会做的更加精细,

搜索引擎的概念(搜索引擎的概念组成和分类)-第6张

它会把所有的文档分成很多个 block,每个 block 正好包含 256 个文档,然后单独对每个文档展开增量编码,计算出储存那个 block 里头所有文档最多需要多少位来保存每个 id,并且把那个位数作为头信息(header)放在每个 block 的前面。那个控制技术叫Frame of Reference

上图也是来自于 ES 官方博客中的一个示例(假设每个 block 只有 3 个文件而不是 256)。

FOR 的步骤可以总结为:

搜索引擎的概念(搜索引擎的概念组成和分类)-第7张

进过最后的位压缩之后,整型数组的类型从固定大小 (8,16,32,64 位)4 种类型,扩展到了[1-64] 位共 64 种类型。

通过以上的方式可以极大的节省 posting list 的空间消耗,提高查询性能。不过 ES 为了提高 filter 过滤器查询的性能,还做了更多的工作,那就是缓存

Roaring Bitmaps (for filter cache)

在 ES 中,可以采用 filters 来优化查询,filter 查询只处理文档是否匹配与否,不涉及文档评分操作,查询的结果可以被缓存。

对于 filter 查询,es 提供了 filter cache 这种特殊的缓存,filter cache 用来储存 filters 得到的结果集。缓存 filters 不需要太多的内存,它只保留一种信息,即哪些文档与 filter 相匹配。同时它可以由其它的查询复用,极大地提升了查询的性能。

我们下面提到的 Frame Of Reference 压缩算法对于 postings list 来说效果很好,但对于需要储存在内存中的 filter cache 等不太合适。

filter cache 会储存那些经常采用的统计数据,针对 filter 的缓存就是为了加速处理效率,对压缩算法要求更高。

对于这类 postings list,ES 采用不一样的压缩方式。那么让我们一步步来。

首先我们知道 postings list 是 Integer 数组,具有压缩空间。

假设有这么一个数组,我们第一个压缩的思路是甚么?用位的方式来表示,每个文档对应其中的一位,也就是我们常说的位图,bitmap。

它经常被作为索引用在统计资料库、查询引擎和浏览器中,并且位操作(如 and 求交集、or 求并集)之间可以并行,效率更好。

搜索引擎的概念(搜索引擎的概念组成和分类)-第8张

但是,位图有个很明显的缺点,不管业务中实际的元素基数有多少,它占用的内存空间都恒定不变。也就是说不适用于稀疏储存。业内对于稀疏位图也有很多成熟的压缩方案,lucene 采用的就是roaring bitmaps

我这里用简单的方式描述一下那个压缩过程是怎么样,

搜索引擎的概念(搜索引擎的概念组成和分类)-第9张

将 doc id 拆成高 16 位,低 16 位。对高位展开聚合 (以高位做 key,value 为有相同高位的所有低位数组),根据低位的统计数据量 (不同高位聚合出的低位数组长度不相同),采用不同的 container(统计数据结构) 储存。

  • len<4096 ArrayContainer 直接存值

  • len>=4096 BitmapContainer 采用 bitmap 储存

分界线的来源:value 的最大总数是为2^16=65536. 假设以 bitmap 方式储存需要65536bit=8kb,而直接存值的方式,一个值 2 byte,4K 个总共需要2byte*4K=8kb。所以当 value 总量 <4k 时,采用直接存值的方式更节省空间。

搜索引擎的概念(搜索引擎的概念组成和分类)-第10张

空间压缩主要体现在:

  • 高位聚合 (假设统计数据中有 100w 个高位相同的值,原先需要 100w2byte,现在只要 12byte)

  • 低位压缩

缺点就在于位操作的速度相对于原生的 bitmap 会有影响。

这就是 trade-off 呀。平衡的艺术。

2. 联合查询

讲完了压缩,我们再来讲讲联合查询。

先讲简单的,如果查询有 filter cache,那就是直接拿 filter cache 来做计算,也就是说位图来做 AND 或者 OR 的计算。

如果查询的 filter 没有缓存,那么就用 skip list 的方式去遍历磁盘上的 postings list。

搜索引擎的概念(搜索引擎的概念组成和分类)-第11张

以上是三个 posting list。我们现在需要把它们用 AND 的亲密关系合并,得出 posting list 的交集。首先选择最短的 posting list,逐个在另外两个 posting list 中查找看是否存在,最后得到交集的结果。遍历的过程可以跳过许多元素,比如我们遍历到绿色的 13 的时候,就可以跳过蓝色的 3 了,因为 3 比 13 要小。

用 skip list 还会带来一个好处,还记得前面说的吗,postings list 在磁盘里头是采用 FOR 的编码方式储存的

会把所有的文档分成很多个 block,每个 block 正好包含 256 个文档,然后单独对每个文档展开增量编码,计算出储存那个 block 里头所有文档最多需要多少位来保存每个 id,并且把那个位数作为头信息(header)放在每个 block 的前面。

因为那个 FOR 的编码是有解压缩成本的。利用 skip list,除了跳过了遍历的成本,也跳过了解压缩这些压缩过的 block 的过程,从而节省了 cpu

五、总结

下面我们来做一个控制技术总结(感觉有点王刚老师的味道😂)

  • 为了能够加速定位到目标文档,ES 采用征迁索引控制技术来优化搜寻速度,虽然空间消耗比较大,但是搜寻性能提高十分显著。

  • 为了能够在数量巨大的 terms 中加速定位到某一个 term,同时节约对内存的采用和减少磁盘 io 的读取,lucene 采用 "term index -> term dictionary -> postings list" 的征迁索引结构,通过FST压缩放入内存,进一步提高搜寻效率。

  • 为了减少 postings list 的磁盘消耗,lucene 采用了FOR(Frame of Reference)控制技术压缩,带来的压缩效果十分明显。

  • ES 的 filter 语句采用了Roaring Bitmap控制技术来缓存搜寻结果,保证高频 filter 查询速度的同时降低储存空间消耗。

  • 在联合查询时,在有 filter cache 的情况下,会直接利用位图的原生特性加速求交并集得到联合查询结果,否则采用skip list对多个 postings list 求交并集,跳过遍历成本并且节省部份统计数据的解压缩 cpu 成本

Elasticsearch 的索引思路

将磁盘里的东西尽量搬进内存,减少磁盘随机读取次数 (同时也利用磁盘顺序读特性),结合各种压缩算法,用及其苛刻的态度采用内存。

所以,对于采用 Elasticsearch 展开索引时需要注意:

  • 不需要索引的字段,一定要明确定义出来,因为默认是自动建索引的

  • 同样的道理,对于 String 类型的字段,不需要 analysis 的也需要明确定义出来,因为默认也是会 analysis 的

  • 选择有规律的 ID 很重要,随机性太大的 ID(比如 Java 的 UUID) 不利于查询

最后说一下,控制技术选型永远伴随着业务场景的考量,每种统计资料库都有他们要解决的问题(或者说擅长的领域),对应的就有他们的统计数据结构,而不同的采用场景和统计数据结构,需要用不同的索引,才能起到最大化加快查询的目的。

这篇文章讲的虽是 Lucene 怎样实现征迁索引,怎样精打细算每一块内存、磁盘空间、怎样用诡谲的位运算加快处理速度,但往高处思考,再类比一下 MySQL,你就会发现,虽然都是索引,但是实现起来,截然不同。笼统的来说,b-tree 索引是为写入优化的索引结构。当我们不需要支持加速的更新的时候,可以用预先排序等方式换取更小的储存空间,更快的索引速度等好处,其代价就是更新慢,就像 ES。

希望本篇文章能给你带来许多收获~

原文:juejin.cn/post/6889020742366920712

参考文档

  • https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps

  • https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up

  • http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html

  • https://www.infoq.cn/article/database-timestamp-02

  • https://zhuanlan.zhihu.com/p/137574234

投 稿 通 道

让你的博客被更多人看到

如果你在 CSDN、博客园、掘金等平台有写控制技术博客的习惯,想让他们的原创博客被更多人看到,可以来 Java后端 投稿。

Java后端 鼓励读者投稿个人控制技术博客、面试经验、教程。不管是入门的图文教程、还是热门控制技术讲解,只要你喜欢写东西,我们欢迎你来投稿。

📝 稿件基本要求:

• 文章确系个人原创作品,如果在其他非公众号渠道有过发表也可以,只要是个人原创即可。

• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰、语句通顺。

• 如果被采纳的原创稿件,我们将提供稿费以及个人影响力曝光,具体内容依据文章阅读量和质量结算稿费。

📬 投稿通道:

• 投稿请联系下方微信,备注:原创投稿

△长按添加 Java后端 小编