架构师训练营第 5 周 - 一致性 hash 算法总结及作业

发布于: 10 小时前

在了解一致性hash算法之前,最好先来了解一下其应用场景,在了解了其应用场景之后,再来理解一致性hash算法,就比较容易了,也能体现一致性hash算法的优点。


场景描述

假设有三台服务器,用于缓存图片,我们为这三台服务器编号为:0,1,2。现在有3万张图片需要缓存,我们希望这3万张图片能均匀的分布在这三台服务器上,以便它们能够分摊缓存的压力。也就是说每台服务器需要缓存大约1万张图片,那么,我们应该怎么做呢?如果我们没有任何规则的将这3万张图片均匀的分布到这3台服务器上,可以满足我们的要求吗?可以!,但是这样做的话,访问某张图片的时候就会遇到问题,我们需要遍历这3台服务器,从3万个缓存项目找到我们需要的图片,遍历过程效率太低,时间太长,当我们找到需要的缓存项时,时长可能是不被接受的,那么也就失去了缓存的意义。缓存的目的就是提高访问速度,改善用户体验,减轻后端服务器的压力,如果每访问一个缓存项都需要遍历所有缓存服务器时,想想都觉得累。那么我们该怎么办呢?原始的做法是对缓存项进行哈希,将hash后的结果对缓存服务器数量进行取模操作,通过取模后的结果,决定将该缓存项缓存在哪台服务器上。

具体的实现过程如下:

1、我们以图片的名称作为访问的key

2、图片的名称是不重复的,这样经过hash计算之后,都会得到一个不同的结果值

3、计算公式为:hash(图片名称)%N,N代表缓存服务器的数量

在经过以上的过程之后,每张图片都能够对应到一台缓存服务器(3台缓存服务器),如下图所示:

由于图片的名称和服务器是固定不变的,所以每次取模出来的值都是一样的,都能唯一映射到一台缓存服务器,这样再访问任意图片的时候,就不用再遍历所有服务器,直接定位至某一台缓存服务器,实现高效访问。

但这种方式存在一些问题,主要的问题就是:

1、取模的N是取的缓存服务器的数量,这样就和缓存服务器强耦合,如果增(删)缓存服务器,由于除数变化,被除数不变,就会造成余数发生变化,余数变化,则以前和缓存服务器之间的映射就失效了。放在以上的应用场景中就是:大量的图片通过hash取模后不能映射到缓存服务器(也会有一些图片会存在有效映射),那么就只有从后端去拿图片,这样在高并发的场景下,就会造成成缓存雪崩,给后端服务器造成巨大的IO压力,有可能造成整个系统瘫痪

由于原始hash算法的这种缺陷,所以一致性hash算法就出现了。


一致性hash算法的概念

其实,一致hash算法也是使用取模的方法,只不过它不是对服务器的数量进行取模(这样会跟服务器产生强耦合),而是对一个固定常数2^32取模。

首先,我们把2^32想象成一个圆,就像钟表一样,钟表的圆是由60个点组成的圆,而此处我们把这个圆想象成是由2^32个点组成的圆,示意图如下:

圆上方的点代表0,0点右侧第一个点代表1,以此类推,2、3、4、5......2^32-1,0点的左侧第一个点就是2^32-1。我们把这个由2^32组成的圆环称为hash环。

服务器在经过hash运算并取模后,会对应到圆上的一个唯一点,同时被缓存的对象经过同样的运算后也会对应到一个唯一的点,然后从顺时针开始离他最近的服务器节点,就是它需要被缓存的服务器节点。

具体实现过程如下:

1、算法公式为:hash(对象/节点)%2^32

2、将所有的缓存服务器节点结过算法计算后,会唯一对应到环上的一个点,记为:A、B、C

3、将所有需要被缓存的对象结处算法计算后,同样会对应到环上的一个点(有可能会与服务器节点合,正好就是它),然后按顺时针查找离该对象最近的服务器节点,就是该对象缓存的宿主

我们还是套用上面的应用场景:

1、假设现在的缓存服务器还是3台,设为:A、B、C;采用服务器Ip进行hash计算

2、需要被缓存的图片有4张,设为:P1、P2、P3、P4;采用图片名称进行hash计算

3、在经过一致性hash算法计算后,环上的分布如下图所示

在经过一致性hash计算之后,P1、P4对应的缓存服务器为B;P2对应的缓存服务器为C;P3对应的缓存服务器为A。这样数据也有大致均匀的分布到各个服务器节点之上,服务器IP地址和图片的名称都是相对固定不变的(如果服务器IP地址发生变化,就当是增/删节点),那么在经过一致性hash算法之后得到的值也是固定不变的,因此满足一次缓存,高效访问的要求。

下面我们再来看一下,增加节点的场景下,一致性hash算法是否还能满足我们的需求:

1、现有缓存服务器由于访问压力大,已经快支撑不住了,因此决定再增加一台缓存服务器D

2、随机访问的图片还是原来的那4张图片,设为:P1、P2、P3、P4

3、增加缓存服务器以后,环上的分布如下图所示

可以看到,P1的缓存失效了(原来是缓存在B服务器中的),需要从后端重新获取,但其他(P2、P3、P4)的缓存是有效的,也没有改变,还是映射到原来的缓存服务器中。

总结:对于一致性hash算法,往现有环中增加服务节点,只会失效有限的缓存项(这部分数据需要重新从后端获取),其他缓存项仍然可用,这就比原始hash算法的效率更高,对前端的影响更小,同时也达到了增加节点,分摊集群压力的效果。

下面我们再来看下删除服务节点的应用场景:

1、C服务器出现硬件故障,需要更换服务器,但新服务器三天后才能到达,现在需要将C服务器从集群中下线,以免造成缓存无服务可用,需从后端拿数据

2、删除C服务器后,环上的分布情况如下:

可能看到,将C服务器从环上移除后,访问P2对象的缓存项失效后,需要从后端拿到数据,然后就可以重新缓存到A服务器中,后面再次对P2进行访问,就可以直接从A服务器中拿取数据,对其他缓存项没有景响。

从上面的分析场景中可以看到,一致性hash算法是似完美的解决了原始hash算法带来的弊端,同时数据分布也均匀,增加/删除服务节点,对缓存项的影响较小,也就意味着对前端的访问不会造成较大的影响,也能减小对后端服务器的IO压力。完美!,NO!在上面的场景中还存在一个假设,那就是服务器节点是均匀分布在环上的。理想很丰满,现实却很骨感。在实际的应用场景中,会出现下面这种情况:

what!这是什么情况,累的累死,闲的闲死。这还是一个集群吗?这不就是个人英雄主义么!

是的,你没看错,这就是一致性hash算法的缺点,人无完人,算法也一样,解决一个问题的同时,也会暴露出另一个问题-数据倾斜。

一致性hash算法的环上有2^32个点,也就是说环上的节越多,分布的就越均匀,但现实情况是,服务器资源有限(3台,大方一点的来个9台),没有那么多服务器拿来给你组个图片缓存集群,就算有这么多的服务器,所有服务器都给你缓存图片了,那公司其他业务还要不要开展了?怎么办呢?没这么多资源,就不可能虚假些节点出来吧


一致性hash算法的改良-带虚拟节点

上文中说道,一致性hash算法是好,但还存在一个问题,那就是数据倾斜,也就是缓存项分布不均匀(累的累死,闲的闲死)。怎么解决这个问题呢?

我们的思路是,一致性hash算法是一个由2^32个节点组成的环,每个服务器节点经过取模后,会唯一映射到一个点上,环上的点越多那么缓存项的分布就会越均匀,但现实中没这么多资源呢,那按照环上的点越多,缓存项的分布越均匀这个思路发展下去,那就是用当前有的服务器节点,通过复制,再映射到多个不同的节点,比如说我现在有3台服务器,通过这种思路,我可以每台再复制出2台节点,总共在环上就会变成9个节点,9个节点的随机分布总比3个节点的随机分布要均匀吧(事无绝对,在极端的情况还是会出现不均匀的情况,但总体来说要好很多,我们也没必要为了1%的概率出现,去用100%的努力去避免)。优化后如下图所示:

通过增加虚拟节点的方式,就可以在一般情况下避免数据倾斜的问题,同时也达到数据均匀分布的要求,做到缓存项分布大致均匀。现在:完美!,真的比较完美了!

一致性hash算法的实现关键点:

1、hash算法的实现,要做到在0~2^32-1之间随机均匀分布,均匀分布得越好,数据缓存项就越均匀

2、虚拟节点的个数,理论上总共保证2^32个节点,数据分布得越均匀,但这是有代价的,所以说虚拟节点不是越多越好,要在成本和效率之间找到平衡

3、加入虚拟节点后的一致性hash计算方法调整为:hash(节点ip+虚拟节点号)%2^32

4、要保证整个一致性hash算法的效率(时间复杂度和空间复杂度)


课后作业:

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

package com.consistent.hash;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
public abstract class DistributeHash {
private TreeMap<Long,String> virtualNodes = new TreeMap<>(); //hash=>物理节点
private int vitual_copies = 64; //物理节点至虚拟节点的复制倍数
private Map<String,Integer> objectNodeMap = new TreeMap<>();
public abstract Long hash(String key);
//添加物理节点
public void addPhysicalNode(String key){
for(int ind=0;ind<vitual_copies;ind++){
long hash = hash(key +"#"+Integer.toString(ind));
virtualNodes.put(hash,key);
}
}
public int getVitual_copies() {
return vitual_copies;
}
public void setVitual_copies(int vitual_copies) {
this.vitual_copies = vitual_copies;
}
public Map<String,Integer> getobjectNodeMap(){
return objectNodeMap;
}
//删除物理节点
public void removePhysicalNode(String key){
for(int ind=0 ; ind < vitual_copies ; ind++){
long hash = hash(key+"#"+Integer.toString(ind));
virtualNodes.remove(hash);
}
}
//查找对象映射的节点
private String getObjectNode(String object){
long hash = hash(object);
SortedMap<Long,String> tailmap = virtualNodes.tailMap(hash);
Long key = tailmap.isEmpty() ? virtualNodes.firstKey():tailmap.firstKey();
return virtualNodes.get(key);
}
//对象与节点映射
public void objectNodeMap(String label,int objectMin,int objectMax){
for(int object = objectMin;object <= objectMax;++object){
String nodeIp = getObjectNode(Integer.toString(object));
Integer count = objectNodeMap.get(nodeIp);
objectNodeMap.put(nodeIp,(count == null ? 0:count + 1));
}
//打印
double totalcount = objectMax - objectMin + 1;
System.out.println("======== " + label + " ========");
for(Map.Entry<String, Integer> entry : objectNodeMap.entrySet()){
long percent = (int)(100 * entry.getValue() / totalcount);
System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
}
}
}
package com.consistent.hash;
public class ConsistentHash extends DistributeHash {
// 32位的 Fowler-Noll-Vo 哈希算法
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
@Override
public Long hash(String key) {
final int p = 16777619;
Long hash = 2166136261L;
for(int ind = 0,num = key.length();ind<num;ind++){
hash = (hash^key.charAt(ind))*p;
}
hash += hash <<13;
hash ^= hash >>7;
hash += hash <<3;
hash ^= hash >>17;
hash += hash <<5;
if(hash < 0){
hash = Math.abs(hash);
}
return hash;
}
}
package com.consistent.hash;
import org.junit.Test;
import java.util.Map;
import java.util.TreeMap;
public class ConsistentHashTest {
//标准方差
public double getstd(Map<String,Integer> objectnodes){
double sum = 0;
int cnt = 0;
for(Map.Entry<String,Integer> entry : objectnodes.entrySet()){
sum += entry.getValue();
cnt++;
}
double average = sum/cnt;
int total = 0;
for(Map.Entry<String,Integer> entry : objectnodes.entrySet()){
total += (entry.getValue() - average) *(entry.getValue() - average);
}
double standardDeviation = Math.sqrt(total/cnt);
return standardDeviation;
}
@Test
public void test(){
Map<String,Integer> objectNodes = new TreeMap<>();
//添加物理服务器节点
DistributeHash ch = new ConsistentHash();
ch.setVitual_copies(102400);
ch.addPhysicalNode("192.168.100.101");
ch.addPhysicalNode("192.168.100.102");
ch.addPhysicalNode("192.168.100.103");
ch.addPhysicalNode("192.168.100.104");
ch.addPhysicalNode("192.168.100.105");
ch.addPhysicalNode("192.168.100.106");
ch.addPhysicalNode("192.168.100.107");
ch.addPhysicalNode("192.168.100.108");
ch.addPhysicalNode("192.168.100.109");
ch.addPhysicalNode("192.168.100.110");
//对象与节点映射
ch.objectNodeMap("10台服务器,单台"+ch.getVitual_copies()+"个虚拟节点",1,1000000);
//计算标准方差
objectNodes = ch.getobjectNodeMap();
System.out.println("标准方差为:"+getstd(objectNodes));
}
}

场景1:10台服务器节点,单台102400-1个虚拟节点,数据分布比较均匀

场景2:10台服务器节点,没有虚拟节点,数据分布不是很均匀(101和105两台服务节点占比20%以上,104服务器空闲,103占比10%以上,剩余节点相对均匀)

场景3:10台服务器节点,单台64-1个虚拟节点,虽然标准方差和场景2一致,但每个服务器节点数据分布比场景2更均匀

场景4:10台服务器节点,单台1024-1个虚拟节点,从运行结果可以看出,当虚拟节点增加到一定量后,整个数据呈均匀分布状态,标准方差为7595,达到了比较理想的分布式缓存要求。

发布于: 10 小时前 阅读数: 10
用户头像

傻傻的帅

关注

走自已的路,让别人无路可走 2019.09.18 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第5周-一致性hash算法总结及作业