一文理解Redis底層數(shù)據(jù)結(jié)構(gòu)

Redis的5種常見數(shù)據(jù)結(jié)構(gòu)：字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)。這些都是Redis對(duì)外暴露的數(shù)據(jù)結(jié)構(gòu)，本文將介紹這些數(shù)據(jù)結(jié)構(gòu)的底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。

Redis底層數(shù)據(jù)結(jié)構(gòu)有六種：

• 簡單動(dòng)態(tài)字符串（SDS）

• 列表

• 字典

• 整數(shù)集合

• 跳躍表

• 壓縮列表

• 快速列表

簡單動(dòng)態(tài)字符串（SDS）

SDS是"simple dynamic string"的縮寫。Redis中所有場(chǎng)景中出現(xiàn)的字符串，基本都是由SDS來實(shí)現(xiàn)的。

使用場(chǎng)景：

• 所有非數(shù)字的key。例如：set msg "hello world"中的key msg.

• 字符串?dāng)?shù)據(jù)類型的值。例如：set msg "hello world"中的msg的值"hello wolrd"

• 非字符串?dāng)?shù)據(jù)類型中的“字符串值”。例如：RPUSH fruits "apple" "banana" "cherry"中的"apple" "banana" "cherry"

SDS結(jié)構(gòu)圖：

• len：記錄當(dāng)前已使用的字節(jié)數(shù)（不包括'\0'），獲取SDS長度的復(fù)雜度為O(1)（C 語言中獲取字符串長度的時(shí)間復(fù)雜度為 O(N)）。此外，len值還避免了二進(jìn)制安全與緩存區(qū)溢出的問題。

• alloc：記錄當(dāng)前字節(jié)數(shù)組總共分配的字節(jié)數(shù)量（不包括'\0'）。

• flags：標(biāo)記當(dāng)前字節(jié)數(shù)組的屬性，是sdshdr8還是sdshdr16等。

• buf：字節(jié)數(shù)組，用于保存字符串，包括結(jié)尾空白字符'\0'。

// flags值定義(為了節(jié)約頭部空間，在Redis3.2開始，增加flag字段。SDS由一種數(shù)據(jù)結(jié)構(gòu)變成了5種數(shù)據(jù)結(jié)構(gòu)，會(huì)根據(jù)SDS存儲(chǔ)的內(nèi)容長度來選擇不同的結(jié)構(gòu)，以達(dá)到節(jié)省內(nèi)存的效果)
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

注：

1. 二進(jìn)制安全：通俗的講，C語言中，用“\0”表示字符串的結(jié)束，如果字符串本身就有“\0”字符，字符串就會(huì)被截?cái)啵捶嵌M(jìn)制安全；若通過某種機(jī)制，保證讀寫字符串時(shí)不損害其內(nèi)容，這就是二進(jìn)制安全。

2. 因?yàn)镃字符串不記錄自身的長度，所以strcat會(huì)假定用戶在執(zhí)行這個(gè)函數(shù)時(shí)，已經(jīng)為dest分配足夠多的內(nèi)存了，可以容納src字符串中的所有內(nèi)容，而一旦這個(gè)假設(shè)不成立，就會(huì)產(chǎn)生緩存區(qū)溢出。

頻繁內(nèi)存分配問題處理

每次增長或者縮短一個(gè)字符，程序都需要對(duì)保存這個(gè)字符串的數(shù)組進(jìn)行一次內(nèi)存重新分配操作。因?yàn)閮?nèi)存重分配涉及復(fù)雜的算法，并且可能需要執(zhí)行系統(tǒng)調(diào)用，所以它通常是一個(gè)比較耗時(shí)的操作。

為了避免C字符串的這種缺陷，SDS通過未使用空間解除了字符串長度和底層數(shù)組長度之間的關(guān)聯(lián)。通過未使用空間，SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。

1. 空間預(yù)分配

空間預(yù)分配用于優(yōu)化SDS的字符串增長操作。當(dāng)SDS的API對(duì)一個(gè)SDS進(jìn)行修改，并且需要對(duì)SDS進(jìn)行空間擴(kuò)展的時(shí)候，程序不僅會(huì)為SDS分配修改所必須要的空間，還會(huì)為SDS分配額外的未使用空間。其中，額外分配的未使用空間數(shù)量由以下公式?jīng)Q定：

• 如果對(duì)SDS進(jìn)行修改之后，SDS的長度將小于1MB，那么程序分配和len屬性同樣大小的未使用空間。

• 如果對(duì)SDS進(jìn)行修改之后，SDS的長度將大于等于1MB，那么程序會(huì)分配1MB的未使用空間。

在擴(kuò)展SDS空間之前，SDS API會(huì)先檢查未使用空間是否足夠，如果足夠的話，API就會(huì)直接使用未使用空間，而無需執(zhí)行內(nèi)存重分配。通過空間預(yù)分配策略，Redis可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。

2. 惰性空間釋放

惰性空間釋放用于優(yōu)化SDS的字符串縮短操作。當(dāng)SDS的API需要縮短SDS保存的字符串時(shí)，程序不會(huì)立即使用內(nèi)存重分配來回收縮短后多出來的字節(jié)，而是使用free屬性將這些字節(jié)的數(shù)量記錄下來，并等待將來使用。

通過惰性空間釋放策略，SDS避免了縮短字符串時(shí)所需的內(nèi)存重分配操作，并為將來可能的增長操作提供了優(yōu)化。

與此同時(shí)，SDS也提供了響應(yīng)的API可以在有需要時(shí)，真正的釋放SDS里面的未使用空間，所以不用擔(dān)心惰性空間釋放策略會(huì)造成內(nèi)存浪費(fèi)。

列表

列表在Redis中應(yīng)用的非常廣，列表的底層實(shí)現(xiàn)就是鏈表。此外，Redis的發(fā)布與訂閱、慢查詢、監(jiān)視器等功能也用到了鏈表。

列表特點(diǎn)：

• 雙端鏈表：帶有指向前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的指針，獲取這兩個(gè)節(jié)點(diǎn)的復(fù)雜度為O(1)。

• 無環(huán)：表頭節(jié)點(diǎn)的prev和表尾節(jié)點(diǎn)的next都指向NULL，對(duì)鏈表的訪問以NULL結(jié)束。

• 鏈表長度計(jì)數(shù)器：帶有l(wèi)en屬性，獲取鏈表長度的復(fù)雜度為O(1)。

• 多態(tài)：鏈表節(jié)點(diǎn)使用 void*指針保存節(jié)點(diǎn)值，可以保存不同類型的值。

列表結(jié)構(gòu)圖：

列表的數(shù)據(jù)結(jié)構(gòu)（adlist.h/listNode與adlist.h/list）：

listNode：

• prev：前置節(jié)點(diǎn)。

• next：后置節(jié)點(diǎn)。

• value：節(jié)點(diǎn)值。

list：

• head：鏈表頭節(jié)點(diǎn)。

• tail：鏈表尾節(jié)點(diǎn)。

• len：鏈表所包含的節(jié)點(diǎn)數(shù)量。

• dup：函數(shù)，用于復(fù)制ptr值，實(shí)現(xiàn)深度復(fù)制。

• free：函數(shù)，用于釋放對(duì)應(yīng)類型結(jié)構(gòu)的內(nèi)存。

• match：函數(shù)，用于對(duì)比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等。

字典

字典，又稱為符號(hào)表（symbol table）、關(guān)聯(lián)數(shù)組（associative array）或映射（map），是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。字典中的每一個(gè)鍵都是唯一的，可以通過鍵查找與之關(guān)聯(lián)的值，并對(duì)其修改或刪除。

Redis的鍵值對(duì)存儲(chǔ)就是用字典實(shí)現(xiàn)的，散列（Hash）的底層實(shí)現(xiàn)之一也是字典。

字典的結(jié)構(gòu)圖（與JDk中的HashMap結(jié)構(gòu)很相似）：

字典的數(shù)據(jù)結(jié)構(gòu)（dict.h/dictht與dict.h/dict）：

dict：

• type：針對(duì)不同類型的鍵值對(duì)，用于創(chuàng)建多類型的字典

• privdata：針對(duì)不同類型的鍵值對(duì)，用于創(chuàng)建多類型的字典

• ht：兩個(gè)元素的數(shù)組，包含兩個(gè)dictht哈希表，一般字典只使用ht[0]哈希表，ht[1]哈希表會(huì)在對(duì)ht[0]哈希表進(jìn)行rehash（重哈希）的時(shí)候使用，即當(dāng)哈希表的鍵值對(duì)數(shù)量超過負(fù)載數(shù)量過多的時(shí)候，會(huì)將鍵值對(duì)遷移到ht[1]上

• rehashidx：rehashidx也是跟rehash相關(guān)的，rehash的操作不是瞬間完成的，rehashidx記錄著rehash的進(jìn)度，圖中沒有進(jìn)行rehash，它的值為-1

dictht：

• table：哈希鏈表（包含了一個(gè)節(jié)點(diǎn)類型為dictEntry的鏈表）

• size：哈希鏈表大小

• sizemask：哈希鏈表大小掩碼，用于計(jì)算索引值，等于size-1

• used：哈希鏈表已有節(jié)點(diǎn)的數(shù)量

dictEntry：

• key：鍵

• next：下一個(gè)dictEntry節(jié)點(diǎn)

• value：union類型，支持不同類型的值

漸進(jìn)式hash

字典類型容量變化過程叫做rehash。需要滿足一定的條件才能觸發(fā)擴(kuò)容機(jī)制：

1. 服務(wù)器當(dāng)前沒有進(jìn)行BGWRITEAOF或者BGSAVE命令，且當(dāng)前鍵值對(duì)個(gè)數(shù)超過一維數(shù)組的大小，才會(huì)觸發(fā)擴(kuò)容。

2. 如果當(dāng)前鍵值對(duì)個(gè)數(shù)超過一維數(shù)組大小的五倍，無論是否在進(jìn)行BGWRITEAOF或者BGSAVE命令，都會(huì)強(qiáng)制擴(kuò)容。

3. 如果當(dāng)前鍵值對(duì)個(gè)數(shù)少于一維數(shù)組大小的十分之一，則觸發(fā)縮容過程。縮容不會(huì)考慮當(dāng)前服務(wù)器是否在進(jìn)行BGWRITEAOF或者BGSAVE命令。

漸進(jìn)式hash的過程，簡單來說類似數(shù)據(jù)庫的遷移，讀的時(shí)候先讀ht[0]，讀不到讀ht[1]；寫的時(shí)候只寫ht[1]；ht[0]數(shù)據(jù)慢慢地往ht[1]上搬。

當(dāng)ht[0]的所有鍵值都遷至ht[1]之后，ht[0]變?yōu)榭毡恚尫舎t[0]。并將ht[1]設(shè)置為ht[0]，并在ht[1]新創(chuàng)建一個(gè)空白哈希表，將rehashidx屬性的值設(shè)為-1，表示rehash操作已完成。

具體步驟如下：

1. 為字典的備用哈希表分配空間：如果執(zhí)行的是擴(kuò)展操作，那么備用哈希表的大小為第一個(gè)大于等于(已用節(jié)點(diǎn)個(gè)數(shù))*2的2n（2的n次方冪） 如果執(zhí)行的是收縮操作，那么備用哈希表的大小為第一個(gè)大于等于(已用節(jié)點(diǎn)個(gè)數(shù))的2n

2. 在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它的值設(shè)置為0，表示rehash工作正式開始（為-1時(shí)表示沒有進(jìn)行rehash）。

3. rehash進(jìn)行期間，每次對(duì)字典執(zhí)行添加、刪除、查找或者更新操作時(shí)，程序除了執(zhí)行指定的操作以外，還會(huì)順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]，當(dāng)一次rehash工作完成之后，程序?qū)ehashidx屬性的值+1。同時(shí)在serverCron中調(diào)用rehash相關(guān)函數(shù)，在1ms的時(shí)間內(nèi)，進(jìn)行rehash處理，每次僅處理少量的轉(zhuǎn)移任務(wù)(100個(gè)元素)。隨著字典操作的不斷執(zhí)行，最終在某個(gè)時(shí)間點(diǎn)上，ht[0]的所有鍵值對(duì)都會(huì)被rehash至ht[1]，這時(shí)程序?qū)ehashidx屬性的值設(shè)為-1，表示rehash操作已完成。

這里比較下Redis的漸進(jìn)hash與JDk中HashMap的resize過程。如果對(duì)HashMap不了解，可以查看《詳解并發(fā)下的HashMap以及JDK8的優(yōu)化》。

整數(shù)集合

整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)，可以保存類型為int16_t、int32_t、int64_t的整數(shù)值，并且保證集合中不會(huì)出現(xiàn)重復(fù)元素 整數(shù)集合是集合（Set）的底層實(shí)現(xiàn)之一，如果一個(gè)集合只包含整數(shù)值元素，且元素?cái)?shù)量不多時(shí)，會(huì)使用整數(shù)集合作為底層實(shí)現(xiàn)

整數(shù)集合的結(jié)構(gòu)圖：

整數(shù)集合的數(shù)據(jù)結(jié)構(gòu)（inset.h/inset）：

intset：

• encoding：決定contents數(shù)組的真正類型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64。

• length：記錄整數(shù)集合的元素?cái)?shù)量，即contents數(shù)組長度

• contents：整數(shù)集合的每個(gè)元素在數(shù)組中按值的大小從小到大排序，且不包含重復(fù)項(xiàng)。

整數(shù)集合的升級(jí)

當(dāng)想要添加一個(gè)新元素到整數(shù)集合中時(shí)，并且新元素的類型比整數(shù)集合現(xiàn)有的所有元素的類型都要長，整數(shù)集合需要先進(jìn)行升級(jí)，才能將新元素添加到整數(shù)集合里面。每次想整數(shù)集合中添加新元素都有可能會(huì)引起升級(jí)，每次升級(jí)都需要對(duì)底層數(shù)組已有的所有元素進(jìn)行類型轉(zhuǎn)換。

升級(jí)添加新元素：

• 根據(jù)新元素類型，擴(kuò)展整數(shù)集合底層數(shù)組的空間大小，并為新元素分配空間。

• 把數(shù)組現(xiàn)有的元素都轉(zhuǎn)換成新元素的類型，并將轉(zhuǎn)換后的元素放到正確的位置，且要保持?jǐn)?shù)組的有序性。

• 添加新元素到底層數(shù)組。

整數(shù)集合的升級(jí)策略可以提升整數(shù)集合的靈活性，并盡可能的節(jié)約內(nèi)存。另外，整數(shù)集合不支持降級(jí)，一旦升級(jí)，編碼就會(huì)一直保持升級(jí)后的狀態(tài)。

跳躍表

一個(gè)普通的單鏈表查詢一個(gè)元素的時(shí)間復(fù)雜度為O(N)，即便該單鏈表是有序的。使用跳躍表（SkipList）是來解決查找問題的，它是一種有序的數(shù)據(jù)結(jié)構(gòu)，不屬于平衡樹結(jié)構(gòu)，也不屬于Hash結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)維持多個(gè)指向其他節(jié)點(diǎn)的指針，而達(dá)到快速訪問節(jié)點(diǎn)的目的 跳躍表是有序集合（Sorted Set）的底層實(shí)現(xiàn)之一，如果有序集合包含的元素比較多，或者元素的成員是比較長的字符串時(shí)，Redis會(huì)使用跳躍表做有序集合的底層實(shí)現(xiàn)。

跳躍表其實(shí)可以把它理解為多層的鏈表，它有如下的性質(zhì)：

• 多層的結(jié)構(gòu)組成，每層是一個(gè)有序的鏈表

• 最底層（level 1）的鏈表包含所有的元素

• 跳躍表的查找次數(shù)近似于層數(shù)，時(shí)間復(fù)雜度為O(logn)，插入、刪除也為 O(logn)

• 跳躍表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)(通過拋硬幣來決定層數(shù))

有關(guān)跳躍表的講解，可以查看《有關(guān)跳躍表的干貨都在這里》

跳躍表的結(jié)構(gòu)圖：

• 每個(gè)跳躍表節(jié)點(diǎn)的層數(shù)在1-32之間

• 一個(gè)跳躍表中，節(jié)點(diǎn)按照分值大小排序，多個(gè)節(jié)點(diǎn)的分值是可以相同的，相同時(shí)，節(jié)點(diǎn)按成員對(duì)象大小排序

• 每個(gè)節(jié)點(diǎn)的成員變量必須是唯一的

壓縮列表

壓縮列表（ziplist）是為了節(jié)約內(nèi)存而設(shè)計(jì)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序性（sequential）數(shù)據(jù)結(jié)構(gòu)，一個(gè)壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

壓縮列表是列表（List）和散列（Hash）的底層實(shí)現(xiàn)之一，一個(gè)列表只包含少量列表項(xiàng)，并且每個(gè)列表項(xiàng)是小整數(shù)值或比較短的字符串，會(huì)使用壓縮列表作為底層實(shí)現(xiàn)（在3.2版本之后是使用quicklist實(shí)現(xiàn)）。

壓縮列表的結(jié)構(gòu)圖：

一個(gè)壓縮列表可以包含多個(gè)節(jié)點(diǎn)（entry），每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。

壓縮列表的數(shù)據(jù)結(jié)構(gòu)：

• zlbytes：記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)，在壓縮列表內(nèi)存重分配，或者計(jì)算zlend的位置時(shí)使用。

• zltail：記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié)，通過該偏移量，可以不用遍歷整個(gè)壓縮列表就可以確定表尾節(jié)點(diǎn)的地址。

• zllen：記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量，但該屬性值小于UINT16_MAX（65535）時(shí)，該值就是壓縮列表的節(jié)點(diǎn)數(shù)量，否則需要遍歷整個(gè)壓縮列表才能計(jì)算出真實(shí)的節(jié)點(diǎn)數(shù)量。

• entryX：壓縮列表的節(jié)點(diǎn)。

• zlend：特殊值0xFF（十進(jìn)制255），用于標(biāo)記壓縮列表的末端。

壓縮列表節(jié)點(diǎn)的構(gòu)成

每個(gè)壓縮列表節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)字或者一個(gè)整數(shù)值。壓縮列表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：

• previous_entry_ength：記錄壓縮列表前一個(gè)字節(jié)的長度。

• encoding：節(jié)點(diǎn)的encoding保存的是節(jié)點(diǎn)的content的內(nèi)容類型。

• content：content區(qū)域用于保存節(jié)點(diǎn)的內(nèi)容，節(jié)點(diǎn)內(nèi)容類型和長度由encoding決定。

快速列表

考慮到鏈表的附加空間相對(duì)太高，prev和next指針就要占去16個(gè)字節(jié)（64bit系統(tǒng)的指針是8個(gè)字節(jié)）。另外每個(gè)節(jié)點(diǎn)的內(nèi)存都是單獨(dú)分配，會(huì)加劇內(nèi)存的碎片化，影響內(nèi)存管理效率。因此Redis3.2版本開始對(duì)列表數(shù)據(jù)結(jié)構(gòu)進(jìn)行了改造，使用快速列表（quicklist）代替了壓縮列表和列表。

快速列表的結(jié)構(gòu)圖：

快速列表的數(shù)據(jù)結(jié)構(gòu)：

quicklistNode：

• prev: 指向鏈表前一個(gè)節(jié)點(diǎn)的指針。

• next: 指向鏈表后一個(gè)節(jié)點(diǎn)的指針。

• zl: 數(shù)據(jù)指針。如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)沒有壓縮，那么它指向一個(gè)ziplist結(jié)構(gòu)；否則，它指向一個(gè)quicklistLZF結(jié)構(gòu)。

• sz: 表示zl指向的ziplist的總大小（包括zlbytes, zltail, zllen, zlend和各個(gè)數(shù)據(jù)項(xiàng)）。需要注意的是：如果ziplist被壓縮了，那么這個(gè)sz的值仍然是壓縮前的ziplist大小。

• count: 表示ziplist里面包含的數(shù)據(jù)項(xiàng)個(gè)數(shù)。這個(gè)字段只有16bit。稍后我們會(huì)一起計(jì)算一下這16bit是否夠用。

• encoding: 表示ziplist是否壓縮了（以及用了哪個(gè)壓縮算法）。目前只有兩種取值：2表示被壓縮了（而且用的是LZF壓縮算法），1表示沒有壓縮。

• container: 是一個(gè)預(yù)留字段。本來設(shè)計(jì)是用來表明一個(gè)quicklist節(jié)點(diǎn)下面是直接存數(shù)據(jù)，還是使用ziplist存數(shù)據(jù)，或者用其它的結(jié)構(gòu)來存數(shù)據(jù)（用作一個(gè)數(shù)據(jù)容器，所以叫container）。但是，在目前的實(shí)現(xiàn)中，這個(gè)值是一個(gè)固定的值2，表示使用ziplist作為數(shù)據(jù)容器。

• recompress: 當(dāng)我們使用類似lindex這樣的命令查看了某一項(xiàng)本來壓縮的數(shù)據(jù)時(shí)，需要把數(shù)據(jù)暫時(shí)解壓，這時(shí)就設(shè)置recompress=1做一個(gè)標(biāo)記，等有機(jī)會(huì)再把數(shù)據(jù)重新壓縮。

• attempted_compress: 這個(gè)值只對(duì)Redis的自動(dòng)化測(cè)試程序有用。

• extra: 其它擴(kuò)展字段。

quickList：

• head: 指向頭節(jié)點(diǎn)（左側(cè)第一個(gè)節(jié)點(diǎn)）的指針。

• tail: 指向尾節(jié)點(diǎn)（右側(cè)第一個(gè)節(jié)點(diǎn)）的指針。

• count: 所有ziplist數(shù)據(jù)項(xiàng)的個(gè)數(shù)總和。

• len: quicklist節(jié)點(diǎn)的個(gè)數(shù)。

• fill: 16bit，ziplist大小設(shè)置，存放list-max-ziplist-size參數(shù)的值。

• compress: 16bit，節(jié)點(diǎn)壓縮深度設(shè)置，存放list-compress-depth參數(shù)的值。

壓縮深度

quicklist默認(rèn)的壓縮深度是0，也就是不壓縮。壓縮的實(shí)際深度由配置參數(shù)list-compress-depth決定。為了支持快速的push/pop操作，quicklist的首尾兩個(gè)ziplist不壓縮，此時(shí)深度就是1；如果深度為2，就表示quicklist的首尾第一個(gè) ziplist以及首尾第二個(gè)ziplist都不壓縮。

zipList長度

quicklist 內(nèi)部默認(rèn)單個(gè)ziplist長度為8k字節(jié)，超出了這個(gè)字節(jié)數(shù)，就會(huì)新起一個(gè)ziplist。ziplist的長度由配置參數(shù)list-max-ziplist-size決定。

編碼

上面介紹了Redis的主要底層數(shù)據(jù)結(jié)構(gòu)，包括簡單動(dòng)態(tài)字符串（SDS）、鏈表、字典、跳躍表、整數(shù)集合、壓縮列表。但是Redis并沒有直接使用這些數(shù)據(jù)結(jié)構(gòu)來構(gòu)建數(shù)據(jù)庫，而是基于這些數(shù)據(jù)結(jié)構(gòu)創(chuàng)建不同的編碼，然后由不同條件下的不同編碼來實(shí)現(xiàn)Redis的這些數(shù)據(jù)類型：字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)。

接下來就介紹Redis五種數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)的編碼。

字符串對(duì)象的編碼

上面介紹了SDS，但這只是字符串對(duì)象的其中一種實(shí)現(xiàn)。字符串對(duì)象的編碼可能有三種：int、raw、embstr。

1. int
   如果一個(gè)字符串對(duì)象，保存的值是一個(gè)整數(shù)值，并且這個(gè)整數(shù)值在long的范圍內(nèi)，那么Redis用整數(shù)值來保存這個(gè)信息，并且將字符串編碼設(shè)置為 int。

2. raw
   如果字符串對(duì)象保存的是一個(gè)字符串, 并且長度大于32個(gè)字節(jié)，它就會(huì)使用前面講過的SDS（簡單動(dòng)態(tài)字符串）數(shù)據(jù)結(jié)構(gòu)來保存這個(gè)字符串值，并且將字符串對(duì)象的編碼設(shè)置為raw。

3. embstr
   如果字符串對(duì)象保存的是一個(gè)字符串，但是長度小于32個(gè)字節(jié)，它就會(huì)使用embstr來保存了，embstr編碼不是一個(gè)數(shù)據(jù)結(jié)構(gòu)，而是對(duì)SDS的一個(gè)小優(yōu)化，當(dāng)使用SDS 的時(shí)候，程序需要調(diào)用兩次內(nèi)存分配，來給字符串對(duì)象和SDS各自分配一塊空間，而embstr只需要一次內(nèi)存分配，因?yàn)樗枰目臻g很少，所以采用連續(xù)的空間保存，即將SDS的值和字符串對(duì)象的值放在一塊連續(xù)的內(nèi)存空間上。這樣能在短字符串的時(shí)候提高一些效率。

浮點(diǎn)數(shù)如何保存：

Redis的字符串?dāng)?shù)據(jù)類型是支持保存浮點(diǎn)數(shù)，并且支持對(duì)浮點(diǎn)數(shù)進(jìn)行加減操作，但是Redis在底層是把浮點(diǎn)數(shù)轉(zhuǎn)換成字符串值，然后按照上述編碼規(guī)則。對(duì)浮點(diǎn)數(shù)進(jìn)行操作時(shí)，也是從字符串轉(zhuǎn)換成浮點(diǎn)數(shù)進(jìn)行計(jì)算，然后再轉(zhuǎn)換成字符串進(jìn)行保存的。

編碼轉(zhuǎn)換條件：

如果對(duì)一個(gè)int編碼的字符串對(duì)象，修改它成非整數(shù)值，則對(duì)象就會(huì)使用raw編碼。而Redis沒有為embstr編碼提供任何的修改操作，embstr編碼的值是只讀的，只要發(fā)生修改，立刻將編碼轉(zhuǎn)換成raw。

編碼	使用條件
int	可以用long保存的整數(shù)
raw	長度大于32的字符串
embstr	字符串長度小于32字節(jié)（或者浮點(diǎn)數(shù)轉(zhuǎn)換后滿足）

列表對(duì)象的編碼

在 Redis 3.2 版本之前，列表對(duì)象底層由 壓縮列表和雙向鏈表配合實(shí)現(xiàn)，當(dāng)元素?cái)?shù)量較少的時(shí)候，使用壓縮列表，當(dāng)元素?cái)?shù)量增多，就開始使用普通的雙向鏈表保存數(shù)據(jù)。

但是這種實(shí)現(xiàn)方式不夠好，雙向鏈表中的每個(gè)節(jié)點(diǎn)，都需要保存前后指針，這個(gè)內(nèi)存的使用量 對(duì)于Redis這個(gè)內(nèi)存數(shù)據(jù)庫來說極其不友好。

因此在 3.2 之后的版本，Redis新實(shí)現(xiàn)了一個(gè)數(shù)據(jù)結(jié)構(gòu)，叫做快速列表（quicklist）。所有列表的底層實(shí)現(xiàn)都是這個(gè)數(shù)據(jù)結(jié)構(gòu)了。它的底層實(shí)現(xiàn)基本上就是將 雙向鏈表和壓縮列表進(jìn)行了結(jié)合，用雙向的指針將壓縮列表進(jìn)行連接，這樣不僅避免了壓縮列表存儲(chǔ)大量元素的性能壓力，同時(shí)避免了雙向鏈表連接指針占用空間過多的問題。

編碼	使用條件
quicklist	無

集合對(duì)象的編碼

集合對(duì)象的編碼可以是intset或者h(yuǎn)ashtable。

當(dāng)集合中的所有元素都是整數(shù)，且元素的數(shù)量不大于512個(gè)的時(shí)候，使用intset編碼。

當(dāng)元素不符合全部為整數(shù)值且元素個(gè)數(shù)小于512時(shí)，集合對(duì)象使用的編碼方式為 hashtable。

編碼	使用條件
intset	所有元素都是整數(shù)且元素個(gè)數(shù)小于 512
hashtable	其他數(shù)據(jù)

有序集合對(duì)象的編碼

有序集合對(duì)象的編碼可以是ziplist以及skiplist。

當(dāng)使用ziplist編碼時(shí)，有序集合對(duì)象的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)為壓縮列表。當(dāng)條件變化，ziplist編碼會(huì)轉(zhuǎn)換成skiplist編碼。

當(dāng)使用skiplist編碼的時(shí)候，內(nèi)部使用zset 來實(shí)現(xiàn)數(shù)據(jù)的保存，zset的定義如下：

typedef struct zset{
  zskiplist *zsl;
  dict *dict;
}zset;

為什么需要同時(shí)使用跳躍表以及字典呢？

• 當(dāng)只使用字典來實(shí)現(xiàn)，可以以O(shè)(1)的時(shí)間復(fù)雜度獲取成員的分值，但是由于字典是無序的，當(dāng)需要進(jìn)行范圍性操作的時(shí)候，需要對(duì)字典中的所有元素進(jìn)行排序，這個(gè)時(shí)間復(fù)雜度至少需要 O(nlogn)。

• 當(dāng)只使用跳躍表來實(shí)現(xiàn)，可以在O(logn)的時(shí)間進(jìn)行范圍排序操作，但是如果要獲取到某個(gè)元素的分值，時(shí)間復(fù)雜度也是O(logn)。

因此，將字典和跳躍表結(jié)合進(jìn)行使用，可以在O(1)的時(shí)間復(fù)雜度下完成查詢分值操作，而對(duì)一些范圍操作使用跳躍表可以達(dá)到O(logn)的時(shí)間復(fù)雜度。

編碼	使用條件
ziplist	元素?cái)?shù)量少于128且所有元素成員的長度小于64字節(jié)
skiplist	不滿足上述條件的其他情況

散列對(duì)象

散列對(duì)象的編碼可以是ziplist或者h(yuǎn)ashtable.

ziplist編碼下的哈希對(duì)象，使用了壓縮列表作為底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，用兩個(gè)連續(xù)的壓縮列表節(jié)點(diǎn)來表示哈希對(duì)象中的一個(gè)鍵值對(duì)。實(shí)現(xiàn)方式類似于上面的有序集合的場(chǎng)景。

哈希結(jié)構(gòu)本身在結(jié)構(gòu)上和字典頗為相似，因此哈希對(duì)象中的每一個(gè)鍵值對(duì)都是字典中的一個(gè)鍵值對(duì)。

• 字典的每一個(gè)鍵都是一個(gè)字符串對(duì)象，對(duì)象中保存了鍵值對(duì)的鍵。

• 字典的每一個(gè)值都是一個(gè)字符串對(duì)象，對(duì)象中保存了鍵值對(duì)的值。

編碼	使用條件
ziplist	鍵值對(duì)的鍵和值的長度都小于64字節(jié)，且鍵值對(duì)個(gè)數(shù)小于512
hastable	不滿足上述條件的其他情況

總結(jié)

基礎(chǔ)數(shù)據(jù)類型	可能的編碼方式
字符串	int, raw, embstr
列表	之前是 ziplist, linkedlist。3.2開始都是quicklist
集合	intset, hashtable
有序集合	ziplist, skiplist
散列	ziplist, hashtable

參考文檔：

1. 《Redis設(shè)計(jì)與實(shí)現(xiàn)》

2. https://github.com/redis/redis

3. 《Redis 深度歷險(xiǎn)：核心原理和應(yīng)用實(shí)踐》