为了在节点数目发生改变时尽可能少的迁移数据
将所有的存储节点排列在收尾相接的Hash环上,每个key在计算Hash后会顺时针找到临近的存储节点存放。而当有节点加入或退出时仅影响该节点在Hash环上顺时针相邻的后续节点。
- 优点:加入和删除节点只影响哈希环中顺时针方向的相邻的节点,对其他节点无影响。
- 缺点:数据的分布和节点的位置有关,因为这些节点不是均匀的分布在哈希环上的,所以数据在进行存储时达不到均匀分布的效果。
📌一致性 Hash 算法背景:
对于分布式存储,不同机器上存储不同对象的数据,我们使用哈希函数建立从数据到服务器之间的映射关系。
使用简单的Hash函数:
m = hash(o) mod n
其中,o为对象名称,n为机器的数量,m为机器编号。考虑以下例子:
3个机器节点,10个数据 的哈希值分别为1,2,3,4,…,10。使用的哈希函数为:(m=hash(o) mod 3)
- 机器0 上保存的数据有:3,6,9
- 机器1 上保存的数据有:1,4,7,10
- 机器2 上保存的数据有:2,5,8
当增加一台机器后,此时n = 4,各个机器上存储的数据分别为:
机器0 上保存的数据有:4,8 机器1 上保存的数据有:1,5,9 机器2 上保存的数据有:2,6,10 机器3 上保存的数据有:3,7
只有数据1和数据2没有移动,所以当集群中数据量很大时,采用一般的哈希函数,在节点数量动态变化的情况下会造成大量的数据迁移,导致网络通信压力的剧增,严重情况,还可能导致数据库宕机。
一致性哈希算法的提出:
一致性哈希算法在1997年由麻省理工学院中提出的,设计目标是为了解决分布式缓存数据变动和映射问题。假设集群中的某个机器宕机了,分母数量改变了,自然取余数不OK了。
提出一致性Hash解决方案。 目的是当服务器个数发生变动时, 尽量减少影响客户端到服务器的映射关系。它可以保证当机器增加或者减少时,节点之间的数据迁移只限于两个节点之间,不会造成全局的网络问题。
📌 一致性 Hash 环:
1.算法构建 Hash 环:
一致性哈希算法必然有个hash
函数并按照算法产生hash
值,这个算法的所有可能哈希值会构成一个全量集,这个集合可以成为一个hash
空间[0,2^32-1]
,这个是一个线性空间,但是在算法中,我们通过适当的逻辑控制将它首尾相连(0 = 2^32)
,这样让它逻辑上形成了一个环形空间。
它也是按照使用取模的方法,节点取模法是对节点(服务器)的数量进行取模。而一致性Hash算法是对2^32取模,简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希环如下图:整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1, 0和2^32-1在零点中方向重合,我们把这个由2^32个点组成的圆环称为Hash环。
2.服务器 IP 节点映射:
将集群中各个IP节点映射到环上的某一个位置。
将各个服务器使用Hash进行一个哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置。假如4个节点NodeA、B、C、D,经过IP地址的哈希函数计算(hash(ip)),使用IP地址哈希后在环空间的位置如下:
3.Key 落键规则:
当我们需要存储一个kv键值对时,首先计算key的hash值,hash(key),将这个key使用相同的函数Hash计算出哈希值并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器,并将该键值对存储在该节点上。
如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:根据一致性Hash算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。
📌一致性哈希算法特点:
1.容错性:
假设Node C宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性Hash算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。简单说,就是C挂了,受到影响的只是B、C之间的数据,并且这些数据会转移到D进行存储。
2.扩展性:
数据量增加了,需要增加一台节点NodeX,X的位置在A和B之间,那收到影响的也就是A到X之间的数据,重新把A到X的数据录入到X上即可,不会导致hash取余全部数据重新洗牌。
3.数据倾斜:
Hash环的数据倾斜问题
一致性Hash算法在服务节点太少时,容易因为节点分布不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题。
例如系统中只有两台服务器: