一致哈希算法(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<Node> nodes;

	public ConsistentHash() {
		nodes = new ArrayList<Node>();
	}

	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<String> iter = maxNode.datas.iterator();
			while (iter.hasNext()) {
				String data = http://www.mamicode.com/iter.next();>
须要进一步完好的地方
不同节点之间互相备份，提高系统的可靠性。节点范围的动态调整。有时候分布可能不够平衡。