基于一致性哈希算法的分布式数据库高效扩展方法

大数据背景下，分布式数据库在使用过程中经常需要扩容，在扩容过程中，各存储节点的哈希值需要重新计算，数据对象也需要大量迁移数据。本文通过预留子分区识别位、数据库扩容过程中物理存储节点编码“高位不变，低位置1”等技术手段实现数据库的高效扩展。对比实验标明：该方法避免了分布式数据库在扩容时的已有存储节点哈希值的重新计算工作，减少了数据对象的数据迁移量，提高了分布式数据库的扩展效率。

随着大数据广泛应用于各个行业领域，越来越多的应用系统采用分布式数据库来管存储管理业务数据[1] [2] [3] [4]。分布式数据库是指在物理上分散存储在的多个计算机，但逻辑上统一的数据库[5]。分布式数据库中的数据分散在多个存储节点上，所以可适当提高系统冗余备份，保障数据的可靠性。在分布式存储系统中，存储节点经常会发生动态的变化，比如节点的失效和增添，如何在节点状态变化时仍然能够对外提供良好的服务，保证数据的一致性，成为一个重要的问题。为此麻省理工学院的Karger 等人提出了一致性哈希算法，修正了简单哈希算法带来的问题，建立了从物理存储节点到虚拟存储节点的映射关系——哈希表(DHT, Distributed Hash Table)，通过对存储对象关键因子的Hash 计算，把数据对象均衡地分布于多个物理存储节点上。在节点发生变化时，发生迁移的数据对象最少，这样分布式数据库在节点变化频繁的场合也可以得到应用[6] [7] [8]。

大数据时代的来临，数据库的增长速度越来越快，在数据库扩展过程中，当原有的地址定义字节长度不能满足物理节点的编号需求时， 如256 个存储节点升级为512 个存储节点， 就要对地址定义进行“升位”。此时计算各个存储节点的哈希值也需要重新，这样就耗费了大量的计算资源和时间，同时存储在各个节点的存储对象也因Hash 值的对应关系发生变化而需要大量迁移。

本文通过对基于一致性哈希算法的哈希空间进行改进，在对物理存储节点进行编码时，预留了若干的子空间标识位，现有物理存储节点的编码放在高N 位，低M 位预留为子空间标识位，预留标识位全部预设为0。

当物理存储节点的数量超过N 位编码容量而需要扩容时， 采用“高位不变， 低位置1”的方法， 进行编码的扩展，这样，原有的物理节点编码不变，其哈希值也不变，在哈希空间的位置也不变，存在原物理节点上的数据也不需要迁移。减小了数据库扩展过程中哈希值的计算量，降低了数据迁移量。

2. 预留分区的哈希空间构造 一致性哈希算法将整个哈希空间组织成一个虚拟的圆环，我们称这个圆环为DHT (Distributed Hash Table)环，分布式数据库的各个物理存储节点按一致性哈希算法映射到DHT 环中，成为虚拟存储节点。

在实现过程中，首先根据对物理存储节点进行编码C，对编码采用CRC 等算法对编码进行哈希运算得到