一致哈希算法(Consistent Hashing Algorithms)是一个分布式系统中常用的算法。传统的Hash算法当槽位(Slot)增减时，面临所有数据重新部署的问题，而一致哈希算法确可以保证，只需要移动K/n份数据(K为数据总量, n为槽位数量)，且只影响现有的其中一个槽位。这使得分布式系统中面对新增或者删除机器时，能够更快速的处理更改请求。本文将用Java实现一个简单版本的一致哈希算法，只为说明一致哈希算法的核心思想。

一致哈希算法介绍

一致哈希算法的介绍很多，如wiki，以及很多的博客。在此只简述其概念，详细的介绍请参考相关论文。第一个概念是节点(Node)，分布式系统中相当于一台机器。所有的节点逻辑上围起来形成一个圆环。第二个概念是数据(Data)，每份数据都有一个key值，数据总是需要存储到某一个节点上。数据和节点之间如何关联的呢？通过区域的概念关联，每一个节点都负责圆环上的一个区域，落在该区域上的就存储在该节点上，通常区域为左侧闭合，右侧开放的形式，如[2500,5000)。

以下是一个拥有4个节点的一致哈希算法示意图:

总的范围定为10000，也限定了总槽位的数量。可以依照项目的需要，制定合适的大小。

Node1的起始位置为0，负责存储[0, 2500)之间的数据

Node2的起始位置为2500，负责存储[2500, 5000)之间的数据

Node3的起始位置为5000，负责存储[5000, 7500)之间的数据

Node4的起始位置为7500，负责存储[7500, 10000)之间的数据

一致哈希算法最大的特点在于新增或者删除节点的处理。如果新增一个起始位置为1250的节点Node5，那么影响到的唯一一个节点就是Node1，Node1的存储范围由[0, 2500)变更[0, 1250)，Node5的存储范围为[1250, 2500)，所以需要把落于[1250, 2500)范围的数据搬移到Node5上。其它的不需要做出改变，这一点非常的重要。相当于Node5分担了Node1的部分工作。如果把Node3删除，那么需要把Node3上面的数据搬移到Node2上面，Node2的范围扩大为[2500,7500)，Node2承担了Node3的工作。

一致哈希算法Java的具体实现

Java是面向对象的语言，首先需要抽象对象。Node，表示节点，有名字，起始位置，以及数据列表三个属性，由于Node和数据之间的匹配，使用的是范围，所以为了简单起见，Node上加了一个end的属性。本来应该有Data以及DataKey的概念，但是为了简单起见，示例中Data就是字符串，Key就是自己。

整个圆环有一个长度，定义为scope，默认为10000。新增节点的算法是，找到最大的空挡，把新增节点放中间。当然也可以换为找到压力(数据量)最大的节点，把新增节点放在该节点之后。删除节点有一点小技巧，如果删除的是开始位置为0的节点，那么把下一个节点的开始位置置为0，和普通的退格不同。这能保证只要有节点，就一定有一个从0开始的节点。这能简化我们的算法和处理逻辑。

addItem方法就是往系统里面放数据，最后为了展示数据的分布效果，提供desc方法，打印出数据分布情况。很有意思。

整体代码如下:

public class ConsistentHash {

private int scope = 10000;

private List nodes;

public ConsistentHash() {

nodes = new ArrayList();

}

public int getScope() {

return scope;

}

public void setScope(int scope) {

this.scope = scope;

}

public void addNode(String nodeName) {

if (nodeName == null || nodeName.trim().equals("")) {

throw new IllegalArgumentException("name can't be null or empty");

}

if (containNodeName(nodeName)) {

throw new IllegalArgumentException("duplicate name");

}

Node node = new Node(nodeName);

if (nodes.size() == 0) {

node.setStart(0);

node.setEnd(scope);

nodes.add(node);

} else {

Node maxNode = getMaxSectionNode();

int middle = maxNode.start + (maxNode.end - maxNode.start) / 2;

node.start = middle;

node.end = maxNode.end;

int maxPosition = nodes.indexOf(maxNode);

nodes.add(maxPosition + 1, node);

maxNode.setEnd(middle);

// move data

Iterator iter = maxNode.datas.iterator();

while (iter.hasNext()) {

String data = iter.next();

int value = Math.abs(data.hashCode()) % scope;

if (value >= middle) {

iter.remove();

node.datas.add(data);

}

}

for (String data : maxNode.datas) {

int value = Math.abs(data.hashCode()) % scope;

if (value >= middle) {

maxNode.datas.remove(data);

node.datas.add(data);

}

}

}

}

public void removeNode(String nodeName) {

if (!containNodeName(nodeName)) {

throw new IllegalArgumentException("unknown name");

}

if (nodes.size() == 1 && nodes.get(0).datas.size() > 0) {

throw new IllegalArgumentException("last node, and still have data");

}

Node node = findNode(nodeName);

int position = nodes.indexOf(node);

if (position == 0) {

if (nodes.size() > 1) {

Node newFirstNode = nodes.get(1);

for (String data : node.datas) {

newFirstNode.datas.add(data);

}

newFirstNode.setStart(0);

}

} else {

Node lastNode = nodes.get(position - 1);

for (String data : node.datas) {

lastNode.datas.add(data);

}

lastNode.setEnd(node.end);

}

nodes.remove(position);

}

public void addItem(String item) {

if (item == null || item.trim().equals("")) {

throw new IllegalArgumentException("item can't be null or empty");

}

int value = Math.abs(item.hashCode()) % scope;

Node node = findNode(value);

node.datas.add(item);

}

public void desc() {

System.out.println("Status:");

for (Node node : nodes) {

System.out.println(node.name + ":(" + node.start + "," + node.end

+ "): " + listString(node.datas));

}

}

private String listString(LinkedList datas) {

StringBuffer buffer = new StringBuffer();

buffer.append("{");

Iterator iter = datas.iterator();

if (iter.hasNext()) {

buffer.append(iter.next());

}

while (iter.hasNext()) {

buffer.append(", " + iter.next());

}

buffer.append("}");

return buffer.toString();

}

private boolean containNodeName(String nodeName) {

if (nodes.isEmpty()) {

return false;

}

Iterator iter = nodes.iterator();

while (iter.hasNext()) {

Node node = iter.next();

if (node.name.equals(nodeName)) {

return true;

}

}

return false;

}

private Node findNode(int value) {

Iterator iter = nodes.iterator();

while (iter.hasNext()) {

Node node = iter.next();

if (value >= node.start && value < node.end) {

return node;

}

}

return null;

}

private Node findNode(String nodeName) {

Iterator iter = nodes.iterator();

while (iter.hasNext()) {

Node node = iter.next();

if (node.name.equals(nodeName)) {

return node;

}

}

return null;

}

private Node getMaxSectionNode() {

if (nodes.size() == 1) {

return nodes.get(0);

}

Iterator iter = nodes.iterator();

int maxSection = 0;

Node maxNode = null;

while (iter.hasNext()) {

Node node = iter.next();

int section = node.end - node.start;

if (section > maxSection) {

maxNode = node;

maxSection = section;

}

}

return maxNode;

}

static class Node {

private String name;

private int start;

private int end;

private LinkedList datas;

public Node(String name) {

this.name = name;

datas = new LinkedList();

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getStart() {

return start;

}

public void setStart(int start) {

this.start = start;

}

public int getEnd() {

return end;

}

public void setEnd(int end) {

this.end = end;

}

public LinkedList getDatas() {

return datas;

}

public void setDatas(LinkedList datas) {

this.datas = datas;

}

}

public static void main(String[] args) {

ConsistentHash hash = new ConsistentHash();

hash.addNode("Machine-1");

hash.addNode("Machine-2");

hash.addNode("Machine-3");

hash.addNode("Machine-4");

hash.addItem("Hello");

hash.addItem("hash");

hash.addItem("main");

hash.addItem("args");

hash.addItem("LinkedList");

hash.addItem("end");

hash.desc();

hash.removeNode("Machine-1");

hash.desc();

hash.addNode("Machine-5");

hash.desc();

hash.addItem("scheduling");

hash.addItem("queue");

hash.addItem("thumb");

hash.addItem("quantum");

hash.addItem("approaches");

hash.addItem("migration");

hash.addItem("null");

hash.addItem("feedback");

hash.addItem("ageing");

hash.addItem("bursts");

hash.addItem("shorter");

hash.desc();

hash.addNode("Machine-6");

hash.addNode("Machine-7");

hash.addNode("Machine-8");

hash.desc();

hash.addNode("Machine-9");

hash.addNode("Machine-10");

hash.addNode("Machine-11");

hash.desc();

hash.addNode("Machine-12");

hash.addNode("Machine-13");

hash.addNode("Machine-14");

hash.addNode("Machine-15");

hash.addNode("Machine-16");

hash.addNode("Machine-17");

hash.desc();

}

}

需要进一步完善的地方

不同节点之间互相备份，提高系统的可靠性。节点范围的动态调整，有时候分布可能不够平衡。