ConsistentHashIng
一致性哈希起源是关于集群和负载均衡
解决服务器集群通信、缓存集群的问题

先构造一个长度为23^2的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 232-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 232-1]),接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点,完成Key到服务器的映射查找。

简单实现代码
- 无虚拟节点
加入节点的时候数据迁移考虑 头 中 俩个节点
删除节点的时候数据迁移考虑 头 中 尾三个节点
package _10_Hash;
//一致性hash
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.*;
/**
* 起源 关于集群和负载均衡 服务器集群
*/
public class ConsistentHashIng1 {
//hash算法 将 关键字映射到2^32的环状空间里面
static long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(
ByteOrder.LITTLE_ENDIAN);
// for big-endian version, do this first:
// finish.position(8-buf.remaining());
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return Math.abs(h);
}
//机器节点==网络节点
static class Node implements HashNode {
String name;
String ip;
@Override
public String getName() {
return name;
}
@Override
public String toString() {
return this.name + "\t" + this.ip;
}
public Node(String name, String ip) {
this.name = name;
this.ip = ip;
}
}
interface HashNode {
String getName();
}
// 节点列表
List<Node> nodes;
TreeMap<Long, Node> hashAndNode = new TreeMap<>();//存机器hash和节点
TreeMap<Long, Node> keyAndNode = new TreeMap<>();//存Userkey和节点
/**
* 机器节点初始化
*
* @param nodes
*/
public ConsistentHashIng1(List<Node> nodes) {
this.nodes = nodes;
init();//初始化
}
private void init() {
for (int i = 0; i < nodes.size(); i++) {
Node node = nodes.get(i);
long hash = hash(node.ip);
hashAndNode.put(hash, node);
}
}
//增加资源 key User
private void add(String key) {
long hash = hash(key);
SortedMap<Long, Node> subMap = hashAndNode.tailMap(hash);//找到map中key所有fromKey大的 所有的键值对,组成一个子Map
if (subMap.size() == 0) {//环的尽头 折回到first
keyAndNode.put(hash, hashAndNode.firstEntry().getValue());
} else {
Node node = subMap.get(subMap.firstKey());//第一个节点,key应该归属的节点
keyAndNode.put(hash, node);
}
}
/**
* 增加新的机器节点
* 要特判 插入的节点在环头
*
* @param newNode
*/
private void add(Node newNode) {
long hash = hash(newNode.ip);
hashAndNode.put(hash, newNode);
//数据迁移 模拟 和实际不相符。
SortedMap<Long, Node> pre = hashAndNode.headMap(hash);//所以小于toKey的hash组成的map
if (pre.size() == 0) {//新机器节点在环的头部
//0~这个节点
SortedMap<Long, Node> between = keyAndNode.subMap(new Long(0), hash);
for (Map.Entry<Long, Node> entry : between.entrySet()) {//改变这个范围内的映射关系
entry.setValue(newNode);
}
//最后一个节点到 2^32
between = keyAndNode.tailMap(hashAndNode.lastKey());
for (Map.Entry<Long, Node> entry : between.entrySet()) {//改变这个范围内的映射关系
entry.setValue(newNode);
}
} else {//在环的非头部
long from = pre.lastKey();
long to = hash;
SortedMap<Long, Node> between = keyAndNode.subMap(from, to);
for (Map.Entry<Long, Node> entry : between.entrySet()) {//改变这个范围内的映射关系
entry.setValue(newNode);
}
}
}
public void remove(Node oldNode) {
long hash = hash(oldNode.ip);
if (!hashAndNode.containsKey(hash))//不存在该节点
return;
SortedMap<Long, Node> pre = hashAndNode.headMap(hash);//所有 比hash小的Node组成的map
SortedMap<Long, Node> next = hashAndNode.tailMap(hash);
int cnt = 0;//取出目标节点的下一个节点
Node nextNode = hashAndNode.firstEntry().getValue();//第一个节点
/**
* 三种情况: 头 中 尾
* 1.如果是删除最后一个节点 next指向 √
* 2. 删除头结点 两部分资源分配
* 3.node 删除 清理
*/
//返回oldNode的下一个节点
for (Map.Entry<Long, Node> entry : next.entrySet()) {
if (cnt++ == 1) {
nextNode = next.get(entry.getKey());
break;
}
}
System.out.println("删除:" + oldNode.name);
System.out.println("迁移:" + nextNode.name);
if (pre.size() == 0) {//该节点 是最小的节点
SortedMap<Long, Node> between = keyAndNode.subMap(new Long(0), hash);
for (Map.Entry<Long, Node> entry : between.entrySet()) {
entry.setValue(nextNode);
}
between = keyAndNode.tailMap(hashAndNode.lastKey());//最后一个节点之后的key
for (Map.Entry<Long, Node> entry : between.entrySet()) {
entry.setValue(nextNode);
}
System.out.println("要删除的是头结点");
} else {
long from = pre.lastKey();
long to = hash;
SortedMap<Long, Node> source = keyAndNode.subMap(from, hash);//被节点删的 key(user)数据
if (source.size() == 0) {//无迁移资源
System.out.println("无迁移资源");
return;
}
for (Map.Entry<Long, Node> entry : source.entrySet()) {//改变这个范围内的映射关系
entry.setValue(nextNode);//换Value 到目标节点
}
}
hashAndNode.remove(hash);
}
public static void main(String[] args) {
ArrayList<Node> nodes = new ArrayList<>();
nodes.add(new Node("node0", "192.168.1.2"));
nodes.add(new Node("node1", "192.168.1.3"));
nodes.add(new Node("node2", "192.168.1.4"));
nodes.add(new Node("node3", "192.168.1.5"));
nodes.add(new Node("node4", "192.168.1.6"));
ConsistentHashIng1 obj = new ConsistentHashIng1(nodes);
// Entry遍历 节点 :遍历TreeMap的键值对
obj.traversalNode(obj.hashAndNode);
//add User资源
obj.add("zhang.sant");
obj.add("saf4t2");
obj.add("sas2gg3rr3t4");
obj.add("saf2gg3425err5456");
obj.add("235f2gg34256434636");
obj.add("saf2gg34256r364y22");
obj.add("s5f2gg3425634636y22hw3h2hh");
obj.add("s652gg342563463hry22hw3h2hh36362");
obj.add("su7tgjg3425634636hhw3h2hh3636245yy4y4");
obj.add("sadfgg3425634636yjtyz2hh3636245yy4y4gdfsgh45u54");
obj.add("sa56gg3425634636y22hw3h2hh36245yy4y4asdg3h45u54");
for (Map.Entry<Long, Node> entry :
obj.keyAndNode.entrySet()) {
System.out.println(entry.getValue().getName() + " \t收到资源: \t" + "hash:" + " \t" + entry.getKey());
}
//加入新节点
nodes.add(new Node("node5", "192.168.1.9"));
obj.add(nodes.get(5));
System.out.println("=====更新List===");
obj.traversalNode(obj.hashAndNode);
obj.traversalUser(obj.keyAndNode);
System.out.println("=====更新List===");
obj.remove(nodes.get(0));
System.out.println("查看删除后的节点User");
obj.traversalNode(obj.hashAndNode);
obj.traversalUser(obj.keyAndNode);
obj.remove(nodes.get(4));
System.out.println("查看删除后的节点User");
obj.traversalNode(obj.hashAndNode);
obj.traversalUser(obj.keyAndNode);
obj.remove(nodes.get(5));
System.out.println("查看删除后的节点User");
obj.traversalNode(obj.hashAndNode);
obj.traversalUser(obj.keyAndNode);
}
private void traversalNode(Map<Long, Node> hashAndNode) {
// Entry遍历 节点 :遍历TreeMap的键值对
for (Map.Entry<Long, Node> entry : hashAndNode.entrySet()) {//升序键序 遍历hashAndNode
System.out.println(entry.getKey() + ": \t" + entry.getValue());
}
}
private void traversalUser(Map<Long, Node> keyAndNode) {
for (Map.Entry<Long, Node> entry :
keyAndNode.entrySet()) {
System.out.println(entry.getValue().getName() + " \t收到资源: \t" + "hash:" + " \t" + entry.getKey());
}
}
}
相关文献
[1]一致性Hash协议
[2]深入浅出一致性hash
[3]一致性hash算法的深入理解
本文作者:Author: 寒光博客
文章标题:[java] 一致性hash
本文地址:https://dxoca.cn/java/318.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/318.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
客串,考古ing
是不是漏掉了虚拟节点和偏斜