文档章节

图解MySQL | [原理解析] Adaptive Hash Index 是如何建立的

爱可生
 爱可生
发布于 02/14 18:24
字数 1855
阅读 127
收藏 0

3 月,跳不动了?>>>

转载自公众号:图解MySQL

Adaptive Hash Index(以下简称 AHI)估计是 MySQL 的各大特性中,大家都知道名字但最说不清原理的一个特性。本期图解我们为大家解析一下 AHI 是如何构建的。

首先我们思考一下 AHI 是为了解决什么问题:

  • 随着 MySQL 单表数据量增大,(尽管 B+ 树算法极好地控制了树的层数)索引 B+ 树的层数会逐渐增多;
  • 随着索引树层数增多,检索某一个数据页需要沿着 B+ 树从上往下逐层定位,时间成本就会上升;
  • 为解决检索成本问题,MySQL 就想到使用某一种缓存结构:根据某个检索条件,直接查询到对应的数据页,跳过逐层定位的步骤。这种缓存结构就是 AHI。

AHI 在实现上就是一个哈希表:从某个检索条件到某个数据页的哈希表,仿佛并不复杂,但其中的关窍在于哈希表不能太大(哈希表维护本身就有成本,哈希表太大则成本会高于收益),又不能太小(太小则缓存命中率太低,没有任何收益)。

这就是 AHI(中文名:自适应哈希索引)中"自适应"的用途:建立一个"不大不小刚刚好"的哈希表。

本文主要讨论 MySQL 是如何建立起一个"刚刚好"的 AHI 的,如图 1 所示:需要经历三个关卡,才能为某个数据页建立 AHI,之后的查询才能使用到该 AHI。

我们逐个关卡来介绍: 关卡 1:某个索引树要被使用足够多次 AHI 是为某个索引树建立的(当该索引树层数过多时,AHI 才能发挥效用)。如果某索引只被使用一两次,就为之建立 AHI,会导致 AHI 太多,维护成本高于收益。因此建立 AHI 的第一关就是:只为频繁使用的索引树建立 AHI。

关卡 2:该索引树上的某个检索条件要被经常使用 显而易见,如果我们为了一个很少出现的检索条件建立 AHI,肯定是入不敷出的。

在此我们插播一个新概念 hash info,hash info 是用来描述一次检索的条件与索引匹配程度(即此次检索是如何使用索引的)。建立AHI时,就可以根据匹配程度,抽取数据中匹配的部分,作为 AHI 的键。关卡 2 就是为了找到经常使用的 hash info。hash info 包括以下三项:

  • 检索条件与索引匹配的列数
  • 第一个不匹配的列中,两者匹配的字节数
  • 匹配的方向是否从左往右进行

我们通过一个例子来简要介绍 hash info 中第一项。假设一张表 table1,其索引是(A1, A2)两列构成的索引:

  • 如果检索条件是(A1=1 and A2=1),那么此次检索使用了该索引的最左两列,hash info 就是(2,0,true)
  • 如果检索条件是(A1=1), 那么此次检索使用了该索引的最左一列,hash info 就是(1,0,true) 关卡 2 就是为了找出经常使用的 hash info,作为建立 AHI 的依据。

关卡 3:该索引树上的某个数据页要被经常使用如果我们为表中所有数据建立 AHI,那 AHI 就失去了缓存的意义:内存已不足以存放其身躯,必然要放到磁盘上,那么其成本显然已经不低于收益。回忆一下,AHI 是为了缩短 B+ 树的查询成本设计的,如果把自己再放到磁盘上,就得变成另一颗 B+ 树(B+ 树算法是处理磁盘查询的高效结构),如此循环往复,呜呼哀哉。

因此我们只能为表中经常被查询的部分数据建立 AHI。所以关卡 3 的任务就是找出哪些数据页是经常被使用的数据页。

修成正果:终于开始建立 AHI 终于可以开始建立 AHI 了, 我们举个例子说明如何建立 AHI。假设以上三个关卡的通关情况如下:

  • 表 table1 具有 4 列:A1,A2,A3,B1。具有两个索引 Idx1(A1,A2,A3) 和 Idx2(B1)
  • 关卡 1:选出的索引是 Idx1
  • 关卡 2:选出的 hash info 是 (2, 0, true) (很多查询命中了 Idx1 的最左两列)
  • 关卡 3:选出了某个数据页 P3,其中包含数据 (1,1,1,1) 和 (1,2,2,2) 等等 那么建立 AHI 的过程是:在内存中,为数据页 P3 中的每一行数据建立索引
  • 对于数据(1,1,1,1),根据 hash info,选取前两列建立 AHI 的一项:(1,1)的哈希值->P3
  • 对于数据(1,2,2,2),根据 hash info,选取前两列建立 AHI 的一项:(1,2)的哈希值->P3
  • 以此类推

普度众生:终于可以使用 AHI 我们终于可以 AHI 加速查询了,假设查询条件是 A1=1 and A2=2,其满足条件:

  • 命中了索引 Idx1
  • 索引 Idx1 上的 hash info 是(2, 0, true),查询条件(A1=1 and A2=2)根据 hash info 转成(1,2)的哈希值
  • 根据此哈希值在 AHI 中查询,可查询到数据页为 P3 从以上过程可以看出,如果命中了 AHI,就可以跳过图 2 中查询索引树的 4 个步骤,一次到位找到数据页,提升性能。

总结 我们回顾一下 MySQL 建立 AHI 的整个过程:

  • 随着数据量增大,索引树变得越来越高,查询数据页成本变大
  • MySQL 引入 AHI 作为查询数据页的缓存,想降低查询数据页的成本
  • AHI 的"自适应"想解决的问题是 缓存不能太大,也不能太小
  • AHI 建立的过程中,通过不断限制条件,只为经常使用的索引和经常使用的数据页建立缓存

运维建议 理解了 AHI 的建立过程,在运维过程中就更容易理解 AHI 的状态,我们简要盘点一下 AHI 的运维:

  • innodb_adaptive_hash_index_parts。凡是缓存都会涉及多个缓存消费者间的锁竞争。MySQL 通过设立多个 AHI 分区,每个分区使用独立的锁,来减少锁竞争。
  • SHOW ENGINE INNODB STATUS。其中有 AHI 的每个分区的使用率和 AHI 的命中率。如果你的业务 AHI 使用率过低,理解了 AHI 建立的原理后,就可以分析该业务为何不命中 AHI,来判断业务是否合理,是否需要改变访问模式或者将数据冷热隔离。也可以考虑关闭 AHI,减少 AHI 的维护成本。
  • 在低版本 MySQL 上使用 AHI,先查阅 MySQL bug 列表。低版本是存在一些与 AHI 相关的影响业务的缺陷,在新版本上均已修复,新版本 MySQL 可放心使用。

本文转载自:https://mp.weixin.qq.com/s/bj6Qe98lWlrd4Hv5B0sn9w

爱可生

爱可生

粉丝 15
博文 248
码字总数 432821
作品 1
徐汇
私信 提问
加载中

评论(0)

腾讯云技术分享:MySQL AHI 实现解析

MySQL 定位用户记录的过程可以描述为:打开索引 -> 根据索引键值逐层查找 B+ 树 branch 结点 -> 定位到叶子结点,将 cursor 定位到满足条件的 rec 上;如果树高为 N, 则需要读取索引树上的 ...

腾讯云开发者社区
2017/03/14
386
2
MySQL AHI 实现解析

版权声明:本文由musazhang 原创文章,转载请注明出处: 文章原文链接:https://www.qcloud.com/community/article/904925001482373849 来源:腾云阁 https://www.qcloud.com/community 前言 ...

偶素浅小浅
2016/12/22
9
0
腾讯云数据库团队:MySQL AHI 实现解析

MySQL 定位用户记录的过程可以描述为:打开索引 -> 根据索引键值逐层查找 B+ 树 branch 结点 -> 定位到叶子结点,将 cursor 定位到满足条件的 rec 上;如果树高为 N, 则需要读取索引树上的 ...

2017/12/18
0
0
善用MySQL AHI加速神器,让你的InnoDB查询飞起来!

作者:张青林,腾讯云布道师、MySQL架构师,隶属腾讯TEG-基础架构部-CDB内核开发团队,专注于MySQL内核研发&相关架构工作,有着服务多个10W级QPS客户的数据库优化及稳定性维护经验。 腾讯云数...

张青林
2017/01/24
0
0
记一次处理MySql锁等待(Lock wait timeout exceeded)

环境 MySQL5.5 现象 A.数据更新或新增后数据经常自动回滚。 B.表操作总报 Lock wait timeout exceeded 并长时间无反应 解决方法 A.应急方法:show processlist; kill掉出现问题的进程 B.根治...

-蒋全忠-
2014/04/14
3.8W
0

没有更多内容

加载失败,请刷新页面

加载更多

C语言动态内存分配:(一)malloc/free的实现及malloc实际分配/释放的内存

一、malloc/free概述 malloc是在C语言中用于在程序运行时在堆中进行动态内存分配的库函数。free是进行内存释放的库函数。 1、函数原型 #include <stdlib.h> void *malloc( size_t size ); v...

shzwork
39分钟前
17
0
什么是JavaBean? - What is a JavaBean exactly?

问题: I understood, I think, that a "Bean" is a Java class with properties and getters/setters. 我认为,“ Bean”是具有属性和getter / setter的Java类。 As much as I understand,......

技术盛宴
46分钟前
21
0
深圳援鄂最后一批工作人员归来,88万元关爱金发放至85人

中国公益在线3月31日深圳讯 深圳援鄂最后一批工作人员归来......深圳市民政局、深圳市卫健委和深圳市慈善会发起了“深爱战疫天使基金”项目,联合龙华区慈善会和 永贤慈善基金会,进行第二次...

传承天下融媒体中心
50分钟前
15
0
easyui 的combobox设置宽度和高度自动适应,如果超出,则指定宽度和高度

<s:select list="newCostTypeMap" theme="simple" cssClass="myCombobox" cssStyle="width:200px" data-options="editable:false,panelHeight:'auto'" />$('.myCombobox').combobox({......

文文1
51分钟前
17
0
Scala的运算符

在Scala中运算符的表示法不局限于字符, 中缀运算符可以是任何方法接受参数的方法 前缀运算符放在值的前面,只能是 + - ! ~ 四者之一, 方法名为unary_*(*为运算符) 后缀运算符是任何不接受参...

dreamness
今天
23
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部