Elasticsearch

为什么需要ES

回忆时光

许多年前，一个刚结婚的名叫 Shay Banon 的失业开发者，跟着他的妻子去了伦敦，他的妻子在那里学习厨师。在寻找一个赚钱的工作的时候，为了给他的妻子做一个食谱搜索引擎，他开始使用 Lucene 的一个早期版本。
直接使用 Lucene 是很难的，因此 Shay 开始做一个抽象层，Java 开发者使用它可以很简单的给他们的程序添加搜索功能。他发布了他的第一个开源项目 Compass。
后来 Shay 获得了一份工作，主要是高性能，分布式环境下的内存数据网格。这个对于高性能，实时，分布式搜索引擎的需求尤为突出，他决定重写 Compass，把它变为一个独立的服务并取名 Elasticsearch。
第一个公开版本在2010年2月发布，从此以后，Elasticsearch 已经成为了 Github 上最活跃的项目之一，他拥有超过300名 contributors(目前736名 contributors )。一家公司已经开始围绕 Elasticsearch 提供商业服务，并开发新的特性，但是，Elasticsearch 将永远开源并对所有人可>用。

据说，Shay 的妻子还在等着她的食谱搜索引擎…

学习了基础的搜索引擎原理我进而想到大量的数据都是存放在哪里的呢? 为了快速查询数据结构必然发生变化,是不是需要有特殊存储方式呢? 尝试思考如下几种方式来实现.

Sql

对于关系型数据，我们通常采用以下或类似架构去解决查询瓶颈和写入瓶颈(拆表)：
1.通过主从备份解决数据安全性问题；
2.通过数据库代理中间件心跳监测，解决单点故障问题；
3.通过代理中间件将查询语句分发到各个slave节点进行查询，并汇总结果

NoSql

对于Nosql数据库，以mongodb为例，其它原理类似：
1.通过副本备份保证数据安全性；
2.通过节点竞选机制解决单点问题；
3.先从配置库检索分片信息，然后将请求分发到各个节点，最后由路由节点合并汇总结果

内存

但把大量数据存在内存中并不靠谱,原因是内存成本太高了.尤其是对于搜索引擎来说需要存大量的数据.内存存储的解决方案,例如redis还是主要用来做高数缓存的,以此来做数据库就不合适了.

为解决以上问题，从源头着手分析，通常会从以下方式来寻找方法：
1.存储数据时按有序存储；
2.将数据和索引分离；
3.压缩数据；

而这就引出了Elasticsearch。

ES基础

ES是elaticsearch简写， Elasticsearch是一个开源的高扩展的分布式全文检索引擎，它可以近乎实时的存储、检索数据；本身扩展性很好，可以扩展到上百台服务器，处理PB级别的数据。
Elasticsearch也使用Java开发并使用Lucene作为其核心来实现所有索引和搜索的功能，但是它的目的是通过简单的RESTful API来隐藏Lucene的复杂性，从而让全文搜索变得简单。

Lucene & elaticsearch

简化Lucene 使用

对于Lucene可以看: Lucene 入门

这里提到了Lucene 是什么呢? 它就是我们想找的那个特殊的存储结构，但是想要使用它，你必须使用Java来作为开发语言并将其直接集成到你的应用中，更糟糕的是，Lucene非常复杂，你需要深入了解检索的相关知识来理解它是如何工作的。

而ES类似于netty框架帮我们封装了复杂的Nio实现他使用Java开发并使用Lucene作为其核心来实现所有索引和搜索的功能,他提供了简单的RESTful API来隐藏Lucene的复杂性，从而让全文搜索变得简单。

ES做了什么

1.检索相关数据；
2.返回统计结果；
3.速度要快。

优点:

分布式实时文件存储，可将每一个字段存入索引，使其可以被检索到。

实时分析的分布式搜索引擎。
分布式：索引分拆成多个分片，每个分片可有零个或多个副本。集群中的每个数据节点都可承载一个或多个分片，并且协调和处理各种操作；
负载再平衡和路由在大多数情况下自动完成。

可以扩展到上百台服务器，处理PB级别的结构化或非结构化数据。也可以运行在单台PC上（已测试）

支持插件机制，分词插件、同步插件、Hadoop插件、可视化插件等。

原理

首先和我们熟悉的mysql对比一下:

对比

关系型数据库中的数据库（DataBase），等价于ES中的索引（Index）
一个数据库下面有N张表（Table），等价于1个索引Index下面有N多类型（Type）
一个数据库表（Table）下的数据由多行（ROW）多列（column，属性）组成，等价于1个Type由多个文档（Document）和多Field组成。
在一个关系型数据库里面，schema定义了表、每个表的字段，还有表和字段之间的关系。与之对应的，在ES中：Mapping定义索引下的Type的字段处理规则，即索引如何建立、索引类型、是否保存原始索引JSON文档、是否压缩原始JSON文档、是否需要分词处理、如何进行分词处理等。
在数据库中的增insert、删delete、改update、查search操作等价于ES中的增PUT/POST、删Delete、改_update、查GET.

进一步理解

Elasticsearch是面向文档型数据库，一条数据在这里就是一个文档，用JSON作为文档序列化的格式

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

而如果是mysql呢?

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

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

一个 Elasticsearch 集群可以包含多个索引(数据库)，也就是说其中包含了很多类型(表)。这些类型中包含了很多的文档(行)，然后每个文档中又包含了很多的字段(列)。

Elasticsearch的交互，可以使用Java API，也可以直接使用HTTP的Restful API方式，比如我们打算插入一条记录，可以简单发送一个HTTP的请求：

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

其有一下几个核心点:

Cluster：集群。

ES可以作为一个独立的单个搜索服务器。不过，为了处理大型数据集，实现容错和高可用性，ES可以运行在许多互相合作的服务器上。这些服务器的集合称为集群。

Node：节点。

形成集群的每个服务器称为节点。

Shard：分片。

当有大量的文档时，由于内存的限制、磁盘处理能力不足、无法足够快的响应客户端的请求等，一个节点可能不够。这种情况下，数据可以分为较小的分片。每个分片放到不同的服务器上。
当你查询的索引分布在多个分片上时，ES会把查询发送给每个相关的分片，并将结果组合在一起，而应用程序并不知道分片的存在。即：这个过程对用户来说是透明的。

Replia：副本。

为提高查询吞吐量或实现高可用性，可以使用分片副本。
副本是一个分片的精确复制，每个分片可以有零个或多个副本。ES中可以有许多相同的分片，其中之一被选择更改索引操作，这种特殊的分片称为主分片。
当主分片丢失时，如：该分片所在的数据不可用时，集群将副本提升为新的主分片。

全文检索。

全文检索就是对一篇文章进行索引，可以根据关键字搜索，类似于mysql里的like语句。
全文索引就是把内容根据词的意义进行分词，然后分别创建索引，例如”你们的激情是因为什么事情来的” 可能会被分词成：“你们“，”激情“，“什么事情“，”来“ 等token，这样当你搜索“你们” 或者 “激情” 都会把这句搜出来。

数据结构

主要就是其索引的建立思路

将磁盘里的东西尽量搬进内存，减少磁盘随机读取次数(同时也利用磁盘顺序读特性)，结合各种奇技淫巧的压缩算法，用及其苛刻的态度使用内存。
并且其一切设计都是为了提高搜索的性能其余的部分肯定会有牺牲,比如插入/更新

倒排索引

这就要引出其核心数据结构倒排索引了对于其的简单理解可以先看一下之前的博客#搜索引擎入门这里结合ES详细介绍一下:

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

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

ID是Elasticsearch自建的文档id，那么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都建立了一个倒排索引，Kate, John, 24, Female这些叫term，而[1,2]就是Posting List。Posting list就是一个int的数组，存储了所有符合某个term的文档id。

接下来才是关键:

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

Term Dictionary

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

Term Index

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

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

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

而FST是什么呢?

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前缀)映射到序号：0，1，2，3，4，5(term dictionary的block位置)。最简单的做法就是定义个Map<String, Integer>，大家找到自己的位置对应入座就好了，但从内存占用少的角度想想，有没有更优的办法呢？答案就是：FST

O表示一种状态

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

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

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

压缩

我们学习mysql的时候肯定知道如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。
但对于搜索来说总不能不让用户搜索这种字段吧,例如男/女这样的. ES对于这种索引就会进行压缩.

压缩方法
ES为了压缩索引真的是不择手段。在压缩过程中使用如下技巧,它会按依次检测以下压缩模式:

如果所有的数值各不相同（或缺失），设置一个标记并记录这些值
如果这些值小于 256，将使用一个简单的编码表
如果这些值大于 256，检测是否存在一个最大公约数
如果没有存在最大公约数，从最小的数值开始，统一计算偏移量(增量)进行编码

Frame Of Reference

增量编码压缩，将大数变小数，按字节存储

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

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

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

Roaring bitmaps

说到Roaring bitmaps，就必须先从bitmap说起。Bitmap是一种数据结构，假设有某个posting list：
[1,3,4,7,10]
对应的bitmap就是：
[1,0,1,1,0,0,1,0,0,1]

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

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

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

为什么是以65535为界限?

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

那为什么用4096来区分采用数组还是bitmap的阀值呢？

这个是从内存大小考虑的，当block块里元素超过4096后，用bitmap更剩空间：采用bitmap需要的空间是恒定的: 65536/8 = 8192bytes 而如果采用short[]，所需的空间是: 2*N(N为数组元素个数) N=4096刚好是边界:

你也许会想 "好吧，貌似对数字很好，不知道字符串怎么样？" 通过借助顺序表（ordinal table），String 类型也是类似进行编码的。String 类型是去重之后存放到顺序表的，通过分配一个 ID，然后通过数字类型的 ID 构建 Doc Values。这样String类型和数值类型可以达到同样的压缩效果。

而顺序表本身也有很多压缩技巧，比如固定长度、变长或是前缀字符编码等等。

联合索引

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

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

先看看跳表的数据结构：

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

假设有下面三个posting list需要联合索引：

如果使用跳表，对最短的posting list中的每个id，逐个在另外两个posting list中查找看是否存在，最后得到交集的结果。
如果使用bitset，就很直观了，直接按位与，得到的结果就是最后的交集。

最后

注意点

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

详细使用

Elasticsearch权威指南1
Elasticsearch权威指南2

ES对外接口

JAVA API接口
常见的增、删、改、查操作实现：
RESTful API接口

论坛

1）国外：https://discuss.elastic.co/
2）国内：http://elasticsearch.cn/