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

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
    dict *dict;                 /* 存儲(chǔ)數(shù)據(jù)庫(kù)所有的key-value */
    dict *expires;              /* 存儲(chǔ)key的過(guò)期時(shí)間 */
    dict *blocking_keys;        /* blpop 存儲(chǔ)阻塞key和客戶端對(duì)象*/
    dict *ready_keys;           /* 阻塞后push 響應(yīng)阻塞客戶端 存儲(chǔ)阻塞后push的key和客戶端對(duì)象 */
    dict *watched_keys;         /* 存儲(chǔ)watch監(jiān)控的的key和客戶端對(duì)象 */
    int id;                     /* Database ID */
    long long avg_ttl;          /* 存儲(chǔ)的數(shù)據(jù)庫(kù)對(duì)象的平均ttl（time to live），用于統(tǒng)計(jì) */
    unsigned long expires_cursor; /* 循環(huán)過(guò)期檢查的光標(biāo). */
    list *defrag_later;         /* 需要嘗試去清理磁盤(pán)碎片的鏈表，會(huì)慢慢的清理 */
} redisDb;

typedef struct redisObject {
    unsigned type:4; //類(lèi)型 對(duì)象類(lèi)型
    unsigned encoding:4;//編碼
	// LRU_BITS為24bit 記錄最后一次被命令程序訪問(wèn)的時(shí)間
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount; //引用計(jì)數(shù)
    void *ptr;//指向底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針
} robj;

127.0.0.1:6379> set a1 111
OK
127.0.0.1:6379> type a1
string

127.0.0.1:6379> OBJECT encoding a1
"int"

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    /* 存儲(chǔ)字符串類(lèi)型數(shù)據(jù) redis3.0版本中使用robj類(lèi)型表示，但是在redis4.0.1中直接使用sds類(lèi)型表示 */
    sds ele;
    /*存儲(chǔ)排序的分值*/
    double score;
    /*后退指針，指向當(dāng)前節(jié)點(diǎn)最底層的前一個(gè)節(jié)點(diǎn)*/
    struct zskiplistNode *backward;
    /*層，柔性數(shù)組，隨機(jī)生成1-64的值*/
    struct zskidictEntryplistLevel {
        struct zskiplistNode *forward; //指向本層下一個(gè)節(jié)點(diǎn)
        unsigned long span; //本層下個(gè)節(jié)點(diǎn)到本節(jié)點(diǎn)的元素個(gè)數(shù)
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    //表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
    struct zskiplistNode *header, *tail;
    //表中節(jié)點(diǎn)的數(shù)量
    unsigned long length;
    //表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
    int level;
} zskiplist;

typedef struct dictht {
    dictEntry **table; // 哈希表數(shù)組
    unsigned long size; // 哈希表數(shù)組的大小
    unsigned long sizemask; // 用于映射位置的掩碼，值永遠(yuǎn)等于(size-1)
    unsigned long used; // 哈希表已有節(jié)點(diǎn)的數(shù)量,包含next單鏈表數(shù)據(jù)
} dictht;

typedef struct dictEntry {
    void *key; // 鍵
    union { // 值v的類(lèi)型可以是以下4種類(lèi)型
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下一個(gè)哈希表節(jié)點(diǎn)，形成單向鏈表 解決hash沖突, 單鏈表中會(huì)存儲(chǔ)key和value
} dictEntry;

typedef struct dict {
    dictType *type; //該字典對(duì)應(yīng)的特定操作函數(shù)
    void *privdata; //上述類(lèi)型函數(shù)對(duì)應(yīng)的可選參數(shù)
    dictht ht[2];/* 兩張哈希表，存儲(chǔ)鍵值對(duì)數(shù)據(jù)，ht[0]為原生哈希表，ht[1]為 rehash 哈希表 */
    long rehashidx; /* rehash標(biāo)識(shí) 當(dāng)?shù)扔?1時(shí)表示沒(méi)有在rehash，否則表示正在進(jìn)行rehash操作，
    				存儲(chǔ)的值表示hash表 ht[0]的rehash進(jìn)行到哪個(gè)索引值(數(shù)組下標(biāo))*/
    unsigned long iterators; /* 當(dāng)前運(yùn)行的迭代器數(shù)量 */
} dict;

typedef struct dictType {
    // 計(jì)算哈希值的函數(shù)
    uint64_t (*hashFunction)(const void *key);

    // 復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *privdata, const void *key);

    // 比較鍵的函數(shù)
    void *(*valDup)(void *privdata, const void *obj);

    // 比較鍵的函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 銷(xiāo)毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);

    // 銷(xiāo)毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

struct ziplistT>{
    unsigned int zlbytes; // ziplist的長(zhǎng)度字節(jié)數(shù)，包含頭部、所有entry和zipend。
    unsigned int zloffset; // 從ziplist的頭指針到指向最后一個(gè)entry的偏移量，用于快速反向查詢
    unsigned short int zllength; // entry元素個(gè)數(shù)T[] entry; // 元素值
    unsigned char zlend; // ziplist結(jié)束符，值固定為0xFF
}
typedef struct zlentry {
    unsigned int prevrawlensize; //previous_entry_length字段的長(zhǎng)度
    unsigned int prevrawlen; //previous_entry_length字段存儲(chǔ)的內(nèi)容
    unsigned int lensize; //encoding字段的長(zhǎng)度
    unsigned int len; //數(shù)據(jù)內(nèi)容長(zhǎng)度
    unsigned int headersize; //當(dāng)前元素的首部長(zhǎng)度，即previous_entry_length字段長(zhǎng)度與 encoding字段長(zhǎng)度之和。
    unsigned char encoding; //數(shù)據(jù)類(lèi)型
    unsigned char *p; //當(dāng)前元素首地址
} zlentry;

127.0.0.1:6379> SADD set:1 12  6  8
(integer) 3
127.0.0.1:6379> OBJECT encoding set:1
"intset"
127.0.0.1:6379> SADD set:2 1 1000000000000000000000000000000000000000000000000000000 99999999999999999999999999999
(integer) 3
127.0.0.1:6379> OBJECT encoding set:2
"hashtable"

typedef struct intset{
    //編碼方式
    uint32_t encoding;
    //集合包含的元素?cái)?shù)量
    uint32_t length;
    //保存元素的數(shù)組
    int8_t contents[];
}intset;

127.0.0.1:6379> LPUSH list:001  2 3 5 6 7
(integer) 5
127.0.0.1:6379> OBJECT encoding list:001
"quicklist"

#if UINTPTR_MAX == 0xffffffff
/* 32-bit */
#   define QL_FILL_BITS 14
#   define QL_COMP_BITS 14
#   define QL_BM_BITS 4
#elif UINTPTR_MAX == 0xffffffffffffffff
/* 64-bit */
#   define QL_FILL_BITS 16
#   define QL_COMP_BITS 16
#   define QL_BM_BITS 4 /* we can encode more, but we rather limit the user
                           since they cause performance degradation. */
#else
#   error unknown arch bits count
#endif

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: 0 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */
typedef struct quicklist {
    quicklistNode *head; // 指向quicklist的頭部
    quicklistNode *tail; // 指向quicklist的尾部
    unsigned long count;        /* 列表中所有數(shù)據(jù)項(xiàng)的個(gè)數(shù)總和 */
    unsigned long len;          /* quicklist節(jié)點(diǎn)的個(gè)數(shù)，即ziplist的個(gè)數(shù) */
    int fill : QL_FILL_BITS;              /* ziplist大小限定，由list-max-ziplist-size給定  (Redis設(shè)定)*/
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS; /*節(jié)點(diǎn)壓縮深度設(shè)置，由list-compress-depth給定*/
    quicklistBookmark bookmarks[]; /*可選新特性 使用realloc重新分配空間的時(shí)候會(huì)用到*/
} quicklist;

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually  32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporary decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev; // 指向上一個(gè)ziplist節(jié)點(diǎn)
    struct quicklistNode *next; // 指向下一個(gè)ziplist節(jié)點(diǎn)
    unsigned char *zl; // 數(shù)據(jù)指針，如果沒(méi)有被壓縮，就指向ziplist結(jié)構(gòu)，反之指向 quicklistLZF結(jié)構(gòu)
    unsigned int sz; // 表示指向ziplist結(jié)構(gòu)的總長(zhǎng)度(內(nèi)存占用長(zhǎng)度)
    unsigned int count : 16; // 表示ziplist中的數(shù)據(jù)項(xiàng)個(gè)數(shù)
    unsigned int encoding : 2; // 編碼方式，1--ziplist，2--quicklistLZF
    unsigned int container : 2; // 預(yù)留字段，存放數(shù)據(jù)的方式，1--NONE，2--ziplist
    unsigned int recompress : 1; // 解壓標(biāo)記，當(dāng)查看一個(gè)被壓縮的數(shù)據(jù)時(shí)，需要暫時(shí)解壓，標(biāo)記此參數(shù)為 1，之后再重新進(jìn)行壓縮
    unsigned int attempted_compress : 1; // 測(cè)試相關(guān)
    unsigned int extra : 10; // 擴(kuò)展字段，暫時(shí)沒(méi)用
} quicklistNode;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF壓縮后占用的字節(jié)數(shù)*/
    char compressed[]; //柔性數(shù)組，指向數(shù)據(jù)部分
} quicklistLZF;

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this 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 */

127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"
127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable"

127.0.0.1:6379> set n1 123
OK
127.0.0.1:6379> object encoding n1
"int"

127.0.0.1:6379> set name:001 zhangfei
OK
127.0.0.1:6379> object encoding name:001
"embstr"

127.0.0.1:6379> set address:001 asdasdasdasdasdasdsadasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdas
OK
127.0.0.1:6379> object encoding address:001
"raw"

127.0.0.1:6379> lpush list:001 1 2 5 4 3
(integer) 5
127.0.0.1:6379> object encoding list:001
"quicklist"

127.0.0.1:6379> hmset user:003 username111111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111111111111111 zhangfei password 111 num 2300000000000000000000000000000000000000000000000000
OK
127.0.0.1:6379> object encoding user:003
"hashtable"

127.0.0.1:6379> HSET user:001 username zhanyun password 123456
(integer) 2
127.0.0.1:6379> OBJECT encoding user:001
"ziplist"

127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"

127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable"

127.0.0.1:6379> zadd hit:1 100 item1 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:1
"ziplist"

127.0.0.1:6379> zadd hit:2 100 item1111111111111111111111111111111111111111111111111111111111111111111111111111 1111111111111111111111111111111111 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:2
"skiplist"