精华内容
下载资源
问答
  • 一致性 hash分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢?强哈希考虑到单服务器不能...

    一致性 hash

    分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢?

    强哈希

    考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。同样不也不能进行动态增加节点。

    弱哈希

    为了解决单点故障,使用 hash() mod (n/m),

    这样任意一个用户都有 m 个服务器备选,可由 client 随机选取。

    由于不同服务器之间的用户需要彼此交互,所以所有的服务器需要确切的知道用户所在的位置。

    因此用户位置被保存到 memcached 中。当一台发生故障,client 可以自动切换到对应 backup,由于切换前另外 1 台没有用户的 session,因此需要 client 自行重新登录。

    好处

    他比强哈希的好处是:解决了单点问题。

    缺点

    但存在以下问题:负载不均衡,尤其是单台发生故障后剩下一台会压力过大;不能动态增删节点;节点发生故障时需要 client 重新登录

    一致性 hash 算法

    一致性 hash 算法提出了在动态变化的 Cache 环境中,判定哈希算法好坏的四个定义:

    平衡性(Balance)

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

    单调性(Monotonicity)

    单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

    分散性(Spread)

    在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。

    当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。

    这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

    负载(Load)

    负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。

    与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    普通的哈希算法(也称硬哈希)采用简单取模的方式,将机器进行散列,这在cache环境不变的情况下能取得让人满意的结果,但是当cache环境动态变化时,

    这种静态取模的方式显然就不满足单调性的要求(当增加或减少一台机子时,几乎所有的存储内容都要被重新散列到别的缓冲区中)。

    代码实现

    实现逻辑

    一致性哈希算法有多种具体的实现,包括 Chord 算法),KAD 算法等实现,以上的算法的实现都比较复杂。

    这里介绍一种网上广为流传的一致性哈希算法的基本实现原理,感兴趣的同学可以根据上面的链接或者去网上查询更详细的资料。

    一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。

    当有一个写入缓存的请求到来时,计算 Key 值 k 对应的哈希值 Hash(k),如果该值正好对应之前某个机器节点的 Hash 值,则直接写入该机器节点,

    如果没有对应的机器节点,则顺时针查找下一个节点,进行写入,如果超过 2^32 还没找到对应节点,则从0开始查找(因为是环状结构)。

    如图 1 所示:

    b69ddbfdb344b3ef5d3503bcb7c2c5ac.png

    图 1 中 Key K 的哈希值在 A 与 B 之间,于是 K 就由节点B来处理。

    另外具体机器映射时,还可以根据处理能力不同,将一个实体节点映射到多个虚拟节点。

    经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,

    例如新加入的节点H的散列在 B 与 C 之间,则原先由 C 处理的一些数据可能将移至 H 处理,

    而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。

    而如果删除一台机器,例如删除 C 节点,此时原来由 C 处理的数据将移至 D 节点,而其它节点的处理情况仍然不变。

    而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。

    而通过引入虚拟节点的方式,也大大提高了平衡性。

    实现代码

    展开全文
  • Redis的作者认为它的crc16(key) mod 16384的效果已经不错了,虽然没有一致性hash灵活,但实现很简单,节点增删时处理起来也很方便。 "为了动态增删节点的时候,不至于丢失数据么?" 节点增删时不丢失数据...

    "用了哈希槽的概念,而没有用一致性哈希算法,不都是哈希么?这样做的原因是为什么呢?"
    Redis Cluster是自己做的crc16的简单hash算法,没有用一致性hash。Redis的作者认为它的crc16(key) mod 16384的效果已经不错了,虽然没有一致性hash灵活,但实现很简单,节点增删时处理起来也很方便。

    "为了动态增删节点的时候,不至于丢失数据么?"
    节点增删时不丢失数据和hash算法没什么关系,不丢失数据要求的是一份数据有多个副本。

    “还有集群总共有2的14次方,16384个哈希槽,那么每一个哈希槽中存的key 和 value是什么?”
    当你往Redis Cluster中加入一个Key时,会根据crc16(key) mod 16384计算这个key应该分布到哪个hash slot中,一个hash slot中会有很多key和value。你可以理解成表的分区,使用单节点时的redis时只有一个表,所有的key都放在这个表里;改用Redis Cluster以后会自动为你生成16384个分区表,你insert数据时会根据上面的简单算法来决定你的key应该存在哪个分区,每个分区里有很多key。

    集群:
    是一个提供多个Redis(分布式)节点间共享数据的程序集。
    集群部署
    Redis 集群的键空间被分割为 16384 hash个槽(slot), 集群的最大节点数量也是 16384 个
    关系:cluster>node>slot>key

    分片:
    Redis Cluster在设计中没有使用一致性哈希(Consistency Hashing),而是使用数据分片引入哈希槽(hash slot)来实现;

    一个 Redis Cluster包含16384(0~16383)个哈希槽,存储在Redis Cluster中的所有键都会被映射到这些slot中,

    集群中的每个键都属于这16384个哈希槽中的一个,集群使用公式slot=CRC16(key)/16384来计算key属于哪个槽,其中CRC16(key)语句用于计算key的CRC16 校验和。

    按照槽来进行分片,通过为每个节点指派不同数量的槽,可以控制不同节点负责的数据量和请求数.

    当前集群有3个节点,槽默认是平均分的:
    节点 A (6381)包含 0 到 5499号哈希槽.
    节点 B (6382)包含5500 到 10999 号哈希槽.
    节点 C (6383)包含11000 到 16383号哈希槽.
    这种结构很容易添加或者删除节点. 比如如果我想新添加个节点D, 我需要从节点 A, B, C中得部分槽到D上. 如果我像移除节点A,需要将A中得槽移到B和C节点上,然后将没有任何槽的A节点从集群中移除即可. 由于从一个节点将哈希槽移动到另一个节点并不会停止服务,所以无论添加删除或者改变某个节点的哈希槽的数量都不会造成集群不可用的状态.

    数据迁移
    数据迁移可以理解为slot(槽)和key的迁移,这个功能很重要,极大地方便了集群做线性扩展,以及实现平滑的扩容或缩容。

    现在要将Master A节点中编号为1、2、3的slot迁移到Master B节点中,在slot迁移的中间状态下,slot 1、2、3在Master A节点的状态表现为MIGRATING(迁移),在Master B节点的状态表现为IMPORTING(入口)。

     

    此时并不刷新node的映射关系

    IMPORTING状态

    被迁移slot 在目标Master B节点中出现的一种状态,准备迁移slot从Mater A到Master B的时候,被迁移slot的状态首先变为IMPORTING状态。

    键空间迁移


    键空间迁移是指当满足了slot迁移前提的情况下,通过相关命令将slot 1、2、3中的键空间从Master A节点转移到Master B节点。此时刷新node的映射关系。

    复制&高可用:
    集群的节点内置了复制和高可用特性。


    特点:1、节点自动发现
    2、slave->master 选举,集群容错
    3、Hot resharding:在线分片
    4、基于配置(nodes-port.conf)的集群管理
    5、客户端与redis节点直连、不需要中间proxy层.
    6、所有的redis节点彼此互联(PING-PONG机制),内部使用二进制协议优化传输速度和带宽.


    --------------------- 
    作者:小小月的春天 
    来源:CSDN 
    原文:https://blog.csdn.net/tianpeng341204/article/details/78963850 
    版权声明:本文为博主原创文章,转载请附上博文链接!

    展开全文
  • 一致性 hash 分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢? 强哈希 考虑到单...

    一致性 hash

    分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢?

    强哈希

    考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。同样不也不能进行动态增加节点。

    弱哈希

    为了解决单点故障,使用 hash() mod (n/m),

    这样任意一个用户都有 m 个服务器备选,可由 client 随机选取。

    由于不同服务器之间的用户需要彼此交互,所以所有的服务器需要确切的知道用户所在的位置。

    因此用户位置被保存到 memcached 中。当一台发生故障,client 可以自动切换到对应 backup,由于切换前另外 1 台没有用户的 session,因此需要 client 自行重新登录。

    • 好处

    他比强哈希的好处是:解决了单点问题。

    • 缺点

    但存在以下问题:负载不均衡,尤其是单台发生故障后剩下一台会压力过大;不能动态增删节点;节点发生故障时需要 client 重新登录

    一致性 hash 算法

    一致性 hash 算法提出了在动态变化的 Cache 环境中,判定哈希算法好坏的四个定义:

    平衡性(Balance)

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

    单调性(Monotonicity)

    单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

    分散性(Spread)

    在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。

    当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。

    这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

    负载(Load)

    负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。

    与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    普通的哈希算法(也称硬哈希)采用简单取模的方式,将机器进行散列,这在cache环境不变的情况下能取得让人满意的结果,但是当cache环境动态变化时,
    这种静态取模的方式显然就不满足单调性的要求(当增加或减少一台机子时,几乎所有的存储内容都要被重新散列到别的缓冲区中)。

    代码实现

    实现逻辑

    一致性哈希算法有多种具体的实现,包括 Chord 算法KAD 算法等实现,以上的算法的实现都比较复杂。

    这里介绍一种网上广为流传的一致性哈希算法的基本实现原理,感兴趣的同学可以根据上面的链接或者去网上查询更详细的资料。

    一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。

    当有一个写入缓存的请求到来时,计算 Key 值 k 对应的哈希值 Hash(k),如果该值正好对应之前某个机器节点的 Hash 值,则直接写入该机器节点,
    如果没有对应的机器节点,则顺时针查找下一个节点,进行写入,如果超过 2^32 还没找到对应节点,则从0开始查找(因为是环状结构)。

    如图 1 所示:

    hash

    图 1 中 Key K 的哈希值在 A 与 B 之间,于是 K 就由节点B来处理。

    另外具体机器映射时,还可以根据处理能力不同,将一个实体节点映射到多个虚拟节点。

    经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,

    例如新加入的节点H的散列在 B 与 C 之间,则原先由 C 处理的一些数据可能将移至 H 处理,
    而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。

    而如果删除一台机器,例如删除 C 节点,此时原来由 C 处理的数据将移至 D 节点,而其它节点的处理情况仍然不变。

    而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。

    而通过引入虚拟节点的方式,也大大提高了平衡性。

    实现代码

    consitent-hashing

    原文地址

    consitent-hashing

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

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

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

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

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

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

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

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

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

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

    可参考下图--图片来源

    具体做法

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

    数据迁移

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

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

    总结

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

    展开全文
  • hash和一致性hash

    千次阅读 2019-07-25 09:19:45
    hash;简单的hash取余 优点: 计算简单,快速定位 缺点: 容错和扩展差,任何的增加机器或减少...一致性hash:hash环 想象一个环,共有2^(32-1) 个节点,如果有五台机器缓存,那么就将这五台的ip分别hash后对2^(32...
  • 一致性 hash分布式过程中我们将服务分散到若干的节点上,以此通过集体的力量提升服务的目的。然而,对于一个客户端来说,该由哪个节点服务呢?或者说对某个节点来说他分配到哪些任务呢?强哈希考虑到单服务器不能...
  • 一致性hash算法

    2020-08-13 15:13:23
    一致性hash算法(数据均匀分布到各个节点上) 普通hash算法的缺点:普通的hash算法将key的hash值对redis实例的个数进行取模,来定位到redis,这样会有一些问题,比如redis实例增加,这个计算公式就会变,于是要将...
  • 一致性hash 易懂 原理

    2020-01-09 11:42:04
    1.普通hash简介 普通hash是根据 Hash(obj)%机器数 来确定落在哪台机器的。 缺点:当我们减少(宕机)或者增加集群...一致性hash算法通过一个叫作一致性hash环的数据结构实现,环的整数分布范围是( 0 , 1 , 2 , 3 … ...
  • 余数hash和一致性hash

    2020-06-06 22:16:56
    今天简单描述两种哈希方式:余数hash和一致性hash。 余数哈希 余数哈希是一般通过对数值取模的方式来获得hash值,比如数据为367,有20个子节点,那么367会根据367%20=7,分配到编号为7的子节点。那么接下来的问题是...
  • 普通Hash与一致性Hash

    2021-01-19 18:46:18
    1.Hash的介绍   Hash算法应用很广泛,比如MD5,SHA加密算法,数据存储和数据查找方面。   Hash算法最主要的应用...这种方法的缺点就是,容易产生Hash冲突,比如数组长度为5,需要存储的数值有1,2,3,4,6,那么在存储1
  • 一致性hash 虚拟桶

    2016-05-12 10:02:20
    关于数据分片讨论最多的是一致性hash,然而它并不是分布式设计中的银弹百试百灵。 在数据稳定性要求比较高的场景下它的缺点是不能容忍的。比如在Redis分布式缓存设计中,使用一致性Hash进行key分片存储,通过虚拟...
  • 【01笔记】Hash和一致性Hash

    千次阅读 2020-02-17 08:31:41
    假设有四台图片缓存服务器。 1、随机 ...3、一致性Hash 对2^32取模,将整个哈希空间组成一个虚拟的环。 将机器IP或主机名为关键字进行哈希,并映射到该环上某个位置, 与机器数量无关,但可能...
  • 5 分钟精通一致性 Hash

    2020-06-25 16:21:25
    起源 在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题 性质 平衡性 单调性 分散性 负载 平滑性 ...数据的均衡性:计算 Hash ...2、一致性hash
  • 第一种:传统的数据分布方法,将key的hash值对机器数取模 这个算法的实现非常简单,计算hash(key)/n,...第二种:一致性hash 试想下如果使用传统取模算法。如果有一个key要存到缓存中,根据hash(key)/n (n表示有n台缓...
  • 2,一致性hash算法,节点,圆环,缺点:节点少无法均匀分布 3,添加虚拟节点 一、分布式算法 在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接...
  • 1、使用一致性Hash算法,尽管增强了系统的伸缩性,但是也有可能导致负载分布不均匀,解决办法就是使用虚拟节点代替真实节点,  2、Hash算法的选择上,首先我们考虑简单的String.HashCode()方法,这个算法的缺点是...
  • 其实大部分中间件都逃不过这两种模式 中心化模式 这种模式的特点是有一Master多slave,一般采用读写分离的方式,只从master中写,然后同步给slave(主从同步)。读是通过负载均衡从所有的...缺点:数据的一致性
  • 一致性哈希算法的定义和思想 一致性哈希的基本过程 Redis集群中一致性哈希的实现 1.分布式系统的基本概念 分布式系统与高并发高可用 当今高并发和海量数据处理等场景越来越多,实现服务应用的高可用、易扩展、短...
  • nginx的hash和一致性hash的区别

    千次阅读 2017-06-12 20:46:07
    hash  nginx的负载均衡时有一个hash $request_uri的选项,这个是类似于LVS的dh。是针对客户端访问的uri来做的绑定。这样客户端访问同一个uri的时候,会被分配到同一个服务器... 缺点:如果一个节点挂了,那么整个
  • libketama 一致性hash有什么用呢?我们最常用的hash方法是这样的:server = serverlist[hash(key) % serverlist的个数]这样明显有一个缺点:当服务器的个数变化时,所有的hash都将无效,全部得重来一次。一致性hash...
  • hash一致性

    2019-07-03 16:06:26
    1.分片计算中,hash取余算法的缺点 在使用redis集群时,hash取余(key.hashCode()&Integer.MAX_VALUE%N),存在两个缺点 • 数据倾斜不可避免(只要是散列hash,数据计算结果倾斜必定存在) • 扩容缩容集群时,数据迁移...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 142
精华内容 56
关键字:

一致性hash缺点