| 编辑推荐: |
| 本文来自于CSDN,本文总结了Elasticsearch的基础知识及例子、架构、实现细节和其他补充。 |
|
一、基础知识
Elasticsearch是面向文档(document oriented)的，这意味着它可以存储整个对象或文档(document)。然而它不仅仅是存储，还会索引(index)每个文档的内容使之可以被搜索。在Elasticsearch中，你可以对文档（而非成行成列的数据）进行索引、搜索、排序、过滤。这种理解数据的方式与以往完全不同，这也是Elasticsearch能够执行复杂的全文搜索的原因之一。
1、例子
我们来看一个实际的例子，假设有如下的数据：
这里每一行是一个document。每个document都有一个docid。那么给这些document建立的倒排索引就是：
可以看到，倒排索引是per field的，一个字段由一个自己的倒排索引。18,20这些叫做 term，而[1,3]就是posting list。Posting list就是一个int的数组，存储了所有符合某个term的文档id。
2、概念
可以把es看做是面向文档的数据库，它与关系型数据库的名词对照关系如下：
Relational DB => Databases => Tables => Rows => Columns
Elasticsearch => Index=> doc Types => Documents => Fields |
2.1、Index 索引
索引（index）是Elasticsearch对逻辑数据的逻辑存储，所以它可以分为更小的部分。你可以把索引看成关系型数据库的表。Elasticsearch可以把索引存放在一台机器或者分散在多台服务器上，每个索引有一或多个分片（shard），每个分片可以有多个副本（replica）。
2.2、doc Types 文档类型
在Elasticsearch中，一个索引对象可以存储很多不同用途的对象。例如，一个博客应用程序可以保存文章和评论。文档类型让我们轻易地区分单个索引中的不同对象。每个文档可以有不同的结构，但在实际部署中，将文件按类型区分对数据操作有很大帮助。
2.3、 Document 文档
存储在Elasticsearch中的主要实体叫文档（document）。用关系型数据库来类比的话，一个文档相当于数据库表中的一行记录。从客户端的角度看，文档是一个JSON对象。每个文档存储在一个索引中并有一个Elasticsearch自动生成的唯一标识符和文档类型。
2.4、field
文档由多个field组成，从客户端的角度看，就是json对象中的多个kv节点。
二、架构
1、shard
实际上，index仅仅只是一个命名空间来指向一个或多个实际的物理分片(shard)。具体的物理分布粒度关系如下：
一个Elasticsearch Index相当于一个MySQL里的表，不同Index的数据是物理上隔离开来的。Elasticsearch的Index会分成多个Shard存储，一部分Shard是Replica备份。一个Shard是一份本地的存储（一个本地磁盘上的目录），也就是一个Lucene的Index。不同的Shard可能会被分配到不同的主机节点上。一个Lucene Index会存储很多的doc，为了好管理，Lucene把Lucene Index再拆成了Segment存储（子目录）。Segment内的doc数量上限是2的31次方，这样doc id就只需要一个int就可以存储。Segment对应了一些列文件存储索引（倒排表等）和主存储（DocValues等），这些文件内部又分为小的Block进行压缩。
一个shard实际上是一个Lucene实例，在它的能力范围内拥有完整的搜索功能(在处理它自己拥有的数据时有所有的功能)。我们所有文档的索引indexed(动词)和存储工作都是在shard上，但这是透明的，我们不需要直接和shard通信，而是和我们创建的index(名词)通信。
shards是ES将数据分布式在你的集群的关键。想象下shards是数据的容器，文档存储在shards里，而shards被分配在集群的每一个节点Node里。当你的集群规模增长和降低时，ES会自动的在Nodes间迁移shards以保持集群的负载均衡。
2、备份
shard可分为primary shard和replica shard。 在一个index里的每一个文档都属于一个单独的primary shard，所以primary shard的数量决定了你最大能存储的数据量(对应于一个index)。
注意：shard是归属与index的，而不是cluster的。
replica shard是primary shard的拷贝。replica有两个作用： 1.冗余容灾 2.提供读请求服务，例如搜索或读取文档
primary shard的数量在索引创建时确定后不能修改，replica可以在任何时候修改。
3、Shards文档路由
当你对一个文档建立索引时，它仅存储在一个primary shard上。ES是怎么知道一个文档应该属于哪个shard？当你创建一个新的文档时，ES是怎么知道应该把它存储至shard1还是shard2？ 这个过程不能随机无规律的，因为以后我们还要将它取出来。它的路由算法是：
shard = hash(routing) % numberofprimary_shards
routing的值可以是文档的id，也可以是用户自己设置的一个值。hash将会根据routing算出一个数值然后%primaryshards的数量。这也是为什么primary_shards在index创建时就不能修改的原因。
我们可以向这个集群的任何一台NODE发送请求，每一个NODE都有能力处理请求。每一个NODE都知道每一个文档所在的位置所以可以直接将请求路由过去。下面的例子，我们将所有的请求都发送到NODE1。
4、写操作
创建、索引、删除文档都是写操作，这些操作必须在primary shard完全成功后才能拷贝至其对应的replicas上。
1.客户端向Node1发送写操作的请求。
2.Node1使用文档的_id来决定这个文档属于shard0，然后将请求路由至NODE3，P0所在的位置。
3.Node3在P0上执行了请求。如果请求成功，则将请求并行的路由至NODE1 NODE2的R0上。当所有的replicas报告成功后，NODE3向请求的node(NODE1)发送成功报告，NODE1再报告至Client。
当客户端收到执行成功后，操作已经在Primary shard和所有的replica shards上执行成功了。
当然，有一些请求参数可以修改这个逻辑。见原文。
5、读操作
一个文档可以在primary shard和所有的replica shard上读取。
读操作步骤：
1.客户端发送Get请求到NODE1。
2.NODE1使用文档的_id决定文档属于shard 0.shard 0的所有拷贝存在于所有3个节点上。这次，它将请求路由至NODE2。
3.NODE2将文档返回给NODE1，NODE1将文档返回给客户端。 对于读请求，请求节点(NODE1)将在每次请求到来时都选择一个不同的replica。
shard来达到负载均衡。使用轮询策略轮询所有的replica shards。
6、更新操作
更新操作，结合了以上的两个操作：读、写。
步骤：
1.客户端发送更新操作请求至NODE1
2.NODE1将请求路由至NODE3，Primary shard所在的位置
3.NODE3从P0读取文档，改变source字段的JSON内容，然后试图重新对修改后的数据在P0做索引。如果此时这个文档已经被其他的进程修改了，那么它将重新执行3步骤，这个过程如果超过了retryon_conflict设置的次数，就放弃。
4.如果NODE3成功更新了文档，它将并行的将新版本的文档同步到NODE1和NODE2的replica shards重新建立索引。一旦所有的replica
shards报告成功，NODE3向被请求的节点(NODE1)返回成功，然后NODE1向客户端返回成功。
7、查询操作
三、实现细节
1、term dictionary 和 term index
为了实现term的快速查询，使用了什么样的数据结构呢？
假设我们有很多个term，比如：
Carla,Sara,Elin,Ada,Patty,Kate,Selena
如果按照这样的顺序排列，找出某个特定的term一定很慢，因为term没有排序，需要全部过滤一遍才能找出特定的term。排序之后就变成了：
Ada,Carla,Elin,Kate,Patty,Sara,Selena
这样我们可以用二分查找的方式，比全遍历更快地找出目标的term。这个就是 term dictionary。有了term dictionary之后，可以用 logN 次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的（一次random access大概需要10ms的时间）。所以尽量少的读磁盘，有必要把一些数据缓存到内存里。但是整个term dictionary本身又太大了，无法完整地放到内存里。于是就有了term index。term index有点像一本字典的大的章节表。比如：
A开头的term ……………. Xxx页
C开头的term ……………. Xxx页
E开头的term ……………. Xxx页
如果所有的term都是英文字符的话，可能这个term index就真的是26个英文字符表构成的了。但是实际的情况是，term未必都是英文字符，term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term，比如x字符开头的term可能一个都没有，而s开头的term又特别多。实际的term index是一棵trie 树：
例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树。这棵树不会包含所有的term，它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。再加上一些压缩技术（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有term的尺寸的几十分之一，使得用内存缓存整个term index变成可能。整体上来说就是这样的效果。
现在我们可以回答“为什么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更节约磁盘空间。
2、如何联合索引查询？
所以给定查询过滤条件 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的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。那么要如何才能联合使用两个索引呢？有两种办法：
使用skip list数据结构。同时遍历gender和age的posting list，互相skip；
使用bitset数据结构，对gender和age两个filter分别求出bitset，对两个bitset做AN操作。
PostgreSQL 从 8.4 版本开始支持通过bitmap联合使用两个索引，就是利用了bitset数据结构来做到的。当然一些商业的关系型数据库也支持类似的联合索引的功能。Elasticsearch支持以上两种的联合索引方式，如果查询的filter缓存到了内存中（以bitset的形式），那么合并就是两个bitset的AND。如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk的posting list。
1、利用 Skip List 合并
以上是三个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编码。示例如下：
考虑到频繁出现的term（所谓low cardinality的值），比如gender里的男或者女。如果有1百万个文档，那么性别为男的posting list里就会有50万个int值。用Frame of Reference编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然mysql b-tree里也有一个类似的posting list的东西，是未经过这样压缩的。
因为这个Frame of Reference的编码是有解压缩成本的。利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了cpu。
2、利用bitset合并
Bitset是一种很直观的数据结构，对应posting list如：
[1,3,4,7,10]
对应的bitset就是：
[1,0,1,1,0,0,1,0,0,1]
每个文档按照文档id排序对应其中的一个bit。Bitset自身就有压缩的特点，其用一个byte就可以代表8个文档。所以100万个文档只需要12.5万个byte。但是考虑到文档可能有数十亿之多，在内存里保存bitset仍然是很奢侈的事情。而且对于个每一个filter都要消耗一个bitset，比如age=18缓存起来的话是一个bitset，18<=age<25是另外一个filter缓存起来也要一个bitset。
所以秘诀就在于需要有一个数据结构：
可以很压缩地保存上亿个bit代表对应的文档是否匹配filter；
这个压缩的bitset仍然可以很快地进行AND和 OR的逻辑操作。
Lucene使用的这个数据结构叫做 Roaring Bitmap。
其压缩的思路其实很简单。与其保存100个0，占用100个bit。还不如保存0一次，然后声明这个0重复了100遍。
这两种合并使用索引的方式都有其用途。Elasticsearch对其性能有详细的对比（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。简单的结论是：因为Frame of Reference编码是如此 高效，对于简单的相等条件的过滤缓存成纯内存的bitset还不如需要访问磁盘的skip list的方式要快。
3、如何减少文档数？
一种常见的压缩存储时间序列的方式是把多个数据点合并成一行。Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction。类似的vivdcortext使用mysql存储的时候，也把一分钟的很多数据点合并存储到mysql的一行里以减少行数。
这个过程可以示例如下：
可以看到，行变成了列了。每一列可以代表这一分钟内一秒的数据。
Elasticsearch有一个功能可以实现类似的优化效果，那就是Nested Document。我们可以把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档。示例如下：
{timestamp:12:05:01, idc:sz, value1:10,value2:11}
{timestamp:12:05:02, idc:sz, value1:9,value2:9}
{timestamp:12:05:02, idc:sz, value1:18,value:17} |
可以打包成：
{
max_timestamp:12:05:02, min_timestamp: 1205:01, idc:sz,
records: [
{timestamp:12:05:01, value1:10,value2:11}
{timestamp:12:05:02, value1:9,value2:9}
{timestamp:12:05:02, value1:18,value:17}
]
} |
这样可以把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸。
（图片来源：https://www.youtube.com/watch?v=Su5SHc_uJw8，Faceting with Lucene Block Join Query）
在存储的时候，无论父文档还是子文档，对于Lucene来说都是文档，都会有文档Id。但是对于嵌套文档来说，可以保存起子文档和父文档的文档id是连续的，而且父文档总是最后一个。有这样一个排序性作为保障，那么有一个所有父文档的posting list就可以跟踪所有的父子关系。也可以很容易地在父子文档id之间做转换。把父子关系也理解为一个filter，那么查询时检索的时候不过是又AND了另外一个filter而已。前面我们已经看到了Elasticsearch可以非常高效地处理多filter的情况，充分利用底层的索引。
使用了嵌套文档之后，对于term的posting list只需要保存父文档的doc id就可以了，可以比保存所有的数据点的doc id要少很多。如果我们可以在一个父文档里塞入50个嵌套文档，那么posting list可以变成之前的1/50。
四、补充
|
