前言昨晚用一个小时把 memcached 的服务端程序看了，发现踩到一个坑，大部分程序都在实现服务器的网络编程的部分。
而我是不懂网络编程的，于是又花了半个小时去找 memcached 的储存代码，发现时使用 hash table 储存的。
于是这里研究一下 memcached 的 hash table .
昨晚记录的 memcached 源码阅读之原理篇 最后说了，服务器端做两部分：一部分是网络编程方面。另一部分就是 hash table 的实现。
刚好前几天我自己实现过一个 hash table 研究与实现, 于是 memcached 的 hash table 可以很快的看完并理解。
这里就简单的讲解一下 memcached 的 hash table .
我的 hash table大家可以先阅读一下我之前的 hash table 研究与实现。
大家可以看出来，我的这个 hash table 实现的太简单了，所以没有实用价值的，只能用来学习 hash table 。
这里我先说一下我的这个 hash table 需要加强之处吧。
node(节点) 与 bucket(桶)先熟悉一下我的 node 节点 和 桶。
class node {public: node():next(-1) { } int next; int pos;};node * hash_bucket ; //指向桶内存的指针
val 的改造首先我的 val 是一个对象，且所有的 val 必须有相同的内存大小。
这往往是不现实的，所以一个很简单的改造就是 val 修改为动态申请内存，然后用指针来储存在 node 里面即可。
class node {public: node():next(-1) { } int next; int pos; void* val; int vallen;};
key 改造我这里是没有 key 的，所以 key 是由 val hash 得到，但是实际中往往是 key-value 的储存方式，所以实际中是有个 key 的。
不过我的那个程序很容易就加入 key.
由于之后还有 key 的比较，且 key 的长度也是未知，所以这里我们就需要也把 key 储存在 node 里面了。
class node {public: node():next(-1) { } int next; int pos; void* val; int vallen; void* key; int keylen;};
内存管理大家还可以明显看到，我的内存管理其实更不现实。
使用前是根本不知道我们会插入多少个加点，所以这个内存需要时动态增加的。
关于这个实现，一会我们看 memcached 里面的实现方式吧。
其他改造改造之后，发现我的 桶没有必要是 node 节点，也就是链表不需要一个头，所以这个桶需要改造。
当然链表又没有头的学问也很大，大家可以自己研究一番。
node** hash_bucket;
memcached 的 hash table头文件认识memcached 的 hash table 有两个文件，一个 .c, 一个 .h .
这是他们的位置 assoc.h 和 assoc.c .
在 .h 中，代码就不足 10 行，可以看一下。 后两个是我自己加上的。
/* associative array */void assoc_init(const int hashpower_init); //初始化 hash tableitem *assoc_find(const char *key, const size_t nkey, const uint32_t hv); //查找int assoc_insert(item *item, const uint32_t hv);//插入void assoc_delete(const char *key, const size_t nkey, const uint32_t hv);//删除void do_assoc_move_next_bucket(void);//int start_assoc_maintenance_thread(void); //开启一个线程来合并两个hash tablevoid stop_assoc_maintenance_thread(void); //结束线程extern unsigned int hashpower; //hash tablestatic void *assoc_maintenance_thread(void *arg);//合并代码static void assoc_expand(void);//自动扩大hash table 的大小，有两个hash table.
核心变量介绍变量的介绍详见我的注释
//hash table 的桶大小永远是2的倍数，且按2的倍数扩增unsigned int hashpower = hashpower_default; // 桶的大小#define hashsize(n) ((ub4)1nkey) && (memcmp(key, item_key(it), nkey) == 0)) { ret = it; break; } it = it->h_next; ++depth; } return ret;}
添加添加比较简单，实现方式和我的差不多，插在链表头部。
这里多了一步桶大小的检测，节点个数超过当前桶大小的 1.5 倍时就增大桶(调用启动增大桶线程)。这里要注意的一点是对于插入的key,已经在其他地方检察过是否存在了。
意思就是这里保证一定不存在。
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;}
删除删除也比较简单，先找到需要删除的那个节点的父节点，然后删除即可。
需要注意的是这里也是保证要删除的节点已经存在。
另外大家不能理解的是为什么要用指向指针的指针。
这个问题曾经在 segmentfault 上有人问过这个问题，不过他那个问题就没有办法使用指向指针的指针了。
问题就是，如果不使用指向指针的指针，查找的节点不在第一个位置的话，可以正常操作。
但是在第一个位置的话，我们的操作不会生效的。
如果你不能明白的话，先去 segmentfault 研究一下那个问题，那个明白了，这个就明白了。
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; *before = nxt; return; }}
父节点的指针实现方式和普通的查找类似，只是使用指向指针的指针。
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;}
启动增大桶线程启动增大桶线程也很简单，只做一件事：给增大桶的线程发送一个信号。
static void assoc_start_expand(void) { if (started_expanding) return; started_expanding = true; pthread_cond_signal(&maintenance_cond);}
线程控制线程控制做两件事：启动线程和停止线程。
线程主要执行 assoc_maintenance_thread 函数。
static pthread_t maintenance_tid;int start_assoc_maintenance_thread() { int ret; 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;}void stop_assoc_maintenance_thread() { mutex_lock(&cache_lock); do_run_maintenance_thread = 0; pthread_cond_signal(&maintenance_cond); mutex_unlock(&cache_lock); pthread_join(maintenance_tid, null);}
线程做的事 - 合并桶这个合并桶的线程只做两件事。
第一件事是桶内的节点一个一个的合并，合并完了回收旧桶。
第二事是旧桶释放后，开始监听是否增大桶，接收到信号，调用增大桶 assoc_expand 函数。
static volatile int do_run_maintenance_thread = 1;#define default_hash_bulk_move 1int hash_bulk_move = default_hash_bulk_move;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 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) { /* finished expanding. tell all threads to use fine-grained locks */ switch_item_lock_type(item_lock_granular); slabs_rebalancer_resume(); /* we are done expanding.. just wait for next invocation */ mutex_lock(&cache_lock); started_expanding = false; pthread_cond_wait(&maintenance_cond, &cache_lock); /* before doing anything, tell threads to use a global lock */ mutex_unlock(&cache_lock); slabs_rebalancer_pause(); switch_item_lock_type(item_lock_global); mutex_lock(&cache_lock); assoc_expand(); mutex_unlock(&cache_lock); } } return null;}
增大桶增大桶做的事很简单，保存旧桶，申请新桶即可。
static void assoc_expand(void) { old_hashtable = primary_hashtable; primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *)); if (primary_hashtable) { if (settings.verbose > 1) fprintf(stderr, hash table expansion starting\n); hashpower++; expanding = true; expand_bucket = 0; } else { primary_hashtable = old_hashtable; }}
memcached 的 hash table 的评价看到这里，大家的心理可能会想几件事
1. 节点的管理怎么没有呢？
2. 简单的几个函数竟然实现了这个复杂功能？
我猜想这就是软件设计的强大之处。
节点管理从 hash table 里面抽象出去，你只需要给我传一个指向那个节点的指针，且那个节点有key的信息和下一个节点的指针即可。
另外对于面向过程的编程方式，想编出好的代码，就要学会函数封装。
每个函数都实现一个简单的功能，合起来就是很强大的功能了。
就像在 acm 比赛的时候，对于模拟题，我就感觉很简单 -- 不就是若干简单函数的实现嘛！
写到这文章也要结束了，打个广告，大家留意到了吗？
没上面没有提起对 key 的 hash 方法，那是因为 对 字符串的hash 又是一个很大的学问，我下篇文章慢慢介绍。
这篇文章之所以介绍的这个详细，是为了补偿昨晚写的那两篇没有价值的记录 《memcached 源码阅读之原理篇》 和 《memcached 源码阅读之库函数介绍》。
《完》
本文出自：http://tiankonguse.github.io, 原文地址：http://github.tiankonguse.com//blog/2014/11/07/memcached-hash-table/, 感谢原作者分享。