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$ 文件中,结构如下:

  1. $zlbytes$ :$4$ 字节压缩列表长度;
  2. $zltail$ :$4$ 字节尾元素相对于压缩列表起始地址偏移量;
  3. $zllen$ :$2$ 字节压缩列表元素数目,长度超过 $2^{16}-1$ ,需要遍历压缩列表才能获取元素数目
  4. $entry$ :元素节点;
  5. $zlend$ :$1$ 字节表示压缩列表结尾,恒为 $0xFF$。

        其中元素节点的编码如下:

  1. $previous_-entry_-length$ :前一个节点的字节长度;
  2. $encoding$ :当前元素编码;
  3. $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\%$ 的概率上升一层。

Redis底层数据结构实现