Memcached一致性哈希分布式算法

memcached是什么？

memcached是一个高性能，分布式内存对象缓存系统，具备通用性，但本来的目的是用于为动态web程序加速，并减轻数据库的负担

键与服务器的对应关系

分布式之取模算法的缺陷

取模算法（最容易想的，但是不适合做集群使用）：有两台服务器的话，key转成数字，对2取模，摸为N，则放第N台服务器

分布式算法之取模算法

假设有8台服务器，运行中突然down一台，则求余的底数变成7

后果 :

key 0%8=0，key0%7=0 (hits)

...

key6 %8=6，key6%7=6 (hits)

key9 %8==1 ,key9%7==2 (miss)

...

key55%8=7   ,key55%7=6 (miss)

key56%8=0，key56%7=0 (hits)

一般的，我们从数学上归纳之

有N台服务器，变为N-1台

每N*(N-1)个数中，求余相同的数字只有N-1个数字

所以命中率在服务器down的短期内，急剧下降至(n-1)/(n*(n-1))=1/n

所以服务器越多，则down机的后果越严重

Consistent Hashing原理： 

首先求出memcached服务器（节点）的哈希值，并将其配置到0-2^32的圆上

然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。

然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过2^32，任然找不到服务器，就会保存到第一台memcached服务器上。

解决一台down后，负担均匀分配到其他服务器上。

需要一个把字符串转成整数的功能

Memcached面试题

我们查询缓存怎么做（memcached），如何做缓存设计，另外，考虑如果其中某台机器突然down了，又要保证query的命中率，有什么好的方案？

Memcached更多知识点