摘要：好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。一致性哈希算法的基本实现原理是将机器节点和值都按照一样的算法映射到一个的圆环上。
一致性 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 所示:
图 1 中 Key K 的哈希值在 A 与 B 之间，于是 K 就由节点B来处理。
另外具体机器映射时，还可以根据处理能力不同，将一个实体节点映射到多个虚拟节点。
经过一致性哈希算法散列之后，当有新的机器加入时，将只影响一台机器的存储情况，
例如新加入的节点H的散列在 B 与 C 之间，则原先由 C 处理的一些数据可能将移至 H 处理，
而其他所有节点的处理情况都将保持不变，因此表现出很好的单调性。
而如果删除一台机器，例如删除 C 节点，此时原来由 C 处理的数据将移至 D 节点，而其它节点的处理情况仍然不变。
而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法，因此也很好得降低了分散性和负载。
而通过引入虚拟节点的方式，也大大提高了平衡性。
实现代码consitent-hashing原文地址
consitent-hashing
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/76734.html
摘要：一致性哈希算法能尽可能减少了服务器数量变化所导致的缓存迁移。哈希算法首先，一致性哈希算法依赖于普通的哈希算法。我们以下面四个量化的指标对基于不同哈希函数的一致性哈希算法进行评测。 一致性哈希算法在分布式缓存领域的 MemCached，负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用，它主要是为了解决传统哈希函数添加哈希表槽位数后要将关键字重新映射的问题。 本文会介绍一...
摘要：是我们一直拥有的，即我们有，。中的迭代器中的迭代器主要包括方法。在遍历过程中，如果已经遍历的数组上的内容变化了，迭代器不会抛出异常。这就是迭代器弱一致的表现。总结的弱一致性主要是为了提升效率，是一致性与效率之间的一种权衡。 本文将用到Java内存模型的happens-before偏序关系（下文将简称为hb）以及ConcurrentHashMap的底层模型相关的知识。happens-be...
摘要：不允许隐式转换的是强类型，允许隐式转换的是弱类型。拿一段代码举例在使用调用函数的时候会先生成一个类模板运行时生成，执行的时候会生成类模板，执行的时候会生成类模板。 0 x 01 引言 今天和一个朋友讨论 C++ 是强类型还是弱类型的时候，他告诉我 C++ 是强类型的，他和我说因为 C++ 在写的时候需要 int，float 等等关键字去定义变量，因此 C++ 是强类型的，我告诉他 C+...
摘要：数据结构和算法树快速排序，堆排序，插入排序其实八大排序算法都应该了解一致性算法，一致性算法的应用的内存结构。如何存储一个的。八大排序算法一定要手敲一遍快排，堆排尤其重要。面试是一个双向选择的过程，不要抱着畏惧的心态去面试，不利于自己的发挥。 前言 16年毕业到现在也近两年了，最近面试了阿里集团（菜鸟网络，蚂蚁金服），网易，滴滴，点我达，最终收到点我达，网易offer，蚂蚁金服二面挂掉，...
阅读 865·2023-04-25 14:35
阅读 819·2021-11-22 15:28
阅读 2664·2021-11-16 11:45
阅读 3201·2021-09-04 16:48
阅读 2064·2021-08-10 09:43
阅读 317·2019-08-30 13:17
阅读 1504·2019-08-29 13:27
阅读 880·2019-08-27 14:20
