consistent hashing由来?
最初由Karger等人设计。在麻省理工学院用作分布式缓存,现在已经扩大到其他领域。
它被设计来解决hash的什么问题?
假设有m个对象需要被映射到n个node上,简单hash就求余映射hash(object)%n->node,就大致均匀的分布到n个node上了。可是问题在于如果n发生变化(多了或者少了),就必须重新计算保存对象存放到node,这代价未免有点大。consistent hashing就是用来解决这个问题。
一般hash的问题在于,映射关系计算是个死的东西。所以consistent hashing就是要把对象和这个node和映射关系搞活一点。那么具体是怎么搞活的?
假设有个ring(环),hash(object)和hash(node)都在投影到这个ring上。
映射关系变成:hash(object)->hash(node),
->(映射关系):查找用的是在ring上顺时针查找,找到最近的hash(node),建立映射关系。
图大概就是这样子的:
如果有个node被咔嚓剪了一个或者咔嚓多了一个,想象下hash(object)像精子一样顺时针沿着ring游动去找他的小伙伴,碰到最近的hash(node)就结合了。node不是很少的话,基本上只要很少的object需要重新寻找亲密小伙伴。
图看着挺好看挺均匀挺和谐的,可是如果我只有两个node,而且好死不死,hash(node)后的值在ring上又紧挨着。。咋整?
问题问的真好
,node少不要怕,在天朝,啥都不知道,造假还有不知道的吗?对,就是造假,明明只有2个node,我们就整他100~1000个(假的成本毕竟低么),如果你胆大不怕查,你也可以多造点。真的node就叫node,假的就叫virtual node(简称vnode)。然后再维护个vnode->node就可以了。
vnode搞越多,越均匀,越好么?
由于查找object所在的vnode需要O(n)步(n为vnode个数),运气不好,查到最后一个才找到,那就悲催了。
consistent hashing可以用来干嘛呢?
大家都知道的分布式cache中常用这个算法。
还有在分布式文件系统中,为了使文件更加均匀的分布和减少node更变带来的影响,也常常会用到。
我想在分布式任务调度系统中,用来分发任务到zookeeper的znode上。这样加个znode或者挂掉个znode,也不用怕了。似乎和consistent hashing解决的典型问题是一样的。
- 大小: 31.6 KB
分享到:
相关推荐
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希,consistent hashing。 算法入门必备 清晰版本,非扫描。
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1]),设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中...
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
针对MR过程的减少阶段,提出了一种虚拟分区一致性哈希(VPCH)算法,以实现工作分配的权衡。 根据结果,使用我们的方法可以减少带有或不带有MJR(mapreduce.job.reduce.slowstart.completedmaps)参数集的任务...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
该存储库提供了常用分布式技术的演示,例如一致性哈希,分布式锁,分布式事务,领导者选举等。 技术 模块 地位 评论 一致性哈希 一致性哈希 完毕 分散式锁 分布式锁 正在做 分散式交易 分布式交易 完毕 共识算法 ...
一致的散列 一致性哈希是用于存储数据多个实例的算法和数据结构。 在这个项目中,我们的工作标题在此期间 信号处理 散列 网络