精华内容
下载资源
问答
  • 采用固定哈希算法平衡负载在大规模的缓存应用中,应运而生了分布式缓存系统。key-value如何均匀的分散到集群中?...随着系统访问压力的增长,缓存系统不得不通过增加机器节点的方式提高集群的相应速...

    采用固定哈希算法平衡负载

    在大规模的缓存应用中,应运而生了分布式缓存系统。key-value如何均匀的分散到集群中?最常规的方式莫过于hash取模的方式。比如集群中可用机器适量为N,那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。但是在一些高速发展的web系统中,这样的解决方案仍有些缺陷。随着系统访问压力的增长,缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式,在增加机器节点的这一时刻,大量的缓存命不中,缓存数据需要重新建立,甚至是进行整体的缓存数据迁移,瞬间会给DB带来极高的系统负载,设置导致DB服务器宕机。

    如果不是缓存数据,而是持久化的数据,那么当扩容的时候,绝大部分数据都要迁移(取模的基数N变化了),这也是不能忍受的。

    一致性哈希平衡负载

    引入一致性哈希,解决以上增减机器导致负载瞬间整体增大问题

    通过在整数范围内负责各区域的方式,节点负责区域的负载不会随着增减节点发生大规模的迁移

    但是最简单的一致性哈希,在增减物理机的时候,似乎要增加一倍节点或减去一半节点才能保证各个节点的负载均衡

    虚拟节点对一致性哈希的改进

    对于一致性哈希的负载分布不平均问题,所以提出:虚拟节点对一致性哈希的改进

    4个物理节点可以变成很多个虚拟节点,每个虚拟节点支持连续的哈希环上的一段。而这时如果加入一个物理节点,就会相应加入很多虚拟节点,这些新的虚拟节点是相对均匀地插入到整个哈希环上,这样,就可以很好的分担现有物理节点的压力了;如果减少一个物理节点,对应的很多虚拟节点就会失效,这样,就会有很多剩余的虚拟节点来承担之前虚拟节点的工作,但是对于物理节点来说,增加的负载相对是均衡的。

    所以可以通过一个物理节点对应非常多的虚拟节点,并且同一个物理节点的虚拟节点尽量均匀分布的方式来解决增加或减少节点时负载不均衡的问题。

    至于一个物理节点对应多少的虚拟节点才能达到比较好的均衡效果,有一个图

    c5c9681f127c270bb278a51e9804bb6f.png

    x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale),y轴是实际物理服务器数,可以看出,当物理服务器的数量很小时,需要更大的虚拟节点,反之则需要更少的节点,从图上可以看出,在物理服务器有10台时,差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。

    映射表与规则自定义计算方式

    映射表示根据分库分表字段的值的查表法来确定数据源的方法,一般用于对热点数据的特殊处理,或者在一些场景下对不完全符合规律的规则进行补充。

    可以通过自定义函数实现来计算最终的分库,举例来说,假设根据id取模分成了4个库,但是对于一些热点id,我们希望将其独立到另外的库,那么通过类似下面的表达式可以完成:

    if (id in hotset) {

    return nodes;

    }

    return hash(id);

    参考:

    http://www.iteye.com/topic/611976

    http://www.iteye.com/topic/684087

    《大型网站系统与Java中间件实践》

    http://blog.csdn.net/sparkliang/article/details/5279393

    展开全文
  • 一致性hash算法时发现虚拟节点是个好东西,但同时也有缺点,需要结合场景使用。此处不做详细排版和铺垫,不了解一致性hash的可以先去查查,此处仅做抛砖引玉。虚拟节点的存在可以使hash环中的节点命中率变的均衡。...

    做一致性hash算法时发现虚拟节点是个好东西,但同时也有缺点,需要结合场景使用。

    此处不做详细排版和铺垫,不了解一致性hash的可以先去查查,此处仅做抛砖引玉。

    虚拟节点的存在可以使hash环中的节点命中率变的均衡。

    虚拟节点越多,分布越均匀。

    但会带来数据牺牲,真实节点增加或者减少时

    由于虚拟节点数量剧烈变化,数据的重新分配可能会影响到更多的真实节点。

    因为有可能所有虚拟节点的下一个节点列表覆盖了其他所有真实节点。

    所以,如果key与服务无关,可以适当调大这个值,达到良好的均衡效果

    服务真实节点较多、数量变化频繁时,适当减少或者不设置,以减少数据迁移带来的影响,提高系统整体的可用性

    可参考下图--图片来源

    具体做法

    当服务挂掉时,刷新 hash环,以适应新的环境

    数据迁移

    服务挂掉时,数据丢失,新数据走到下一个节点。

    服务增加或恢复时,将新服务的每个虚拟节点的下一个节点中的数据遍历一遍,进行迁移,其他节点不受影响

    总结

    虚拟节点越多 在服务增加或恢复时,涉及数据迁移的真实节点就越多。有数据迁移场景需求的话需要考虑这一点。

    展开全文
  • consistent hashing算法的原理consistent hashing是一种hash算法,简单的说,在移除/添加一个cache时,它能够尽可能小的改变已存在key映射关系,尽可能的满足单调的要求。下面就来按照5个步骤简单讲讲consistent ...

    consistent hashing 算法的原理

    consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在key 映射关系,尽可能的满足单调性的要求。

    下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

    1 环形hash 空间

    考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

    60655f4fe99526426397d7b16d168f2d.png

    图 1 环形 hash 空间

    2 把对象映射到hash 空间

    接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

    hash(object1) = key1;

    … …

    hash(object4) = key4;

    09096c4baaa3004f4c8cad582fec9666.png

    图 2 4 个对象的 key 值分布

    3 把cache 映射到hash 空间

    Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的 hash算法。

    假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash 值排列。

    hash(cache A) = key A;

    … …

    hash(cache C) = key C;

    1eaf0aed35673dc9cfc71d92dc04880d.png

    图 3 cache 和对象的 key 值分布

    说到这里,顺便提一下 cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash输入。

    4 把对象映射到cache

    现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

    在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

    依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 和object3 对应到 cache C ; object4 对应到 cache B ;

    5 考察cache 的变动

    前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时, cache会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。

    5.1移除 cache

    考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。

    因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。

    f999c8a54d459d92e0736ea063b1ed1e.png

    图 4 Cache B 被移除后的 cache 映射

    5.2添加 cache

    再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 和object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

    因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。

    ebe2ed74041a20daa0fc5627f7422db8.png

    图 5 添加 cache D 后的映射关系

    虚拟节点

    考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

    平衡性

    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

    hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了object2 、 object3 和 object4 ;分布是很不均衡的。

    为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

    “虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

    仍以仅部署 cache A 和 cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 。

    116f6c63261f7b6c017acfde1c98f305.png

    图 6 引入“虚拟节点”后的映射关系

    此时,对象到“虚拟节点”的映射关系为:

    objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ;

    因此对象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。

    引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。

    4382e244af43901a0ebcc8e7140159c9.png

    图 7 查询对象所在 cache

    “虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为202.168.14.241 。

    引入“虚拟节点”前,计算 cache A 的 hash 值:

    Hash(“202.168.14.241”);

    引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值:

    Hash(“202.168.14.241#1”);  // cache A1

    Hash(“202.168.14.241#2”);  // cache A2

    展开全文
  • 一致性哈希算法——虚拟节点一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是...

    一致性哈希算法——虚拟节点

    一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。

    因此,引入了一致性哈希算法:

    把数据用hash函数(如MD5),映射到一个很大的空间里,如图所示。数据的存储时,先得到一个hash值,对应到这个环中的每个位置,如k1对应到了图中所示的位置,然后沿顺时针找到一个机器节点B,将k1存储到B这个节点中。

    如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示:

    这样,只会影响C节点,对其他的节点A,D的数据不会造成影响。然而,这又会造成一个“雪崩”的情况,即C节点由于承担了B节点的数据,所以C节点的负载会变高,C节点很容易也宕机,这样依次下去,这样造成整个集群都挂了。

    为此,引入了“虚拟节点”的概念:即把想象在这个环上有很多“虚拟节点”,数据的存储是沿着环的顺时针方向找一个虚拟节点,每个虚拟节点都会关联到一个真实节点,如下图所使用:

    图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点,机器A负载存储A1、A2的数据,机器B负载存储B1、B2的数据,机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成“雪崩”现象。

    展开全文
  • 最近在优化部门分布式调度任务,在读 XXL-JOB 源码时,发现它的负载均衡逻辑中用到了一致性 hash 算法。其实在分布式缓存集群中也用到了一致性 hash 算法,(如:redis集群)是为了提高缓存的容错性和可扩展性。至于 ...
  • 一致性哈希算法在1997年由麻省理工学院提出,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。...
  • Hash 算法也叫做散列算法,他可以让任意长度的数据M映射成为长度固定的值H。Hash算法的作用Hash算法的第一个作用就是数据的快速存储与查找。写过程序的人都知道,基本上主流的编程语言里面都有个数据结构叫做Map...
  • 假设初始节点数为 N,则传统的对 N 取模的映射方式存在一个问题在于:当节点增删,即 N 值变化时,整个哈希表(Hash Table)需要重新映射,这便意味着大部分数据需要在节点之间移动。因此现在普遍使用的是被称为一致性...
  • redis系列之——一致性hash算法一致性hash算法你了解吗?什么时候使用?解决什么问题?redis集群模式使用了一致性hash算法了吗?数据分片(sharding)分布式数据存储时,经常要考虑数据分片,避免将大量的数据放在单表...
  • Hash算法Hash 算法在路由算法应用中,为了保证数据均匀的分布,例如有 3 个桶,分别是 0 号桶, 1 号桶和 2 号桶;现在有 12 个球,怎么样才能让 12 个球平均分布到 3 个桶中呢?使用 Hash 算法的做法是,将 12 个球...
  • 一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法,常用于负载均衡。Memcached client 也选择这种算法,解决将 key-value 均匀分配到众多 Memcached server 上的问题。它可以取代传统的取模操作,解决...
  • 一致性hash虚拟节点

    2020-08-10 17:35:42
    consistent hashing是一种hash算法,简单的说,在移除/添加一个cache时,它能够尽可能小的改变已存在key映射关系,尽可能的满足单调的要求。 下面就来按照5个步骤简单讲讲consistent hashing算法的基本原理。 1...
  • 为了解决数据倾斜问题,一致性 Hash 算法提出了【虚拟节点】,会对每一个服务节点计算多个哈希,然后放到圈上的不同位置。 当然我们也可以发现,一致性 Hash 算法,也只是解决大部分数据的问题。 文章转自:公众号...
  • 1 LVS-sh调度算法(souce address hash)本节是LVS中sh调度算法的实现分析;ip_vs_sh_init_svc() - 创建256个hash bucket的hash table,并将rs映射到这256个bucket中,增加rs的引用计数器;ip_vs_sh_done_svc() - 释放...
  • memcached 内存模型memcached 的缓存算法(简单列举多集中缓存算法/调度算法)分布式算法/一致性Hash虚拟节点技术memcached 的优缺点/简单的跟redis对比 2.memcached 工作原理 首先 memcached 是以...
  • 一致性hash的原理介绍,前人已经做的很清楚了,可以参看下面链接: 一致性HASH算法详解 上文美中不足的是,数据结构的设计较复杂,hash环的实现,属性用简单的列表和字典实现即可。 一致性哈希(不设置虚拟节点)...
  • 文章目录一致性哈希一致性 hash —— 基础类型一致性 hash —— 虚拟节点Golang 实现结构定义hash 环的初始化hash 环添加节点一致性 hash 请求 一致性哈希 简单哈希 hash(object)%N 是最常用的算法,这种均衡性可能...
  • 在了解一致性哈希算法之前,最好先了解一下缓存中的一个应用场景,了解了这个应用场景之后,再来理解一致性哈希算法,就容易多了,也更能体现出一致性哈希算法的优点,那么,我们先来描述一下这个经典的分布式缓存的...
  • 数据倾斜 为了解决数据倾斜问题,一致性 Hash 算法提出了【虚拟节点】,会对每一个服务节点计算多个哈希,然后放到圈上的不同位置。 虚拟节点 当然我们也可以发现,一致性 Hash 算法,也只是解决大部分数据的问题。...
  • import java.util.LinkedList; import java.util.List; import java.util.SortedMap; import java.util.TreeMap;...分布式缓存一致性hash算法,带虚拟节点 @author lisl */ public class HashCacheT...
  • 数据倾斜 为了解决数据倾斜问题,一致性 Hash 算法提出了【虚拟节点】,会对每一个服务节点计算多个哈希,然后放到圈上的不同位置。 虚拟节点 当然我们也可以发现,一致性 Hash 算法,也只是解决大部分数据的问题。...
  • 最近在看关于一致性hash,其原理就是不仅对数据的key进行hash,同时对节点也进行hash,比如使用节点的ip值来进行hash,然后看key的hash值落在节点的hash值的区间来确定这个key在哪个节点上(我们的应该是数据会发到...
  • 一致性HASH算法(虚拟节点)

    千次阅读 2016-07-15 14:00:35
    真实的环境是删除了s2后,所有他的虚拟节点都会马上被删除,虚拟节点上的连接也会重新连接到另一个主机的虚拟节点,不会存在这种中间情况。 以下给出所有的实现代码,大家共同学习: [java]   ...
  • 一致性hash,讲的不错 https://www.cnblogs.com/yixiwenwen/p/3580646.html https://www.cnblogs.com/xhj123/p/9087532.html
  • public class ConsistentHashingWithVirtualNode { ... //待添加入Hash环的服务器列表 private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:11...
  • 一致性hash 虚拟

    2016-05-12 10:02:20
    比如在Redis分布式缓存设计中,使用一致性Hash进行key分片存储,通过虚拟节点最大化降低添加或删除节点带来的影响。这里强调降低二字,即是它还是有影响的,在一般情况下我们还可以接受。但是某些场景下要求动态扩容...
  • 考虑到以往的技术应用,准备参考Mycat的一致性hash算法,实现此功能。查阅网上资料和Mycat一致性hash算法的源码后,编写了一个简单的实现算法。 具体实现如下: 缓存实现参考:...
  • 小白一只,, 最近在看哈希算法,中有提到hash算法的虚拟节点···请大佬···告知。。。一致性hash算法中的虚拟节点是根据什么加的,是如何加的,位置怎么选,加在哪里?···感谢···

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 307
精华内容 122
关键字:

一致性hash虚拟节点