tk注册网站,又拍云 wordpress使用,上海高端品牌网站制作,猎奇网站模板一致哈希算法(Consistent Hashing Algorithms)是一个分布式系统中常用的算法。传统的Hash算法当槽位(Slot)增减时#xff0c;面临所有数据重新部署的问题#xff0c;而一致哈希算法确可以保证#xff0c;只需要移动K/n份数据(K为数据总量, n为槽位数量)#xff0c;且只影响…一致哈希算法(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那么影响到的唯一一个节点就是Node1Node1的存储范围由[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 cant 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 dataIterator 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 cant 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();}}需要进一步完善的地方不同节点之间互相备份提高系统的可靠性。节点范围的动态调整有时候分布可能不够平衡。
