對象

當(dāng)稱呼一個數(shù)據(jù)庫鍵為"字符串鍵"、"列表鍵"時，指的是這個鍵對應(yīng)的值為"字符串對象"、"列表對象"。

Redis并沒有直接使用前面介紹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)鍵值對數(shù)據(jù)庫，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了一個對象系統(tǒng)，這個系統(tǒng)包含字符串對象（string）、列表對象（list）、哈希對象（hash）、集合對象（set）、有序集合對象（zset）。

Redis對象帶有訪問時間記錄信息，該信息可以用于計算數(shù)據(jù)庫鍵的空轉(zhuǎn)時間，在服務(wù)器啟用maxmemory功能情況下，空轉(zhuǎn)時間較大的那些鍵可能會優(yōu)先被服務(wù)器刪除。

1. 對象的類型與編碼

Redis使用對象來表示數(shù)據(jù)庫中的鍵和值。

Redis中的每個對象都由一個redisObject結(jié)構(gòu)表示。該結(jié)構(gòu)中和保存數(shù)據(jù)有關(guān)的三個屬性分別是type、encoding、ptr。

typedef struct redisObject{

    // 類型
    unsigned type:4;

    // 編碼
    unsigned encoding:4;

    // 指向底層實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針
    void *ptr;

    // ...
}

1.1 類型

對象的type屬性記錄了對象的類型，這個屬性可以是下面表格中的一個。

Redis數(shù)據(jù)庫的鍵總是字符串對象，值是上面表格中的一種。

當(dāng)稱呼一個數(shù)據(jù)庫鍵為"字符串鍵"、"列表鍵"時，指的是這個鍵對應(yīng)的值為"字符串對象"、"列表對象"。

TYPE命令返回的也是數(shù)據(jù)庫鍵對應(yīng)的值對象的類型。

1.2 編碼和底層實現(xiàn)

對象的ptr指針指向?qū)ο蟮牡讓訉崿F(xiàn)數(shù)據(jù)結(jié)構(gòu)，而這些數(shù)據(jù)結(jié)構(gòu)由對象的encoding屬性決定。

encoding記錄了對象使用的編碼，也就是這個對象使用了什么數(shù)據(jù)結(jié)構(gòu)作為對象的底層實現(xiàn)。這個屬性的值可以是下面列表中的一個：

每種類型的對象都至少使用兩種編碼，下面是每種類型對象可使用的編碼：

使用OBJECT ENCODING命令可以查看一個數(shù)據(jù)庫鍵的值對象的編碼。

2. 字符串對象

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

如果字符串對象保存的是整數(shù)值，并且這個整數(shù)值可以用long類型來表示，那么字符串對象會將整數(shù)值保存在字符串對象結(jié)構(gòu)的ptr屬性里（將void*轉(zhuǎn)化為long），并將字符串對象的編碼設(shè)置成int。

如果字符串對象保存的是一個字符串值，并且這個字符串值的長度大于32字節(jié)，那么字符串對象將使用一個簡單動態(tài)字符串（SDS）來保存這個字符串值，并將對象的編碼設(shè)置為raw。

如果字符串對象保存的是一個字符串值，并且這個字符串值的長度小于等于32字節(jié)，那么字符串對象將使用embstr編碼的方式來保存這個字符串值。

embstr編碼是專門用于保存短字符串的一種優(yōu)化編碼方式，這種編碼和raw編碼一樣，都使用redisObject、sdshdr結(jié)構(gòu)來表示字符串對象。raw編碼會調(diào)用兩次內(nèi)存分配函數(shù)來分別創(chuàng)建redisObject、sdshdr結(jié)構(gòu)；embstr編碼則通過調(diào)用一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的空間，空間中依次包含redisObject、sdshdr結(jié)構(gòu)。

使用embstr編碼的字符串對象來保存短字符串值有以下好處：

1. embstr編碼將創(chuàng)建字符串對象所需的內(nèi)存分配次數(shù)從raw編碼的兩次降為一次。
2. 釋放embstr編碼的字符串對象只需要調(diào)用一次內(nèi)存釋放函數(shù)，釋放raw編碼的字符串對象需要調(diào)用兩次內(nèi)存釋放函數(shù)。
3. embstr編碼的字符串對象的所有數(shù)據(jù)都保存在一塊連續(xù)的內(nèi)存里面，這種編碼的字符串對象比起raw編碼的字符串對象能更好地利用緩存帶來的優(yōu)勢。

long double類型表示的浮點數(shù)在Redis中也是作為字符串值來保存的。如果要保存一個浮點數(shù)到字符串對象里面，那么程序會先將這個浮點數(shù)轉(zhuǎn)換成字符串值，然后再保存轉(zhuǎn)換所得的字符串值。在有需要時，程序會將保存在字符串對象里面的字符串值轉(zhuǎn)換回浮點數(shù)值，執(zhí)行某些操作，然后再將執(zhí)行操作所得的浮點數(shù)值轉(zhuǎn)換回字符串值，并繼續(xù)保存在字符串對象里面。

下表是字符串對象保存各類型值的編碼方式：

2.1 編碼的轉(zhuǎn)換

int編碼的字符串對象、embstr編碼的字符串對象在條件滿足的情況下，會被轉(zhuǎn)換為raw編碼的字符串對象。如

SET number 10086

APPEND number " is a good number"

Redis沒有給embstr編碼的字符串對象編寫任何相應(yīng)的修改程序，只有int、raw編碼的字符串對象有這些程序。embstr編碼的字符串對象實際上是只讀的。embstr編碼的字符串對象在執(zhí)行修改命令之后，總會變成一個raw編碼的字符串對象。

2.2 字符串命令的實現(xiàn)

字符串命令的實現(xiàn)

3. 列表對象

列表對象的編碼可以是ziplist、linkedlist。

ziplist編碼的列表對象使用壓縮列表作為底層實現(xiàn)，每個壓縮列表節(jié)點（entry）保存了一個列表元素。

linkedlist編碼的列表對象使用雙端鏈表作為底層實現(xiàn)，每個雙端鏈表節(jié)點（node）都保存了一個字符串對象，每個字符串對象都保存了一個列表中的元素。

RPUSH numbers 1 "three" 5

上面numbers鍵的值對象使用ziplist編碼，結(jié)構(gòu)如下圖。

ziplist編碼的numbers列表對象

如果上面的numbers鍵的值對象使用linkedlist編碼，結(jié)構(gòu)如下圖。

linkedlist編碼的numbers列表對象

其中，下面是上圖中使用的簡化字符串對象表示。

簡化的字符串對象表示

下圖是上面簡圖的完整表示

完整的字符串對象表示

3.1 編碼轉(zhuǎn)換

當(dāng)列表對象可以同時滿足以下兩個條件時，列表對象使用ziplist編碼：

1. 列表對象保存的所有字符串元素的長度都小于64字節(jié)。
2. 列表對象保存的元素數(shù)量小于512個。

不能滿足上面兩個條件的列表對象使用linkedlist編碼。

另外，上面兩個條件的上限值是可以修改的，是配置文件中的list-max-ziplist-value、list-max-ziplist-entries。

3.2 列表命令的實現(xiàn)

[圖片上傳失敗...(image-afe8b9-1582442860908)]

4. 哈希對象

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

ziplist編碼的哈希對象使用壓縮列表作為底層實現(xiàn)，每當(dāng)有新的鍵值對要加入哈希對象時，程序會先將保存了鍵的壓縮列表節(jié)點推入到壓縮列表表尾，然后再將保存了值的壓縮列表節(jié)點推入到壓縮列表表尾。于是：

1. 保存了同一鍵值對的兩個節(jié)點總是緊挨在一起，保存鍵的節(jié)點在前，保存值的節(jié)點在后。
2. 先添加到哈希對象中的鍵值對會被放在壓縮列表的表頭方向，后來添加到哈希對象中的鍵值對會被放在壓縮列表的表尾方向。

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

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

HSET profile name "Tom"
HSET profile age 25
HSET profile career "Programer"

上面，profile是用ziplist編碼實現(xiàn)，如下圖

ziplist編碼的profile哈希對象

如果，用hashtable實現(xiàn)profile，會是下面這樣：

hashtable編碼的profile哈希對象

4.1 編碼轉(zhuǎn)換

當(dāng)哈希對象可以同時滿足以下兩個條件時，哈希對象使用ziplist編碼：

1. 哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于64字節(jié)。
2. 哈希對象保存的鍵值對數(shù)量小于512個。

不能滿足這兩個條件的哈希對象需要使用hashtable編碼。

另外，上面兩個條件的上限值是可以修改的，是配置文件中的hash-max-ziplist-value、hash-max-ziplist-entries。

4.2 哈希命令的實現(xiàn)

哈希命令的實現(xiàn)

5. 集合對象

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

intset編碼的集合對象使用整數(shù)集合作為底層實現(xiàn)，集合對象包含的所有元素都被保存在整數(shù)集合里面。

hashtable編碼的集合對象使用字典作為底層實現(xiàn)，字典的每個鍵都是一個字符串對象，每個字符串包含了一個集合元素，字典的值全被設(shè)為NULL。

SAD Dfruits "apple" "banana" "cherry"

下圖是兩種編碼表示的集合對象：

兩種編碼表示的集合對象

5.1 編碼轉(zhuǎn)換

當(dāng)集合對象同時滿足下面兩個條件時，對象使用intset編碼：

1. 集合對象保存的所有元素都是整數(shù)值
2. 集合對象保存的元素數(shù)量不超過512個

不能滿足上面兩個條件的集合對象使用hashtable編碼。

上面第二個條件的上限值可以通過set-max-intset-entries修改。

5.2 集合命令的實現(xiàn)

集合命令的實現(xiàn)

6. 有序集合對象

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

ziplist編碼的壓縮列表對象使用壓縮列表作為底層實現(xiàn)，每個集合元素使用兩個緊挨在一起的壓縮列表節(jié)點來保存，第一個節(jié)點保存元素的成員（member），第二個元素保存元素的分值（score）。

壓縮集合列表內(nèi)的集合元素按分值從小到大進行排序，分值較小的元素被放置在靠近表頭的方向，分值較大的元素被放置到靠近表尾的方向。

ZADD price 8.5 apple 5.0 banana 6.0 cherry

ziplist編碼的有序集合對象

skiplist編碼的有序集合對象使用zset結(jié)構(gòu)作為底層實現(xiàn)，一個zset結(jié)構(gòu)同時包含一個字典、一個跳躍表。

typedef struct zset{

    zskiplist *zsl;

    dict *dict;
}zset;

zset結(jié)構(gòu)中的zsl跳躍表按分值從小到大保存了所有組合元素，每個跳躍表節(jié)點都保存了一個集合元素：跳躍表節(jié)點的object屬性保存了元素的成員，而跳躍表節(jié)點的score屬性保存了元素的分值。通過這個跳躍表，程序可以對有序集合進行范圍型操作，如ZRANK、ZRANGE等命令就是基于跳躍表API來實現(xiàn)的。

zset結(jié)構(gòu)中的dict字典為有序集合創(chuàng)建了一個從成員到分值的映射，字典中的每個鍵值對都保存了一個集合元素：字典的鍵保存了元素的成員，字典的值保存了元素的分值。通過這個字典，程序可以O(shè)(1)
查找給定成員的分值，ZSCORE命令就是根據(jù)這一特性實現(xiàn)，很多其他有序集合命令都在實現(xiàn)內(nèi)部用到了這一特性。

有序集合每個元素的成員都是一個字符串對象，而每個元素的分值都是一個double類型的浮點數(shù)。雖然zset結(jié)構(gòu)同時使用跳躍表和字典來保存有序集合元素，但這兩種數(shù)據(jù)結(jié)構(gòu)都會通過指針來共享相同元素的成員和分值，所以同時使用跳躍表和字典來保存集合元素不會產(chǎn)生任何重復(fù)成員或者分值，不會因此浪費額外的內(nèi)存。

理論上，有序集合可以單獨使用字典和跳躍表的其中一種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，但無論單獨使用字典還是跳躍表，在性能上對比起同時使用字典和跳躍表都會有所降低：

1. 如，只使用字典來實現(xiàn)有序集合，雖然以O(shè)(1)復(fù)雜度查找成員的分值這一特性會被保留，但是，因為字典以無序的方式來保存集合元素，所以每次在執(zhí)行范圍型操作——如ZRANK、ZRANGE等命令時，程序都需要對字典保存的所有元素進行排序，完成這種排序需要至少O(NlogN)時間復(fù)雜度，以及額外O(N)內(nèi)存空間。
2. 如，只使用跳躍表來實現(xiàn)有序集合，那么跳躍表執(zhí)行范圍型操作的所有優(yōu)點都會被保留，但因為沒有了字典，所以根據(jù)成員查找分值的這一操作的復(fù)雜度將從O(1)上升為O(logN)。

因為以上原因，為了讓有序集合的查找和范圍型操作都盡可能快地執(zhí)行，Redis選擇同時使用字典和跳躍表兩種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)有序集合。

如果上述price集合對象使用skiplist編碼，那么如下圖所示。

skiplist編碼的有序集合對象

上圖在字典和跳躍表中重復(fù)展示了各個元素的成員和分值，但在實際中，字典和跳躍表會共享元素的成員和分值，所以并不會造成任何數(shù)據(jù)重復(fù)，也不會因此而浪費任何內(nèi)存。

6.1 編碼轉(zhuǎn)換

當(dāng)有序集合對象可以同時滿足以下兩個條件時，對象使用ziplist編碼：

1. 有序集合保存的元素數(shù)量小于128個。
2. 有序集合保存的所有元素成員的長度都小于64字節(jié)。

不能同時滿足以上兩個條件的有序集合對象將使用skiplist編碼。

以上兩個條件的上限值可以通過zset-max-ziplist-entries和zset-max-ziplist-value來設(shè)置。

6.2 有序集合命令的實現(xiàn)

有序集合命令的實現(xiàn)方法

7. 類型檢查與命令多態(tài)

Redis中用于操作鍵的命令基本上可以分為兩類：

1. 其中一種命令可以對任何類型的鍵執(zhí)行，如DEL、EXPIRE、RENAME、TYPE、OBJECT。
2. 另一種命令只能對特定類型的鍵執(zhí)行，如
   • SET、GET、APPEND、STRLEN等命令只能對字符串鍵執(zhí)行。
   • HDEL、HSET、HGET、HLEN等命令只能對哈希鍵執(zhí)行。
   • RPUSH、LPOP、LINSERT、LLEN等命令只能對列表鍵執(zhí)行。
   • SADD、SPOP、SINTER、SCARD等命令只能對集合鍵執(zhí)行。
   • ZADD、ZCARD、ZRANK、ZSCORE等命令只能對有序集合鍵執(zhí)行。

7.1 類型檢查的實現(xiàn)

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

類型特定命令所進行的類型檢查是通過redisObject結(jié)構(gòu)的type屬性來實現(xiàn)的：

1. 在執(zhí)行一個類型特定命令之前，服務(wù)器會先檢查輸入數(shù)據(jù)庫鍵的值對象是否為執(zhí)行命令所需的類型，如果是，服務(wù)器就對鍵執(zhí)行指定的命令。
2. 否則，服務(wù)器將拒絕執(zhí)行命令，并向客戶端返回一個類型錯誤。

7.2 多態(tài)命令的實現(xiàn)

Redis還會根據(jù)值對象的編碼方式，選擇正確的命令實現(xiàn)代碼來執(zhí)行命令。

8. 內(nèi)存回收

C語言不具備自動回收內(nèi)存的功能，Redis在自己的對象系統(tǒng)中構(gòu)建了引用計數(shù)技術(shù)實現(xiàn)的內(nèi)存回收機制。

每個對象的引用計數(shù)信息由redisObject結(jié)構(gòu)的refcount屬性記錄。

typedef truct redisObject{

    // ...
    // 引用計數(shù)
    int refcount;

    // ...
} robj;

對象的引用計數(shù)信息的變化情況：

1. 在創(chuàng)建一個新對象時，引用計數(shù)的值會被初始化為1。
2. 當(dāng)對象被一個新程序使用時，引用計數(shù)增1。
3. 當(dāng)對象不再被一個新程序使用時，引用計數(shù)減1。
4. 當(dāng)對象的引用計數(shù)值變?yōu)?時，對象所占用的內(nèi)存會釋放。

下圖是修改對象引用計數(shù)的API。

修改對象引用計數(shù)的API

對象的整個生命周期分為創(chuàng)建對象、操作對象、釋放對象三個階段，下面是一個字符串對象從創(chuàng)建到釋放的過程。

// 創(chuàng)建一個字符串對象s，對象的引用計數(shù)為1
robj *s = createStringObject(...)

// 對s執(zhí)行各種操作，...

// 將對象的引用計數(shù)減1，使得對象的引用計數(shù)變?yōu)?，導(dǎo)致對象s被釋放
decrRefCount(s)

9. 對象共享

對象的引用計數(shù)還帶有對象共享的作用。如下圖是被共享的字符串對象。

被共享的字符串對象

在Redis中，讓多個鍵共享同一個值對象需要執(zhí)行下面兩個步驟：

1. 將數(shù)據(jù)庫鍵的值指針指向一個現(xiàn)有的值對象。
2. 將被共享的值對象的引用計數(shù)增1。

目前來說，Redis會在初始化服務(wù)器時，創(chuàng)建0——9999這一萬個字符串對象，服務(wù)器會使用這些共享對象，不再創(chuàng)建新對象?？梢孕薷膔edis.h/REDIS_SHARED_INTEGERS常量來修改創(chuàng)建的共享這些包含整數(shù)值的字符串對象的數(shù)量。

這些共享對象不單單只有字符串鍵可以使用，那些在數(shù)據(jù)結(jié)構(gòu)中嵌套了字符串對象的對象（linkedlist編碼的列表對象、hashtable編碼的哈希對象、hashtable編碼的集合對象、zset編碼的有序集合對象）都可以使用這些共享對象。

Redis只對包含整數(shù)值的字符串對象進行共享，因為：

1. 如果共享對象是保存整數(shù)值的字符串對象，那么驗證操作的復(fù)雜度為O(1)。
2. 如果共享對象是保存字符串值的字符串對象，那么驗證操作的復(fù)雜度為O(N)。
3. 如果共享對象是包含了多個值（或者對象的）對象，如列表對象或者哈希對象，那么驗證操作的復(fù)雜度會是O(N^2)。

上面說的驗證操作指的是Redis要比較需要創(chuàng)建的新對象與已經(jīng)存在的對象的值是否相同。

10. 對象的空轉(zhuǎn)時長

redisObject結(jié)構(gòu)中的lru屬性記錄了對象最后一次被命令程序訪問的時間。

typedef struct redisObject{

    // ...

    unsigned lru:22;

    // ...
} robj;

OBJECT IDLETIME可以打印給定鍵的空轉(zhuǎn)時長，通過計算當(dāng)前時間減去鍵的值對象的lru時間得出。

OBJECT IDLETIME不會修改值對象的lru屬性。

如果服務(wù)器打開了maxmemory選項，并且服務(wù)器用于回收內(nèi)存的算法為volatile-lru或allkeys-lru，那么當(dāng)服務(wù)器占用的內(nèi)存數(shù)超過了maxmemory選項所設(shè)置的上限值時，空轉(zhuǎn)時長較高的那部分鍵會優(yōu)先被服務(wù)器釋放，從而回收內(nèi)存。