memcached学习笔记——存储命令源码分析下篇

上一篇回顾:《memcached学习笔记——存储命令源码分析上篇》通过分析memcached的存储命令源码的过程,了解了memcached如何解析文本命令和mencached的内存管理机制。

本文是延续上一篇,继续分析存储命令的源码。接上一篇内存分配成功后,本文主要讲解:1、memcached存储方式;2、add和set命令的区别。

memcached存储方式

哈希表(HashTable)

哈希表在实践中使用的非常广泛,例如编译器通常会维护的一个符号表来保存标记,很多高级语言中也显式的支持哈希表。 哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,这些操作在最坏的情况下和链表的性能一样为O(n)。 不过通常并不会这么坏,合理设计的哈希算法能有效的避免这类情况,通常哈希表的这些操作时间复杂度为O(1)。 这也是它被钟爱的原因。

memcached是通过一个HashTable来存储所有的item(注:memcached的slab模型是管理内存的,HashTable是用来存储数据的),memcached中HashTable的哈希冲突解决方法就是链接法,memcached的如此高效查询可以归功于HashTable。

memcached的HashTable是声明和操作在assoc.c文件中,下面我们先看看memcached的HashTable声明和相关操作定义

 /* primary_hashtable是主要的HashTable */
static item** primary_hashtable = ; /* 如果memcached对HashTable进行扩展,那么旧的数据就会被存放在old_hashtable */
static item** old_hashtable = ; /* HashTable中保存item的数量 */
static unsigned int hash_items = ; /* expanding是标记HashTable是否进行了扩展,如果进行了扩展,那么进行查询的时候就会在primary_hashtable和old_hashtable中查询,否则只会在primary_hashtable中查询 */
static bool expanding = false; /* HashTable初始化函数 */
void assoc_init(const int hashpower_init);
/* HashTable查询操作 */
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv);
/* HashTable插入操作 */
int assoc_insert(item *item, const uint32_t hv);
/* HashTable删除操作 */
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv);

memcached内存分配成功后,返回新item,接着把这item保存到HashTable中,complete_nread_ascii > store_item > do_store_item

在complete_nread_ascii(memcached.c)中store_item(thread.c)根据返回的结果,向客户端返回本次命令的最终结果

 static void complete_nread_ascii(conn *c) {
assert(c != NULL); item *it = c->item;
int comm = c->cmd;
enum store_item_type ret; pthread_mutex_lock(&c->thread->stats.mutex);
c->thread->stats.slab_stats[it->slabs_clsid].set_cmds++;
pthread_mutex_unlock(&c->thread->stats.mutex); if (strncmp(ITEM_data(it) + it->nbytes - , "\r\n", ) != ) {
out_string(c, "CLIENT_ERROR bad data chunk");
} else {
ret = store_item(it, comm, c); // memcached存储item操作 //........ switch (ret) {
case STORED:
out_string(c, "STORED"); // 存储成功后客户端得到的结果
break;
case EXISTS:
out_string(c, "EXISTS");
break;
case NOT_FOUND:
out_string(c, "NOT_FOUND");
break;
case NOT_STORED:
out_string(c, "NOT_STORED"); // 我们通过add存储一个已经存在的key的时候会得到这样的结果
break;
default:
out_string(c, "SERVER_ERROR Unhandled storage type.");
} } //.........
}

store_item(thread.c)

 enum store_item_type store_item(item *item, int comm, conn* c) {
enum store_item_type ret;
uint32_t hv; // memcached根据hash算法计算出当前item的key的hash值hv
hv = hash(ITEM_key(item), item->nkey, ); item_lock(hv);
// memcached存储item的核心操作
ret = do_store_item(item, comm, c, hv);
item_unlock(hv);
return ret;
}

do_store_item(memcached.c)

 enum store_item_type do_store_item(item *it, int comm, conn *c, const uint32_t hv) {                                        //comm 是命令
char *key = ITEM_key(it); // 通过key和hv哈希值查询HashTable(assoc_find,后面会讲解)中是否已经存在对应的item
item *old_it = do_item_get(key, it->nkey, hv); // 存储的结果,初始值是NOT_STORED
enum store_item_type stored = NOT_STORED; item *new_it = NULL;
int flags; if (old_it != NULL && comm == NREAD_ADD) {
/* add only adds a nonexistent item, but promote to head of LRU */
// 数据项不为空, 更新时间
// 如果调用的是add命令并且,之前已经存在了相应的key的,那么就只是修改使用时间,stored的值还是NOT_STORED,
// 所以调用add来添加已经存在的项,会得到NOT_STORED的结果,key对应的value没有改变,在complete_nread输出信息
do_item_update(old_it); } else if (!old_it && (comm == NREAD_REPLACE
|| comm == NREAD_APPEND || comm == NREAD_PREPEND))
{ // .......... } else if (comm == NREAD_CAS) { // ............ } else {
// old_it为空,并且comm为add、set、replace、append;或者old_it不为空,并且comm为set、replace、append
/*
* Append - combine new and old record into single one. Here it's
* atomic and thread-safe.
*/
if (comm == NREAD_APPEND || comm == NREAD_PREPEND) { // .......... } // 存储的结果,初始值是NOT_STORED
if (stored == NOT_STORED) {
if (old_it != NULL)
item_replace(old_it, it, hv); // old_it不为空,并且命令为set:在HashTable中用新的item it替换旧的item old_it
else
do_item_link(it, hv); // old_it为空,并且命令为add、set:那么就把item it插入到HashTable中 c->cas = ITEM_get_cas(it); stored = STORED; // 修改存储的结果
}
}// end if // ......... return stored;
}

最后我们看看assoc_find函数,HashTable的查询操作

 item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
item *it;
unsigned int oldbucket; // 正如我们上面:expanding是标记HashTable是否进行了扩展,如果进行了扩展,那么进行查询的时候就会在primary_hashtable和old_hashtable中查询,否则只会在primary_hashtable中查询
// 这里通过key和hv哈希值,先定位item所在链表
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - ))) >= expand_bucket)
{
it = old_hashtable[oldbucket];
} else {
it = primary_hashtable[hv & hashmask(hashpower)];
} item *ret = NULL;
int depth = ;
// 遍历上面找到的链表it,从it中查询key对应的item
// 返回找到的item ret,否则就返回NULL
while (it) {
if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == )) {
ret = it;
break;
}
it = it->h_next;
++depth;
}
MEMCACHED_ASSOC_FIND(key, nkey, depth);
return ret;
}

add和set命令的区别

从do_store_item函数中可以看出,1)如果是add命令,但是key对应的value已经存在,那么只是更新key的最近使用时间,value没有被新的value覆盖,返回NOT_STORED的结果;2)如果是add命令,第一次存储,那么value就会添加到HashTable中,返回STORED结果;3)如果是set命令,无论key对应的value是否已经存在,最后新的value会插入到HashTable中,返回STORED结果

最后,感谢各位在大冷天的看完小弟拙文,谢谢!

(完)

更多文章请移步:www.hcoding.com

上一篇:jQuery UI 实例 - 自动完成(Autocomplete)


下一篇:读取本地已有的.db数据库