架构师训练营」第 4 周作业
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
前言
写这个作业前,找了很多的资料对着看 ,一致性 Hash 算法学习起来还是有点难度 。
一致性 Hash 算法实现版本 1:不带虚拟节点
使用一致性 Hash 算法,尽管增强了系统的伸缩性,但是也有可能导致负载分布不均匀,解决办法就是使用,虚拟节点代替真实节,第一个代码版本,先来个简单的,不带虚拟节点。
下面来看一下不带虚拟节点的一致性 Hash 算法的 Java 代码实现:
可以运行一下看一下结果:
看到经过 FNV1_32_HASH 算法重新计算过后的 Hash 值,就比原来 String 的 hashCode()方法好多了。从运行结果来看,也没有问题,三个点路由到的都是顺时针离他们 Hash 值最近的那台服务器上。
使用虚拟节点来改善一致性 Hash 算法
上面的一致性 Hash 算法实现,可以在很大程度上解决很多分布式环境下不好的路由算法导致系统伸缩性差的问题,但是会带来另外一个问题:负载不均。
比如说有 Hash 环上有 A、B、C 三个服务器节点,分别有 100 个请求会被路由到相应服务器上。现在在 A 与 B 之间增加了一个节点 D,这导致了原来会路由到 B 上的部分节点被路由到了 D 上,这样 A、C 上被路由到的请求明显多于 B、D 上的,原来三个服务器节点上均衡的负载被打破了。 某种程度上来说,这失去了负载均衡的意义,因为负载均衡的目的本身就是为了使得目标服务器均分所有的请求 。
解决这个问题的办法是引入虚拟节点,其工作原理是: 将一个物理节点拆分为多个虚拟节点,并且同一个物理节点的虚拟节点尽量均匀分布在 Hash 环上 。采取这样的方式,就可以有效地解决增加或减少节点时候的负载不均衡的问题。
至于一个物理节点应该拆分为多少虚拟节点,下面可以先看一张图:
横轴表示需要为每台福利服务器扩展的虚拟节点倍数,纵轴表示的是实际物理服务器数。可以看出,物理服务器很少,需要更大的虚拟节点;反之物理服务器比较多,虚拟节点就可以少一些。比如有 10 台物理服务器,那么差不多需要为每台服务器增加 100~200 个虚拟节点才可以达到真正的负载均衡。
一致性 Hash 算法实现版本 2:带虚拟节点
在理解了使用虚拟节点来改善一致性 Hash 算法的理论基础之后,就可以尝试开发代码了。编程方面需要考虑的问题是:
一个真实结点如何对应成为多个虚拟节点?
虚拟节点找到后如何还原为真实结点?
这两个问题其实有很多解决办法,我这里使用了一种简单的办法,给每个真实结点后面根据虚拟节点加上后缀再取 Hash 值,比如"192.168.0.0:111"就把它变成"192.168.0.0:111&&VN0"到"192.168.0.0:111&&VN4",VN 就是 Virtual Node 的缩写,还原的时候只需要从头截取字符串到"&&"的位置就可以了。
下面来看一下带虚拟节点的一致性 Hash 算法的 Java 代码实现:
关注一下运行结果:
从代码运行结果看,每个点路由到的服务器都是 Hash 值顺时针离它最近的那个服务器节点,没有任何问题。通过采取虚拟节点的方法,一个真实结点不再固定在 Hash 换上的某个点,而是大量地分布在整个 Hash 环上,这样即使上线、下线服务器,也不会造成整体的负载不均衡。
最后 总结一下,很多知识我也是边写边学,难免有很多写得不好、理解得不透彻的地方,而且代码整体也比较糙,未有考虑到可能的各种情况。抛砖引玉。
一方面,写得不对的地方,还望网友朋友们指正;
另一方面,后续我也将通过自己的工作、学习不断完善上面的代码。
评论