精华内容
下载资源
问答
  • hash环/一致性hash

    2020-03-15 13:26:34
    hash环

    在负载均衡的策略中,一般有:

    • 轮询
    • 权重
    • 最小活跃
    • 一致性hash

    场景

    Dubbo中的负载均衡策略就有一致性hash,那一致性hash或者说hash环到底是什么呢?

    假设我有多台缓存服务器,编号分别为0,1,2…n-1。对于一个key,由客户端来决定存放到哪台机器,那最简单的hash公式就是 key % N,其中N是机器的总数。

    但这有个问题,一旦机器数变少,或者增加机器,N发生变化,那之前存放的数据就全部无效了。因为你按照新的N值取模计算出的机器编号,和当时按旧的N值取模算出的机器编号肯定是不等的,也就意味着绝大部分缓存会失效。

    比如原先N是5,key是8,这个key会在编号3(8%5 = 3)的机器上,如果说编号5的机器挂了,这时N变成4,key是8,这个key会在编号0(8%4 = 0)的机器上,这样就不对。

    会引起两个问题:

    1. 缓存的位置变化,找不到缓存。
    2. 缓存雪崩,因为很多缓存都失效了。

    这个问题的解决办法就是用1种特别的Hash函数,尽可能使得,增加机器/减少机器时,缓存失效的数目降到最低,这就是Hash环,或者叫一致性Hash。

    一致性hash的做法

    上面说的Hash函数,只经过了1次hash,即把key hash到对应的机器编号。
    而Hash环有2次Hash,就是对2的32次方取模:

    1. 把所有机器编号hash到这个环上
    2. 把key也hash到这个环上。然后在这个环上进行匹配,看这个key和哪台机器匹配。

    假设有4台服务器,地址为ip1,ip2,ip3,ip4。

    服务器IP哈希

    首先计算四个ip地址对应的hash值
    hash(ip1),hash(ip2),hash(ip3),hash(ip3),计算出来的hash值是0到2的32次方-1中的一个值,这四个值在一致性hash环上呈现如下图:
    在这里插入图片描述

    用户请求的key哈希

    根据hash(用户key)计算路由规则(对2的32次方取模后的hash值),然后看hash值落到了hash环的那个地方,根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip。
    在这里插入图片描述
    如上图可知user1,user2的请求会落到服务器ip2进行处理,User3的请求会落到服务器ip3进行处理,user4的请求会落到服务器ip4进行处理,user5,user6的请求会落到服务器ip1进行处理。

    有服务器挂掉怎么办

    下面考虑当ip2的服务器挂了的时候会出现什么情况?
    当ip2的服务器挂了的时候,一致性hash环大致如下图:
    在这里插入图片描述
    根据顺时针规则可知user1,user2的请求会被服务器ip3进行处理,而其它用户的请求对应的处理服务器不变,也就是只有之前被ip2处理的一部分用户的映射关系被破坏了,并且其负责处理的请求被顺时针下一个节点委托处理。

    有新增服务器怎么办

    当新增一个ip5的服务器后,一致性hash环大致如下图:
    在这里插入图片描述
    根据顺时针规则可知之前user5的请求应该被ip5服务器处理,现在被新增的ip5服务器处理,其他用户的请求处理服务器不变,也就是新增的服务器顺时针最近的服务器的一部分请求会被新增的服务器所替代。

    一致性hash倾斜的问题

    理想中服务器的IP是均匀分布在环中,但是现实并非如此,如果出现下面不均匀的情况,每台服务器上收到的key就不均匀,不能保证每个服务器处理的请求的数量大致相同。
    在这里插入图片描述

    虚拟节点

    当服务器节点比较少的时候会出现上面所说的一致性hash倾斜的问题,一个解决方法是多加机器,但是加机器是有成本的,那么就加虚拟节点,比如上面三个机器,每个机器引入1个虚拟节点后的一致性hash环的图如下:
    在这里插入图片描述
    其中ip1-1是ip1的虚拟节点,ip2-1是ip2的虚拟节点,ip3-1是ip3的虚拟节点。
    可知当物理机器数目为M,虚拟节点为N的时候,实际hash环上节点个数为M*N。比如当客户端计算的hash值处于ip2和ip3或者处于ip2-1和ip3-1之间时候使用ip3服务器进行处理。

    均匀一致哈希

    上节我们使用虚拟节点后的图看起来比较均衡,但是如果生成虚拟节点的算法不够好很可能会得到下面的环:
    在这里插入图片描述
    可知每个服务节点引入1个虚拟节点后,情况相比没有引入前均衡性有所改善,但是并不均衡。

    均衡的一致性hash应该是如下图:
    在这里插入图片描述
    均匀一致性hash的目标是如果服务器有N台,客户端的hash值有M个,那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡。

    链接:https://www.jianshu.com/p/e968c081f563

    展开全文
  • Hash环/一致性Hash原理

    2020-05-11 20:42:26
  • hash环是1997年麻省理工创建的一种数学模型,基础是hash散列.可以将任意的内存对象(二进制)转化映射到0-2^32-1整数区间.称这个区间为hash环. 0-1=最大环整数, 最大环整数+1=0(通过加一和减一在可以到最大和最小,...

    1.概述

    hash环是1997年麻省理工创建的一种数学模型,基础是hash散列.可以将任意的内存对象(二进制)转化映射到0-2^32-1整数区间.称这个区间为hash环. 0-1=最大环整数, 最大环整数+1=0(通过加一和减一在可以到最大和最小,理解上感觉是一个环)

    映射:利用某种计算关系,将两边的数据对应起来

    2. 一致性hash原理

    2.1数据映射

    读取的节点信息,和数据的key值都会在这个环找到对应的整数映射,而且节点信息不变,key值不变情况下整数映射结果不变

    2.2 数据key与节点对应关系

    key值要找到对应处理这个key的节点,只需要在hash环上计算:顺时针寻找最近的节点整数

    如下图,key1 顺时针寻找最近的节点就是10.9.160.137.6379(因为是顺时针寻找,所以一个key只能找到一个节点,保证了单调性)

    上述计算逻辑,确实可以保证key对应节点node后有单调性.他是算法的基础

    节点信息和key值做映射---(给定一个key,可以指定要找那个节点处理)

    2.3 扩容

    当集群发生节点变化时,一致性hash能够尽可能的减小对单调性破坏范围

    因为顺时针找,所以插入节点后,影响的部分是插入节点逆时针到下一个节点间的部分,如下图,当插入节点

    10.9.160.137:9000 时受影响的部分是下图标记绿色的部分

    2.4数据的平衡性

    一致性hash的计算,只使用真实节点信息,由于真实节点有限的,所以不能保证平衡性,引入了虚拟节点的概念

    当节点相互映射的整数挨的比较近,必定会有某些节点对应key值远远大于其他节点,造成严重的数据倾斜,所以需要解决这个问题,一致性hash计算逻辑中可以引入虚拟节点.

     

    jedis实现的一致性hash,通过计算一个节点的虚拟节点 160*weight, 调整权重值,实现比例的分配,默认weight=1

     

    展开全文
  • 一、前言 在解决分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些...一致性hash则利用hash环对其进行了改进。 二、一致性Ha...

    一、前言

    在解决分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些请求的信息),起到负载均衡的作用。

    但是普通的余数hash(hash(比如用户id)%服务器机器数)算法伸缩性很差,当新增或者下线服务器机器时候,用户id与服务器的映射关系会大量失效。一致性hash则利用hash环对其进行了改进。

    二、一致性Hash概述

    为了能直观的理解一致性hash原理,这里结合一个简单的例子来讲解,假设有4台服务器,地址为ip1,ip2,ip3,ip4。

    • 一致性hash是首先计算四个ip地址对应的hash值
      hash(ip1),hash(ip2),hash(ip3),hash(ip3),计算出来的hash值是0~最大正整数直接的一个值,这四个值在一致性hash环上呈现如下图:

       

      image.png

    • hash环上顺时针从整数0开始,一直到最大正整数,我们根据四个ip计算的hash值肯定会落到这个hash环上的某一个点,至此我们把服务器的四个ip映射到了一致性hash环

    • 当用户在客户端进行请求时候,首先根据hash(用户id)计算路由规则(hash值),然后看hash值落到了hash环的那个地方,根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip.

       

       

    如上图可知user1,user2的请求会落到服务器ip2进行处理,User3的请求会落到服务器ip3进行处理,user4的请求会落到服务器ip4进行处理,user5,user6的请求会落到服务器ip1进行处理。

    下面考虑当ip2的服务器挂了的时候会出现什么情况?
    当ip2的服务器挂了的时候,一致性hash环大致如下图:

     

     

    根据顺时针规则可知user1,user2的请求会被服务器ip3进行处理,而其它用户的请求对应的处理服务器不变,也就是只有之前被ip2处理的一部分用户的映射关系被破坏了,并且其负责处理的请求被顺时针下一个节点委托处理。

    下面考虑当新增机器的时候会出现什么情况?
    当新增一个ip5的服务器后,一致性hash环大致如下图:

     

     

    根据顺时针规则可知之前user5的请求应该被ip5服务器处理,现在被新增的ip5服务器处理,其他用户的请求处理服务器不变,也就是新增的服务器顺时针最近的服务器的一部分请求会被新增的服务器所替代。

    三、一致性hash的特性

    • 单调性(Monotonicity),单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理,又有新的服务器加入到系统中时候,应保证原有的请求可以被映射到原有的或者新的服务器中去,而不会被映射到原来的其它服务器上去。 这个通过上面新增服务器ip5可以证明,新增ip5后,原来被ip1处理的user6现在还是被ip1处理,原来被ip1处理的user5现在被新增的ip5处理。

    • 分散性(Spread):分布式环境中,客户端请求时候可能不知道所有服务器的存在,可能只知道其中一部分服务器,在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环,那么可能会导致,同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的,因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。好的哈希算法应尽量避免尽量降低分散性。 一致性hash具有很低的分散性

    • 平衡性(Balance):平衡性也就是说负载均衡,是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求,但是不能保证每个服务器处理的请求的数量大致相同,如下图

       

    服务器ip1,ip2,ip3经过hash后落到了一致性hash环上,从图中hash值分布可知ip1会负责处理大概80%的请求,而ip2和ip3则只会负责处理大概20%的请求,虽然三个机器都在处理请求,但是明显每个机器的负载不均衡,这样称为一致性hash的倾斜,虚拟节点的出现就是为了解决这个问题。

    五、虚拟节点

    当服务器节点比较少的时候会出现上节所说的一致性hash倾斜的问题,一个解决方法是多加机器,但是加机器是有成本的,那么就加虚拟节点,比如上面三个机器,每个机器引入1个虚拟节点后的一致性hash环的图如下:

     

     

    其中ip1-1是ip1的虚拟节点,ip2-1是ip2的虚拟节点,ip3-1是ip3的虚拟节点。
    可知当物理机器数目为M,虚拟节点为N的时候,实际hash环上节点个数为M*N。比如当客户端计算的hash值处于ip2和ip3或者处于ip2-1和ip3-1之间时候使用ip3服务器进行处理。

    六、均匀一致性hash

    上节我们使用虚拟节点后的图看起来比较均衡,但是如果生成虚拟节点的算法不够好很可能会得到下面的环:

     

     

     

    可知每个服务节点引入1个虚拟节点后,情况相比没有引入前均衡性有所改善,但是并不均衡。

    均衡的一致性hash应该是如下图:

     

     

    均匀一致性hash的目标是如果服务器有N台,客户端的hash值有M个,那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡

    七、总结

    在分布式系统中一致性hash起着不可忽略的地位,无论是分布式缓存,还是分布式Rpc框架的负载均衡策略都有所使用。


    原文出自:
    作者:阿里加多
    链接:https://www.jianshu.com/p/e968c081f563
    来源:简书

    展开全文
  • 一致性Hash算法是对2^32取模,2^32个点组成的圆环称为Hash环。根据服务节点的IP或者机器名称进行哈希,就能确定每台机器就能确定其在哈希环上的位置; 将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环...
  • 由于结果是32位二进制,0减一变成2^32-1 最大数加一变成0,这个取值区间称谓hash环 2)数据映射计算: 节点收集信息时,每个节点信息作为一个对象映射到这个环上一个整数 key值作为字符串数据也会映射到这个环上一个整数...
  • Memcached:为分布式客户端做分发,hash环 TWY Redis:为分布式客户端做分发 ,hash环 Redis Cluster:点对点,2Khash槽 当前,Memcached、Redis这类分布式kv缓存已经非常普遍。从本篇开始,本系列将分析分布式...
  • 用于分布式系统中多个服务器集群,当增加减少节点时,使用该hash环算法,可减少数据因节点变动,出现大量命中失败问题,redis集群就是通过hash环思想实现的。 解释: 一致性哈希环,分散化实体项的节点位置选择,...
  • 一致性Hash及其原理、Hash环

    千次阅读 2018-05-05 20:16:42
    转载的主要愿意是因为本文通俗易懂,以防后面找不到,故转载。 原文:http://www.zsythink.net/archives/1182
  • 一致性hash算法(hash环)

    2020-02-22 22:40:29
    一致性hash算法 1.前景(hash算法) 分布式缓存: 需求: 将图片均匀的分布到3台服务器上。 方案: 使用hash算法。 对于一个key,由客户端来决定存放到哪台机器,那最简单的hash公式就是 hash(key)% N,其中N是机器的...
  • 一致性Hash算法(hash环

    千次阅读 2017-12-01 15:37:07
    一致性Hash(DHT)性质 考虑到分布式系统每个节点都有可能失效,并且新的节点很可能动态的增加进来,如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务,这是值得考虑的,尤其实在设计分布式缓存系统...
  • 一致性Hash(Hash环

    2018-03-26 17:18:04
    这个问题的解决办法就是用1种特别的Hash函数,尽可能使得,增加机器/减少机器时,缓存失效的数目降到最低,这就是Hash环,或者叫一致性Hash。 Hash环 上面说的Hash函数,只经过了1次hash,即把key hash到对应...
  • 转载 原文
  • 先聊一下一致性hash诞生的背景“ 一致性Hash算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot Spot)问题,初衷和CARP十分相似,将来自网络上的流量动态的...
  • 这个问题的解决办法就是用1种特别的Hash函数,尽可能使得,增加机器/减少机器时,缓存失效的数目降到最低,这就是Hash环,或者叫一致性Hash。 有兴趣朋友可以关注公众号“架构之道与术”, 获取最新文章。 或扫描...
  • 普通的hash使用的时候: a. 创建哈希表需要先指定大小 b.当添加的元素达到了装载因子乘以表长时,需要扩容 但是在扩容时,代价很大,可能影响到所有元素的移动,为了减少扩容时元素的移动,总是将哈希表扩容成...
  • 环形hash算法java实现

    2016-06-12 13:13:34
    一致性Hash算法关于一致性Hash算法,在我...算法的具体原理这里再次贴上:先构造一个长度为2 32 的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 2 32-1])将服务器节点放置在这个Hash
  • 但是切割hash环的时候,遇到一个思考题: 在数字环上随机落N个点,把环切分成N个区间,原点要算一个切分点吗?如果算,就只产生N-1个随机数就可以了,如果不算,要产生N个随机点。 为什么会产生这个疑问?如上图...
  • 一致性Hash和环形Hash

    2017-04-02 04:23:01
    一致性Hash 是为了解决动态缓存节点映射问题的 一致性hash的要求: 平衡性:数据分配要均匀 单调性:原有的数据只能映射到其所在的缓冲区或者新的缓冲区,而非其他旧缓冲区。 分散性:同样的内容映射到相同的缓冲区...
  • hash和一致性hash

    千次阅读 2019-07-25 09:19:45
    hash;简单的hash取余 优点: 计算简单,快速定位 缺点: 容错和扩展差,任何的增加机器或减少...一致性hash:hash环 想象一个环,共有2^(32-1) 个节点,如果有五台机器缓存,那么就将这五台的ip分别hash后对2^(32...
  • 一致性hash

    2019-02-20 22:36:21
    先构造一个长度为2^32的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 232-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 232-1]),接着在...
  • 一致性hash算法

    2019-12-04 16:14:27
    什么是hash环 对象怎么映射到hash环 服务器节点怎么映射到hash环 对象怎么映射到服务器节点 服务器节点新增、失效影响点分析 虚拟节点 一、什么是hash环 hash算法:通常的hash算法是将一个value映射到一个32位...
  • 它将Hash函数的值域空间组织成圆环,假设Hash函数的值域空间为0~232-1(即Hash值是一个32位的无符号整数),整个空间按照顺时针方向进行组织,然后对相应的服务器节点进行Hash,将他们映射到Hash环上,假设有4台...
  • 一致性HASH

    2019-09-06 21:38:41
    前面提到分布式数据库数据分区规则有 【节点取余分区】 【一致性哈希分区】 ... 根据hash(用户id)计算路由规则(hash值),然后看hash值落到了hash环的那个地方,根据hash值在hash环上的位置顺时针找距离最近的i...
  • 先构造一个长度为2^32的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 2^32-1])将缓存服务器节点放置在这个Hash环上,然后根据需要缓存的数据的Key值计算得到其Hash值(其分布也为[0, 2^...
  • 一致性hash的golang实现

    千次阅读 2018-03-26 13:13:29
    对于一致性hash环的介绍本文就不在此赘述了,直接看怎样实现 package hashring import ( "crypto/md5" "fmt" "math" "sort" ) type HashKey uint32 type ...
  • 一致性Hash算法

    2020-06-28 17:33:47
    个人觉得一致性Hash算法相较普通Hash算法,重点就是引入了Hash环作为标准参照 一致性Hash算法解决的是数据落点问题,通过一致性Hash算法可以将数据均衡的分配到分布式环境下的多台服务器上,比如Redis缓存集群每台...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,843
精华内容 17,137
关键字:

hash环