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; // 数据行行号或者其它含义的 valuenode * 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.

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

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

3. 所有桶的元素迁移完成之后，释放老的 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 年，并在通信、金融、交通、能源、物联网等行业成功商用落地。