`

分布式系统下的哈希一致性算法设计

阅读更多

本文涉及:普通哈希算法存在的问题,分布式系统的哈希一致性算法,哈希一致性算法中的数据倾斜问题

我们知道,在分布式系统中当数据量无法使用单机进行存储时,最简单粗暴的方法就是水平扩展:加机器,搞集群。

然而所有的集群模式都会面临一个数据存放的问题:即一个集群有多台机器,我们怎么知道这次的数据应该放在哪个机器上呢?这次的数据放到了一台机器上我下一次读取的时候能保证还来这台机器上找么?

假如当前我们有一个Redis集群,共5个节点对外提供服务


Hash取模

最开始的解决方案就是首先给5台机器分别编号:1、2、3、4、5
当对一个数据进行操作时首先计算key的hash然后对机器数量5进行取余,得出的余数就是需要放置的机器的编号。

1
key应该放置的机器编号=hash(key) % 5

这个方案完美解决了文章开始提到的两个问题,但是大家都知道,程序员的智力是没有上限,当然主要是因为问题逼的:

如果其中一台机器宕机了、或者新增了服务器,则整个集群所有的数据都需要重新计算位置,这个过程简直不要太痛苦。


一致性Hash

既然出现了问题,聪明的程序员很快就想到了解决方案:一致性哈希算法
1

如上图所示,程序员们把所有的机器模拟成了一个虚拟的哈希环,然后设计了一个空间的大小,这个空间被平均分配到了所有机器的中间。当需要对一个key操作时,同样进行进行取模运算,只不过这里的模不再是机器数量而是空间大小,然后根据得出的结果,去离结果顺时针最近的一个节点上操作key。

例如:当一个集群有5个节点、空间大小被设置为500的时候,当要设置一个key的hash值为601时。首先会对key的hash进行取余,601%500 结果为101,然后根据结果101顺时针查找最近的节点找到了192.168.1.3。
同理,设置另一个key,先算hash,假如是888,则首先取余得出结果388然后得出节点192.168.1.5。

使用Hash一致性的时候如果遇到了节点宕机或者新增服务器的情况下可就简单的多了:
1

节点宕机,只需要把宕机节点的数据迁移到顺时针的下一个服务器上
1

新增节点仅仅需要迁移逆时针的第一台服务器的部分数据


数据倾斜

一致性哈希算法完美的解决了普通的哈希算法的问题,但是呢,没有十全十美的算法,一致性哈希算法同样存在一些问题。由上方的示例我们可以看出来,当集群内扩缩容次数多了以后,数据很容易出现不均匀的情况,有的机器负责了大半的空间,而有的机器仅仅负责一点点空间。这个问题有一个名词,数据倾斜:
1

为了解决数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即将每一个服务节点都计算为多个虚拟节点,避免单个节点持有连续的大空间:
1

推荐阅读

  1. SpringCloud学习系列汇总
  2. 多线程面试必备基础知识汇总
  3. Java集合源码分析汇总-JDK1.8
  4. Linux常用命令速查-汇总篇

博客所有文章首发于公众号《Java学习录》转载请保留
扫码关注公众号即可领取2000GJava学习资源

1

0
0
分享到:
评论

相关推荐

    一致性哈希算法在分布式系统中的应用.pdf

    一致性哈希算法是一种在分布式系统中用于解决数据分发和负载均衡问题的算法。随着互联网技术的快速发展,分布式...在设计和实现分布式系统时,理解并有效利用一致性哈希算法,能够极大地优化系统的架构,降低运维成本。

    分布式存储系统中改进的一致性哈希算法.pdf

    一致性哈希算法是在分布式系统中广泛使用的一种数据定位算法,尤其适用于分布式缓存系统,如Redis。传统的哈希算法在分布式存储系统中有一个缺点,即当系统扩展或缩减节点时,数据的迁移量过大。一致性哈希算法通过...

    分布式存储系统中一致性哈希算法的研究.pdf

    一致性哈希算法由David Karger等人在1997年提出,它是一种特殊的哈希算法,主要用于分布式系统中实现负载均衡。与传统的哈希算法不同,一致性哈希算法在处理节点增减时,能够最小化重新分配数据的数量,从而提高系统...

    基于一致性哈希算法的分布式数据库高效扩展方法.pdf

    一致性哈希算法最初由麻省理工学院的K等人提出,并被广泛应用于分布式系统中,以解决节点动态变化时数据一致性问题。其核心思想是通过引入哈希环,将数据对象均匀分布在哈希环上的不同节点中,以此降低节点变更对...

    一致性哈希算法及其在分布式系统中的应用

    ### 一致性哈希算法及其在分布式系统中的应用 #### 摘要 一致性哈希算法是一种用于解决分布式系统中节点动态变化导致的数据重新分布...在现代分布式系统的设计和实践中,一致性哈希算法已成为不可或缺的核心技术之一。

    Python-分布式系统中常用的的算法python实现

    在分布式系统领域,为了保证高可用性、可扩展性和数据一致性,往往需要运用一系列特定的算法。本项目“Python-分布式系统中常用的的算法python实现”聚焦于将这些算法用Python语言进行实践,同时提供了实用的工具类...

    基于一致性哈希算法的分布式数据库高效扩展方法研究.pdf

    总的来说,本文的研究提供了一种基于一致性哈希的高效数据库扩展方案,通过预留子分区识别位和CRC32校验,解决了传统方法中的效率问题,降低了扩展成本,对于分布式系统的扩展性和稳定性有着重要的实际意义。...

    基于C# 实现的一致性哈希算法

    在传统的哈希算法中,如果增加或减少服务器节点,会导致大量数据重新分配,而一致性哈希算法通过特殊的设计,使得节点的增减对整个系统的影响降到最低。在C#环境下实现一致性哈希,可以应用于如分布式缓存、负载均衡...

    一致性哈希算法源码 Ketama一致性hash算法源码

    总的来说,Ketama一致性哈希算法是分布式系统中解决数据分布问题的重要工具,通过巧妙的设计实现了在节点变化时尽可能少的数据迁移,提高了系统的稳定性和扩展性。通过深入理解并运用这种算法,我们可以构建更加健壮...

    一致性哈希算法C版实现

    一致性哈希算法是一种在分布式系统中解决数据分片和负载均衡问题的算法,它主要解决了在动态添加或移除节点时,尽可能少地改变已经存在的数据分布。在云计算和大数据处理领域,一致性哈希被广泛应用,例如在分布式...

    深入探讨一致性哈希:分布式系统中的应用与优势

    本文将详细介绍一致性哈希的概念、原理以及在分布式系统中的应用。 一致性哈希为分布式系统提供了一种高效且灵活的数据分布机制。通过本文的介绍,我们学习了一致性哈希的概念、原理、应用场景以及如何实现它。一致...

    Mycat一致性哈希分片算法1

    * 高效的数据分布:Mycat的一致性哈希分片算法可以将数据分布式存储在多个数据库节点中,提高数据存取效率和系统可扩展性。 * 轻松的维护和管理:Mycat的一致性哈希分片算法可以轻松地添加或删除数据库节点,简化了...

    分布式哈希表和一致性哈希

    分布式哈希表(Distributed Hash Table,简称DHT)是一种在分布式系统中用以实现大规模数据存储和快速定位的算法。DHT通过分布式的方式将数据以键值对的形式存储在各个节点上,从而实现无需中心服务器的高效数据管理...

    分布式系统 概念与设计 习题答案(完整版).

    例如,Paxos、Raft等一致性算法用于在分布式环境中保证数据的一致性。 4. 分布式事务处理:ACID(原子性、一致性、隔离性、持久性)原则是分布式事务处理的基础。CAP理论指出,一个分布式系统无法同时满足一致性、...

    解决分布式数据插入数据库~一致性hash算法

    一致性哈希算法(Consistent Hashing)是一种常用于分布式系统中的数据分片策略,它有效地解决了数据在多台服务器间均匀分布的问题,同时减少了因节点加入或离开时的数据迁移成本。 首先,一致性哈希的基本原理是将...

    一致性哈希算法演示.rar

    在大型分布式系统中,例如缓存系统、分布式数据库等,一致性哈希能够确保当节点加入或离开时,尽可能少的数据需要迁移,从而保持系统的稳定性。此算法由麻省理工学院的研究人员在1997年提出,主要应用于分布式存储和...

    Mycat一致性哈希分片算法.zip

    《Mycat一致性哈希分片算法详解》 在分布式数据库系统中,数据分片是实现高可用性和可扩展性的重要手段。Mycat作为一款开源的分布式数据库中间件,其核心特性之一就是数据分片策略,而一致性哈希分片算法在其中扮演...

    分布式radius系统高可用负载均衡算法的设计与实现.pdf

    它是在传统的哈希算法基础上发展起来的,特别适用于分布式系统中的动态资源调整。在RADIUS系统中,一致性哈希能够确保即使服务器数量发生变化,大部分接入请求仍能保持在原有的服务器上,避免了大量请求的重新分配,...

Global site tag (gtag.js) - Google Analytics