InnoDB中Adaptive hash index存在问题、Percona改进及一个bug

简介:

背景
  Adaptive hash index  (AHI) 是InnoDB中用于加速索引查找的一个结构。InnoDB本身不支持hash索引,所有的索引检索都走B树查询。AHI可以认为是“索引的索引”。当对一个页面的访问次数满足一定条件后,将这个页面的地址存在一个hash表中,下次查询可以直接访问到页面,不需要走B树查询。

问题
  天下没有免费的午餐,在加速查询的同时,AHI与其他缓存结构一样,也面临维护的问题。作为一个全局结构,在更新时必然有一个全局锁操作(btr_search_latch),一个查询里面可能会对其作多次加x_lock操作。

 

Percona的改进
    如同Buffer Pool可以用多个instance减少锁冲突,Percona也用类似的策略来处理AHI的锁问题。由于本身就是Hash结构,这个处理既自然又方便。所有的数据节点都必然属于一个索引,AHI就用索引id来作分区的key(block->index->id).计算规则为(index_id % btr_search_index_num), 这个 btr_search_index_num 就是 Percona中引入的只读参数 innodb_adaptive_hash_index_partitions。
  全局的btr_search_latch则分为btr_search_index_num 份,AHI中每个block中新增一个成员指向 btr_search_latch_part[i].

 

淘汰流程
  缓存结构必然还涉及一个淘汰流程,大致逻辑如下:
  a)x_lock(block->btr_search_latch);
  b)从hash表中删除这个page信息
  c)x_unlock

  但因为并非所有的page都在AHI中, 若所有的页面操作都作这个处理,则会导致很多额外的锁冲突(x_lock排他),因此需要一个“预判断“的流程。
  简单的判断流程是
  a) s_lock(block->btr_search_latch);
  b) 判断block->index是否为空
  c) 若为空则unlock后直接返回(说明没有在AHI中)
  ….
  (后续流程不表)

 

预判流程逻辑
  这个预判断流程在 btr_search_index_num =1时是没有问题的,但当btr_search_index_num>1时,由于block->btr_search_latch是可变的,也就说存在一种状态,在线程A访问这个锁的时候,线程B刚好把某个page替换掉,甚至于会将这个block用于缓存另外一个page。这样线程A就”锁错了“
  由于存在这种中间状态,在Percona现在的实现上面是通过double-check,在加锁之后作了若干判断,若出现上述的情况,则重试。代码在函数(btr_search_drop_page_hash_index)中

retry:
          if (btr_search_index_num > 1) {
                rw_lock_t*      btr_search_latch;

                /* FIXME: This may be optimistic implementation still. */
                btr_search_latch = (rw_lock_t*)(block->btr_search_latch);
                if (UNIV_LIKELY(!btr_search_latch)) {
                        if (block->index) {
                                goto retry;
                        }   
                        return;
                }   
                rw_lock_s_lock(btr_search_latch);
                if (UNIV_LIKELY(btr_search_latch != block->btr_search_latch)) {
                        rw_lock_s_unlock(btr_search_latch);
                        goto retry;
                }   
                if (UNIV_LIKELY(!block->index)) {
                        rw_lock_s_unlock(btr_search_latch);  //(*)
                        goto retry;
                }   
                index = block->index;
                ut_a(btr_search_latch == btr_search_get_latch(index->id));
         }

 

其中行(*)也是一种中间状态,表示这个block刚刚淘汰掉。因为这些状态被认为是出现在其他线程在AHI中作淘汰操作时出现的,因此多次重试可以认为是等待其他线程完成。

 

BUG描述
但在实现上却漏考虑了一个背景,就是虽然innodb_adaptive_hash_index_partitions是只读变量,但AHI确是可以动态开关的。当用户调用 set global innodb_adaptive_hash_index=off时,会将所有的block.index清空。虽然AHI被关闭后,不会再有“淘汰”的逻辑,但page从LRU list中被淘汰的时候,还是必须得调用btr_search_drop_page_hash_index的,上面的代码逻辑仍会走到(*)行。在这个线程中就出现了死循环,从客户端看,就是查询线程等待。


复现步骤
  1、设置my.cnf中
    innodb_adaptive_hash_index_partitions=8
    innodb_buffer_pool_size=32M
 
  2、souce ahi_loop.txt;
  
 现象是客户端出现等待,即使客户端取消该查询,但仍然占用一个cpu(死循环),若多次重试,CPU IDLE会跌为0

 

简单修改是在关闭AHI的时候,将block->index设置为NULL的同时,加一句 block->btr_search_latch = NULL;

目录
相关文章
|
6月前
|
存储 关系型数据库 MySQL
索引大战:探秘InnoDB数据库中B树和Hash索引的优劣
索引大战:探秘InnoDB数据库中B树和Hash索引的优劣
63 0
|
2月前
|
存储 关系型数据库 MySQL
InnoDB and MyISAM Index Statistics Collection
存储引擎收集表统计信息,供优化器使用,关键数据为平均值组大小,反映相同键前缀值的行数均值。该值影响索引效率,值越大,索引查找行数越多,效用越低。MySQL通过调整`innodb_stats_method`和`myisam_status`系统变量控制统计方法,涉及NULL值处理,如nulls_equal将所有NULL视为同一值组,可能影响索引使用决策。通过设置变量可优化统计信息收集,提升查询性能。
|
5月前
|
缓存 关系型数据库 MySQL
MySQL数据库——InnoDB引擎-架构-内存结构(Buffer Pool、Change Buffer、Adaptive Hash Index、Log Buffer)
MySQL数据库——InnoDB引擎-架构-内存结构(Buffer Pool、Change Buffer、Adaptive Hash Index、Log Buffer)
98 3
|
SQL 存储 关系型数据库
Mysql 的InnoDB引擎下支持hash索引吗?
Mysql 的InnoDB引擎下支持hash索引吗?
868 0
Mysql 的InnoDB引擎下支持hash索引吗?
|
SQL NoSQL 安全
Percona 8.0.30中"show engine innodb status"导致coredump排查及分析
Percona 8.0.30中"show engine innodb status"导致coredump排查及分析
|
SQL 关系型数据库 MySQL
InnoDB这个将近20年的"bug"修复了
InnoDB这个将近20年的"bug"修复了
|
存储 缓存 算法
InnoDB & index页-mysql详解(二)
InnoDB & index页-mysql详解(二)
|
SQL 关系型数据库 MySQL
InnoDB这个将近20年的"bug"修复了
InnoDB这个将近20年的"bug"修复了
|
关系型数据库 MySQL
MYSQL INNODB中hash查找表的实现
原创有误请指出: 版本:5.7.14 源码位置为hash0hash.h hash0hash.cc 作为一种时间复杂度最优为O(1)的数据结构,但是最坏时间复杂对位O(n)的一种数据结构,但是在 良好的设计hash函数的情况下性能还是非常好的。
1206 0