Redis底层数据结构详解

typedef struct redisDb {
    dict *dict;                 
    dict *expires;              
    dict *blocking_keys;        
    dict *ready_keys;           
    dict *watched_keys;         
    int id;                     
    long long avg_ttl;          
    unsigned long expires_cursor; 
    list *defrag_later;         
} redisDb;

typedef struct redisObject {
    unsigned type:4; //类型 对象类型
    unsigned encoding:4;//编码
	// LRU_BITS为24bit 记录最后一次被命令程序访问的时间
    unsigned lru:LRU_BITS; 
    int refcount; //引用计数
    void *ptr;//指向底层实现数据结构的指针
} 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"

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; 
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; 
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

typedef struct zskiplistNode {
    
    sds ele;
    
    double score;
    
    struct zskiplistNode *backward;
    
    struct zskidictEntryplistLevel {
        struct zskiplistNode *forward; //指向本层下一个节点
        unsigned long span; //本层下个节点到本节点的元素个数
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    //表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;
} zskiplist;

typedef struct dictht {
    dictEntry **table; // 哈希表数组
    unsigned long size; // 哈希表数组的大小
    unsigned long sizemask; // 用于映射位置的掩码，值永远等于(size-1)
    unsigned long used; // 哈希表已有节点的数量,包含next单链表数据
} dictht;

typedef struct dictEntry {
    void *key; // 键
    union { // 值v的类型可以是以下4种类型
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下一个哈希表节点，形成单向链表 解决hash冲突, 单链表中会存储key和value
} dictEntry;

typedef struct dict {
    dictType *type; //该字典对应的特定操作函数
    void *privdata; //上述类型函数对应的可选参数
    dictht ht[2];
    long rehashidx; 
    unsigned long iterators; 
} dict;

typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*hashFunction)(const void *key);

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);

    // 比较键的函数
    void *(*valDup)(void *privdata, const void *obj);

    // 比较键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);

    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

struct ziplist<T>{
    unsigned int zlbytes; // ziplist的长度字节数，包含头部、所有entry和zipend。
    unsigned int zloffset; // 从ziplist的头指针到指向最后一个entry的偏移量，用于快速反向查询
    unsigned short int zllength; // entry元素个数T[] entry; // 元素值
    unsigned char zlend; // ziplist结束符，值固定为0xFF
}
typedef struct zlentry {
    unsigned int prevrawlensize; //previous_entry_length字段的长度
    unsigned int prevrawlen; //previous_entry_length字段存储的内容
    unsigned int lensize; //encoding字段的长度
    unsigned int len; //数据内容长度
    unsigned int headersize; //当前元素的首部长度，即previous_entry_length字段长度与 encoding字段长度之和。
    unsigned char encoding; //数据类型
    unsigned char *p; //当前元素首地址
} 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;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    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

#   define QL_FILL_BITS 14
#   define QL_COMP_BITS 14
#   define QL_BM_BITS 4
#elif UINTPTR_MAX == 0xffffffffffffffff

#   define QL_FILL_BITS 16
#   define QL_COMP_BITS 16
#   define QL_BM_BITS 4 
#else
#   error unknown arch bits count
#endif


typedef struct quicklist {
    quicklistNode *head; // 指向quicklist的头部
    quicklistNode *tail; // 指向quicklist的尾部
    unsigned long count;        
    unsigned long len;          
    int fill : QL_FILL_BITS;              
    unsigned int compress : QL_COMP_BITS; 
    unsigned int bookmark_count: QL_BM_BITS; 
    quicklistBookmark bookmarks[]; 
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev; // 指向上一个ziplist节点
    struct quicklistNode *next; // 指向下一个ziplist节点
    unsigned char *zl; // 数据指针，如果没有被压缩，就指向ziplist结构，反之指向 quicklistLZF结构
    unsigned int sz; // 表示指向ziplist结构的总长度(内存占用长度)
    unsigned int count : 16; // 表示ziplist中的数据项个数
    unsigned int encoding : 2; // 编码方式，1--ziplist，2--quicklistLZF
    unsigned int container : 2; // 预留字段，存放数据的方式，1--NONE，2--ziplist
    unsigned int recompress : 1; // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为 1，之后再重新进行压缩
    unsigned int attempted_compress : 1; // 测试相关
    unsigned int extra : 10; // 扩展字段，暂时没用
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; 
    char compressed[]; //柔性数组，指向数据部分
} quicklistLZF;

#define OBJ_ENCODING_RAW 0     
#define OBJ_ENCODING_INT 1     
#define OBJ_ENCODING_HT 2      
#define OBJ_ENCODING_ZIPMAP 3  
#define OBJ_ENCODING_LINKEDLIST 4 
#define OBJ_ENCODING_ZIPLIST 5 
#define OBJ_ENCODING_INTSET 6  
#define OBJ_ENCODING_SKIPLIST 7  
#define OBJ_ENCODING_EMBSTR 8  
#define OBJ_ENCODING_QUICKLIST 9 
#define OBJ_ENCODING_STREAM 10 

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"