模板
教程
環境
性能
功能
管理
memcached深度分析(4)
NewHash的原型參考：http://burtleburtle.net/bob/hash/evahash.html。數學家總是有點奇怪，呵呵～
為了變換方便，定義了u4和u1兩種數據類型，u4就是無符號的長整形，u1就是無符號char(0-255)。
具體代碼可以參考1.1和1.2源碼包。
注意這里的hashtable長度，1.1和1.2也是有區別的，1.1中定義了HASHPOWER常量為20，hashtable表長為 hashsize(HASHPOWER)，就是4MB(hashsize是一個宏，表示1右移n位)，1.2中是變量16，即hashtable表長 65536：
typedef unsigned long int ub4; /* unsigned 4-byte quantities */ typedef unsigned char ub1; /* unsigned 1-byte quantities */ #define hashsize(n) ((ub4)1<<(n)) #define hashmask(n) (hashsize(n)-1) |
在assoc_init()中，會對primary_hashtable做初始化，對應的hash操作包括：assoc_find()、assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete()，對應于item的讀寫操作。其中assoc_find()是根據key和key長尋找對應的item地址的函數(注意在C中，很多時候都是同時直接傳入字符串和字符串長度，而不是在函數內部做strlen)，返回的是item結構指針，它的數據地址在slab中的某個chunk上。
items.c是數據項的操作程序，每一個完整的item包括幾個部分，在item_make_header()中定義為：
key：鍵
nkey：鍵長
flags：用戶定義的flag(其實這個flag在memcached中沒有啟用)
nbytes：值長(包括換行符號\r\n)
suffix：后綴Buffer
nsuffix：后綴長
一個完整的item長度是鍵長+值長+后綴長+item結構大小(32字節)，item操作就是根據這個長度來計算slab的classid的。
hashtable中的每一個桶上掛著一個雙鏈表，item_init()的時候已經初始化了heads、tails、sizes三個數組為0，這三個數組的大小都為常量LARGEST_ID(默認為255，這個值需要配合factor來修改)，在每次item_assoc()的時候，它會首先嘗試從slab中獲取一塊空閑的chunk，如果沒有可用的chunk，會在鏈表中掃描50次，以得到一個被LRU踢掉的item，將它unlink，然后將需要插入的item插入鏈表中。
注意item的refcount成員。item被unlink之后只是從鏈表上摘掉，不是立刻就被free的，只是將它放到刪除隊列中(item_unlink_q()函數)。
item對應一些讀寫操作，包括remove、update、replace，當然最重要的就是alloc操作。
item還有一個特性就是它有過期時間，這是memcached的一個很有用的特性，很多應用都是依賴于memcached的item過期，比如session存儲、操作鎖等。item_flush_expired()函數就是掃描表中的item，對過期的item執行unlink操作，當然這只是一個回收動作，實際上在get的時候還要進行時間判斷：
/* expires items that are more recent than the oldest_live setting. */
void item_flush_expired() {
int i;
item *iter, *next;
if (! settings.oldest_live)
return;
for (i = 0; i < LARGEST_ID; i++) {
/* The LRU is sorted in decreasing time order, and an item's timestamp
* is never newer than its last access time, so we only need to walk
* back until we hit an item older than the oldest_live time.
* The oldest_live checking will auto-expire the remaining items.
*/
for (iter = heads[i]; iter != NULL; iter = next) {
if (iter->time >= settings.oldest_live) {
next = iter->next;
if ((iter->it_flags & ITEM_SLABBED) == 0) {
item_unlink(iter);
}
} else {
/* We've hit the first old item. Continue to the next queue. */
break;
}
}
}
}
/* wrapper around assoc_find which does the lazy expiration/deletion logic */
item *get_item_notedeleted(char *key, size_t nkey, int *delete_locked) {
item *it = assoc_find(key, nkey);
if (delete_locked) *delete_locked = 0;
if (it && (it->it_flags & ITEM_DELETED)) {
/* it's flagged as delete-locked. let's see if that condition
is past due, and the 5-second delete_timer just hasn't
gotten to it yet... */
if (! item_delete_lock_over(it)) {
if (delete_locked) *delete_locked = 1;
it = 0;
}
}
if (it && settings.oldest_live && settings.oldest_live <= current_time &&
it->time <= settings.oldest_live) {
item_unlink(it);
it = 0;
}
if (it && it->exptime && it->exptime <= current_time) {
item_unlink(it);
it = 0;
}
return it;
}
|
原文轉自：http://www.uml.org.cn/sjjm/201411134.asp
