转载

关于一致性hash,这可能是全网最形象生动最容易理解的文档,想做架构师的你来了解一下

问题提出

一致性hash是什么?假设有4台缓存服务器 N0,N1,N2,N3 ,现在需要存储数据 OBJECT1,OBJECT2,OBJECT3,OBJECT4,OBJECT5,OBJECT5,OBJECT7,OBJECT8 ,我们需要将这些数据缓存到这4台服务器上，相应的问题是

如何设计数据存放策略?即ObjectX 应该存放在哪台服务器上?

为了解决这个问题,我们有如下几个思路。

1. 余数hash方案

采用hash(Objectx)%4来确定服务器节点

假设 hash(OBJECT1)=2 ,由 2%4=2,可知, Object1 则应该存放到节点 N2 上假设 hash(OBJECT2)=3 ,由 3%4=3,可知, Object2 则应该存放到节点 N3 上假设 hash(OBJECT3)=1 ,由 1%4=1,可知, Object3 则应该存放到节点 N1 上假设 hash(OBJECT4)=0 ,由 1%4=1,可知, Object4 则应该存放到节点 N0 上假设 hash(OBJECT5)=5 ,由 5%4=1,可知, Object5 则应该存放到节点 N1 上假设 hash(OBJECT6)=6 ,由 6%4=2,可知, Object6 则应该存放到节点 N2 上假设 hash(OBJECT7)=7 ,由 7%4=3,可知, Object7 则应该存放到节点 N3 上假设 hash(OBJECT8)=8 ,由 8%4=0,可知, Object8 则应该存放到节点 N0 上

假设我们需要读取 Object3 的数据,则由 hash(object3)=1 可知,我们只需要访问节点 N1 即可。

1.1 现在假设 `N3` 忽然故障下线

我们面临缓存重新构造的问题

采用hash(Objectx)%3来确定服务器节点

假设 hash(OBJECT1)=2 ,由 2%3=2,可知, Object1 则应该存放到节点 N2 上假设 hash(OBJECT2)=3 ,由 3%3=0,可知, Object2 则应该存放到节点 N0 上假设 hash(OBJECT3)=1 ,由 1%3=1,可知, Object3 则应该存放到节点 N1 上假设 hash(OBJECT4)=0 ,由 0%3=0,可知, Object4 则应该存放到节点 N0 上假设 hash(OBJECT5)=5 ,由 5%3=2,可知, Object5 则应该存放到节点 N2 上假设 hash(OBJECT6)=6 ,由 6%3=0,可知, Object6 则应该存放到节点 N0 上假设 hash(OBJECT7)=7 ,由 7%3=1,可知, Object7 则应该存放到节点 N1 上假设 hash(OBJECT8)=8 ,由 8%3=2,可知, Object8 则应该存放到节点 N2 上

此时为了保证数据的准确性,我们需要将数据 Object2 从 N3 迁移到 N0 将数据 Object5 从 N1 迁移到 N2 将数据 Object6 从 N2 迁移到 N0 将数据 Object7 从 N3 迁移到 N1 将数据 Object8 从 N0 迁移到 N2

1.2 现在假设我们添加一台新的服务器 `N4`

我们面临缓存重新构造的问题

采用hash(Objectx)%5来确定服务器节点

假设 hash(OBJECT1)=2 ,由 2%5=2,可知, Object1 则应该存放到节点 N2 上假设 hash(OBJECT2)=3 ,由 3%5=3,可知, Object2 则应该存放到节点 N3 上假设 hash(OBJECT3)=1 ,由 1%5=1,可知, Object3 则应该存放到节点 N1 上假设 hash(OBJECT4)=0 ,由 0%5=0,可知, Object4 则应该存放到节点 N0 上假设 hash(OBJECT5)=5 ,由 5%5=0,可知, Object5 则应该存放到节点 N0 上假设 hash(OBJECT6)=6 ,由 6%5=1,可知, Object6 则应该存放到节点 N1 上假设 hash(OBJECT7)=7 ,由 7%5=2,可知, Object7 则应该存放到节点 N2 上假设 hash(OBJECT8)=8 ,由 8%5=3,可知, Object8 则应该存放到节点 N3 上