ES 简介
官方文档内容很全,推荐阅读 ES 官方文档
Elasticsearch 是一个分布式、可扩展、实时的搜索与数据分析引擎。基于 Lucene 作为其核心来实现所有索引和搜索的功能。原本 Lucene 只是一个库, 想要使用它必须用 Java 语言将其集成到你的应用中, 麻烦在于 Lucene 比较复杂, 使用者必须深入了解检索的相关知识来理解它是如何工作的。但 ES 通过简单的 RESTful API 来隐藏 Lucene 的复杂性, 从而让全文搜索变得简单。
ES 除了基于 Lucene 上开发的搜索引擎外,还提供了:
- 分布式的实时文件存储,每个字段都被索引并且可被搜索
- 实时分析的分布式搜索引擎
- 可以扩展到上百台服务器,处理 PB 级结构化或非结构化数据
除此之外, ES 是高度可定制化的,你可以根据不同领域需求定制 ES 的高级特性。
ES 核心概念
- 集群:一个集群就是由一个或多个节点组织在一起,他们共同持有你的整个数据,并一起提供索引和搜索功能。一个集群由一个唯一的名字标识,一个节点只能通过指定某个集群的名字,来加入这个集群。
- 节点:一个节点是你集群中的一个服务器,作为集群的一部分,它存储你的数据,参与集群的索引和搜索功能。节点也是由一个名字来标识的。
- 索引:一个索引就是一个拥有积分相似特征的文档的集合。一个索引由一个名字来标识(必须全部是小写字母的),并且当我们要对对应于这个索引中的文档进行索引、搜索、更新和删除的时候,都要使用到这个名字。对应到数据库中的概念的话,应该是 Database。
- 类型:在一个索引中,你可以定义一种或多种类型。一个类型是你的索引的一个逻辑上的分类/分区。通常,会为具有一组共同字段的文档定义一个类型。对应数据库中的 Table。
- 文档:一个文档是一个可被索引的基础信息单元,文档以 JSON 格式来标识,文档类似于关系型数据库中Record的概念。ES 会为一个文档添加如 _index、_type和_id 等用户数据以外的字段。
- 分片:Elasticsearch提供了将索引划分成多份的能力,当你创建一个索引的时候,你可以指定你想要的分片的数量。每个分片本身也是一个功能完善并且独立的“索引”,这个“索引”可以被放置到集群中的任何节点上。
- 复制:为了数据安全, ES 允许用户创建分片的一份或多份拷贝。同时复制还可以通过在所有复制上并行运行搜索,扩展搜索量/吞吐量。默认情况下,Elasticsearch中的每个索引被分片5个主分片和1个复制。
简单查询原理
倒排索引
倒排索引指的是,把文档拆分成一个个单词,每个单词指向包含该单词的文档ID。在查询时,根据关键字,找到包含该关键字的文档ID列表。再根据ID读取具体的数据。
比如现在库里有三个文档
- doc0: “it is what it is”
- doc1: “what is it”
- doc2: “it is a banana”
那么我们就可以得到如下的反向文件索引
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
当查询 what 这个词时,我们可以定位到 0 和 1 这两个文档。当多个查询且要求必须匹配的话,则会取对应文档的交集。
接下来的问题是,建立索引和查询的基本单位是什么呢?颗粒度太小,如字那么返回的结果会太多,没什么意义。对于中文来说,一般查询的基本单位是词。 ES 自带的中文分词不太够用,一般采用 ik 中文切词插件。在https://github.com/medcl/elasticsearch-analysis-ik上找到我们elasticSearch对应的版本,然后对应安装就行了。 ik 还可以自定义词典和切割模式,很好用。
在 Lucene 中,倒排索引的底层实现是基于 FST(Finite State Transducer) 数据结构,它有两个优点:
- 空间占用小。通过对词典中单词前缀和后缀的重复利用,压缩了存储空间
- 查询速度快。O(len(str)) 的查询时间复杂度。
ES 是如何写入文档,创建索引的?
如下图所示:
[]
- 第一步,客户向集群某节点写入数据,发送数据。如果没有指定路由/协调节点,请求的节点扮演路由节点的角色。
- 节点 1 接收到请求后,使用文档 _id 确定文档所属分片,此处为 0.请求会被转到另外的节点,假定节点 3. 因此分片 0 的主分片分配到节点 3 上。具体的分片分配公式为: \(n_shard = hash(_routing)%(num_of_primary_shards)\)
- 节点 3 在主分片上执行写操作,如果成功,则将请求并行转发到节点 1和节点 2 的副本分片上,等待结果返回。所有的副本分片都报告成功,节点 3 将向协调节点(节点 1)报告成功,节点 1 向请求客户端报告写入成功。
ES 的搜索过程?
可以拆解为 query 和 fetch 两个阶段。
query 阶段的目的是定位到位置,但不取:
- 假设一个索引数据有 5 主+1 副本 共 10 分片,一次请求会命中(主或者副本分片中)的一个。
- 每个分片在本地进行查询,结果返回到本地有序的优先队列中。
- 第 (2)步骤的结果发送到协调节点,协调节点产生一个全局的排序列表。
Fetch 阶段的目的是取数据:路由节点获取所有文档,返回给客户端。
ES 的更新和删除文档的过程
删除和更新也都是写操作,但是 Elasticsearch 中的文档是不可变的,因此不能被删除或者改动以展示其变更。盘上的每个段都有一个相应的.del 文件。当删除请求发送后,文档并没有真的被删除,而是在.del 文件中被标记为删除。该文档依然能匹配查询,但是会在结果中被过滤掉。当段合并时,在.del 文件中被标记为删除的文档将不会被写入新段。在新的文档被创建时,Elasticsearch 会为该文档指定一个版本号,当执行更新时,旧版本的文档在.del 文件中被标记为删除,新版本的文档被索引到一个新段。旧版本的文档依然能匹配查询,但是会在结果中被过滤掉。
拼写纠错是如何实现的?
拼写纠错是基于编辑距离来实现的。对于拼写纠错,我们考虑构造一个度量空间(Metric Space),该空间内任何关系满足以下三条基本条件:
- d(x,y) = 0 – 假如 x 与 y 的距离为 0,则 x=y
- d(x,y) = d(y,x) – x 到 y 的距离等同于 y 到 x 的距离
- d(x,y) + d(y,z) >= d(x,z) – 三角不等式
1、根据三角不等式,则满足与 query 距离在 n 范围内的另一个字符转 B,其与 A 的距离最大为 d+n,最小为 d-n。
2、BK 树 (Burkhard Keller Tree) 的构造就过程如下:每个节点有任意个子节点,每条边有个值表示编辑距离。所有子节点到父节点的边上标注 n 表示编辑距离恰好为 n。比如,我们有棵树父节点是”book”和两个子节点”cake”和”books”,”book”到”books” 的边标号 1,”book”到”cake”的边上标号 4。从字典里构造好树后,无论何时你想插入新单词时,计算该单词与根节点的编辑距离,并且查找数值为d(neweord, root)的边。递归得与各子节点进行比较,直到没有子节点,你就可以创建新的子节点并将新单词保存在那。比如,插入”boo”到刚才上述例子的树中,我们先检查根节点,查找 d(“book”, “boo”) = 1 的边,然后检查标号为 1 的边的子节点,得到单词”books”。我们再计算距离 d(“books”, “boo”)=2,则将新单词插在”books”之后,边标号为 2。
3、查询相似词如下:计算单词与根节点的编辑距离 d,然后递归查找每个子节点标号为 d-n 到 d+n(包含)的边。假如被检查的节点与搜索单词的距离 d 小于 n,则返回该节点并继续查询。比如输入 cape 且最大容忍距离为 1,则先计算和根的编辑距离 d(“book”, “cape”)=4,然后接着找和根节点之间编辑距离为 3 到5 的,这个就找到了 cake 这个节点,计算 d(“cake”, “cape”)=1,满足条件所以返回 cake,然后再找和 cake 节点编辑距离是 0 到 2 的,分别找到 cape 和cart 节点,这样就得到 cape 这个满足条件的结果。
Elasticsearch 是如何实现 Master 选举的?
Elasticsearch 的选主是 ZenDiscovery 模块负责的,主要包含 Ping(节点之间通过这个 RPC 来发现彼此)和 Unicast(单播模块包含一个主机列表以控制哪些节点需要 ping 通)这两部分。
对所有可以成为 master 的节点(node.master: true)根据 nodeId 字典排序,每次选举每个节点都把自己所知道节点排一次序,然后选出第一个(第 0 位)节点,暂且认为它是 master 节点。如果对某个节点的投票数达到一定的值(可以成为 master 节点数 n/2+1)并且该节点自己也选举自己,那这个节点就是 master。否则重新选举一直到满足上述条件。
可以发现,按照上述方式,可能会出现Elasticsearch 中的节点(比如共 20 个),其中的 10 个选了一个 master,另外 10 个选了另一个 master 的情况。此时:
- 当集群 master 候选数量不小于 3 个时,可以通过设置最少投票通过数量(discovery.zen.minimum_master_nodes)超过所有候选节点一半以上来解决脑裂问题。
- 当候选数量为两个时,智能修改为唯一的一个 master 候选,其他作为 data 节点,避免脑裂问题。
查询评分
对于多术语查询,Lucene采用布尔模型(Boolean model)、词频/逆向文档频率(TF/IDF)、以及向量空间模型(Vector Space Model),然后将他们合并到单个包中来收集匹配文档和分数计算。 只要一个文档与查询匹配,Lucene 就会为查询计算分数,然后合并每个匹配术语的分数。
布尔检索
根据多个查询项之间的关系(and/ or/ not) 来查找候选文档。and 表示同时出现, Or 表示出现一个就可以,not 表示不包含。布尔检索优点是系统构建简单,缺点是查询构建比较复杂,同时没有考虑查询词间的重要性等因素。
实用评分函数
\[score(q, d ) = 查询正则化 * 协调因子 * \sum_{t in d}(tf(t) * id(t)^{2} * t.getBoost() * norm(t, d))\]其中
- 查询正则化: 试图将查询进行正则化来达到比较不同查询结果的目的,但其实比较不同查询结果的相关度分数并没有什么意义,同一查询结果间的相对分值更有用。
- 协调因子: 文档里出现的查询术语越多,协调因子就会越大,结果也往往更好。
- 求和是对文档中每个与查询匹配的 t 进行遍历。
- tf(t):术语在文档中出现的频次, \(tf(t) = \sqrt{频次}\)
- \(idf(t)^{2}\):逆向文档频率的平方, 其中 \(idf(t) = 1 + \log(总文档数/(包含t的文档数 + 1))\)
- t.getBoost():查询中使用的 boost,默认为1,用户也可以进行设置,使得某一个查询 term 比其他的更重要。但需要注意的是, 权重提升值会经过正则化和一些其他的内部优化过程,boost 为 2 的最终分数并不代表是 boost 为1 的2倍。但还是提高了的,也表明你想让该term 比 boost 比它低的 更重要。这一项很重要,因为大部分情况下简单查询配合 boost 就能获得不错的召回效果,但在实际应用中,无法通过简单的公式得出某个特定查询语句的 “正确” 权重提升值,只能通过不断尝试获得。需要记住的是 boost 只是影响相关度评分的其中一个因子;它还需要与其他因子相互竞争。
- 字段长度正则值:t 所在的字段越短权值越高,如 term 出现在标题中就会比出现在内容中的相关度更高, \(norm(d) = 1 / \sqrt{t 所在段的长度}\)
向量空间模型
每个词都用向量表示,查询时计算向量间的相似度,两个向量越相似则 cos 值越大。
更牛的评分机制
上面是常见的评分策略,但是对于实体来说,大部分都很短, 而且每个字都很重要, 此时 tf-idf 就不那么重要了, 此时可以用 constant_score 查询 来为任意一个匹配的文档制定分数,忽略掉 TF-IDF 信息。
更进一步,如果想改变当前的排序规则,ES 还提供了function_score 查询, 实体链接没这么复杂,暂时没用到就不记了。
利用 python 控制 ES
ES 不同版本间的差距还比较大,这里用的是 ES 7 和对应的 python 模块。
建立索引
es = Elasticsearch(es_server)
mappings = {
"mappings": {
"_doc": {
"properties":{
{
"field":{"type": "text",
"index": True,
"store": True,
"analyzer": "ik_max_word",
"search_analyzer": "ik_max_word",
}
}
}
}
}
}
es.indices.create(index="index_name", body=mappings)
删除索引
es.indices.delete(index=index_name)
插入数据
data = {"field": "刘德华"}
es.index(index=index_name, body = data, doc_type="_doc")
查询
doc = {
"query":{
"bool": {
"should": [
{"match": {
"field": {"query": "刘德美",
"boost": 2}
}
}
]
}
}
}
这里的 should 可以换做 must 和 must_not,should 等价于 OR, must 等价于 AND, must_not 等价于 NOT。