php-memcache扩展分析(二) 一致性哈希初阶

标签:

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

memcached不能算是分布式缓存系统,因为每个缓存节点之间是相互不可感知的,要实现分布式缓存需要借助客户端实现,而实现分布式缓存的关键在于katama算法。

###一致性哈希
一致性哈希,即katama算法。其中几个关键点是:

  1. 虚节点
  2. 0 ~ 2^32-1 的圆环
  3. 顺时针查找服务器
  4. hash(key)超过2^32-1 则缓存在第一台服务器

具体怎么实现的,大家去谷歌吧~ 我贴两张经典图片看下。

ketama算法

ketama算法

新增缓存节点

新增缓存节点

那么问题就来了:

  1. 到底多少个虚节点?
  2. 怎么哈希?
  3. katama算法在php-memcache扩展中如何实现?
  4. 每次hash(key)之后和2^32-1取余?
  5. hash(key)怎么找到对应的缓存服务器?
  6. 什么参数会影响服务器在圆环上的位置?
  7. 缓存节点在“圆环”上怎么分布的?
  8. 怎么预估每个节点的缓存数据量?

本系列文章主要是针对php-memcache扩展而言。
源码地址:http://git.oschina.net/moxi/php-memcache-test
基于php-memcache扩展,分析扩展中使用的一致性哈希算法
master分支是原始版本3.0.8 beta
master-test 分支是基于原始版本的测试版本,增加了测试方法

关于Memcache和MemcachePool类

先看两个类的初始化:地址

INIT_CLASS_ENTRY(ce, "MemcachePool", php_memcache_pool_class_functions);
memcache_pool_ce = zend_register_internal_class(&ce TSRMLS_CC);

INIT_CLASS_ENTRY(ce, "Memcache", php_memcache_class_functions);
memcache_ce = zend_register_internal_class_ex(&ce, memcache_pool_ce, NULL TSRMLS_CC);

我们看到两个类分别被注册,并且,Memcache类共用了MemcachePool类的方法。

再看两个类的方法定义: MemcachePool类Memcache类

区别的地方是 Memcache类独有的以下方法

<!-- lang: cpp -->
static zend_function_entry php_memcache_class_functions[] = {
PHP_FALIAS(connect,                 memcache_connect,                   NULL)
PHP_FALIAS(pconnect,                memcache_pconnect,                  NULL)
PHP_FALIAS(addserver,               memcache_add_server,                NULL)
{NULL, NULL, NULL}
};

关于测试用的Memcached信息

memcached服务版本:
STAT version 1.4.21
STAT libevent 2.0.21-stable

要分析php-memcache的一致性哈希实现,只需要注意两个函数,memcache_add_server和 memcache_get。

Memcache 和 MemcachePool 两个方法的定义位置:

Memcache::addServer()

MemcachePool::addServer()

两个方法是用同一个连接函数:

php_mmc_pool_addserver(mmc_object, host, host_len, tcp_port, udp_port, weight, persistent, timeout, retry_interval, status, NULL TSRMLS_CC);

从这里我们也可以看出MemcachePool的addServer支持udp。

memcache_consistent_hash.c 这个文件是关于一致性哈希的具体实现。

addServer方法添加服务器时是用的是mmc_consistent_add_server ,这个函数就是关于一致性哈希添加服务器节点的。

<!-- lang: cpp -->
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);//服务器信息 host+port+- 的哈希值
    /* 这里是权重影响的points的数量 ,直接影响缓存服务器的节点分布 */
    /* 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);
            /* 每个point的哈希值,分别用当前ponit数去重新哈希上面服务器信息的哈希 */
        hash = state->hash->finish(state->hash->combine(seed, key, key_len));
        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);
}

用什么哈希函数,为什么是2^32-1?

php-memcache有两种哈希策略:crc32 和 fnv1a 。

哈希函数策略定义:地址

<!-- lang: cpp -->
typedef unsigned int (*mmc_hash_function_init)();
typedef unsigned int (*mmc_hash_function_combine)(unsigned int seed, const void *key, unsigned int key_len);
typedef unsigned int (*mmc_hash_function_finish)(unsigned int seed);

typedef struct mmc_hash_function {
    mmc_hash_function_init      init;
    mmc_hash_function_combine   combine;
    mmc_hash_function_finish    finish;
} mmc_hash_function_t;

extern mmc_hash_function_t mmc_hash_crc32;
extern mmc_hash_function_t mmc_hash_fnv1a;

#define mmc_hash(hash, key, key_len) ((hash)->finish((hash)->combine((hash)->init(), (key), (key_len))))

我们常用的哈希策略是crc32。

关于crc32和fnv1a的优缺点:
FNV-1a比CRC32速度稍低,但是散列效果更好。

那就按照通用的CRC32来说。
PS:这种哈希算法方面不精通,纯摘自网络。

CRC32定义

<!-- lang: cpp -->
/* 调用php的CRC32算法 */
#include "ext/standard/crc32.h"

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) /*
    CRC32 hash {{{ */
{
    const char *p = (const char *)key, *end = p + key_len;
    while (p < end) {
        CRC32(seed, *(p++));
    }

    return seed;
}
/* }}} */

mmc_hash_function_t mmc_hash_crc32 = {
    mmc_hash_crc32_init,
    mmc_hash_crc32_combine,
    mmc_hash_crc32_finish
};

php-src/ext/standard/crc32.h php源码里的crc32就不贴代码了,看这个文件,就知道CRC32使用的是CRC32查表法。了解详情请自行谷歌。

CRC32:CRC本身是“冗余校验码”的意思,CRC32则表示会产生一个32bit(8位十六进制数)的校验值。由于CRC32产生校验值时源数据块的每一个bit(位)都参与了计算,所以数据块中即使只有一位发生了变化,也会得到不同的CRC32值。

所以一个值经过CRC32哈希之后,最大值就是0xffff ffff。转为无符号整形的取值范围就是0~0xffff fffe 即 0 ~ 2^32-1

关于points 和 state 结构

<!-- lang: cpp -->
typedef struct mmc_consistent_point {/* 这个可以理解为 服务器节点的映像,一个哈希结构,多条记录对应一个缓存实体 */
    mmc_t                   *server;//指向缓存节点信息的指针
        unsigned int            point;//上述中 服务器节点信息哈希后再用point值哈希的一个哈希值
} mmc_consistent_point_t;

typedef struct mmc_consistent_state {
    int                     num_servers;//当前服务器实体数量
    mmc_consistent_point_t          *points;//缓存映像哈希表
    int                     num_points;//缓存映像数量
    mmc_t                   *buckets[MMC_CONSISTENT_BUCKETS];/* 这里就是 一致性哈希的所有节点哈希表 */
    int                     buckets_populated;
    mmc_hash_function_t     *hash;/* 哈希函数 */
} mmc_consistent_state_t;

这部分结构就是实现一致性哈希的重点结构。聪明的你可以已经知道圆环上节点的数量了,下篇文章会详细解释。

下篇文章开始讲解一致性哈希的缓存节点分布实现。


评论已关闭