Algorithm

Memcache应用场景 基本场景 比如有 N 台 cache 服务器（后面简称 cache），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到N个cache; hash(object)%N 如下图： 这时，一切都运行正常，再考虑如下的两种情况： 一个 cache服务器m down掉了（在实际应用中必须要考虑这种情况），这样所有映射到cache m的对象都会失效，怎么办，需要把cache m从cache 中移除，这时候 cache 是 $N-1$ 台，映射公式变成了 hash(object)%(N-1) 。此时数据 $3%3-1=3%2=1$ 此时，3应该在S3上，但是由于S3down机导致到S1去取，这时会未命中。如下图 由于访问加重，需要添加 cache ，这时候 cache 是 $N+1$ 台，映射公式变成了 hash(object)%(N+1) 。1和2意味着突然之间几乎所有的 cache 都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器。$\frac{N-1} { N\times (N-1)}$ 即： 有N台服务器，变为 $N-1$ 台，即每 $N \times (N-1)$个数中，求余相同的只有 N-1 个。命中率为：$\frac{1}{3}$ 再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash 算法也做不到。 有什么方法可以改变这个状况呢，这就是 consistent hashing… 但现在一致性hash算法在分布式系统中也得到了广泛应用，研究过memcached缓存数据库的人都知道，memcached服务器端本身不提供分布式cache的一致性，而是由客户端来提供，具体在计算一致性hash时采用如下步骤： 首先求出memcached服务器（节点）的哈希值，并将其配置到 0～232 的圆（continuum）上。 然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。...