下面我们先通过一个案例来验证一下我们上面的说法。
例一
有两台Memcached做事。我们利用php来向Memcached中添加数据。
代码一
$MEMCACHE_SERVERS = array("192.168.5.111", //memcached1"192.168.5.102" //memcached2);$memcache = new Memcache();foreach($MEMCACHE_SERVERS as $server){$memcache->addServer ( $server ); //将两个台做事器地址都添加进连接池}$memcache->set("onmpw", 5);$memcache->set("jiyi", 4);
上面php代码实行往后，按照分布式系统事理来说该当两台做事器中都有key为onmpw和jiyi的数据，但是事实是这样吗，我们可以分别登录到两台做事上进行查看。
Connect 5.111# telnet 192.168.5.111 11211Trying 192.168.5.111...Connected to 192.168.5.111 (192.168.5.111).Escape character is '^]'.get jiyiVALUE jiyi 768 14ENDget onmpw //在5.111上并没有onmpw这条数据ENDConnect 5.102Trying 192.168.5.102...Connected to 192.168.5.102 (192.168.5.102).Escape character is '^]'.get onmpwVALUE onmpw 768 15ENDget jiyi //在5.102上同样是没有jiyi这条数据END
由此可见在Memcached的做事端并不去同步集群中的数据。
那数据又是怎么将不同的键值对分发到不同的节点上去的呢，这便是客户端所要实现的分布式了。在这里会涉及到一种算法——hash算法。这里面涉及到两种hash算法：一种是取余数打算分散，一种是同等性hash算法(Consistent Hashing)。同等性hash算法在 全面理解同等性哈希算法及PHP代码实现 这篇文章中有比较系统的表述。而对付取余数办法的表述却有欠详细，以是在这里对此做一个稍详细的表述，以填补那篇文章的不敷。
一样平常的hash算法——根据余数打算分散
首先是根据集群做事的节点数创建一个哈希表，然后根据键名打算出键名的整数哈希值，用该哈希值对节点数取余，末了根据余数在哈希表中取出节点。
根据余数在哈希表中取节点
个中在打算key的哈希值的时候利用的是CRC（循环冗余校验）。下面利用php简化的代码来进行解释
代码二
$nodes = array('node1','node2','node3'); //nodes代表做事器节点$keys = array('onmpw', 'jiyi', 'onmpw_key', 'jiyi_key', 'www','www_key'); //这是key值foreach( $keys as $key) {$crc = crc32($key); // CRC値$mod = $crc % ( count($nodes) );$server = $nodes[ $mod ]; // 根据余数选择做事器printf("%s => %s\n", $key, $server);}
首先求得key的crc值，然后和node的个数取余数。上面代码的实行结果如下
onmpw => node2jiyi => node2onmpw_key => node1jiyi_key => node2www => node1www_key => node3
根据上面的结果，我们看到onmpw、jiyi和jiyi_key分散到node2，onmpw_key和www分散到node1，www分散到node3。
php客户端分布式实现
在php实现的Memcache的客户端是支持余数分散这种算法的。下面我们来看一下其源码中涉及该算法的部分。这里利用的php-memcache版本为memcache-3.0.6
mmc_t mmc_standard_find_server(void s, const char key, unsigned int key_len TSRMLS_DC) { mmc_standard_state_t state = s; if (state->num_servers > 1) { / "new-style" hash / //打算key值的哈希值 unsigned int hash = (mmc_hash(state->hash, key, key_len) >> 16) & 0x7fff; //用得到的哈希值对节点数取余 return state->buckets[(hash ? hash : 1) % state->num_buckets];}return state->buckets[0];}
我们看到，打算hash值的办法是利用mmc_hash()函数得到一个值，然后将该值向右移动16位，末了再和0x7fff做‘与’运算。
这里我们在看mmc_hash()是如何打算key的值的。
#define mmc_hash(hash, key, key_len) ((hash)->finish((hash)->combine((hash)->init(), (key), (key_len))))
太坑了，这算神马函数？各位先不要焦急，这里无非是一个宏定义，可以大略的认为mmc_hash(hash, key, key_len)实在便是一个值，这个值是什么呢？是由((hash)->finish((hash)->combine((hash)->init(), (key), (key_len))))来得到的。实在紧张的部分还是finish()、combine()和init()函数。我们来看这三个函数的实现。
上面三个函数由以下构造体定义
typedef struct mmc_hash_function {mmc_hash_function_init init;mmc_hash_function_combine combine;mmc_hash_function_finish finish;} mmc_hash_function_t;
同时对付mmc_hash_function_t做了如下的映射
extern mmc_hash_function_t mmc_hash_crc32;
也便是说这些函数的实现是在mmc_hash_crc32中实现的。连续追寻，创造下面的代码
mmc_hash_function_t mmc_hash_crc32 = {mmc_hash_crc32_init,mmc_hash_crc32_combine,mmc_hash_crc32_finish };
追根寻底，实在init()、combine()和finish()函数分别对应mmc_hash_crc32_init()、mmc_hash_crc32_combine()和mmc_hash_crc32_finish()。下面看这些函数的实现
static unsigned int mmc_hash_crc32_init() { return ~0; }static unsigned int mmc_hash_crc32_finish(unsigned int seed) { return ~seed; }static unsigned int mmc_hash_crc32_combine(unsigned int seed, const void key, unsigned int key_len){const char p = (const char )key, end = p + key_len;while (p < end) { CRC32(seed, (p++));}return seed;}
在上面的代码中我们是不是看到了熟习的身影。底层的实现也是用的crc32函数（该函数在php源码的ext/standard/crc32.h中有定义，有兴趣的可以去研究一下）。顺便多说一句，在mmc_hash_crc32_init()函数中返回的值是~0，它的值为-1。而’~’表示是按位取反。在定义函数的返回值的类型时是unsigned（无符号）的。以是-1的二进制表示为11111111111111111111111111111111（统共32位）。
我们看到，利用余数打算的实现方法很大略，而且其数据也是比较分散的。但是这种办法也是有很大的毛病的，当我们须要横向扩展节点的时候，缓存重组的代价也是非常大的。下面我们修正代码二，在nodes中添加node4。
代码三
$nodes = array('node1','node2','node3','node4'); //nodes代表做事器节点$keys = array('onmpw', 'jiyi', 'onmpw_key', 'jiyi_key', 'www','www_key'); //这是key值foreach( $keys as $key) {$crc = crc32($key); // CRC値$mod = $crc % ( count($nodes) );$server = $nodes[ $mod ]; // 根据余数选择做事器printf("%s => %s\n", $key, $server);}
再次运行代码创造其结果如下
onmpw => node4jiyi => node4onmpw_key => node3jiyi_key => node3www => node2www_key => node3
我们看上面的结果，创造只有www_key命中了。像这种情形在添加节点的时候命中率降落，当添加Memcached做事器的时候缓存效率会瞬间降落，这时候负载汇合中到数据库的做事器上面，从而有可能导致数据库由于瞬间压力过大而无法供应正常的做事。
以是说，还须要一种新的办法来办理集群横向扩展的问题。因此随着该问题的涌现，新的分布式方法也出身了——同等性Hash算法（Consistent Hashing）。
Consistent Hashing
同等性hash算法和一样平常的hash算法一样，都是对集群中的节点建立一个字典。由于该算法在Consistent Hashing算法入门及php实现 这篇文章中有详细的描述，并且有大略的php代码的实现，以是本章不再对Consistent Hashing有过多的赘述。
和一样平常的hash算法不同的是该办法相对来说在有节点添加或减少的时候能最大限度的减少数据的移动。也便是说命中率会有相称大的提高。那它是怎么来实现的呢？
首先求出memcached做事器（节点）的哈希值， 并将其配置到0～1的圆上。 然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个做事器上。 如果超过1仍旧找不到做事器，就会保存到第一台memcached做事器上。
详细在PHP-Memcache客户端中的实当代码的核心部分如下
void mmc_consistent_add_server(void s, mmc_t mmc, unsigned int weight){ mmc_consistent_state_t state = s;int i, key_len, points = weight MMC_CONSISTENT_POINTS;unsigned int seed = state->hash->init(), hash; / buffer for "host:port-i\0" /char key = emalloc(strlen(mmc->host) + MAX_LENGTH_OF_LONG 2 + 3);key_len = sprintf(key, "%s:%d-", mmc->host, mmc->tcp.port);seed = state->hash->combine(seed, key, key_len);/ add weight MMC_CONSISTENT_POINTS number of points for this server // 申请保存所有节点及其各自的虚拟节点的空间 /state->points = erealloc(state->points, sizeof(state->points) (state->num_points + points));for (i=0; i<points; i++) { key_len = sprintf(key, "%d", i); // 对每个节点及虚拟节点打算hash值 hash = state->hash->finish(state->hash->combine(seed, key, key_len)); // 保存个虚拟节点的hash值和该节点的信息 state->points[state->num_points + i].server = mmc; state->points[state->num_points + i].point = hash;} state->num_points += points; state->num_servers++; state->buckets_populated = 0; efree(key); }
上面的代码是对做事节点的分散，使每个节点及其各自的虚拟节点随机的均匀分布在圆上。
mmc_t mmc_consistent_find_server(void s, const char key, unsigned int key_len TSRMLS_DC){mmc_consistent_state_t state = s; if (state->num_servers > 1) { unsigned int hash; if (!state->buckets_populated) { mmc_consistent_populate_buckets(state); } //打算key的hash值 hash = mmc_hash(state->hash, key, key_len); return state->buckets[hash % MMC_CONSISTENT_BUCKETS];}//没有找到相应的做事节点，则返回第一个节点return state->points[0].server;}
这段核心代码是在存储一个键值对的时候根据该键值对的key去探求要存储的做事节点。同样的，是对key值进行hash打算，然后根据打算出的hash值，该key肯定也会分布在圆的某个位置上，然后从该位置开始顺时针查找将要碰着的第一个做事节点。如果一贯到末端都没有碰着做事节点，则直接返回第一个做事节点。这也便是 return state->points[0].server的意义所在。
总结：以上两种办法都在PHP-Memcache客户端中已经实现。还是那句话，对付Memcached的分布式思想都是在客户端中表示的。不同的客户端实现的办法可能有所不同，但是相信基本思想都是一样的。 同时也欢迎大家能给出不同的见地。
