Elastic基础原理介绍

目录

介绍

基本概念

索引

Elasticsearch是如何做到快速索引的

总结和思考

介绍

       Elasticsearch 是一个分布式可扩展的实时搜索和分析引擎,一个建立在全文搜索引擎 Apache Lucene(TM) 基础上的搜索引擎.当然 Elasticsearch 并不仅仅是 Lucene 那么简单&＃xff0c;它不仅包括了全文搜索功能&＃xff0c;还可以进行以下工作:

• 分布式实时文件存储&＃xff0c;并将每一个字段都编入索引&＃xff0c;使其可以被搜索。
• 实时分析的分布式搜索引擎。
• 可以扩展到上百台服务器&＃xff0c;处理PB级别的结构化或非结构化数据。

基本概念

       先说Elasticsearch的文件存储&＃xff0c;Elasticsearch是面向文档型数据库&＃xff0c;一条数据在这里就是一个文档&＃xff0c;用JSON作为文档序列化的格式&＃xff0c;比如下面这条用户数据&＃xff1a;

{"name" : "John","sex" : "Male","age" : 25,"birthDate": "1990/05/01","about" : "I love to go rock climbing","interests": [ "sports", "music" ]
}


       用Mysql这样的数据库存储就会容易想到建立一张User表&＃xff0c;有balabala的字段等&＃xff0c;在Elasticsearch里这就是一个文档&＃xff0c;当然这个文档会属于一个User的类型&＃xff0c;各种各样的类型存在于一个索引当中。这里有一份简易的将Elasticsearch和关系型数据术语对照表:

关系数据库 ⇒ 数据库 ⇒ 表 ⇒ 行 ⇒ 列(Columns)Elasticsearch ⇒ 索引(Index) ⇒ 类型(type) ⇒ 文档(Docments) ⇒ 字段(Fields)


       一个 Elasticsearch 集群可以包含多个索引(数据库)&＃xff0c;也就是说其中包含了很多类型(表)。这些类型中包含了很多的文档(行)&＃xff0c;然后每个文档中又包含了很多的字段(列)。Elasticsearch的交互&＃xff0c;可以使用Java API&＃xff0c;也可以直接使用HTTP的Restful API方式&＃xff0c;比如我们打算插入一条记录&＃xff0c;可以简单发送一个HTTP的请求&＃xff1a;

PUT /megacorp/employee/1
{"name" : "John","sex" : "Male","age" : 25,"about" : "I love to go rock climbing","interests": [ "sports", "music" ]
}


       更新&＃xff0c;查询也是类似这样的操作&＃xff0c;具体操作手册可以参见Elasticsearch权威指南

索引

       Elasticsearch最关键的就是提供强大的索引能力了&＃xff0c;其实InfoQ的这篇时间序列数据库的秘密(2)——索引写的非常好&＃xff0c;我这里也是围绕这篇结合自己的理解进一步梳理下&＃xff0c;也希望可以帮助大家更好的理解这篇文章。

       Elasticsearch索引的精髓&＃xff1a;

一切设计都是为了提高搜索的性能

       另一层意思&＃xff1a;为了提高搜索的性能&＃xff0c;难免会牺牲某些其他方面&＃xff0c;比如插入/更新&＃xff0c;否则其他数据库不用混了。前面看到往Elasticsearch里插入一条记录&＃xff0c;其实就是直接PUT一个json的对象&＃xff0c;这个对象有多个fields&＃xff0c;比如上面例子中的name, sex, age, about, interests&＃xff0c;那么在插入这些数据到Elasticsearch的同时&＃xff0c;Elasticsearch还默默的为这些字段建立索引--倒排索引&＃xff0c;因为Elasticsearch最核心功能是搜索。

Elasticsearch是如何做到快速索引的

I       nfoQ那篇文章里说Elasticsearch使用的倒排索引比关系型数据库的B-Tree索引快&＃xff0c;为什么呢&＃xff1f;

       什么是B-Tree索引?

       上大学读书时老师教过我们&＃xff0c;二叉树查找效率是logN&＃xff0c;同时插入新的节点不必移动全部节点&＃xff0c;所以用树型结构存储索引&＃xff0c;能同时兼顾插入和查询的性能。因此在这个基础上&＃xff0c;再结合磁盘的读取特性(顺序读/随机读)&＃xff0c;传统关系型数据库采用了B-Tree/B&＃43;Tree这样的数据结构&＃xff1a;

       为了提高查询的效率&＃xff0c;减少磁盘寻道次数&＃xff0c;将多个值作为一个数组通过连续区间存放&＃xff0c;一次寻道读取多个数据&＃xff0c;同时也降低树的高度。什么是倒排索引?

       继续上面的例子&＃xff0c;假设有这么几条数据(为了简单&＃xff0c;去掉about, interests这两个field):

| ID | Name | Age | Sex |
| -- |:------------:| -----:| -----:|
| 1 | Kate | 24 | Female
| 2 | John | 24 | Male
| 3 | Bill | 29 | Male


I       D是Elasticsearch自建的文档id&＃xff0c;那么Elasticsearch建立的索引如下:

Name:

| Term | Posting List |
| -- |:----:|
| Kate | 1 |
| John | 2 |
| Bill | 3 |


Age:

| Term | Posting List |
| -- |:----:|
| 24 | [1,2] |
| 29 | 3 |


Sex:

| Term | Posting List |
| -- |:----:|
| Female | 1 |
| Male | [2,3] |


Posting List

       Elasticsearch分别为每个field都建立了一个倒排索引&＃xff0c;Kate, John, 24, Female这些叫term&＃xff0c;而[1,2]就是Posting List。Posting list就是一个int的数组&＃xff0c;存储了所有符合某个term的文档id。

       通过posting list这种索引方式似乎可以很快进行查找&＃xff0c;比如要找age&＃61;24的同学&＃xff0c;爱回答问题的小明马上就举手回答&＃xff1a;我知道&＃xff0c;id是1&＃xff0c;2的同学。但是&＃xff0c;如果这里有上千万的记录呢&＃xff1f;如果是想通过name来查找呢&＃xff1f;

Term Dictionary

       Elasticsearch为了能快速找到某个term&＃xff0c;将所有的term排个序&＃xff0c;二分法查找term&＃xff0c;logN的查找效率&＃xff0c;就像通过字典查找一样&＃xff0c;这就是Term Dictionary。现在再看起来&＃xff0c;似乎和传统数据库通过B-Tree的方式类似啊&＃xff0c;为什么说比B-Tree的查询快呢&＃xff1f;

Term Index

       B-Tree通过减少磁盘寻道次数来提高查询性能&＃xff0c;Elasticsearch也是采用同样的思路&＃xff0c;直接通过内存查找term&＃xff0c;不读磁盘&＃xff0c;但是如果term太多&＃xff0c;term dictionary也会很大&＃xff0c;放内存不现实&＃xff0c;于是有了Term Index&＃xff0c;就像字典里的索引页一样&＃xff0c;A开头的有哪些term&＃xff0c;分别在哪页&＃xff0c;可以理解term index是一颗树&＃xff1a;

       这棵树不会包含所有的term&＃xff0c;它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset&＃xff0c;然后从这个位置再往后顺序查找。

       所以term index不需要存下所有的term&＃xff0c;而仅仅是他们的一些前缀与Term Dictionary的block之间的映射关系&＃xff0c;再结合FST(Finite State Transducers)的压缩技术&＃xff0c;可以使term index缓存到内存中。从term index查到对应的term dictionary的block位置之后&＃xff0c;再去磁盘上找term&＃xff0c;大大减少了磁盘随机读的次数。

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

       假设我们现在要将mop, moth, pop, star, stop and top(term index里的term前缀)映射到序号&＃xff1a;0&＃xff0c;1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5(term dictionary的block位置)。最简单的做法就是定义个Map&＃xff0c;大家找到自己的位置对应入座就好了&＃xff0c;但从内存占用少的角度想想&＃xff0c;有没有更优的办法呢&＃xff1f;答案就是&＃xff1a;FST(理论依据在此&＃xff0c;但我相信99%的人不会认真看完的)

       ⭕️表示一种状态

       -->表示状态的变化过程&＃xff0c;上面的字母/数字表示状态变化和权重

       将单词分成单个字母通过⭕️和-->表示出来&＃xff0c;0权重不显示。如果⭕️后面出现分支&＃xff0c;就标记权重&＃xff0c;最后整条路径上的权重加起来就是这个单词对应的序号。

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

       FST以字节的方式存储所有的term&＃xff0c;这种压缩方式可以有效的缩减存储空间&＃xff0c;使得term index足以放进内存&＃xff0c;但这种方式也会导致查找时需要更多的CPU资源。

后面的更精彩&＃xff0c;看累了的同学可以喝杯咖啡……

压缩技巧

       Elasticsearch里除了上面说到用FST压缩term index外&＃xff0c;对posting list也有压缩技巧。 
小明喝完咖啡又举手了:"posting list不是已经只存储文档id了吗&＃xff1f;还需要压缩&＃xff1f;"

       嗯&＃xff0c;我们再看回最开始的例子&＃xff0c;如果Elasticsearch需要对同学的性别进行索引(这时传统关系型数据库已经哭晕在厕所……)&＃xff0c;会怎样&＃xff1f;如果有上千万个同学&＃xff0c;而世界上只有男/女这样两个性别&＃xff0c;每个posting list都会有至少百万个文档id。 Elasticsearch是如何有效的对这些文档id压缩的呢&＃xff1f;

Frame Of Reference

增量编码压缩&＃xff0c;将大数变小数&＃xff0c;按字节存储

       首先&＃xff0c;Elasticsearch要求posting list是有序的(为了提高搜索的性能&＃xff0c;再任性的要求也得满足)&＃xff0c;这样做的一个好处是方便压缩&＃xff0c;看下面这个图例&＃xff1a; 

如果数学不是体育老师教的话&＃xff0c;还是比较容易看出来这种压缩技巧的。

       原理就是通过增量&＃xff0c;将原来的大数变成小数仅存储增量值&＃xff0c;再精打细算按bit排好队&＃xff0c;最后通过字节存储&＃xff0c;而不是大大咧咧的尽管是2也是用int(4个字节)来存储。

Roaring bitmaps

说到Roaring bitmaps&＃xff0c;就必须先从bitmap说起。Bitmap是一种数据结构&＃xff0c;假设有某个posting list&＃xff1a;

[1,3,4,7,10]

对应的bitmap就是&＃xff1a;

[1,0,1,1,0,0,1,0,0,1]

       非常直观&＃xff0c;用0/1表示某个值是否存在&＃xff0c;比如10这个值就对应第10位&＃xff0c;对应的bit值是1&＃xff0c;这样用一个字节就可以代表8个文档id&＃xff0c;旧版本(5.0之前)的Lucene就是用这样的方式来压缩的&＃xff0c;但这样的压缩方式仍然不够高效&＃xff0c;如果有1亿个文档&＃xff0c;那么需要12.5MB的存储空间&＃xff0c;这仅仅是对应一个索引字段(我们往往会有很多个索引字段)。于是有人想出了Roaring bitmaps这样更高效的数据结构。

       Bitmap的缺点是存储空间随着文档个数线性增长&＃xff0c;Roaring bitmaps需要打破这个魔咒就一定要用到某些指数特性&＃xff1a;

       将posting list按照65535为界限分块&＃xff0c;比如第一块所包含的文档id范围在0~65535之间&＃xff0c;第二块的id范围是65536~131071&＃xff0c;以此类推。再用<商&＃xff0c;余数>的组合表示每一组id&＃xff0c;这样每组里的id范围都在0~65535内了&＃xff0c;剩下的就好办了&＃xff0c;既然每组id不会变得无限大&＃xff0c;那么我们就可以通过最有效的方式对这里的id存储。

       细心的小明这时候又举手了:"为什么是以65535为界限?"

       程序员的世界里除了1024外&＃xff0c;65535也是一个经典值&＃xff0c;因为它&＃61;2^16-1&＃xff0c;正好是用2个字节能表示的最大数&＃xff0c;一个short的存储单位&＃xff0c;注意到上图里的最后一行“If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”&＃xff0c;如果是大块&＃xff0c;用节省点用bitset存&＃xff0c;小块就豪爽点&＃xff0c;2个字节我也不计较了&＃xff0c;用一个short[]存着方便。

       那为什么用4096来区分大块还是小块呢&＃xff1f;

       个人理解&＃xff1a;都说程序员的世界是二进制的&＃xff0c;4096*2bytes &＃xff1d; 8192bytes <1KB, 磁盘一次寻道可以顺序把一个小块的内容都读出来&＃xff0c;再大一位就超过1KB了&＃xff0c;需要两次读。

联合索引

上面说了半天都是单field索引&＃xff0c;如果多个field索引的联合查询&＃xff0c;倒排索引如何满足快速查询的要求呢&＃xff1f;

• 利用跳表(Skip list)的数据结构快速做“与”运算&＃xff0c;或者
• 利用上面提到的bitset按位“与”

先看看跳表的数据结构&＃xff1a;

       将一个有序链表level0&＃xff0c;挑出其中几个元素到level1及level2&＃xff0c;每个level越往上&＃xff0c;选出来的指针元素越少&＃xff0c;查找时依次从高level往低查找&＃xff0c;比如55&＃xff0c;先找到level2的31&＃xff0c;再找到level1的47&＃xff0c;最后找到55&＃xff0c;一共3次查找&＃xff0c;查找效率和2叉树的效率相当&＃xff0c;但也是用了一定的空间冗余来换取的。

假设有下面三个posting list需要联合索引&＃xff1a;

       如果使用跳表&＃xff0c;对最短的posting list中的每个id&＃xff0c;逐个在另外两个posting list中查找看是否存在&＃xff0c;最后得到交集的结果。

如果使用bitset&＃xff0c;就很直观了&＃xff0c;直接按位与&＃xff0c;得到的结果就是最后的交集。

总结和思考

Elasticsearch的索引思路:

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

所以&＃xff0c;对于使用Elasticsearch进行索引时需要注意:

• 不需要索引的字段&＃xff0c;一定要明确定义出来&＃xff0c;因为默认是自动建索引的
• 同样的道理&＃xff0c;对于String类型的字段&＃xff0c;不需要analysis的也需要明确定义出来&＃xff0c;因为默认也是会analysis的
• 选择有规律的ID很重要&＃xff0c;随机性太大的ID(比如java的UUID)不利于查询

关于最后一点&＃xff0c;个人认为有多个因素:

       其中一个(也许不是最重要的)因素: 上面看到的压缩算法&＃xff0c;都是对Posting list里的大量ID进行压缩的&＃xff0c;那如果ID是顺序的&＃xff0c;或者是有公共前缀等具有一定规律性的ID&＃xff0c;压缩比会比较高&＃xff1b;

       另外一个因素: 可能是最影响查询性能的&＃xff0c;应该是最后通过Posting list里的ID到磁盘中查找Document信息的那步&＃xff0c;因为Elasticsearch是分Segment存储的&＃xff0c;根据ID这个大范围的Term定位到Segment的效率直接影响了最后查询的性能&＃xff0c;如果ID是有规律的&＃xff0c;可以快速跳过不包含该ID的Segment&＃xff0c;从而减少不必要的磁盘读次数&＃xff0c;具体可以参考这篇如何选择一个高效的全局ID方案(评论也很精彩)

备注&＃xff1a;原文地址