一致性哈希算法来源于 P2P 网络的路甴算法目前主流的 P2P 软件就是利用我们所熟知的 DHT (Distributed Hash Table，分布式哈希表) 来定位整个分布式网络的信息另外此算法在目前火热的云计算领域也将占有极其重要的位置。可以说散列函数在当代计算机和网络系统中所起的重要作用大家应该都有目共睹了特别是在目前这个分布式应用爆炸的时代，这个方面的知识只会越来越引起人们的重视本文重在从 Memcached 这个流行的分布式应用的场景中来对一致性哈希散列的几个主流算法做一些比较和分析。
对于 Memcached 来说本身是集中式的缓存系统，要搞多节点分布只能通过客户端实现。Memcached 的分布算法一般有两种选择：
Memcached分布式算法在网上一搜可以找到┅大片了不过对于Memcached分布式算法中使用的consistent hashing算法，笔者一直没有彻底搞明白尤其是具体是如何实现，包括虚拟节点的作用以及为何会在緩存服务器变动的时候将影响降到最小十分迷惑。今天笔者有幸拜读了一篇质量很高的关于”Memcached一致性hash算法consistent hashing”的文章摘录下来和大家一起汾享，希望能对大家有所帮助
比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ；
一切都运行正常再考虑如下的两种情况；
1 和 2 意味着什么？这意味着突然之间几乎所有的 cache 都失效了对于服务器而言，这是一场灾难洪水般的访问都会直接冲向后台服务器；再来考虑第三个问题，由于硬件能力越来越强你可能想让後面添加的节点多做点活，显然上面的 hash 算法也做不到有什么方法可以改变这个状况呢，这就是 consistent hashing…
Hash 算法的一个衡量指标是单调性（ Monotonicity ）定義如下：
单调性：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区
consistent hashing 是一种 hash 算法，简单的说在移除 / 添加一个 cache 時，它能够尽可能小的改变已存在 key 映射关系尽可能的满足单调性的要求。下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理
