以前在使用Redis的時(shí)候，只是簡(jiǎn)單地使用它提供的基本數(shù)據(jù)類型和接口，并沒(méi)有深入研究它底層的數(shù)據(jù)結(jié)構(gòu)。最近打算重新學(xué)習(xí)梳理一下Redis方面的知識(shí)，所以打算從介紹Redis的基本類型及其數(shù)據(jù)結(jié)構(gòu)入手。

[[275524]]

redisObject

Redis的key是頂層模型，它的value是扁平化的。Redis中，所有的value都是一個(gè)object，它的結(jié)構(gòu)如下：

typedef struct redisObject { 
 unsigned [type] 4; 
 unsigned [encoding] 4; 
 unsigned [lru] REDIS_LRU_BITS; 
 int refcount; 
 void *ptr; 
} robj; 

簡(jiǎn)單介紹一下這幾個(gè)字段：

• type：數(shù)據(jù)類型，就是我們熟悉的string、hash、list等。
• encoding：內(nèi)部編碼，其實(shí)就是本文要介紹的數(shù)據(jù)結(jié)構(gòu)。指的是當(dāng)前這個(gè)value底層是用的什么數(shù)據(jù)結(jié)構(gòu)。因?yàn)橥粋€(gè)數(shù)據(jù)類型底層也有多種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，所以這里需要指定數(shù)據(jù)結(jié)構(gòu)。
• REDIS_LRU_BITS：當(dāng)前對(duì)象可以保留的時(shí)長(zhǎng)。這個(gè)我們?cè)诤竺嬷v鍵的過(guò)期策略的時(shí)候講。
• refcount：對(duì)象引用計(jì)數(shù)，用于GC。
• ptr：指針，指向以encoding的方式實(shí)現(xiàn)這個(gè)對(duì)象的實(shí)際地址。

string

在Redis內(nèi)部，string類型有兩種底層儲(chǔ)存結(jié)構(gòu)。Redis會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)及用戶的操作指令自動(dòng)選擇合適的結(jié)構(gòu)：

• int：存放整數(shù)類型;
• SDS：存放浮點(diǎn)、字符串、字節(jié)類型;

SDS: 簡(jiǎn)單動(dòng)態(tài)字符串 simple dynamic string 

SDS

SDS的內(nèi)部數(shù)據(jù)結(jié)構(gòu)：

typedef struct sdshdr { 
 // buf中已經(jīng)占用的字符長(zhǎng)度 
 unsigned int len; 
 // buf中剩余可用的字符長(zhǎng)度 
 unsigned int free; 
 // 數(shù)據(jù)空間 
 char buf[]; 
} 

可見(jiàn)，其底層是一個(gè)char數(shù)組。buf最大容量為512M，里面可以放字符串、浮點(diǎn)數(shù)和字節(jié)。所以你甚至可以放一張序列化后的圖片。它為什么沒(méi)有直接使用數(shù)組，而是包裝成了這樣的數(shù)據(jù)結(jié)構(gòu)呢?

因?yàn)閎uf會(huì)有動(dòng)態(tài)擴(kuò)容和縮容的需求。如果直接使用數(shù)組，那每次對(duì)字符串的修改都會(huì)導(dǎo)致重新分配內(nèi)存，效率很低。

buf的擴(kuò)容過(guò)程如下：

• 如果修改后len長(zhǎng)度將小于1M,這時(shí)分配給free的大小和len一樣,例如修改過(guò)后為10字節(jié), 那么給free也是10字節(jié)，buf實(shí)際長(zhǎng)度變成了10 + 10 + 1 = 21byte
• 如果修改后len長(zhǎng)度將大于等于1M,這時(shí)分配給free的長(zhǎng)度為1M,例如修改過(guò)后為30M,那么給free是1M.buf實(shí)際長(zhǎng)度變成了30M + 1M + 1byte 

惰性空間釋放指的是當(dāng)字符串縮短時(shí)，并沒(méi)有真正的縮容，而是移動(dòng)free的指針。這樣將來(lái)字符串長(zhǎng)度增加時(shí)，就不用重新分配內(nèi)存了。但這樣會(huì)造成內(nèi)存浪費(fèi)，Redis提供了API來(lái)真正釋放內(nèi)存。

list

list底層有兩種數(shù)據(jù)結(jié)構(gòu)：鏈表linkedlist和壓縮列表ziplist。當(dāng)list元素個(gè)數(shù)少且元素內(nèi)容長(zhǎng)度不大時(shí)，使用ziplist實(shí)現(xiàn)，否則使用linkedlist。

鏈表

Redis使用的鏈表是雙向鏈表。為了方便操作，使用了一個(gè)list結(jié)構(gòu)來(lái)持有這個(gè)鏈表。如圖所示：

typedef struct list{ 
 //表頭節(jié)點(diǎn) 
 listNode *head; 
 //表尾節(jié)點(diǎn) 
 listNode *tail; 
 //鏈表所包含的節(jié)點(diǎn)數(shù)量 
 unsigned long len; 
 //節(jié)點(diǎn)值復(fù)制函數(shù) 
 void *(*dup)(void *ptr); 
 //節(jié)點(diǎn)值釋放函數(shù) 
 void *(*free)(void *ptr); 
 //節(jié)點(diǎn)值對(duì)比函數(shù) 
 int (*match)(void *ptr,void *key); 
}list; 

data存的其實(shí)也是一個(gè)指針。鏈表里面的元素是上面介紹的string。因?yàn)槭请p向鏈表，所以可以很方便地把它當(dāng)成一個(gè)?；蛘哧?duì)列來(lái)使用。

壓縮列表

與上面的鏈表相對(duì)應(yīng)，壓縮列表有點(diǎn)兒類似數(shù)組，通過(guò)一片連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)數(shù)據(jù)。不過(guò)，它跟數(shù)組不同的一點(diǎn)是，它允許存儲(chǔ)的數(shù)據(jù)大小不同。每個(gè)節(jié)點(diǎn)上增加一個(gè)length屬性來(lái)記錄這個(gè)節(jié)點(diǎn)的長(zhǎng)度，這樣比較方便地得到下一個(gè)節(jié)點(diǎn)的位置。

上圖的各字段含義為：

• zlbytes：列表的總長(zhǎng)度
• zltail：指向最末元素
• zllen：元素的個(gè)數(shù)
• entry：元素的內(nèi)容，里面記錄了前一個(gè)Entry的長(zhǎng)度，用于方便雙向遍歷
• zlend：恒為0xFF，作為ziplist的定界符

壓縮列表不只是list的底層實(shí)現(xiàn)，也是hash的底層實(shí)現(xiàn)之一。當(dāng)hash的元素個(gè)數(shù)少且內(nèi)容長(zhǎng)度不大時(shí)，使用壓縮列表來(lái)實(shí)現(xiàn)。

hash

hash底層有兩種實(shí)現(xiàn)：壓縮列表和字典(dict)。壓縮列表剛剛上面已經(jīng)介紹過(guò)了，下面主要介紹一下字典的數(shù)據(jù)結(jié)構(gòu)。

字典

字典其實(shí)就類似于Java語(yǔ)言中的Map,Python語(yǔ)言中的dict。與Java中的HashMap類似，Redis底層也是使用的散列表作為字典的實(shí)現(xiàn)，解決hash沖突使用的是鏈表法。Redis同樣使用了一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)持有這個(gè)散列表：

在鍵增加或減少時(shí)，會(huì)擴(kuò)容或縮容，并且進(jìn)行rehash，根據(jù)hash值重新計(jì)算索引值。那如果這個(gè)字典太大了怎么辦呢?

為了解決一次性擴(kuò)容耗時(shí)過(guò)多的情況，可以將擴(kuò)容操作穿插在插入操作的過(guò)程中，分批完成。當(dāng)負(fù)載因子觸達(dá)閾值之后，只申請(qǐng)新空間，但并不將老的數(shù)據(jù)搬移到新散列表中。當(dāng)有新數(shù)據(jù)要插入時(shí)，將新數(shù)據(jù)插入新散列表中，并且從老的散列表中拿出一個(gè)數(shù)據(jù)放入到新散列表。每次插入一個(gè)數(shù)據(jù)到散列表，都重復(fù)上面的過(guò)程。經(jīng)過(guò)多次插入操作之后，老的散列表中的數(shù)據(jù)就一點(diǎn)一點(diǎn)全部搬移到新散列表中了。這樣沒(méi)有了集中的一次一次性數(shù)據(jù)搬移，插入操作就都變得很快了。這個(gè)過(guò)程也被稱為漸進(jìn)式rehash。

set

set里面沒(méi)有重復(fù)的集合。set的實(shí)現(xiàn)比較簡(jiǎn)單。如果是整數(shù)類型，就直接使用整數(shù)集合intset。使用二分查找來(lái)輔助，速度還是挺快的。不過(guò)在插入的時(shí)候，由于要移動(dòng)元素，時(shí)間復(fù)雜度是O(N)。

如果不是整數(shù)類型，就使用上面在hash那一節(jié)介紹的字典。key為set的值，value為空。

zset

zset是可排序的set。與hash的實(shí)現(xiàn)方式類似，如果元素個(gè)數(shù)不多且不大，就使用壓縮列表ziplist來(lái)存儲(chǔ)。不過(guò)由于zset包含了score的排序信息，所以在ziplist內(nèi)部，是按照score排序遞增來(lái)存儲(chǔ)的。意味著每次插入數(shù)據(jù)都要移動(dòng)之后的數(shù)據(jù)。

跳表

跳表(skiplist)是另一種實(shí)現(xiàn)dict的數(shù)據(jù)結(jié)構(gòu)。跳表是對(duì)鏈表的一個(gè)增強(qiáng)。我們?cè)谑褂面湵淼臅r(shí)候，即使元素的有序排列的，但如果要查找一個(gè)元素，也需要從頭一個(gè)個(gè)查找下去，時(shí)間復(fù)雜度是O(N)。而跳表顧名思義，就是跳躍了一些元素，可以抽象多層。

如下圖所示，比如我們要查找8，先在最上層L2查找，發(fā)現(xiàn)在1和9之間;然后去L1層查找，發(fā)現(xiàn)在5和9之間;然后去L0查找，發(fā)現(xiàn)在7和9之間，然后找到8。

當(dāng)元素比較多時(shí)，使用跳表可以顯著減少查找的次數(shù)。

同list類似，Redis內(nèi)部也不是直接使用的跳表，而是使用了一個(gè)自定義的數(shù)據(jù)結(jié)構(gòu)來(lái)持有跳表。下圖左邊藍(lán)色部分是skiplist，右邊是4個(gè)zskiplistNode。zskiplistNode內(nèi)部有很多層L1、L2等，指針指向這一層的下一個(gè)結(jié)點(diǎn)。BW是回退指針(backward)，用于查找的時(shí)候回退。然后下面是score和對(duì)象本身object。

總結(jié)

Redis對(duì)外暴露的是對(duì)象(數(shù)據(jù)類型)，而每個(gè)對(duì)象都是用一個(gè)redisObject持有，通過(guò)不同的編碼，映射到不同的數(shù)據(jù)結(jié)構(gòu)。從最開(kāi)始的那個(gè)圖可以知道，有時(shí)候不同對(duì)象可能會(huì)底層使用同一種數(shù)據(jù)結(jié)構(gòu)，比如壓縮列表和字典等。

在了解數(shù)據(jù)結(jié)構(gòu)后，我們就能夠更清楚應(yīng)該選用什么樣的對(duì)象，出現(xiàn)問(wèn)題時(shí)應(yīng)該如何優(yōu)化了。