一致性哈希在分布式数据库分片中的应用 题目描述 想象你正在设计一个分布式数据库，数据被分散存储在多个物理分片（Shard）上。随着数据量的增长，你希望增加分片数量以水平扩容；反之，当负载降低时，你可能希望减少分片以节省资源。使用传统哈希函数（例如 hash(key) % N ）时，分片数量N的变化会导致绝大部分数据被重新映射到新的分片，引发大规模数据迁移，系统开销巨大。 一致性哈希算法 能解决这个问题。它将哈希空间组织成一个 虚拟环 ，将节点（分片）和数据键都映射到这个环上，每个键被分配到 顺时针方向 遇到的第一个节点。当增删节点时，只影响环上相邻节点的数据，从而大幅减少数据迁移量。 本题要求： 理解一致性哈希的基本原理。 通过虚拟节点（Virtual Node）解决节点分布不均的问题。 模拟一致性哈希在分片数量变化时的数据迁移过程。 解题步骤 1. 构建哈希环 假设哈希函数能将任意输入映射到一个固定范围（例如 0 ~ 2^32-1 ）的整数，这个范围构成一个 哈希环 。 将每个物理分片（例如服务器节点）通过哈希函数映射到环上的一个位置。例如，节点A的哈希值为 hash(“A”) ，将其放在环上对应的点。 2. 数据键的分配 对每个数据键（例如主键 key ），计算其哈希值 hash(key) 。 在环上 顺时针 找到第一个哈希值 大于等于 hash(key) 的节点，这个节点就是该键所属的分片。 如果没找到，则回绕到环的开头，选择环上第一个节点。 3. 增加或删除节点 增加节点 ：在环上加入新节点的位置，只影响新节点 逆时针方向 到前一节点之间的数据，这些数据会迁移到新节点。 删除节点 ：移除节点后，原本属于它的数据会顺时针迁移到下一个节点。 这样，只有局部数据被重新分配，而不是全部数据。 4. 虚拟节点（Virtual Node）解决负载不均 如果物理节点较少，可能因哈希值分布不均导致某些节点负载过高。 解决方案：为每个物理节点生成多个 虚拟节点 ，每个虚拟节点映射到环上的不同位置。 数据键先映射到虚拟节点，再通过虚拟节点与物理节点的对应关系找到最终分片。 优点：虚拟节点分散在环上，使得数据分布更均匀，也便于在扩缩容时平滑调整负载。 5. 模拟数据迁移 假设初始有3个物理节点（A、B、C），每个节点有100个虚拟节点。 增加新节点D，同样为其分配100个虚拟节点。 此时，原本分配到A、B、C的部分虚拟节点的数据，会因为D的虚拟节点插入环中，而改由D的虚拟节点负责。 迁移的数据量 ≈ 新节点虚拟节点数 / 总虚拟节点数 × 总数据量。 6. 算法实现要点 使用有序结构（如红黑树）存储虚拟节点在环上的位置，以支持快速的顺时针查找。 维护虚拟节点到物理节点的映射表。 添加/删除节点时，只更新受影响的数据键。 举例说明 假设哈希环范围是 0~9（实际中通常更大，如 0~2^32-1），初始有2个节点： 节点A的哈希值为2，节点B的哈希值为6。 数据键 key1 哈希值为3，顺时针找到节点B（哈希值6），所以 key1 属于B。 现在增加节点C，哈希值为4。 原来哈希值在(2,4]之间的数据（例如哈希值为3的 key1 ）会从B迁移到C。 其他数据不受影响。 通过虚拟节点，我们可以让A、B、C各自在环上拥有多个代表点，使得数据分布更均匀。 关键优势 可扩展性：增删节点只影响少量数据迁移。 负载均衡：通过虚拟节点分散热点。 广泛应用于分布式缓存、数据库分片、负载均衡器等场景。 通过以上步骤，你可以实现一个基本的一致性哈希分片系统，并理解其在分布式数据库分片中的核心价值。