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

当 使 用   s e l e c t   *   f r o m   t a b l e   w h e r e   a   =   v a l u e ;   进 行 查 询 时 ， 先 根 据 v a l u e 计 算 h a s h 值 ， 算 出 在 第 几 个 h a s h 桶 ， 然 后 遍 历 h a s h 桶 下 的 元 素 ， 根 据 存 储 的 行 号 ， 取 出 每 一 行 a 列 存 储 的 值 ， 与 v a l u e 进 行 比 对 ， 若 完 全 相 等 ， 则 就 是 要 找 的 行 。

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

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

s i z e o f ( n o d e ) 总 共   8 + 8 + 8   = 2 4 个 字 节 ；

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

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

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

s i z e o f ( a r r a y _ n o d e ) 总 共   8 + 8   = 1 6 个 字 节 ， o i d 为 0 代 表 上 一 个 、 下 一 个 节 点 为 空 ， 即 本 节 点 的 前 面 或 者 后 面 没 有 其 它 节 点 了 。 对 于 某 张 有 n 行 数 据 的 数 据 表 ， 申 请 分 配 数 组 空 间 a r r a y _ n o d e [ n ] ， 对 于 数 组 中 的 某 个 元 素 a r r a y _ n o d e [ k ] ， k 有 两 个 含 义 ：

• 数 组 中 的 下 标 ， 用 于 访 问 a r r a y _ n o d e [ k ] .   p r e v _ o i d 和 a r r a y _ n o d e [ k ] .   n e x t _ o i d ；

• a r r a y _ n o d e [ k ] 指 向 数 据 库 此 表 中 的 第 k 行 ， 可 以 去 访 问 这 张 表 第 k 行 的 内 容 。 这 样 就 避 免 存 储 了 u i n t 8   o i d ( 数 据 行 行 号 ) ， 节 省 了 1 / 3 的 内 存 空 间 ； 如 果 h a s h 桶 下 的 节 点 是 单 向 链 表 ， 则 节 省 了 2 / 3 的 内 存 。

下 面 举 例 说 明 ：

假 设 一 张 数 据 表 初 始 建 表 时 预 分 配 了 m 行 ， 则 对 应 的 h a s h 结 构 的 b u c k e t 个 数 为 n ( n 在 实 现 时 为 大 于 m 的 最 小 素 数 ) ， 对 应 h a s h 索 引 的 桶 节 点 数 组 预 分 配 n 个 元 素 ， 即 u i n t 8   b u c k e t _ h e a d [ n ] ,   b u c k e t _ h e a d 记 录 每 个 桶 的 头 节 点 指 向 第 几 行 ( 也 代 表 指 向 数 组 a r r a y _ n o d e 的 第 几 个 元 素 ) ； 分 配 连 续 数 组 a r r a y _ n o d e [ m ] ,   对 应 于 b u c k e t 下 面 双 向 链 接 的 节 点 元 素 。

假 设 对 于 某 个 h a s h 索 引 ,   数 据 表 的 第 3 行 ， 第 2 9 行 ， 第 3 6 8 1 5 行 都 映 射 到 桶 2 下 ， 则 桶 2 的 头 结 点 指 向 表 上 的 第 3 行 数 据 ,   也 指 向 a r r a y _ n o d e 的 第 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；

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

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

如 图 2 所 示 ， 每 个 h a s h 桶 下 面 都 有 一 把 桶 锁 l o c k ， 当 读 取 、 插 入 、 删 除 桶 下 元 素 时 ， 需 要 对 桶 加 锁 。 m i g r a t e _ n o d e 指 示 当 前 正 在 迁 移 的 b u c k e t ， 具 体 迁 移 某 个 b u c k e t 时 ， 也 是 先 对 b u c k e t 加 桶 锁 ， 迁 移 完 b u c k e t 下 面 的 所 有 元 素 后 释 放 桶 锁 ， 然 后 m i g r a t e _ n o d e 再 指 向 下 一 个 b u c k e t .

1 .   每 当 表 的 数 据 行 增 加 一 定 数 量 时 ， 新 建 一 个 新 的 h a s h _ t a b l e 结 构 ， 此 时 新 老 两 套 h a s h _ t a b l e 并 存 ；

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

3 .   所 有 桶 的 元 素 迁 移 完 成 之 后 ， 释 放 老 的 h a s h _ t a b l e 结 构 ， 数 据 的 增 删 改 查 完 全 切 换 到 新 的 h a s h _ t a b l e ;

图 2 ： A n t D B - M 动 态 r e h a s h 示 意 图

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

图 3 ： 动 态 r e h a s h 过 程 中 的 f i n d

图 4 ： 动 态 r e h a s h 过 程 中 的 i n s e r t

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

综 上 所 述 ， h a s h 索 引 巧 妙 设 计 的 数 据 结 构 ， 以 及 动 态 r e h a s h 的 并 行 算 法 使 得 A n t D B - M 的 h a s h 索 引 具 备 持 续 高 性 能 的 特 性 ， 以 满 足 复 杂 业 务 应 用 的 性 能 需 求 。

关 于 A n t D B 数 据 库

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