一致性hash算法

当我们均匀的把请求分散在多个服务节点的时候,可以使用请求号然后对节点数取模,即使在服务节点增加或者减少的时候,依旧可以正常运行,因为请求落到不同的服务节点,不会影响整体运行。

然而在某些情况下,比如分布式缓存,依赖查找的key计算hash值来寻找服务节点,假设服务节点的数量发生了改变,那么整个集群将处于不可用状态,因为一旦发生了数量上的改变,查找到的服务节点很有可能不是同一个节点了,那么缓存基本都会miss,必须进行数据重分布后整个集群才能继续对外提供服务,这样的代价太大了。

一致性hash就可以部分的解决这个问题,或者是相对较小代价下解决这个问题。

首先,上述提到的hash取模,取出来的是定值,一直索引到服务节点。而一致性hash,则依赖范围查找。

我们来看看简单的一致性hash的实现。在定义中,将0-2^32-1个数顺时针绕成一个圆,然后对于集群中的节点,通过某些方法计算hash值 (0-2^32-1),然后把该节点放到圆对应的位置上去。

而对于Key,计算它的hash,然后将hash放到该圆上,顺时针的查找最近的节点,那么就找到了相应的节点。

假设目前有4个节点,分别为

1) NodeA hash 128
2) NodeB hash 256
3) NodeC hash 384
4) NodeD hash 512

插入4个键,分别为

1) KeyA hash 129
2) KeyB hash 257
3) keyC hash 385
4) KeyD hash 513

那么由4个节点,将该圆切成了4部分:

1) [129, 256] -> NodeB
2) [257, 384] -> NodeC
3) [385, 512] -> NodeD
4) [513, 2^32-1] [1, 128] -> NodeA

由此可见,相应的键的分布为

1) KeyA -> NodeB
2) KeyB -> NodeC
3) KeyC -> NodeD
4) KeyD -> NodeA

上述就是大概的分布方式。

该分布方式的最大好处就是,当4个节点中移除了某个节点,或者是增加了一个新的节点,那么大部分Key的分不行不会发生改变,只会影响小部分的Key。

假设移除了一个节点B,那么原先属于NodeB的Key,都会映射到NodeC中,其余不会被影响。

假设在NodeB和NodeC中新增了一个节点NodeE,则NodeB与NodeC之间的Key会被映射到NodeE中,其余不受影响。

简单的理解大概就是这样,先做个笔记。

共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day