背景
09 年初，我们做了一个 memcached 的智能客户端库，业务只要将这个库链上，就能跟 memcached 服务器通信。并且实现了一致性哈希的分布式算法，后端 memcached 服务器可以无限制扩展，而且客户端能对 memcached 做自动故障转移以及恢复。
我们知道，在没有对数据做冗余存储的情况下，无论是一致性哈希还是求余数分布式算法，在新增或删除 memcached 节点时，命中率都会不同程度的降低。本文旨在解决当新增 memcached 节点时，如何保证命中率不变。
基本原理
当 新增一个 memcached 节点时，将该新节点的下一个节点的且属于该新节点的数据迁移过来。
上面的这个基本原理读起来可能会比较拗口，容我下面详细说明。
原理描述
如图 1 所示，假设当前哈希环上有 n 个 memcached 节点，记为 M 1 ~M n ，存储到这些节点上的数据的有效期都是一致的，记为 T e 。因此从图 1 可以看出，从 M 1 到 M k 区间的数据均从 M k 上存取。比如数据 K 1 ， K 2 ， K n 。
图1
当新增节点 M x 时，如图 2 所示。
图2
此时数据 K 1 ， K 2 从新节点 M x 读取不到的，但节点 M k 存储了这些数据，我们需要做的就是将这些数据迁移到新节点 M x 。
具体做法是：将新加入的节点 M x 标记为 N （ New ）状态，表示该节点是新增的。在 N 状态下读取数据 K 1 的步骤为：
1） 从 M x 读取数据，如果读取得到，则返回，否则进行 2 ）；
2） 从 M k 读取数据，如果读取不到，则返回，否则进行 3 ）；
3） 将读取到的数据 K 1 写入 M x ；
4） 将 K 1 从 M k 删除；
在 N 状态下，不断进行上面的 4 个步骤
因为数据的有效期是 T e ，所以在经过 T e 时间后， M k 上的数据随之自动失效了，此时将 M x 标记为 O （ Old ）状态，在 O 状态下，如果读取不到数据也立即返回，无需再次到它下一个节点尝试读取。
