上一篇回顧:《memcached學習筆記——存儲命令源碼分析上篇》通過分析memcached的存儲命令源碼的過程，了解了memcached如何解析文本命令和mencached的內存管理機制。
本文是延續上一篇，繼續分析存儲命令的源碼。接上一篇內存分配成功後，本文主要講解：1、memcached存儲方式；2、add和set命令的區別。
哈希表(HashTable)
哈希表在實踐中使用的非常廣泛，例如編譯器通常會維護的一個符號表來保存標記，很多高級語言中也顯式的支持哈希表。 哈希表通常提供查找(Search)，插入(Insert)，刪除(Delete)等操作，這些操作在最壞的情況下和鏈表的性能一樣為O(n)。 不過通常並不會這麼壞，合理設計的哈希算法能有效的避免這類情況，通常哈希表的這些操作時間復雜度為O(1)。 這也是它被鐘愛的原因。
memcached是通過一個HashTable來存儲所有的item（注：memcached的slab模型是管理內存的，HashTable是用來存儲數據的），memcached中HashTable的哈希沖突解決方法就是鏈接法，memcached的如此高效查詢可以歸功於HashTable。
memcached的HashTable是聲明和操作在assoc.c文件中，下面我們先看看memcached的HashTable聲明和相關操作定義
1 /* primary_hashtable是主要的HashTable */ 2 static item** primary_hashtable = 0; 3 4 /* 如果memcached對HashTable進行擴展，那麼舊的數據就會被存放在old_hashtable */ 5 static item** old_hashtable = 0; 6 7 /* HashTable中保存item的數量 */ 8 static unsigned int hash_items = 0; 9 10 /* expanding是標記HashTable是否進行了擴展，如果進行了擴展，那麼進行查詢的時候就會在primary_hashtable和old_hashtable中查詢，否則只會在primary_hashtable中查詢 */ 11 static bool expanding = false; 12 13 /* HashTable初始化函數 */ 14 void assoc_init(const int hashpower_init); 15 /* HashTable查詢操作 */ 16 item *assoc_find(const char *key, const size_t nkey, const uint32_t hv); 17 /* HashTable插入操作 */ 18 int assoc_insert(item *item, const uint32_t hv); 19 /* HashTable刪除操作 */ 20 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）根據返回的結果，向客戶端返回本次命令的最終結果
1 static void complete_nread_ascii(conn *c) { 2 assert(c != NULL); 3 4 item *it = c->item; 5 int comm = c->cmd; 6 enum store_item_type ret; 7 8 pthread_mutex_lock(&c->thread->stats.mutex); 9 c->thread->stats.slab_stats[it->slabs_clsid].set_cmds++; 10 pthread_mutex_unlock(&c->thread->stats.mutex); 11 12 if (strncmp(ITEM_data(it) + it->nbytes - 2, "\r\n", 2) != 0) { 13 out_string(c, "CLIENT_ERROR bad data chunk"); 14 } else { 15 ret = store_item(it, comm, c); // memcached存儲item操作 16 17 18 //........ 19 20 21 switch (ret) { 22 case STORED: 23 out_string(c, "STORED"); // 存儲成功後客戶端得到的結果 24 break; 25 case EXISTS: 26 out_string(c, "EXISTS"); 27 break; 28 case NOT_FOUND: 29 out_string(c, "NOT_FOUND"); 30 break; 31 case NOT_STORED: 32 out_string(c, "NOT_STORED"); // 我們通過add存儲一個已經存在的key的時候會得到這樣的結果 33 break; 34 default: 35 out_string(c, "SERVER_ERROR Unhandled storage type."); 36 } 37 38 } 39 40 //......... 41 }store_item（thread.c）
1 enum store_item_type store_item(item *item, int comm, conn* c) { 2 enum store_item_type ret; 3 uint32_t hv; 4 5 // memcached根據hash算法計算出當前item的key的hash值hv 6 hv = hash(ITEM_key(item), item->nkey, 0); 7 8 item_lock(hv); 9 // memcached存儲item的核心操作 10 ret = do_store_item(item, comm, c, hv); 11 item_unlock(hv); 12 return ret; 13 }do_store_item（memcached.c）
1 enum store_item_type do_store_item(item *it, int comm, conn *c, const uint32_t hv) { //comm 是命令 2 char *key = ITEM_key(it); 3 4 // 通過key和hv哈希值查詢HashTable（assoc_find，後面會講解）中是否已經存在對應的item 5 item *old_it = do_item_get(key, it->nkey, hv); 6 7 // 存儲的結果，初始值是NOT_STORED 8 enum store_item_type stored = NOT_STORED; 9 10 item *new_it = NULL; 11 int flags; 12 13 if (old_it != NULL && comm == NREAD_ADD) { 14 /* add only adds a nonexistent item, but promote to head of LRU */ 15 // 數據項不為空, 更新時間 16 // 如果調用的是add命令並且，之前已經存在了相應的key的，那麼就只是修改使用時間，stored的值還是NOT_STORED， 17 // 所以調用add來添加已經存在的項，會得到NOT_STORED的結果，key對應的value沒有改變，在complete_nread輸出信息 18 do_item_update(old_it); 19 20 } else if (!old_it && (comm == NREAD_REPLACE 21 || comm == NREAD_APPEND || comm == NREAD_PREPEND)) 22 { 23 24 // .......... 25 26 } else if (comm == NREAD_CAS) { 27 28 // ............ 29 30 } else { 31 // old_it為空，並且comm為add、set、replace、append；或者old_it不為空，並且comm為set、replace、append 32 /* 33 * Append - combine new and old record into single one. Here it's 34 * atomic and thread-safe. 35 */ 36 if (comm == NREAD_APPEND || comm == NREAD_PREPEND) { 37 38 // .......... 39 40 } 41 42 // 存儲的結果，初始值是NOT_STORED 43 if (stored == NOT_STORED) { 44 if (old_it != NULL) 45 item_replace(old_it, it, hv); // old_it不為空，並且命令為set：在HashTable中用新的item it替換舊的item old_it 46 else 47 do_item_link(it, hv); // old_it為空，並且命令為add、set：那麼就把item it插入到HashTable中 48 49 c->cas = ITEM_get_cas(it); 50 51 stored = STORED; // 修改存儲的結果 52 } 53 }// end if 54 55 56 // ......... 57 58 return stored; 59 }最後我們看看assoc_find函數，HashTable的查詢操作
1 item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) { 2 item *it; 3 unsigned int oldbucket; 4 5 // 正如我們上面：expanding是標記HashTable是否進行了擴展，如果進行了擴展，那麼進行查詢的時候就會在primary_hashtable和old_hashtable中查詢，否則只會在primary_hashtable中查詢 6 // 這裡通過key和hv哈希值，先定位item所在鏈表 7 if (expanding && 8 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) 9 { 10 it = old_hashtable[oldbucket]; 11 } else { 12 it = primary_hashtable[hv & hashmask(hashpower)]; 13 } 14 15 item *ret = NULL; 16 int depth = 0; 17 // 遍歷上面找到的鏈表it，從it中查詢key對應的item 18 // 返回找到的item ret，否則就返回NULL 19 while (it) { 20 if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) { 21 ret = it; 22 break; 23 } 24 it = it->h_next; 25 ++depth; 26 } 27 MEMCACHED_ASSOC_FIND(key, nkey, depth); 28 return ret; 29 }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
