php-memcache扩展分析(三)一致性哈希分布实现

标签:

搬运自之前留在oschina上的文章

首先明确:

Memcache::addServer()增加一个服务器到连接池中。通过Memcache::addServer()
打开的连接将会在脚本执行结束后自动关闭,也可以使用Memcache::close()进行手动关闭。
您也可以使用memcache_add_server()来添加服务器。
当使用这个方法的时候(与Memcache::connect()和Memcache::pconnect()相反)
网络连接并不会立刻建立,而是直到真正使用的时候才建立。 因此在加入大量服务器到连接池中时也是没有开销的,因为它们可能并不会被使用。

所以在看到服务器节点在圆环上的分布情况,需要先add一个缓存。

当add是发生初始化连接池操作,初始化连接池的代码:链接

<!-- lang: cpp -->
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);//这个函数用来初始化一致性哈希的连接池
        }
        
        hash = mmc_hash(state->hash, key, key_len);//这里可以看到 将缓存值的key哈希后得到一个数
            /** 和圆环上的虚节点数量取余,找到对应服务器节点,取出服务器连接信息 **/
        return state->buckets[hash % MMC_CONSISTENT_BUCKETS];
    }

    return state->points[0].server;//当缓存服务器只有一台时取唯一的服务器节点映像。
}

那么,从这里我们就可以看出一致性哈希的圆环上总共多少虚节点。链接

<!-- lang: cpp -->
#define MMC_CONSISTENT_BUCKETS  1024        /* number of precomputed buckets, should be power of 2 */

结论,虚节点数是个整数,总共1024个。

连接池初始化

<!-- lang: cpp -->
static void mmc_consistent_populate_buckets(mmc_consistent_state_t *state) /* {{{ */
{
    unsigned int i, step = 0xffffffff / MMC_CONSISTENT_BUCKETS;

    qsort((void *)state->points, state->num_points, sizeof(mmc_consistent_point_t), mmc_consistent_compare);
    for (i=0; i<MMC_CONSISTENT_BUCKETS; i++) {
        state->buckets[i] = mmc_consistent_find(state, step * i);
    }

    state->buckets_populated = 1;
}

前面我们已经知道一致性哈希的范围是 0 ~ 0xfffffffe 即 0 ~ 2^32-1。

step 是计算每个节点之前的步长(距离)。

现将之前addServer时生成的节点映像 按 hash值排序。为什么排序?因为后面用到了折半查找。

state->buckets[i] = mmc_consistent_find(state, step * i); 这句就是节点位置得到的对应的缓存节点。

mmc_consistent_find

<!-- lang: cpp -->
static mmc_t *mmc_consistent_find(mmc_consistent_state_t *state, unsigned int point) /* {{{ */
{
    int lo = 0, hi = state->num_points - 1, mid;

    while (1) {
        /* point is outside interval or lo >= hi, wrap-around */
        if (point <= state->points[lo].point || point > state->points[hi].point) {
            return state->points[lo].server;
        }

        /* test middle point */
        mid = lo + (hi - lo) / 2;

        /* perfect match */
        if (point <= state->points[mid].point && point > (mid ? state->points[mid-1].point : 0)) {
            return state->points[mid].server;
        }

        /* too low, go up */
        if (state->points[mid].point < point) {
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
}

关于折半查找算法(链接)没什么好说的。需要注意的是:

<!-- lang: cpp -->
int lo = 0, hi = state->num_points - 1;
if (point <= state->points[lo].point || point > state->points[hi].point) {
    return state->points[lo].server;
}

因为我们知道,hash(key) 落到圆环上找对应的缓存服务器时是顺时针查找,这段代码就保证了顺时针查到最后节点到 2^32-1之间时缓存数据能够落到第一个服务器节点。

目前为止我们已经看到了一致性哈希的实现 和 一致性哈希的圆环上缓存节点的分布。因为哈希的不确定性,每个缓存服务器所属的节点在圆环上是否是连续性的呢?每个缓存服务器能分配多少个节点呢?

下篇文章,我们来做实验,我给php-memcache扩展增加了两个函数来验证这两个问题。


评论已关闭