搜索功能

问题

• 分库分表数据查询（存储）
• 大数据量亿级别/PB级别查询（性能）
• 分词查询

全文索引

全文索引时将存储在数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获取全文中有关章，节，段，句，词等信息，也可以进行各种统计和分析

定义

全文索引技术是搜索引擎的关键技术。
试想在1M大小的文件中搜索一个词，可能需要几秒，在100M的文件中可能需要几十秒，如果在更大的文件中搜索那么就需要更大的系统开销，这样的开销是不现实的。
所以在这样的矛盾下出现了全文索引技术，有时候有人叫倒排文档技术。

原理

先定义一个词库，然后在文章中查找每个词条(term)出现的频率和位置，把这样的频率和位置信息按照词库的顺序归纳，这样就相当于对文件建立了一个以词库为目录的索引，这样查找某个词的时候就能很快的定位到该词出现的位置。

问题

问题在处理英文文档的时候显然这样的方式是非常好的，因为英文自然的被空格分成若干词，只要我们有足够大的词汇库就能很好的处理。但是亚洲文字因为没有空格作为断词标志，所以就很难判断一个词，而且人们使用的词汇在不断的变化，而维护一个可扩展的词汇库的成本是很高的，所以问题出现了。

解决方案

解决出现这样的问题使“分词”成为全文索引的关键技术。
有两种基本的方法：

• 二元法
  它把所有有可能的每两两汉字的组合看为一个词组，这样就没有维护词库的开销。
• 词库法
  它使使用词库中的词作为切分的标准，这样也出现了词库跟不上词汇发展的问题，除非你维护词库。

实际上现在很多著名的搜索引擎都使用了多种分词的办法，比如“正向最大匹配”+“逆向最大匹配”，基于统计学的新词识别，自动维护词库等技术，但是显然这样的技术还没有做到完美。

技术方案

• mysql 全文索引，数据量少的情况下
• lucene 单实例搜索引擎，可以支持分库分表的整合查询
• es 基于lucene实现的分布式搜索引擎

ES介绍

使用场景

• 维基百科
• stackoverflow
• github
• ebay
• 日志数据分析
• …

相关概念

cluster：代表一个集群，集群中有多个节点，其中有一个为主节点，这个主节点是可以通过选举产生的，主从节点是对于集群内部来说的。es的一个概念就是去中心化，字面上理解就是无中心节点，这是对于集群外部来说的，因为从外部来看es集群，在逻辑上是个整体，你与任何一个节点的通信和与整个es集群通信是等价的。
shards：代表索引分片，es可以把一个完整的索引分成多个分片，这样的好处是可以把一个大的索引拆分成多个，分布到不同的节点上。构成分布式搜索。分片的数量只能在索引创建前指定，并且索引创建后不能更改。
replicas：代表索引副本，es可以设置多个索引的副本，副本的作用一是提高系统的容错性，当某个节点某个分片损坏或丢失时可以从副本中恢复。二是提高es的查询效率，es会自动对搜索请求进行负载均衡。
recovery：代表数据恢复或叫数据重新分布，es在有节点加入或退出时会根据机器的负载对索引分片进行重新分配，挂掉的节点重新启动时也会进行数据恢复。
river：代表es的一个数据源，也是其它存储方式（如：数据库）同步数据到es的一个方法。它是以插件方式存在的一个es服务，通过读取river中的数据并把它索引到es中，官方的river有couchDB的，RabbitMQ的，Twitter的，Wikipedia的。
gateway：代表es索引快照的存储方式，es默认是先把索引存放到内存中，当内存满了时再持久化到本地硬盘。gateway对索引快照进行存储，当这个es集群关闭再重新启动时就会从gateway中读取索引备份数据。es支持多种类型的gateway，有本地文件系统（默认），分布式文件系统，Hadoop的HDFS和amazon的s3云存储服务。
discovery.zen：代表es的自动发现节点机制，es是一个基于p2p的系统，它先通过广播寻找存在的节点，再通过多播协议来进行节点之间的通信，同时也支持点对点的交互。
Transport：代表es内部节点或集群与客户端的交互方式，默认内部是使用tcp协议进行交互，同时它支持http协议（json格式）、thrift、servlet、memcached、zeroMQ等的传输协议（通过插件方式集成）。

特点

• NRT near real time 近实时
• 集群cluster
• Node 节点
• Index 索引
• Document 文档
• Field 字段

分片

• 主分片
• 备份分片

索引

• 传统数据库索引：二叉搜索树、b树、b+树（磁盘查询优化）
• ES倒排索引

正排索引

正排索引是指文档ID为key，表中记录每个关键词出现的次数，查找时扫描表中的每个文档中字的信息，直到找到所有包含查询关键字的文档。
试想一下，我们搜一个关键字（Tom），当100个网页的10个网页含有Tom这个关键字。但是由于是正排是doc id 作为索引的，所以我们不得不把100个网页都扫描一遍，然后找出其中含有Tom的10个网页。然后再进行rank，sort等。效率就比较低了。不过与之相比的是，正排这种模式容易维护。由于是采用doc 作为key来存储的，所以新增网页的时候，只要在末尾新增一个key，然后把词、词出现的频率和位置信息分析完成后就可以使用了。
所以正排的优点是：易维护；缺点是搜索的耗时太长

Postint list 倒排索引

倒排是以word作为关键索引。ES默认会为每个field都建立一个倒排索引，Posting list就是一个int的数组，存储了所有符合某个term的文档id。
我们拿到三条结构化数据：

ID	Name	Age	Sex
1	aa	18	Female
2	bb	50	Male
3	cc	18	Male

ID是Elasticsearch自建的文档id，那么Elasticsearch建立的索引如下:
Name:

Term	Posting List
aa	1
bb	2
cc	3

Age:

Term	Posting List
50	2
18	[1,3]

Sex:

Term	Posting List
Female	1
Male	[2,3]

倒排包含两部分：
1、由不同的索引词（index term）组成的索引表，称为“词典”（lexicon）。其中包含了各种词汇，以及这些词汇的统计信息（如出现频率nDocs），这些统计信息可以直接用于各种排名算法。
2、由每个索引词出现过的文档集合，以及命中位置等信息构成。也称为“记录表”。就是正排索引产生的那张表。当然这部分可以没有。具体看自己的业务需求了。

Term Dictionary

但如何高效的在这个索引结构中查询到aa呢，Elasticsearch为了能快速找到某个term，将所有的term排个序，二分法查找term，log(N)的查找效
率，就像通过字典查找一样，这就是Term Dictionary，只要我们将 Term 有序排列，便可以使用二叉树搜索树的数据结构在o(logn) 下查询到数据。

将一个文本拆分成一个一个独立 Term 的过程其实就是我们常说的分词。

而将所有 Term 合并在一起就是一个 Term Dictionary ，也可以叫做单词词典。

英文的分词相对简单，只需要通过空格、标点符号将文本分隔便能拆词，中文则相对复杂，但也有许多开源工具做支持（由于不是本文重点，对分词感兴趣的可以自行搜索）。
当我们的文本量巨大时，分词后的 Term 也会很多，这样一个倒排索引的数据结构如果存放于内存那肯定是不够存的，但如果像 MySQL 那样存放于磁盘，效率也没那么高。

Term Index

所以我们可以选择一个折中的方法，既然无法将整个 Term Dictionary 放入内存中，那我们可以为 Term Dictionary 创建一个索引然后放入内存中。
这样便可以高效的查询 Term Dictionary ，最后再通过 Term Dictionary 查询到 Posting List 。

相对于 MySQL 中的 B+树 来说也会减少了几次 磁盘IO 。

如果我们是以 j 开头的 Term 进行搜索，首先第一步就是通过在内存中的 Term Index 查询出以 j 打头的 Term 在 Term Dictionary 字典文件中的哪个位置（这个位置可以是一个文件指针，可能是一个区间范围）。

紧接着在将这个位置区间中的所有 Term 取出，由于已经排好序，便可通过二分查找快速定位到具体位置；这样便可查询出 Posting List。

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

更多优化

FST 有限状态传感器

Finite StateTransducers 简称 FST，通常中文译作有穷状态转换器或者有限状态传感器
FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.
FST是一项将一个字节序列映射到block块的技术

压缩技巧之Frame Of Reference

Elasticsearch里除了上面说到用FST压缩term index外，对posting list也有压缩技巧

Roaring Bitmaps 咆哮位图

Roaring Bitmap是由int数组和bitmap这两个数据结构改良过的成果——int数组速度快但是空间消耗大，bitmap相对来说空间消耗小但是不管包含多少文档都需要12.5MB的空间，即使只有一个文件也要12.5MB的空间（8 位的整数，相当于是范围在(0,99999999)，也就是说 99999999 个 bit），这样实在不划算，所以权衡之后就有了下面的Roaring Bitmap。

比如现在需要查询 name=li and age=18 的数据，这时我们需要通过这两个字段将各自的结果 Posting List
取出,最简单的方法是分别遍历两个集合，取出重复的数据，但这个明显效率低下。 这时我们便可使用 bitmap
的方式进行存储（还节省存储空间），同时利用 位与 计算便可得出结果 。 [1, 3, 5] ⇒ 10101 [1, 2, 4, 5] ⇒
11011 这样两个二进制数组求与便可得出结果（多条件查询）： 10001 ⇒ [1, 5] 最终反解出 Posting List 为
[1, 5] ,这样的效率自然是要高上许多。

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

1.Roaring Bitmap首先会根据每个id的高16位分配id到对应的block里面，比如第一个block里面id应该都是在0到65535之间，第二个block的id在65536和131071之间
2. 对于每一个block里面的数据，根据id数量分成两类
– 如果数量小于4096，就是用short数组保存
– 数量大于等于4096，就使用bitmap保存
在每一个block里面，一个数字实际上只需要2个字节来保存就行了，因为高16位在这个block里面都是相同的，高16位就是block的id，block id和文档的id都用short保存

至于4096这个分界线，因为当数量小于4096的时候，如果用bitmap就需要8kB的空间，而使用2个字节的数组空间消耗就要少一点。比如只有2048个值，每个值2字节，一共只需要4kB就能保存，但是bitmap需要8kB。
由此见得，Elasticsearch使用的倒排索引确实比关系型数据库的B-Tree索引快

联合索引

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