架构师训练营」第 4 周作业

edd

关注

发布于: 2020 年 07 月 08 日

用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。

前言

写这个作业前，找了很多的资料对着看，一致性 Hash 算法学习起来还是有点难度。

一致性 Hash 算法实现版本 1：不带虚拟节点

使用一致性 Hash 算法，尽管增强了系统的伸缩性，但是也有可能导致负载分布不均匀，解决办法就是使用，虚拟节点代替真实节，第一个代码版本，先来个简单的，不带虚拟节点。

下面来看一下不带虚拟节点的一致性 Hash 算法的 Java 代码实现：

package org.example.hash;
import java.util.SortedMap;import java.util.TreeMap;
/** * 不带虚拟节点的一致性Hash算法 *  * @author qianjiang * */public class ConsistentHashingWithoutVirtualNode {	/**	 * 待添加入Hash环的服务器列表	 */	private static String[] servers = { "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111",			"192.168.0.4:111" };
	/**	 * key表示服务器的hash值，value表示服务器的名称	 */	private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
	/**	 * 程序初始化，将所有的服务器放入sortedMap中	 */	static {		for (int i = 0; i < servers.length; i++) {			int hash = getHash(servers[i]);			System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);			sortedMap.put(hash, servers[i]);		}		System.out.println();	}
	/**	 * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别	 */	private static int getHash(String str) {		final int p = 16777619;		int hash = (int) 2166136261L;		for (int i = 0; i < str.length(); i++)			hash = (hash ^ str.charAt(i)) * 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;	}
	/**	 * 得到应当路由到的结点	 */	private static String getServer(String node) {		// 得到带路由的结点的Hash值		int hash = getHash(node);		// 得到大于该Hash值的所有Map		SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);		// 第一个Key就是顺时针过去离node最近的那个结点		Integer i = subMap.firstKey();		// 返回对应的服务器名称		return subMap.get(i);	}
	public static void main(String[] args) {		String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333" };		for (int i = 0; i < nodes.length; i++)			System.out					.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");	}}

复制代码

可以运行一下看一下结果：

[192.168.0.0:111]加入集合中, 其Hash值为575774686[192.168.0.1:111]加入集合中, 其Hash值为8518713[192.168.0.2:111]加入集合中, 其Hash值为1361847097[192.168.0.3:111]加入集合中, 其Hash值为1171828661[192.168.0.4:111]加入集合中, 其Hash值为1764547046    [127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111][221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.4:111][10.211.0.1:3333]的hash值为1393836017,被路由到结点[192.168.0.4:111]

复制代码

看到经过 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 代码实现：


 package org.example.hash;
import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;
/**   * 带虚拟节点的一致性Hash算法   * @author qianjiang   */  public class ConsistentHashingWithVirtualNode  {      /**       * 待添加入Hash环的服务器列表       */     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",            "192.168.0.3:111", "192.168.0.4:111"};          /**      * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好      */    private static List<String> realNodes = new LinkedList<String>();          /**      * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称     */     private static SortedMap<Integer, String> virtualNodes =             new TreeMap<Integer, String>();          /**      * 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点     */     private static final int VIRTUAL_NODES = 5;          static     {        // 先把原始的服务器添加到真实结点列表中         for (int i = 0; i < servers.length; i++)             realNodes.add(servers[i]);                 // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高         for (String str : realNodes)         {             for (int i = 0; i < VIRTUAL_NODES; i++)             {                 String virtualNodeName = str + "&&VN" + String.valueOf(i);                 int hash = getHash(virtualNodeName);                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);                 virtualNodes.put(hash, virtualNodeName);             }         }         System.out.println();     }          /**      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别       */     private static int getHash(String str)     {         final int p = 16777619;         int hash = (int)2166136261L;         for (int i = 0; i < str.length(); i++)            hash = (hash ^ str.charAt(i)) * 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;     }          /**      * 得到应当路由到的结点      */     private static String getServer(String node)    {         // 得到带路由的结点的Hash值        int hash = getHash(node);         // 得到大于该Hash值的所有Map         SortedMap<Integer, String> subMap =                  virtualNodes.tailMap(hash);        // 第一个Key就是顺时针过去离node最近的那个结点         Integer i = subMap.firstKey();         // 返回对应的虚拟节点名称，这里字符串稍微截取一下        String virtualNode = subMap.get(i);         return virtualNode.substring(0, virtualNode.indexOf("&&"));    }          public static void main(String[] args)     {         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};        for (int i = 0; i < nodes.length; i++)            System.out.println("[" + nodes[i] + "]的hash值为" +                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");    }}

复制代码

关注一下运行结果：

虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1686427075虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为354859081虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1306497370虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为817889914虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为396663629虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1032739288虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为707592309虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为302114528虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为36526861虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为848442551虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1452694222虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为2023612840虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为697907480虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为790847074虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为2010506136虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为891084251虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为1725031739虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为1127720370虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为676720500虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为2050578780虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为586921010虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为184078390虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为1331645117虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为918790803虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为1232193678
[127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111][221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.0:111][10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.2:111]

复制代码

从代码运行结果看，每个点路由到的服务器都是 Hash 值顺时针离它最近的那个服务器节点，没有任何问题。通过采取虚拟节点的方法，一个真实结点不再固定在 Hash 换上的某个点，而是大量地分布在整个 Hash 环上，这样即使上线、下线服务器，也不会造成整体的负载不均衡。

最后总结一下，很多知识我也是边写边学，难免有很多写得不好、理解得不透彻的地方，而且代码整体也比较糙，未有考虑到可能的各种情况。抛砖引玉。
一方面，写得不对的地方，还望网友朋友们指正；
另一方面，后续我也将通过自己的工作、学习不断完善上面的代码。

发布于: 2020 年 07 月 08 日阅读数: 66

edd

关注

还未添加个人签名 2018.01.18 加入

还未添加个人简介

发布

暂无评论

创作场景

架构师训练营」第 4 周作业

前言

一致性 Hash 算法实现版本 1：不带虚拟节点

使用虚拟节点来改善一致性 Hash 算法

一致性 Hash 算法实现版本 2：带虚拟节点

edd

评论