一致性HASH的记录

下面是相关内容的连接

 

http://lishuaibt.iteye.com/blog/609364

 

http://sebug.net/paper/databases/nosql/Nosql.html

 

大概理解总结了下

 

 

一致性hash

 

1:集群CACHE的命中问题

例如原有4台CACHE服务器编号为：0，1，2，3

用户数据按照hash(用户ID) mod 4 分别存在4台服务器上

1 mod 4 = 1

2 mod 4 = 2

3 mod 4 = 3

4 mod 4 = 0

5 mod 4 = 1

6 mod 4 = 2

...

 

在CACHE服务器不出现问题或是不需要增加服务器的情况下上述解决方案工作正常

当需要添加一台服务器5的时候问题就来了

 

因为现在的N变成了5，那么

1 mod 5 = 1

2 mod 5 = 2

3 mod 5 = 3

4 mod 5 = 4

5 mod 5 = 0

6 mod 5 = 1

...

 

那么hash(用户ID)=5和6的数据所在的服务器位置发生了变化，也就是说需要重新计算用户所在CACHE服务器

的位置，严重的需要进行数据迁移等等操作。

 

2:一直性HASH的出现

为了尽量解决这种问题(可能不能完全避免)，用一致性HASH能相对大的程度解决问题

2^32的闭环上将4台服务器也用hash算法计算出hash值顺时针分布在该环上

 

（2）访问方式

如果有一个写入缓存的请求，其中Key值为K，计算器hash值Hash(K)， Hash(K) 对应于图 - 1环中的某一个点，如果该点对应没有映射到具体的某一个机器节点，那么顺时针查找，直到第一次找到有映射机器的节点，该节点就是确定的目标节点，如果超过了2^32仍然找不到节点，则命中第一个机器节点。比如 Hash(K) 的值介于A~B之间，那么命中的机器节点应该是B节点（如上图 - 1）。

 

（3）增加节点的处理

如上图 - 1，在原有集群的基础上欲增加一台机器F，增加过程如下：

计算机器节点的Hash值，将机器映射到环中的一个节点

增加机器节点F之后，访问策略不改变，依然按照（2）中的方式访问，此时缓存命不中的情况依然不可避免，不能命中的数据是hash(K)在增加节点以前落在C～F之间的数据。尽管依然存在节点增加带来的命中问题，但是比较传统的hash取模的方式，一致性hash已经将不命中的数据降到了最低。