一个简单的consistent hashing的例子,很容易理解。
首先有一个设备类,定义了机器名和ip:
- public class Cache
- {
- public String name;
- public String ipAddress;
- }
然后是主要的实现:
- public class Shard<T> {
- //hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,
- //所以增加虚拟节点
- private TreeMap<Long, T> nodes;
- private List<T> shards; //节点碎片
- private final int NODE_NUM = 10; // 每个机器节点关联的虚拟节点个数
- public Shard(List<T> shards) {
- this.shards = shards;
- init();
- }
- private void init() {
- nodes = new TreeMap<Long, T>();
- for (int i = 0; i < shards.size(); i++)
- { // 遍历真实节点
- final T shardInfo = shards.get(i);
- for (int n = 0; n < NODE_NUM; n++)
- {
- // 真实节点关联虚拟节点,真实节点是VALUE;
- nodes.put((long) Hash("SHARD-" + i + "-NODE-" + n), shardInfo);
- }
- System.out.println(shardInfo);
- }
- }
- public T getShardInfo(String key) {
- SortedMap<Long, T> tail = nodes.tailMap((long) Hash(key));
- if (tail.size() == 0) {
- return nodes.get(nodes.firstKey());
- }
- //找到最近的虚拟节点
- return tail.get(tail.firstKey());
- }
- /**
- * 改进的32位FNV算法,高离散
- *
- * @param string
- * 字符串
- * @return int值
- */
- public static int Hash(String str)
- {
- final int p = 16777619;
- int hash = (int) 2166136261L;
- for (byte b : str.getBytes())
- hash = (hash ^ b) * p;
- hash += hash << 13;
- hash ^= hash >> 7;
- hash += hash << 3;
- hash ^= hash >> 17;
- hash += hash << 5;
- return hash;
- }
- }
到这里就完了,是不是很简单,下面来测试下:
- public class Test
- {
- /**
- * @param args
- */
- public static void main(String[] args)
- {
- List<Cache> myCaches=new ArrayList<Cache>();
- Cache cache1=new Cache();
- cache1.name="COMPUTER1";
- Cache cache2=new Cache();
- cache2.name="COMPUTER2";
- myCaches.add(cache1);
- myCaches.add(cache2);
- Shard<Cache> myShard=new Shard<Cache>(myCaches);
- Cache currentCache=myShard.getShardInfo("info1");
- System.out.println(currentCache.name);
- // for(int i=0;i<20;i++)
- // {
- // String object=getRandomString(20);//产生20位长度的随机字符串
- // Cache currentCache=myShard.getShardInfo(object);
- // System.out.println(currentCache.name);
- // }
- }
- public static String getRandomString(int length) { //length表示生成字符串的长度
- String base = "abcdefghijklmnopqrstuvwxyz0123456789";
- Random random = new Random();
- StringBuffer sb = new StringBuffer();
- for (int i = 0; i < length; i++) {
- int number = random.nextInt(base.length());
- sb.append(base.charAt(number));
- }
- return sb.toString();
- }
- }
我们有两台设备,computer1和computer2,第一次初始化要构建一个2的32次方的环,并往上面放设备。这个环由改进的FNV算法实现。位置也由hash算法确定。
但我们只有两台设备,很明显在环上会分布不均匀(这个就不解释了,网上很多资料)。于是我们每台设备增加10个虚拟设备。
最后分布如下:
- <SPAN style="COLOR: #003300">-1561290727=Hash.Cache@10f11b8,
- -1083588870=Hash.Cache@10f11b8,
- -697149481=Hash.Cache@10f11b8,
- -253517545=Hash.Cache@10f11b8,
- 397383558=Hash.Cache@10f11b8,
- 1078505027=Hash.Cache@10f11b8,
- 1810977445=Hash.Cache@10f11b8,
- 1844081498=Hash.Cache@10f11b8,
- 2004894833=Hash.Cache@10f11b8,
- 2051863688=Hash.Cache@10f11b8</SPAN>
-2147483648到2147483647之间是不是比较均匀,这是java的,如果是c#的就是0~2的32次方。我们hash计算出KEY值为2049553054,然后顺时针找到最近的位置,即为
结果我们定位到了COMPUTER1
最好我们要看看平衡性如何:取消上面注释的代码,循环20次,得到结果如下:
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER1
COMPUTER1
COMPUTER2
COMPUTER2
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER1
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
大家可以自己取试试,
FNV哈希算法是一种高离散性的哈希算法,特别适用于哈希非常相似的字符串,例如:URL,IP,主机名,文件名等。
以下服务使用了FNV:
1、calc
2、DNS
3、mdbm key/value查询函数
4、数据库索引hash
5、主流web查询/索引引擎
6、高性能email服务
7、基于消息ID查询函数
8、auti-spam反垃圾邮件过滤器
9、NFS实现(比如freebsd 4.3, linux NFS v4)
10、Cohesia MASS project
11、Ada 95的spellchecker
12、开源x86汇编器:flatassembler user-defined symbol hashtree
13、PowerBASIC
14、PS2、XBOX上的文本资源
15、非加密图形文件指纹
16、FRET
17、Symbian DASM
18、VC++ 2005的hash_map实现
19、memcache中的libketama
20、 PHP 5.x
21、twitter中用于改进cache碎片
22、BSD IDE project
23、deliantra game server
24、 Leprechaun
25、IPv6流标签
相关推荐
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希,consistent hashing。 算法入门必备 清晰版本,非扫描。
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1]),设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中...
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
针对MR过程的减少阶段,提出了一种虚拟分区一致性哈希(VPCH)算法,以实现工作分配的权衡。 根据结果,使用我们的方法可以减少带有或不带有MJR(mapreduce.job.reduce.slowstart.completedmaps)参数集的任务...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
该存储库提供了常用分布式技术的演示,例如一致性哈希,分布式锁,分布式事务,领导者选举等。 技术 模块 地位 评论 一致性哈希 一致性哈希 完毕 分散式锁 分布式锁 正在做 分散式交易 分布式交易 完毕 共识算法 ...
一致的散列 一致性哈希是用于存储数据多个实例的算法和数据结构。 在这个项目中,我们的工作标题在此期间 信号处理 散列 网络