public class LoadBalanceManager {
private static TreeMap<Long, Node> nodes; // 虚拟节点到真实节点的映射
private static TreeMap<Long, Node> treeKey; // key到真实节点的映射
private static final int NODE_NUM = 10; // 每个机器节点关联的虚拟节点个数
/**
* 初始化方法,将作为节点的机器List传入作为参数
* @param nodeList
*/
public LoadBalanceManager(List<Node> nodeList) {
nodes = new TreeMap<Long, Node>();
treeKey = new TreeMap<Long, Node>();
for (Node node : nodeList) {
for (int n = 0; n < NODE_NUM; n++) {
// 一个真实机器节点关联NODE_NUM个虚拟节点
nodes.put(hash("SHARD-" + node.getIp() + "-NODE-" + n), node);
}
}
}
/**
* 映射key到真实节点
* @param ip
*/
public void loadBalance(String ip) {
SortedMap<Long, Node> tail = nodes.tailMap(hash(ip)); // 沿环的顺时针找到一个虚拟节点
if (tail.size() == 0) {
// 如果此ip的hash值比任何一个节点的值都大,则取第一个节点
Node first = nodes.firstEntry().getValue();
treeKey.put(hash(ip), first);
System.out.println(ip + "(hash: " + hash(ip) + ")连接到主机->" + first);
return;
}
treeKey.put(hash(ip), tail.get(tail.firstKey()));
System.out.println(ip + "(hash: " + hash(ip) + ")连接到主机->"
+ tail.get(tail.firstKey()));
}
/**
* 增加一个主机
*
* @param node
*/
public void addNode(Node node) {
System.out.println("增加主机" + node + "的变化:");
for (int n = 0; n < NODE_NUM; n++) {
Long key = hash("SHARD-" + node.getIp() + "-NODE-" + n);
addS(key, node);
}
}
/**
* 删除真实节点
*
* @param node
*/
public void deleteNode(Node node) {
if (node == null) {
return;
}
System.out.println("删除主机" + node + "的变化:");
for (int i = 0; i < NODE_NUM; i++) {
// 定位s节点的第i的虚拟节点的位置
Long key = hash("SHARD-" + node.getIp() + "-NODE-" + i);
SortedMap<Long, Node> tail = nodes.tailMap(key);
SortedMap<Long, Node> head = nodes.headMap(key);
Long begin = 0L;
Long end = 0L;
SortedMap<Long, Node> between;
if (head.size() == 0) {
between = treeKey.headMap(nodes.firstKey());
end = tail.firstKey();
tail.remove(end);
// nodes.remove(end);// 从nodes中删除s节点的第i个虚拟节点
} else {
begin = head.lastKey();
end = tail.firstKey();
tail.remove(end);
between = treeKey.subMap(begin, end);// 在s节点的第i个虚拟节点的所有key的集合
}
for (Iterator<Long> it = between.keySet().iterator(); it.hasNext();) {
Long lo = it.next();
treeKey.put(lo, tail.get(tail.firstKey()));
System.out.println("hash(" + lo + ")改变到->"
+ tail.get(tail.firstKey()));
}
}
}
/**
* 添加一个虚拟节点进环形结构,lg为虚拟节点的hash值
*
* @param hashKey
* @param node
*/
private void addS(Long hashKey, Node node) {
SortedMap<Long, Node> tail = nodes.tailMap(hashKey);
SortedMap<Long, Node> head = nodes.headMap(hashKey);
Long begin = 0L;
SortedMap<Long, Node> between;
if (head.size() == 0) {
between = treeKey.headMap(hashKey);
} else {
begin = head.lastKey();
between = treeKey.subMap(begin, hashKey);
}
nodes.put(hashKey, node);
for (Iterator<Long> it = between.keySet().iterator(); it.hasNext();) {
Long lo = it.next();
treeKey.put(lo, nodes.get(hashKey));
System.out.println("hash(" + lo + ")改变到->"
+ tail.get(tail.firstKey()));
}
}
/**
* MurMurHash算法,是非加密HASH算法,性能很高,
* 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)
* 等HASH算法要快很多,而且据说这个算法的碰撞率很低.
*/
private 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);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}
分享到:
相关推荐
一致性 hash 算法介绍
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)
IT面试常见的题目,对于分布式存储系统中常碰到的故障问题,如何解决,就是采用一致性hash算法
一致性hash算法
一致性Hash算法的原理及实现
一致性hash算法简介
一致性hash算法简介加C++实现
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。 首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们...
基于go语言实现的分布式缓存系统源码+项目说明(以键值对的形式存储数据,一致性hash算法选择存储节点,Protobuf通信协议编解码。用户输入查询请求后,会优先在缓存系统查询,查不到则使用回调函数去源数据库查询,...
一致性Hash算法,易于扩容;添加了 单元测试,使用Spring提供的RestTemplate调用RestFul风格的API接口;整合了 quartz 定时任务框架 ,并进行了封装,只需在构建完定时任务Job类后,在 application-quartz....
主要介绍了PHP实现的一致性Hash算法,结合实例形式详细分析了php一致性Hash算法的概念、原理及相关实现与使用技巧,需要的朋友可以参考下
随着虚拟节点的增加,数据量分配就比较平均了,但是并不是虚拟节点数量越多就越好,因为要考虑这些虚拟节点带来的性能开销以及算法的复杂性;
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
c++实现的一致性hash算法库,可以直接编译成静态库、动态库,包含demo程序。
比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ; hash(object)%N
引入“虚拟节点”后,映射关系就从{对象->节点}转换到了{对象->虚拟节点}。查询物体所在 cache时的映射关系如图 7 所示。图 7 查询对象所在 cach