一致性哈希算法代码实现

一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,

如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,

如果有一个机器加入或退出这个集群,则所有的数据映射都无效了。


一致性哈希算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。


一致性hash算法实现

1、不带虚拟节点的

package hash;

 

import java.util.SortedMap;

import java.util.TreeMap;

 

/**

 * 不带虚拟节点的一致性Hash算法

 */

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();

	}

 

	//得到应当路由到的结点

	private static String getServer(String key) {

		//得到该key的hash值

		int hash = getHash(key);

		//得到大于该Hash值的所有Map

		SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);

		if(subMap.isEmpty()){

			//如果没有比该key的hash值大的,则从第一个node开始

			Integer i = sortedMap.firstKey();

			//返回对应的服务器

			return sortedMap.get(i);

		}else{

			//第一个Key就是顺时针过去离node最近的那个结点

			Integer i = subMap.firstKey();

			//返回对应的服务器

			return subMap.get(i);

		}

	}

	

	//使用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;

		}

 

	public static void main(String[] args) {

		String[] keys = {"太阳", "月亮", "星星"};

		for(int i=0; i<keys.length; i++)

			System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i])

					+ ", 被路由到结点[" + getServer(keys[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


[太阳]的hash值为1977106057, 被路由到结点[192.168.0.1:111]

[月亮]的hash值为1132637661, 被路由到结点[192.168.0.3:111]

[星星]的hash值为880019273, 被路由到结点[192.168.0.3:111]

2、带虚拟节点的

package hash;

 

import java.util.LinkedList;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;

 

import org.apache.commons.lang.StringUtils;

 

/**

  * 带虚拟节点的一致性Hash算法

  */

 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"};

     

     //真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用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 key){

        //得到该key的hash值

         int hash = getHash(key);

         // 得到大于该Hash值的所有Map

         SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);

         String virtualNode;

         if(subMap.isEmpty()){

            //如果没有比该key的hash值大的,则从第一个node开始

            Integer i = virtualNodes.firstKey();

            //返回对应的服务器

            virtualNode = virtualNodes.get(i);

         }else{

            //第一个Key就是顺时针过去离node最近的那个结点

            Integer i = subMap.firstKey();

            //返回对应的服务器

            virtualNode = subMap.get(i);

         }

         //virtualNode虚拟节点名称要截取一下

         if(StringUtils.isNotBlank(virtualNode)){

             return virtualNode.substring(0, virtualNode.indexOf("&&"));

         }

         return null;

     }

     

     public static void main(String[] args){

         String[] keys = {"太阳", "月亮", "星星"};

         for(int i=0; i<keys.length; i++)

             System.out.println("[" + keys[i] + "]的hash值为" +

                     getHash(keys[i]) + ", 被路由到结点[" + getServer(keys[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


[太阳]的hash值为1977106057, 被路由到结点[192.168.0.2:111]

[月亮]的hash值为1132637661, 被路由到结点[192.168.0.4:111]

[星星]的hash值为880019273, 被路由到结点[192.168.0.3:111]


评论区
京ICP备19006603号-1 Rick ©2018