Redis 数据结构的实现
?
?Redis 數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)
?
?
?
?
先看個對照關(guān)系：??
| Redis數(shù)據(jù)結(jié)構(gòu) | 實現(xiàn)一 | 實現(xiàn)二 |
| string | 整數(shù)（如果value能夠表示為整數(shù)） | 字符串 |
| hash | 壓縮列表（只包含少量鍵值對， 并且每個鍵值對的鍵和值要么就是小整數(shù)值， 要么就是長度比較短的字符串） | 字典 |
| list | 壓縮列表（只包含少量列表項， 并且每個列表項要么就是小整數(shù)值， 要么就是長度比較短的字符串） | 雙端鏈表 |
| set | 整數(shù)集合（當(dāng)一個集合只包含整數(shù)值元素， 并且這個集合的元素數(shù)量不多時） | 字典 |
| sorted set | 壓縮列表 | 跳表 |
?
再討論每種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)原理：
?
雙端鏈表
?實現(xiàn)如下：
typedef struct listNode {// 前置節(jié)點struct listNode *prev;// 后置節(jié)點struct listNode *next;// 節(jié)點的值void *value;} listNode;typedef struct list {// 表頭節(jié)點listNode *head;// 表尾節(jié)點listNode *tail;// 鏈表所包含的節(jié)點數(shù)量unsigned long len;// 節(jié)點值復(fù)制函數(shù)void *(*dup)(void *ptr);// 節(jié)點值釋放函數(shù)void (*free)(void *ptr);// 節(jié)點值對比函數(shù)int (*match)(void *ptr, void *key);} list;?
?
?
字典（dictionay）?
Redis 的字典使用哈希表作為底層實現(xiàn)，?
哈希表的實現(xiàn)如下：
typedef struct dictht {// 哈希表數(shù)組dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩碼，用于計算索引值// 總是等于 size - 1unsigned long sizemask;// 該哈希表已有節(jié)點的數(shù)量unsigned long used;} dictht;typedef struct dictEntry {// 鍵void *key;// 值 union {void *val;uint64_t u64;int64_t s64;} v;// 指向下個哈希表節(jié)點，形成鏈表struct dictEntry *next;} dictEntry;?
字典的實現(xiàn)：
typedef struct dict {// 類型特定函數(shù)dictType *type;// 私有數(shù)據(jù)void *privdata;// 哈希表，一般情況下只使用ht[0]，rehash才使用ht[1]dictht ht[2];// rehash 索引// 當(dāng) rehash 不在進行時，值為 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;?
?
擴張和收縮（rehash）
隨著操作的不斷執(zhí)行， 哈希表保存的鍵值對會逐漸地增多或者減少， 為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內(nèi)， 當(dāng)哈希表保存的鍵值對數(shù)量太多或者太少時， 程序需要對哈希表的大小進行相應(yīng)的擴展或者收縮。
rehash步驟：
- 如果執(zhí)行的是擴展操作， 那么?ht[1]?的大小為第一個大于等于?ht[0].used?*?2?的?2^n?（2?的?n?次方冪）；
- 如果執(zhí)行的是收縮操作， 那么?ht[1]?的大小為第一個大于等于?ht[0].used?的?2^n?。
當(dāng)以下條件中的任意一個被滿足時， 程序會自動開始對哈希表執(zhí)行擴展操作：
其中哈希表的負載因子可以通過公式：
# 負載因子 = 哈希表已保存節(jié)點數(shù)量 / 哈希表大小 load_factor = ht[0].used / ht[0].size根據(jù)?BGSAVE?命令或?BGREWRITEAOF?命令是否正在執(zhí)行， 服務(wù)器執(zhí)行擴展操作所需的負載因子并不相同， 這是因為在執(zhí)行?BGSAVE命令或?BGREWRITEAOF?命令的過程中， Redis 需要創(chuàng)建當(dāng)前服務(wù)器進程的子進程， 而大多數(shù)操作系統(tǒng)都采用寫時復(fù)制（copy-on-write）技術(shù)來優(yōu)化子進程的使用效率， 所以在子進程存在期間， 服務(wù)器會提高執(zhí)行擴展操作所需的負載因子， 從而盡可能地避免在子進程存在期間進行哈希表擴展操作， 這可以避免不必要的內(nèi)存寫入操作， 最大限度地節(jié)約內(nèi)存。
另一方面， 當(dāng)哈希表的負載因子小于?0.1?時， 程序自動開始對哈希表執(zhí)行收縮操作。
為了避免 rehash 對服務(wù)器性能造成影響， 服務(wù)器不是一次性將?ht[0]?里面的所有鍵值對全部 rehash 到?ht[1]?， 而是分多次、漸進式地將?ht[0]?里面的鍵值對慢慢地 rehash到?ht[1]?。以下是哈希表漸進式 rehash 的詳細步驟：
漸進式 rehash 的好處在于它采取分而治之的方式， 將 rehash 鍵值對所需的計算工作均灘到對字典的每個添加、刪除、查找和更新操作上， 從而避免了集中式 rehash 而帶來的龐大計算量。
因為在進行漸進式 rehash 的過程中， 字典會同時使用?ht[0]?和?ht[1]?兩個哈希表， 所以在漸進式 rehash 進行期間， 字典的刪除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進行： 比如說， 要在字典里面查找一個鍵的話， 程序會先在?ht[0]里面進行查找， 如果沒找到的話， 就會繼續(xù)到?ht[1]?里面進行查找， 諸如此類。
另外， 在漸進式 rehash 執(zhí)行期間， 新添加到字典的鍵值對一律會被保存到?ht[1]?里面， 而?ht[0]?則不再進行任何添加操作： 這一措施保證了?ht[0]?包含的鍵值對數(shù)量會只減不增， 并隨著 rehash 操作的執(zhí)行而最終變成空表。
?
?
?
整數(shù)集合（intset）
?整數(shù)集合是用一個有序數(shù)組實現(xiàn)的，
typedef struct intset {// 編碼方式 uint32_t encoding;// 集合包含的元素數(shù)量 uint32_t length;// 保存元素的數(shù)組 int8_t contents[];} intset;雖然?intset?結(jié)構(gòu)將?contents?屬性聲明為?int8_t?類型的數(shù)組， 但實際上?contents?數(shù)組的真正類型取決于?encoding?屬性的值：
- 如果?encoding?屬性的值為?INTSET_ENC_INT16?， 那么?contents?就是一個?int16_t?類型的數(shù)組， 數(shù)組里的每個項都是一個?int16_t?類型的整數(shù)值 （最小值為?-32,768?，最大值為?32,767?）。
- 如果?encoding?屬性的值為?INTSET_ENC_INT32?， 那么?contents?就是一個?int32_t?類型的數(shù)組， 數(shù)組里的每個項都是一個?int32_t?類型的整數(shù)值 （最小值為?-2,147,483,648?，最大值為?2,147,483,647?）。
- 如果?encoding?屬性的值為?INTSET_ENC_INT64?， 那么?contents?就是一個?int64_t?類型的數(shù)組， 數(shù)組里的每個項都是一個?int64_t?類型的整數(shù)值 （最小值為?-9,223,372,036,854,775,808?，最大值為?9,223,372,036,854,775,807?）。
?
升級（upgrade）
intset 的升級操作：例如當(dāng)向一個底層為?int16_t?數(shù)組的整數(shù)集合添加一個?int64_t?類型的整數(shù)值時， intset 已有的所有元素都會被轉(zhuǎn)換成?int64_t?類型。
升級整數(shù)集合并添加新元素共分為三步進行：
?升級之后新元素的擺放位置
因為引發(fā)升級的新元素的長度總是比整數(shù)集合現(xiàn)有所有元素的長度都大， 所以這個新元素的值要么就大于所有現(xiàn)有元素， 要么就小于所有現(xiàn)有元素：
- 在新元素小于所有現(xiàn)有元素的情況下， 新元素會被放置在底層數(shù)組的最開頭（索引?0?）；
- 在新元素大于所有現(xiàn)有元素的情況下， 新元素會被放置在底層數(shù)組的最末尾（索引?length-1?）。
?注意：intset不支持降級！
?
?
跳表（skiplist）
數(shù)據(jù)結(jié)構(gòu)定義如下：
typedef struct zskiplistNode {// 后退指針struct zskiplistNode *backward;// 分值double score;// 成員對象robj *obj;// 層struct zskiplistLevel {// 前進指針struct zskiplistNode *forward;// 跨度unsigned int span;} level[];} zskiplistNode;typedef struct zskiplist {// 表頭節(jié)點和表尾節(jié)點struct zskiplistNode *header, *tail;// 表中節(jié)點的數(shù)量unsigned long length;// 表中層數(shù)最大的節(jié)點的層數(shù)int level;} zskiplist;?
?
上圖展示了一個跳躍表示例， 位于圖片最左邊的是?zskiplist?結(jié)構(gòu)， 該結(jié)構(gòu)包含以下屬性：
- header?：指向跳躍表的表頭節(jié)點。
- tail?：指向跳躍表的表尾節(jié)點。
- level?：記錄目前跳躍表內(nèi)，層數(shù)最大的那個節(jié)點的層數(shù)（表頭節(jié)點的層數(shù)不計算在內(nèi)）。
- length?：記錄跳躍表的長度，也即是，跳躍表目前包含節(jié)點的數(shù)量（表頭節(jié)點不計算在內(nèi)）。
位于?zskiplist?結(jié)構(gòu)右方的是四個?zskiplistNode?結(jié)構(gòu)， 該結(jié)構(gòu)包含以下屬性：
- 層（level）：節(jié)點中用?L1?、?L2?、?L3?等字樣標記節(jié)點的各個層，?L1?代表第一層，?L2?代表第二層，以此類推。每個層都帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他節(jié)點，而跨度則記錄了前進指針所指向節(jié)點和當(dāng)前節(jié)點的距離。在上面的圖片中，連線上帶有數(shù)字的箭頭就代表前進指針，而那個數(shù)字就是跨度。當(dāng)程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。
- 后退（backward）指針：節(jié)點中用?BW?字樣標記節(jié)點的后退指針，它指向位于當(dāng)前節(jié)點的前一個節(jié)點。后退指針在程序從表尾向表頭遍歷時使用。
- 分值（score）：各個節(jié)點中的?1.0?、?2.0?和?3.0?是節(jié)點所保存的分值。在跳躍表中，節(jié)點按各自所保存的分值從小到大排列。
- 成員對象（obj）：各個節(jié)點中的?o1?、?o2?和?o3?是節(jié)點所保存的成員對象。
?
?
?
?
壓縮列表（ziplist）
ziplist是由若干個entry 組成，每個entry可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。
?
?
| zlbytes | uint32_t | 4? | 記錄整個壓縮列表占用的內(nèi)存字節(jié)數(shù)：在對壓縮列表進行內(nèi)存重分配， 或者計算?zlend的位置時使用。 |
| zltail | uint32_t | 4? | 記錄壓縮列表表尾節(jié)點距離壓縮列表的起始地址有多少字節(jié)： 通過這個偏移量，程序無須遍歷整個壓縮列表就可以確定表尾節(jié)點的地址。 |
| zllen | uint16_t | 2? | 記錄了壓縮列表包含的節(jié)點數(shù)量： 當(dāng)這個屬性的值小于?UINT16_MAX?（65535）時， 這個屬性的值就是壓縮列表包含節(jié)點的數(shù)量； 當(dāng)這個值等于?UINT16_MAX?時， 節(jié)點的真實數(shù)量需要遍歷整個壓縮列表才能計算得出。 |
| entryX | 列表節(jié)點 | 不定 | 壓縮列表包含的各個節(jié)點，節(jié)點的長度由節(jié)點保存的內(nèi)容決定。 |
| zlend | uint8_t | 1? | 特殊值?0xFF?（十進制?255?），用于標記壓縮列表的末端。 |
?
?
?entry
entry可以保存一個字節(jié)數(shù)組或者一個整數(shù)值， 其中， 字節(jié)數(shù)組可以是以下三種長度的其中一種：
而整數(shù)值則可以是以下六種長度的其中一種：
每個壓縮列表entry都由?previous_entry_length?、?encoding?、?content?三個部分組成，
?
| 屬性 | 類型 | 長度 | 用途 |
| previous_entry_length | 整型 | 1（小于254）或5（大于或等于254） | 前一個entry的長度 |
| encoding | 整型 | ? | 記錄content的類型和長度 |
| content | 整數(shù)或字節(jié)數(shù)組 | ? | ?entry的值 |
?
?
?
?
?
連鎖更新（cascade update）
現(xiàn)在， 考慮這樣一種情況： 在一個壓縮列表中， 有多個連續(xù)的、長度介于?250?字節(jié)到?253?字節(jié)之間的節(jié)點?e1?至?eN?，如下圖：
因為?e1?至?eN?的所有節(jié)點的長度都小于?254?字節(jié)， 所以記錄這些節(jié)點的長度只需要?1?字節(jié)長的?previous_entry_length?屬性， 換句話說，?e1?至?eN?的所有節(jié)點的?previous_entry_length?屬性都是?1?字節(jié)長的。?
這時， 如果我們將一個長度大于等于?254?字節(jié)的新節(jié)點?new?設(shè)置為壓縮列表的表頭節(jié)點， 那么?new?將成為?e1?的前置節(jié)點， 如圖 ?
因為?e1?的?previous_entry_length?屬性僅長?1?字節(jié)， 它沒辦法保存新節(jié)點?new?的長度， 所以程序?qū)嚎s列表執(zhí)行空間重分配操作， 并將?e1?節(jié)點的?previous_entry_length?屬性從原來的?1?字節(jié)長擴展為?5?字節(jié)長。
現(xiàn)在， 麻煩的事情來了 ——?e1?原本的長度介于?250?字節(jié)至?253?字節(jié)之間， 在為?previous_entry_length?屬性新增四個字節(jié)的空間之后，e1?的長度就變成了介于?254?字節(jié)至?257?字節(jié)之間， 而這種長度使用?1?字節(jié)長的?previous_entry_length?屬性是沒辦法保存的。
因此， 為了讓?e2?的?previous_entry_length?屬性可以記錄下?e1?的長度， 程序需要再次對壓縮列表執(zhí)行空間重分配操作， 并將?e2?節(jié)點的?previous_entry_length?屬性從原來的?1?字節(jié)長擴展為?5?字節(jié)長。
正如擴展?e1?引發(fā)了對?e2?的擴展一樣， 擴展?e2?也會引發(fā)對?e3?的擴展， 而擴展?e3?又會引發(fā)對?e4?的擴展……為了讓每個節(jié)點的?previous_entry_length?屬性都符合壓縮列表對節(jié)點的要求， 程序需要不斷地對壓縮列表執(zhí)行空間重分配操作， 直到?eN?為止。
Redis 將這種在特殊情況下產(chǎn)生的連續(xù)多次空間擴展操作稱之為“連鎖更新”。
除了添加新節(jié)點可能會引發(fā)連鎖更新之外， 刪除節(jié)點也可能會引發(fā)連鎖更新。
因為連鎖更新在最壞情況下需要對壓縮列表執(zhí)行?N?次空間重分配操作， 而每次空間重分配的最壞復(fù)雜度為?O(N)?， 所以連鎖更新的最壞復(fù)雜度為?O(N^2)?。
?
?
?
參考文檔：
http://redisbook.com/
?
總結(jié)
以上是生活随笔為你收集整理的Redis 数据结构的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 我对if(!this.IsPostBac
- 下一篇： 一篇文章带你了解Cloud Native