3分钟，教你用Java实现一致性哈希

站长

2023年09月07日 11:23 · 阅读数 11

上篇讲了一致性哈希的原理，本篇就用代码一步步实现一致性哈希的基础功能！！！

构建哈希环（DHT）

由于一致性哈希讲究有序，所以哈希环的数据结构选择 TreeMap(key位置坐标，value为实际节点) ，可以方便的顺时针查找下一个节点。

列举一下DHT的主要方法

节点对自己IP和端口 进行哈希映射到环上不同的位置
数据对key映射到环上的节点进行存储

哈希算法的选择

Java内建的散列码[hash code]概念被限制为32位，并且没有分离散列算法和它们所作用的数据，因此很难用备选算法进行替换，Object.hashCode往往很快，但是在预防碰撞上却很弱，也没有对分散性的预期。

我们选择 Guava 包 MurmurHash() 算法，运算效率高，预防碰撞也很强。

直接上代码

我们模拟实际存储节点类，如下

 public class ServerNode {
      private String ip;
 
     private List<String> dataList = new ArrayList<>();
 
     public void addData(String data) {
         dataList.add(data);
     }
 
     public String getIp() {
         return ip;
     }
 
     public void setIp(String ip) {
         this.ip = ip;
     }
 
     public ServerNode(String ip) {
         this.ip = ip;
     }
 
     @Override
     public String toString() {
         return "ServerNode{" +
                 "ip='" + ip + ''' +
                 ", dataList=" + dataList +
                 '}';
     }
 }

哈希环定义如下

 
 public class DHT {
     private  TreeMap<Long, ServerNode> dht = new TreeMap<>();
     HashFunction hashFunction = Hashing.murmur3_128(64);
     /**
      *  节点映射 
      *  
      * 添加节点 对节点 hash（IP + port）%16384结果 作为哈希环下标
      */
    public void addNode(ServerNode serverNode) {
 
         HashCode hashCode = getHashCode(serverNode.getIp());
         long index = hashCode.asLong() % 16384L;
         System.out.println(serverNode.getIp() + ": " + Math.abs(index));
         dht.put(Math.abs(index), serverNode);
 
     }
     
     private HashCode getHashCode(String ip) {
         return hashFunction.newHasher()
                 .putString(ip, StandardCharsets.UTF_8)
                 .hash();
     }
 
 
     /**
      * 根据key 选择一个节点，如果没有命中节点，则顺时针查找下一个节点
      */
     public ServerNode selectNode(String key) {
         HashCode hashCode = hashFunction.newHasher()
                 .putString(key, StandardCharsets.UTF_8)
                 .hash();
 
         long index = Math.abs(hashCode.asLong()) % 16384L;
         SortedMap<Long, ServerNode> subDht = dht.tailMap(index);
           System.out.print("key:" + key + "的位置: " + index + " 选择的节点: ");
         return dht.get(subDht.firstKey());
 
     }
 
     /**
      * 向集群中 添加数据 
      */
     public void addData(String key) {
         //先通过哈希算法选择 一个实际节点
         ServerNode serverNode = selectNode(key);
         System.out.println(serverNode.getIp());
         serverNode.addData(key);
     }
 
 }

然后我们创建测试程序

 public class Main {
     public static void main(String[] args) {
         DHT dht = new DHT();
         System.out.println("初始化节点映射.....");
         ServerNode serverNode = new ServerNode("10.6.3.178");
         ServerNode serverNode2 = new ServerNode("10.6.3.191");
         ServerNode serverNode3 = new ServerNode("10.6.3.183");
         ServerNode serverNode4 = new ServerNode("10.6.3.189");
         dht.addNode(serverNode);
         dht.addNode(serverNode2);
         dht.addNode(serverNode3);
         dht.addNode(serverNode4);
         System.out.println("添加数据");
         dht.addData("shop:sku:4");
         dht.addData("shop:sku:7");
     }
 }

运行结果如下图

3分钟，教你用Java实现一致性哈希

虚拟节点优化

上面的节点数量太少，容易造成数据倾斜问题。如果对数据分布想要达到更均匀，可以采取虚拟节点优化。

实践

我们维护虚拟节点和实际节点的映射关系。key为虚拟节点IP，value为实际节点。

举个例子对于ip为10.6.3.178的节点，对应的虚拟节点IP就可以是10.6.3.178#1，10.6.3.178#2，10.6.3.178#3。映射关系可以如下设计

  private final HashMap<String, ServerNode> vit = new HashMap<>();

然后在修改节点映射方法

  public void addNode(ServerNode serverNode) {
 
         HashCode hashCode = getHashCode(serverNode.getIp());
 
         long index = hashCode.asLong() % 16384L;
         System.out.println(serverNode.getIp() + ": " + Math.abs(index));
         dht.put(Math.abs(index), serverNode);
         //添加虚拟节点
         for (int i = 0; i < 15;i++) {
             //获得虚拟节点的哈希值
             HashCode hashCodeVit = getHashCode(serverNode.getIp() + "#" + i);
             long indexV = hashCodeVit.asLong() % 16384L;
             ServerNode serverNodeV = new ServerNode(serverNode.getIp() + "#" + i);
             //将虚拟节点添加到哈希环，
             dht.put(Math.abs(indexV), serverNodeV);
             //建立虚拟IP和 真实节点的映射关系
             vit.put(serverNode.getIp() + "#" + i, serverNodeV);
         }
     }

添加数据时， sleectNode() 获得的节点ip，接着去映射获取serverNode，获取为空则该节点就是真实节点；不为空，则获取的serverNode就是真实节点。

总结

以上的是实现提供了一致性哈希的实现思路。实际在生产中还要考虑读写性能，数据迁移等等。

对于数据倾斜问题，虚拟节点的总数量一定要足够大，数据才可以分布均匀。在实际项目里，为了避免机器太少造成的数据倾斜问题，往往会把哈希环的容纳总量（16384）调小，也可以使数据分布均匀。

我是爱聊技术的山人，我们下期再见🤗🤗