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

[[275524]]

redisObject

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

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

簡單介紹一下這幾個字段：

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

string

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

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

SDS: 簡單動態(tài)字符串 simple dynamic string 

SDS

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

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

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

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

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

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

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

list

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

鏈表

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

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

data存的其實也是一個指針。鏈表里面的元素是上面介紹的string。因為是雙向鏈表，所以可以很方便地把它當(dāng)成一個?；蛘哧犃衼硎褂?。

壓縮列表

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

上圖的各字段含義為：

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

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

hash

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

字典

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

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

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

set

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

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

zset

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

跳表

跳表(skiplist)是另一種實現(xiàn)dict的數(shù)據(jù)結(jié)構(gòu)。跳表是對鏈表的一個增強(qiáng)。我們在使用鏈表的時候，即使元素的有序排列的，但如果要查找一個元素，也需要從頭一個個查找下去，時間復(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ù)。

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

總結(jié)

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

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