以 web 为例,cache 节点(如 Redis Memcache)广泛用于 web 中,以提升效能。随着 web 规模扩大,单个节点无论是从效能上还是容量上都无法支撑大规模的业务,所以需要用多个节点以提升效能和容量。

在多个节点下,给定某个 object,客户端如何知道它储存在哪个节点呢?最简单的做法是选取某个节点做为元资料服务器,记录每个 object 存放的节点,每次访问该 object 时,客户端首先访问元资料服务器,获取其所存放的节点,最后从该节点获取 object。元资料服务器需要维护所有 object 的位置资讯,并且每次访问 object 都需要先访问元资料服务器,如此,元资料服务器容易成为效能和容量的瓶颈,不利于大规模扩充套件。

去中心化的系统最大优点之一就是易水平扩充套件,那是否有办法可以去除上述元资料服务器呢。答案是肯定的,比如计算 object 的 hash 值,然后均匀的分布到各个节点上。

但是如果某个节点宕机,剔除宕机节点后数目为 N – 1,此时对映关系变为:

另外,可能由于负载过高,需要新增一个节点,此时对映关系为:

无论是增加还是减少节点,都有可能会改变对映关系,造成大量请求的 miss。那是否能避免大量的 miss 呢?答案也是肯定的,一致性杂凑解决了节点增减造成大量 hash 重定位的问题。

当某个节点宕机时,仅有该节点的物件被重杂凑到相邻节点上。

与此类似,当新增一个节点时,仅有一个节点的部分 object 需要重杂凑。

节点的位置是由自身杂凑值决定的,它们的分布并非均匀,特别当节点数目很少时,容易造成 object 的分布不均匀,即平衡性低,例如:

为了解决这个问题,我们引入虚拟节点,虚拟节点实际上是物理节点的复制品,一个物理节点包含多个虚拟节点,我们将这些虚拟节点对映到数值空间 [0 2^32 – 1],对于某个 object,我们根据上节步骤计算该 object 存放的虚拟节点,进而得出物理节点。如下图共有 2 个物理节点,每个物理节点有三个虚拟机器节点。当虚拟节点越多,虚拟节点的位置分布越均匀,相应的,对映到物理节点的 object 数目也越均匀,提高了平衡性。

透过一致性杂凑,客户端可以在本地计算 object 的存放位置,去除了中心节点,使得系统容易水平扩充套件,便于按需提升/降低整体的容量和效能,同时避免了每次增删节点造成大量杂凑重定位的问题,最大化的减少了资料迁移。为使 object 能够尽可能均衡的分散在各个节点上,一致性杂凑引入了虚节点,以提高平衡性。