java 哈希一致算法_一致哈希算法Java实现
一致哈希算法(Consistent Hashing Algorithms)是一個分布式系統(tǒng)中常用的算法。傳統(tǒng)的Hash算法當(dāng)槽位(Slot)增減時，面臨所有數(shù)據(jù)重新部署的問題，而一致哈希算法確可以保證，只需要移動K/n份數(shù)據(jù)(K為數(shù)據(jù)總量, n為槽位數(shù)量)，且只影響現(xiàn)有的其中一個槽位。這使得分布式系統(tǒng)中面對新增或者刪除機(jī)器時，能夠更快速的處理更改請求。本文將用Java實現(xiàn)一個簡單版本的一致哈希算法，只為說明一致哈希算法的核心思想。
一致哈希算法介紹
一致哈希算法的介紹很多，如wiki，以及很多的博客。在此只簡述其概念，詳細(xì)的介紹請參考相關(guān)論文。第一個概念是節(jié)點(Node)，分布式系統(tǒng)中相當(dāng)于一臺機(jī)器。所有的節(jié)點邏輯上圍起來形成一個圓環(huán)。第二個概念是數(shù)據(jù)(Data)，每份數(shù)據(jù)都有一個key值，數(shù)據(jù)總是需要存儲到某一個節(jié)點上。數(shù)據(jù)和節(jié)點之間如何關(guān)聯(lián)的呢？通過區(qū)域的概念關(guān)聯(lián)，每一個節(jié)點都負(fù)責(zé)圓環(huán)上的一個區(qū)域，落在該區(qū)域上的就存儲在該節(jié)點上，通常區(qū)域為左側(cè)閉合，右側(cè)開放的形式，如[2500,5000)。
以下是一個擁有4個節(jié)點的一致哈希算法示意圖:
總的范圍定為10000，也限定了總槽位的數(shù)量。可以依照項目的需要，制定合適的大小。
Node1的起始位置為0，負(fù)責(zé)存儲[0, 2500)之間的數(shù)據(jù)
Node2的起始位置為2500，負(fù)責(zé)存儲[2500, 5000)之間的數(shù)據(jù)
Node3的起始位置為5000，負(fù)責(zé)存儲[5000, 7500)之間的數(shù)據(jù)
Node4的起始位置為7500，負(fù)責(zé)存儲[7500, 10000)之間的數(shù)據(jù)
一致哈希算法最大的特點在于新增或者刪除節(jié)點的處理。如果新增一個起始位置為1250的節(jié)點Node5，那么影響到的唯一一個節(jié)點就是Node1，Node1的存儲范圍由[0, 2500)變更[0, 1250)，Node5的存儲范圍為[1250, 2500)，所以需要把落于[1250, 2500)范圍的數(shù)據(jù)搬移到Node5上。其它的不需要做出改變，這一點非常的重要。相當(dāng)于Node5分擔(dān)了Node1的部分工作。如果把Node3刪除，那么需要把Node3上面的數(shù)據(jù)搬移到Node2上面，Node2的范圍擴(kuò)大為[2500,7500)，Node2承擔(dān)了Node3的工作。
一致哈希算法Java的具體實現(xiàn)
Java是面向?qū)ο蟮恼Z言，首先需要抽象對象。Node，表示節(jié)點，有名字，起始位置，以及數(shù)據(jù)列表三個屬性，由于Node和數(shù)據(jù)之間的匹配，使用的是范圍，所以為了簡單起見，Node上加了一個end的屬性。本來應(yīng)該有Data以及DataKey的概念，但是為了簡單起見，示例中Data就是字符串，Key就是自己。
整個圓環(huán)有一個長度，定義為scope，默認(rèn)為10000。新增節(jié)點的算法是，找到最大的空擋，把新增節(jié)點放中間。當(dāng)然也可以換為找到壓力(數(shù)據(jù)量)最大的節(jié)點，把新增節(jié)點放在該節(jié)點之后。刪除節(jié)點有一點小技巧，如果刪除的是開始位置為0的節(jié)點，那么把下一個節(jié)點的開始位置置為0，和普通的退格不同。這能保證只要有節(jié)點，就一定有一個從0開始的節(jié)點。這能簡化我們的算法和處理邏輯。
addItem方法就是往系統(tǒng)里面放數(shù)據(jù)，最后為了展示數(shù)據(jù)的分布效果，提供desc方法，打印出數(shù)據(jù)分布情況。很有意思。
整體代碼如下:
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();
}
}
需要進(jìn)一步完善的地方
不同節(jié)點之間互相備份，提高系統(tǒng)的可靠性。節(jié)點范圍的動態(tài)調(diào)整，有時候分布可能不夠平衡。
總結(jié)
以上是生活随笔為你收集整理的java 哈希一致算法_一致哈希算法Java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 电脑多开抢红包(多开抢红包助手)
- 下一篇： 血手键盘快捷键使用(血手鼠标按键功能)