首页 > 代码库 > 一致哈希算法Java实现
一致哈希算法Java实现
一致哈希算法(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();>需要进一步完善的地方
不同节点之间互相备份,提高系统的可靠性。节点范围的动态调整,有时候分布可能不够平衡。
一致哈希算法Java实现