Redis底层数据结构详解

/* 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; /* 存储数据库所有的key-value */
dict *expires; /* 存储key的过期时间 */
dict *blocking_keys; /* blpop 存储阻塞key和客户端对象*/
dict *ready_keys; /* 阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象 */
dict *watched_keys; /* 存储watch监控的的key和客户端对象 */
int id; /* Database ID */
long long avg_ttl; /* 存储的数据库对象的平均ttl（time to live），用于统计 */
unsigned long expires_cursor; /* 循环过期检查的光标. */
list *defrag_later; /* 需要尝试去清理磁盘碎片的链表，会慢慢的清理 */
} redisDb;

typedef struct redisObject {
unsigned type:4; //类型 对象类型
unsigned encoding:4;//编码
// LRU_BITS为24bit 记录最后一次被命令程序访问的时间
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; //引用计数
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”

/* 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 {
/* 存储字符串类型数据 redis3.0版本中使用robj类型表示，但是在redis4.0.1中直接使用sds类型表示 */
sds ele;
/*存储排序的分值*/
double score;
/*后退指针，指向当前节点最底层的前一个节点*/
struct zskiplistNode *backward;
/*层，柔性数组，随机生成1-64的值*/
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];/* 两张哈希表，存储键值对数据，ht[0]为原生哈希表，ht[1]为 rehash 哈希表 */
long rehashidx; /* rehash标识 当等于-1时表示没有在rehash，否则表示正在进行rehash操作，
存储的值表示hash表 ht[0]的rehash进行到哪个索引值(数组下标)*/
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
/* 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; /* 列表中所有数据项的个数总和 */
unsigned long len; /* quicklist节点的个数，即ziplist的个数 */
int fill : QL_FILL_BITS; /* ziplist大小限定，由list-max-ziplist-size给定 (Redis设定)*/
unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
unsigned int bookmark_count: QL_BM_BITS; /*节点压缩深度设置，由list-compress-depth给定*/
quicklistBookmark bookmarks[]; /*可选新特性 使用realloc重新分配空间的时候会用到*/
} 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; // 指向上一个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;

/* 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压缩后占用的字节数*/
char compressed[]; //柔性数组，指向数据部分
} 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”