Distributed System-分布式系统 Consistent Hashing 一致性哈希

Distributed System 分布式系统 Consistent Hashing 一致性哈希

DHT

Distributed Hash Table (DHT) 是分布式系统的一个基础组件

环形 Hash 空间

把 Hash 空间头尾相连,形成一个闭合的环形

DistributedSystem-ConsistentHashing-Circle

机器和数据配对

  1. 将机器(IP或机器唯一标识作为输入)通过 Hash 算法映射到环上
  2. 将数据通过 Hash 算法映射到环上
  3. 按顺时针转动。让数据点找到跟它最近的机器点

DistributedSystem-ConsistentHashing-Pair

机器的添加与删除

向集群中增加机器 C4

DistributedSystem-ConsistentHashing-Add

只有数据 M4 会从 C2 迁移到 C4,其他数据不受影响

从集群中删除机器 C1

DistributedSystem-ConsistentHashing-Remove

只有 C1 的数据会迁移到 C3,其他数据不受影响

问题和方案

问题:当集群中的节点数量较少时,可能会出现节点在哈希空间中分布不平衡的问题。(Hash 环的倾斜)

DistributedSystem-ConsistentHashing-Question

  • A、B、C三台机器的负载极其不均衡
  • 雪崩效应
    • 在极端情况下,假如A节点出现故障,A上的数据全部转移到B上,大量的数据导可能会导致节点B的崩溃,之后A和B上所有的数据向节点C迁移,导致节点C也崩溃,由此导致整个集群宕机。

方案:虚拟节点

解决哈希环偏斜问题的方法就是,让集群中的节点尽可能的多,从而让各个节点均匀的分布在哈希空间中。

在现实情境下,机器的数量一般都是固定的,所以我们只能将现有的物理节通过虚拟的方法复制多个出来,这些由实际节点虚拟复制而来的节点被称为虚拟节点。

DistributedSystem-ConsistentHashing-Solution