继续说 Memcached 的 Sharding
转载
曾经 [url=[archive=314]]写了一篇很啰嗦的文章[/url] 只为了说明求余这么大点事。我主要当时想的是数据库的分割，后来刘涛老拿我这方法的缺点说事，于是又想到用另外一种方法，跟这个差不多，但更适合动态增减 Memcached 的情况。
原来求余方法说的是，如果有大量的 key 存放在 n 台 server 上，应该是 crc32(key) % n，余几就放在第几台 server 上（当然，我说的是 0 起始）。额外还要说明一点 PHP 里的原始的 crc32 函数返回的是有符号 32 位整数，需要用 sprintf("%u" 来转成无符号的，范围在 0 到 2 ^ 32 - 1 = 4294967295 之间。
另一种方法也是用 crc32，不过不是求余而是除法，crc32(key) / 4294967295 会得到 0 - 1 之间的一个小数，在根据这个小数来决定放在哪台 server 上，假设你有 4 台 sever，那接收的 key 范围应该是以 1/4、2/4、3/4 分隔的 4 段，假设你要存储一个 key 叫“abcdef”，在 PHP 里 [incode]echo sprintf("%u", crc32("abcdef")) / 4294967295[/incode] 会得到一个小数 0.295138951227，在 1/4 和 2/4 之间，那应该放到第二台机器上。
[img][file=102][/img]
如果 server 数不变，这两种存法（后面简称求余法和小数法，这只是我起的土名，如果有人知道学名希望不惜赐教）几乎没有什么区别，问题就在于如果要新增几台机器的时候
一旦出现变化，求余法基本要完全乱套，比方说 7 台变成 9 台时候，余数根本没有规律可循，只有一种极特殊的情况（就像初中学的尺规做图只能给直角做三等分一样），就是变化后是变化前的倍数，而且最好是 2 倍，这时可以保证有 50% 的数据被保留，虽然还是很糟糕，但这已经是极限了。当然这仅仅是对于 Memcached 来说，如果是 MySQL 能停机十几分钟就好办了，停机后以最快速度（cp data 目录的方式）一对一复制出新增的一倍机器，启动 MySQL，这时候所有的 server 都有一半冗余数据，跑一个脚本删掉即可，因为总之那部分都不会被访问到，因此甚至可以在之后几天的空闲时间里慢慢删（如果举个具体的例子是这样，原有 2 台 server，分别装着余 0 和余 1 的 key，变成 4 台后假设原来 2 复制成 2、4 两台，新的两台分应该别装着余 1 和余 3 的 key，但这些 key 都是除 2 余 1 的子集。新 2 应该删掉余 3 的那部分，新 4 删掉余 1 的）
还拿刚开始说小数法的 4 台 server 的例子，如果新增第五台，我们把他放在列表中第四台的后面（之后会说明这是最错误的情况），各段的范围会有变化，原来是 1/4、2/4、3/4 分隔，现在是 1/5、2/5、3/5、4/5 分隔，比方说如果有 key 被做成小数后得 0.22，那么原来他是在 0 到 1/4 这个段，应该存在第一台 server，变化后就到了 1/5 到 2/5 这个段。想知道有多少 key 所在的 server 变化了，可能用图片解释更简单一些。
[img][file=103][/img]
两排线段分别表示 4 台和 5 台 server 的情况，而黄色的部分，表示在变化后还有多少数据保留在原 server 上，相信数学好的可以马上给函数出来了，可惜我只会四则运算，只能画这么个图了。
当然，我前面说过这么放是错误的，应该把新 server 5 放在 2 和 3 之间，这样可以保留的数据会变成这样。
[img][file=104][/img]
当 server 数量拓展到无穷大的时候，如果把一台新 server 放在原有列表的尾部和中间的时候，数据被保留的数量如下：
[img][file=105][/img]
如果放的不是一台，而是多台，情况可能是这样（分数表示新机器所处的位置，两条分别表示新机器全部放在列表尾部或放在合适位置这两种情况），但最多保留 3/4 的数据，这是可以肯定的了
[img][file=107][/img]
[hr]
还有一些其他的想法（只是想法，说不上经验）
如果某台 server 挂了，不要尝试重连（如果 memcached 没挂会让压力问题恶化，如果已经挂了还是浪费时间等超时）、不要尝试寻求替补 server（这跟 httpd 和 db 处理方式很不一样，当然我说的替补是指另外一台编号的机器，而非原机下线后的备份），cache 就是 cache，只是 db 的挡箭牌，cache 挂了就直接找 db，应该把精力集中在及时判断 memcached 出问题时及时重启、再有问题备份机跟上这些方面，假设命中比 80%，10 台 memcached，挂掉一台会让 MySQL 的压力提升 40%（(1 - 80% * 9/10) / (1 - 80%) - 1），但只持续最多 5 - 10 分钟，应该问题不是很大。
很重要的一条（也很好实现的一条），如果连接服务器失败，PHP 里应该相应的返回一个替补空对象来代替 new Memcache() 所生成的对象，这个替补对象具有原来对象所有的方法，只是所有方法都不做任何处理，直接返回 false（唯独 add 方法可能需要返回 true，自己体会），以实现之前所说的不要尝试重连。
有人跟我说过 [url=http://code.google.com/p/flexihash/]flexihash[/url] 或者别的什么算法，说实在的，我看不懂，也不想花时间看懂。仅根据大量随机 key 做测试的结果来看我就知道不是我想要的东西，也就没再细研究。
大体我明白其意思，在高度冗余的前提下保证服务器变化时损失最小（比方说电驴里的 KAD 这种应用），我所能接触到的规模，第一，服务器不会经常变化，第二，规模没大到需要为服务器多花很多钱买冗余的程度。比方说，同样多的数据，用 crc32 可能需要 10 台机器，用 flexihash 可能需要 20 台，不然由于木桶短板，有的 server 抗不住（哪怕不是说硬件负载，而仅仅是因为容量不够导致的命中比下降），但同样这 20 台，用 crc32 可能出问题的几率更小。等到 facebook 及以上级别需要为规模的诅咒多花钱了，但是，如果主要应用还局限在一个机房内，还是 crc32 更有效
不管怎么说，我都认为大家需要为 Memcached 做更多的探索，仅从 Sharding 的算法来说，旧有的针对 db 或者别的什么算法都不适合直接套在 Memcached 上，而有些问题的争议（比方前面说的连接失败时要不要继续选择别的 server）可能还未盖棺定论。