Redis数据结构底层实现

内容均为个人学习后整理，如需转载请注明出处。

redis数据模型-自整理.png

adlist

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

quicklist(由ziplist构成)

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

dict

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

zskiplist

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward; 
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length; 
    int level;  
} zskiplist;

intset

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

五种对象类型：

127.0.0.1:6379> set msg "hello world"
OK
127.0.0.1:6379> type msg
string
127.0.0.1:6379> rpush numbers 1 3 5
(integer) 3
127.0.0.1:6379> type numbers
list
127.0.0.1:6379> hmset person name Sonya age 23 career Programmer
OK
127.0.0.1:6379> type person
hash
127.0.0.1:6379> sadd fruits apple banana cherry
(integer) 3
127.0.0.1:6379> type fruits
set
127.0.0.1:6379> zadd price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
127.0.0.1:6379> type price
zset

编码类型：

127.0.0.1:6379> set msg "hello world"
OK
127.0.0.1:6379> object encoding msg
"embstr"
127.0.0.1:6379> set story "long long long long long long long long ago..."
OK
127.0.0.1:6379> object encoding story
"raw"
127.0.0.1:6379> sadd numberSet 1 2 3
(integer) 3
127.0.0.1:6379> object encoding numberSet
"intset"
127.0.0.1:6379> sadd numberSet "Sonya"
(integer) 1
127.0.0.1:6379> object encoding numberSet
"hashtable"

字符串对象编码、编码转换

127.0.0.1:6379> set number 123
OK
127.0.0.1:6379> object encoding number
"int"
127.0.0.1:6379> incr number
(integer) 124
127.0.0.1:6379> object encoding number
"int"
127.0.0.1:6379> set pi 3.14
OK
127.0.0.1:6379> object encoding pi
"embstr"
127.0.0.1:6379> INCRBYFLOAT pi 1.0
"4.14"
127.0.0.1:6379> object encoding pi
"embstr"
127.0.0.1:6379> append number ", wooden boy"
(integer) 15
127.0.0.1:6379> object encoding number
"raw"
127.0.0.1:6379> append pi " is a float"
(integer) 15
127.0.0.1:6379> object encoding pi
"raw"
127.0.0.1:6379> set msg "hello world"
OK
127.0.0.1:6379> object encoding msg
"embstr"
127.0.0.1:6379> append msg ", redis"
(integer) 18
127.0.0.1:6379> object encoding msg
"raw"

列表对象

127.0.0.1:6379> rpush sayHi hello world redis
(integer) 3
127.0.0.1:6379> object encoding sayHi
"quicklist"

quicklist结构是在redis 3.2版本中新加的数据结构，用在列表的底层实现。

quicklist是由ziplist组成的双向链表，链表中的每一个节点都以压缩列表ziplist的结构保存着数据，而ziplist有多个entry节点，保存着数据。相当与一个quicklist节点保存的是一片数据，而不再是一个数据。

哈希对象

127.0.0.1:6379> hset booki name "Redis Design"
(integer) 1
127.0.0.1:6379> object encoding booki
"ziplist"
127.0.0.1:6379> hset booki description RedisLongLongLongLongLongLongLongLongLongLongLongLongLongDescription
(integer) 1
127.0.0.1:6379> object encoding booki
"hashtable"

集合对象

127.0.0.1:6379> sadd numberset 1 2 3
(integer) 3
127.0.0.1:6379> object encoding numberset
"intset"
127.0.0.1:6379> sadd numberset "str"
(integer) 1
127.0.0.1:6379> object encoding numberset
"hashtable"
127.0.0.1:6379> 
127.0.0.1:6379> 
127.0.0.1:6379> EVAL "for i=1, 512 do redis.call('SADD',KEYS[1], i) end" 1 integers
(nil)
127.0.0.1:6379> scard integers
(integer) 512
127.0.0.1:6379> object encoding integers
"intset"
127.0.0.1:6379> sadd integers 513
(integer) 1
127.0.0.1:6379> object encoding integers
"hashtable"

有序集合对象

127.0.0.1:6379> EVAL "for i=1, 128 do redis.call('ZADD', KEYS[1], i, i) end" 1 datas
(nil)
127.0.0.1:6379> object encoding datas
"ziplist"
127.0.0.1:6379> zcard datas
(integer) 128
127.0.0.1:6379> zadd datas 3.14 pi
(integer) 1
127.0.0.1:6379> zcard datas
(integer) 129
127.0.0.1:6379> object encoding datas
"skiplist"
127.0.0.1:6379>
127.0.0.1:6379>
127.0.0.1:6379>
127.0.0.1:6379> zadd objs 1.0 www
(integer) 1
127.0.0.1:6379> object encoding objs
"ziplist"
127.0.0.1:6379> zadd objs 2.0 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
(integer) 1
127.0.0.1:6379> object encoding objs

学习内容来源: 《Redis设计与实现》