一致性hash及应用

发表于2019-04-11更新于2022-05-04阅读次数

简介

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

为什么要使用一致性hash

对于分布式缓存，不同机器上存储不同对象的数据。为了实现这些缓存机器的负载均衡，可以使用式子1来定位对象缓存的存储机器：

1
m = hash(o) mod n ——式子1

其中，o为对象的名称，n为机器的数量，m为机器的编号，hash为一hash函数。

上图的负载均衡器（load balancer）正是使用式子1来将客户端对不同对象的请求分派到不同的机器上执行，例如，对于对象o，经过式子1的计算，得到m的值为3，那么所有对对象o的读取和存储的请求都被发往机器3执行。

式子1在大部分时候都可以工作得很好，然而，当机器需要扩容或者机器出现宕机的情况下，事情就比较棘手了。
当机器扩容，需要增加一台缓存机器时，负载均衡器使用的式子变成：

1
m = hash(o) mod (n + 1) ——式子2

当机器宕机，机器数量减少一台时，负载均衡器使用的式子变成：

1
m = hash(o) mod (n - 1) ——式子3

我们以机器扩容的情况为例，说明简单的取模方法会导致什么问题。假设机器由3台变成4台，对象o1由式子1计算得到的m值为2，由式子2计算得到的m值却可能为0，1，2，3（一个 3t + 2的整数对4取模，其值可能为0，1，2，3，读者可以自行验证），大约有75%（3/4)的可能性出现缓存访问不命中的现象。随着机器集群规模的扩大，这个比例线性上升。当99台机器再加入1台机器时，不命中的概率是99%（99/100）。这样的结果显然是不能接受的，因为这会导致数据库访问的压力陡增，严重情况，还可能导致数据库宕机。

一致性hash算法正是为了解决此类问题的方法，它可以保证当机器增加或者减少时，对缓存访问命中的概率影响减至很小。

一致性Hash性质

考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其是在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效（即由于系统节点数目变少，客户端在请求某一对象时需要重新计算其hash值（通常与系统中的节点数目有关），由于hash值已经改变，所以很可能找不到保存该对象的服务器节点），因此一致性hash就显得至关重要，良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：

  • 平衡性(Balance)
    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

  • 单调性(Monotonicity)
    单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

  • 分散性(Spread)
    在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

  • 负载(Load)
    负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

  • 平滑性(Smoothness)
    平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

原理

简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

  • 整个空间按顺时针方向组织。0和2^32-1在零点中方向重合。
    下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将四台服务器使用ip地址哈希后在环空间的位置如下：

    接下来使用如下算法定位数据访问到相应服务器：
  • 将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

一致性Hash算法的容错性和可扩展性

容错性

现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

可扩展性

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：

此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

Hash环的数据倾斜问题

一致性哈希算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如下：

此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。
为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制。

  • 对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。

具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

一致性hash算法的Java实现

  1. 不带虚拟节点的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    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]) + "]");
    	}
    }
  2. 带虚拟节点的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    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]) + "]");
         }
     }

总结

一致性hash算法解决了分布式环境下机器增加或者减少时，简单的取模运算无法获取较高命中率的问题。通过虚拟节点的使用，一致性hash算法可以均匀分担机器的负载，解决数据倾斜问题。

参考资料