重學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<<5unsigned char flags; char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {     // 對應的字符串長度小于 1<<8uint8_t len; /* used */                       // 目前字符創的長度,使用1個byteuint8_t alloc;                                // 已經分配的總長度,使用1個byteunsigned char flags;                          // flag用3bit來標明類型，類型后續解釋，其余5bit目前沒有使用。使用1byte。char buf[];                                   // 柔性數組，以'\0'結尾
};
struct __attribute__ ((__packed__)) sdshdr16 {    // 對應的字符串長度小于 1<<16uint16_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 __attribute__ ((__packed__)) sdshdr32 {    // 對應的字符串長度小于 1<<32uint32_t len; /* used,使用4byte */uint32_t alloc; /* excluding the header and null terminator,使用4byte */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {    // 對應的字符串長度小于 1<<64uint64_t len; /* used */uint64_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};

2，SDS的特點

二進制安全的數據結構，不會產生數據的丟失
內存預分配機制，避免了頻繁的內存分配。當字符串長度小于 1M 時，擴容都是加倍現有的空間，如果超過 1M，擴容時一次只會多擴 1M 的空間。(字符串最大長度為 512M)
兼容c語言函數庫

二、Redis中幾種數據結構

redisDb 默認情況下有16個，每個 redisDb 內部包含一個 dict 的數據結構，dict 內部包含 dictht 數組，數組個數為2，主要用于 hash 擴容使用。dictht 內部包含 dictEntry 的數組，dictEntry 其實就是 hash 表的一個 key-value 節點，如果沖突通過 [鏈地址法]解決

image

1，redisServer

數據結構 redisServer 是一個 redis 服務端的抽象，定義在server.h中。 redisServer中的屬性非常多，以下為節選的一部分，簡單介紹下

struct redisServer {/* General */pid_t pid;                  /* Main process pid. */    ......  int hz;                     /* serverCron() calls frequency in hertz */redisDb *db;dict *commands;             /* Command table */dict *orig_commands;        /* Command table before command renaming. */aeEventLoop *el; ...... char runid[CONFIG_RUN_ID_SIZE+1];  /* 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. */......
};

hz: redis** 定時任務觸發的頻率**
*db: redisDb 數組，默認 16 個 redisDb
*commands: redis 支持的命令的字典
*el: redis 事件循環實例
runid[CONFIG_RUN_ID_SIZE+1]: 當前 redis 實例的 runid

2，redisDb

redisDb 是 redis 數據庫的抽象，定義在 server.h 中，比較關鍵的屬性如下

typedef struct redisDb {dict *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;                     /* 數據庫ID */long long avg_ttl;          /* 鍵的平均過期時間 */
} redisDb;

3，dict

dict 是 redis 中的字典，定義在 dict.h 文件中，其主要的屬性如下

typedef struct dict {dictType *type;void *privdata;dictht ht[2]; //方便漸進的rehash擴容，dict的hashtablelong 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 是哈希表結構，定義在 dict.h 文件中，其重要的屬性如下

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 鍵值對節點，是實際存儲數據的節點**，定義在 dict.h 文件中，其重要的屬性如下

typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;
} dictEntry;

*key: 鍵對象，總是一個字符串類型的對象 SDS
*val: 值對象，可能是任意類型的對象。對應常見的5種數據類型：string,hash,list,set,zset
*next: 尾指針，指向下一個節點

三、數據類型

1，Redis數據對象結構

Redis 數據庫中所有數據都以 key-value 節點 dictEntry 存儲，其中 key 和 value 都是一個 redisObject 結構體對象，只不過 key 總是一個字符串類型的對象(SDS)，value 則可能是任意一種數據類型的對象。 redisObject 結構體定義在 server.h 中如下所示

typedef struct redisObject {unsigned type:4;       //占用4bitunsigned encoding:4;   //占用4bitunsigned 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;          //占用4bytevoid *ptr;             //占用8byte  總空間:4bit+4bit+24bit+4byte+8byte = 16byte
} robj;

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

type: 該屬性標明了數據對象的類型，比如 String，List 等
encoding: 這個屬性指明了對象底層的存儲結構，比如 ZSet 類型對象可能的存儲結構有 ZIPLIST 和 SKIPLIST
*ptr: 指向底層存儲結構的指針

2，Redis數據類型及存儲結構

Redis 中數據類型及其存儲結構定義在 server.h 文件中

/* 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中常用數據類型和結構

image

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。

image

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 中

image

d）redis.conf配置

通過設置每個ziplist的最大容量，quicklist的數據壓縮范圍，提升數據存取效率。

list-max-ziplist-size -2                    //單個ziplist節點最大能存儲8kb，超過則進行分裂，將數據存儲在新的ziplist節點中
list-compress-depth   0                     //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) ，但是無序，結合兩者可以實現優勢互補
集合的元素成員和分值是共享的，跳躍表和字典通過指針指向同一地址，不會浪費內存

image

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)個

image

b）OBJ_ENCODING_HT

底層為 dict 字典，哈希對象中的每個 key-value 對都使用一個字典鍵值對dictEntry來保存，字典的鍵和值都是字符串對象。

c）檢測

HMSET key f1 v1 f2 v2 f3 v3                 //在一個哈希表key中存儲多個鍵值對
OBJECT ENCODING key                         //查看key在redis中的存儲類型為ziplist
HGETALL key                                 //查看key對應的所有field和value發現為有序的
HSET key f4 x...x                           //在一個哈希表key中存儲一個長度超過64的value
HSTRLEN key f4                              //查看key中field為f4的長度
OBJECT ENCODING key                         //查看key在redis中的存儲類型為hashtable
HGETALL key                                 //查看key對應的所有field和value發現為無序

? 著作權歸作者所有,轉載或內容合作請聯系作者