自己实现一个一致性 Hash 算法

前言

在前文分布式理论(八)—— Consistent Hash（一致性哈希算法）中，我们讨论了一致性 hash 算法的原理，并说了，我们会自己写一个简单的算法。今天就来写一个。

普通 hash 的结果

先看看普通 hash 怎么做。

首先，需要缓存节点对象，缓存中的存储对象，还有一个缓存节点集合，用于保存有效的缓存节点。

1. 实际存储对象，很简单的一个类，只需要获取他的 hash 值就好：

  static class Obj {
    String key;
    Obj(String key) {
      this.key = key;
    }
    @Override
    public int hashCode() {
      return key.hashCode();
    }
    @Override
    public String toString() {
      return "Obj{" +
          "key='" + key + '\'' +
          '}';
    }
  }

2. 缓存节点对象，用于存储实际对象：

  static class Node {

    Map<Integer, Obj> node = new HashMap<>();
    String name;

    Node(String name) {
      this.name = name;
    }

    public void putObj(Obj obj) {
      node.put(obj.hashCode(), obj);
    }

    Obj getObj(Obj obj) {
      return node.get(obj.hashCode());
    }

    @Override
    public int hashCode() {
      return name.hashCode();
    }
  }

也很简单，内部使用了一个 map 保存节点。

3. 缓存节点集合，用于保存有效的缓存节点：

 static class NodeArray {

    Node[] nodes = new Node[1024];
    int size = 0;

    public void addNode(Node node) {
      nodes[size++] = node;
    }

    Obj get(Obj obj) {
      int index = obj.hashCode() % size;
      return nodes[index].getObj(obj);
    }

    void put(Obj obj) {
      int index = obj.hashCode() % size;
      nodes[index].putObj(obj);
    }
  }

内部一个数组，取数据时，通过取余机器数量获取缓存节点，再从节点中取出数据。

4. 测试：当增减节点时，还能不能找到原有数据：

 /**
   * 验证普通 hash 对于增减节点，原有会不会出现移动。
   */
  public static void main(String[] args) {

    NodeArray nodeArray = new NodeArray();

    Node[] nodes = {
        new Node("Node--> 1"),
        new Node("Node--> 2"),
        new Node("Node--> 3")
    };

    for (Node node : nodes) {
      nodeArray.addNode(node);
    }

    Obj[] objs = {
        new Obj("1"),
        new Obj("2"),
        new Obj("3"),
        new Obj("4"),
        new Obj("5")
    };

    for (Obj obj : objs) {
      nodeArray.put(obj);
    }

    validate(nodeArray, objs);
  }

  private static void validate(NodeArray nodeArray, Obj[] objs) {
    for (Obj obj : objs) {
      System.out.println(nodeArray.get(obj));
    }

    nodeArray.addNode(new Node("anything1"));
    nodeArray.addNode(new Node("anything2"));

    System.out.println("========== after  =============");

    for (Obj obj : objs) {
      System.out.println(nodeArray.get(obj));
    }
  }

测试步骤如下：

1. 向集合中添加 3 个节点。
2. 向 集群 中添加 5 个对象，这 5 个对象会根据 hash 值散列到不同的节点中。
3. 打印 未增减前 的数据。
4. 打印 增加 2 个节点 后数据，看看还能不能访问到数据。

结果：

一个都访问不到了。这就是普通的取余的缺点，在增减机器的情况下，这种结果无法接收。

再看看一致性 hash 如何解决。

一致性 Hash 的结果

关键的地方来了。

缓存节点对象和实际保存对象不用更改，改的是什么？

改的是保存对象的方式和取出对象的方式，也就是不使用对机器进行取余的算法。

新的 NodeArray 对象如下：

static class NodeArray {

/** 按照 键 排序*/
TreeMap<Integer, Node> nodes = new TreeMap<>();

void addNode(Node node) {
  nodes.put(node.hashCode(), node);
}

void put(Obj obj) {
  int objHashcode = obj.hashCode();
  Node node = nodes.get(objHashcode);
  if (node != null) {
    node.putObj(obj);
    return;
  }

  // 找到比给定 key 大的集合
  SortedMap<Integer, Node> tailMap = nodes.tailMap(objHashcode);
  // 找到最小的节点
  int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey();
  nodes.get(nodeHashcode).putObj(obj);

}

Obj get(Obj obj) {
  Node node = nodes.get(obj.hashCode());
  if (node != null) {
    return node.getObj(obj);
  }

  // 找到比给定 key 大的集合
  SortedMap<Integer, Node> tailMap = nodes.tailMap(obj.hashCode());
  // 找到最小的节点
  int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey();
  return nodes.get(nodeHashcode).getObj(obj);
}
}

该类和之前的类的不同之处在于：

1. 内部没有使用数组，而是使用了有序 Map。
2. put 方法中，对象如果没有落到缓存节点上，就找比他小的节点且离他最近的。这里我们使用了 TreeMap 的 tailMap 方法，具体 API 可以看文档。
3. get 方法中，和 put 步骤相同，否则是取不到对象的。

具体寻找节点的方式如图：

image.png

相同的测试用例，执行结果如下：

image.png

找到了之前所有的节点。解决了普通 hash 的问题。

总结

代码比较简单，主要是通过 JDK 自带的 TreeMap 实现的寻找临近节点。当然，我们这里也只是测试了添加，关于修改还没有测试，但思路是一样的。这里只是做一个抛砖引玉。

同时，我们也没有实现虚拟节点，感兴趣的朋友可以尝试一下。

good luck！！！！