簡單動態字串

導讀

Redis 只會使用 C 字串作為字面量，在大多數情況下， Redis 使用 SDS （Simple Dynamic String，簡單動態字串）作為字串表示，
比起 C 字串， SDS 具有以下優點：

1. 常數復雜度獲取字串長度，
2. 杜絕緩沖區溢位，
3. 減少修改字串長度時所需的記憶體重分配次數，
4. 二進制安全，
5. 兼容部分 C 字串函式，

簡單動態字串

Redis 沒有直接使用 C 語言傳統的字串表示（以空字符結尾的字符陣列，以下簡稱 C 字串），而是自己構建了一種名為簡單動態字串（simple dynamic string，SDS）的抽象型別，并將 SDS 用作 Redis 的默認字串表示，

SDS 的定義

每個 sds.h/sdshdr 結構表示一個 SDS 值：

struct sdshdr {

    // 記錄 buf 陣列中已使用位元組的數量
    // 等于 SDS 所保存字串的長度
    int len;

    // 記錄 buf 陣列中未使用位元組的數量
    int free;

    // 位元組陣列，用于保存字串
    char buf[];

};

SDS vs C字串

表 2-1 C 字串和 SDS 之間的區別

C 字串	SDS
獲取字串長度的復雜度為O(N)，	獲取字串長度的復雜度為O(1)，
API 是不安全的，可能會造成緩沖區溢位，	API 是安全的，不會造成緩沖區溢位，
修改字串長度N次必然需要執行N次記憶體重分配，	修改字串長度N次最多需要執行N次記憶體重分配，
只能保存文本資料，	可以保存文本或者二進制資料，
可以使用所有<string.h>庫中的函式，	可以使用一部分<string.h>庫中的函式，

常數復雜度獲取字串長度

通過使用 SDS 而不是 C 字串， Redis 將獲取字串長度所需的復雜度從 O(N) 降低到了 O(1) ，這確保了獲取字串長度的作業不會成為 Redis 的性能瓶頸，

杜絕緩沖區溢位

減少修改字串時帶來的記憶體重分配次數：通過未使用空間， SDS 實作了空間預分配和惰性空間釋放兩種優化策略，

空間預分配 - 通過這種策略， SDS 將連續增長 N 次字串所需的記憶體重分配次數從必定 N 次降低為最多 N 次，

空間預分配用于優化 SDS 的字串增長操作：當 SDS 的 API 對一個 SDS 進行修改，并且需要對 SDS 進行空間擴展的時候，程式不僅會為 SDS 分配修改所必須要的空間，還會為 SDS 分配額外的未使用空間，

其中，額外分配的未使用空間數量由以下公式決定：

如果對 SDS 進行修改之后， SDS 的長度（也即是 len 屬性的值）將小于 1 MB ，那么程式分配和 len 屬性同樣大小的未使用空間，這時 SDS len 屬性的值將和 free 屬性的值相同，舉個例子，如果進行修改之后， SDS 的 len 將變成 13 位元組，那么程式也會分配 13 位元組的未使用空間， SDS 的 buf 陣列的實際長度將變成 13 + 13 + 1 = 27 位元組（額外的一位元組用于保存空字符），

如果對 SDS 進行修改之后， SDS 的長度將大于等于 1 MB ，那么程式會分配 1 MB 的未使用空間，舉個例子，如果進行修改之后， SDS 的 len 將變成 30 MB ，那么程式會分配 1 MB 的未使用空間， SDS 的 buf 陣列的實際長度將為 30 MB + 1 MB + 1 byte ，

惰性空間釋放 - 通過這種策略， SDS 避免了縮短字串時所需的記憶體重分配操作，并為將來可能有的增長操作提供了優化，

惰性空間釋放用于優化 SDS 的字串縮短操作：當 SDS 的 API 需要縮短 SDS 保存的字串時，程式并不立即使用記憶體重分配來回收縮短后多出來的位元組，而是使用 free 屬性將這些位元組的數量記錄起來，并等待將來使用，

與此同時， SDS 也提供了相應的 API ，讓我們可以在有需要時，真正地釋放 SDS 里面的未使用空間，所以不用擔心惰性空間釋放策略會造成記憶體浪費，

二進制安全

所有 SDS API 都會以處理二進制的方式來處理 SDS 存放在 buf 陣列里的資料，程式不會對其中的資料做任何限制、過濾、或者假設 —— 資料在寫入時是什么樣的，它被讀取時就是什么樣，這也是我們將 SDS 的 buf 屬性稱為位元組陣列的原因 —— Redis 不是用這個陣列來保存字符，而是用它來保存一系列二進制資料，
SDS 使用 len 屬性的值而不是空字符來判斷字串是否結束，
通過使用二進制安全的 SDS ，而不是 C 字串，使得 Redis 不僅可以保存文本資料，還可以保存任意格式的二進制資料，

兼容部分 C 字串函式

雖然 SDS 的 API 都是二進制安全的，但它們一樣遵循 C 字串以空字符結尾的慣例：這些 API 總會將 SDS 保存的資料的末尾設定為空字符，并且總會在為 buf 陣列分配空間時多分配一個位元組來容納這個空字符，這是為了讓那些保存文本資料的 SDS 可以重用一部分 <string.h> 庫定義的函式，這樣 Redis 就不用自己專門去實作一套函式，

表 2-2 SDS 的主要操作 API

函式	作用	時間復雜度
sdsnew	創建一個包含給定 C 字串的 SDS ，	O(N)，N為給定 C 字串的長度，
sdsempty	創建一個不包含任何內容的空 SDS ，	O(1)
sdsfree	釋放給定的 SDS ，	O(1)
sdslen	回傳 SDS 的已使用空間位元組數，	這個值可以通過讀取 SDS 的len屬性來直接獲得，復雜度為O(1)，
sdsavail	回傳 SDS 的未使用空間位元組數，	這個值可以通過讀取 SDS 的free屬性來直接獲得，復雜度為 O(1)，
sdsdup	創建一個給定 SDS 的副本（copy），	O(N)，N為給定 SDS 的長度，
sdsclear	清空 SDS 保存的字串內容，	因為惰性空間釋放策略，復雜度為O(1)，
sdscat	將給定 C 字串拼接到 SDS 字串的末尾，	O(N)，N為被拼接 C 字串的長度，
sdscatsds	將給定 SDS 字串拼接到另一個 SDS 字串的末尾，	O(N)，N為被拼接 SDS 字串的長度，
sdscpy	將給定的 C 字串復制到 SDS 里面，覆寫 SDS 原有的字串，	O(N)，N為被復制 C 字串的長度，
sdsgrowzero	用空字符將 SDS 擴展至給定長度，	O(N)，N為擴展新增的位元組數，
sdsrange	保留 SDS 給定區間內的資料，不在區間內的資料會被覆寫或清除，	O(N)，N為被保留資料的位元組數，
sdstrim	接受一個 SDS 和一個 C 字串作為引數，從 SDS 左右兩端分別移除所有在 C 字串中出現過的字符，	O(M*N)，M為 SDS 的長度，N為給定 C 字串的長度，
sdscmp	對比兩個 SDS 字串是否相同，	O(N)，N為兩個 SDS 中較短的那個 SDS 的長度，

鏈表

導讀

鏈表提供了高效的節點重排能力，以及順序性的節點訪問方式，并且可以通過增刪節點來靈活地調整鏈表的長度，因為 Redis 使用的 C 語言并沒有內置這種資料結構，所以 Redis 構建了自己的鏈表實作，

鏈表被廣泛用于實作 Redis 的各種功能，比如串列鍵，發布與訂閱，慢查詢，監視器，等等，
每個鏈表節點由一個 listNode 結構來表示，每個節點都有一個指向前置節點和后置節點的指標，所以 Redis 的鏈表實作是雙端鏈表，
每個鏈表使用一個 list 結構來表示，這個結構帶有表頭節點指標、表尾節點指標、以及鏈表長度等資訊，
因為鏈表表頭節點的前置節點和表尾節點的后置節點都指向 NULL ，所以 Redis 的鏈表實作是無環鏈表，
通過為鏈表設定不同的型別特定函式， Redis 的鏈表可以用于保存各種不同型別的值，

鏈表和鏈表節點的實作

每個鏈表節點使用一個 adlist.h/listNode 結構來表示：

1 typedef struct listNode {
 2 
 3     // 前置節點
 4     struct listNode *prev;
 5 
 6     // 后置節點
 7     struct listNode *next;
 8 
 9     // 節點的值
10     void *value;
11 
12 } listNode;

多個 listNode 可以通過 prev 和 next 指標組成雙端鏈表，如圖 3-1 所示，

雖然僅僅使用多個 listNode 結構就可以組成鏈表，但使用 adlist.h/list 來持有鏈表的話，操作起來會更方便：

 1 typedef struct list {
 2 
 3     // 表頭節點
 4     listNode *head;
 5 
 6     // 表尾節點
 7     listNode *tail;
 8 
 9     // 鏈表所包含的節點數量
10     unsigned long len;
11 
12     // 節點值復制函式
13     void *(*dup)(void *ptr);
14 
15     // 節點值釋放函式
16     void (*free)(void *ptr);
17 
18     // 節點值對比函式
19     int (*match)(void *ptr, void *key);
20 
21 } list;

list 結構為鏈表提供了表頭指標 head 、表尾指標 tail ，以及鏈表長度計數器 len ，而 dup 、 free 和 match 成員則是用于實作多型鏈表所需的型別特定函式：

dup 函式用于復制鏈表節點所保存的值；
free 函式用于釋放鏈表節點所保存的值；
match 函式則用于對比鏈表節點所保存的值和另一個輸入值是否相等，

圖 3-2 是由一個 list 結構和三個 listNode 結構組成的鏈表：

鏈表和鏈表節點的 API

函式	作用	時間復雜度
listSetDupMethod	將給定的函式設定為鏈表的節點值復制函式，	O(1)，
listGetDupMethod	回傳鏈表當前正在使用的節點值復制函式，	復制函式可以通過鏈表的dup屬性直接獲得， O(1)
listSetFreeMethod	將給定的函式設定為鏈表的節點值釋放函式，	O(1)，
listGetFree	回傳鏈表當前正在使用的節點值釋放函式，	釋放函式可以通過鏈表的free屬性直接獲得， O(1)
listSetMatchMethod	將給定的函式設定為鏈表的節點值對比函式，	O(1)
listGetMatchMethod	回傳鏈表當前正在使用的節點值對比函式，	對比函式可以通過鏈表的match 屬性直接獲得， O(1)
listLength	回傳鏈表的長度（包含了多少個節點），	鏈表長度可以通過鏈表的len屬性直接獲得， O(1) ，
listFirst	回傳鏈表的表頭節點，	表頭節點可以通過鏈表的head屬性直接獲得， O(1) ，
listLast	回傳鏈表的表尾節點，	表尾節點可以通過鏈表的tail屬性直接獲得， O(1) ，
listPrevNode	回傳給定節點的前置節點，	前置節點可以通過節點的prev屬性直接獲得， O(1) ，
listNextNode	回傳給定節點的后置節點，	后置節點可以通過節點的next屬性直接獲得， O(1) ，
listNodeValue	回傳給定節點目前正在保存的值，	節點值可以通過節點的value屬性直接獲得， O(1) ，
listCreate	創建一個不包含任何節點的新鏈表，	O(1)
listAddNodeHead	將一個包含給定值的新節點添加到給定鏈表的表頭，	O(1)
listAddNodeTail	將一個包含給定值的新節點添加到給定鏈表的表尾，	O(1)
listInsertNode	將一個包含給定值的新節點添加到給定節點的之前或者之后，	O(1)
listSearchKey	查找并回傳鏈表中包含給定值的節點，	O(N)，N為鏈表長度，
listIndex	回傳鏈表在給定索引上的節點，	O(N)，N為鏈表長度，
listDelNode	從鏈表中洗掉給定節點，	O(1)
listRotate	將鏈表的表尾節點彈出，然后將被彈出的節點插入到鏈表的表頭，成為新的表頭節點，	O(1)
listDup	復制一個給定鏈表的副本，	O(N)，N為鏈表長度，
listRelease	釋放給定鏈表，以及鏈表中的所有節點，	O(N)，N為鏈表長度，

字典

Redis 所使用的 C 語言并沒有內置這種資料結構，因此 Redis 構建了自己的字典實作，

字典，又稱符號表（symbol table）、關聯陣列（associative array）或者映射（map），是一種用于保存鍵值對（key-value pair）的抽象資料結構，
在字典中，一個鍵（key）可以和一個值（value）進行關聯（或者說將鍵映射為值），這些關聯的鍵和值就被稱為鍵值對，
字典中的每個鍵都是獨一無二的，程式可以在字典中根據鍵查找與之關聯的值，或者通過鍵來更新值，又或者根據鍵來洗掉整個鍵值對，等等，

導讀

字典被廣泛用于實作 Redis 的各種功能，其中包括資料庫和哈希鍵，
Redis 中的字典使用哈希表作為底層實作，每個字典帶有兩個哈希表，一個用于平時使用，另一個僅在進行 rehash 時使用，
當字典被用作資料庫的底層實作，或者哈希鍵的底層實作時， Redis 使用 MurmurHash2 演算法來計算鍵的哈希值，
哈希表使用鏈地址法來解決鍵沖突，被分配到同一個索引上的多個鍵值對會連接成一個單向鏈表，
在對哈希表進行擴展或者收縮操作時，程式需要將現有哈希表包含的所有鍵值對 rehash 到新哈希表里面，并且這個 rehash 程序并不是一次性地完成的，而是漸進式地完成的，

字典的實作

Redis 的字典使用哈希表作為底層實作，一個哈希表里面可以有多個哈希表節點，而每個哈希表節點就保存了字典中的一個鍵值對，

字典

Redis 中的字典由 dict.h/dict 結構表示：

 1 typedef struct dict {
 2 
 3     // 型別特定函式
 4     dictType *type;
 5 
 6     // 私有資料
 7     void *privdata;
 8 
 9     // 哈希表
10     dictht ht[2];
11 
12     // rehash 索引
13     // 當 rehash 不在進行時，值為 -1
14     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
15 
16 } dict;

type 屬性和 privdata 屬性是針對不同型別的鍵值對，為創建多型字典而設定的：
type 屬性是一個指向 dictType 結構的指標，每個 dictType 結構保存了一簇用于操作特定型別鍵值對的函式， Redis 會為用途不同的字典設定不同的型別特定函式，
而 privdata 屬性則保存了需要傳給那些型別特定函式的可選引數，
ht 屬性是一個包含兩個項的陣列，陣列中的每個項都是一個 dictht 哈希表，一般情況下，字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用，
除了 ht[1] 之外，另一個和 rehash 有關的屬性就是 rehashidx ：它記錄了 rehash 目前的進度，如果目前沒有在進行 rehash ，那么它的值為 -1 ，

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 結構定義：

 1 typedef struct dictht {
 2 
 3     // 哈希表陣列
 4     dictEntry **table;
 5 
 6     // 哈希表大小
 7     unsigned long size;
 8 
 9     // 哈希表大小掩碼，用于計算索引值
10     // 總是等于 size - 1
11     unsigned long sizemask;
12 
13     // 該哈希表已有節點的數量
14     unsigned long used;
15 
16 } dictht;
17 table 屬性是一個陣列， 陣列中的每個元素都是一個指向 dict.h/dictEntry 結構的指標， 每個 dictEntry 結構保存著一個鍵值對，

table 屬性是一個陣列，陣列中的每個元素都是一個指向 dict.h/dictEntry 結構的指標，每個 dictEntry 結構保存著一個鍵值對，
size 屬性記錄了哈希表的大小，也即是 table 陣列的大小，而 used 屬性則記錄了哈希表目前已有節點（鍵值對）的數量，
sizemask 屬性的值總是等于 size - 1 ，這個屬性和哈希值一起決定一個鍵應該被放到 table 陣列的哪個索引上面，

圖 4-1 展示了一個大小為 4 的空哈希表（沒有包含任何鍵值對），

哈希表節點

哈希表節點使用 dictEntry 結構表示，每個 dictEntry 結構都保存著一個鍵值對：

 1 typedef struct dictEntry {
 2 
 3     // 鍵
 4     void *key;
 5 
 6     // 值
 7     union {
 8         void *val;
 9         uint64_t u64;
10         int64_t s64;
11     } v;
12 
13     // 指向下個哈希表節點，形成鏈表
14     struct dictEntry *next;
15 
16 } dictEntry;

key 屬性保存著鍵值對中的鍵，
v 屬性則保存著鍵值對中的值，其中鍵值對的值可以是一個指標，或者是一個 uint64_t 整數，又或者是一個 int64_t 整數，
next 屬性是指向另一個哈希表節點的指標，這個指標可以將多個哈希值相同的鍵值對連接在一次，以此來解決鍵沖突（collision）的問題，

圖 4-3 展示了一個普通狀態下（沒有進行 rehash）的字典：

哈希演算法

當要將一個新的鍵值對添加到字典里面時，程式需要先根據鍵值對的鍵計算出哈希值和索引值，然后再根據索引值，將包含新鍵值對的哈希表節點放到哈希表陣列的指定索引上面，

Redis 計算哈希值和索引值的方法如下：

1 # 使用字典設定的哈希函式，計算鍵 key 的哈希值
2 hash = dict->type->hashFunction(key);
3 
4 # 使用哈希表的 sizemask 屬性和哈希值，計算出索引值
5 # 根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
6 index = hash & dict->ht[x].sizemask;

舉個例子，對于圖 4-4 所示的字典來說，如果我們要將一個鍵值對 k0 和 v0 添加到字典里面，那么程式會先使用陳述句：

hash = dict->type->hashFunction(k0);

計算鍵 k0 的哈希值，

假設計算得出的哈希值為 8 ，那么程式會繼續使用陳述句：

index = hash & dict->ht[0].sizemask = 8 & 3 = 0;

計算出鍵 k0 的索引值 0 ，這表示包含鍵值對 k0 和 v0 的節點應該被放置到哈希表陣列的索引 0 位置上，如圖 4-5 所示，

當字典被用作資料庫的底層實作，或者哈希鍵的底層實作時， Redis 使用 MurmurHash2 演算法來計算鍵的哈希值，

MurmurHash 演算法最初由 Austin Appleby 于 2008 年發明，這種演算法的優點在于，即使輸入的鍵是有規律的，演算法仍能給出一個很好的隨機分布性，并且演算法的計算速度也非常快，

MurmurHash 演算法目前的最新版本為 MurmurHash3 ，而 Redis 使用的是 MurmurHash2 ，關于 MurmurHash 演算法的更多資訊可以參考該演算法的主頁： http://code.google.com/p/smhasher/ ，

解決鍵沖突

哈希表節點的next 屬性是用來解決鍵沖突（collision）的問題，它指向另一個哈希表節點的指標，

當有兩個或以上數量的鍵被分配到了哈希表陣列的同一個索引上面時，我們稱這些鍵發生了沖突（collision），
Redis 的哈希表使用鏈地址法（separate chaining）來解決鍵沖突：每個哈希表節點都有一個 next 指標，多個哈希表節點可以用 next 指標構成一個單向鏈表，被分配到同一個索引上的多個節點可以用這個單向鏈表連接起來，這就解決了鍵沖突的問題，

因為 dictEntry 節點組成的鏈表沒有指向鏈表表尾的指標，所以為了速度考慮，程式總是將新節點添加到鏈表的表頭位置（復雜度為 O(1)），排在其他已有節點的前面，

rehash

隨著操作的不斷執行，哈希表保存的鍵值對會逐漸地增多或者減少，為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內，當哈希表保存的鍵值對數量太多或者太少時，程式需要對哈希表的大小進行相應的擴展或者收縮，

擴展和收縮哈希表的作業可以通過執行 rehash （重新散列）操作來完成， Redis 對字典的哈希表執行 rehash 的步驟如下：

為字典的 ht[1] 哈希表分配空間，這個哈希表的空間大小取決于要執行的操作，以及 ht[0] 當前包含的鍵值對數量（也即是 ht[0].used 屬性的值）：
如果執行的是擴展操作，那么 ht[1] 的大小為第一個大于等于 ht[0].used * 2 的 2^n （2 的 n 次方冪）；
如果執行的是收縮操作，那么 ht[1] 的大小為第一個大于等于 ht[0].used 的 2^n ，
將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面： rehash 指的是重新計算鍵的哈希值和索引值，然后將鍵值對放置到 ht[1] 哈希表的指定位置上，
當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后（ht[0] 變為空表），釋放 ht[0] ，將 ht[1] 設定為 ht[0] ，并在 ht[1] 新創建一個空白哈希表，為下一次 rehash 做準備，

舉個例子，假設程式要對含有5個鍵值對字典的 ht[0] 進行擴展操作，那么程式將執行以下步驟：

ht[0].used 當前的值為 5 ， 5 * 2 = 10 ，而第一個大于等于10的且2 的 n 次方的數是16，所以程式會將 ht[1] 哈希表的大小設定為 16 ，
將 ht[0] 包含的5個鍵值對都 rehash 到 ht[1]，
釋放 ht[0] ，并將 ht[1] 設定為 ht[0] ，然后為 ht[1] 分配一個空白哈希表，

哈希表的擴展與收縮

當哈希表的負載因子小于 0.1 時，程式自動開始對哈希表執行收縮操作，
當以下條件中的任意一個被滿足時，程式會自動開始對哈希表執行擴展操作：

服務器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的負載因子大于等于 1 ；
服務器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的負載因子大于等于 5 ；

其中哈希表的負載因子可以通過公式計算得出：

1 # 負載因子 = 哈希表已保存節點數量 / 哈希表大小
2 load_factor = ht[0].used / ht[0].size

根據 BGSAVE 命令或 BGREWRITEAOF 命令是否正在執行，服務器執行擴展操作所需的負載因子并不相同，這是因為在執行 BGSAVE 命令或 BGREWRITEAOF 命令的程序中， Redis 需要創建當前服務器行程的子行程，而大多數作業系統都采用寫時復制（copy-on-write）技術來優化子行程的使用效率，所以在子行程存在期間，服務器會提高執行擴展操作所需的負載因子，從而盡可能地避免在子行程存在期間進行哈希表擴展操作，這可以避免不必要的記憶體寫入操作，最大限度地節約記憶體，

漸進式 rehash

上一節說過，擴展或收縮哈希表需要將 ht[0] 里面的所有鍵值對 rehash 到 ht[1] 里面，但是，這個 rehash 動作并不是一次性、集中式地完成的，而是分多次、漸進式地完成的，
原因在于，如果哈希表里保存的鍵值對數量巨大，有四百萬、四千萬甚至四億個鍵值對，那么要一次性將這些鍵值對全部 rehash 到 ht[1] 的話，龐大的計算量可能會導致服務器在一段時間內停止服務，
因此，為了避免 rehash 對服務器性能造成影響，服務器不是一次性將 ht[0] 里面的所有鍵值對全部 rehash 到 ht[1] ，而是分多次、漸進式地將 ht[0] 里面的鍵值對慢慢地 rehash 到 ht[1] ，
漸進式 rehash 的好處在于它采取分而治之的方式，將 rehash 鍵值對所需的計算作業均灘到對字典的每個添加、洗掉、查找和更新操作上，從而避免了集中式 rehash 而帶來的龐大計算量，

哈希表漸進式 rehash 的詳細步驟：

為 ht[1] 分配空間，讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表，
在字典中維持一個索引計數器變數 rehashidx ，并將它的值設定為 0 ，表示 rehash 作業正式開始，
在 rehash 進行期間，每次對字典執行添加、洗掉、查找或者更新操作時，程式除了執行指定的操作以外，還會順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ，當 rehash 作業完成之后，程式將 rehashidx 屬性的值增一，
隨著字典操作的不斷執行，最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ，這時程式將 rehashidx 屬性的值設為 -1 ，表示 rehash 操作已完成，

問題：如果漸進式rehash程序中，鍵值對數量迅速增大，最終在還沒有rehash完，又需要擴容情況怎么辦？

字典 API

表 4-1 字典的主要操作 API

函式	作用	時間復雜度
dictCreate	創建一個新的字典，	O(1)
dictAdd	將給定的鍵值對添加到字典里面，	O(1)
dictReplace	將給定的鍵值對添加到字典里面，如果鍵已經存在于字典，那么用新值取代原有的值，	O(1)
dictFetchValue	回傳給定鍵的值，	O(1)
dictGetRandomKey	從字典中隨機回傳一個鍵值對，	O(1)
dictDelete	從字典中洗掉給定鍵所對應的鍵值對，	O(1)
dictRelease	釋放給定字典，以及字典中包含的所有鍵值對，	O(N)，N為字典包含的鍵值對數量，

跳躍表

導讀

跳躍表是有序集合的底層實作之一，除此之外它在 Redis 中沒有其他應用，
Redis 的跳躍表實作由 zskiplist 和 zskiplistNode 兩個結構組成，其中 zskiplist 用于保存跳躍表資訊（比如表頭節點、表尾節點、長度），而 zskiplistNode 則用于表示跳躍表節點，
每個跳躍表節點的層高都是 1 至 32 之間的亂數，
在同一個跳躍表中，多個節點可以包含相同的分值，但每個節點的成員物件必須是唯一的，
跳躍表中的節點按照分值大小進行排序，當分值相同時，節點按照成員物件的大小進行排序，

跳躍表的實作

Redis 的跳躍表由 redis.h/zskiplistNode 和 redis.h/zskiplist 兩個結構定義，其中 zskiplistNode 結構用于表示跳躍表節點，而 zskiplist 結構則用于保存跳躍表節點的相關資訊，比如節點的數量，以及指向表頭節點和表尾節點的指標，等等，

圖 5-1 展示了一個跳躍表示例，位于圖片最左邊的是 zskiplist 結構，該結構包含以下屬性：

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

位于 zskiplist 結構右方的是四個 zskiplistNode 結構，該結構包含以下屬性：

層（level）：節點中用 L1 、 L2 、 L3 等字樣標記節點的各個層， L1 代表第一層， L2 代表第二層，以此類推，每個層都帶有兩個屬性：前進指標和跨度，前進指標用于訪問位于表尾方向的其他節點，而跨度則記錄了前進指標所指向節點和當前節點的距離，在上面的圖片中，連線上帶有數字的箭頭就代表前進指標，而那個數字就是跨度，當程式從表頭向表尾進行遍歷時，訪問會沿著層的前進指標進行，
后退（backward）指標：節點中用 BW 字樣標記節點的后退指標，它指向位于當前節點的前一個節點，后退指標在程式從表尾向表頭遍歷時使用，
分值（score）：各個節點中的 1.0 、 2.0 和 3.0 是節點所保存的分值，在跳躍表中，節點按各自所保存的分值從小到大排列，
成員物件（obj）：各個節點中的 o1 、 o2 和 o3 是節點所保存的成員物件，

注意表頭節點和其他節點的構造是一樣的：表頭節點也有后退指標、分值和成員物件，不過表頭節點的這些屬性都不會被用到，所以圖中省略了這些部分，只顯示了表頭節點的各個層，

跳躍表節點 zskiplistNode

跳躍表節點的實作由 redis.h/zskiplistNode 結構定義：

 1 typedef struct zskiplistNode {
 2 
 3     // 后退指標
 4     struct zskiplistNode *backward;
 5 
 6     // 分值
 7     double score;
 8 
 9     // 成員物件
10     robj *obj;
11 
12     // 層
13     struct zskiplistLevel {
14 
15         // 前進指標
16         struct zskiplistNode *forward;
17 
18         // 跨度
19         unsigned int span;
20 
21     } level[];
22 
23 } zskiplistNode;

層

跳躍表節點的 level 陣列可以包含多個元素，每個元素都包含一個指向其他節點的指標，程式可以通過這些層來加快訪問其他節點的速度，一般來說，層的數量越多，訪問其他節點的速度就越快，
每次創建一個新跳躍表節點的時候，程式都根據冪次定律 （power law，越大的數出現的概率越小）隨機生成一個介于 1 和 32 之間的值作為 level 陣列的大小，這個大小就是層的“高度”，

圖 5-2 分別展示了三個高度為 1 層、 3 層和 5 層的節點，因為 C 語言的陣列索引總是從 0 開始的，所以節點的第一層是 level[0] ，而第二層是 level[1] ，以此類推，

前進指標

每個層都有一個指向表尾方向的前進指標（level[i].forward 屬性），用于從表頭向表尾方向訪問節點，

圖 5-3 用虛線表示出了程式從表頭向表尾方向，遍歷跳躍表中所有節點的路徑：

迭代程式首先訪問跳躍表的第一個節點（表頭），然后從第四層的前進指標移動到表中的第二個節點，
在第二個節點時，程式沿著第二層的前進指標移動到表中的第三個節點，
在第三個節點時，程式同樣沿著第二層的前進指標移動到表中的第四個節點，
當程式再次沿著第四個節點的前進指標移動時，它碰到一個 NULL ，程式知道這時已經到達了跳躍表的表尾，于是結束這次遍歷，

跨度

層的跨度（level[i].span 屬性）用于記錄兩個節點之間的距離：
- 兩個節點之間的跨度越大，它們相距得就越遠，
- 指向 NULL 的所有前進指標的跨度都為 0 ，因為它們沒有連向任何節點，
初看上去，很容易以為跨度和遍歷操作有關，但實際上并不是這樣 —— 遍歷操作只使用前進指標就可以完成了，跨度實際上是用來計算排位（rank）的：在查找某個節點的程序中，將沿途訪問過的所有層的跨度累計起來，得到的結果就是目標節點在跳躍表中的排位，

舉個例子，圖 5-4 用虛線標記了在跳躍表中查找分值為 3.0 、成員物件為 o3 的節點時，沿途經歷的層：查找的程序只經過了一個層，并且層的跨度為 3 ，所以目標節點在跳躍表中的排位為 3 ，

再舉個例子，圖 5-5 用虛線標記了在跳躍表中查找分值為 2.0 、成員物件為 o2 的節點時，沿途經歷的層：在查找節點的程序中，程式經過了兩個跨度為 1 的節點，因此可以計算出，目標節點在跳躍表中的排位為 2 ，

后退指標

節點的后退指標（backward 屬性）用于從表尾向表頭方向訪問節點：跟可以一次跳過多個節點的前進指標不同，因為每個節點只有一個后退指標，所以每次只能后退至前一個節點，

圖 5-6 用虛線展示了如果從表尾向表頭遍歷跳躍表中的所有節點：程式首先通過跳躍表的 tail 指標訪問表尾節點，然后通過后退指標訪問倒數第二個節點，之后再沿著后退指標訪問倒數第三個節點，再之后遇到指向 NULL 的后退指標，于是訪問結束，

分值和成員

節點的分值（score 屬性）是一個 double 型別的浮點數，跳躍表中的所有節點都按分值從小到大來排序，
節點的成員物件（obj 屬性）是一個指標，它指向一個字串物件，而字串物件則保存著一個 SDS 值，
在同一個跳躍表中，各個節點保存的成員物件必須是唯一的，但是多個節點保存的分值卻可以是相同的：分值相同的節點將按照成員物件在字典序中的大小來進行排序，成員物件較小的節點會排在前面（靠近表頭的方向），而成員物件較大的節點則會排在后面（靠近表尾的方向），

舉個例子，在圖 5-7 所示的跳躍表中，三個跳躍表節點都保存了相同的分值 10086.0 ，但保存成員物件 o1 的節點卻排在保存成員物件 o2 和 o3 的節點之前，而保存成員物件 o2 的節點又排在保存成員物件 o3 的節點之前，由此可見， o1 、 o2 、 o3 三個成員物件在字典中的排序為 o1 <= o2 <= o3 ，

跳躍表 zskiplist

雖然僅靠多個跳躍表節點就可以組成一個跳躍表，但通過使用一個 zskiplist 結構來持有這些節點，程式可以更方便地對整個跳躍表進行處理，比如快速訪問跳躍表的表頭節點和表尾節點，又或者快速地獲取跳躍表節點的數量（也即是跳躍表的長度）等資訊，如圖 5-9 所示，

zskiplist 結構的定義如下：

 1 typedef struct zskiplist {
 2 
 3     // 表頭節點和表尾節點
 4     struct zskiplistNode *header, *tail;
 5 
 6     // 表中節點的數量
 7     unsigned long length;
 8 
 9     // 表中層數最大的節點的層數
10     int level;
11 
12 } zskiplist;
13 header 和 tail 指標分別指向跳躍表的表頭和表尾節點， 通過這兩個指標， 程式定位表頭節點和表尾節點的復雜度為 O(1) ，

header 和 tail 指標分別指向跳躍表的表頭和表尾節點，通過這兩個指標，程式定位表頭節點和表尾節點的復雜度為 O(1) ，
length 屬性用來記錄節點的數量，程式可以在 O(1) 復雜度內回傳跳躍表的長度，
level 屬性則用于在 O(1) 復雜度內獲取跳躍表中層高最大的那個節點的層數量，注意表頭節點的層高并不計算在

整數集合

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

導讀

整數集合是集合鍵的底層實作之一，
整數集合的底層實作為陣列，這個陣列以有序、無重復的方式保存集合元素，在有需要時，程式會根據新添加元素的型別，改變這個陣列的型別，
升級操作為整數集合帶來了操作上的靈活性，并且盡可能地節約了記憶體，
整數集合只支持升級操作，不支持降級操作，

整數集合的實作

整數集合（intset）是 Redis 用于保存整數值的集合抽象資料結構，它可以保存型別為 int16_t 、 int32_t 或者 int64_t 的整數值，并且保證集合中不會出現重復元素，

每個 intset.h/intset 結構表示一個整數集合：

1 typedef struct intset {
 2 
 3     // 編碼方式
 4     uint32_t encoding;
 5 
 6     // 集合包含的元素數量
 7     uint32_t length;
 8 
 9     // 保存元素的陣列
10     int8_t contents[];
11 
12 } intset;
13 contents 陣列是整數集合的底層實作： 整數集合的每個元素都是 contents 陣列的一個陣列項（item）， 各個項在陣列中按值的大小從小到大有序地排列， 并且陣列中不包含任何重復項，

contents 陣列是整數集合的底層實作：整數集合的每個元素都是 contents 陣列的一個陣列項（item），各個項在陣列中按值的大小從小到大有序地排列，并且陣列中不包含任何重復項，
length 屬性記錄了整數集合包含的元素數量，也即是 contents 陣列的長度，

雖然 intset 結構將 contents 屬性宣告為 int8_t 型別的陣列，但實際上 contents 陣列并不保存任何 int8_t 型別的值 —— contents 陣列的真正型別取決于 encoding 屬性的值：

如果 encoding 屬性的值為 INTSET_ENC_INT16 ，那么 contents 就是一個 int16_t 型別的陣列，陣列里的每個項都是一個 int16_t 型別的整數值（最小值為 -32,768 ，最大值為 32,767 ），
如果 encoding 屬性的值為 INTSET_ENC_INT32 ，那么 contents 就是一個 int32_t 型別的陣列，陣列里的每個項都是一個 int32_t 型別的整數值（最小值為 -2,147,483,648 ，最大值為 2,147,483,647 ），
如果 encoding 屬性的值為 INTSET_ENC_INT64 ，那么 contents 就是一個 int64_t 型別的陣列，陣列里的每個項都是一個 int64_t 型別的整數值（最小值為 -9,223,372,036,854,775,808 ，最大值為 9,223,372,036,854,775,807 ），

升級

每當我們要將一個新元素添加到整數集合里面，并且新元素的型別比整數集合現有所有元素的型別都要長時，整數集合需要先進行升級（upgrade），然后才能將新元素添加到整數集合里面，

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

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

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

升級之后新元素的擺放位置

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

在新元素小于所有現有元素的情況下，新元素會被放置在底層陣列的最開頭（索引 0 ）；
在新元素大于所有現有元素的情況下，新元素會被放置在底層陣列的最末尾（索引 length-1 ），

升級的好處

整數集合的升級策略有兩個好處，一個是提升整數集合的靈活性，另一個是盡可能地節約記憶體，

提升靈活性

因為 C 語言是靜態型別語言，為了避免型別錯誤，我們通常不會將兩種不同型別的值放在同一個資料結構里面，
整數集合可以通過自動升級底層陣列來適應新元素，所以我們可以隨意地將 int16_t 、 int32_t 或者 int64_t 型別的整數添加到集合中，而不必擔心出現型別錯誤，這種做法非常靈活，

節約記憶體

要讓一個陣列可以同時保存 int16_t 、 int32_t 、 int64_t 三種型別的值，最簡單的做法就是直接使用 int64_t 型別的陣列作為整數集合的底層實作，不過這樣一來，就會出現浪費記憶體的情況，
整數集合現在的做法既可以讓集合能同時保存三種不同型別的值，又可以確保升級操作只會在有需要的時候進行，這可以盡量節省記憶體，

降級

整數集合不支持降級操作，一旦對陣列進行了升級，編碼就會一直保持升級后的狀態，
舉個例子，對于一個整數集合來說，即使我們將集合里唯一一個真正需要使用 int64_t 型別來保存的元素 4294967295 洗掉了，整數集合的編碼仍然會維持 INTSET_ENC_INT64 ，底層陣列也仍然會是 int64_t 型別的，

整數集合 API

表 6-1 列出了整數集合的操作 API ，

函式	作用	時間復雜度
intsetNew	創建一個新的整數集合，	O(1)
intsetAdd	將給定元素添加到整數集合里面，	O(N)
intsetRemove	從整數集合中移除給定元素，	O(N)
intsetFind	檢查給定值是否存在于集合，	因為底層陣列有序，查找可以通過二分查找法來進行，所以復雜度為 O(\log N) ，
intsetRandom	從整數集合中隨機回傳一個元素，	O(1)
intsetGet	取出底層陣列在給定索引上的元素，	O(1)
intsetLen	回傳整數集合包含的元素個數，	O(1)
intsetBlobLen	回傳整數集合占用的記憶體位元組數，	O(1)

壓縮串列

導讀

壓縮串列是一種為節約記憶體而開發的順序型資料結構，
壓縮串列被用作串列鍵和哈希鍵的底層實作之一，
壓縮串列可以包含多個節點，每個節點可以保存一個位元組陣列或者整數值，
添加新節點到壓縮串列，或者從壓縮串列中洗掉節點，可能會引發連鎖更新操作，但這種操作出現的幾率并不高，

壓縮串列的構成

壓縮串列是 Redis 為了節約記憶體而開發的，由一系列特殊編碼的連續記憶體塊組成的順序型（sequential）資料結構，
一個壓縮串列可以包含任意多個節點（entry），每個節點可以保存一個位元組陣列或者一個整數值，

圖 7-1 展示了壓縮串列的各個組成部分，表 7-1 則記錄了各個組成部分的型別、長度、以及用途，

表 7-1 壓縮串列各個組成部分的詳細說明

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

壓縮串列節點的構成

每個壓縮串列節點都由 previous_entry_length 、 encoding 、 content 三個部分組成，如圖 7-4 所示，

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

長度小于等于 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

節點的 previous_entry_length 屬性以位元組為單位，記錄了壓縮串列中前一個節點的長度，
previous_entry_length 屬性的長度可以是 1 位元組或者 5 位元組：
如果前一節點的長度小于 254 位元組，那么 previous_entry_length 屬性的長度為 1 位元組：前一節點的長度就保存在這一個位元組里面，
如果前一節點的長度大于等于 254 位元組，那么 previous_entry_length 屬性的長度為 5 位元組：其中屬性的第一位元組會被設定為 0xFE （十進制值 254），而之后的四個位元組則用于保存前一節點的長度，
因為節點的 previous_entry_length 屬性記錄了前一個節點的長度，所以程式可以通過指標運算，根據當前節點的起始地址來計算出前一個節點的起始地址，

圖 7-5 展示了一個包含一位元組長 previous_entry_length 屬性的壓縮串列節點，屬性的值為 0x05 ，表示前一節點的長度為 5 位元組，

圖 7-6 展示了一個包含五位元組長 previous_entry_length 屬性的壓縮節點，屬性的值為 0xFE00002766 ，其中值的最高位位元組 0xFE 表示這是一個五位元組長的 previous_entry_length 屬性，而之后的四位元組 0x00002766 （十進制值 10086 ）才是前一節點的實際長度，

encoding

節點的 encoding 屬性記錄了節點的 content 屬性所保存資料的型別以及長度：

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

表 7-2 記錄了所有可用的位元組陣列編碼，而表 7-3 則記錄了所有可用的整數編碼，表格中的下劃線 _ 表示留空，而 b 、 x 等變數則代表實際的二進制資料，為了方便閱讀，多個位元組之間用空格隔開，

編碼	編碼長度	content 屬性保存的值
00bbbbbb	1 位元組	長度小于等于 63 位元組的位元組陣列，
01bbbbbb xxxxxxxx	2 位元組	長度小于等于 16383 位元組的位元組陣列，
10______ aaaaaaaa bbbbbbbb cccccccc dddddddd	5 位元組	長度小于等于 4294967295 的位元組陣列，

表 7-3 整數編碼

編碼	編碼長度	content 屬性保存的值
11000000	1 位元組	int16_t 型別的整數，
11010000	1 位元組	int32_t 型別的整數，
11100000	1 位元組	int64_t 型別的整數，
11110000	1 位元組	24 位有符號整數，
11111110	1 位元組	8 位有符號整數，
1111xxxx	1 位元組	使用這一編碼的節點沒有相應的 content 屬性，因為編碼本身的 xxxx 四個位已經保存了一個介于 0 和 12 之間的值，所以它無須 content 屬性，

content

節點的 content 屬性負責保存節點的值，節點值可以是一個位元組陣列或者整數，值的型別和長度由節點的 encoding 屬性決定，
圖 7-9 展示了一個保存位元組陣列的節點示例：
編碼的最高兩位 00 表示節點保存的是一個位元組陣列；
編碼的后六位 001011 記錄了位元組陣列的長度 11 ；
content 屬性保存著節點的值 "hello world" ，

圖 7-10 展示了一個保存整數值的節點示例：
編碼 11000000 表示節點保存的是一個 int16_t 型別的整數值；
content 屬性保存著節點的值 10086 ，

連鎖更新

添加新節點可能會引發連鎖更新之外，
洗掉節點也可能會引發連鎖更新，
因為連鎖更新在最壞情況下需要對壓縮串列執行 N 次空間重分配操作，而每次空間重分配的最壞復雜度為 O(N) ，所以連鎖更新的最壞復雜度為 O(N^2) ，
要注意的是，盡管連鎖更新的復雜度較高，但它真正造成性能問題的幾率是很低的：
首先，壓縮串列里要恰好有多個連續的、長度介于 250 位元組至 253 位元組之間的節點，連鎖更新才有可能被引發，在實際中，這種情況并不多見；
其次，即使出現連鎖更新，但只要被更新的節點數量不多，就不會對性能造成任何影響：比如說，對三五個節點進行連鎖更新是絕對不會影響性能的；

因為以上原因， ziplistPush 等命令的平均復雜度僅為 O(N) ，在實際中，我們可以放心地使用這些函式，而不必擔心連鎖更新會影響壓縮串列的性能，

壓縮串列 API

表 7-4 列出了所有用于操作壓縮串列的 API ，

函式	作用	演算法復雜度
ziplistNew	創建一個新的壓縮串列，	O(1)
ziplistPush	創建一個包含給定值的新節點，并將這個新節點添加到壓縮串列的表頭或者表尾，	平均 O(N) ，最壞 O(N^2) ，
ziplistInsert	將包含給定值的新節點插入到給定節點之后，	平均 O(N) ，最壞 O(N^2) ，
ziplistIndex	回傳壓縮串列給定索引上的節點，	O(N)
ziplistFind	在壓縮串列中查找并回傳包含了給定值的節點，	因為節點的值可能是一個位元組陣列，所以檢查節點值和給定值是否相同的復雜度為 O(N) ，而查找整個串列的復雜度則為 O(N^2) ，
ziplistNext	回傳給定節點的下一個節點，	O(1)
ziplistPrev	回傳給定節點的前一個節點，	O(1)
ziplistGet	獲取給定節點所保存的值，	O(1)
ziplistDelete	從壓縮串列中洗掉給定的節點，	平均 O(N) ，最壞 O(N^2) ，
ziplistDeleteRange	洗掉壓縮串列在給定索引上的連續多個節點，	平均 O(N) ，最壞 O(N^2) ，
ziplistBlobLen	回傳壓縮串列目前占用的記憶體位元組數，	O(1)
ziplistLen	回傳壓縮串列目前包含的節點數量，	節點數量小于 65535 時 O(1) ，大于 65535 時 O(N) ，

因為 ziplistPush 、 ziplistInsert 、 ziplistDelete 和 ziplistDeleteRange 四個函式都有可能會引發連鎖更新，所以它們的最壞復雜度都是 O(N^2) ，

物件

在前面的數個章節里，我們陸續介紹了 Redis 用到的所有主要資料結構，比如簡單動態字串（SDS）、雙端鏈表、字典、壓縮串列、整數集合，等等，

Redis 并沒有直接使用這些資料結構來實作鍵值對資料庫，而是基于這些資料結構創建了一個物件系統，這個系統包含字串物件、串列物件、哈希物件、集合物件和有序集合物件這五種型別的物件，每種物件都用到了至少一種我們前面所介紹的資料結構，
通過這五種不同型別的物件，（1）Redis 可以在執行命令之前，根據物件的型別來判斷一個物件是否可以執行給定的命令，（2）可以針對不同的使用場景，為物件設定多種不同的資料結構實作，從而優化物件在不同場景下的使用效率，
Redis 的物件系統還實作了基于參考計數技術的記憶體回識訓制：當程式不再使用某個物件的時候，這個物件所占用的記憶體就會被自動釋放；另外， Redis 還通過參考計數技術實作了物件共享機制，這一機制可以在適當的條件下，通過讓多個資料庫鍵共享同一個物件來節約記憶體，
最后， Redis 的物件帶有訪問時間記錄資訊，該資訊可以用于計算資料庫鍵的空轉時長，在服務器啟用了 maxmemory 功能的情況下，空轉時長較大的那些鍵可能會優先被服務器洗掉，

導讀

Redis 資料庫中的每個鍵值對的鍵和值都是一個物件，
Redis 共有字串、串列、哈希、集合、有序集合五種型別的物件，每種型別的物件至少都有兩種或以上的編碼方式，不同的編碼可以在不同的使用場景上優化物件的使用效率，
服務器在執行某些命令之前，會先檢查給定鍵的型別能否執行指定的命令，而檢查一個鍵的型別就是檢查鍵的值物件的型別，
Redis 的物件系統帶有參考計數實作的記憶體回識訓制，當一個物件不再被使用時，該物件所占用的記憶體就會被自動釋放，
Redis 會共享值為 0 到 9999 的字串物件，
物件會記錄自己的最后一次被訪問的時間，這個時間可以用于計算物件的空轉時間，

物件的型別與編碼

Redis 使用物件來表示資料庫中的鍵和值，每次當我們在 Redis 的資料庫中新創建一個鍵值對時，我們至少會創建兩個物件，一個物件用作鍵值對的鍵（鍵物件），另一個物件用作鍵值對的值（值物件），
Redis 中的每個物件都由一個 redisObject 結構表示，該結構中和保存資料有關的三個屬性分別是 type 屬性、 encoding 屬性和 ptr 屬性：

 1 typedef struct redisObject {
 2 
 3     // 型別
 4     unsigned type:4;
 5 
 6     // 編碼
 7     unsigned encoding:4;
 8 
 9     // 指向底層實作資料結構的指標
10     void *ptr;
11 
12     // ...
13 
14 } robj;

舉個例子，以下 SET 命令在資料庫中創建了一個新的鍵值對，其中鍵值對的鍵是一個包含了字串值 "msg" 的物件，而鍵值對的值則是一個包含了字串值 "hello world" 的物件：

1 redis> SET msg "hello world"
2 OK

型別

物件的 type 屬性記錄了物件的型別，這個屬性的值可以是以下常量的其中一個，

表 8-1 物件的型別

型別常量	物件的名稱
REDIS_STRING	字串物件
REDIS_LIST	串列物件
REDIS_HASH	哈希物件
REDIS_SET	集合物件
REDIS_ZSET	有序集合物件

對于 Redis 資料庫保存的鍵值對來說，鍵總是一個字串物件，而值則可以是字串物件、串列物件、哈希物件、集合物件或者有序集合物件的其中一種，因此：
當我們稱呼一個資料庫鍵為“字串鍵”時，我們指的是“這個資料庫鍵所對應的值為字串物件”；
當我們稱呼一個鍵為“串列鍵”時，我們指的是“這個資料庫鍵所對應的值為串列物件”，諸如此類，
TYPE 命令的實作方式也與此類似，當我們對一個資料庫鍵執行 TYPE 命令時，命令回傳的結果為資料庫鍵對應的值物件的型別，而不是鍵物件的型別：

1 # 鍵為字串物件，值為串列物件
2 redis> RPUSH numbers 1 3 5
3 (integer) 6
4 
5 redis> TYPE numbers
6 list

表 8-2 列出了 TYPE 命令在面對不同型別的值物件時所產生的輸出，

物件	物件 type 屬性的值	TYPE 命令的輸出
字串物件	REDIS_STRING	"string"
串列物件	REDIS_LIST	"list"
哈希物件	REDIS_HASH	"hash"
集合物件	REDIS_SET	"set"
有序集合物件	REDIS_ZSET	"zset"

編碼和底層實作

物件的 ptr 指標指向物件的底層實作資料結構，而這些資料結構由物件的 encoding 屬性決定，

encoding 屬性記錄了物件所使用的編碼，也即是說這個物件使用了什么資料結構作為物件的底層實作，這個屬性的值可以是表 8-3 列出的常量的其中一個，

編碼常量	編碼所對應的底層資料結構	OBJECT ENCODING 命令輸出
REDIS_ENCODING_INT	long 型別的整數	"int"
REDIS_ENCODING_EMBSTR	embstr 編碼的簡單動態字串	"embstr"
REDIS_ENCODING_RAW	簡單動態字串	"raw"
REDIS_ENCODING_HT	字典	"hashtable"
REDIS_ENCODING_LINKEDLIST	雙端鏈表	"linkedlist"
REDIS_ENCODING_ZIPLIST	壓縮串列	"ziplist"
REDIS_ENCODING_INTSET	整數集合	"intset"
REDIS_ENCODING_SKIPLIST	跳躍表和字典	"skiplist"

其中，每種type型別的物件都至少使用了兩種不同的編碼，表 8-4 不同型別和編碼的物件

型別常量	編碼	物件
REDIS_STRING	REDIS_ENCODING_INT	使用整數值實作的字串物件，
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用 embstr 編碼的簡單動態字串實作的字串物件，
REDIS_STRING	REDIS_ENCODING_RAW	使用簡單動態字串實作的字串物件，
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用壓縮串列實作的串列物件，
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用雙端鏈表實作的串列物件，
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用壓縮串列實作的哈希物件，
REDIS_HASH	REDIS_ENCODING_HT	使用字典實作的哈希物件，
REDIS_SET	REDIS_ENCODING_INTSET	使用整數集合實作的集合物件，
REDIS_SET	REDIS_ENCODING_HT	使用字典實作的集合物件，
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用壓縮串列實作的有序集合物件，
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳躍表和字典實作的有序集合物件，

使用 OBJECT ENCODING 命令可以查看一個資料庫鍵的值物件的編碼：

 1 redis> SET msg "hello wrold"
 2 OK
 3 
 4 redis> OBJECT ENCODING msg
 5 "embstr"
 6 
 7 redis> SET story "long long long long long long ago ..."
 8 OK
 9 
10 redis> OBJECT ENCODING story
11 "raw"
12 
13 redis> SADD numbers 1 3 5
14 (integer) 3
15 
16 redis> OBJECT ENCODING numbers
17 "intset"
18 
19 redis> SADD numbers "seven"
20 (integer) 1
21 
22 redis> OBJECT ENCODING numbers
23 "hashtable"

通過 encoding 屬性來設定物件所使用的編碼，而不是為特定型別的物件關聯一種固定的編碼，極大地提升了 Redis 的靈活性和效率，因為 Redis 可以根據不同的使用場景來為一個物件設定不同的編碼，從而優化物件在某一場景下的效率，

舉個例子，在串列物件包含的元素比較少時， Redis 使用壓縮串列作為串列物件的底層實作：

因為壓縮串列比雙端鏈表更節約記憶體，并且在元素數量較少時，在記憶體中以連續塊方式保存的壓縮串列比起雙端鏈表可以更快被載入到快取中；
隨著串列物件包含的元素越來越多，使用壓縮串列來保存元素的優勢逐漸消失時，物件就會將底層實作從壓縮串列轉向功能更強、也更適合保存大量元素的雙端鏈表上面；

其他型別的物件也會通過使用多種不同的編碼來進行類似的優化，

在接下來的內容中，我們將分別介紹 Redis 中的五種不同型別的物件，說明這些物件底層所使用的編碼方式，列出物件從一種編碼轉換成另一種編碼所需的條件，以及同一個命令在多種不同編碼上的實作方法，

字串物件

字串物件的編碼可以是 int 、 raw 或者 embstr ，
如果一個字串物件保存的是整數值，并且這個整數值可以用 long 型別來表示，那么字串物件會將整數值保存在字串物件結構的 ptr 屬性里面（將 void* 轉換成 long ），并將字串物件的編碼設定為 int ，

舉個例子，如果我們執行以下 SET 命令，那么服務器將創建一個如圖 8-1 所示的 int 編碼的字串物件作為 number 鍵的值：

1 redis> SET number 10086
2 OK
3 
4 redis> OBJECT ENCODING number
5 "int"

如果字串物件保存的是一個字串值，并且這個字串值的長度大于 39 位元組，那么字串物件將使用一個簡單動態字串（SDS）來保存這個字串值，并將物件的編碼設定為 raw ，

舉個例子，如果我們執行以下命令，那么服務器將創建一個如圖 8-2 所示的 raw 編碼的字串物件作為 story 鍵的值：

1 redis> SET story "Long, long, long ago there lived a king ..."
2 OK
3 
4 redis> STRLEN story
5 (integer) 43
6 
7 redis> OBJECT ENCODING story
8 "raw"

如果字串物件保存的是一個字串值，并且這個字串值的長度小于等于 39 位元組，那么字串物件將使用 embstr 編碼的方式來保存這個字串值，

embstr 編碼是專門用于保存短字串的一種優化編碼方式，這種編碼和 raw 編碼一樣，都使用 redisObject 結構和 sdshdr 結構來表示字串物件，但 raw 編碼會呼叫兩次記憶體分配函式來分別創建 redisObject 結構和 sdshdr 結構，而 embstr 編碼則通過呼叫一次記憶體分配函式來分配一塊連續的空間，空間中依次包含 redisObject 和 sdshdr 兩個結構，如圖 8-3 所示，

embstr 編碼的字串物件在執行命令時，產生的效果和 raw 編碼的字串物件執行命令時產生的效果是相同的，但使用 embstr 編碼的字串物件來保存短字串值有以下好處：

embstr 編碼將創建字串物件所需的記憶體分配次數從 raw 編碼的兩次降低為一次，
釋放 embstr 編碼的字串物件只需要呼叫一次記憶體釋放函式，而釋放 raw 編碼的字串物件需要呼叫兩次記憶體釋放函式，
因為 embstr 編碼的字串物件的所有資料都保存在一塊連續的記憶體里面，所以這種編碼的字串物件比起 raw 編碼的字串物件能夠更好地利用快取帶來的優勢，

作為例子，以下命令創建了一個 embstr 編碼的字串物件作為 msg 鍵的值，值物件的樣子如圖 8-4 所示：

1 redis> SET msg "hello"
2 OK
3 
4 redis> OBJECT ENCODING msg
5 "embstr"

最后要說的是，可以用 long double 型別表示的浮點數在 Redis 中也是作為字串值來保存的：如果我們要保存一個浮點數到字串物件里面，那么程式會先將這個浮點數轉換成字串值，然后再保存起轉換所得的字串值，在有需要的時候，程式會將保存在字串物件里面的字串值轉換回浮點數值，執行某些操作，然后再將執行操作所得的浮點數值轉換回字串值，并繼續保存在字串物件里面，

表 8-6 字串物件保存各型別值的編碼方式

值	編碼
可以用 long 型別保存的整數，	int
可以用 long double 型別保存的浮點數，	embstr 或者 raw
字串值，或者因為長度太大而沒辦法用 long 型別表示的整數，又或者因為長度太大而沒辦法用 long double 型別表示的浮點數，	embstr 或者 raw

編碼的轉換

int 編碼的字串物件和 embstr 編碼的字串物件在條件滿足的情況下，會被轉換為 raw 編碼的字串物件，
對于 int 編碼的字串物件來說，如果我們向物件執行了一些命令，使得這個物件保存的不再是整數值，而是一個字串值，那么字串物件的編碼將從 int 變為 raw ，比如APPEND 命令
另外，因為 Redis 沒有為 embstr 編碼的字串物件撰寫任何相應的修改程式（只有 int 編碼的字串物件和 raw 編碼的字串物件有這些程式），所以 embstr 編碼的字串物件實際上是只讀的：當我們對 embstr 編碼的字串物件執行任何修改命令時，程式會先將物件的編碼從 embstr 轉換成 raw ，然后再執行修改命令；因為這個原因， embstr 編碼的字串物件在執行修改命令之后，總會變成一個 raw 編碼的字串物件，

字串命令的實作

因為字串鍵的值為字串物件，所以用于字串鍵的所有命令都是針對字串物件來構建的，表 8-7 列舉了其中一部分字串命令，以及這些命令在不同編碼的字串物件下的實作方法，

命令	int 編碼的實作方法	embstr 編碼的實作方法	raw 編碼的實作方法
SET	使用 int 編碼保存值，	使用 embstr 編碼保存值，	使用 raw 編碼保存值，
GET	拷貝物件所保存的整數值，將這個拷貝轉換成字串值，然后向客戶端回傳這個字串值，	直接向客戶端回傳字串值，	直接向客戶端回傳字串值，
APPEND	將物件轉換成 raw 編碼，然后按 raw 編碼的方式執行此操作，	將物件轉換成 raw 編碼，然后按 raw 編碼的方式執行此操作，	呼叫 sdscatlen 函式，將給定字串追加到現有字串的末尾，
INCRBYFLOAT	取出整數值并將其轉換成 long double 型別的浮點數，對這個浮點數進行加法計算，然后將得出的浮點數結果保存起來，	取出字串值并嘗試將其轉換成 long double 型別的浮點數，對這個浮點數進行加法計算，然后將得出的浮點數結果保存起來，如果字串值不能被轉換成浮點數，那么向客戶端回傳一個錯誤，	取出字串值并嘗試將其轉換成 long double 型別的浮點數，對這個浮點數進行加法計算，然后將得出的浮點數結果保存起來，如果字串值不能被轉換成浮點數，那么向客戶端回傳一個錯誤，
INCRBY	對整數值進行加法計算，得出的計算結果會作為整數被保存起來，	embstr 編碼不能執行此命令，向客戶端回傳一個錯誤，	raw 編碼不能執行此命令，向客戶端回傳一個錯誤，
DECRBY	對整數值進行減法計算，得出的計算結果會作為整數被保存起來，	embstr 編碼不能執行此命令，向客戶端回傳一個錯誤，	raw 編碼不能執行此命令，向客戶端回傳一個錯誤，
STRLEN	拷貝物件所保存的整數值，將這個拷貝轉換成字串值，計算并回傳這個字串值的長度，	呼叫 sdslen 函式，回傳字串的長度，	呼叫 sdslen 函式，回傳字串的長度，
SETRANGE	將物件轉換成 raw 編碼，然后按 raw 編碼的方式執行此命令，	將物件轉換成 raw 編碼，然后按 raw 編碼的方式執行此命令，	將字串特定索引上的值設定為給定的字符，
GETRANGE	拷貝物件所保存的整數值，將這個拷貝轉換成字串值，然后取出并回傳字串指定索引上的字符，	直接取出并回傳字串指定索引上的字符，

串列物件

串列物件的編碼可以是 ziplist 或者 linkedlist ，
ziplist 編碼的串列物件使用壓縮串列作為底層實作，每個壓縮串列節點（entry）保存了一個串列元素，
另一方面， linkedlist 編碼的串列物件使用雙端鏈表作為底層實作，每個雙端鏈表節點（node）都保存了一個字串物件，而每個字串物件都保存了一個串列元素，

舉個例子，如果我們執行以下 RPUSH 命令，那么服務器將創建一個串列物件作為 numbers 鍵的值：

1 redis> RPUSH numbers 1 "three" 5
2 (integer) 3

注意， linkedlist 編碼的串列物件在底層的雙端鏈表結構中包含了多個字串物件，這種嵌套字串物件的行為在稍后介紹的哈希物件、集合物件和有序集合物件中都會出現，字串物件是 Redis 五種型別的物件中唯一一種會被其他四種型別物件嵌套的物件，

注意

為了簡化字串物件的表示，我們在圖 8-6 使用了一個帶有 StringObject 字樣的格子來表示一個字串物件，而 StringObject 字樣下面的是字串物件所保存的值，

比如說，圖 8-7 代表的就是一個包含了字串值 "three" 的字串物件，它是 8-8 的簡化表示，

本書接下來的內容將繼續沿用這一簡化表示，

編碼轉換

當串列物件可以同時滿足以下兩個條件時，串列物件使用 ziplist 編碼：

串列物件保存的所有字串元素的長度都小于 64 位元組；
串列物件保存的元素數量小于 512 個；

不能滿足這兩個條件的串列物件需要使用 linkedlist 編碼，

對于使用 ziplist 編碼的串列物件來說，當使用 ziplist 編碼所需的兩個條件的任意一個不能被滿足時，物件的編碼轉換操作就會被執行：原本保存在壓縮串列里的所有串列元素都會被轉移并保存到雙端鏈表里面，物件的編碼也會從 ziplist 變為 linkedlist ，

注意

以上兩個條件的上限值是可以修改的，具體請看組態檔中關于 list-max-ziplist-value 選項和 list-max-ziplist-entries 選項的說明，

串列命令的實作

因為串列鍵的值為串列物件，所以用于串列鍵的所有命令都是針對串列物件來構建的，

表 8-8 列出了其中一部分串列鍵命令，以及這些命令在不同編碼的串列物件下的實作方法，

命令	ziplist 編碼的實作方法	linkedlist 編碼的實作方法
LPUSH	呼叫 ziplistPush 函式，將新元素推入到壓縮串列的表頭，	呼叫 listAddNodeHead 函式，將新元素推入到雙端鏈表的表頭，
RPUSH	呼叫 ziplistPush 函式，將新元素推入到壓縮串列的表尾，	呼叫 listAddNodeTail 函式，將新元素推入到雙端鏈表的表尾，
LPOP	呼叫 ziplistIndex 函式定位壓縮串列的表頭節點，在向用戶回傳節點所保存的元素之后，呼叫 ziplistDelete 函式洗掉表頭節點，	呼叫 listFirst 函式定位雙端鏈表的表頭節點，在向用戶回傳節點所保存的元素之后，呼叫 listDelNode 函式洗掉表頭節點，
RPOP	呼叫 ziplistIndex 函式定位壓縮串列的表尾節點，在向用戶回傳節點所保存的元素之后，呼叫 ziplistDelete 函式洗掉表尾節點，	呼叫 listLast 函式定位雙端鏈表的表尾節點，在向用戶回傳節點所保存的元素之后，呼叫 listDelNode 函式洗掉表尾節點，
LINDEX	呼叫 ziplistIndex 函式定位壓縮串列中的指定節點，然后回傳節點所保存的元素，	呼叫 listIndex 函式定位雙端鏈表中的指定節點，然后回傳節點所保存的元素，
LLEN	呼叫 ziplistLen 函式回傳壓縮串列的長度，	呼叫 listLength 函式回傳雙端鏈表的長度，
LINSERT	插入新節點到壓縮串列的表頭或者表尾時，使用 ziplistPush 函式；插入新節點到壓縮串列的其他位置時，使用 ziplistInsert 函式，	呼叫 listInsertNode 函式，將新節點插入到雙端鏈表的指定位置，
LREM	遍歷壓縮串列節點，并呼叫 ziplistDelete 函式洗掉包含了給定元素的節點，	遍歷雙端鏈表節點，并呼叫 listDelNode 函式洗掉包含了給定元素的節點，
LTRIM	呼叫 ziplistDeleteRange 函式，洗掉壓縮串列中所有不在指定索引范圍內的節點，	遍歷雙端鏈表節點，并呼叫 listDelNode 函式洗掉鏈表中所有不在指定索引范圍內的節點，
LSET	呼叫 ziplistDelete 函式，先洗掉壓縮串列指定索引上的現有節點，然后呼叫 ziplistInsert 函式，將一個包含給定元素的新節點插入到相同索引上面，	呼叫 listIndex 函式，定位到雙端鏈表指定索引上的節點，然后通過賦值操作更新節點的值，

哈希物件

哈希物件的編碼可以是 ziplist 或者 hashtable ，
ziplist 編碼的哈希物件使用壓縮串列作為底層實作，每當有新的鍵值對要加入到哈希物件時，程式會先將保存了鍵的壓縮串列節點推入到壓縮串列表尾，然后再將保存了值的壓縮串列節點推入到壓縮串列表尾，因此：
- 保存了同一鍵值對的兩個節點總是緊挨在一起，保存鍵的節點在前，保存值的節點在后；
- 先添加到哈希物件中的鍵值對會被放在壓縮串列的表頭方向，而后來添加到哈希物件中的鍵值對會被放在壓縮串列的表尾方向，
另一方面， hashtable 編碼的哈希物件使用字典作為底層實作，哈希物件中的每個鍵值對都使用一個字典鍵值對來保存：
- 字典的每個鍵都是一個字串物件，物件中保存了鍵值對的鍵；
- 字典的每個值都是一個字串物件，物件中保存了鍵值對的值，

舉個例子，如果我們執行以下 HSET 命令，那么服務器將創建一個串列物件作為 profile 鍵的值：

1 redis> HSET profile name "Tom"
2 (integer) 1
3 
4 redis> HSET profile age 25
5 (integer) 1
6 
7 redis> HSET profile career "Programmer"
8 (integer) 1

編碼轉換

當哈希物件可以同時滿足以下兩個條件時，哈希物件使用 ziplist 編碼：

哈希物件保存的所有鍵值對的鍵和值的字串長度都小于 64 位元組；
哈希物件保存的鍵值對數量小于 512 個；

不能滿足這兩個條件的哈希物件需要使用 hashtable 編碼，

對于使用 ziplist 編碼的串列物件來說，當使用 ziplist 編碼所需的兩個條件的任意一個不能被滿足時，物件的編碼轉換操作就會被執行：原本保存在壓縮串列里的所有鍵值對都會被轉移并保存到字典里面，物件的編碼也會從 ziplist 變為 hashtable ，

注意

這兩個條件的上限值是可以修改的，具體請看組態檔中關于 hash-max-ziplist-value 選項和 hash-max-ziplist-entries 選項的說明，

哈希命令的實作

因為哈希鍵的值為哈希物件，所以用于哈希鍵的所有命令都是針對哈希物件來構建的，表 8-9 列出了其中一部分哈希鍵命令，以及這些命令在不同編碼的哈希物件下的實作方法，

命令	ziplist 編碼實作方法	hashtable 編碼的實作方法
HSET	首先呼叫 ziplistPush 函式，將鍵推入到壓縮串列的表尾，然后再次呼叫 ziplistPush 函式，將值推入到壓縮串列的表尾，	呼叫 dictAdd 函式，將新節點添加到字典里面，
HGET	首先呼叫 ziplistFind 函式，在壓縮串列中查找指定鍵所對應的節點，然后呼叫 ziplistNext 函式，將指標移動到鍵節點旁邊的值節點，最后回傳值節點，	呼叫 dictFind 函式，在字典中查找給定鍵，然后呼叫 dictGetVal 函式，回傳該鍵所對應的值，
HEXISTS	呼叫 ziplistFind 函式，在壓縮串列中查找指定鍵所對應的節點，如果找到的話說明鍵值對存在，沒找到的話就說明鍵值對不存在，	呼叫 dictFind 函式，在字典中查找給定鍵，如果找到的話說明鍵值對存在，沒找到的話就說明鍵值對不存在，
HDEL	呼叫 ziplistFind 函式，在壓縮串列中查找指定鍵所對應的節點，然后將相應的鍵節點、以及鍵節點旁邊的值節點都洗掉掉，	呼叫 dictDelete 函式，將指定鍵所對應的鍵值對從字典中洗掉掉，
HLEN	呼叫 ziplistLen 函式，取得壓縮串列包含節點的總數量，將這個數量除以 2 ，得出的結果就是壓縮串列保存的鍵值對的數量，	呼叫 dictSize 函式，回傳字典包含的鍵值對數量，這個數量就是哈希物件包含的鍵值對數量，
HGETALL	遍歷整個壓縮串列，用 ziplistGet 函式回傳所有鍵和值（都是節點），	遍歷整個字典，用 dictGetKey 函式回傳字典的鍵，用 dictGetVal 函式回傳字典的值，

集合物件

集合物件的編碼可以是 intset 或者 hashtable ，
intset 編碼的集合物件使用整數集合作為底層實作，集合物件包含的所有元素都被保存在整數集合里面，
另一方面， hashtable 編碼的集合物件使用字典作為底層實作，字典的每個鍵都是一個字串物件，每個字串物件包含了一個集合元素，而字典的值則全部被設定為 NULL ，

舉個例子，以下代碼將創建一個如圖 8-12 所示的 intset 編碼集合物件：

1 redis> SADD numbers 1 3 5
2 (integer) 3

以下代碼將創建一個如圖 8-13 所示的 hashtable 編碼集合物件：

1 redis> SADD fruits "apple" "banana" "cherry"
2 (integer) 3

編碼的轉換

當集合物件可以同時滿足以下兩個條件時，物件使用 intset 編碼：

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

不能滿足這兩個條件的集合物件需要使用 hashtable 編碼，

對于使用 intset 編碼的集合物件來說，當使用 intset 編碼所需的兩個條件的任意一個不能被滿足時，物件的編碼轉換操作就會被執行：原本保存在整數集合中的所有元素都會被轉移并保存到字典里面，并且物件的編碼也會從 intset 變為 hashtable ，

注意

第二個條件的上限值是可以修改的，具體請看組態檔中關于 set-max-intset-entries 選項的說明，

集合命令的實作

因為集合鍵的值為集合物件，所以用于集合鍵的所有命令都是針對集合物件來構建的，表 8-10 列出了其中一部分集合鍵命令，以及這些命令在不同編碼的集合物件下的實作方法，

表 8-10 集合命令的實作方法

命令	intset 編碼的實作方法	hashtable 編碼的實作方法
SADD	呼叫 intsetAdd 函式，將所有新元素添加到整數集合里面，	呼叫 dictAdd ，以新元素為鍵， NULL 為值，將鍵值對添加到字典里面，
SCARD	呼叫 intsetLen 函式，回傳整數集合所包含的元素數量，這個數量就是集合物件所包含的元素數量，	呼叫 dictSize 函式，回傳字典所包含的鍵值對數量，這個數量就是集合物件所包含的元素數量，
SISMEMBER	呼叫 intsetFind 函式，在整數集合中查找給定的元素，如果找到了說明元素存在于集合，沒找到則說明元素不存在于集合，	呼叫 dictFind 函式，在字典的鍵中查找給定的元素，如果找到了說明元素存在于集合，沒找到則說明元素不存在于集合，
SMEMBERS	遍歷整個整數集合，使用 intsetGet 函式回傳集合元素，	遍歷整個字典，使用 dictGetKey 函式回傳字典的鍵作為集合元素，
SRANDMEMBER	呼叫 intsetRandom 函式，從整數集合中隨機回傳一個元素，	呼叫 dictGetRandomKey 函式，從字典中隨機回傳一個字典鍵，
SPOP	呼叫 intsetRandom 函式，從整數集合中隨機取出一個元素，在將這個隨機元素回傳給客戶端之后，呼叫 intsetRemove 函式，將隨機元素從整數集合中洗掉掉，	呼叫 dictGetRandomKey 函式，從字典中隨機取出一個字典鍵，在將這個隨機字典鍵的值回傳給客戶端之后，呼叫 dictDelete 函式，從字典中洗掉隨機字典鍵所對應的鍵值對，
SREM	呼叫 intsetRemove 函式，從整數集合中洗掉所有給定的元素，	呼叫 dictDelete 函式，從字典中洗掉所有鍵為給定元素的鍵值對，

有序集合物件

有序集合的編碼可以是 ziplist 或者 skiplist ，
ziplist 編碼的有序集合物件使用壓縮串列作為底層實作，每個集合元素使用兩個緊挨在一起的壓縮串列節點來保存，第一個節點保存元素的成員（member），而第二個元素則保存元素的分值（score），
壓縮串列內的集合元素按分值從小到大進行排序，分值較小的元素被放置在靠近表頭的方向，而分值較大的元素則被放置在靠近表尾的方向，
skiplist 編碼的有序集合物件使用 zset 結構作為底層實作，一個 zset 結構同時包含一個字典和一個跳躍表：

1 typedef struct zset {
2     
3     zskiplist *zsl;
4     dict *dict;
5     
6 } zset;

- zset 結構中的 zsl 跳躍表按分值從小到大保存了所有集合元素，每個跳躍表節點都保存了一個集合元素：跳躍表節點的 object 屬性保存了元素的成員，而跳躍表節點的 score 屬性則保存了元素的分值，通過這個跳躍表，程式可以對有序集合進行范圍型操作，比如 ZRANK 、 ZRANGE 等命令就是基于跳躍表 API 來實作的，
- zset 結構中的 dict 字典為有序集合創建了一個從成員到分值的映射，字典中的每個鍵值對都保存了一個集合元素：字典的鍵保存了元素的成員，而字典的值則保存了元素的分值，通過這個字典，程式可以用 O(1) 復雜度查找給定成員的分值， ZSCORE 命令就是根據這一特性實作的，而很多其他有序集合命令都在實作的內部用到了這一特性，
- 值得一提的是，雖然 zset 結構同時使用跳躍表和字典來保存有序集合元素，但這兩種資料結構都會通過指標來共享相同元素的成員和分值，所以同時使用跳躍表和字典來保存集合元素不會產生任何重復成員或者分值，也不會因此而浪費額外的記憶體，
有序集合每個元素的成員都是一個字串物件，而每個元素的分值都是一個 double 型別的浮點數，

舉個例子，如果我們執行以下 ZADD 命令，那么服務器將創建一個有序集合物件作為 price 鍵的值：

1 redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
2 (integer) 3

如果 price 鍵的值物件使用的是 ziplist 編碼，那么這個值物件將會是圖 8-14 所示的樣子，而物件所使用的壓縮串列則會是 8-15 所示的樣子，

如果前面 price 鍵創建的不是 ziplist 編碼的有序集合物件，而是 skiplist 編碼的有序集合物件，那么這個有序集合物件將會是圖 8-16 所示的樣子，而物件所使用的 zset 結構將會是圖 8-17 所示的樣子，

注意

為了展示方便，圖 8-17 在字典和跳躍表中重復展示了各個元素的成員和分值，但在實際中，字典和跳躍表會共享元素的成員和分值，所以并不會造成任何資料重復，也不會因此而浪費任何記憶體，

為什么有序集合需要同時使用跳躍表和字典來實作？

在理論上來說，有序集合可以單獨使用字典或者跳躍表的其中一種資料結構來實作，但無論單獨使用字典還是跳躍表，在性能上對比起同時使用字典和跳躍表都會有所降低，
舉個例子，如果我們只使用字典來實作有序集合，那么雖然以 O(1) 復雜度查找成員的分值這一特性會被保留，但是，因為字典以無序的方式來保存集合元素，所以每次在執行范圍型操作 —— 比如 ZRANK 、 ZRANGE 等命令時，程式都需要對字典保存的所有元素進行排序，完成這種排序需要至少 O(N \log N) 時間復雜度，以及額外的 O(N) 記憶體空間（因為要創建一個陣列來保存排序后的元素），
另一方面，如果我們只使用跳躍表來實作有序集合，那么跳躍表執行范圍型操作的所有優點都會被保留，但因為沒有了字典，所以根據成員查找分值這一操作的復雜度將從 O(1) 上升為 O(\log N) ，
因為以上原因，為了讓有序集合的查找和范圍型操作都盡可能快地執行， Redis 選擇了同時使用字典和跳躍表兩種資料結構來實作有序集合，

編碼的轉換

當有序集合物件可以同時滿足以下兩個條件時，物件使用 ziplist 編碼：

有序集合保存的元素數量小于 128 個；
有序集合保存的所有元素成員的長度都小于 64 位元組；

不能滿足以上兩個條件的有序集合物件將使用 skiplist 編碼，

對于使用 ziplist 編碼的有序集合物件來說，當使用 ziplist 編碼所需的兩個條件中的任意一個不能被滿足時，程式就會執行編碼轉換操作，將原本儲存在壓縮串列里面的所有集合元素轉移到 zset 結構里面，并將物件的編碼從 ziplist 改為 skiplist ，

注意

以上兩個條件的上限值是可以修改的，具體請看組態檔中關于 zset-max-ziplist-entries 選項和 zset-max-ziplist-value 選項的說明，

有序集合命令的實作

因為有序集合鍵的值為有序集合物件，所以用于有序集合鍵的所有命令都是針對有序集合物件來構建的，表 8-11 列出了其中一部分有序集合鍵命令，以及這些命令在不同編碼的有序集合物件下的實作方法，

命令	ziplist 編碼的實作方法	zset 編碼的實作方法
ZADD	呼叫 ziplistInsert 函式，將成員和分值作為兩個節點分別插入到壓縮串列，	先呼叫 zslInsert 函式，將新元素添加到跳躍表，然后呼叫 dictAdd 函式，將新元素關聯到字典，
ZCARD	呼叫 ziplistLen 函式，獲得壓縮串列包含節點的數量，將這個數量除以 2 得出集合元素的數量，	訪問跳躍表數據結構的 length 屬性，直接回傳集合元素的數量，
ZCOUNT	遍歷壓縮串列，統計分值在給定范圍內的節點的數量，	遍歷跳躍表，統計分值在給定范圍內的節點的數量，
ZRANGE	從表頭向表尾遍歷壓縮串列，回傳給定索引范圍內的所有元素，	從表頭向表尾遍歷跳躍表，回傳給定索引范圍內的所有元素，
ZREVRANGE	從表尾向表頭遍歷壓縮串列，回傳給定索引范圍內的所有元素，	從表尾向表頭遍歷跳躍表，回傳給定索引范圍內的所有元素，
ZRANK	從表頭向表尾遍歷壓縮串列，查找給定的成員，沿途記錄經過節點的數量，當找到給定成員之后，途經節點的數量就是該成員所對應元素的排名，	從表頭向表尾遍歷跳躍表，查找給定的成員，沿途記錄經過節點的數量，當找到給定成員之后，途經節點的數量就是該成員所對應元素的排名，
ZREVRANK	從表尾向表頭遍歷壓縮串列，查找給定的成員，沿途記錄經過節點的數量，當找到給定成員之后，途經節點的數量就是該成員所對應元素的排名，	從表尾向表頭遍歷跳躍表，查找給定的成員，沿途記錄經過節點的數量，當找到給定成員之后，途經節點的數量就是該成員所對應元素的排名，
ZREM	遍歷壓縮串列，洗掉所有包含給定成員的節點，以及被洗掉成員節點旁邊的分值節點，	遍歷跳躍表，洗掉所有包含了給定成員的跳躍表節點，并在字典中解除被洗掉元素的成員和分值的關聯，
ZSCORE	遍歷壓縮串列，查找包含了給定成員的節點，然后取出成員節點旁邊的分值節點保存的元素分值，	直接從字典中取出給定成員的分值，

型別檢查與命令多型

Redis 中用于操作鍵的命令基本上可以分為兩種型別，
其中一種命令可以對任何型別的鍵執行，比如說 DEL 命令、 EXPIRE 命令、 RENAME 命令、 TYPE 命令、 OBJECT 命令，等等，
而另一種命令只能對特定型別的鍵執行，比如說：
- SET 、 GET 、 APPEND 、 STRLEN 等命令只能對字串鍵執行；
- HDEL 、 HSET 、 HGET 、 HLEN 等命令只能對哈希鍵執行；
- RPUSH 、 LPOP 、 LINSERT 、 LLEN 等命令只能對串列鍵執行；
- SADD 、 SPOP 、 SINTER 、 SCARD 等命令只能對集合鍵執行；
- ZADD 、 ZCARD 、 ZRANK 、 ZSCORE 等命令只能對有序集合鍵執行；

例子1，以下代碼就展示了使用 DEL 命令來洗掉三種不同型別的鍵：

 1 # 字串鍵
 2 redis> SET msg "hello"
 3 OK
 4 
 5 # 串列鍵
 6 redis> RPUSH numbers 1 2 3
 7 (integer) 3
 8 
 9 # 集合鍵
10 redis> SADD fruits apple banana cherry
11 (integer) 3
12 
13 redis> DEL msg
14 (integer) 1
15 
16 redis> DEL numbers
17 (integer) 1
18 
19 redis> DEL fruits
20 (integer) 1

例子2，我們可以用 SET 命令創建一個字串鍵，然后用 GET 命令和 APPEND 命令操作這個鍵，但如果我們試圖對這個字串鍵執行只有串列鍵才能執行的 LLEN 命令，那么 Redis 將向我們回傳一個型別錯誤：

 1 redis> SET msg "hello world"
 2 OK
 3 
 4 redis> GET msg
 5 "hello world"
 6 
 7 redis> APPEND msg " again!"
 8 (integer) 18
 9 
10 redis> GET msg
11 "hello world again!"
12 
13 redis> LLEN msg
14 (error) WRONGTYPE Operation against a key holding the wrong kind of value

型別檢查的實作

從上面發生型別錯誤的代碼示例可以看出，為了確保只有指定型別的鍵可以執行某些特定的命令，在執行一個型別特定的命令之前， Redis 會先檢查輸入鍵的型別是否正確，然后再決定是否執行給定的命令，

型別特定命令所進行的型別檢查是通過 redisObject 結構的 type 屬性來實作的：

在執行一個型別特定命令之前，服務器會先檢查輸入資料庫鍵的值物件是否為執行命令所需的型別，如果是的話，服務器就對鍵執行指定的命令；
否則，服務器將拒絕執行命令，并向客戶端回傳一個型別錯誤，

舉個例子，對于 LLEN 命令來說：

在執行 LLEN 命令之前，服務器會先檢查輸入資料庫鍵的值物件是否為串列型別，也即是，檢查值物件 redisObject 結構 type 屬性的值是否為 REDIS_LIST ，如果是的話，服務器就對鍵執行 LLEN 命令；
否則的話，服務器就拒絕執行命令并向客戶端回傳一個型別錯誤；

其他型別特定命令的型別檢查程序也和這里展示的 LLEN 命令的型別檢查程序類似，

多型命令的實作

Redis 除了會根據值物件的型別來判斷鍵是否能夠執行指定命令之外，還會根據值物件的編碼方式，選擇正確的命令實作代碼來執行命令，
舉個例子，在前面介紹串列物件的編碼時我們說過，串列物件有 ziplist 和 linkedlist 兩種編碼可用，其中前者使用壓縮串列 API 來實作串列命令，而后者則使用雙端鏈表 API 來實作串列命令，

現在，考慮這樣一個情況，如果我們對一個鍵執行 LLEN 命令，那么服務器除了要確保執行命令的是串列鍵之外，還需要根據鍵的值物件所使用的編碼來選擇正確的 LLEN 命令實作：

如果串列物件的編碼為 ziplist ，那么說明串列物件的實作為壓縮串列，程式將使用 ziplistLen 函式來回傳串列的長度；
如果串列物件的編碼為 linkedlist ，那么說明串列物件的實作為雙端鏈表，程式將使用 listLength 函式來回傳雙端鏈表的長度；

借用面向物件方面的術語來說，我們可以認為 LLEN 命令是多型（polymorphism）的：只要執行 LLEN 命令的是串列鍵，那么無論值物件使用的是 ziplist 編碼還是 linkedlist 編碼，命令都可以正常執行，

圖 8-19 其他型別特定命令的執行程序也是類似的，

實際上，我們可以將 DEL 、 EXPIRE 、 TYPE 等命令也稱為多型命令，因為無論輸入的鍵是什么型別，這些命令都可以正確地執行，他們和 LLEN 等命令的區別在于，前者是基于型別的多型 —— 一個命令可以同時用于處理多種不同型別的鍵，而后者是基于編碼的多型 —— 一個命令可以同時用于處理多種不同編碼，

記憶體回收

因為 C 語言并不具備自動的記憶體回收功能，所以 Redis 在自己的物件系統中構建了一個參考計數（reference counting）技術實作的記憶體回識訓制，通過這一機制，程式可以通過跟蹤物件的參考計數資訊，在適當的時候自動釋放物件并進行記憶體回收，

每個物件的參考計數資訊由 redisObject 結構的 refcount 屬性記錄：

 1 typedef struct redisObject {
 2 
 3     // ...
 4 
 5     // 參考計數
 6     int refcount;
 7 
 8     // ...
 9 
10 } robj;

物件的參考計數資訊會隨著物件的使用狀態而不斷變化：
- 在創建一個新物件時，參考計數的值會被初始化為 1 ；
- 當物件被一個新程式使用時，它的參考計數值會被增一；
- 當物件不再被一個程式使用時，它的參考計數值會被減一；
- 當物件的參考計數值變為 0 時，物件所占用的記憶體會被釋放，
表 8-12 列出了修改物件參考計數的 API ，這些 API 分別用于增加、減少、重置物件的參考計數，

函式	作用
incrRefCount	將物件的參考計數值增一，
decrRefCount	將物件的參考計數值減一，當物件的參考計數值等于 0 時，釋放物件，
resetRefCount	將物件的參考計數值設定為 0 ，但并不釋放物件，這個函式通常在需要重新設定物件的參考計數值時使用，

物件的整個生命周期可以劃分為創建物件、操作物件、釋放物件三個階段，

作為例子，以下代碼展示了一個字串物件從創建到釋放的整個程序：

1 // 創建一個字串物件 s ，物件的參考計數為 1
2 robj *s = createStringObject(...)
3 
4 // 物件 s 執行各種操作 ...
5 
6 // 將物件 s 的參考計數減一，使得物件的參考計數變為 0
7 // 導致物件 s 被釋放
8 decrRefCount(s)

其他不同型別的物件也會經歷類似的程序，

物件共享

除了用于實作記憶體回識訓制之外，物件的參考計數屬性還帶有物件共享的作用，
在 Redis 中，讓多個鍵共享同一個值物件需要執行以下兩個步驟：

1. 將資料庫鍵的值指標指向一個現有的值物件；
2. 將被共享的值物件的參考計數增一，

舉個例子，圖 8-21 就展示了包含整數值 100 的字串物件同時被鍵 A 和鍵 B 共享之后的樣子，可以看到，除了物件的參考計數從之前的 1 變成了 2 之外，其他屬性都沒有變化，

共享物件機制對于節約記憶體非常有幫助，資料庫中保存的相同值物件越多，物件共享機制就能節約越多的記憶體，

比如說，假設資料庫中保存了整數值 100 的鍵不只有鍵 A 和鍵 B 兩個，而是有一百個，那么服務器只需要用一個字串物件的記憶體就可以保存原本需要使用一百個字串物件的記憶體才能保存的資料，

目前來說， Redis 會在初始化服務器時，創建一萬個字串物件，這些物件包含了從 0 到 9999 的所有整數值，當服務器需要用到值為 0 到 9999 的字串物件時，服務器就會使用這些共享物件，而不是新創建物件，

注意

創建共享字串物件的數量可以通過修改 redis.h/REDIS_SHARED_INTEGERS 常量來修改，

舉個例子，如果我們創建一個值為 100 的鍵 A ，并使用 OBJECT REFCOUNT 命令查看鍵 A 的值物件的參考計數，我們會發現值物件的參考計數為 2 ：

1 redis> SET A 100
2 OK
3 
4 redis> OBJECT REFCOUNT A
5 (integer) 2

參考這個值物件的兩個程式分別是持有這個值物件的服務器程式，以及共享這個值物件的鍵 A ，如圖 8-22 所示，

另外，這些共享物件不單單只有字串鍵可以使用，那些在資料結構中嵌套了字串物件的物件（linkedlist 編碼的串列物件、 hashtable 編碼的哈希物件、 hashtable 編碼的集合物件、以及 zset 編碼的有序集合物件）都可以使用這些共享物件，

為什么 Redis 不共享包含字串的物件？

當服務器考慮將一個共享物件設定為鍵的值物件時，程式需要先檢查給定的共享物件和鍵想創建的目標物件是否完全相同，只有在共享物件和目標物件完全相同的情況下，程式才會將共享物件用作鍵的值物件，而一個共享物件保存的值越復雜，驗證共享物件和目標物件是否相同所需的復雜度就會越高，消耗的 CPU 時間也會越多：

如果共享物件是保存整數值的字串物件，那么驗證操作的復雜度為 O(1) ；
如果共享物件是保存字串值的字串物件，那么驗證操作的復雜度為 O(N) ；
如果共享物件是包含了多個值（或者物件的）物件，比如串列物件或者哈希物件，那么驗證操作的復雜度將會是 O(N^2) ，

因此，盡管共享更復雜的物件可以節約更多的記憶體，但受到 CPU 時間的限制， Redis 只對包含整數值的字串物件進行共享，

物件的空轉時長

除了前面介紹過的 type 、 encoding 、 ptr 和 refcount 四個屬性之外， redisObject 結構包含的最后一個屬性為 lru 屬性，該屬性記錄了物件最后一次被命令程式訪問的時間：

typedef struct redisObject {
   // ... 
   unsigned lru:22; 
   // ... 
} robj;

OBJECT IDLETIME 命令可以列印出給定鍵的空轉時長，這一空轉時長就是通過將當前時間減去鍵的值物件的 lru 時間計算得出的.
除了可以被 OBJECT IDLETIME 命令列印出來之外，鍵的空轉時長還有另外一項作用：如果服務器打開了 maxmemory 選項，并且服務器用于回收記憶體的演算法為 volatile-lru 或者 allkeys-lru ，那么當服務器占用的記憶體數超過了 maxmemory 選項所設定的上限值時，空轉時長較高的那部分鍵會優先被服務器釋放，從而回收記憶體，
- 組態檔的 maxmemory 選項和 maxmemory-policy 選項的說明介紹了關于這方面的更多資訊，

 1 redis> SET msg "hello world"
 2 OK
 3 
 4 # 等待一小段時間
 5 redis> OBJECT IDLETIME msg
 6 (integer) 20
 7 
 8 # 等待一陣子
 9 redis> OBJECT IDLETIME msg
10 (integer) 180
11 
12 # 訪問 msg 鍵的值
13 redis> GET msg
14 "hello world"
15 
16 # 鍵處于活躍狀態，空轉時長為 0
17 redis> OBJECT IDLETIME msg
18 (integer) 0

Redis五種型別的鍵的介紹到這里就結束了，歡迎和大家討論、交流，

內容參考自: 《Redis設計與實作》

========== 碼字不易，轉載請注明出處 ==========

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/259674.html

標籤：NoSQL

上一篇：MySQL視圖

下一篇：Redis五大型別及底層實作原理

Redis五大型別及底層實作原理

目錄

簡單動態字串

導讀