摘要：一致性算法与其他算法对比对于集群中缓存类数据的节点分配问题，有这几种解决方法，简单的取模，槽映射，一致性。这显然是不可接受的。一致性一致性如上文所言，其新增一个节点的失效率仅为，通过一致性最大程度的降低了实效率。
概述
这里存在一种场景, 当一个服务由多个服务器组共同提供时, key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目), 这里乍一看没什么问题, 但是当服务器数目发送增加或减少时, 分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效迁移,如果后端key对应的是有状态的存储数据,那么毫无疑问,这种做法将导致服务器间大量的数据迁移,从而照成服务的不稳定. 为了解决类问题,一致性hash算法应运而生.
1. 一致性hash算法特点在分布式缓存中, 一个好的hash算法应该要满足以下几个条件:
均衡性(Balance)
均衡性主要指,通过算法分配, 集群中各节点应该要尽可能均衡.
单调性(Monotonicity)
单调性主要指当集群发生变化时, 已经分配到老节点的key, 尽可能的任然分配到之前节点,以防止大量数据迁移, 这里一般的hash取模就很难满足这点,而一致性hash算法能够将发生迁移的key数量控制在较低的水平.
分散性(Spread)
分散性主要针对同一个key, 当在不同客户端操作时,可能存在客户端获取到的缓存集群的数量不一致,从而导致将key映射到不同节点的问题,这会引发数据的不一致性.好的hash算法应该要尽可能避免分散性.
负载(Load)
负载主要是针对一个缓存而言, 同一缓存有可能会被用户映射到不同的key上,从而导致该缓存的状态不一致.
从原理来看,一致性hash算法针对以上问题均有一个合理的解决.
2. 一致性hash详解一致性hash的核心思想为将key作hash运算, 并按一定规律取整得出0-2^32-1之间的值, 环的大小为2^32，key计算出来的整数值则为key在hash环上的位置，如何将一个key，映射到一个节点， 这里分为两步.
第一步, 将服务的key按该hash算法计算,得到在服务在一致性hash环上的位置.
第二步, 将缓存的key，用同样的方法计算出hash环上的位置，按顺时针方向，找到第一个大于等于该hash环位置的服务key，从而得到该key需要分配的服务器。
如图， 各key根据hash算法分配到各节点，当某一节点失效实效时， 如NODE 2， 则NODE 2 上的key将分配到hash环上相邻的节点，而其他key所在位置不变。
虚拟节点提高均衡性
如上图可看到， 由于节点只有3个，存在某些节点所在位置周围有大量的hash点从而导致分配到这些节点到key要比其他节点多的多，这样会导致集群中各节点负载不均衡，为解决这个问题，引入虚拟节点， 即一个实节点对应多个虚拟节点。缓存的key作映射时，先找到对应的虚拟节点，再对应到实节点。如下图所示， 每个节点虚拟出两个虚拟节点，从而提高均衡性。
3. 一致性hash算法与其他算法对比对于集群中缓存类数据key的节点分配问题，有这几种解决方法，简单的hash取模，槽映射，一致性hash。
hash取模
对于hash取模，均衡性没有什么问题，但是如果集群中新增一个节点时，将会有N／（N+1）的数据实效，当N值越大，失效率越高。这显然是不可接受的。
槽映射
redis采用的就是这种算法, 其思想是将key值做一定运算（如crc16， crc32，hash）， 获得一个整数值，再将该值与固定的槽数取模（slots）， 每个节点处理固定的slots。获取key所在的节点时，先要计算出key与槽的对应关系，再通过槽与节点的对应关系找到节点，这里每次新增节点时，只需要迁移一定槽对应的key即可，而不迁移的槽点key值则不会实效，这种方式将失效率降低到了 1／（N+1）。不过这种方式有个缺点就是所有节点都需要知道槽与节点对应关系，如果client端不保存槽与节点的对应关系的话，它需要实现重定向的逻辑。
一致性hash
一致性hash如上文所言，其新增一个节点的失效率仅为1／（N+1），通过一致性hash最大程度的降低了实效率。同时相比于槽映射的方式，不需要引人槽来做中间对应，最大限度的简化了实现。
4. 基于golang的一致性hash算法实现这里讲采用golang实现一致性hash，考虑到实际使用场景中，存在服务节点之间机器配置可能不一样，因此提供了基于节点权重进行虚拟节点再分配的逻辑，从而尽可能让权重高的节点多承担一些key，而权重低的节点少承担一些key，当然这里权重的计算也涉及到较多东西，代码见：
https://github.com/g4zhuj/has...
本文分析了一致性性hash的原理，并与其它的分布式集群分配算法进行了对比，从分布式缓存的角度来说，两大出名的分布存储系统redis， memcached分别采用了槽映射，及一致性hash来实现，由于采用的算法不同，集群中节点变更时所触发的一系列动作也不尽相同，各有各的考虑。
6.参考Consistent Hasing https://en.wikipedia.org/wiki...
Redis Cluster https://redis.io/topics/clust...
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/36516.html
摘要：好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。一致性哈希算法的基本实现原理是将机器节点和值都按照一样的算法映射到一个的圆环上。 一致性 hash 分布式过程中我们将服务分散到若干的节点上，以此通过集体的力量提升服务的目的。然而，对于一个客户端来说，该由哪个节点服务呢？或者说对某个节点来说他分配到哪些任务呢？ 强哈希 考虑到单服务器不能承载，因此使用了分布式架构，最初...
摘要：前言在上一章中我们介绍了的一些内部原理在这一章中我们再来讨论在五种数据结构中的基本使用和一些内部实现基本介绍的呢相当于中的也是双向链表具有一些和同样的特征比如插入和删除一条很快时间复杂度为获取头结点和尾节点也很快时间复杂度也为随机读取则相对 前言 在上一章中我们介绍了 String 的一些内部原理,在这一章中我们再来讨论在五种数据结构中 List 的基本使用和一些内部实现. 基本介绍 ...
摘要：前言在上一章中我们介绍了的一些内部原理在这一章中我们再来讨论在五种数据结构中的基本使用和一些内部实现基本介绍的呢相当于中的也是双向链表具有一些和同样的特征比如插入和删除一条很快时间复杂度为获取头结点和尾节点也很快时间复杂度也为随机读取则相对 前言 在上一章中我们介绍了 String 的一些内部原理,在这一章中我们再来讨论在五种数据结构中 List 的基本使用和一些内部实现. 基本介绍 ...
摘要：方向课程内容作为一个支持协议，以某种支持事务的分布式存储引擎为底层存储的引擎，主要需要处理与客户端的交互，在底层存储引擎中存取数据，以及实现功能。课程设置上分为两个方向，分别是面向引擎的方向和面向大规模一致性的分布式存储的方向。 作者：谢海滨 在 上篇文章 中我们介绍了 PingCAP Talent Plan - TiKV 方向的课程内容，本文将从课程设计的角度和大家聊一聊 TiDB ...
摘要：为程序员金三银四精心挑选的余道面试题与答案，欢迎大家向我推荐你在面试过程中遇到的问题我会把大家推荐的问题添加到下面的常用面试题清单中供大家参考。 为Java程序员金三银四精心挑选的300余道Java面试题与答案，欢迎大家向我推荐你在面试过程中遇到的问题,我会把大家推荐的问题添加到下面的常用面试题清单中供大家参考。 前两天写的以下博客，大家比较认可，热度不错，希望可以帮到准备或者正在参加...
阅读 603·2021-09-26 09:55
阅读 1808·2021-09-22 15:44
阅读 1278·2019-08-30 15:54
阅读 1170·2019-08-30 15:54
阅读 2532·2019-08-29 16:57
阅读 350·2019-08-29 16:26
阅读 2386·2019-08-29 15:38
阅读 2181·2019-08-27 14:19
