一致性hash算法介绍

分布式系统中，数据的分布式存储采用哈希算法进行数据映射；传统的取模（数据mod节点个数）哈希算法无法适应分布式系统中节点的添加和删除，节点的变动会导致几乎全部的数据位置发生变化，为了保证原有数据被正常检索到，数据迁移的成本非常大。

一致性hash是由一个固定长度的Hash环构成，大小为2的32次方。根据节点的Hash值对2的32次方取模，将服务器节点放置在这个Hash环上，然后根据数据值对2的32次方取模，计算得到其Hash值，接着在Hash环上顺时针查找距离这个数值的Hash值最近的服务器节点，完成数据到服务器的映射查找。如图：

当一个服务器节点删除时，只有该节点和逆时针遇到的第一个节点之间的数据需要迁移，其他数据不需要变。如图：

当一个节点新增时，只有该节点和逆时针遇到的第一个节点之间的数据需要迁移，其他数据不需要变，如图：

为了保证数据分布的均衡，引入了虚拟节点。虚拟节点（ virtual node ）是实际节点在 hash 空间的复制节点，一个实际的节点对应了若干个虚拟节点， 虚拟节点在 hash 空间中以hash值排列，如图：

当有虚拟节点时，数据的检索过程如下：

那虚拟节点的个数该如何设置呢？如下图：

横轴表示需要为每台服务器扩展的虚拟节点倍数，纵轴表示的是实际物理服务器数。可以看出，物理服务器很少，需要更大的虚拟节点；反之物理服务器比较多，虚拟节点就可以少一些。比如有10台物理服务器，那么差不多需要为每台服务器增加100个虚拟节点才可以达到真正的负载均衡。

实现一致性hash的步骤如下：

1.构造出一个长度为2的32此方的整数环，根据节点名称的Hash值将服务器节点放置在这个Hash环上，由于大部分情况下，服务器节点的数量变动不会很频繁，比较频繁的操作是对数据做节点的映射，这样就需要用数据的hash值在环上查找到相应的节点，多查找少更新，选取红黑树做环，java中用TreeMap实现

2.节点的hash值计算方式，基于String默认的hashcode方法计算出的hash值分散度不够，节点位置过于集中

192.168.0.0:111的哈希值：1845870087

192.168.0.1:111的哈希值：1874499238

192.168.0.2:111的哈希值：1903128389

192.168.0.3:111的哈希值：1931757540

192.168.0.4:111的哈希值：1960386691

目前常用的hash算法：CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法，用别的Hash算法也可以。

附上实现代码：

• 没有虚拟节点的实现

import java.util.HashMap;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import org.apache.commons.lang3.StringUtils;
public class ConsistentHashingWithoutVirtualNode {
  private static String[] servers = {"192.168.0.0", "192.168.0.1", "192.168.0.2", "192.168.0.3",
      "192.168.0.4"};
  private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
  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]);
    }
  }
  //FNV1_32_HASH
  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 data) {
    int hash = getHash(data);
    Integer i;
    SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
    if (subMap.size() == 0) {
      i = sortedMap.firstKey();
    } else {
      i = subMap.firstKey();
    }
    return sortedMap.get(i);
  }
  public static void main(String[] args) {
    Integer maxNum = 50000;
    Map<String, String> map = new HashMap<>();
    for (Integer i = 0; i < maxNum; i++) {
      String server = getServer(i.toString());
      System.out.println(
          "[" + i + "]的hash值为" + getHash(i.toString()) + ", 被路由到结点[" + server
              + "]");
      map.put(i.toString(), server);
    }
  }
}

• 添加了虚拟节点的实现

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import org.apache.commons.lang3.StringUtils;
public class ConsistentHashingWithVirtualNode {
  private static String[] servers = {"192.168.0.0", "192.168.0.1", "192.168.0.2","192.168.0.3", "192.168.0.4"};
  //真实节点,真实节点将不保存在Hash环中
  private static List<String> realNodes = new LinkedList<String>();
  //虚拟节点,Hash环
  private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
  //每个真实节点对应的虚拟节点数
  private static final int VIRTUAL_NODES = 200;
  static {
    //添加真实节点
    for (int i = 0; i < servers.length; i++)
      realNodes.add(servers[i]);
    //添加虚拟节点
    for (String str : realNodes) {
      for (int i = 0; i < VIRTUAL_NODES; i++) {
        //给虚拟节点命名
        String virtualNodeName = str + "&&VN" + String.valueOf(i);
        //重写Hash算法后的虚拟节点的Hash值
        int hash = getHash(virtualNodeName);
//        System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
        virtualNodes.put(hash, virtualNodeName);
      }
    }
  }
  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) {
    int hash = getHash(node);
    String virtualNode;
    Integer i;
    SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
    if (subMap.size() == 0) {
      i = virtualNodes.firstKey();
      virtualNode = virtualNodes.get(i);
    } else {
      i = subMap.firstKey();
      virtualNode = virtualNodes.get(i);
    }
    //返回真实节点的IP,端口,而不是虚拟节点名称
    return virtualNode.substring(0, virtualNode.indexOf("&&"));
  }
  public static void main(String[] args) {
    Integer maxNum = 50000;
    Map<String, String> map = new HashMap<>();
    for (Integer i = 0; i < maxNum; i++) {
      String server = getServer(i.toString());
      System.out.println(
          "[" + i + "]的hash值为" + getHash(i.toString()) + ", 被路由到结点[" + server
              + "]");
      map.put(i.toString(), server);
    }
     
  }
}