Redis 之字典和跳錶

1 人贊了文章

字典

Redis整個資料庫其實就是一個大的字典

set msg "hello world"

以上命令實際上就是設置了資料庫字典中一個key為msg，value為「hello world」

dict相關結構定義：

typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; } v; struct dictEntry *next;} dictEntry;typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used;} dictht;typedef struct dict { dictType *type; void *privdata; dictht ht[2]; int rehashidx; /* rehashing not in progress if rehashidx == -1 */ int iterators; /* number of iterators currently running */} dict;

dictEntry是一個單鏈表實現，next指向下一個結點。v採用了聯合，可以使int64_t 或者void * 或者uint64_t。

dictht即使一個哈希表的實現，簡單講就是一個數組，每個數組上指向一條鏈表，每添加一對鍵值對，講key進行hash運算得到一個值，按一定演算法映射到數組中，哈希演算法必然存在哈希衝突，對於相同的hash的值，掛在同一個鏈表上。

idx = h & d->ht[table].sizemask; he = d->ht[table].table[idx];

sizemask永遠為size-1，因為數組下標從0開始，hash與sizemask與即可計算出數組下標。

size表示數組的大小，used記錄已使用結點的數量,rehash時會減少。會用於評估負載因子

注意：這個used統計的只是table數組中的已使用的數量，不會統計鏈表中的量。

dict里的ht[2],適用於rehash的，根據負載因子，判斷是否需要rehash，進行hash表擴容，

if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)){ return dictExpand(d, d->ht[0].used*2);}

rehashidx默認為-1，如果需要rehash，在dictExpand函數里會將它置為0。

d->ht[1] = n;d->rehashidx = 0;

初始的ht是ht[0],擴容後將新哈希表設置為 1 號哈希表，將字典的 rehash 標識打開開始對字典進行 rehash。

dictType實際上定義了一些操作特定鍵值對的函數，其中包括複製值，複製鍵，計算hash等。

hash表的hash演算法選取尤為重要，要避免大量的hash衝突，而且分散隨機，不然性能退化很嚴重，dict的hash演算法選取了MurmurHash，這個知道一下就好了。

漸進式rehash：

一旦判定需要rehash怎麼辦？直接rehash嗎?redis是單線程的，直接進行rehash，所有的後續請求都會被阻塞到那，redis並沒有直接全部rehash，通過rehashidx記錄了rehash的數組下標，將整個rehash分散到各個請求中。單步rehash，也支持按時間批量rehash。

static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1);}int dictRehashMilliseconds(dict *d, int ms) { long long start = timeInMilliseconds(); int rehashes = 0; while(dictRehash(d,100)) { rehashes += 100; if (timeInMilliseconds()-start > ms) break; } return rehashes;}

單步rehash會分布到find，get，delete, add中

dictEntry *dictFind(dict *d, const void *key){ if (dictIsRehashing(d)) _dictRehashStep(d);}dictEntry *dictAddRaw(dict *d, void *key){ if (dictIsRehashing(d)) _dictRehashStep(d);}...

注意一點，在進行添加的時候，是需要根據當前是否在rehash，在添加到新ht，不再放舊的。

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

在刪除的時候，同樣也要做類似的判斷，都需要操作。find的時候，實際上只要沒有rehash結束，需要在兩個ht里都尋找，因為指向的是指針，所以無論哪一個找到都可以返回了。

if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0;}

當rehash結束後，釋放掉ht[0]原有內容，重新指向ht[1],重置rehashidx 為-1。

跳錶

跳錶(skiplist)是一種有序數據結構，雙鏈表結構，在每個節點上維護了多個指向後序節點的指針，可以快速訪問節點。在Redis中Z開頭命令操作的有序集合的實現都是基於zskiplist的。

實現代碼：

typedef struct zskiplistNode { robj *obj; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[];} zskiplistNode;

zskiplistNode：

1. 層級：每個節點記錄了多個後序節點的指針，一層一個指向，level包含了多個指向，層越多，訪問跨度越大，概率訪問速度就越快
2. 前進指針：這個和普通的鏈表的next等價，指向下一個鄰近節點。level[0]指向鄰近的節點，方便遍歷
3. 跨度：level[i].span 表示指向節點和當前的距離，指向null的span為0，可以根據span來判定某個節點的排位
4. 後退指針：skiplist是個雙向鏈表，可以根據表尾tail從後向前訪問，每次只能後退一個節點
5. 分值和成員：score為double型，是人為設定的一個分值，用於排序，obj則是指向具體的內容，同一個表中，分值可以相同，但對象必須唯一，zslInsert的時候找插入位置會去比較：

int compareStringObjectsWithFlags(robj *a, robj *b, int flags) { if (a == b) return 0; ... return strcoll(astr,bstr); ...}

多個跳躍節點組成跳躍表：

typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level;} zskiplist;

形成類似的結構：

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) { x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && compareStringObjects(x->level[i].forward->obj,obj) < 0))) { rank[i] += x->level[i].span; x = x->level[i].forward; } update[i] = x; }

插入這裡有講究，從head的最高的level往下找，

1.如果還比指向的節點大，則繼續查找，此時就是一個單鏈表查找了

2.比指向節點小，則再低一層查找

整個過程其實在不斷的縮小查找區間，update[] 記錄每層第一個比他大的節點的前一個節點，最終只有兩種可能，header和將要插入位置的前一個節點,所以下面初始化會直接指向header。這個思考了很久。

rank[]記錄了最後一個比他小的節點和當前指向節點的span跨度和，i 層的起始 rank 值為 i+1 層的 rank 值，層數越低越靠前，rank[0]則表示最終插入點的最終排位

level = zslRandomLevel(); if (level > zsl->level) { for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; }

隨機生成一個level層數，實際上為了保證隨機性，跳錶追求的是概率性平衡 。

如果新節點的層數比表中其他節點的層數都要大，update[i]直接指向header，level[i]的span直接設置為最大length。更新zsl->level為最新。

x = zslCreateNode(level,score,obj); for (i = 0; i < level; i++) { x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; /* update span covered by update[i] as x is inserted here */ x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); update[i]->level[i].span = (rank[0] - rank[i]) + 1; } /* increment span for untouched levels */ for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; else zsl->tail = x; zsl->length++; return x;}//end zslInsert

for循環里等同於雙向鏈表的插入，以及更新span。跳錶是帶頭結點的，如果0層為header，則x就是第一個節點，backword設為NULL，不是則指向update[0]，如果沒有forward則為尾節點，更新zsl的tail，length++。

Redis的實現代碼簡直是C的典範，沒有一行多餘代碼，就這一個函數，就挺費腦子的，我想《Redis設計和實現》在跳錶這一章並沒有講具體的插入，也是因為講了，還是要費些勁兒理解，不過這書還是一本通俗易懂的書。

寫此文耗挺費時間的，當然我的理解也加深了，學習就該腳踏實地，吃透。

skiplist的演算法性能分析這又是一個話題，寫此文的時候，看到了之前一同事張鐵蕾寫的skiplist，對問題理解之深。網上大量的都是轉載他的文章。