image.png
为什么 Elasticsearch/Lucene 检索可以比 mysql 快
Mysql 只有 term dictionary 这一层，是以 b-tree 排序的方式存储在磁盘上的。检索一个 term 需要若干次的 random access 的磁盘操作。而 Lucene 在 term dictionary 的基础上添加了 term index 来加速检索，term index 以树的形式缓存在内存中。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。
额外值得一提的两点是：term index 在内存中是以 FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term dictionary 在磁盘上是以分 block 的方式保存的，一个 block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。这样 term dictionary 可以比 b-tree 更节约磁盘空间。
两者对比
对于倒排索引，要分两种情况：
1、基于分词后的全文检索
这种情况是es的强项，而对于mysql关系型数据库而言完全是灾难
因为es分词后，每个字都可以利用FST高速找到倒排索引的位置，并迅速获取文档id列表
但是对于mysql检索中间的词只能全表扫（如果不是搜头几个字符）
2、精确检索
这种情况我想两种相差不大，有些情况下mysql的可能会更快些
如果mysql的非聚合索引用上了覆盖索引，无需回表，则速度可能更快
es还是通过FST找到倒排索引的位置并获取文档id列表，再根据文档id获取文档并根据相关度算分进行排序，但es还有个杀手锏，即天然的分布式使得在大数据量面前可以通过分片降低每个分片的检索规模，并且可以并行检索提升效率
用filter时更是可以直接跳过检索直接走缓存
什么是Term Index？
将分词后的term进行排序索引，类似的mysql对于"term"(即主键，或者索引键)只是做了排序, 并且是大部分是放在磁盘上的，只有B+树的上层才是放在内存中的，查询仍然需要logN的访问磁盘，而ES将term分词排序后还做了一次索引，term index，即将term的通用前缀取出，构建成Trie树
通过这个树可以快速的定位到Term dictionary的本term的offset，再经过顺序查找，便可以很快找到本term的posting list。
什么是FST？
答: Finite State Transducer
FST有两个优点：1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；2）查询速度快。O(len(str))的查询时间复杂度。
3 FST原理简析
lucene从4开始大量使用的数据结构是FST（Finite State Transducer）。FST有两个优点：1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；2）查询速度快。O(len(str))的查询时间复杂度。
下面简单描述下FST的构造过程（工具演示：[http://examples.mikemccandless.com/fst.py?terms=&cmd=Build+it%21](http://examples.mikemccandless.com/fst.py?terms=&cmd=Build+it%21)）。我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST（注：必须已排序）。
1）插入“cat”
插入cat，每个字母形成一条边，其中t边指向终点。
image.png
2）插入“deep”
与前一个单词“cat”进行最大前缀匹配，发现没有匹配则直接插入，P边指向终点。
image.png
3）插入“do”
与前一个单词“deep”进行最大前缀匹配，发现是d，则在d边后增加新边o，o边指向终点。
image.png
4）插入“dog”
与前一个单词“do”进行最大前缀匹配，发现是do，则在o边后增加新边g，g边指向终点。
image.png
5）插入“dogs”
image.png
最终我们得到了如上一个有向无环图。利用该结构可以很方便的进行查询，如给定一个term “dog”，我们可以通过上述结构很方便的查询存不存在，甚至我们在构建过程中可以将单词与某一数字、单词进行关联，从而实现key-value的映射。
Term Dictionary为什么节约空间?
Term dictionary 在磁盘上是以分 block 的方式保存的，一个 block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。这样 term dictionary 可以比 b-tree 更节约磁盘空间。
3.6 联合索引查询
以上都是单field索引，如果多个field索引的联合查询，比如查询age=18 AND gender=女，倒排索引如何满足快速查询的要求呢？大致过程如下：根据过滤条件 age=18 的先从term index找到18在term dictionary的大概位置，然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针。然后再查询gender=女的过程也是类似的。最后得出 age=18 AND gender=女，就是把两个 posting list 做一个“与”的合并。
这个理论上的“与”合并的操作可不容易。对于mysql来说，如果你给age和gender两个字段都建立了索引，查询的时候只会选择其中最selective的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。那么要如何才能联合使用两个索引呢？有两种办法：
a）使用skip list数据结构。同时遍历gender和age的posting list，互相skip；
b）使用bitset数据结构，对gender和age两个filter分别求出bitset，对两个bitset做AND操作。
利用 Skip List 合并
image.png
以上是三个posting list。我们现在需要把它们用AND的关系合并，得出posting list的交集。首先选择最短的posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小。
整个过程如下:
Next -> 2
Advance(2) -> 13
Advance(13) -> 13
Already on 13
Advance(13) -> 13 MATCH!!!
Next -> 17
Advance(17) -> 22
Advance(22) -> 98
Advance(98) -> 98
Advance(98) -> 98 MATCH!!!
最后得出的交集是[13,98]，所需的时间比完整遍历三个posting list要快得多。但是前提是每个list需要指出Advance这个操作，快速移动指向的位置。什么样的list可以这样Advance往前做蛙跳？skip list：
从概念上来说，对于一个很长的posting list，比如：
[1,3,13,101,105,108,255,256,257]
我们可以把这个list分成三个block：
[1,3,13] [101,105,108] [255,256,257]
然后可以构建出skip list的第二层：
[1,101,255]
1,101,255分别指向自己对应的block。这样就可以很快地跨block的移动指向位置了。
Lucene自然会对block再次进行压缩。其压缩方式是上文提到的Frame Of Reference。补充一点的是，利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了cpu。
利用bitset合并
如果使用bitset，就很直观了，直接按位与，得到的结果就是最后的交集。
倒排索引·
img.jpg
搜索时
image.png
当我们搜索关键字“pie”时，搜索引擎快速查找匹配到的记录
Filesystem Cache
查询亿级数据毫秒级返回
性能优化的杀手锏：Filesystem Cache
你往 ES 里写的数据，实际上都写到磁盘文件里去了，查询的时候，操作系统会将磁盘文件里的数据自动缓存到 Filesystem Cache 里面去。
整个过程，如下图所示：
image.png
ES 的搜索引擎严重依赖于底层的 Filesystem Cache，你如果给 Filesystem Cache 更多的内存，尽量让内存可以容纳所有的 IDX Segment File 索引数据文件，那么你搜索的时候就基本都是走内存的，性能会非常高。
性能差距究竟可以有多大？我们之前很多的测试和压测，如果走磁盘一般肯定上秒，搜索性能绝对是秒级别的，1 秒、5 秒、10 秒。
但如果是走 Filesystem Cache，是走纯内存的，那么一般来说性能比走磁盘要高一个数量级，基本上就是毫秒级的，从几毫秒到几百毫秒不等。
来看一个真实的案例：某个公司 ES 节点有 3 台机器，每台机器看起来内存很多 64G，总内存就是 64 * 3 = 192G。
每台机器给 ES JVM Heap 是 32G，那么剩下来留给 Filesystem Cache 的就是每台机器才 32G，总共集群里给 Filesystem Cache 的就是 32 * 3 = 96G 内存。
而此时，整个磁盘上索引数据文件，在 3 台机器上一共占用了 1T 的磁盘容量，ES 数据量是 1T，那么每台机器的数据量是 300G。
这样性能好吗？
Filesystem Cache 的内存才 100G，十分之一的数据可以放内存，其他的都在磁盘，然后你执行搜索操作，大部分操作都是走磁盘，性能肯定差。
归根结底，你要让 ES 性能好，最佳的情况下，就是你的机器的内存，至少可以容纳你的总数据量的一半。
根据我们自己的生产环境实践经验，最佳的情况下，是仅仅在 ES 中就存少量的数据。
也就是说，你要用来搜索的那些索引，如果内存留给 Filesystem Cache 的是 100G，那么你就将索引数据控制在 100G 以内。这样的话，你的数据几乎全部走内存来搜索，性能非常之高，一般可以在1秒以内。
比如说你现在有一行数据：id，name，age .... 30 个字段。但是你现在搜索，只需要根据 id，name，age 三个字段来搜索。
如果你傻乎乎往 ES 里写入一行数据所有的字段，就会导致 90% 的数据是不用来搜索的。
但是呢，这些数据硬是占据了 ES 机器上的 Filesystem Cache 的空间，单条数据的数据量越大，就会导致 Filesystem Cahce 能缓存的数据就越少。
其实，仅仅写入 ES 中要用来检索的少数几个字段就可以了，比如说就写入 es id，name，age 三个字段。
然后你可以把其他的字段数据存在 MySQL/HBase 里，我们一般是建议用 ES + HBase 这么一个架构。
网友评论