memcache研究笔记 之 hashtable
查找过程中与关键字进行比较的次数通常取决于三个因素：哈希函数，解决冲突的方法和哈希表的填装因子。处理冲突方法相同的hashtable，其平均查找长度依赖于哈希表的装填因子：装填因子a = 表中填入的记录数/哈希表长度
memcached 采用的hash 函数是Bob Jenkins 先生在1996 创立的一个算法，复杂度为O（6n+35），而且冲突率极低，该算法具体过程可以参阅这里。冲突处理的方法为开链法。
memcached 中实际有两个hash 表，一个是“主hash 表”（primary_hashtable），另外一个是“原有hash 表”（old_hashtable）。每次操作的时候，先会检测表是否正处于扩展(expanding)状态，如果扩展还没完成时，先在原有hash 表中操作数据。 向primary_hashtable插入数据assoc_insert，会检查primary_hashtable中数据项的数量，如果(K-V数量) > (primary_hashtable哈希桶数量 * 3/ 2)，则将primary_hashtable扩大一倍，这项工作是由assoc维护线程负责。所以memcache可以避免由于哈希桶太深导致hash table性能下降。值得学习的时，在扩展primary_hashtable时，memcache作者先将primary_hashtable备份到old_hashtable, 然后将old_hashtable的哈希桶一个一个重新插入primary_hashtalbe。这样就避免了长久占用cache lock导致其它工作线程过久等待，影响请求响应时间。
main中启动维护线程assoc_maintenance_thread，然后等待条件变量进行hash长度扩容。在assoc_insert达到条件*3/2*的时候触发条件变量后assoc_maintenance_thread进行扩容。
涉及到的变量：
static unsigned int hashpower = 16;
#define hashsize(n) ((ub4)1<<(n)) //hashtable初始化大小设置为2^16
#define hashmask(n) (hashsize(n)-1) // 初始hashmask=0x1111 1111 1111 1111，用来将哈希函数计算的结果映射到hashsize域内，hashmask二进制值永远是hashpower位1的串
static unsigned int hash_items = 0; // hashtable中存在的item数量
static unsigned int expand_bucket = 0; // 当前扩展的位置（old_hashtable中的索引）大于等于expand_bucket表示还在old_hashtable中
总结：
1、当无需扩容，直接操作primary_hashtable
2、待primary_hashtable正在扩容，指定了hash_bulk_move，然后指定了expand_bucket在当前bucket里面的位置，
1）如果新操作位置<expand_bucket，直接操作primary_hashtable
2）如果新操作位置>=expand_bucket，直接操作old_hashtable
3、锁的数据同步保证cache_lock
思考：
影响mc_hash的性能的因素：1、散列函数 2、表自然增长
页:
[1]