重學Redis：Redis常用資料型別+儲存結構（原始碼篇）

一、SDS

1，SDS原始碼解讀

sds （Simple Dynamic String），

Simple

的意思是簡單，

Dynamic

即動態，意味著其具有動態增加空間的能力，擴容不需要使用者關心。

String

是字串的意思。說白了

就是用C語言自己封裝了一個字串型別

，這個專案由Redis作者

antirez

建立，作為Redis中基本的資料結構之一，現在也被獨立出來成為了一個單獨的專案。

sds 有兩個版本，在

Redis 3。2

之前使用的是第一個版本，其資料結構如下所示：

typedef

char

sds

；

//注意，sds其實不是一個結構體型別，而是被typedef的char*

struct

sdshdr

{

unsigned

int

len

；

//buf中已經使用的長度

unsigned

int

free

；

//buf中未使用的長度

char

buf

［］；

//柔性陣列buf

}；

但是在

Redis 3。2 版本

中，對資料結構做出了修改，針對不同的長度範圍定義了不同的結構，如下，這是目前的結構：

typedef

char

sds

；

struct

__attribute__

（（

__packed__

））

sdshdr5

{

// 對應的字串長度小於 1<<5

unsigned

char

flags

；

char

buf

［］；

}；

struct

（（

__packed__

））

sdshdr8

{

// 對應的字串長度小於 1<<8

uint8_t

len

；

/* used */

// 目前字元創的長度，使用1個byte

uint8_t

alloc

；

// 已經分配的總長度，使用1個byte

unsigned

char

flags

；

// flag用3bit來標明型別，型別後續解釋，其餘5bit目前沒有使用。使用1byte。

char

buf

［］；

// 柔性陣列，以‘\0’結尾

}；

struct

（（

__packed__

））

sdshdr16

{

// 對應的字串長度小於 1<<16

uint16_t

len

；

/* used，使用2byte */

uint16_t

alloc

；

/* excluding the header and null terminator，使用2byte */

unsigned

char

flags

；

/* 3 lsb of type， 5 unused bits */

char

buf

［］；

}；

struct

（（

__packed__

））

sdshdr32

{

// 對應的字串長度小於 1<<32

uint32_t

len

；

/* used，使用4byte */

uint32_t

alloc

；

/* excluding the header and null terminator，使用4byte */

unsigned

char

flags

；

char

buf

［］；

}；

struct

（（

__packed__

））

sdshdr64

{

// 對應的字串長度小於 1<<64

uint64_t

len

；

/* used */

uint64_t

alloc

；

/* excluding the header and null terminator */

unsigned

char

flags

；

char

buf

［］；

}；

2，SDS的特點

二進位制安全的資料結構，不會產生資料的丟失

記憶體預分配機制，避免了頻繁的記憶體分配。當字串長度

小於 1M 時，擴容都是加倍

現有的空間，如果

超過 1M，擴容

時一次只會

多擴 1M

的空間。（字串最大長度為 512M）

相容c語言函式庫

二、Redis中幾種資料結構

redisDb 預設情況下有16個，每個 redisDb 內部包含一個 dict 的資料結構，dict 內部包含 dictht 陣列，陣列個數為2，主要用於 hash 擴容使用。dictht 內部包含 dictEntry 的陣列，dictEntry 其實就是 hash 表的一個 key-value 節點，如果衝突透過［鏈地址法］解決

1，redisServer

資料結構

redisServer

是一個 redis 服務端的抽象，定義在

server。h

中。

中的屬性非常多，以下為節選的一部分，簡單介紹下

struct

redisServer

{

/* General */

pid_t

pid

；

/* Main process pid。 */

……

int

；

/* serverCron（） calls frequency in hertz */

redisDb

；

dict

commands

；

/* Command table */

dict

orig_commands

；

/* Command table before command renaming。 */

aeEventLoop

；

……

char

runid

［

CONFIG_RUN_ID_SIZE

］；

/* ID always different at every exec。 */

……

list

clients

；

/* List of active clients */

list

clients_to_close

；

/* Clients to close asynchronously */

list

clients_pending_write

；

/* There is to write or install handler。 */

list

clients_pending_read

；

/* Client has pending read socket buffers。 */

list

slaves

，

monitors

；

/* List of slaves and MONITORs */

client

current_client

；

/* Current client executing the command。 */

……

}；

： redis** 定時任務觸發的頻率**

*db

： redisDb 陣列，預設 16 個 redisDb

*commands

： redis 支援的命令的字典

*el

： redis 事件迴圈例項

runid［CONFIG_RUN_ID_SIZE+1］

：當前 redis 例項的 runid

2，redisDb

redisDb

是 redis 資料庫的抽象，定義在

中，比較關鍵的屬性如下

typedef

struct

redisDb

{

dict

；

/* 鍵值對字典，儲存資料庫中所有的鍵值對 */

dict

expires

；

/* 過期字典，儲存著設定過期的鍵和鍵的過期時間*/

dict

blocking_keys

；

/*儲存著所有造成客戶端阻塞的鍵和被阻塞的客戶端（BLPOP） */

dict

ready_keys

；

/* 儲存著處於阻塞狀態的鍵，value為NULL*/

dict

watched_keys

；

/* 事物模組，用於儲存被WATCH命令所監控的鍵 */

// 當記憶體不足時，Redis會根據LRU演算法回收一部分鍵所佔的空間，而該eviction_pool是一個長為16陣列，儲存可能被回收的鍵

// eviction_pool中所有鍵按照idle空轉時間，從小到大排序，每次回收空轉時間最長的鍵

struct

evictionPoolEntry

eviction_pool

；

/* Eviction pool of keys */

int

；

/* 資料庫ID */

long

avg_ttl

；

/* 鍵的平均過期時間 */

}

redisDb

；

3，dict

dict

是 redis 中的字典，定義在

dict。h

檔案中，其主要的屬性如下

typedef

struct

dict

{

dictType

type

；

void

privdata

；

dictht

［

］；

//方便漸進的rehash擴容，dict的hashtable

long

rehashidx

；

/* rehashing not in progress if rehashidx == -1 */

unsigned

long

iterators

；

/* number of iterators currently running */

}

dict

；

ht［2］

：雜湊表陣列，為了擴容方便有 2 個元素，其中

一個雜湊表正常儲存資料

，

另一個雜湊表為空，空雜湊表在 rehash 時使用

rehashidx

：rehash 索引，當不在進行 rehash 時，值為 -1

4，dictht

dictht

是雜湊表結構，定義在

檔案中，其重要的屬性如下

typedef

struct

dictht

{

dictEntry

table

；

unsigned

long

size

；

unsigned

long

sizemask

；

unsigned

long

used

；

}

dictht

；

**table

：

key-value 鍵值對

節點陣列，類似 Java 中的 HashMap 底層陣列

size

：雜湊表容量大小

sizemask

：總是等於 size - 1，用於計算索引值

used

：雜湊表實際儲存的 dictEntry 數量

5，dictEntry

dictEntry

是 redis 中的** key-value 鍵值對節點，是實際儲存資料的節點**，定義在

typedef

struct

dictEntry

{

void

key

；

union

{

void

val

；

uint64_t

u64

；

int64_t

s64

；

double

；

}

；

struct

dictEntry

；

}

dictEntry

；

*key

：

鍵物件

，總是一個字串型別的物件 SDS

*val

：

值物件

，可能是任意型別的物件。對應常見的5種資料型別：string，hash，list，set，zset

*next

：

尾指標

，指向下一個節點

三、資料型別

1，Redis資料物件結構

Redis 資料庫中所有資料都以 key-value 節點 dictEntry 儲存，其中 key 和 value 都是一個

redisObject

結構體物件，只不過 key 總是一個字串型別的物件（SDS），value 則可能是任意一種資料型別的物件。

結構體定義在

中如下所示

typedef

struct

redisObject

{

unsigned

type

：

；

//佔用4bit

unsigned

encoding

：

；

//佔用4bit

unsigned

lru

：

LRU_BITS

；

/*佔用24bit LRU time （relative to global lru_clock） or

* LFU data （least significant 8 bits frequency

* and most significant 16 bits access time）。 */

int

refcount

；

//佔用4byte

void

ptr

；

//佔用8byte 總空間：4bit+4bit+24bit+4byte+8byte = 16byte

}

robj

；

可以看到該結構體中重要的屬性如下，不同的物件具有不同的型別 type，同一個型別的 type 會有不同的儲存形式 encoding

type

：該屬性標明瞭

資料物件的型別

，比如 String，List 等

encoding

：這個屬性指明瞭

物件底層的儲存結構

，比如 ZSet 型別物件可能的儲存結構有 ZIPLIST 和 SKIPLIST

*ptr

：指向

底層儲存結構的指標

2，Redis資料型別及儲存結構

Redis 中資料型別及其儲存結構定義在

檔案中

/* The actual Redis Object */

#define OBJ_STRING 0

/* String object。 */

#define OBJ_LIST 1

/* List object。 */

#define OBJ_SET 2

/* Set object。 */

#define OBJ_ZSET 3

/* Sorted set object。 */

#define OBJ_HASH 4

/* Hash object。 */

#define OBJ_MODULE 5

/* Module object。 */

#define OBJ_STREAM 6

/* Stream object。 */

#define OBJ_ENCODING_RAW 0

/* Raw representation */

#define OBJ_ENCODING_INT 1

/* Encoded as integer */

#define OBJ_ENCODING_HT 2

/* Encoded as hash table */

#define OBJ_ENCODING_ZIPMAP 3

/* Encoded as zipmap */

#define OBJ_ENCODING_LINKEDLIST 4

/* No longer used： old list encoding。 */

#define OBJ_ENCODING_ZIPLIST 5

/* Encoded as ziplist */

#define OBJ_ENCODING_INTSET 6

/* Encoded as intset */

#define OBJ_ENCODING_SKIPLIST 7

/* Encoded as skiplist */

#define OBJ_ENCODING_EMBSTR 8

/* Embedded sds string encoding */

#define OBJ_ENCODING_QUICKLIST 9

/* Encoded as linked list of ziplists */

#define OBJ_ENCODING_STREAM 10

/* Encoded as a radix tree of listpacks */

四、Redis中常用資料型別和結構

1，字串物件String

OBJ_STRING

字串物件底層資料結構一般為簡單動態字串（SDS），但其儲存方式可以是

OBJ_ENCODING_INT

、

OBJ_ENCODING_EMBSTR

和

OBJ_ENCODING_RAW

，不同的儲存方式代表著物件記憶體結構的不同。

a）OBJ_ENCODING_INT

如果儲存的字串長度小於 20 並且可以解析為

整數

（值範圍為：-2^63 ~ 2^63-1），那麼這個整數就會直接儲存在

redisObject

的

ptr

屬性裡

b）OBJ_ENCODING_EMBSTR

長度小於 44

（OBJ_ENCODING_EMBSTR_SIZE_LIMIT）的字串將以簡單動態字串（SDS）的形式儲存，但是

會使用 malloc 方法一次分配記憶體

，將 redisObject 物件頭和 SDS 物件連續存在一起。因為預設分配空間為64byte，而其中value為string型別採用sdshdr8中len、alloc、flags各佔用1byte，buf以‘\0’佔用1byte，redisObject佔用16位元組，剩餘buff可使用為64-4-16=44byte。

c）OBJ_ENCODING_RAW

字串將以簡單動態字串（SDS）的形式儲存，需要

兩次 malloc 分配記憶體

，redisObject 物件頭和 SDS 物件在記憶體地址上一般是不連續的

d）檢測

#string型別檢視redis的儲存

SET

key

value

//存入字串鍵值對

STRLEN

key

//檢視key的長度（佔用的byte位元組）

OBJECT

ENCODING

key

//檢視key在redis中的儲存型別

SETRANGE

key

offset

value

//修改key從offset（字元偏移量）字元修改為value，如果原本為embstr修改後也會變成raw。

GETRANGE

key

start

end

//獲取key的部分值

2，列表物件list

OBJ_LIST

列表物件的底層儲存結構有過 3 種實現，分別是

OBJ_ENCODING_LINKEDLIST

、

OBJ_ENCODING_ZIPLIST

和

OBJ_ENCODING_QUICKLIST

，其中 OBJ_ENCODING_LINKEDLIST 在 3。2 版本以後就廢棄了。使用命令：OBJECT ENCODING key 檢視儲存型別。

a）OBJ_ENCODING_LINKEDLIST

底層採用雙端連結串列實現，每個連結串列節點都儲存了一個字串物件，在每個字串物件內儲存了一個元素。

b）OBJ_ENCODING_ZIPLIST

底層實現類似陣列，使用特點屬性儲存整個列表的元資訊，如整個列表佔用的記憶體大小，列表儲存的資料開始的位置，列表儲存的資料的個數等，其儲存的資料被封裝在

zlentry。

zlbytes：記錄

整個壓縮列表佔用的記憶體位元組數

。uint_32_t，4byte。

zltail：記錄壓縮列表

表尾節點距離起始地址有多少位元組

，透過這個偏移量，程式無需遍歷整個壓縮列表就能確定

表尾節點地址

。uint_32_t，4byte。

zlen：記錄壓縮列表包含的

節點數量

。uint_16_t，2byte。

entryX：

壓縮列表的各個節點

，節點長度由儲存的內容決定。

zlend：特殊值（

0xFFF

），用於

標記壓縮列表末端

。uint_8_t，1byte。

prerawlen：表示當前節點的前一個節點長度

len：當前節點的長度

data：當前節點的資料

c）OBJ_ENCODING_QUICKLIST

底層採用

雙端連結串列結構

，不過每個連結串列節點都儲存一個 ziplist，資料儲存在 ziplist 中

d）redis。conf配置

透過

設定每個ziplist的最大容量

，quicklist的資料壓縮範圍，提升資料存取效率。

list

max

ziplist

size

//單個ziplist節點最大能儲存8kb，超過則進行分裂，將資料儲存在新的ziplist節點中

list

compress

depth

//0代表所有節點，都不進行壓縮。1，代表從頭節點往後走一個，尾部節點往前走一個不用壓縮，其他的全部壓縮。

3，集合物件Set

OBJ_SET`集合物件的底層儲存結構有兩種，`OBJ_ENCODING_HT`和`OBJ_ENCODING_INTSET

a）OBJ_ENCODING_INTSET

typedef

struct

intset

{

uint32_t

encoding

；

//編碼型別

uint32_t

length

；

//元素個數

int8_t

contents

［］；

//元素資料

}

intset

；

//redis中儲存整型的編碼型別有int16_t，int32_t，int64_t

#define INTSET_ENC_INT16（sizeof（int16_t））

#define INTSET_ENC_INT32（sizeof（int32_t））

#define INTSET_ENC_INT64（sizeof（int64_t））

集合儲存的

所有元素都是整數值將會採用這種儲存結構

，但①當集合物件儲存的

元素數量超過512

（由server。set_max_intset_entries 配置）或者②

元素無法用整型表示

後會轉化為 OBJ_ENCODING_HT

b）OBJ_ENCODING_HT

底層為

dict字典

，資料作為字典的鍵儲存，鍵對應的值都是NULL，與 Java 中的 HashSet 類似

4，有序集合ZSet

OBJ_ZSET` 有序集合物件的儲存結構分為 `OBJ_ENCODING_SKIPLIST` 和 `OBJ_ENCODING_ZIPLIST

a）OBJ_ENCODING_ZIPLIST

當 ziplist 作為 zset 的底層儲存結構時，每個集合元素使用兩個緊挨在一起的壓縮列表節點來儲存，第一個節點儲存元素值，第二個元素儲存元素的分值，而且分值小的靠近表頭，大的靠近表尾

有序集合物件使用 ziplist 儲存需要同時滿足以下兩個條件，不滿足任意一條件將使用 skiplist

所有元素長度小於64 （server。zset_max_ziplist_value 配置）位元組

元素個數小於128 （server。zset-max-ziplist-entries 配置）

b）OBJ_ENCODING_SKIPLIST

底層實現是跳躍表結合字典。每個

跳躍表節點都儲存一個集合元素

，並按分值從小到大排列，節點的 object 屬性儲存了元素的值，score屬性儲存分值；字典的每個鍵值對儲存一個集合元素，元素值包裝為字典的鍵，元素分值儲存為字典的值。

skiplist 同時使用跳躍表和字典實現的原因：

跳躍表優點是有序

，但是查詢分值時複雜度為O（logn）；

字典查詢分值

（zscore命令）複雜度為O（1），但是

無序

，結合兩者可以實現優勢互補

集合的元素成員和分值是共享的，

跳躍表和字典透過指標指向同一地址

，不會浪費記憶體

5，雜湊物件Hash

OBJ_HASH

的儲存結構分為

OBJ_ENCODING_ZIPLIST

和

OBJ_ENCODING_HT（使用命令：OBJECT ENCODING key 檢視儲存型別）

，其實現如下：

a）OBJ_ENCODING_ZIPLIST

在以

ziplist

結構儲存資料的

雜湊物件

中，key-value 鍵值對以緊密相連的方式存入壓縮連結串列，先把

key放入表尾，再放入value

；鍵值對總是向表尾新增。

雜湊物件使用 ziplist 儲存資料需要同時滿足以下兩個條件，

不滿足任意一個都使用 dict 結構

所有鍵值對的鍵和值的

字串長度都小於64

（server。hash_max_ziplist_value 配置）位元組

鍵值對

數量小於512

（server。hash-max-ziplist-entries）個

b）OBJ_ENCODING_HT

底層為

dict

字典，雜湊物件中的每個 key-value 對都使用一個字典鍵值對

dictEntry

來儲存，字典的鍵和值都是字串物件。

c）檢測

HMSET

key

//在一個雜湊表key中儲存多個鍵值對

OBJECT

ENCODING

key

//檢視key在redis中的儲存型別為ziplist

HGETALL

key

//檢視key對應的所有field和value發現為有序的

HSET

key

。。。

//在一個雜湊表key中儲存一個長度超過64的value

HSTRLEN

key

//檢視key中field為f4的長度

OBJECT

ENCODING

key

//檢視key在redis中的儲存型別為hashtable

HGETALL

key

//檢視key對應的所有field和value發現為無序