1、倒排索引
Elasticsearch 使用一种称为倒排索引的结构,它适用于快速的全文搜索。
有倒排索引,肯定会对应有正向索引:
- 正向索引(forward index)
- 反向索引(inverted index,实际就是倒排索引)
所谓的正向索引,就是搜索引擎会将待搜索的文件都对应一个文件ID,搜索时将这个ID和搜索关键字进行对应,形成K-V对,然后对关键字进行统计计数。
但是互联网上收录在搜索引擎中的文档的数目是个天文数字,这样的索引结构根本无法满足实时返回排名结果的要求。所以,搜索引擎会将正向索引重新构建为倒排索引,即把文件ID对应到关键词的映射转换为关键词到文件ID的映射(跟正向索引反过来了),每个关键词都对应着一系列的文件,这些文件中都出现这个关键词。
1.1、倒排索引示例
倒排索引的例子:一个倒排索引由文档中所有不重复词的列表构成,对于其中每个词,有一个包含它的文档列表。例如,假设我们有两个文档,每个文档的 content 域包含如下内容:
- The quick brown fox jumped over the lazy dog
- Quick brown foxes leap over lazy dogs in summer
为了创建倒排索引,我们首先将每个文档的 content 域拆分成单独的词(我们称它为词条或tokens ),创建一个包含所有不重复词条的排序列表,然后列出每个词条出现在哪个文档。结果如下所示:
现在,如果我们想搜索 quick
brown
,我们只需要查找包含每个词条的文档:
两个文档都匹配,但是第一个文档比第二个匹配度更高。如果我们使用仅计算匹配词条数量的简单相似性算法,那么我们可以说,对于我们查询的相关性来讲,第一个文档比第二个文档更佳。
但是,我们目前的倒排索引有一些问题:
-
Quick
和quick
以独立的词条出现,然而用户可能认为它们是相同的词。 -
fox
和foxes
非常相似,就像dog
和dogs
;他们有相同的词根。 -
jumped
和leap
,尽管没有相同的词根,但他们的意思很相近。他们是同义词。
使用前面的索引搜索+Quick +fox不会得到任何匹配文档。(记住,+前缀表明这个词必须存在)。只有同时出现Quick和fox 的文档才满足这个查询条件,但是第一个文档包含quick fox ,第二个文档包含Quick foxes 。我们的用户可以合理的期望两个文档与查询匹配。我们可以做的更好。
如果我们将词条规范为标准模式,那么我们可以找到与用户搜索的词条不完全一致,但具有足够相关性的文档。例如:
- Quick可以小写化为quick。
- foxes可以词干提取变为词根的格式为fox。类似的,dogs可以为提取为dog。
- jumped和leap是同义词,可以索引为相同的单词jump 。
现在索引看上去像这样:
这还远远不够。我们搜索+Quick +fox 仍然会失败,因为在我们的索引中,已经没有Quick了。但是,如果我们对搜索的字符串使用与content域相同的标准化规则,会变成查询+quick +fox,这样两个文档都会匹配!分词和标准化的过程称为分析,这非常重要。你只能搜索在索引中出现的词条,所以索引文本和查询字符串必须标准化为相同的格式。
1.2、不可改变的倒排索引
早期的全文检索会为整个文档集合建立一个很大的倒排索引并将其写入到磁盘。 一旦新的索引就绪,旧的就会被其替换,这样最近的变化便可以被检索到。
倒排索引被写入磁盘后是不可改变的:它永远不会修改。不变性的好处如下:
- 不需要锁。如果你从来不更新索引,你就不需要担心多进程同时修改数据的问题。
- 一旦索引被读入内核的文件系统缓存,便会留在哪里,由于其不变性,只要文件系统缓存中还有足够的空间,那么大部分读请求会直接请求内存,而不会命中磁盘,这提供了很大的性能提升。
- 其它缓存(像filter缓存),在索引的生命周期内始终有效,它们不需要在每次数据改变时被重建,因为数据不会变化。
- 写入单个大的倒排索引允许数据被压缩,可减少磁盘 IO 和需要被缓存到内存的索引的使用量。
坏处:
- 每次都要重新构建整个索引
2.1.3、如何动态更新倒排索引
一个不变的索引有上述好处,当然也有不好的地方,主要因为是它是不可变的,你不能修改它。所以如果你需要让一个新的文档可被搜索,你需要重建整个索引。这要么对一个索引所能包含的数据量造成了很大的限制,要么对索引可被更新的频率造成了很大的限制。
如何在保留不变性的前提下实现倒排索引的更新?答案是:用更多的索引。通过增加新的补充索引来反映新近的修改,而不是直接重写整个倒排索引。每一个倒排索引都会被轮流查询到,从最早的开始查询,然后再对结果进行合并。
Elasticsearch基于Lucene,这个java库引入了按段搜索的概念。每一段本身都是一个倒排索引,但索引在 Lucene 中除表示所有段的集合外,还增加了提交点的概念:一个列出了所有已知段的文件。
按段搜索会以如下流程执行:
1)新文档被收集到内存索引缓存。
2)不时地,缓存被提交。
- 一个新的段,一个追加的倒排索引,被写入磁盘。
- 一个新的包含新段名字的提交点被写入磁盘。
- 磁盘进行同步,所有在文件系统缓存中等待的写入都刷新到磁盘,以确保它们被写入物理文件
3)新的段被开启,让它包含的文档可见以被搜索。
4)内存缓存被清空,等待接收新的文档。
当一个查询被触发,所有已知的段按顺序被查询。词项统计会对所有段的结果进行聚合,以保证每个词和每个文档的关联都被准确计算,这种方式可以用相对较低的成本将新文档添加到索引。
段是不可改变的,所以既不能从把文档从旧的段中移除,也不能修改旧的段来进行反映文档的更新。取而代之的是,每个提交点会包含一个.del 文件,文件中会列出这些被删除文档的段信息。
- 当一个文档被“删除”时,它实际上只是在 .del 文件中被标记删除。一个被标记删除的文档仍然可以被查询匹配到,但它会在最终结果被返回前从结果集中移除。
- 文档更新也是类似的操作方式:当一个文档被更新时,旧版本文档被标记删除,文档的新版本被索引到一个新的段中。可能两个版本的文档都会被一个查询匹配到,但被删除的那个旧版本文档在结果集返回前就已经被移除。
2、文档更新原理
一个文档从开始更新或修改,到可被搜索的延迟主要就是主分片的延时 + 并行写入副本的最大延时,如下图:
2.1、文档更新(实现近实时搜索)
随着按段(per-segment)搜索的发展,一个新的文档从索引到可被搜索的延迟显著降低了。新文档在几分钟之内即可被检索,但这样还是不够快,磁盘在这里成为了瓶颈。提交(Commiting)一个新的段到磁盘需要一个 fsync 来确保段被物理性地写入磁盘,这样在断电的时候就不会丢失数据。但是 fsync 操作代价很大:如果每次索引一个文档都去执行一次的话会造成很大的性能问题。
这时我们需要的是一个更轻量的方式来使一个文档可被搜索,这意味着fsync要从整个过程中被移除,实际上实现的方式就是在 Elasticsearch 和磁盘之间用文件系统缓存。像之前描述的一样,在内存索引缓冲区中的文档会被写入到一个新的段中,但是这里新段会被先写入到文件系统缓存 -- 这一步代价会比较低,稍后再被刷新到磁盘 -- 这一步代价比较高。不过当文件在文件系统缓存中时,就已经可以像其它文件一样被打开和读取了。
Lucene 允许新段被写入和打开,使其包含的文档在未进行一次完整提交时便对搜索可见。这种方式比进行一次提交代价要小得多,并且在不影响性能的前提下可以被频繁地执行。
在 Elasticsearch 中,写入和打开一个新段的轻量的过程叫做 refresh,默认情况下每个分片会每秒自动刷新一次。这就是为什么我们说 Elasticsearch是近实时搜索:文档的变化并不是立即对搜索可见,但会在一秒之内变为可见。
这些行为可能会对新用户造成困惑:他们索引了一个文档然后尝试搜索它,但却没有搜到。这个问题的解决办法是用refresh API执行一次手动刷新:/usersl_refresh
尽管刷新是比提交轻量很多的操作,它还是会有性能开销。当写测试的时候,手动刷新很有用,但是不要在生产环境下每次索引一个文档都去手动刷新。相反,你的应用需要意识到Elasticsearch 的近实时的性质,并接受它的不足。
并不是所有的情况都需要每秒刷新。可能你正在使用Elasticsearch索引大量的日志文件,你可能想优化索引速度而不是近实时搜索,可以通过设置refresh_interval ,降低每个索引的刷新频率
{"settings": {"refresh_interval": "30s"}
}
refresh_interval 可以在既存索引上进行动态更新。在生产环境中,当你正在建立一个大的新索引时,可以先关闭自动刷新,待开始使用该索引时,再把它们调回来。
# 关闭自动刷新
PUT /users/_settings
{ "refresh_interval": -1 }# 每一秒刷新
PUT /users/_settings
{ "refresh_interval": "1s" }