写点什么

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

用户头像
傻傻的帅
关注
发布于: 2020 年 07 月 06 日

在了解一致性 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,达到了比较理想的分布式缓存要求。


发布于: 2020 年 07 月 06 日阅读数: 103
用户头像

傻傻的帅

关注

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

还未添加个人简介

评论

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