memcached 中 hash 表相关操作
以下转自 http://blog.csdn.net/luotuo44/article/details/42773231
memcached 源码中 assoc.c 文件里面的代码是构造一个哈希表。memcached 快的一个原因是使用了哈希表。现在就来看一下 memcached 是怎么使用哈希表的。
哈希结构:
main 函数会调用 assoc_init 函数申请并初始化哈希表。为了减少哈希表发生冲突的可能性,memcached 的哈希表是比较长的,并且哈希表的长度为 2 的幂。全局变量 hashpower 用来记录 2 的幂次。main 函数调用 assoc_init 函数时使用全局变量 settings.hashpower_init 作为参数,用于指明哈希表初始化时的幂次。settings.hashpower_init 可以在启动 memcached 的时候设置。
- #define HASHPOWER_DEFAULT 16
-
- unsigned int hashpower = HASHPOWER_DEFAULT;
-
- #define hashsize(n) ((ub4)1<<(n))// 这里是 1 左移 n 次
- #define hashmask(n) (hashsize(n)-1)
-
- static item** primary_hashtable = 0;
-
-
- void assoc_init(const int hashtable_init) {
- if (hashtable_init) {
- hashpower = hashtable_init;
- }
-
-
-
-
- primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
- if (! primary_hashtable) {
- fprintf(stderr, "Failed to init hashtable.\n");
- exit(EXIT_FAILURE);
- }
-
- }
说到哈希表,那么就对应有两个问题:哈希算法,怎么解决冲突。
对于哈希函数 (算法),memcached 直接使用开源的 MurmurHash3 和 jenkins_hash 两个中的一个。默认是使用 jenkins,可以在启动 memcached 的时候设置设置为 MurmurHash3。memcached 是直接把客户端输入的键值作为哈希算法的输入,得到一个 32 位的无符号整型输出 (用变量 hv 存储)。因为哈希表的长度没有 2^32- 1 这么大,所以需要一个函数将 hv 映射在哈希表的范围之内。memcached 采用了最简单的取模运算作为映射函数,即 hv%hashsize(hashpower)。对于 CPU 而言,取模运算是一个比较耗时的操作。所以 memcached 利用哈希表的长度是 2 的幂的性质,采用位操作进行优化,即: hv & hashmask(hashpower)。因为对哈希表进行增删查操作都需要定位,所以经常本文的代码中经常会出现 hv & hashmask(hashpower)。
memcached 使用最常见的链地址法解决冲突问题。从前面的代码可以看到,primary_hashtable 是一个的二级指针变量,它指向的是一个一维指针数组,数组的每一个元素指向一条链表 (链表上的 item 节点具有相同的哈希值)。数组的每一个元素,在 memcached 里面也称为桶 (bucket),所以后文的表述中会使用桶。下图是一个哈希表,其中第 0 号桶有 2 个 item,第 2、3、5 号桶各有一个 item。item 就是用来存储用户数据的结构体。
基本操作:
插入 item:
接着看一下怎么在哈希表中插入一个 item。它是直接根据哈希值找到哈希表中的位置 (即找到对应的桶),然后使用头插法插入到桶的冲突链中。item 结构体有一个专门的 h_next 指针成员变量用于连接哈希冲突链。
- static unsigned int hash_items = 0;
-
- int assoc_insert(item *it, const uint32_t hv) {
- unsigned int oldbucket;
-
-
-
- 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++;
- …
- return 1;
- }
查找 item:
往哈希表插入 item 后,就可以开始查找 item 了。下面看一下怎么在哈希表中查找一个 item。item 的键值 hv 只能定位到哈希表中的桶位置,但一个桶的冲突链上可能有多个 item,所以除了查找的时候除了需要 hv 外还需要 item 的键值。
- 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)
- {
- it = old_hashtable[oldbucket];
- } else {
-
- it = primary_hashtable[hv & hashmask(hashpower)];
- }
-
-
-
- item *ret = NULL;
- while (it) {
-
- if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
- ret = it;
- break;
- }
- it = it->h_next;
- }
- return ret;
- }
删除 item:
下面看一下从哈希表中删除一个 item 是怎么实现的。从链表中删除一个节点的常规做法是:先找到这个节点的前驱节点,然后使用前驱节点的 next 指针进行删除和拼接操作。memcached 的做法差不多,实现如下:
- void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
- item **before = _hashitem_before(key, nkey, hv);
-
- if (*before) {
- item *nxt;
- hash_items--;
-
-
-
-
- nxt = (*before)->h_next;
- (*before)->h_next = 0; /* probably pointless, but whatever. */
- *before = nxt;
- return;
- }
-
- assert(*before != 0);
- }
-
-
-
- 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)];
- }
-
-
- while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
- pos = &(*pos)->h_next;
- }
-
- return pos;
- }
扩展哈希表:
当哈希表中 item 的数量达到了哈希表表长的 1.5 倍时,那么就会扩展哈希表增大哈希表的表长。memcached 在插入一个 item 时会检查当前的 item 总数是否达到了哈希表表长的 1.5 倍。由于 item 的哈希值是比较均匀的,所以平均来说每个桶的冲突链长度大概就是 1.5 个节点。所以 memcached 的哈希查找还是很快的。
迁移线程:
扩展哈希表有一个很大的问题:扩展后哈希表的长度变了,item 哈希后的位置也是会跟着变化的 (回忆一下 memcached 是怎么根据键值的哈希值确定桶的位置的)。所以如果要扩展哈希表,那么就需要对哈希表中所有的 item 都要重新计算哈希值得到新的哈希位置 (桶位置),然后把 item 迁移到新的桶上。对所有的 item 都要做这样的处理,所以这必然是一个耗时的操作。后文会把这个操作称为数据迁移。
因为数据迁移是一个耗时的操作,所以这个工作由一个专门的线程 (姑且把这个线程叫做迁移线程吧) 负责完成。这个迁移线程是由 main 函数调用一个函数创建的。看下面代码:
- #define DEFAULT_HASH_BULK_MOVE 1
- int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
-
- int start_assoc_maintenance_thread() {
- int ret;
- char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
- if (env != NULL) {
-
- 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\n", strerror(ret));
- return -1;
- }
- return 0;
- }
迁移线程被创建后会进入休眠状态 (通过等待条件变量),当 worker 线程插入 item 后,发现需要扩展哈希表就会调用 assoc_start_expand 函数唤醒这个迁移线程。
- static bool started_expanding = false;
-
- static void assoc_start_expand(void) {
- if (started_expanding)
- return;
- started_expanding = true;
- pthread_cond_signal(&maintenance_cond);
- }
-
-
- static bool expanding = false;
- static volatile int do_run_maintenance_thread = 1;
- static void *assoc_maintenance_thread(void *arg) {
-
-
-
- while (do_run_maintenance_thread) {
- int ii = 0;
-
-
- item_lock_global();
- mutex_lock(&cache_lock);
-
- ...
-
-
- mutex_unlock(&cache_lock);
- item_unlock_global();
-
-
- if (!expanding) {
-
- mutex_lock(&cache_lock);
- started_expanding = false;
-
-
-
-
- pthread_cond_wait(&maintenance_cond, &cache_lock);
- mutex_unlock(&cache_lock);
-
- ...
-
- mutex_lock(&cache_lock);
- assoc_expand();
- mutex_unlock(&cache_lock);
- }
- }
- return NULL;
- }
逐步迁移数据:
为了避免在迁移的时候 worker 线程增删哈希表,所以要在数据迁移的时候加锁,worker 线程抢到了锁才能增删查找哈希表。memcached 为了实现快速响应 (即 worker 线程能够快速完成增删查找操作),就不能让迁移线程占锁太久。但数据迁移本身就是一个耗时的操作,这是一个矛盾。
memcached 为了解决这个矛盾,就采用了逐步迁移的方法。其做法是,在一个循环里面:加锁 -》只进行小部分数据的迁移 -》解锁。这样做的效果是:虽然迁移线程会多次抢占锁,但每次占有锁的时间都是很短的,这就增加了 worker 线程抢到锁的概率,使得 worker 线程能够快速完成它的操作。一小部分是多少个 item 呢?前面说到的全局变量 hash_bulk_move 就指明是多少个桶的 item,默认值是 1 个桶,后面为了方便叙述也就认为 hash_bulk_move 的值为 1。
逐步迁移的具体做法是,调用 assoc_expand 函数申请一个新的更大的哈希表,每次只迁移旧哈希表一个桶的 item 到新哈希表,迁移完一桶就释放锁。此时就要求有一个旧哈希表和新哈希表。在 memcached 实现里面,用 primary_hashtable 表示新表 (也有一些博文称之为主表),old_hashtable 表示旧表 (副表)。
前面说到,迁移线程被创建后就会休眠直到被 worker 线程唤醒。当迁移线程醒来后,就会调用 assoc_expand 函数扩大哈希表的表长。assoc_expand 函数如下:
- static void assoc_expand(void) {
- old_hashtable = primary_hashtable;
-
-
- primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
- if (primary_hashtable) {
-
- hashpower++;
- expanding = true;
- expand_bucket = 0;
- } else {
- primary_hashtable = old_hashtable;
-
- }
- }
现在看一下完整一点的 assoc_maintenance_thread 线程函数,体会迁移线程是怎么逐步数据迁移的。为什么说完整一点呢?因为该函数里面还是有一些东西本篇博文是没有解释的,但这并不妨碍我们阅读该函数。后面还会有其他博文对这个线程函数进行讲解的。
- 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) {
-
-
-
- while (do_run_maintenance_thread) {
- int ii = 0;
-
-
- item_lock_global();
- mutex_lock(&cache_lock);
-
-
-
- for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
- item *it, *next;
- int bucket;
-
-
-
-
- for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
- next = it->h_next;
-
-
- bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);
-
-
- it->h_next = primary_hashtable[bucket];
- primary_hashtable[bucket] = it;
- }
-
-
- old_hashtable[expand_bucket] = NULL;
-
-
- expand_bucket++;
-
- if (expand_bucket == hashsize(hashpower - 1)) {
- expanding = false;
- free(old_hashtable);
- }
- }
-
-
- mutex_unlock(&cache_lock);
- item_unlock_global();
-
-
- if (!expanding) {
-
-
-
- ...
- mutex_lock(&cache_lock);
- started_expanding = false;
-
-
-
-
- pthread_cond_wait(&maintenance_cond, &cache_lock);
-
- mutex_unlock(&cache_lock);
-
- ...
- mutex_lock(&cache_lock);
- assoc_expand();
- mutex_unlock(&cache_lock);
- }
- }
- return NULL;
- }
回马枪:
现在再回过头来再看一下哈希表的插入、删除和查找操作,因为这些操作可能发生在哈希表迁移阶段。有一点要注意,在 assoc.c 文件里面的插入、删除和查找操作,是看不到加锁操作的。但前面已经说了,需要和迁移线程抢占锁,抢到了锁才能进行对应的操作。其实,这锁是由插入、删除和查找的调用者 (主调函数) 负责加的,所以在代码里面看不到。
因为插入的时候可能哈希表正在扩展,所以插入的时候要面临一个选择:插入到新表还是旧表?memcached 的做法是:当 item 对应在旧表中的桶还没被迁移到新表的话,就插入到旧表,否则插入到新表。下面是插入部分的代码。
- int assoc_insert(item *it, const uint32_t hv) {
- unsigned int oldbucket;
-
-
-
- if (expanding &&
- (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++;
-
-
- if (! expanding && hash_items> (hashsize(hashpower) * 3) / 2) {
- assoc_start_expand();
- }
-
- return 1;
- }
这里有一个疑问,为什么不直接插入到新表呢?直接插入到新表对于数据一致性来说完全是没有问题的啊。网上有人说是为了保证同一个桶 item 的顺序,但由于迁移线程和插入线程对于锁抢占的不确定性,任何顺序都不能通过 assoc_insert 函数来保证。本文认为是为了快速查找。如果是直接插入到新表,那么在查找的时候就可能要同时查找新旧两个表才能找到 item。查找完一个表,发现没有,然后再去查找另外一个表,这样的查找被认为是不够快速的。
如果按照 assoc_insert 函数那样的实现,不用查找两个表就能找到 item。看下面的查找函数。
- 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)
- {
- it = old_hashtable[oldbucket];
- } else {
-
- it = primary_hashtable[hv & hashmask(hashpower)];
- }
-
-
-
- item *ret = NULL;
- while (it) {
-
- 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);
-
- if (*before) {
- item *nxt;
- hash_items--;
-
-
-
-
-
- nxt = (*before)->h_next;
- (*before)->h_next = 0; /* probably pointless, but whatever. */
- *before = nxt;
- return;
- }
-
- assert(*before != 0);
- }
-
-
- 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)];
- }
-
-
-
-
- while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
- pos = &(*pos)->h_next;
- }
-
- return pos;
- }
由上面的讨论可以知道,插入和删除一个 item 都必须知道这个 item 对应的桶有没有被迁移到新表上了。
来源: http://www.bubuko.com/infodetail-2439785.html