财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

时间:2021-02-12 23:37:17

财务平台进行分录分表以后,随着数据量的日渐递增,业务人员对账务数据的实时分析响应时间越来越长,体验性慢慢下降,之前我们基于mysql的性能优化做了一遍,可以说基于mysql该做的优化已经基本上都做了,本次是基于elasticsearch对其做进一步的性能优化

正文

1mysql索引原理

基于mysql最常用也最直接有效的性能优化也就是添加索引。

mysql索引是怎么实现的呢?数据库最基本的查询算法是顺序查找,时间复杂度为O(n),显然在数据量很大的时候很低,优化的查询算法有二分查找,二叉树查找,虽然查找效率提高了,但是各自对检索的数据都有要求,二分查找检索被要求数据是有序的,而二叉树查找只能用于二叉树上,但是数据本身的组织结构不可能完全满足各种数据结构,例如,理论上不可能同时将两列都按顺序进行组织,所以在数据之外,数据库系统还维护者满足特定查找算法的数据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。

索引是什么?索引是存储引擎用于快速找到记录的一种数据结构,这是索引的基本功能,主要基于hash,b+tree。

我们开发当中一般用到都是mysql innoDB引擎,采用的是b+tree。

b+tree的优势主要体现在查询性能上,在单元素查询时,b+tree会自顶层向下逐层查找节点,最终找到我们需要的叶子节点,范围查询时,b+tree找到叶子节点的起始位置,通过叶子节点链表依次查询数据,直到范围结束为止。

财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

参考上面的示意图

总结:基于b+tree的mysql索引,当这个树的形状瘦低的时候查询效率就会很快,因为查找磁盘的io次数很少,但是如果这个树的形状胖高的时候,查询磁盘的次数就会比较多,那么查询效率就会越来越慢,所以基于mysql索引的性能优化,索引是有限制的,适量的添加索引会对查询效率有明显提升,但是索引过量就适得其反,不但查询效率会降低,也会影响其他操作的效率,因为其他操作的时候也是需要维护索引的。

1elasticsearch索引原理

elasticsearch底层是索引原理是倒排索引,使用场景一般是OLAP,支持rest风格json数据格式交互的全文检索引擎,开源,面向文档设计,实时检索,索引可以无限扩展,只要你的服务器的磁盘、内存足够大。

我们先看一个列子

财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

一个字段有一个自己的倒排索引。18,20这些叫做term,而[1,3]就是postinglist。Posting list就是一个int的数组,存储了所有符合某个term的文档id。

term Dictionary

term排序后的集合,方便二分查找,有了term Dictionary之后就可以在磁盘上查找到具体的document,磁盘的读操作非常昂贵,一次大概需要10ms时间,不同存储方式的磁盘性能不一样,所以为了减少磁盘的读取次数就必要把一些数据缓存到内存中,但是term Dictionary会有很多,不能完整的放到内存中,于是就有了termindex

term index

可以理解为就是英文词典的目录,它是一棵树的结构

示意图

财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

这棵树不会包含所有的term,它只包含term的一些前缀,通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找,大大减少了磁盘访问次数

示意图

财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

所以term index不需要存下所有的term,而仅仅是他们的一些前缀与Term Dictionary的block之间的映射关系,再结合FST(Finite StateTransducers)的压缩技术,可以使term index缓存到内存中

为什么elasticsearch比mysql快

mysql只有 termdictionary这一层,是以树的方式存储在磁盘上的。检索一个term需要若干次的磁盘访问操作,而elasticsearch,在term dictionary的基础上添加了term index来加速检索,term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后,再去磁盘上找term,大大减少了磁盘的访问次数。

term index在内存中是以FST的形式保存的,其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的,一个block内部利用公共前缀压缩,比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以更节约磁盘空间。

压缩技术

用FST压缩term index之外,对posting list也有压缩。

联合索引查询

以上都是单field索引,如果多个field索引的联合查询,比如查询age=18 AND gender=女,倒排索引如何满足快速查询的要求呢?大致过程如下:根据过滤条件 age=18 的先从term index找到18在term dictionary的大概位置,然后再从term dictionary里精确地找到18这个term,然后得到一个posting list或者一个指向posting list位置的指针。然后再查询gender=女的过程也是类似的。最后得出age=18 AND gender=女,就是把两个 posting list做一个“与”的合并

1、skip list

2、bitset 二进制,直接按位与

总结

elasticsearch就是尽量将磁盘里的东西搬进内存,减少磁盘随机读取次数(同时也利用磁盘顺序读特性),结合各种压缩算法,高效使用内存,从而达到快速搜索的目的。

1mysql索引与elasticsearch索引对比

mysql

如果数据量不是特别大,在千万级别,适当的管理好索引,查询效率还是可以的,但是对索引命中率有要求,就是必须要保证索引的命中率,还有就是索引的数量限制好,但是查询条件比较多、需要添加很多索引的时候mysql索引就有瓶颈了。

elasticsearch

使用了OLAP场景,海量数据实时查询,亿级以上数据量,因为底层采用的是倒排索引机制,只要你的服务器资源足够好,理论上随着数据量的增加、索引的增量,实时查询效率是线性的。

倒排索引

倒排索引应用场景:搜索引擎、实时排名,如百度搜索,搜狗搜索

索引分为正向索引和反向索引(倒排索引)

正向索引:通过Key找Value

正向索引的结构如下:

   “文档1”的ID > 单词1:出现次数,出现位置列表;单词2:出现次数,出现位置列表;…………。

   “文档2”的ID > 此文档出现的关键词列表。



  • 1
  • 2
  • 3

倒排索引:通过Value找Key

倒排索引的结构如下:

   “关键词1”:“文档1”的ID,“文档2”的ID,…………。

   “关键词2”:带有此关键词的文档ID列表。



  • 1
  • 2
  • 3

对应的倒排列表为:{(3;1;<4>),(5;1;<4>)},其含义为在文档3和文档5出现过这个单词,单词频率都为1,单词“拉斯”在两个文档中的出现位置都是4,即文档中第四个单词是“拉斯”。

倒排索引可以统计文档ID,出现次数,出现位置。

转载自:https://mp.weixin.qq.com/s/IfjwPEP5RjkfDt-VKSE2gg