Redis设计与实现（二）——基础数据结构和对象系统

这篇博文主要介绍在Redis中的各种基本数据结构以及由其实现的各种高层对象

SDS

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

SDS的定义如下：

struct sdshdr {
    int len;  // 记录buf数组中已使用字节的数量
    int free; // 记录buf数组中未使用字节的数量
    char buf[]; // 字节数组，用于保存字符串
}

相较于原生的C字符串，SDS有如下几点好处：

1. 常数复杂度获取字符串长度
2. 减少修改字符串带来的内存重分配次数：当由于修改而需要对SDS进行空间扩展的时候，SDS不仅会分配修改所需要的空间，还会为SDS分配额外的未使用空间，从而减少内存重分配的次数
3. 可以保存文本或者二进制数据，不一定空字符就是结尾了，决定字符串长度的是len属性
4. 兼容部分C字符串函数：SDS同样也以空字符结尾（但是该空字符不计入len中），因此可以直接复用<string.h>中的函数了

链表

链表提供了高效的节点重排能力、顺序性的节点访问方式并且可以通过增删节点来灵活地调整链表的长度，由于链表是一种很常见的数据结构，因此这里仅仅简单地给出对应的定义：

struct listNode {
    struct listNode *prev; // 前置节点
    struct listNode *next; // 后置节点
    void *value; // 节点的值
}

// 虽然仅仅使用多个linstNode结构就可以组成链表，但是使用list来持有链表的话操作起来会更方便
struct list {
    listNode *head; // 头节点
    listNode *tail; // 尾节点
    unsigned long lenth; // 长度
}

在listNode中使用void* 指针来保存节点值，因此链表可以用于保存各种不同类型的值

字典

在字典中，一个键（key）可以和一个值（value）进行关联或者说映射

在Redis中字典的实现如下：

struct dictEntry {
    void *key // 键，在哈希值相同的情况下，通过比对键来实现区分
    
    // 值，通过union在支持多种类型的同时也节省了空间
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    
    // 指向下一个哈希表节点，从而使得哈希值相同的节点形成链表（使用链地址法来解决哈希冲突）
    dictEntry *next
}

struct dictht {
    // dictEntry数组，其中哈希值作为数组的下标
    dictEntry **table;
    
    unsigned long size;
    
    // 哈希值掩码 sizemask = size - 1，一般都是2 ^ n - 1，从而可以使用&操作替代取余
    unsigned log sizemask;
    
    undigned long used;
}

struct dict {
    // 哈希表
    dictht ht[2];
    
    // rehash索引，当rehash不在进行时，值为-1
    int trehashindex;
}

这里需要注意的是字典使用了两个HashTable，从而实现动态扩容，其步骤如下：

1. 为ht[1]分配对应的空间，往往是size * 2
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面去：rehash指的是重新计算键的哈希值和索引值
3. 在ht[0]的所有键值对都迁移到了ht[1]之后，释放ht[0]，然后将ht[1]设置为ht[0]

由于rehash操作可能会比较耗费时间，因此在具体实现中rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的：通过rehashindex记录索引计数器，在rehash进行期间，每次对字典执行CRUD操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]上，并且rehashindex++，也即将原本的一个集中式大操作通过分而治之的思想分摊到了多次命令执行中，又由于字典中采用了两个哈希表，因此渐进式的rehash的操作也不会对操作造成影响。

跳跃表

跳跃表是一种类似于平衡二叉树的数据结构，但是其实现会比二叉树简单很多，其原理在之前的博文中已经给出，它是有序集合的底层实现之一，这里仅仅给出Redis的实现以及对应的简单解释:

struct zskiplistNode {
    // 后退指针，跳跃表的遍历是从后往前遍历的
    zsiplistNode *backward
    
    // 分值
    double score;
    
    // 成员对象，也即存的高层对象
    redis_object *obj;
    
    // 层次数组，索引代表了在第几层，层数越高，跨度越大
    struct zskipListLevel {
        // 前进指针，指向相同层的下一个节点，从而实现跨多节点快速查找
        zskiplistNode *forward;
        
        // 跨度，通过跨度记录相同的邻接节点之间的距离，从而可以快速计算排位
        int span;
    } level[];
}

// 仅靠多个节点就可以组成一个跳跃表，但是通过使用zskiplist结构来持有会方便对于整个跳跃表进行处理（类似链表）
struct zskiplist {
    // tail主要用于遍历，header主要用于二分查找
    skiplistNode *header, *tail;
    
    unsigned long lenth;
    
    // 表中层数最大的节点的层数
    int level;
}

整数集合

整数集合是Redis用于保存整数值的集合抽象数据结构，它可以保存int16，int32，int64的整数值并且保证集合中不会出现重复元素，其结构如下：

struct intset {
    // 编码方式
    uint32_t encoding;
    
    uint32_t length;
    
    int8_t contents[];
}

contents数组是整数集合的底层实现，它的每个元素是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序地排列

虽然contents属性是int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，它的真正类型取决于encoding属性的值，另外当向整数集合添加一个大于目前已有数组项类型的元素时所有的元素都会转成最大的元素类型（升级），如：像一个底层为int16_t类型的整数集合添加一个int64_t类型的的整数值时，整数集合已有的所有元素都会被转换成int64_t类型。通过升级可以在同时保存三种不同类型的值的时候尽量节省内存，仅仅在需要的时候才升级

整数集合相较于基于字典实现的集合相当于用时间去换空间

压缩列表

压缩列表是Redis为了节约内存而开发的，它是由一系列基于对应规则的连续内存块组成的顺序性数据结构，一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值，其结构如下所示：
<-- zlbytes --><-- zltail --><-- zllen --><-- entry-1 -->...<-- entry-n -->

entry的结构如下：
<-- previous_entry_length --><-- encoding --><-- content -->

其中content可以是字节数组也可以是一个整数值

压缩列表的遍历是从尾往头遍历的，其原理就是zltail + 每个entry的privious_entry_length，而压缩列表之所以可以用来实现哈希表，一方面是可以用它连续存一个key和一个value来节省空间，另外一方面是修改某个key时只要简单地append在最后再结合从尾往头遍历的特性就可以了，明显地压缩列表也是典型的一个用时间换空间的例子

对象

Redis里面的每个键值对都是由对象（redisObject）组成的，其中数据库键总是一个字符串对象，而数据库键的值可以是：字符串对象、列表对象、哈希对象、集合对象以及有序集合对象，上述的对象都是高层的对象，在redisObject中使用type字段决定，为了灵活性去适配不同的使用场景，每一种对象都至少有两种以上的基本数据结构（在本博文中上述的基本数据结构）作为底层的实现，底层的具体实现在redisObject中使用encoding字段决定，redisObject的定义如下：

struct redisObject {
    // 高层类型
    unsigned type: 4;
    
    // 基本数据结构类型
    unsigned encoding: 4;
    
    // 指向底层实现数据结构的指针
    void *ptr
}

各个高层类型和基本数据结构类型的对应如下表所示：

embstr和raw的区别

embstr编码是专门用于保存短字符串的一种优化编码方式，相较于raw编码会调用两次内存分配函数来分别创建redisObject结构和ptr指向的sdshdr结构，embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构

内存回收和对象共享

因为C语言并不具备自动内存回收的功能，因此Redis在自己的对象系统中构建了一个引用计数技术实现的内存回收机制，也即每个redisObject会有一个refcount属性记录它的引用数

recount属性除了用于实现引用计数内存回收机制之外，它还带有对象共享的作用，比如键A创建了一个包含整数值100的字符串对象作为值对象，此时键B也要创建一个同样保存了整数值100的字符串对象作为值对象，那么可以让键A和键B共享同一个字符串对象

目前，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0到9999的所有整数值

对象的空转时长

除了前面介绍的type、encoding、ptr和refcount四个属性之外，redisObject中还包含了一个lru属性，该属性记录了对象最后一次被命令程序访问的时间，可以使用OBJECT IDLETIME命令打印出给定键的空转时长，也即简单地将当前时间减去对应的lru字段得到的

• ← Previous Post
• Next Post →