快速,持续,稳定,傻瓜式
支持Mysql,Sqlserver数据同步

为什么Elasticsearch查询速度比关系型数据库快

在线QQ客服:1922638

专业的SQL Server、MySQL数据库同步软件

首先考虑几个问题:

  • 为什么ES 的搜索功能接近实时
  • 为什么实时对文档进行CRUD(创建,读取,更新,删除)操作?

以下是介绍ES和Lucene内部结构的一些图片。

图1,ES群集

图2,ES节点Node,一个节点等效于ES服务器。

图3,ElasticSearch索引索引是通过在一个或多个节点中组合一个或多个小绿色方块形成的。

图4在一个索引下,分布在多个节点中的绿色小方块称为碎片。

图5中,碎片是Lucene索引。

图6,Lucene中有许多小段,这是Lucene存储的最小管理单元。

接下来,我们将从节点,碎片和分段的角度解释为什么Elasticsearch如此之快。

多节点群集解决方案提高了整个系统的并发处理能力。

将文档路由到分片:为文档建立索引时,文档存储在主分片中。 Elasticsearch如何知道文档应存储在哪个分片中?实际上,此过程是根据以下公式确定的:

碎片=哈希(路由)%

路由是一个变量值,默认值是文档的_id,也可以将其设置为自定义值。这就解释了为什么我们在创建索引时必须确定主分片的数量,并且永远不会更改此数字:因为如果该数字发生更改,那么所有先前的路由值将无效,并且无法再找到该文档到了

确定哪个分片在其中,然后确定它在哪个节点上。

因此,当确定主要分片的数量时,如果集群扩展了怎么办?下图是扩展主分片的方法。它最初在单个节点上设置为5个分片,然后扩展为5个节点,每个节点都有一个分片。换句话说,单个分片的容量会变大,但数量不会增加,如下图所示:

节点分为主节点,主节点,数据节点,数据节点和客户端节点(仅用于请求的分发和聚集)。每个节点都可以接受客户的请求,并且每个节点都知道群集中任何文档的位置,因此它可以将请求直接转发到所需的节点。接受请求后,该节点将成为”协调节点”。从这个角度来看,整个系统可以接受更高的并发请求,当然搜索速度也更快。

以更新后的文档为例,如下图所示:

  • 客户端向节点1发送更新请求。
  • 它将请求转发到主分片所在的节点3。
  • 节点3从主碎片中检索文档,修改字段中的JSON,并尝试重新索引主碎片的文档。如果文档已被其他过程修改,它将重试步骤3,并在更多次后放弃。
  • 如果节点3成功更新了文档,它将并行转发该文档的新版本到节点1和节点2上的副本分片以重新编制索引。一旦所有副本片段都返回成功,则节点3还将成功返回给协调节点,并且协调节点将成功返回给客户端。

在Elasticsearch中使用的此方法假定冲突是不可能的,并且不会阻止尝试的操作。因为没有阻塞,所以提高了索引的速度,同时,可以通过以下字段确保并发情况下的正确性:

仅当索引中的文档现在为1时,才能成功更新此文档。

您可以设置分片副本的数量以提高在高并发情况下的搜索速度,但同时会降低索引效率。

在底层采用分段存储模式,几乎避免了读写过程中出现锁,从而大大提高了读写性能。

  • 不需要锁定。如果您从不更新索引,则无需担心多个进程同时修改数据的问题。
  • 一旦将索引读入内核的文件系统高速缓存,由于其不变性,它将保留在该位置。只要文件系统高速缓存中有足够的空间,大多数读取请求将直接请求内存而不会碰到磁盘。这可以极大地提高性能。
  • 其他缓存(例如过滤器缓存)在索引的生存期内始终有效。由于数据不会更改,因此不需要每次数据更改时都重新构建它们。
  • 编写单个大的反向索引允许压缩数据,从而减少了磁盘I/O和需要缓存在内存中的索引的使用。

如何在保留不变性的同时更新倒排索引?使用上述内容创建更多索引文档。实际上,UPDATE操作包括DELETE操作(段合并时实际上仅删除记录标志)和CREATE操作。

为了提高索引写入速度并同时确保可靠性,Elasticsearch在分段的基础上添加了一个事务日志或事务日志,并在每次对Elasticsearch进行操作时对其进行记录。

为文档建立索引后,会将其添加到内存缓冲区中并附加到事务日志中,如下图所示:

碎片每秒刷新(刷新)一次:

  • 不使用fsync操作将内存缓冲区中的文档写入新段。
  • 已打开此部分以使其可搜索。
  • 清除了内存缓冲区。

此过程继续进行,将更多文档添加到内存缓冲区中并追加到事务日志中,如下所示:

每次-例如,事务日志变得越来越大-索引都会被刷新;创建新的事务日志并执行完全提交:

  • 内存缓冲区中的所有文档均被写入新段。
  • 缓冲区已清除。
  • 提交点已写入硬盘。
  • 通过fsync刷新文件系统缓存。
  • 旧的记录已删除。

在刷新段之前,数据将保存在内存中并且不可搜索,这就是为什么Lucene被称为提供近实时而不是实时查询的原因。

但是上述机制避免了随机写入,并且数据写入是批处理和追加,可以实现高吞吐量。同时,为了提高写入效率,文件高速缓存系统和内存用于加快写入过程中的性能,日志用于防止数据丢失。

LSM-Tree的示意图如下。可以看出,Lucene的写作思想与LSM-Tree一致:

最后,谈到倒排索引,他们都说倒排索引可以提高搜索速度。那么采用什么特定的体系结构或数据结构来实现这一目标呢?

以上是Lucene中的实际索引结构。使用示例来说明以上三个概念:

ID是文档ID,然后创建的索引如下:

名称:

年龄:

性别:

可以看出,已经为每个字段建立了倒排索引。发布列表是一个int数组,用于存储与某个特定术语匹配的所有文档ID。实际上,此外,它还包括:计算数量时使用的文档数量,每个文档中条目的出现次数,出现位置,每个文档的长度,所有文档的平均长度等。关联。

假设我们有很多术语,例如:

卡拉,萨拉,埃琳,艾达,帕蒂,凯特,赛琳娜

如果按此顺序排列,则查找特定术语的速度必须非常慢,因为该术语未排序,因此需要对所有术语进行过滤以找到特定术语。排序后,它变为:

Ada,Carla,Elin,Kate,Patty,Sara,Selena

这样,我们可以使用二进制搜索比完全遍历更快地找到目标术语。这是术语词典。使用术语词典,您可以使用logN磁盘搜索来获取目标。

但是磁盘的随机读取操作仍然非常昂贵(随机访问大约需要10毫秒)。为了尽可能少地读取磁盘,有必要在内存中缓存一些数据。但是,整个术语词典本身太大,无法完全容纳在内存中。因此有一个术语索引。术语索引有点像字典的大章节表。例如:

术语以A………………开头。 Xxx页面

术语以C………………开头。 yyy页面

术语以E………………开头。 Zzz页面

如果所有术语均为英文字符,则术语索引实际上可能由26个英文字符表组成。但是实际情况是术语可能不是全英文字符,术语可能是任何字节数组。并且26个英文字符不一定每个字都具有相等的用语。例如,可能没有任何以x字符开头的术语,特别是有很多以s开头的术语。实际的词项索引是一棵trie树:

该示例是一个trie树,其中包含” A”,” to”,” tea”,” ted”,” ten”,” i”,” in”和” inn”。该树不包含所有术语,而是包含术语的某些前缀。您可以通过术语索引快速找到术语词典的偏移量,然后从该位置顺序搜索。

现在我们可以回答”为什么Elasticsearch/Lucene检索比mysql更快。Mysql仅具有术语词典层,该术语以b树排序方式存储在磁盘上。检索术语需要多次随机访问磁盘Lucene在术语词典的基础上增加了术语索引以加快检索速度,并将术语索引以树的形式缓存在内存中,从术语索引中找到相应术语词典的块位置后,转到磁盘查找术语,大大减少了磁盘的随机访问时间。

实际上,Lucene中的术语索引是一个”变量”特里前缀树或FST。 FST比特里树更好吗?特里树仅共享前缀,而FST共享前缀和后缀,从而节省了更多空间。

FST是6元组(Q,I,O,S,E,f):

  • Q是一个有限状态集
  • 我是一组有限的输入符号
  • O是一组有限的输出符号
  • S是Q中的状态,称为初始状态
  • E是Q的子集,称为终止状态集
  • f是转换函数,f? Q×(I∪{ε})×(O∪{ε})×Q,其中ε表示空字符。

    也就是说,从状态q1开始,接收输入字符i,您可以到达另一个状态q2,并产生输出o。

例如,存在以下一组映射关系:

它可以由FST在下图中表示:

本文非常好:对Lucene的字典FST的深入分析

考虑一下为什么不需要HashMap,HashMap可以实现有序地图吗?内存消耗!以牺牲存储性能为代价,目的是将所有术语索引都存储在内存中,最终的效果是提高速度。从上面可以看出,FST是一种压缩字典树后缀的图形结构。她具有Trie的高效搜索功能,并且非常小。在这种情况下,我们的搜索可以将整个FST加载到内存中。

综上所述,FST具有更高的数据压缩率和查询效率,因为字典驻留在内存中,并且FST具有良好的压缩率,因此FST在最新版本的Lucene中具有很多使用场景,也是默认的字典数据结构。

Lucene的提示文件是术语索引结构,而tim文件是术语词典结构。从图片中可以看到,提示中存储了多个FST,

FST存储\ lt;字前缀,以及所有以字首开头的所有Term压缩块在磁盘上的位置。即,在从上述术语索引中找到相应术语词典的块位置,然后在磁盘上寻找该术语之后,大大减少了磁盘的随机访问时间。

从视觉上可以理解, 术语词典是新华字典的正文部分,包含所有词汇,术语索引是新华字典前面的索引页,指示词汇表是

但是FST不能知道术语在词典(.tim)文件中的特定位置,也不能确切知道术语是否仅通过FST确实存在。它只能告诉您查询的术语可能在这些块中。 FST的存在不能给出确切答案。因为FST由字典中每个块的前缀组成,所以通过FST只能直接找到该块。.tim文件上的特定文件指针不能直接找到术语。

返回到上面的示例,给定查询过滤条件age = 24的过程是,首先从术语索引中找到18在术语词典中的近似位置,然后从术语词典中准确找到术语18,然后然后获取发布列表或指向发布列表位置的指针。查询性别=女性的过程与此类似。最后,得出的结论是,年龄= 24 AND性别=女性是将两个过帐列表合并为AND。

这种理论上的”与”合并操作并不容易。对于mysql,如果您同时为年龄和性别字段创建索引,则只会选择最有选择性的索引进行查询,然后另一个条件是在遍历各行的过程中在内存中进行计算后将其过滤掉。那么我们如何一起使用两个索引呢?有两种方法:

  • 使用跳过列表数据结构。同时遍历性别和年龄的发布列表,彼此跳过;
  • 使用位集数据结构查找性别和年龄过滤器的位集,并对这两个位集执行AN操作。

Elasticsearch支持以上两种联合索引方法。如果查询过滤器缓存在内存中(以位集的形式),则合并是两个位集的与。如果查询过滤器未缓存,则使用跳过列表遍历磁盘上的两个列表。

使用一个示例来说明如何使用跳过列表的思想进行合并(请参阅Lucene学习摘要7:Lucene搜索过程分析(5)):

  1. 反向列表最初如下,可以看出每个发布列表已经按顺序排列:

  2. 根据从小到大的第一个文档编号排列每个过帐清单:

  3. 首先调用具有最小文档编号的倒排表,然后将最后一个过帐清单的文档编号作为doc(显然,您可以跳过上一个文档作为交集)。也就是说,doc = 8,首先指向第0个项目,前进到大于8的第一个文档,即文档10,然后将doc = 10,第一个指向第一个项目。

  4. doc = 10,首先指向项目1,前进到文档11,然后将doc = 11,首先指向项目2。

  5. doc = 11,首先指向项目3,前进到文档11,然后将doc = 11,首先指向项目4。

  6. 以同样的方式,第一个指向最后一个项目。也就是说,doc = 11,首先指向项目7,前进到文档11,然后将doc = 11,首先指向项目0。

  7. doc = 11,首先指向项目0,前进到文档11,然后将doc = 11,首先指向项目1。

  8. doc = 11,首先指向项目1。因为11 \\ 11为假,循环结束并返回doc = 11。这时,我们将发现,当循环退出时,所有反向列表的第一个文档为11,因此11是所有跳过列表的公共项。

  9. 根据此方法,重复外循环以获得剩余的公共项目。

什么是高级操作?这是跳过列表提供的快速跳过功能。

另一方面,对于较长的发布列表,例如:

[1,3,13,101,105,108,255,256,257]

我们可以将此列表分为三个块:

[1,3,13] [101,105,108] [255,256,257]

然后可以构建跳过列表的第二层:

[1,101,255]

1,101,255指向其相应的块。这样,您可以快速跨块移动以指向该位置。

Lucene会自然地再次压缩该块。压缩方法称为参考帧编码。示例如下:

考虑频繁出现的术语(所谓的低基数值),例如男性或女性。如果有一百万个文档,那么在男性发布列表中将有500,000 int值。使用参考帧编码进行压缩可以大大减少磁盘使用量。此优化对于减小索引大小非常重要。当然,在mysql b树中有一个类似的发布列表,它不是用这种方式压缩的。

因为此参考帧的编码已解压缩。使用跳过列表,除了跳过遍历的开销外,还跳过了了解这些压缩块的压缩过程,从而节省了CPU。

还可以看出,Lucene确实尽了最大的努力来节省内存。

位集是一种非常直观的数据结构,与发布列表相对应,例如:

[1,3,4,7,10]

对应的位集是:

[1,0,1,1,0,0,1,0,0,1]

每个文档均按文档ID排序,并与其中一位相对应。位集本身具有压缩特性,可以用一个字节表示8个文档。因此,一百万个文档只需要125,000个字节。但是考虑到可能存在数十亿个文档,将位集存储在内存中仍然是一种奢侈。对于每个过滤器,必须使用一个位集。例如,当age = 18被高速缓存时,它是一个位集,并且18 \\ lt; =年龄lt; 25是另一个过滤器,在缓存时需要一个位集。

因此,秘诀在于需要具有数据结构:

它可以压缩方式节省数亿位,以指示相应的文档是否与过滤器匹配;

此压缩的位集仍可以快速执行AND和OR逻辑运算。

Lucene使用的数据结构称为Roaring Bitmap。

压缩的想法实际上很简单。它不占用100个零,而是占用100位。最好保存一次0,然后声明此0重复100次。

为什么限制为65535?除了程序员世界中的1024个字符外,65535也是一个经典值,因为它= 2 ^ 16-1,恰好是可以用2个字节表示的最大数字(一个简短的存储单元),请注意最后一行”如果一个块具有超过4096个值,则编码为位集,否则作为每个值使用2个字节的简单数组”,我不再关心字节,使用short []方便。

在Lucene 7.0之后,Lucene采用了不同的存储方式来降低位集的稀疏性:当位集相对稀疏时,它直接存储DocID;当位集密集时,它将直接存储位集的位数据。根据数据的不同分布,采用合适的结构不仅可以提高空间的利用率,而且可以提高遍历的效率。

Elasticsearch/Lucene为了提高索引和搜索的效率,从上层到下层,使用各种聪明的数据结构和设计,它们依靠出色的理论和极端的优化来实现最终的查询性能。

  • Elasticsearch:权威指南
  • 详细的Elasticsearch
  • Lucene的内部结构
  • 倒排索引简介
  • FST简介(1)
  • FST简介(2)
  • 跳过表简介
  • Lucene查询原理
  • Lucene倒排索引原理的问题

相关推荐

 
QQ在线咨询
售前咨询热线
QQ1922638