`
winnerbao
  • 浏览: 10409 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

简介一致性Hash(Consistent Hashing)

 
阅读更多
[介绍]
一致性Hash(Consistent Hashing)被应用在很多地方,如LVS, 缓存(memcache, redis)等等.
 
[Ref 1],与 [Ref 2]已经给出了非常清楚明白的解释,我也是参考他们的。其他相关的文章更是多得汗牛充栋。
我写这个小短文(以我自己的语言重新组织)的目的是为了加深印象,以及稍加补充我觉得更加好理解的解释。
 
[现实问题]
问题:对key使用普通hash方法产生hashcode,以决定该key分配到那些缓存节点上。当减少(或者增加)节点数量时,将会倒置几乎所有的key都将重新分配到其他的节点上。因为hash的mod值从N,变成了N-1(or N+1). 譬如原来映射到节点 X, 则之后映射到X-1 (or X+1). 进而原有的缓存内容全部失效。 这将引起系统功能的剧烈变化。
 
 
[为什么一致性Hash]
一致性hash中,针对 key 和 缓存节点 都生成hash code(0 ~ 2^32-1)。将这些hash code映射到一个环上。这样,按照以顺时针方向,key距离那个节点比较近,就分配到哪个节点上。
这样,增加、减少节点则只对换上相邻的key产生影响。其他的key仍然还在原有节点上。


 
此图来自 [Ref 1]
 
 
[深入]
1. 平衡性
只是映射节点和key的话,可能有些节点load很大,其他确很小。引起所谓的,不平衡问题。为了缓解(注意:缓解,而非彻底解决)这个问题,引入虚拟节点的概念。每个物理节点,对应若干虚拟节点。使用虚拟节点的hashcode映射到环上,注意:同一物理节点的虚拟节点在换上不相邻。因为有了更多的“节点”在环上、而且物理节点都打散了,则key的分布必然会更平均一些。
[Ref 1]中也描述了
 
2. 判断该算法好坏的四个特性
- 平衡性 Balance    "哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。" [Ref 2]
- 单调性 Monotonicity。 What:已缓存到NodeA中的内容,由于增加新节点NodeX,可能不得不映射到新的节点上。只能映射到原有NodeA或者新的NodeX中。而不能映射到其他Node上。How: 一致性Hash的圆环很简单的保证了这点。
- 分散性 Spread。 相同内容被cache到不同节点上、导致低存储效率的程度。BY:什么时候会曹成重复cache呢?谁给个实际的例子? [Ref 2]说“在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分”, 为啥不能看到所有缓冲?
- 负载 Load - BY:无法理解[Ref 2]中说解释的Load。
[Ref 2]中给出了比较好的解释。但是需要认真读才行。读之前,请理解一致性hash。读的时候,请结合一致性hash。
 
3. 一致性哈希算法有多种具体的实现,包括Chord算法KAD算法等实现
 
Reference 
 
2. 一致性hash算法简介
  • 大小: 18.5 KB
分享到:
评论

相关推荐

    一致性Hash(Consistent Hashing)原理剖析1

    一致性哈希(Consistent Hashing)是一种用于分布式系统的哈希算法,主要应用于分布式缓存、分布式数据库等场景,目的是在节点动态增减时保持哈希表的稳定性,从而最小化数据迁移的影响。它解决了传统哈希取模方法在...

    一致性哈希算法 consistent hashing

    在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。

    Ketama一致性Hash算法(含Java代码) 1

    一致性哈希算法(Consistent Hashing)是一种在分布式系统中平衡数据分布的策略,尤其适用于缓存服务如Memcached或Redis。它的核心思想是通过哈希函数将对象映射到一个固定大小的环形空间中,然后将服务器也映射到这个...

    一致性Hash简单实现

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

    consistent-hash:一致性哈希工具类 Implementing Consistent Hashing in Kotlin

    一致性哈希 consistent-hash Implementing Consistent Hashing in Kotlin Java Kotlin实现的一致性哈希工具 简单示例 val a = HostPortPhysicalNode("A", "192.169.1.1", 8080) val b = HostPortPhysicalNode("B", ...

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

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

    fly-arch:分布式架构consistent-hashing(一致性hash) http

    #fly-archflylib创立的各种常见的架构技术内容列表cassandra-demo cassandra数据库的入门编程consistent-hash Java implementation of consistent-hashing基于java的一致性hash的实现一致性hash(consistent-hashing)...

    Jump-Consistent-Hashing-Evaluation:对一致性哈希的评估,尤其是 Google 的 Jump Consistent Hashing

    跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。

    一致性hashjava实现

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

    Consistent-Hashing:Consistent Hashing 一致哈希

    一致性哈希(Consistent Hashing)是一种分布式哈希算法,主要应用于分布式缓存、负载均衡等领域,例如在Redis、Memcached等系统中广泛使用。它解决了传统哈希算法在节点动态增减时导致的大量数据迁移问题。在Java中...

    ConsistentHash(Ketama)

    一致性哈希(Consistent Hashing)是一种分布式哈希(Distributed Hash Table,DHT)算法,主要用于解决在分布式系统中的数据存储和检索问题。在云计算、缓存系统(如Redis、Memcached)以及负载均衡等领域广泛应用...

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

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

    Go-Consistent-hashing:Go中的散列环实现

    一致性哈希(Consistent Hashing)是一种在分布式系统中解决数据分片问题的算法,它在Go语言中的实现对于构建可扩展且容错的服务至关重要。在Go开发中,尤其是在涉及分布式缓存、负载均衡等场景下,一致性哈希能够...

    lua-consistent-hash:lua中实现的一致性哈希

    lua 一致性哈希基于 yaoweibin 的一致性哈希分支( )在 lua 中重新实现一致性哈希用法 local chash = require " chash "chash. add_upstream ( " 192.168.0.251 " )chash. add_upstream ( " 192.168.0.252 " )chash...

    一致性Hash算法1

    一致性哈希算法(Consistent Hashing)是一种特殊的哈希算法,设计目的是为了在分布式缓存系统中解决节点动态增减时导致的键值映射大量变更的问题。它最早在1997年的论文《Consistent hashing and random trees》中被...

    一致性hash算法1

    一致性哈希算法(Consistent Hashing)是一种特殊的哈希算法,设计目的是为了在分布式缓存系统中解决节点动态增减时导致的数据分布不均问题。该算法最早在1997年的论文《Consistent Hashing and Random Trees》中被...

Global site tag (gtag.js) - Google Analytics