https://segmentfault.com/a/11...节点减少、缩小会导致已有数据映射谬误。（三个节点时，5会映射到第二个节点上，缩减为2个节点时，5会映射到第一个节点上，此时去第一个节点其实找不到5）如果分布式缓存大量生效就会产生缓存雪崩。指标：尽可能小的扭转已有数据的映射关系，从而缩小数据挪动的开销。解决分布式哈希表动静伸缩的问题。 哈希算法应满足平衡性:各节点均衡散布，在算法层面做负载平衡枯燥性：新增或删除节点时不影响零碎裕兴分散性：节点只须要保留一部分数据原理对象向2^32-1个桶里hash，放到哈希环上。把服务器也放到哈希环上。顺时针找离对象最近的机器。新增、删除机器时，只有机器左右的对象被影响。为了让重调配更平衡，减少虚构节点，对象先找到本人属于的虚构节点，再找到虚构节点属于的实在节点。一台实在节点对应大量虚构节点，扩散在环的各处，当减少或删除一台实在节点时，很多台其余节点都会受到轻微的影响。
一致性Hash 算法1，介绍一致性hash算法（Consistent Hashing）及其在分布式缓存中的利用，以及对一致性hash算法原理的介绍。2，简略的代码实现3，发现有什么问题不便请指出下。。谢谢。。一，背景咱们通过一个问题思考引入。。 假如咱们有个网站，随着用户量的一直增长，日活量的一直晋升，导致 mysql 的数据读写压力飞速增长，对咱们的服务造成极大的压力。。 为了解决下面的窘境咱们引入了 redis 作为缓存机制，然而你会发现其实随着业务扩张，单台 redis 很快就无奈撑持起你零碎服务，那么为了解决这个问题，咱们会开始引入多台 redis 形成服务集群为网站提供缓存服务； 因为咱们不可能所有的 redis 服务都缓存所有数据，因为这样意义不大，咱们现实的是 每个 redis 服务提供一部分用户的缓存数据，而后依据不同的客户的申请读取不同 redis 的缓存数据； 在这个时候：很多人会想起 hash取模 法； 如上图：依据 Customer_id 取模失去值，依据值流入指定的redis服务中。如果 customer_id 是自增的，咱们每个 redis 服务外面的值的数量都是相对均匀的； 然而短期问题是解决了。。然而你有没有想过，当3个redis 服务无奈失常撑持，须要退出 第 4 个 redis 服务 或者资源过剩了，你心愿回收一个 redis 应用两个 redis 撑持服务了。。然而这个时候你会发现。。 取模的值一旦扭转。。之前缓存的数据就会产生错乱。。这样会有大量的申请穿过你的 redis 缓存服务，间接达到你的 mysql。。而且 redis 缓存服务也缓存着大量无用数据，结果有点可怕。。 为了解决上述问题。。。咱们引入 一致性Hash算法 二，算法简述简略来说咱们把所有数据做一致性hash计算后的所有后果看作一个 hash 闭环，而闭环的大小为0~2^32，也就说所有的数据都会坐落在这个 hash 闭环；如下图： 0 和 2^32 在 hash 闭环中重合，这里为什么要这样做 大家能够思考下。。 下一步咱们把 redis 服务 的IP 也应用 雷同的 hash("redis服务IP") 办法进行求出 hash 值，这样咱们 redis服务 也会坐落在咱们的 hash闭环 中，他的作用 能够看做个桶，承接顺指针流入的数据；如下图： ...
前言一致性哈希算法(Consistent Hashing)在分布式系统的应用还是十分广泛的，本文尽量结合业务场景快速讲解一致性哈希算法的应用及与其相关的话题。1 分布式缓存随着业务的扩展，流量的剧增，单体项目逐渐划分为分布式系统。对于经常使用的数据，我们可以使用Redis作为缓存机制，减少数据层的压力。因此，重构后的系统架构如下图所示：优化最简单的策略就是，把常用的数据保存到Redis中，为了实现高可用使用了3台Redis（没有设置集群，集群至少要6台）。每次Redis请求会随机发送到其中一台，但是这种策略会引发如下两个问题：同一份数据可能在多个Redis数据库，造成数据冗余某一份数据在其中一台Redis数据库已存在，但是再次访问Redis数据库，并没有命中数据已存在的库。无法保证对相同的key的所有访问都发送到相同的Redis中要解决上述的问题，我们需要稍稍改变一些key存入Redis的规则：使用hash算法例如，有三台Redis，对于每次的访问都可以通过计算hash来求得hash值。如公式 h=hash(key)%3，我们把Redis编号设置成0,1,2来保存对应hash计算出来的值，h的值等于Redis对应的编号。但是hash算法也会面临容错性和扩展性的问题。容错性是指当系统中的某个服务出现问题时，不能影响其他系统。扩展性是指当加入新的服务器后，整个系统能正确高效运行。现假设有一台Redis服务器宕机了，那么为了填补空缺，要将宕机的服务器从编号列表中移除，后面的服务器按顺序前移一位并将其编号值减一，此时每个key就要按h = Hash(key) % 2重新计算。同样，如果新增一台服务器，规则也同样需要重新计算，h = Hash(key) % 4。因此，系统中如果有服务器更变，会直接影响到Hash值，大量的key会重定向到其他服务器中，造成缓存命中率降低，而这种情况在分布式系统中是十分糟糕的。一个设计良好的分布式哈希方案应该具有良好的单调性，即服务节点的变更不会造成大量的哈希重定位。一致性哈希算法由此而生~2 一致性哈希算法一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n 个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。简单的说，一致性哈希是将整个哈希值空间组织成一个虚拟的圆环，如假设哈希函数H的值空间为0-2^32-1（哈希值是32位无符号整形），整个哈希空间环如下：整个空间按顺时针方向组织，0和2^32-1在零点中方向重合。接下来，把服务器按照IP或主机名作为关键字进行哈希，这样就能确定其在哈希环的位置。然后，我们就可以使用哈希函数H计算值为key的数据在哈希环的具体位置h，根据h确定在环中的具体位置，从此位置沿顺时针滚动，遇到的第一台服务器就是其应该定位到的服务器。例如我们有A、B、C、D四个数据对象，经过哈希计算后，在环空间上的位置如下：根据一致性哈希算法，数据A会被定为到Server 1上，数据B被定为到Server 2上，而C、D被定为到Server 3上。3 容错性和扩展性那么使用一致性哈希算法的容错性和扩展性如何呢？3.1 容错性假如RedisService2宕机了，那么会怎样呢？那么，数据B对应的节点保存到RedisService3中。因此，其中一台宕机后，干扰的只有前面的数据（原数据被保存到顺时针的下一个服务器），而不会干扰到其他的数据。3.2 扩展性下面考虑另一种情况，假如增加一台服务器Redis4，具体位置如下图所示：原本数据C是保存到Redis3中，但由于增加了Redis4，数据C被保存到Redis4中。干扰的也只有Redis3而已，其他数据不会受到影响。因此，一致性哈希算法对于节点的增减都只需重定位换空间的一小部分即可，具有较好的容错性和可扩展性4 虚拟节点前面部分都是讲述到Redis节点较多和节点分布较为均衡的情况，如果节点较少就会出现节点分布不均衡造成数据倾斜问题。例如，我们的的系统有两台Redis，分布的环位置如下图所示：这会产生一种情况，Redis4的hash范围比Redis3的hash范围大，导致数据大部分都存储在Redis4中，数据存储不平衡。为了解决这种数据存储不平衡的问题，一致性哈希算法引入了虚拟节点机制，即对每个节点计算多个哈希值，每个计算结果位置都放置在对应节点中，这些节点称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现，例如上面的情况，可以为每个服务节点增加三个虚拟节点，于是可以分为 RedisService1#1、 RedisService1#2、 RedisService1#3、 RedisService2#1、 RedisService2#2、 RedisService2#3，具体位置如下图所示：对于数据定位的hash算法仍然不变，只是增加了虚拟节点到实际节点的映射。例如，数据C保存到虚拟节点Redis1#2，实际上数据保存到Redis1中。这样，就能解决服务节点少时数据不平均的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。总结本文简要的介绍了一致性哈希算法，目前一致性哈希算法基本成为了分布式系统组件的标准配置，因此，我们十分有必要了解该算法。 作者-fangqing 广州芦苇科技Java开发团队芦苇科技-广州专业互联网软件服务公司抓住每一处细节 ，创造每一个美好关注我们的公众号，了解更多想和我们一起奋斗吗？lagou搜索“ 芦苇科技 ”或者投放简历到 server@talkmoney.cn 加入我们吧关注我们，你的评论和点赞对我们最大的支持