摘要
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接下来会对这个算法进行相对详细的描述,并讨论一些如虚拟节点等与此算法应用相关的话题。
分布式缓存问题
假设我们有一个网站,最近发现随着流量增加,服务器压力越来越大,之前直接读写数据库的方式不太给力了,于是我们想引入Memcached作为缓存机制。现在我们一共有三台机器可以作为Memcached服务器,如下图所示。
很显然,最简单的策略是将每一次Memcached请求随机发送到一台Memcached服务器,但是这种策略可能会带来两个问题:一是同一份数据可能被存在不同的机器上而造成数据冗余,二是有可能某数据已经被缓存但是访问却没有命中,因为无法保证对相同key的所有访问都被发送到相同的服务器。因此,随机策略无论是时间效率还是空间效率都非常不好。
要解决上述问题只需做到如下一点:保证对相同key的访问会被发送到相同的服务器。很多方法可以实现这一点,最常用的方法是计算哈希。例如对于每次访问,可以按如下算法计算其哈希值:
h = Hash(key) % 3
其中Hash是一个从字符串到正整数的哈希映射函数。这样,如果我们将Memcached Server分别编号为0、1、2,那么就可以根据上式和key计算出服务器编号h,然后去访问。
这个方法虽然解决了上面提到的两个问题,但是存在一些其它的问题。如果将上述方法抽象,可以认为通过:
h = Hash(key) % N
这个算式计算每个key的请求应该被发送到哪台服务器,其中N为服务器的台数,并且服务器按照0 – (N-1)编号。
这个算法的问题在于容错性和扩展性不好。所谓容错性是指当系统中某一个或几个服务器变得不可用时,整个系统是否可以正确高效运行;而扩展性是指当加入新的服务器后,整个系统是否可以正确高效运行。
现假设有一台服务器宕机了,那么为了填补空缺,要将宕机的服务器从编号列表中移除,后面的服务器按顺序前移一位并将其编号值减一,此时每个key就要按h = Hash(key) % (N-1)重新计算;同样,如果新增了一台服务器,虽然原有服务器编号不用改变,但是要按h = Hash(key) % (N+1)重新计算哈希值。因此系统中一旦有服务器变更,大量的key会被重定位到不同的服务器从而造成大量的缓存不命中。而这种情况在分布式系统中是非常糟糕的。
一个设计良好的分布式哈希方案应该具有良好的单调性,即服务节点的增减不会造成大量哈希重定位。一致性哈希算法就是这样一种哈希方案。
相关推荐
#资源达人分享计划#
#资源达人分享计划#
#资源达人分享计划#
#资源达人分享计划#
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
#资源达人分享计划#
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
IMKVS系统使用一致性哈希来决定在何处存储目标。一致性哈希使用起来方法简单,但可能引起网络负载的不平衡。为了提高IMKVS的缓存性能,提出一种软件定义网络中利用IMKVS结合NFV的分布式网络负载均衡策略。该策略包含...
与传统的一致性哈希算法相比,分布式数据具有更多的平衡。多丽丝建筑高性能Doris提供了高性能的KV访问,并具有低延迟和高吞吐量。 通常的数据访问时间少于4毫秒。可扩展性Doris旨在支持多达2000个以上节点的大规模...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
很多哈希算法都能够满足这一条件。单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
一致性哈希(Consistenthash)很好的解决了这个问题,当节点发生变化时,只会影响到部分数据,而且永远可以找到一个提供服务的节点。对于数据库Sharding的架构,Consistenthash并不十分适合,我们采用了一种新的hash...
+ Dubbo泛化调用的地址为一致性哈希负载均衡算法计算所得 + 解决了自定义协议在传输中导致的粘包、拆包问题 + 群聊批量ACK处理,避免因创建过多的超时计时器导致的压力过大 + 利用leaf-sno 【备注】 1、该资源内项目...
本文将粗略讲述一下Hash算法的概念特性,里边会结合分布式系统负载均衡实例对Hash的一致性做深入探讨。另外,探讨一下Hash算法在海量数据处理方案中的通用性。最后,从源代码出发,具体分析一下Hash算法在MapReduce...