“All problems in computer science can be solved by another level of indirection.”
– David J. Wheeler
“计算机世界就是 trade-off 的艺术”
一、前言
最近接触的几个我的项目都应用到了 Elasticsearch (以下简称 ES) 来存储数据和对数据进行搜寻剖析，就对 ES 进行了一些学习。本文整顿自我本人的一次技术分享。
本文不会关注 ES 外面的分布式技术、相干 API 的应用，而是专一分享下 ”ES 如何疾速检索“ 这个主题下面。这个也是我在学习之前对 ES 最感兴趣的局部。
本文大抵包含以下内容：
-
对于搜寻
- 传统关系型数据库和 ES 的差异
- 搜索引擎原理
-
细究倒排索引
- 倒排索引具体是个什么样子的（posting list -> term dic -> term index）
- 对于 postings list 的一些巧技（FOR、Roaring Bitmaps）
- 如何疾速做联结查问？
二、对于搜寻
先构想一个对于搜寻的场景，假如咱们要搜寻一首诗句内容中带“前”字的新诗，
用 传统关系型数据库和 ES 实现会有什么差异？
如果用像 MySQL 这样的 RDBMS 来存储新诗的话，咱们应该会去应用这样的 SQL 去查问
select name from poems where content like "% 前 %";这种咱们称为程序扫描法，须要遍历所有的记录进行匹配。
岂但效率低，而且不合乎咱们搜寻时的冀望，比方咱们在搜寻“ABCD” 这样的关键词时，通常还心愿看到 ”A”,”AB”,”CD”,“ABC”的搜寻后果。
于是乎就有了业余的搜索引擎，比方咱们明天的配角 — ES。
搜索引擎原理
搜索引擎的搜寻原理简略概括的话能够分为这么几步，
- 内容爬取，进展词过滤
比方一些无用的像 ” 的 ”，“了”之类的语气词 / 连接词
- 内容分词，提取关键词
- 依据关键词建设 倒排索引
- 用户输出关键词进行搜寻
这里咱们就引出了一个概念，也是咱们明天的要分析的重点 – 倒排索引。也是 ES 的外围知识点。
如果你理解 ES 应该晓得，ES 能够说是对 Lucene 的一个封装，外面对于倒排索引的实现就是通过 lucene 这个 jar 包提供的 API 实现的，所以上面讲的对于倒排索引的内容实际上都是 lucene 外面的内容。
三、倒排索引
首先咱们还不能忘了咱们之前提的搜寻需要，先看下建设倒排索引之后，咱们上述的查问需要会变成什么样子，
这样咱们一输出“前”，借助倒排索引就能够间接定位到合乎查问条件的新诗。
当然这只是一个很大文言的模式来形容倒排索引的简要工作原理。在 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。
相干的名词都是 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/bl…
OK，当初咱们能失去 lucene 倒排索引大抵是个什么样子的了。
四、对于 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 会做的更加精密，
它会把所有的文档分成很多个 block，每个 block 正好蕴含 256 个文档，而后独自对每个文档进行增量编码，计算出存储这个 block 外面所有文档最多须要多少位来保留每个 id，并且把这个位数作为头信息（header）放在每个 block 的后面。这个技术叫 Frame of Reference。
上图也是来自于 ES 官网博客中的一个示例（假如每个 block 只有 3 个文件而不是 256）。
FOR 的步骤能够总结为：
进过最初的位压缩之后，整型数组的类型从固定大小 (8,16,32,64 位)4 种类型, 扩大到了[1-64] 位共 64 种类型。
通过以上的形式能够极大的节俭 posting list 的空间耗费，进步查问性能。不过 ES 为了进步 filter 过滤器查问的性能，还做了更多的工作，那就是 缓存。
Roaring Bitmaps (for filter cache)
在 ES 中，能够应用 filters 来优化查问，ilter 查问只解决文档是否匹配与否，不波及文档评分操作，查问的后果能够被缓存。
对于 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 求并集）之间能够并行，效率更好。
然而，位图有个很显著的毛病，不论业务中理论的元素基数有多少，它占用的内存空间都恒定不变。也就是说不适用于稠密存储。业内对于稠密位图也有很多成熟的压缩计划，lucene 采纳的就是roaring bitmaps。
我这里用简略的形式形容一下这个压缩过程是怎么样，
将 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 时, 应用间接存值的形式更节俭空间。
空间压缩次要体现在:
- 高位聚合 (假如数据中有 100w 个高位雷同的值, 原先须要 100w2byte, 当初只有 12byte)
- 低位压缩
毛病就在于位操作的速度绝对于原生的 bitmap 会有影响。
这就是 trade-off 呀。均衡的艺术。
2. 联结查问
讲完了压缩，咱们再来讲讲联结查问。
先讲简略的，如果查问有 filter cache，那就是间接拿 filter cache 来做计算，也就是说位图来做 AND 或者 OR 的计算。
如果查问的 filter 没有缓存，那么就用 skip list 的形式去遍历磁盘上的 postings list。
以上是三个 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。
心愿本篇文章能给你带来一些播种~
参考文档
- https://www.elastic.co/cn/blo…
- https://www.elastic.co/cn/blo…
- http://blog.mikemccandless.co…
- https://www.infoq.cn/article/…
- https://zhuanlan.zhihu.com/p/…