在分布式缓存或者存储系统中经常都会用到hash算法,最早的时候memeched开源客户端都用的简单取余的hash算法来做分布式缓存集群中的命中要缓存的机器,一致性hash算法的原理在这里就不用描述了网上很多资料,下面的图来回忆下原理。简单的说就是把所有的机器结点投放到0-2^32-1结点圆环上去。再对key做哈希运算找到环上的结点存储。因为把有限几个阶段分布到2^32个几点上去需要均匀命中,会在实际几点中间虚拟很多结点。n1和n2之间的虚拟结点命中之后,会在n2上存储。
最近看了下jedis里面对这个功能的实现,是有些变通的做法来实现,下满的方法initialize
参数是实际结点列表,nodes = new TreeMap<Long, S>();为hash圆环,每个结点通过hash之后都散落在nodes上,客户端端取实际要使用的结点是通过nodes.tailMap(algo.hash(key));取环上顺时针比当前key大的结点map,在通过 tail.get(tail.firstKey());取这个map上第一个key所在虚拟结点上的值,这个虚拟结点与顺时针第一个相邻的结点实际连接主机是一样。
下面这个算法是讲key 先md5然后取hash
private void initialize(List<S> shards) {
nodes = new TreeMap<Long, S>();
for (int i = 0; i != shards.size(); ++i) {
final S shardInfo = shards.get(i);
if (shardInfo.getName() == null)
for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
nodes.put(this.algo.hash("SHARD-" + i + "-NODE-" + n),
shardInfo);
}
else
for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
nodes.put(
this.algo.hash(shardInfo.getName() + "*"
+ shardInfo.getWeight() + n), shardInfo);
}
resources.put(shardInfo, shardInfo.createResource());
}
}
public R getShard(byte[] key) {
return resources.get(getShardInfo(key));
}
public R getShard(String key) {
return resources.get(getShardInfo(key));
}
public S getShardInfo(byte[] key) {
SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
if (tail.isEmpty()) {
return nodes.get(nodes.firstKey());
}
return tail.get(tail.firstKey());
}
通过算法看和我们在文章上看的hash算法还是有点变通,文章中图上实际节点和虚拟几点都会是连续,程序算法中,虚拟结点是随机(作了md5)分布到环上的实际对应的主机是一个主机。因为同一个虚拟结点随机分布在环上,取主机的时候只要取比hash(md5(key))大的结点上第一个结点对应的主机就可以,并不关心是node1 还是node2...
- 大小: 38.7 KB
分享到:
相关推荐
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)
一致性 hash 算法介绍
IT面试常见的题目,对于分布式存储系统中常碰到的故障问题,如何解决,就是采用一致性hash算法
一致性hash算法
一致性Hash算法的原理及实现
简单模拟实现一致性Hash,透过虚拟节点映射至实际结点,解决一致性Hash的单调性和平衡性问题。
一致性hash算法简介加C++实现
别人写的一个一致性hash的java实现,分享下
一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。 首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们...
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
一致性hash算法简介
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
主要介绍了PHP实现的一致性Hash算法,结合实例形式详细分析了php一致性Hash算法的概念、原理及相关实现与使用技巧,需要的朋友可以参考下
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
一致性Hash算法,易于扩容;添加了 单元测试,使用Spring提供的RestTemplate调用RestFul风格的API接口;整合了 quartz 定时任务框架 ,并进行了封装,只需在构建完定时任务Job类后,在 application-quartz....
c++实现的一致性hash算法库,可以直接编译成静态库、动态库,包含demo程序。
一致性哈希算法的php版,希望能帮到phper了解一致性哈希