Redis 数据结构

发表于

最近又开始学习 Redis 的实现原理，配和《Redis 设计与实现》这本书和 Redis 源码梳理一下 Redis 的实现原理。

SDS

Redis 没有直接使用 C 语言传统的字符串表示（以空字符串结尾的字符数组，C 字符串），而是自己创建了一种名为简单动态字符串（Simple Dynamic String，SDS）的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。

// sds.h
struct sdshdr {
    
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};

Redis 之所以使用 SDS，是因为它与 C 字符串相比有下面一些优势：

常数复杂度获取字符串长度

C 字符串使用 strlen 方法获取长度，时间复杂度是 O(n)，而 SDS 直接返回 len 字段，时间复杂度是 O(1)。

杜绝缓冲区溢出

char * strcat(char * dest, const char * src) {
    char *tmp = dest;
    while (*dest)
        dest++;
    while ((*dest++ = *src++) != '\0')
        ;
    return tmp;
}

C 字符串的 strcat 方法将字符串 src 添加到字符串 desc 后面，执行之前如果没有申请足够的空间，会导致 src 溢出的 dest 后面的内存中，造成缓冲区溢出（Buffer Overflow）。而 SDS 的 API 在修改时，会先检查 free 的空间是不是足够，如果不够会先扩展之后再执行，不会造成缓冲区溢出。

减少修改字符串时带来的内存重分配次数

SDS 使用空间预分配优化字符串增长操作，当使用 API （如 sdscat）修改 SDS 且需要扩展空间时，实现上不仅会分配必需的扩展空间，还会分配额外的未使用（free）空间：若修改后 SDS 长度 len 小于 1MB 则分配和 len 相同的 free 空间，否则分配 1MB 的 free 空间。

SDS 使用惰性空间释放优化字符串缩短操作，当使用 API （如 sdstrim）缩短 SDS 所保存的字符串时，实现上会把缩短的字节数计入到 free 属性中，并不会通过重新分配内存释放掉，当然也有 API 可以实现 SDS 未使用空间的释放。

二进制安全

C 字符串使用空字符标识结尾，所以保存的字符串中间不能包含空字符，否则字符串会被截断，所以 C 字符串只能保存文本数据，不能保存图片、音视频、压缩文件这样的二进制数据（二进制数据中空字符很常见）。而 SDS 是二进制安全（Binary Safe）的，因为它使用 len 属性的值而不是空字符来判断字符串是否结束。

兼容部分 C 字符串函数

SDS 的 buf 属性是个以空字符结尾的 C 字符串，可以重用 C 字符串的 strcat、strcmp 等操作函数。

链表

作为一种常用数据结构，链表内置在很过高级的编程语言中，但是 Redis 使用的 C 语言并没有内置这种数据结构，所以 Redis 构建了自己的链表实现。

// adlist.h
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;

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

Redis 的链表与普通的双向链表相比，有两个独特的地方：

  • 长度计数器：使用 len 属性记录链表包含的节点数量，所以获取链表节点数量的时间复杂度是 O(1)；
  • 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构中的 dup、free、match 三个属性分别为节点值设置复制、释放、比较（是否相等）的函数，所以链表可以保存各种不同类型的值。

字典

C 语言同样没有内置字典这种数据结构，所以 Redis 构建了自己的字典实现。

// dict.h
typedef struct dict {
    
    // 类型特定函数
    dictType *type;
    
    // 私有数据
    void *privdata;
    
    // 哈希表
    dictht ht[2];
    
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
    
} 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;

typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;
    
    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    
    // 该哈希表已有节点的数量
    unsigned long used;
    
} dictht;

typedef struct dictEntry {
    
    // 键
    void *key;
    
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
    
} dictEntry;

Redis 中的字典由 dict 结构定义，type 属性保存了操作特定类型键值对的函数集合，而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。ht 属性包含两个 dictht 哈希表，一般情况下只是用 ht[0]，ht[1] 只会在对 ht[0] 进行 rehash 时使用，rehashidx 属性则记录了 rehash 目前的进度。

哈希算法

// 计算给定键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

h = dictHashKey(d, key);

// 使用哈希值和 sizemask 计算索引值
idx = h & d->ht[table].sizemask;

Redis 使用 MurmurHash2 算法来计算键的哈希值，即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性，并且算法的计算速度也非常快。

Redis 使用链地址法（Separate Chaining，又称拉链法）来解决哈希冲突，因为 dictEntry 节点组成的链表没有指向表尾的指针，所以为了速度考虑，实现上总是将新节点添加到链表的表头，时间复杂度为 O(1)。

渐进式 Rehash

哈希表有个重要的指标叫作负载因子（Load Factor），是哈希表已保存节点数量和哈希表大小的比值，即 ht[0].used / ht[0].size 。随着操作的不断执行，哈希表保存的键值对数量会逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，需要对哈希表的大小进行相应的扩展或收缩，即重新散列（Rehash）。Redis 对字典的哈希表执行 Rehash 的步骤如下：

  • 为字段的 ht[1] 哈希表分配空间：若是扩展操作，那么 ht[1] 的大小为第一个不小于 ht[0].used * 2 的 2^n；若是收缩操作，那么 ht[1] 的大小是第一个不小于 ht[0].used 的 2^n；
  • 重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上；
  • 当 ht[0] 的所有键值对都迁移到 ht[1] 后，释放 ht[0] 并将 ht[1] 设置为 ht[0]，最后在 ht[1] 新创建一个空白哈希表。

Redis 中 Rehash 的动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的，这样做的原因在于，如果一次性将大量键值对 Rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。具体步骤是：

  • 在为 ht[1] 分配空间后，设置 rehashidx 属性的值为 0，表示开始 Rehash；
  • 在 Rehash 期间，每次对字段执行添加、删除、查找或者更新操作时，除了执行指定的操作外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 Rehash 到 ht[1]，并递增 rehashidx 的值；
  • 随着字典操作的不断执行，Rehash 最终会在某个时间点完成，这时设置 rehashidx 的值为 -1，表示 Rehash 完成。

在渐进式 Rehash 期间，字典的删除（delete）、查找（find）、更新（update）等操作会在 ht[0] 和 ht[1] 两个哈希表上执行，但是添加（add）操作只会在 ht[1] 上执行，保证 ht[0] 的键值对数量只减不增，并随着 Rehash 操作的执行而最终变成空表。

// 如果字典正在 rehash ，那么将新键添加到 1 号哈希表
// 否则，将新键添加到 0 号哈希表
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 为新节点分配空间
entry = zmalloc(sizeof(*entry));
// 将新节点插入到链表表头
entry->next = ht->table[index];
ht->table[index] = entry;

跳跃表

跳跃表（Skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均 O(logn)、最坏 O(n) 时间复杂度的节点查找，大部分情况下其效率可以和平衡树媲美，但是跳跃表的实现比平衡树要简单得多，所以成为一个不错的替代者。Redis 只在两个地方用到了跳跃表，一个是有序集合键，另一个是在集群节点中用作内部的数据结构。

图 1：一个跳跃表
// redis.h
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

typedef struct zskiplistNode {

    // 成员对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 对象最后一次被访问的时间
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用计数
    int refcount;

    // 指向实际值的指针
    void *ptr;

} robj;

层

跳跃表节点的 level 数据可以包含多个元素，一般来说，层的数量越多，访问其他节点的速度就越快。每次创一个新跳跃表节点时，都会根据幂次定律（Power Law，越大的数出现的概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的高度。

层的前进指针（level[i].forward 属性）用于从表头向表尾遍历节点，图中用虚线标出了遍历跳跃表中所有节点的路径。

层的跨度（level[i].span 属性）用于记录两个节点之间的距离，用于计算排位（Rank）：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

后退指针

节点的后退指针（backward 属性）用于从表尾向表头遍历节点，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

分值和成员

节点的分值（score 属性）是一个 double 类型的浮点数，跳跃表中的所有节点都按分值从小到大排序。

节点的成员对象（obj 属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

在同一个跳跃表中，各个节点保存的成员对象必须唯一，但是多个节点保存的分值可以相同，若两个节点的分值相同，成员对象字典序较小的节点会排在前面（靠近表头的方向），另一个节点则排在后面。

整数集合

整数集合（Intset）是 Redis 用于保存整数值的集合抽象数据结构，可以保存类型为 int16_t、int32_t 或 int64_t 的整数值，并保证集合中不会出现重复元素。

// intset.h
typedef struct intset {
    
    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

contents 数组中按值从小到大存储整数值，且不包含任何重复项，虽然被声明为 int8_t 类型，但是其真正类型取决与 endcoding 的值是 INTSET_ENC_INT16、 INTSET_ENC_INT32 还是 INTSET_ENC_INT64。

每当要将一个新元素添加到整数集合中，且新元素的类型比整数集合当前类型要长时，整数集合就需要先进行升级（Upgrade），升级操作分三步：根据新元素类型，扩展 contents 数组大小，并为新元素分配空间；将原来的元素都转换成与新元素相同的类型，并放置到正确的位置上；最后将新元素添加进来。一旦对 contents 数组进行了升级，编码就会一直保持升级后的状态，不支持降级。

整数集合在每次插入新元素时，都会使用 zrealloc 函数扩展内存空间，并不会提前分配额外的未使用空间。

压缩列表

压缩列表（Ziplist）是列表键和哈希键的底层实现之一，由一系列特殊编码的连续内存块组成的顺序型（Sequential）数据结构。一个压缩列表可以包含任意多个节点（Entry），每个节点可以保存一个字节数组或者一个整数值。

列表结构

zlbytes zltail zllen entry1 entry2 … entryn zlend
4 字节 4 字节 2 字节 1 字节 
// ziplist.c
unsigned char *ziplistNew(void) {

    // ZIPLIST_HEADER_SIZE 是 ziplist 表头的大小
    // 1 字节是表末端 ZIP_END 的大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;

    // 为表头和表末端分配空间
    unsigned char *zl = zmalloc(bytes);

    // 初始化表属性
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;

    // 设置表末端
    zl[bytes-1] = ZIP_END;

    return zl;
}

#define ZIP_END 255
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

Redis 源码中并没有一个数据结构来表示压缩列表，都是按照编码规则进行字节运算。如上表所示，zlbytes 记录整个压缩列表占用的内存字节数；zltail 记录压缩列表表尾节点距离起始地址有多少个字节；zllen 记录了压缩列表包含的节点数量；zlend 是特殊值 0xFF（十进制值 255）用于标记压缩列表的末端。

节点结构

previous_entry_length encoding content
1 / 5 字节 1 / 2 / 5 字节 根据 encoding 的值判断

因为压缩列表节点的长度不定，也没有固定的数据结构表示，但是每个节点能够分为如上表所示的三部分。

previous_entry_length 属性记录压缩列表中前一个节点的长度，用于从表尾向表头遍历。该属性的长度可以是 1 字节或 5 字节：如果前一节点的长度小于 254 字节，该属性长度为 1 字节；如果前一节点的长度不小于 254 字节，该属性长度为 5 字节且第一个字节设置为 0xFE（十进制值 254），后 4 字节保存前一节点的长度。

encoding 属性记录节点数据的类型和长度，该属性本身的长度可以是 1 字节、2 字节或 5 字节：

  • 1 字节、2 字节或 5 字节长，最高位为 00、01 或 10 时表示数据为字节数组，数组的长度最高位后的其他位记录（标为 L 的位用来表示 content 保存的字节数组的长度）；
encoding 值 encoding 长度 content 字节数组长度
00LLLLLL 1 字节 不大于 63 （2^6 - 1）
01LLLLLL LLLLLLLL 2 字节 不大于 16383（2^14 - 1）
10XXXXXX LLLLLLLL LLLLLLLL LLLLLLLL LLLLLLLL 5 字节 不大于 2^32 - 1
  • 1 字节长，最高位为 11 表示数据为整数值，整数值的类型和长度由去掉最高位之后的其他位记录。
encoding 值 content 整数长度及类型
11000000 int16_t
11010000 int32_t
11100000 int64_t
11110000 24 位有符号
11111110 8 位有符号
1111XXXX 无，encoding 低 4 位保存一个 [0, 12]
0%