从分布式看一致性哈希算法

vlambda
2020-04-06

从分布式看一致性哈希算法

最近一段时间忙着两个重大项目的发布，好久没有更新文章了。一致性哈希其实并不复杂，在各大面试中都能接触到。一般的套路就是从Hashmap开始问起其中的hashcode，到一致性哈希的思路，今天我们从实现的角度看一个简单的实现，也让大家有个更直观的印象。

在强一致性的分布式选举算法Raft中使用leader-follower机制实现了共识协商，但写请求只能限制在leader节点上处理，导致了集群的处理性能类似于单机，那么请求量的增加，集群的性能可能就扛不住了，会造成系统过载和服务不可用，这时可以考虑使用哈希算法。

1、哈希算法

关于哈希算法，我曾经在《》中介绍过哈希算法的原理，其最终根据计算得到一个int型的数据，这个数值就是hashcode。这个int型的hashcode也是下面我们说的一致性哈希为什么会在2的32次方减1这个圆环上分布节点和数据的原因。

哈希算法是计算数据的哈希值，然后根据节点的个数作为哈希桶，将该数据的哈希值进行取余操作，然后存放到该节点中。等查找该数据的时候，需要根据该数据的哈希值得到存放的节点，然后获取该节点下的数据。这里，可以把节点想象成分布式系统下的单台服务器。数据存放在某节点就代表存放在某台机器。

这里，我们以一个Key-Value数据为例，类似于Redis集群那样存放。这里假设定义的节点DataObj类如下：

public class DataObj { String key;    String value; public DataObj(String key, String value) { this.key = key; this.value = value;    }   //此处省略hashcode方法和toString方法}

我们定义一下机器的节点Node类，用于存储上面的数据节点。简单起见，我们只实现一下存和取方法。

public class Node { HashMap<Integer,DataObj> hashmap;    String NodeName;//NodeName的作用在实现虚拟节点有用 public Node(String nodeName) { NodeName = nodeName; hashmap = new HashMap<>(); }  //存放数据 public void putDataObj(DataObj obj){ hashmap.put(obj.hashCode(),obj); return; }    //获取数据 public DataObj getData(DataObj obj){      return hashmap.get(obj.hashCode()); }}

接下来，我们实现一个类NodeArray存放所有节点，通过该类存放和获取数据，相当于访问集群的意思了。

public class NodeArray { public static final int MAX_NODE= 1024; Node[] nodes = new Node[MAX_NODE];    int size = 0; public NodeArray() { }
 public void addNode(Node node){        if(size>MAX_NODE) return; nodes[size++] = node; }
 DataObj get(DataObj obj) { int index = obj.hashCode() % size; return nodes[index].getData(obj); }
   void put(DataObj obj) { int index = obj.hashCode() % size; nodes[index].putDataObj(obj); }}

下面我们测试看看，假如我们创建了3个节点，并存放了5个数据。最后再逐一访问这些数据节点，这些数据可以正常查询到。

然后，我们新增一个节点或删除一个节点，此时已经无法获取到节点了。

2、一致性哈希算法

上面的问题出现在增加或减少节点的情况下，这就类似于某台机器故障或扩容了一台机器，此时数据访问基本全部失效，需要重新rehash全部数据。而一致性哈希算法则可以有效减少数据迁移工作。那么一致性哈希算法如何解决的呢？

一致性哈希首先将节点也映射到这个环上面，这个环就是hashcode的大小，当通过节点的key去查找节点的时候，先找到最近的Node，然后再获取值。

public class ConsistNodeArray { /** 按照键排序*/    TreeMap<Integer, Node> nodes = new TreeMap<>(); void addNode(Node node) { nodes.put(node.hashCode(), node); }
 void put(DataObj obj) {       int objHashcode = obj.hashCode(); Node node = nodes.get(objHashcode); if (node != null) { node.putDataObj(obj); return; }     // 找到比给定 key 大的集合     SortedMap<Integer, Node> tailMap = nodes.tailMap(objHashcode);     // 找到最小的节点     int nodeHashcode = tailMap.isEmpty() ?       nodes.firstKey() : tailMap.firstKey();     nodes.get(nodeHashcode).putDataObj(obj); }
 DataObj get(DataObj obj) { Node node = nodes.get(obj.hashCode()); if (node != null) { return node.getData(obj);        }      // 找到比给定 key 大的集合      SortedMap<Integer,Node> tailMap=nodes.tailMap(obj.hashCode()); // 找到最小的节点     int nodeHashcode = tailMap.isEmpty() ?         nodes.firstKey():tailMap.firstKey();     return nodes.get(nodeHashcode).getData(obj); }}

此时如果不新增节点的话，测试结果可以全部查询到数据。如果新增2个节点，也能获取大部分数据。

这里需要注意的是，新增或减少节点，肯定需要做部分数据迁移的，只是这个迁移量很小，有一些专业的测试结果显示：对于 1000 万 key 的 3 节点 KV 存储，如果我们增加 1 个节点，变为 4 节点集群，只需要迁移 24.3% 的数据。如果原有节点数量越多，其实迁移量更少。当然了，如果这里引入虚拟节点，那么迁移量更低。

至于虚拟节点的实现，可以在创建Node的时候指定名称为NodeName-A，NodeName-B之类的，实际节点是同一个Node即可，这里不再赘述。

3、总结

一致性哈希算法通过两次哈希计算，不直接寻找映射的节点，而是找到距离当前数据哈希值最近的节点Node，然后将数据存储到该节点上。当发生节点Node故障或新增节点时，也只是影响这部分区域的节点。

对于要是想数据更均匀的分布在一致性哈希算法上面，可以引入虚拟节点的方法解决。

vlambda博客
学习文章列表