分布存储的基本方法
作者：郑凯
就是在数据量变得单机难以承受（比方说 MySQL 上千万行、或者 Memcache 的用量超过 4G 而你用的服务器又都是 32 位机）的时候，可以通过很简单的一点小改动来让现有程序架构提升一两个数量级
这是一个基础课程，整个内容其实用两个词就可以概括了：hash、求余，通过将 key 转化成整数后求余，来决定数据装在哪个容器里。能明白不用继续看了。为了让尽可能的人看明白，我写的比较冗长。
最初是听说微软的 passport 是用的注册 E-mail 的 md5 来分割并存储帐号，当时还很傻的认为只能按 16 组或者 256 组（就是取前一个或者前两个字母的样子），经车东提醒才知道 crc32 更方便些，而且终于解明白了“进制”这个结
[hr]
[b]求余[/b]
从原理上应该倒着说，先说求余。举个现实点的问题，假设一个投票功能，像那些电视里常出现的肥皂节目一样，通过手机短信投票，但是可能是经理脑子灌水了，他说每个手机号只允许投一票，又假设这次投票超级火，高峰时段的访问量极大，又需要实时在电视上显示投票数，磁盘 I/O 已经成为瓶颈，你需要有缓存，最佳方案只能用 Memcache 来作为检查重复的工具了，每当来了一条短信，你都像这么访问一下 Memcache：
[phpcode]
$bValid = $oMemcache->add("13012345678", 1);
[/phpcode]
以手机号作为为 key，通过 add 方法存入内存，同一个 key 只能 add 一次（可以无限更新的那叫 set），当你得到 $bValid = FALSE 也就意味着这个手机号之前已经投过票了，是无效的。
现在问题来了，假设服务器都是三年前的配置，内存都是 1G 内存，实际 Memcache 只能使用其中 800MB，你预计需要 1.2G 才能确保万无一失，现在已经来不及去那外地的机房给机器加内存，最多再临时抽调给你一台和之前一样配置的机器。你该怎么办？
肯定要把所有的手机号分成两组，分别存进两台服务器，这样哪台服务器也不会溢出。怎么分？这还不好说，奇数一组，偶数一组，不就得了。
表面看起来是位数 1 3 5 7 9 一组，2 4 6 8 0 一组，但实际上偶数的定义是，能否被 2 整除，而任何数被 2 除都只有两种余数，0 和 1，因此实际的规律就通过于是，把手机号（key）通过除 2 求余，根据余数来决定存进标签为 0 或者为 1 的那台服务器的 Memcache 里。
我之前没意识到的问题是，我总想通过个位数来决定分配，因此只能存进指定的 10 或者 16 个容器（Memcache、MySQL）里，实际上取个位数是类似 1000 除以 10，或者 16 进制 FFFF 除以 F 的一种特殊情况。我当时忽略问题的实质，求余。
现在你会明白如何把那些手机号如何装进 3 个或者更多任意数量的 Memcache Server 里了，但假设你要缓存的不是手机号、而是 E-mail、昵称 呢？或者更麻烦些的，如果是命你给一个访问量奇大的论坛增加防止重复回复的功能呢（天啊，我终于举出一个有实际意义的例子了）
[b]Hash[/b]
md5 应该都知道吧？通过 PHP 函数 md5 和 md5_file，你可以把任意字符串或者文件（其实文件就是一个超长字符串，如果不考虑效率问题，你可以认为 md5_file($sFilename) == md5(file_get_contents($sFilename))）变成一个 32 位长的 16 进制数（HEX），你可以用 hexdec 把他转换成 10 进制数，实际上这个数太大了，大到毫无意义。那就用 substr() 来截取前几位吧，比方说截 8 位。PHP 里是这么个过程：
[phpcode]
$sMD5 = md5("abcd"); // $sMD5 = "e2fc714c4727ee9395f324cd2e7f331f"
$sMD5 = substr($sMD5, 0, 6); // $sMD5 = "e2fc71"
$iHash = hexdec($sMD5); // $iHash = 14875761
$iServer = $iHash % 7; // $iServer = 5
[/phpcode]
即字符串 abcd 如果是分 7 个 server 来装，应该存在第 6 个 server 里（从 0 起始的）
回到这节之前的那个问题，如果任何一个字符串 key 能简单转换成整数用来求余，那不就可以轻松的决定他们都存在哪个 Memcache Server 里了？
再说防止重复回复，实际就是判断 $sMD5 = md5($帖子id."\n".$用户id."\n".$用户回复内容) 经过处理后的那个整数求余来决定存在哪个服务器，存的内容是 add($sMD5, 1)。
不要担心 md5 可能有重复（碰撞），因为你根本理解不了 16 的 32 次方是个多大的数（十进制是 1 后面 77 个 0），如果你想稳妥的验证一下是否会有碰撞遍，可以遍历你的（或者所有你认识的人的）硬盘，所有的文件 md5 一遍看看会不会有重复。一千万个不同字符串里有冲撞的几率，大约相当于连续一个月每期都是只买一张彩票就中 500万。
hash 这个词的词义是“混乱”。信息摘要类算法的基本目的就是，让所有的整数（字符串可以写成十六进制形式再转成十进制的，进而一切信息你都可以认为是超长大整数）都尽可能散列并分布在一个指定的范围内，我们要的只是这个性质，算法高级与否、可逆不可逆已经无所谓了。因此 crc32 是最合适的，在 PHP 里他是直接返回一个有符号的整数，而不用像我上面说的用 substr 了的 md5 再 hexdec 来产生整数求余。当然，key 还是需要用 md5 来避免碰撞的。
这里还隐藏的一个问题是，各容器的使用率不可能是绝对平均，但是偏差已经很小了，实际上每条数据和容器容量之间的比率越大（就是装的数量越多），浪费的可能性就越小。计算出浪费的概率也不是太难，要较真的话自己算一下吧
[hr]
我认为即使是在程序员里，大部分人的数学也不是很好（好吧，包括我在内）。针对本文题目我分成了“hash”“求余”两块。其实更基础、更重要的知识还有两条：
1. 之前所说的，万物（任何信息）皆整数（你可以抬杠，把所有整数再加个“0.”然后说万物皆 0 到 1 之间的小数）
2. 真正理解“进制”的含义。我觉得在招聘的时候，面试第一道题目：用笔算，把一个 6 位的 7 进制数转成 13 进制的，估计能轻松档掉很多人……
[hr]
这一部分是一个实例，我现在正在用的一个扩展的 Memcache 类，叫 Memcache[b][color=red]z[/color][/b]，用于多 server 的目的而写，里面还添了点出于自己喜好而使用的风格。使用的方法是填装一个数组形式的 server 群，之后就可以基本照常 add/set/get 了
[phpcode]
$cfg["cache"] = array(
"192.168.0.8:11211",
"192.168.0.9:11211",
);
$oCache = new Memcachez($cfg["cache"]);
[/phpcode]
类代码如下：
[phpcode]
/*
* MemCacheZ
*
* 多台服务器时自动根据 key 的 crc32 值来选择相应服务器
*
* Zheng Kai 2007-04-29 18:28:10
*/
/*
method:
setCompress (boolean) 是否使用 gzip 压缩（add/set/replace）
setExpire (int) 设置过期时间
add
set
get
replace
increment
decrement
以上这些照常使用
不过注意 add/set/replace 这三个方法的原第三个参数（是否 zlib 压缩）已经省略，
由最后一次 setCompress 来决定；最后一个参数 iExpire 如果为空则沿用 setExpire
的设置，如果都不填，则缺省的默认时间为一小时
*/
class Memcachez {
protected $aLink = array();
protected $aServerList = array();
protected $iServerNumber = 3;
protected $iCompress = 0;
protected $iCompressNow = 0;
protected $iExpire = 3600;
protected $iExpireNow = 3600;
protected $iServerNow = -1;
function __construct($aServerList) {
$this->aServerList = array_values($aServerList);
$this->iServerNumber = count($aServerList);
}
public function setCompress($sSwitch = "") {
if (empty($sSwitch)||(strtolower($sSwitch) == "false")) {
$this->iCompress = 0;
} else {
$this->iCompress = MEMCACHE_COMPRESSED;
}
}
public function setExpire($iExpire) {
$iExpire = intval($iExpire);
if ($iExpire > 1) {
$this->iExpire = $iExpire;
}
}
// 选择 memcached server
protected function _selectServer($sKey, $bServerID = FALSE) {
if ($bServerID) {
$iServerID = intval($sKey);
} else {
$iServerID = sprintf("%u", crc32($sKey)) % $this->iServerNumber;
}
if (($this->iServerNow != $iServerID)&&(!array_key_exists($iServerID, $this->aLink))) {
$this->aLink[$iServerID] = new Memcache();
list($sHost, $iPort) = explode(":", $this->aServerList[$iServerID]);
$this->aLink[$iServerID]->connect($sHost, $iPort);
}
$this->iServerNow = $iServerID;
}
// 选择过期时间
protected function _selectExpire($iExpire) {
$this->iExpireNow = ($iExpire <= 0) ? $this->iExpire : $iExpire;
}
protected function _selectCompress($iCompress) {
$this->iExpireNow = ($iCompress <= 0) ? $this->iCompressNow : $iCompress;
}
// add
public function add($sKey, $sValue, $iExpire = 0, $iCompress = 0) {
$this->_selectServer($sKey);
$this->_selectExpire($iExpire);
$this->_selectCompress($iCompress);
return $this->aLink[$this->iServerNow]->add($sKey, $sValue, $this->iCompressNow, $this->iExpireNow);
}
// set
public function set($sKey, $sValue, $iExpire = 0, $iCompress = 0) {
$this->_selectServer($sKey);
$this->_selectExpire($iExpire);
$this->_selectCompress($iCompress);
return $this->aLink[$this->iServerNow]->set($sKey, $sValue, $this->iCompressNow, $this->iExpireNow);
}
// replace
public function replace($sKey, $sValue, $iExpire = 0, $iCompress = 0) {
$this->_selectServer($sKey);
$this->_selectExpire($iExpire);
$this->_selectCompress($iCompress);
return $this->aLink[$this->iServerNow]->replace($sKey, $sValue, $this->iCompressNow, $this->iExpireNow);
}
// get
public function get($sKey) {
$this->_selectServer($sKey);
return $this->aLink[$this->iServerNow]->get($sKey);
}
// delete
public function delete($sKey, $iTimeout = 0) {
$this->_selectServer($sKey);
return $this->aLink[$this->iServerNow]->delete($sKey, $iTimeout);
}
// increment
public function increment($sKey, $iValue) {
$this->_selectServer($sKey);
return $this->aLink[$this->iServerNow]->increment($sKey, $iValue);
}
// decrement
public function decrement($sKey, $iValue) {
$this->_selectServer($sKey);
return $this->aLink[$this->iServerNow]->decrement($sKey, $iValue);
}
// getStats
public function getStats() {
$aStats = array();
foreach ($this->aServerList as $iKey => $sValue) {
$this->_selectServer($iKey, TRUE);
$aStats[$sValue] = $this->aLink[$iKey]->getStats();
}
return $aStats;
}
// flush
public function flush() {
foreach ($this->aServerList as $iKey => $sValue) {
$this->_selectServer($iKey, TRUE);
$this->aLink[$iKey]->flush();
}
}
}
[/phpcode]