Redis底层数据结构实现
1. 对象
Redis中的每个键值对都是由两个对象结构表示，定义在 $server.h$ 文件中。
// 对象类型
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
#define OBJ_MODULE 5
#define OBJ_STREAM 6
// 对象编码
#define OBJ_ENCODING_RAW 0 // SDS
#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 // embstr编码的SDS
#define OBJ_ENCODING_QUICKLIST 9
#define OBJ_ENCODING_STREAM 10
// 对象结构
typedef struct redisObject {
unsigned type:4; // 类型
unsigned encoding:4; // 编码
unsigned lru:LRU_BITS; // 最后一次访问时间
int refcount; // 引用计数
void *ptr; // 底层指针
} robj;
1. SDS
简单动态字符串 ( $simple\ \ dynamic\ \ string$, $SDS$ ) 是Redis中字符串的数据结构，定义在 $sds.h$ 头文件中。
typedef char *sds;
// 不使用该结构，而是直接访问flag
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; // 已使用的字节数，不包括'\0'
uint8_t alloc; // 总共分配的字节数，不包括'\0'
unsigned char flags; // 类型
char buf[]; // 字节数组，包括'\0'
};
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[];
};
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
__ $attribute$ __ $(($ __ $packed$ __ $))$ 作用是取消字节对齐，从而允许通过传入 $buf$ 的方式访问 $flags$ ，即 $buf[-1]$ 。
Redis会根据字符串长度选择对应的数据结构。在 $sds.c$ 文件中定义了如下函数：
static inline char sdsReqType(size_t string_size) {
if (string_size < 1 << 5) // 32
return SDS_TYPE_5;
if (string_size < 1 << 8) // 256
return SDS_TYPE_8;
if (string_size < 1 << 16) // 65536
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1LL << 32) // 2^32
return SDS_TYPE_32;
return SDS_TYPE_64; // 2^64
#else
return SDS_TYPE_32;
#endif;
}
与普通的字符数组相比，$SDS$ 可以直接获取长度，并且在添加字节时不用每次都重新创建。由于底层用的也是字符数组，因此 $SDS$ 也兼容C库函数中的字符串操作。
2. 链表
链表定义在 $adlist.h$ 文件中。
// 节点
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
// 迭代器
typedef struct listIter {
listNode *next;
int direction;
} listIter;
// 链表
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;
3. 整数集合
如果一个 $set$ 只包含整数，那么就会使用整数集合存储。整数集合定义在 $intset.h$ 中。
typedef struct intset {
uint32_t encoding; // 集合类型
uint32_t length; // 长度
int8_t contents[]; // 以不包含重复项的形式升序排序的数组
} intset;
整数集合中保存的整数类型取决于 $encoding$ 。如果存入的整数不符合编码格式，就需要升级，升级要根据新元素的类型扩展数组并重新分配空间。
4. Hash
$Hash$ 定义在 $dict.h$ 文件中。
typedef struct dicEntry { // 节点
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值
struct dicEntry *next; // 链表结构解决冲突
} dictEntry;
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); // 删除值
int (*expandAllowed)(size_t moreMem, double usedRatio); // 扩容
} dictType;
typedef struct dictht { // 哈希表
dictEntry **table; // 哈希数组
unsigned long size; // 表大小，2的幂次
unsigned long sizemask; // 计算索引，即表大小-1
unsigned long used; // 已使用节点数
} dictht;
typedef struct dict { // 字典
dictType *type; // 类型
void *privdata; // 私有数据
dictht ht[2]; // 两个哈希表
long rehashidx; // rehash索引，不进行rehash时为-1
int16_t pauserhash; // 如果>0说明rehash暂停，<0说明发生错误
} dict;
typedef struct dictIterator {
dict *d;
long index;
int table, safe;
dictEntry *entry, *nextEntry;
long long fingerprint;
} dictIterator;
Redis的字典使用链地址法解决哈希冲突，采用头插法。Redis中的字典不仅可以进行扩容操作，也可以进行收缩操作，大小固定为不小于当前使用空间的最小的 $2$ 的整数次幂。在每次执行 $CRUD$ 操作之后都会进行 $rehash$ 操作，将保存在 $ht[0]$ 中的键值对迁移到 $ht[1]$ 中，直到 $ht[0]$ 为空，然后交换 $ht[0]$ 和 $ht[1]$ ，并在 $ht[1]$ 上重建一个新表。$rehashidx$ 的作用是记录每次操作过程中应该进行迁移的键值对的索引，如果迁移完成，会重新设为 $-1$ 。
5. 压缩列表
压缩列表是 $list$ 和 $hash$ 的底层实现之一，对于只包含少量数据的项，会使用压缩列表存储。压缩列表定义在 $ziplist.c$ 文件中，结构如下：
- $zlbytes$ ：$4$ 字节压缩列表长度；
- $zltail$ ：$4$ 字节尾元素相对于压缩列表起始地址偏移量；
- $zllen$ ：$2$ 字节压缩列表元素数目，长度超过 $2^{16}-1$ ，需要遍历压缩列表才能获取元素数目
- $entry$ ：元素节点；
- $zlend$ ：$1$ 字节表示压缩列表结尾，恒为 $0xFF$。
其中元素节点的编码如下：
- $previous_-entry_-length$ ：前一个节点的字节长度；
- $encoding$ ：当前元素编码；
- $content$ ：存储的数据，可以是字节数组或者整数。
// zl为char*类型，指向压缩列表首地址
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
// zl+4指向zltail字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t)((zl)+sizeof(uint32_t))))
// zl+zltail指向尾元素首地址
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// zl+8指向zllen字段
#define ZIPLIST_LENGTH(zl) (*((uint16_t)((zl)+sizeof(uint32_T)*2)))
// 最后一个字段为zlend
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
// 存储经过解码后的节点
typedef struct zlentry {
unsigned int prevrawlensize; // 前驱节点长度的字节长度
unsigned int prevrawlen; // 前驱节点长度
unsigned int lensize; // encoding字段的字节长度
unsigned int len; // 数据字节长度
unsigned int headersize; // prevrawlensize + lensize，即previous_entry_length+encoding长度
unsigned char encoding; // ZIP_STR_* 或者 ZIP_INT_*
unsigned char *p; // 存储数据的首地址
} zlentry;
6. 跳表
跳表定义在 $server.h$ 文件中。
typedef struct zskiplistNode { // 跳表节点
sds ele; // 元素
double score; // 分值
struct zskiplistNode * backward; // 后向指针
struct zskiplistLevel { // 层
struct zskiplistNode *forward; // 前向指针
unsigned long span; // 跨度，即同层相邻节点之间最底层节点的数量
} level[];
} zskiplistNode;
typedef struct zskiplist { // 跳表
struct zskiplistNode *header, *tail;
unsigned long length; // 长度
int level; // 最大层数
} zskiplist;
typedef struct zset { // 有序集合
dict *dict; // 字典
zskiplist *zsl; // 跳表
} zset;
$ZSKIPLIST_-P$ 为 $0.25$ ，代表每次插入的节点都有 $25\%$ 的概率上升一层。