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

关注
发布于: 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]
看到经过FNV132HASH算法重新计算过后的Hash值，就比原来String的hashCode()方法好多了。从运行结果来看，也没有问题，三个点路由到的都是顺时针离他们Hash值最近的那台服务器上。
使用虚拟节点来改善一致性Hash算法上面的一致性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 日阅读数: 54
edd

关注
还未添加个人签名 2018.01.18 加入
还未添加个人简介
发布
暂无评论
创作场景

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

前言

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

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

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

edd

评论
