memcached源码分析-----哈希表基本操作以及扩容过程
来源：程序员人生 发布时间：2015-01-20 08:42:39 阅读次数：4206次
转载请注明出处：http://blog.csdn.net/luotuo44/article/details/42773231
温馨提示：本文用到了1些可以在启动memcached设置的全局变量。关于这些全局变量的含义可以参考《memcached启动参数详解》。对这些全局变量，处理方式就像《如何浏览memcached源代码》所说的那样直接取其默许值。
assoc.c文件里面的代码是构造1个哈希表。memcached快的1个缘由是使用了哈希表。现在就来看1下memcached是怎样使用哈希表的。
哈希结构：
main函数会调用assoc_init函数申请并初始化哈希表。为了减少哈希表产生冲突的可能性，memcached的哈希表是比较长的，并且哈希表的长度为2的幂。全局变量hashpower用来记录2的幂次。main函数调用assoc_init函数时使用全局变量settings.hashpower_init作为参数，用于指明哈希表初始化时的幂次。settings.hashpower_init可以在启动memcached的时候设置，具体可以参考《memcached启动参数详解和关键配置的默许值》。
//memcached.h文件
#define HASHPOWER_DEFAULT 16
//assoc.h文件
unsigned int hashpower = HASHPOWER_DEFAULT;
#define hashsize(n) ((ub4)1<<(n))//这里是1 左移 n次
//hashsize(n)为2的幂，所以hashmask的值的2进制情势就是后面全为1的数。这就很像位操作里面的 &
//value & hashmask(n)的结果肯定是比hashsize(n)小的1个数字.即结果在hash表里面
//hashmask(n)也能够称为哈希掩码
#define hashmask(n) (hashsize(n)⑴)
//哈希表数组指针
static item** primary_hashtable = 0;
//默许参数值为0。本函数由main函数调用，参数的默许值为0
void assoc_init(const int hashtable_init) {
if (hashtable_init) {
hashpower = hashtable_init;
}
//由于哈希表会渐渐增大，所以要使用动态内存分配。哈希表存储的数据是1个
//指针，这样更省空间。
//hashsize(hashpower)就是哈希表的长度了
primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
if (! primary_hashtable) {
fprintf(stderr, "Failed to init hashtable.
");
exit(EXIT_FAILURE);//哈希表是memcached工作的基础，如果失败只能退出运行
}
}
说到哈希表，那末就对应有两个问题，1个是哈希算法，1个怎样解决冲突。
对哈希函数(算法)，memcached直接使用开源的MurmurHash3和jenkins_hash两个中的1个。默许是使用jenkins，可以在启动memcached的时候设置设置为MurmurHash3。memcached是直接把客户端输入的键值作为哈希算法的输入，得到1个32位的无符号整型输出(用变量hv存储)。由于哈希表的长度没有2^32- 1这么大，所以需要用到前面代码中的hashmask宏进行截断。由因而位操作，所以常常能在memcached代码中看的hv & hashmask(hashpower)。
memcached使用最多见的链地址法解决冲突问题。从前面的代码可以看到，primary_hashtable是1个的2级指针变量，它指向的是1个1维指针数组，数组的每个元素指向1条链表(链表上的item节点具有相同的哈希值)。数组的每个元素，在memcached里面也称为桶(bucket)，所以后文的表述中会使用桶。下图是1个哈希表，其中第0号桶有2个item，第2、3、5号桶各有1个item。item就是用来存储用户数据的结构体。
基本操作：
插入item:
接着看1下怎样在哈希表中插入1个item。它是直接根据哈希值找到哈希表中的位置(即找到对应的桶)，然后使用头插法插入到桶的冲突链中。item结构体有1个专门的h_next指针成员变量用于连接哈希冲突链。
static unsigned int hash_items = 0;//hash表中item的个数
/* Note: this isn't an assoc_update. The key must not already exist to call this */
//hv是这个item键值的哈希值
int assoc_insert(item *it, const uint32_t hv) {
unsigned int oldbucket;
//使用头插法 插入1个item
//第1次看本函数，直接看else部份
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
...
} else {
//使用头插法插入哈希表中
it->h_next = primary_hashtable[hv & hashmask(hashpower)];
primary_hashtable[hv & hashmask(hashpower)] = it;
}
hash_items++;//哈希表的item数量加1
…
return 1;
}
查找item：
往哈希表插入item后，就能够开始查找item了。下面看1下怎样在哈希表中查找1个item。item的键值hv只能定位到哈希表中的桶位置，但1个桶的冲突链上可能有多个item，所以除查找的时候除需要hv外还需要item的键值。
//由于哈希值只能肯定是在哈希表中的哪一个桶(bucket)，但1个桶里面是有1条冲突链的
//此时需要用到具体的键值遍历并逐一比较冲突链上的所有节点。虽然key是以' '结尾
//的字符串，但调用strlen还是有点耗时(需要遍历键值字符串)。所以需要另外1个参数
//nkey指明这个key的长度
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
item *it;
unsigned int oldbucket;
//直接看else部份
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
it = old_hashtable[oldbucket];
} else {
//由哈希值判断这个key是属于那个桶(bucket)的
it = primary_hashtable[hv & hashmask(hashpower)];
}
//到这里，已肯定这个key是属于那个桶的。 遍历对应桶的冲突链便可
item *ret = NULL;
while (it) {
//长度相同的情况下才调用memcmp比较，更高效
if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
ret = it;
break;
}
it = it->h_next;
}
return ret;
}
删除item：
下面看1下从哈希表中删除1个item是怎样实现的。从链表中删除1个节点的常规做法是：先找到这个节点的先驱节点，然后使用先驱节点的next指针进行删除和拼接操作。memcached的做法差不多，实现以下：
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
item **before = _hashitem_before(key, nkey, hv);//得到先驱节点的h_next成员地址
if (*before) {//查找成功
item *nxt;
hash_items--;
//由于before是1个2级指针，其值为所查找item的先驱item的h_next成员地址.
//所以*before指向的是所查找的item.由于before是1个2级指针，所以
//*before作为左值时，可以给h_next成员变量赋值。所以下面3行代码是
//使得删除中间的item后，前后的item还能连得起来。
nxt = (*before)->h_next;
(*before)->h_next = 0; /* probably pointless, but whatever. */
*before = nxt;
return;
}
/* Note: we never actually get here. the callers don't delete things
they can't find. */
assert(*before != 0);
}
//查找item。返回先驱节点的h_next成员地址,如果查找失败那末就返回冲突链中最后
//1个节点的h_next成员地址。由于最后1个节点的h_next的值为NULL。通过对返回值
//使用 * 运算符便可知道有无查找成功。
static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
item **pos;
unsigned int oldbucket;
//一样，看的时候直接跳到else部份
if (expanding &&//正在扩大哈希表
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
pos = &old_hashtable[oldbucket];
} else {
//找到哈希表中对应的桶位置
pos = &primary_hashtable[hv & hashmask(hashpower)];
}
//遍历桶的冲突链查找item
while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
pos = &(*pos)->h_next;
}
//*pos就能够知道有无查找成功。如果*pos等于NULL那末查找失败，否则查找成功。
return pos;
}
扩大哈希表：
当哈希表中item的数量到达了哈希表表长的1.5倍时，那末就会扩大哈希表增大哈希表的表长。memcached在插入1个item时会检查当前的item总数是不是到达了哈希表表长的1.5倍。由于item的哈希值是比较均匀的，所以平均来讲每一个桶的冲突链长度大概就是1.5个节点。所以memcached的哈希查找还是很快的。
迁移线程：
扩大哈希表有1个很大的问题：扩大后哈希表的长度变了，item哈希后的位置也是会随着变化的(回想1下memcached是怎样根据键值的哈希值肯定桶的位置的)。所以如果要扩大哈希表，那末就需要对哈希表中所有的item都要重新计算哈希值得到新的哈希位置(桶位置)，然后把item迁移到新的桶上。对所有的item都要做这样的处理，所以这必定是1个耗时的操作。后文会把这个操作称为数据迁移。
由于数据迁移是1个耗时的操作，所以这个工作由1个专门的线程(姑且把这个线程叫做迁移线程吧)负责完成。这个迁移线程是由main函数调用1个函数创建的。看下面代码：
#define DEFAULT_HASH_BULK_MOVE 1
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
//main函数会调用本函数，启动数据迁移线程
int start_assoc_maintenance_thread() {
int ret;
char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
if (env != NULL) {
//hash_bulk_move的作用在后面会说到。这里是通过环境变量给hash_bulk_move赋值
hash_bulk_move = atoi(env);
if (hash_bulk_move == 0) {
hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
}
}
if ((ret = pthread_create(&maintenance_tid, NULL,
assoc_maintenance_thread, NULL)) != 0) {
fprintf(stderr, "Can't create thread: %s
", strerror(ret));
return ⑴;
}
return 0;
}
迁移线程被创建后会进入休眠状态(通过等待条件变量)，当worker线程插入item后，发现需要扩大哈希表就会调用assoc_start_expand函数唤醒这个迁移线程。
static bool started_expanding = false;
//assoc_insert函数会调用本函数，当item数量到了哈希表表长的1.5倍才会调用的
static void assoc_start_expand(void) {
if (started_expanding)
return;
started_expanding = true;
pthread_cond_signal(&maintenance_cond);
}
static bool expanding = false;//标明hash表是不是处于扩大状态
static volatile int do_run_maintenance_thread = 1;
static void *assoc_maintenance_thread(void *arg) {
//do_run_maintenance_thread是全局变量，初始值为1，在stop_assoc_maintenance_thread
//函数中会被赋值0，终止迁移线程
while (do_run_maintenance_thread) {
int ii = 0;
//上锁
item_lock_global();
mutex_lock(&cache_lock);
...//进行item迁移
//遍历完就释放锁
mutex_unlock(&cache_lock);
item_unlock_global();
if (!expanding) {//不需要迁移数据(了)。
/* We are done expanding.. just wait for next invocation */
mutex_lock(&cache_lock);
started_expanding = false; //重置
//挂起迁移线程，直到worker线程插入数据后发现item数量已到了1.5倍哈希表大小，
//此时调用worker线程调用assoc_start_expand函数，该函数会调用pthread_cond_signal
//唤醒迁移线程
pthread_cond_wait(&maintenance_cond, &cache_lock);
mutex_unlock(&cache_lock);
...
mutex_lock(&cache_lock);
assoc_expand();//申请更大的哈希表,并将expanding设置为true
mutex_unlock(&cache_lock);
}
}
return NULL;
}
逐渐迁移数据：
为了不在迁移的时候worker线程增删哈希表，所以要在数据迁移的时候加锁，worker线程抢到了锁才能增删查找哈希表。memcached为了实现快速响应(即worker线程能够快速完成增删查找操作)，就不能让迁移线程占锁太久。但数据迁移本身就是1个耗时的操作，这是1个矛盾。
memcached为了解决这个矛盾，就采取了逐渐迁移的方法。其做法是，在1个循环里面：加锁-》只进行小部份数据的迁移-》解锁。这样做的效果是：虽然迁移线程会屡次抢占锁，但每次占有锁的时间都是很短的，这就增加了worker线程抢到锁的几率，使得worker线程能够快速完成它的操作。1小部份是多少个item呢？前面说到的全局变量hash_bulk_move就指明是多少个桶的item，默许值是1个桶，后面为了方便叙述也就认为hash_bulk_move的值为1。
逐渐迁移的具体做法是，调用assoc_expand函数申请1个新的更大的哈希表，每次只迁移旧哈希表1个桶的item到新哈希表，迁移完1桶就释放锁。此时就要求有1个旧哈希表和新哈希表。在memcached实现里面，用primary_hashtable表示新表(也有1些博文称之为主表)，old_hashtable表示旧表(副表)。
前面说到，迁移线程被创建后就会休眠直到被worker线程唤醒。当迁移线程醒来后，就会调用assoc_expand函数扩大哈希表的表长。assoc_expand函数以下：
static void assoc_expand(void) {
old_hashtable = primary_hashtable;
//申请1个新哈希表，并用old_hashtable指向旧哈希表
primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
if (primary_hashtable) {
hashpower++;
expanding = true;//标明已进入扩大状态
expand_bucket = 0;//从0号桶开始数据迁移
} else {
primary_hashtable = old_hashtable;
/* Bad news, but we can keep running. */
}
}
现在看1下完全1点的assoc_maintenance_thread线程函数，体会迁移线程是怎样逐渐数据迁移的。为何说完全1点呢？由于该函数里面还是有1些东西本篇博文是没有解释的，但这其实不妨碍我们浏览该函数。后面还会有其他博文对这个线程函数进行讲授的。
static unsigned int expand_bucket = 0;//指向待迁移的桶
#define DEFAULT_HASH_BULK_MOVE 1
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
static volatile int do_run_maintenance_thread = 1;
static void *assoc_maintenance_thread(void *arg) {
//do_run_maintenance_thread是全局变量，初始值为1，在stop_assoc_maintenance_thread
//函数中会被赋值0，终止迁移线程
while (do_run_maintenance_thread) {
int ii = 0;
//上锁
item_lock_global();
mutex_lock(&cache_lock);
//hash_bulk_move用来控制每次迁移，移动多少个桶的item。默许是1个.
//如果expanding为true才会进入循环体，所以迁移线程刚创建的时候，其实不会进入循环体
for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
item *it, *next;
int bucket;
//在assoc_expand函数中expand_bucket会被赋值0
//遍历旧哈希表中由expand_bucket指明的桶,将该桶的所有item
//迁移到新哈希表中。
for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
next = it->h_next;
//重新计算新的哈希值,得到其在新哈希表的位置
bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);
//将这个item插入到新哈希表中
it->h_next = primary_hashtable[bucket];
primary_hashtable[bucket] = it;
}
//不需要清空旧桶。直接将冲突链的链头赋值为NULL便可
old_hashtable[expand_bucket] = NULL;
//迁移完1个桶，接着把expand_bucket指向下1个待迁移的桶
expand_bucket++;
if (expand_bucket == hashsize(hashpower - 1)) {//全部数据迁移终了
expanding = false; //将扩大标志设置为false
free(old_hashtable);
}
}
//遍历完hash_bulk_move个桶的所有item后，就释放锁
mutex_unlock(&cache_lock);
item_unlock_global();
if (!expanding) {//不再需要迁移数据了。
/* finished expanding. tell all threads to use fine-grained(细粒度的) locks */
//进入到这里，说明已不需要迁移数据(停止扩大了)。
...
mutex_lock(&cache_lock);
started_expanding = false; //重置
//挂起迁移线程，直到worker线程插入数据后发现item数量已到了1.5倍哈希表大小，
//此时调用worker线程调用assoc_start_expand函数，该函数会调用pthread_cond_signal
//唤醒迁移线程
pthread_cond_wait(&maintenance_cond, &cache_lock);
/* Before doing anything, tell threads to use a global lock */
mutex_unlock(&cache_lock);
...
mutex_lock(&cache_lock);
assoc_expand();//申请更大的哈希表,并将expanding设置为true
mutex_unlock(&cache_lock);
}
}
return NULL;
}
回马枪：
现在再回过头来再看1下哈希表的插入、删除和查找操作，由于这些操作可能产生在哈希表迁移阶段。有1点要注意，在assoc.c文件里面的插入、删除和查找操作，是看不到加锁操作的。但前面已说了，需要和迁移线程抢占锁，抢到了锁才能进行对应的操作。其实，这锁是由插入、删除和查找的调用者(主调函数)负责加的，所以在代码里面看不到。
由于插入的时候可能哈希表正在扩大，所以插入的时候要面临1个选择：插入到新表还是旧表？memcached的做法是：当item对应在旧表中的桶还没被迁移到新表的话，就插入到旧表，否则插入到新表。下面是插入部份的代码。
/* Note: this isn't an assoc_update. The key must not already exist to call this */
//hv是这个item键值的哈希值
int assoc_insert(item *it, const uint32_t hv) {
unsigned int oldbucket;
//使用头插法 插入1个item
if (expanding &&//目前处于扩大hash表状态
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)//数据迁移时还没迁移到这个桶
{
//插入到旧表
it->h_next = old_hashtable[oldbucket];
old_hashtable[oldbucket] = it;
} else {
//插入到新表
it->h_next = primary_hashtable[hv & hashmask(hashpower)];
primary_hashtable[hv & hashmask(hashpower)] = it;
}
hash_items++;//哈希表的item数量加1
//当hash表的item数量到达了hash表容量的1.5倍时，就会进行扩大
//固然如果现在正处于扩大状态，是不会再扩大的
if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
assoc_start_expand();//唤醒迁移线程，扩大哈希表
}
return 1;
}
这里有1个疑问，为何不直接插入到新表呢？直接插入到新表对数据1致性来讲完全是没有问题的啊。网上有人说是为了保证同1个桶item的顺序，但由于迁移线程和插入线程对锁抢占的不肯定性，任何顺序都不能通过assoc_insert函数来保证。本文认为是为了快速查找。如果是直接插入到新表，那末在查找的时候便可能要同时查找新旧两个表才能找到item。查找完1个表，发现没有，然后再去查找另外1个表，这样的查找被认为是不够快速的。
如果依照assoc_insert函数那样的实现，不用查找两个表就可以找到item。看下面的查找函数。
//由于哈希值只能肯定是在哈希表中的哪一个桶(bucket)，但1个桶里面是有1条冲突链的
//此时需要用到具体的键值遍历并逐一比较冲突链上的所有节点。由于key其实不是以' '结尾
//的字符串，所以需要另外1个参数nkey指明这个key的长度
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
item *it;
unsigned int oldbucket;
if (expanding &&//正在扩大哈希表
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)//该item还在旧表里面
{
it = old_hashtable[oldbucket];
} else {
//由哈希值判断这个key是属于那个桶(bucket)的
it = primary_hashtable[hv & hashmask(hashpower)];
}
//到这里已肯定了要查找的item是属于哪一个表的了，并且也肯定了桶位置。遍历对应桶的冲突链便可
item *ret = NULL;
while (it) {
//长度相同的情况下才调用memcmp比较，更高效
if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
ret = it;
break;
}
it = it->h_next;
}
return ret;
}
删除操作和查找操作差不多，这里直接贴出，不多说了。删除操作也是要进行查找操作的。
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
item **before = _hashitem_before(key, nkey, hv);//得到先驱节点的h_next成员地址
if (*before) {//查找成功
item *nxt;
hash_items--;
//由于before是1个2级指针，其值为所查找item的先驱item的h_next成员地址.
//所以*before指向的是所查找的item.由于before是1个2级指针，所以
//*before作为左值时，可以给h_next成员变量赋值。所以下面3行代码是
//使得删除中间的item后，前后的item还能连得起来。
nxt = (*before)->h_next;
(*before)->h_next = 0; /* probably pointless, but whatever. */
*before = nxt;
return;
}
/* Note: we never actually get here. the callers don't delete things
they can't find. */
assert(*before != 0);
}
//查找item。返回先驱节点的h_next成员地址,如果查找失败那末就返回冲突链中最后
//1个节点的h_next成员地址。由于最后1个节点的h_next的值为NULL。通过对返回值
//使用 * 运算符便可知道有无查找成功。
static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
item **pos;
unsigned int oldbucket;
if (expanding &&//正在扩大哈希表
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
pos = &old_hashtable[oldbucket];
} else {
//找到哈希表中对应的桶位置
pos = &primary_hashtable[hv & hashmask(hashpower)];
}
//到这里已肯定了要查找的item是属于哪一个表的了，并且也肯定了桶位置。遍历对应桶的冲突链便可
//遍历桶的冲突链查找item
while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
pos = &(*pos)->h_next;
}
//*pos就能够知道有无查找成功。如果*pos等于NULL那末查找失败，否则查找成功。
return pos;
}
由上面的讨论可以知道，插入和删除1个item都必须知道这个item对应的桶有无被迁移到新表上了。
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
