`
xubindehao
  • 浏览: 243311 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

一致性hash

阅读更多

协议简介

  

 

一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

编辑本段 哈希算法

  一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件:

平衡性(Balance)

  平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

  单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。   简单的哈希算法往往不能满足单调性的要求,如最简单的线性哈希:   x → ax + b mod (P)

  

 

在上式中,P表示全部缓冲的大小。不难看出,当缓冲大小发生变化时(从P1到P2),原来所有的哈希结果均会发生变化,从而不满足单调性的要求。   哈希结果的变化意味着当缓冲空间发生变化时,所有的映射关系需要在系统内全部更新。而在P2P系统内,缓冲的变化等价于Peer加入或退出系统,这一情况在P2P系统中会频繁发生,因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够避免这一情况的发生。

分散性(Spread)

   在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有 可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到 不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。   负载(Load)   负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。   从表面上看,一致性哈希针对的是分布式缓冲的问题,但是如果将缓冲看作P2P系统中的Peer,将映射的内容看作各种共享的资源(数据,文件,媒体流等),就会发现两者实际上是在描述同一问题。   路由算法   在一致性哈希算法中,每个节点(对应P2P系统中的Peer)都有随机分配的ID。在将内容映 射到节点时,使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的, 比如从0000到9999的整数集合。   根据键值存储内容时,内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容,系统中有ID为1000,1010,1100的节点,该内容将被映射到1000节点。   为了构建查询所需的路由,一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小 的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP地址)。当节点需要查找内容时,就可以根据内容的键值决定向上行或下行节点发起查询请 求。收到查询请求的节点如果发现自己拥有被请求的目标,可以直接向发起查询请求的节点返回确认;如果发现不属于自身的范围,可以转发请求到自己的上行/下 行节点。   为了维护上述路由信息,在节点加入/退出系统时,相邻的节点必须及时更新路由信息。这就要求节 点不仅存储直接相连的下行节点位置信息,还要知道一定深度(n跳)的间接下行节点信息,并且动态地维护节点列表。当节点退出系统时,它的上行节点将尝试直 接连接到最近的下行节点,连接成功后,从新的下行节点获得下行节点列表并更新自身的节点列表。同样的,当新的节点加入到系统中时,首先根据自身的ID找到 下行节点并获得下行节点列表,然后要求上行节点修改其下行节点列表,这样就恢复了路由关系。

编辑本段 结论

  一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。   但是一致性哈希的路由算法尚有不足之处。在查询过程中,查询消息要经过O(N)步(O(N)表 示与N成正比关系,N代表系统内的节点总数)才能到达被查询的节点。不难想象,当系统规模非常大时,节点数量可能超过百万,这样的查询效率显然难以满足使 用的需要。换个角度来看,即使用户能够忍受漫长的时延,查询过程中产生的大量消息也会给网络带来不必要的负荷。

分享到:
评论

相关推荐

    C++实现一致性hash算法

    一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)

    一致性Hash简单实现

    一致性哈希(Consistent Hashing)是一种分布式哈希表(DHT)的算法,它主要应用于分布式缓存、负载均衡等场景,旨在解决在动态扩展或收缩系统规模时,尽量减少数据迁移的问题。在这个简单的实现中,我们将探讨如何...

    一致性Hash算法的原理及实现

    ### 一致性Hash算法的原理及实现 #### 一、引言 一致性Hash算法是一种用于解决分布式环境下数据存储和检索问题的重要技术。它最初由David Karger等人在1997年的论文《Consistent Hashing and Random Trees: ...

    C/C++ 一致性hash算法

    一致性哈希算法是一种分布式哈希(Distributed Hash Table, DHT)技术,它在处理大量数据分布到多个节点上时,能保持较好的均衡性和可扩展性。在C/C++编程中,一致性哈希通常用于构建分布式系统,如负载均衡、缓存...

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

    一致性哈希算法是一种分布式哈希(Distributed Hash Table, DHT)技术,旨在解决在分布式环境中数据分布不均匀的问题。Ketama算法是基于一致性哈希的一种优化实现,由Last.fm公司的Simon Willison提出,其目标是在...

    memcache分布式一致性hash

    分布式一致性哈希是一种解决在分布式缓存系统中如何高效、稳定地分配数据的算法,尤其在Memcache等缓存服务中广泛应用。它旨在确保当缓存集群中的节点增减时,对现有数据的映射影响最小,从而降低数据迁移和系统压力...

    基于一致性Hash的分布式海量分子检索模型.pdf

    【基于一致性Hash的分布式海量分子检索模型】 在大数据环境下,传统的通用图匹配搜索方法面临着效率低下和无法快速定位折射率数据的问题。为了应对这一挑战,本文提出了一种基于一致性Hash的分布式海量分子检索模型...

    搞懂分布式技术11:分布式session解决方案与一致性hash.docx

    ### 分布式Session解决方案与一致性Hash详解 #### 一、问题背景及提出 在现代互联网应用中,随着用户量的增长和服务需求的增加,单一服务器往往难以满足高性能、高可用性的需求,因此分布式系统逐渐成为主流架构之...

    利用一致性hash把不同分类的数据存储到redis集群,_把不同的分类作为一致性hash的key_h

    利用一致性hash把不同分类的数据存储到redis集群,_把不同的分类作为一致性hash的key_hashConsistent-redis

    一致性hashjava实现

    一致性哈希(Consistent Hashing)是一种分布式哈希算法,主要应用于分布式缓存、负载均衡等领域,以解决在分布式环境中动态添加或删除节点时,尽可能少地改变已有的哈希映射关系。在这个Java实现中,我们看到的是...

    对一致性Hash算法,Java代码实现的深入研究1

    【一致性Hash算法】是一种分布式系统中用于负载均衡的哈希算法。它的主要目的是解决当服务节点增加或减少时,能够尽量少地改变已有的请求分配,以保持系统的稳定性。在传统的哈希算法中,增加或删除一个服务器可能...

    一致性hash算法简介.pdf

    一致性hash算法简介

    一致性hash算法简介加C++实现

    一致性hash算法简介加C++实现

    基于go语言实现的分布式缓存系统源码+项目说明(以键值对的形式存储数据,一致性hash算法选择存储节点).zip

    基于go语言实现的分布式缓存系统源码+项目说明(以键值对的形式存储数据,一致性hash算法选择存储节点,Protobuf通信协议编解码。用户输入查询请求后,会优先在缓存系统查询,查不到则使用回调函数去源数据库查询,...

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

    为了解决这个问题,可以采用跳数法(Jump Consistent Hash)或者更高级的一致性哈希变体,如Ketama或libketama。哈希冲突则可以通过开放寻址、链地址法等方法来解决。 此外,一致性哈希算法在分布式缓存如Memcached...

    SpringBoot_shardDB_shardTable:SpringBoot集成Sharding-JDBC实现分库分表,自定义分片算法,基于一致性hash算法,易于扩容

    一致性Hash算法,易于扩容;添加了 单元测试,使用Spring提供的RestTemplate调用RestFul风格的API接口;整合了 quartz 定时任务框架 ,并进行了封装,只需在构建完定时任务Job类后,在 application-quartz....

    libconhash一致性hash

    一致性哈希(Consistent Hashing)是一种在分布式系统中解决数据分片问题的算法,它使得在节点加入或离开时,只需要少量的数据迁移就能保持系统的稳定性。在这个上下文中,`libconhash`是一个专门实现一致性哈希的...

Global site tag (gtag.js) - Google Analytics