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.
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年,并在通信、金融、交通、能源、物联网等行业成功商用落地。