AntDB-M高性能设计之hash索引动态rehash

AntDB-M支持hash索引、btree索引等索引类型，hash索引以hash表的方式实现，一个简单的hash表示意图如图1所示。hash桶下的元素节点为单向或者双向链表，数据行上某一个或者某几个字段组成索引，通过hash函数对索引字段的值进行运算，映射到某个hash桶下，hash桶下的元素节点存储了数据行的行号。

图1：hash table原理示意图

当使用 select * from table where a = value; 进行查询时，先根据value计算hash值，算出在第几个hash桶，然后遍历hash桶下的元素，根据存储的行号，取出每一行a列存储的值，与value进行比对，若完全相等，则就是要找的行。

以hash桶下的节点为双向链表举例，桶下的元素节点结构一般为

struct node { uint8 oid; // 数据行行号或者其它含义的value node * node_prev; // 上一个节点 node * node_next; // 下一个节点 }

sizeof(node)总共 8+8+8 =24个字节；

对于AntDB-M来讲，内存是非常宝贵的资源，在实现hash索引且保证性能的前提下，内存占用必须尽量小。对于数据库里的某张表，假设表总共有m行，表上有n个hash索引，则这张表就有n套hash结构，每套hash结构有m个桶节点，以上述双向链表为例，这张表的hash索引占用的内存为 n*(hash索引头节点占用内存 + m*24字节)，24个字节有时甚至比数据表中这行数据本身还要大。

AntDB-M hash索引数据结构优化

为了减少索引数据的内存占用，AntDB-M使用数组元素来模拟链表节点，不再额外分配空间存储链表节点的值。一次性分配所有的节点，避免频繁的内存分配释放。

struct array_node { uint8 prev_oid; // 上一个节点的位置 uint8 next_oid; // 下一个节点的位置 }

sizeof(array_node)总共 8+8 =16个字节，oid为0代表上一个、下一个节点为空，即本节点的前面或者后面没有其它节点了。对于某张有n行数据的数据表，申请分配数组空间array_node[n]，对于数组中的某个元素array_node[k]，k有两个含义：

数组中的下标，用于访问array_node[k]. prev_oid和array_node[k]. next_oid；

array_node[k]指向数据库此表中的第k行，可以去访问这张表第k行的内容。这样就避免存储了uint8 oid(数据行行号)，节省了1/3的内存空间；如果hash桶下的节点是单向链表，则节省了2/3的内存。

下面举例说明：

假设一张数据表初始建表时预分配了m行，则对应的hash结构的bucket个数为n(n在实现时为大于m的最小素数)，对应hash索引的桶节点数组预分配n个元素，即uint8 bucket_head[n], bucket_head记录每个桶的头节点指向第几行(也代表指向数组array_node的第几个元素)；分配连续数组array_node[m], 对应于bucket下面双向链接的节点元素。

假设对于某个hash索引, 数据表的第3行，第29行，第36815行都映射到桶2下，则桶2的头结点指向表上的第3行数据, 也指向array_node的第3个元素。

bucket_head[2]=3； array_node [3] ->prev_oid=0； array_node [3] -> next_oid=29； array_node [29] ->prev_oid=3； array_node [29] ->next_oid=36815； array_node [36815] ->prev_oid=29； array_node [36815] ->next_oid=0；

这样，同样做到了前后的遍历(next_oid=0表示这是链表上的最后一个有效元素)，相比前一种方式，通过数组来模拟链表，内存占用减少，并且数组的内存是一次性分配出来，内存连续，访问速度快。

随着业务的运行，数据表的规模可能不断地扩大，比如一张表刚创建时预分配1000万行，运行一段时间后扩展到5000万行，如果hash结构的bucket个数还是1000万左右，则每个bucket下面的平均有5个元素，hash冲突增大，查找效率降低。此时，我们需要对数据进行rehash，动态调整hash结构，减少hash冲突，同时又不阻塞hash table的增删改查。

AntDB-M 动态rehash原理

如图2所示，每个hash桶下面都有一把桶锁lock，当读取、插入、删除桶下元素时，需要对桶加锁。migrate_node指示当前正在迁移的bucket，具体迁移某个bucket时，也是先对bucket加桶锁，迁移完bucket下面的所有元素后释放桶锁，然后migrate_node再指向下一个bucket.

每当表的数据行增加一定数量时，新建一个新的hash_table结构，此时新老两套hash_table并存；

遍历老的hash_table, 从第一个桶开始，加桶锁，遍历桶下面的每一个元素，计算它在新的hash_table上的位置，迁移插入到新的hash_table结构；

所有桶的元素迁移完成之后，释放老的hash_table结构，数据的增删改查完全切换到新的hash_table;

图2：AntDB-M动态rehash示意图

为何动态rehash的过程不阻塞hash table的增删改查，本文以查找和插入举例，用流程图的方式说明如下。更新(分解为查找+删除+插入)和删除的流程也是类似的，不管是查找，插入、更新、删除，都要先在老的hash结构上查找数据位于哪个bucket下面。

图3：动态rehash过程中的find

图4：动态rehash过程中的insert

性能优势

表扩容时动态扩展hash结构，不阻塞AntDB-M服务及应用，对用户透明。AntDB-M内部通过增加hash桶个数和迁移桶下元素，减少hash冲突，使得hash索引性能不因数据行的增多而降低，快速定位数据。

综上所述，hash索引巧妙设计的数据结构，以及动态rehash的并行算法使得AntDB-M的hash索引具备持续高性能的特性，以满足复杂业务应用的性能需求。

关于AntDB数据库

AntDB数据库始于2008年，是亚信科技自主研发的分布式关系型数据库品牌，AntDB-M是面向高性能内存型数据库，是AntDB的子产品之一，在运营商的核心系统上，为全国24个省份的10亿多用户提供在线服务，具备高性能、弹性扩展、高可靠等产品特性，峰值每秒可处理百万笔通信核心交易，保障系统持续稳定运行近15年，并在通信、金融、交通、能源、物联网等行业成功商用落地。