《Redis設計與實現》[第一部分]數據結構與對象

四、跳躍表

關鍵字：層高隨機

跳躍表支持平均O（logN）、最壞O(N)復雜度的結點查找，還可以通過順序性操作來批量處理結點。

在大部分情況下，跳躍表的效率可以和平衡樹相媲美，因為跳躍表的實現比平衡樹來得更為簡單，所以不少程序都使用跳躍表代替平衡樹。

Redis使用跳躍表作為有序集合鍵的底層實現之一，如果有一個有序集合包含的元素數量比較多，或有序集合中元素的成員是比較長的字符串時，Redis就會使用跳躍表作為有序集合鍵的底層實現。

Redis只在兩個地方用到了跳躍表，一個是實現有序集合鍵，另一個是在集群結點中用作內部數據結構

數據結構源碼

Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結構定義：

/*
 * 跳躍表節點
 */
typedef struct zskiplistNode {

    // 成員對象
    robj *obj;

    // 分值
    double score;

    // 後退指針
    struct zskiplistNode *backward;

    // 層
    struct zskiplistLevel {

        // 前進指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

zskiplistNode結構包含以下屬性：

層（level）數組可以包含多個元素：每個層帶有兩個屬性：前進指針和跨度。前進指針用於訪問位於表尾方向的其他結點，而跨度則記錄了前進指針所指向結點和當前節點的距離。當程序從表頭向表尾進行遍歷時，訪問會沿著層的前進指針進行。層的數量越多，訪問其他結點的速度就越快。

每次創建一個新跳躍表結點，程序都根據冪次定律（power law，越大的數出現的概率越小）隨機生成一個介於1和32之間的值作為level數組的大小，即層的高度。 前進指針為NULL的層跨度為0

後退（backward）指針：結點中用BW字樣標記結點的後退指針，它指向位於當前節點的前一個結點。後退指針在程序從表尾向表頭遍歷時使用。與可以一次跳過多個結點的前進指針不同，每個結點只有一個後退指針，所以每次只能後退至前一個結點

分值（score）：一個double類型的浮點數，跳躍表中，結點按各自所保存的分值從小到大排列

成員對象（obj）：一個指針，指向保存著一個SDS值的字符串對象 在同一個跳躍表中，各個節點保存的成員對象必須是唯一的，但是多個結點保存的分值可以相同：分值相同的結點按照成員對象在字典序中的大小排序，較小的排在前面（靠近表頭）

/*
 * 跳躍表
 */
typedef struct zskiplist {

    // 表頭節點和表尾節點
    struct zskiplistNode *header, *tail;

    // 表中節點的數量
    unsigned long length;

    // 表中層數最大的節點的層數
    int level;

} zskiplist;

zskiplist結構用於保存跳躍表結點的相關信息，如結點數量，指向表頭結點和表尾結點的指針等：

header:指向跳躍表的表頭結點 tail：指向跳躍表的表尾結點 level：記錄目前跳躍表內，層數最大的那個結點的層數（表頭結點的層數不計算在內） length:記錄跳躍表的長度，即，跳躍表目前包含結點的數量（表頭結點不計算在內）

表頭結點和其他結點的構造是一樣的：表頭結點也有後退指針、分值和成員對象，不過表頭結點的這些屬性都不會被用到。

五、整數集合

關鍵字：升級規則

整數集合（intset）是集合鍵的底層實現之一，當一個集合只包含整數值元素，並且這個集合的元素數量不多時，Redis就使用整數集合作為集合鍵的底層實現。

數據結構源碼

typedef struct intset {

    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素數量
    uint32_t length;

    // 保存元素的數組
    int8_t contents[];

} intset;

整數集合（intset）是Redis用於保存整數值的集合抽象數據結構，可以保存類型為int16_t、int32_t或int64_t的整數值，並且保證集合中不會出現重復元素。

contents數組是 整數集合的底層實現：整數集合的每個元素都是contents數組的一個數組項，各個項在數組中按值的大小從小到大有序排列，並且數組中不包含任何重復項

length屬性記錄了整數集合包含的元素數量，即contents數組的長度

encoding屬性：雖然intset結構將contents屬性聲明為int8_t類型的數組，但實際上contents數組並不保存任何int8_t類型的值，contents數組的真正類型取決於encoding屬性的值

若encoding屬性的值為INTSET_ENC_INT16,那麼contents就是一個int16_t類型的數組，數組裡的每個項都是一個int16_t類型的整數值（最小為-32768，最大為32767） 如果encoding屬性的值為INTSET_ENC_INT32，那麼contents是一個int32_t類型的數組，每個項都是一個int32_t類型的整數值（最小-2147483648，最大2147483647） 如果encoding屬性的值為INTSET_ENC_INT64，那麼contents是一個int64_t類型的數組，數組每個項是一個int64_t類型的整數值（最小為-9223372036854775808，最大為9223372036854775807）

整數集合的升級策略

當將一個新元素添加到整數集合裡面，並且新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行升級（upgrade），然後才能將新元素添加到整數集合裡面。

升級整數集合並添加新元素共分為三步進行：

根據新元素的類型，擴展整數集合底層數組的空間大小，並為新元素分配空間 將底層數組現有的所有元素都轉換成與新元素相同的類型，並將類型轉換後的元素放置到正確的位置上，而且在放置元素的過程中，需要繼續維持底層數組的有序性質不變 講新元素添加到底層數組裡面

因為每次向整數集合添加新元素都可能會引起升級，而每次升級都需要對底層數組中已有的所有元素進行類型轉換，所以向整數集合添加新元素的時間復雜度為O(N)

引發升級的新元素長度總是比整數集合現有所有元素的長度都大，所以這個新元素的值要麼大於所有現有元素，要麼小於所有現有元素：

新元素小於所有現有元素，新元素會被放置在底層數組的最開頭（索引0） 新元素大於所有現有元素，新元素放置在底層數組的最末尾（索引length-1）

整數集合的升級策略有兩個好處：

提升整數集合的靈活性，可以隨意將int16_t、int32_t或int64_t類型的整數添加到集合中，不必擔心出現類型錯誤

節約內存，這樣做可以讓集合能同時保存三種不同類型的值，又可以確保升級操作只會在有需要的時候進行

整數集合不支持降級操作，一旦對數組升級，編碼就會一直保持升級後的狀態。

六、壓縮列表

關鍵字：連鎖更新

壓縮列表（ziplist）是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項，且每個列表項要麼是小整數值，要麼是長度比較短的字符串，那麼Redis就會是一壓縮列表來做列表鍵的底層實現

壓縮列表是Redis為了節約內存開發的，是由一系列特殊編碼的連續內存塊組成的順序型（sequential）數據結構。一個壓縮列表可以包含任意多個結點（Entry），每個結點保存一個字節數組或一個整數值。

數據結構源碼

/* 
空白 ziplist 示例圖

area        |<---- ziplist header ---->|<-- end -->|

size          4 bytes   4 bytes 2 bytes  1 byte
            +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
            |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
            +---------+--------+-------+-----------+
                                       ^
                                       |
                               ZIPLIST_ENTRY_HEAD
                                       &
address                        ZIPLIST_ENTRY_TAIL
                                       &
                               ZIPLIST_ENTRY_END

非空 ziplist 示例圖

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL
*/

zlbytes屬性:uint32_t類型，4個字節，記錄整個壓縮列表占用的內存字節數：在對壓縮列表進行內存重分配，或計算zlend的位置時使用 zltail屬性：uint32_t類型，4個字節，記錄壓縮列表表尾結點距離壓縮列表的起始地址有多少字節：通過這個偏移量，無須遍歷整個壓縮列表就可以確定表尾結點的地址 zllen屬性：uint16_t類型，2個字節，記錄了壓縮列表包含的結點數量：當這個值小於uint16_max（65535）時，這個值是壓縮列表包含結點的數量；當這個值等於uint16_max時，結點的真實數量需要遍歷整個壓縮列表才能計算出 extryX屬性：列表結點，字節數不定，壓縮列表包含的各個節點，結點的長度由節點保存的內容決定 zlend屬性：uint8_t類型，1個字節，特殊值0xFF（十進制255），用於標記壓縮列表的末端

/*
 * 保存 ziplist 節點信息的結構
 */
typedef struct zlentry {

    // prevrawlen ：前置節點的長度
    // prevrawlensize ：編碼 prevrawlen 所需的字節大小
    unsigned int prevrawlensize, prevrawlen;

    // len ：當前節點值的長度
    // lensize ：編碼 len 所需的字節大小
    unsigned int lensize, len;

    // 當前節點 header 的大小
    // 等於 prevrawlensize + lensize
    unsigned int headersize;

    // 當前節點值所使用的編碼類型
    unsigned char encoding;

    // 指向當前節點的指針
    unsigned char *p;

} zlentry;

每個壓縮列表結點可以保存一個字節數組或者一個整數值，其中，字節數組可以是以下三種長度的其中一種：

長度小於等於63（2^6-1）字節的字節數組 長度小於等於16383（2^14-1）字節的字節數組 長度小於等於4294967295（2^32-1）字節的字節數組

整數值則可以是以下中的一種：

4位長，介於0到12之間的無符號整數 1字節長的有符號整數 3字節長的有符號整數 int16_t類型整數 int32_t類型整數 int64_t類型整數

每個壓縮列表結點都由previous_entry_length、encoding、content三個部分：

結點的previous_entry_length屬性以字節為單位，記錄了壓縮列表中前一個結點的長度。previous_entry_length屬性的長度可以是1字節或5字節

若前一結點的長度小於254字節，那麼previous_entry_length的長度為1字節：前一結點的長度就保存在這一個字節裡面

如果前一結點長度大於等於254字節，那麼previous_entry_length屬性的長度為5字節：其中屬性的第一字節會被設置為0xFE（十進制254），而之後的四個字節則用於保存前一結點的長度

因為結點的previous_entry_length屬性記錄了前一個結點的長度，所以程序可以通過指針運算，根據當前節點的起始地址計算出前一個結點的起始地址

壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實現的，只要擁有一個指向某個結點起始地址的指針，那麼通過這個指針以及這個結點的previous_entry_length屬性，就可以一直向前一個結點回溯，最終到達壓縮列表的表頭結點。

encoding屬性記錄了結點的content屬性所保存數據的類型以及長度：

一字節、兩字節或五字節長，值的最高位為00、01或者10的是字節數組編碼：這種編碼表示節點的content屬性保存著字節數組，數組的長度由編碼除去最高兩位之後的其他位記錄 一字節長，值的最高位以11開頭的是整數編碼：這種編碼表示節點的content屬性保存著整數值，整數值的類型和長度由編碼最高兩位之後的其他位記錄

content屬性保存結點的值，結點值可以是一個字節數組或整數，值的類型和長度由節點的encoding屬性決定

連鎖更新

壓縮列表的添加新節點操作和刪除結點操作都可能會引發連鎖更新：

連鎖更新在最壞情況下需要對壓縮列表執行N次空間重分配操作，而每次空間重分配的最壞復雜度為O（N），所以連鎖更新的最壞復雜度為O(N^2)

盡管連鎖更新的復雜度較高，但它真正造成性能問題的可能性不大：

壓縮列表要恰好有多個連續、長度介於250字節到253字節之間的結點，連鎖更新才可能被引發 其次，即使出現連鎖更新，但只要被更新的結點數量不多，就不會對性能造成影響

七、對象

關鍵字：編碼轉換，多態命令，內存回收與共享，LRU

Redis基於以上數據結構創建了一個對象系統，這個系統包含字符串對象、列表對象、哈希對象、集合對象和有序集合對象這五種類型的對象，每種對象都用到了至少一種以上數據結構。

使用對象的好處：

Redis執行命令前，根據對象的類型判斷一個對象是否可以執行給定命令 可以針對不同的使用場景，為對象設置多種不同的數據結構實現，從而優化對象在不同場景下的使用效率 Redis的對象系統實現了基於引用計數技術的內存回收機制，當程序不再使用某個對象的時候，這個對象所占用的內存就會被自動釋放 Redis還通過引用計數技術實現了對象共享機制，通過讓多個數據庫鍵共享同一個對象來節約內存 Redis的對象帶有訪問時間記錄信息，該信息可以用於計算數據庫鍵的空轉時長，在服務器啟用maxmemory功能的情況下，空轉時長大的那些鍵可能會被優先刪除

數據結構源碼

Redis使用對象來表示數據庫中的鍵和值，數據庫中新創建一個鍵值對時，至少會創建兩個對象：鍵對象，用作鍵值對的鍵，值對象，用作鍵值對的值

typedef struct redisObject {

    // 類型
    unsigned type:4;

    // 編碼
    unsigned encoding:4;

    // 對象最後一次被訪問的時間，用於計算對象的空轉時長
    // 當服務器占用的內存數超過了maxmemory選項設置的上限時，空轉時長高的那部分鍵會優先被服務器釋放，從而回收內存
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用計數
    int refcount;

    // 指向實際值的指針
    void *ptr;

} robj;

Redis中的每個對象都由一個redisObject結構表示，該結構中的type屬性、encoding屬性和ptr屬性與保存數據有關：

type屬性記錄對象的類型，是常量，可選值有REDIS_STRING字符串對象，REDIS_LIST列表對象，REDIS_HASH哈希對象，REDIS_SET集合對象，REDIS_ZSET有序集合對象

對於Redis數據庫保存的鍵值對來說，鍵總是一個字符串對象，而值則可以是字符串對象、列表對象、哈希對象、集合對象或者有序集合對象的一種

type命令的實現方式也類似，對一個數據庫鍵執行type命令時，命令返回的結果為數據庫鍵對應的值對象的類型。

encoding屬性記錄了對象所使用的編碼，即對象使用了什麼數據結構作為對象的底層實現

通過encoding設定對象所使用的編碼，使得Redis可以根據不同的使用場景為一個對象設置不同的編碼，從而優化對象在某一場景下的效率

字符串對象的編碼轉換

字符串對象的編碼可以是int、raw或embstr。

如果一個字符串對象保存的是long類型的整數值，那麼字符串對象會將整數值保存在字符串對象結構的ptr屬性裡（將void*轉換成long），並將字符串對象的編碼設置為int。

如果字符串對象保存的是一個字符串值，並且這個字符串值的長度小於等於32字節，那麼字符串對象將使用embstr編碼的方式來保存這個字符串值。

可以用long double類型表示的浮點數在Redis中也是作為字符串值保存的。

對於int編碼的字符串對象，如果我們向對象執行了一些命令，使對象保存的不再是整數，而是一個字符串值，那麼字符串對象的編碼將從int變為raw。

embstr編碼的字符串對象實際上是只讀的。對embstr編碼的字符串對象執行任何修改命令時，程序會先將對象的編碼從embstr轉換成raw，然後再執行修改命令。所以，embstr編碼的字符串對象在執行修改命令後，總會變成一個raw編碼的字符串對象

列表對象的編碼轉換

列表對象的編碼可以是ziplist或Linkedlist。

ziplist編碼的列表對象使用壓縮列表作為底層實現，每個壓縮列表結點（Entry）保存了一個列表元素。

Linkedlist編碼的列表對象使用雙端鏈表作為底層實現，每個雙端鏈表結點（Node）保存一個字符串對象，而每個字符串對象保存一個列表元素。

當列表對象同時滿足以下兩個條件時，列表對象使用ziplist編碼：

列表對象保存的所有字符串元素的長度都小於64字節 列表對象保存的元素數量小於512個

否則使用linkedlist編碼。

哈希對象的編碼轉換

哈希對象的編碼可以是ziplist或hashtable。

ziplist編碼的哈希對象使用壓縮列表作為底層實現，每當有新的鍵值對要加入到哈希對象時，程序會先將保存鍵的壓縮列表結點推入到壓縮列表表尾，然後再將保存值的壓縮列表結點推入到壓縮列表表尾：

保存了統一鍵值對的兩個結點總是緊挨在一起，保存鍵的結點在前，保存值的結點在後 先添加到哈希對象中的鍵值對會被放在壓縮列表的表頭方向，而後來添加到哈希對象的鍵值對在壓縮列表的表尾方向

hashtable編碼的哈希對象使用字典作為底層實現，哈希對象中的每個鍵值對都使用一個字典鍵值對來保存：

字典的每個鍵都是一個字符串對象，對象中保存了鍵值對的鍵 字典的每個值都是一個字符串對象，對象中保存了鍵值對的值

當哈希對象同時滿足下列兩個條件時，哈希對象使用ziplist編碼：

哈希對象保存的所有鍵值對的鍵和值的字符串長度都小於64字節 哈希對象保存的鍵值對數量小於512個

否則需要使用hashtable編碼。

集合對象的編碼轉換

集合對象的編碼可以是intset或hashtable。

intset編碼的集合對象使用整數集合作為底層實現，集合對象包含的所有元素都被保存在整數集合裡。

hashtable編碼的集合對象使用字典作為底層實現，字典的每個鍵都是一個字符串對象，每個字符串對象包含一個集合元素，而字典的值則全部被設置為null.

當滿足以下兩個條件時，使用intset編碼：

集合對象保存的所有元素都是整數值 集合對象保存的元素數量不超過512個

否則使用hashtable編碼。

有序集合對象的編碼轉換

有序集合的編碼可以是ziplist或skiplist。

ziplist編碼的有序集合對象使用壓縮列表作為底層實現，每個集合元素使用兩個緊挨在一起的壓縮列表結點保存，第一個結點保存元素的成員（member），第二個元素則保存元素的分值（score）。

壓縮列表內的集合元素按分值從小到大進行排序，分值較小的元素靠近表頭的方向，分值較大靠近表尾。

skiplist編碼的有序集合對象使用zset結構作為底層實現，一個zset結構同時包含一個字典和一個跳躍表：

/*
 * 有序集合
 */
typedef struct zset {

    // 字典，鍵為成員，值為分值
    // 用於支持 O(1) 復雜度的按成員取分值操作
    dict *dict;

    // 跳躍表，按分值排序成員
    // 用於支持平均復雜度為 O(log N) 的按分值定位成員操作
    // 以及范圍操作
    zskiplist *zsl;

} zset;

有序集合每個元素的成員都是一個字符串對象，而每個元素的分值都是一個double類型的浮點數。

雖然zset結構同時使用跳躍表和字典來保存有序集合元素，但這兩種數據結構都會通過指針來共享相同元素的成員和分值，所以同時使用跳躍表和字典保存集合元素，不會產生重復成員和分值，不會因此浪費額外內存。

滿足以下兩個條件時，對象使用ziplist編碼：

有序集合保存的元素數量小於128個 有序集合保存的所有元素成員的長度都小於64字節

否則有序集合對象使用skiplist編碼。

類型檢查與命令多態

Redis中用於操作鍵的命令可分為兩種類型：

一種可以對任何類型的鍵執行，比如del命令、expire命令、rename命令、type命令、Object命令 一種智能對特定類型的鍵執行的命令

在執行一個類型特定的命令之前，Redis會先檢查輸入鍵的類型是否正確，然後再決定是否執行給定的命令。

類型特定命令的類型檢查是通過redisObject結構的type屬性來實現的：

在執行一個類型特定命令之前，服務器會先檢查輸入數據庫鍵的值對象是否為執行命令所需的類型，若是，執行命令； 否則服務器拒絕執行命令，並向客戶端返回一個類型錯誤。

Redis還會根據對象的編碼方式，選擇正確的命令實現代碼來執行命令。

內存回收與對象共享

Redis通過引用計數技術實現內存回收機制。

對象的引用計數信息會隨著對象的使用狀態而不斷變化：

在創建一個新對象時，引用計數的值會被初始化為1 當對象被一個新程序使用時，它的引用計數加一 當對象不再被一個程序使用時，它的引用計數減一 當對象的引用計數值變為0時，對象所占用的內存會被釋放

基於引用計數的對象共享機制使Redis更節約內存。

Redis的共享對象包括字符串鍵，以及那些在數據結構中嵌套了字符串對象的對象（linkedlist編碼的列表對象、hashtable編碼的哈希對象、hashtable編碼的集合對象，zset編碼的有序集合對象）也可以使用這些共享對象。

Redis只對包含整數值的字符串對象進行共享。