一致性哈希算法

分布式均衡寻址算法

在分布式集群中,对机器的添加删除,或者机器故障后自动脱落集群的操作是分布式集群管理的基本功能。

在集群环境中,判断分布式寻址算法好坏的原则:

  • 平衡性(Balance)
  • 单调性(Monotonicity)
  • 分散性(Spread)
  • 负载(Load)

Hash(Object)%N

集群N台机器,根据N取模,路由到对应的机器,但是缺点在于,对于机器的添加删除,已经缓存的数据都失效、严重违反单调性, 大量的缓存重建

假设0-3个节点、20个数据: 哈希数据

进行取模后分布: 哈希取模后分布

扩容后: 扩容后 当前只有4个数据能命中。命中率 4/20 = 20% ,命中率底下,并且有大量缓存需要重建

一致性Hash ( DHT )

公共哈希函数和哈希环 Hash算法设计: 采取取模方式,按常用的 Hash 算法将对应的 Key 哈希到一个具有 2^32 次方的桶空间中,即 0 ~ (2^32)-1 的数字空间。想想一下,将数字首位相连,组成一个闭合的环形。 环形Hash空间

对象(Object)映射到哈希环 把对象映射到 0-2^32-1 空间里,假设有4个对象 object1-4 ,映射进hash环状 对象映射环形Hash空间

缓存(Cache)映射到哈希环 下面将 Cache 映射进 Hash 空间,假设现在有三个cache:

基本思想就是 Object 和 Cache 都映射到同一 Hash 数值空间中,并且使用相同的 Hash算法,可以使用 Cache 的 IP地址或者其他因子)

Cache映射环形Hash空间

对象(Object映射到缓存(Cache)节点 每个 Cache 的 Key 顺时针,找到第一个 Cache 节点就是存储位置: 找到Cache存储位置

移除一个缓存节点 移除一个 CacheB 节点, 这时候 key4 无法找寻到 Cache,key4将继续使用一致性Hash算法算出最新的 CacheC, 以后存储与读取都在 CacheC 上。 移除CacheB节点

移除节点后的影响范围在该节点逆时针计算到遇到的第一个cache节点之间的数据节点。

增加一个缓存节点 增加一个 Cache节点 新增Cache节点

影响范围为:添加节点逆时针遇到的第一个cache节点之间的数据节点

虚拟Cache节点 物理上不可能部署节点有限,所以需要虚拟出足够多的虚拟节点,最终达到数据在哈希换上均匀分布

假如只有两个节点,每个节点都复制成3倍,结果看上去部署了6个节点。可以想象当复制倍数是 2^32 时候,就达到绝对的均匀,通常可取的复制倍数为32 或者更高

虚拟节点哈希值计算方法调整为 对 “节点IP(或机器名)+虚拟节点的序号(1~N)” 作哈希

Redis Cluster

Redis Cluster 是 Redis 官方出品的分布式解决方案

Redis Cluster 由多个 Redis 实例组成的整体,数据按照 槽(slot) 存储分布在多个实例上,通过 Gossip 协议来进行节点通信。

redis 为什么使用 16384 slots? redis 作者给出答案

一致性hash算法的JAVA实现与检验

   public class ConsistentHashing {
       // 物理节点
       private Set<String> physicalNodes = new TreeSet<String>() {
           {
               add("192.168.1.101");
               add("192.168.1.102");
               add("192.168.1.103");
               add("192.168.1.104");
               add("192.168.1.105");
               add("192.168.1.106");
           }
       };
   
       //虚拟节点
       private final int VIRTUAL_COPIES = 1; // 物理节点至虚拟节点的复制倍数
       private TreeMap<Long, String> virtualNodes = new TreeMap<>(); // 哈希值 => 物理节点
   
       // 32位的 Fowler-Noll-Vo 哈希算法
       // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
       private static Long FNVHash(String key) {
           final int p = 16777619;
           Long hash = 2166136261L;
           for (int idx = 0, num = key.length(); idx < num; ++idx) {
               hash = (hash ^ key.charAt(idx)) * 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 ConsistentHashing() {
           for (String nodeIp : physicalNodes) {
               addPhysicalNode(nodeIp);
           }
       }
   
       // 添加物理节点
       public void addPhysicalNode(String nodeIp) {
           for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
               long hash = FNVHash(nodeIp + "#" + idx);
               virtualNodes.put(hash, nodeIp);
           }
       }
   
       // 删除物理节点
       public void removePhysicalNode(String nodeIp) {
           for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
               long hash = FNVHash(nodeIp + "#" + idx);
               virtualNodes.remove(hash);
           }
       }
   
       // 查找对象映射的节点
       public String getObjectNode(String object) {
           long hash = FNVHash(object);
           SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
           Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
           return virtualNodes.get(key);
       }
   
       // 统计对象与节点的映射关系
       public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
           // 统计
           Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
           for (int object = objectMin; object <= objectMax; ++object) {
               String nodeIp = getObjectNode(Integer.toString(object));
               Integer count = objectNodeMap.get(nodeIp);
               objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1));
           }
   
           // 打印
           double totalCount = objectMax - objectMin + 1;
           System.out.println("======== " + label + " ========");
           for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
               long percent = (int) (100 * entry.getValue() / totalCount);
               System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");
           }
       }
   
       public static void main(String[] args) {
           ConsistentHashing ch = new ConsistentHashing();
   
           // 初始情况
           ch.dumpObjectNodeMap("初始情况", 0, 65536);
   
           // 删除物理节点
           ch.removePhysicalNode("192.168.1.105");
           ch.dumpObjectNodeMap("删除物理节点", 0, 65536);
   
           // 添加物理节点
           ch.addPhysicalNode("192.168.1.107");
           ch.dumpObjectNodeMap("添加物理节点", 0, 65536);
       }
   }

复制倍数为 1 时的均衡性(VIRTUAL_COPIES = 1)

  ======== 初始情况 ========
  IP=192.168.1.101: RATE=28%
  IP=192.168.1.102: RATE=3%
  IP=192.168.1.103: RATE=28%
  IP=192.168.1.104: RATE=19%
  IP=192.168.1.105: RATE=16%
  IP=192.168.1.106: RATE=2%
  ======== 删除物理节点 ========
  IP=192.168.1.101: RATE=45%
  IP=192.168.1.102: RATE=3%
  IP=192.168.1.103: RATE=28%
  IP=192.168.1.104: RATE=19%
  IP=192.168.1.106: RATE=2%
  ======== 添加物理节点 ========
  IP=192.168.1.101: RATE=45%
  IP=192.168.1.102: RATE=3%
  IP=192.168.1.103: RATE=25%
  IP=192.168.1.104: RATE=19%
  IP=192.168.1.106: RATE=2%
  IP=192.168.1.107: RATE=3%

复制倍数为 32 时的均衡性(VIRTUAL_COPIES = 32)

 ======== 初始情况 ========
 IP=192.168.1.101: RATE=17%
 IP=192.168.1.102: RATE=12%
 IP=192.168.1.103: RATE=23%
 IP=192.168.1.104: RATE=12%
 IP=192.168.1.105: RATE=12%
 IP=192.168.1.106: RATE=21%
 ======== 删除物理节点 ========
 IP=192.168.1.101: RATE=17%
 IP=192.168.1.102: RATE=12%
 IP=192.168.1.103: RATE=25%
 IP=192.168.1.104: RATE=23%
 IP=192.168.1.106: RATE=21%
 ======== 添加物理节点 ========
 IP=192.168.1.101: RATE=16%
 IP=192.168.1.102: RATE=12%
 IP=192.168.1.103: RATE=14%
 IP=192.168.1.104: RATE=23%
 IP=192.168.1.106: RATE=15%
 IP=192.168.1.107: RATE=17%

复制倍数为 1M 时的均衡性(VIRTUAL_COPIES = 1048576)

 ======== 初始情况 ========
 IP=192.168.1.101: RATE=16%
 IP=192.168.1.102: RATE=16%
 IP=192.168.1.103: RATE=16%
 IP=192.168.1.104: RATE=16%
 IP=192.168.1.105: RATE=16%
 IP=192.168.1.106: RATE=16%
 ======== 删除物理节点 ========
 IP=192.168.1.101: RATE=19%
 IP=192.168.1.102: RATE=19%
 IP=192.168.1.103: RATE=20%
 IP=192.168.1.104: RATE=19%
 IP=192.168.1.106: RATE=19%
 ======== 添加物理节点 ========
 IP=192.168.1.101: RATE=16%
 IP=192.168.1.102: RATE=16%
 IP=192.168.1.103: RATE=16%
 IP=192.168.1.104: RATE=16%
 IP=192.168.1.106: RATE=16%
 IP=192.168.1.107: RATE=16%
comments powered by Disqus