Redis数据结构与对象

Redis是用c语言开发的一个开源的高性能键值对（key-value）数据库，Redis数据库里面的每个键值对都是由对象（object）组成，其中：

• 数据库键总是一个字符串对象（string object）
• 数据库键的值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象这五种对象中的其中的一种。

每种类型的对象，至少都有两种或以上的编码方式（即底层实现），不同的编码可以在使用场景上优化对象的使用效率。

1. 底层数据结构

1.1 简单动态字符串

SDS是C字符串的一种封装，其定义如下所示

struct sdshder{
    //记录buf数组中已使用字节的数量，不包含'\0'
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组，用于保存字符串
    char buf[];
}

通过使用SDS而不是C字符串，Redis将获取字符串长度所需要的复杂度从O(N)降低到了O(1)，同时因为SDS结构中记录了free的大小，所以杜绝了发生缓冲区溢出的可能性。

同时，为了减少修改字符串时带来的内存重分配次数，SDS实现空间预分配和惰性空间释放两种优化策略。

空间预分配指的就是当需要对SDS进行空间扩展的时候，程序不仅为SDS分配修改所需要的空间，还会为SDS分配额外的未使用空间。通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性空间释放是指当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性讲这些字节的数量纪录起来，并等待将来使用。

1.2 链表

typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值赋值函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr,void *key);
}list;

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

Redis的链表实现的特性可以总结如下：

• 双端：双向指针
• 无环
• 带表头指针和表尾指针
• 带链表长度计数器
• 多态：

1.3 字典

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

//哈希表
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;
    }v;
    //指向下一个哈希表节点，形成链表
    struct dictEntry *next;
}dictEntry;

//字典
typedef struct dict{
    //类型特定函数
    dictType *type;
    
    //私有数据
    void *privdata;
    
    //哈希表,一般情况下，字典只是用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
    dictht ht[2];
   
    // 记录了rehash目前的进度，当rehash不在进行时，值为-1
    int trehashidx；
}dict;

哈希算法和解决键冲突的办法与Java中HashMap大同小异，在此不做赘述，下面主要讲解下rehash的过程。

Rehash

当一下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

1. 服务器目前没有执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子大于等于1.
2. 服务器目前正在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载印在大于等于5

（负载因子的计算方法与hashmap一致，即 哈希表已保存结点数量/哈希表数组大小）

Redis对字典的哈希表执行rehash的总体步骤如下：

1. 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作以及ht[0]当前包含的键值对数量。如果是扩充操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方。
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面
3. 当ht[0]包含的所有键值对都前移到了ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白的哈希表，为下一次rehash做准备

然后，需要注意的是，Redis的rehash过程是一个渐进式的rehash过程。

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2. 在字典上维持一个索引计数器变量rehashidx（这个rehashidx的含义就是正在进行rehash的ht[0]上的索引），并将它的值设为0，表示rehash工作正式开始
3. 在rehash进行期间，每次对字典执行增删改查时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引所有键值对rehash到ht[1]，当rehash工作完成之后，将rehashidx属性的值增1
4. 当ht[0]的所有键值对都被rehash到ht[1]上猴，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

在渐进式rehash的过程中，增直接发生在ht[1]上，改、查、删则发生在ht[0]和ht[1]上。

1.4 跳跃表

跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，是有序集合键的底层实现之一。

Redis的跳跃表由zskiplistNode和zskiplist组成。在zskiplist结构中，该结构包含以下属性

• header: 指向跳表的表头节点
• tail: 指向跳表的表尾节点
• level: 记录目前跳跃表内，层数最大的那个节点的层数
• length: 记录跳跃表的长度，也就是跳跃表目前包含节点的数量

而在跳跃表节点中，其结构定义如下所示：

typedef struct zskiplistNode{
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //成员对象
    robj *obj;
    //层
    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    }level[];
}zskiplistNode;

跳跃表节点中有level[]数组，每一个level中都有一个指向表尾方向的指针以及跨度，其中跨度是用来计算某个节点在跳跃表中的排位。每个跳跃表节点的层高都是1-32之间的随机数。跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

1.5 整数集合

typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组，具体类型由encoding所决定，可以是int16_t, int32_t, int64_t 
    int8_t contents[];
} intset;

各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

升级

当我们将一个新元素添加到整数集合里面时，如果新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。升级整数集合并添加新元素共分为三步进行：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 将底层数组所有元素都转换为新元素相同的类型，并将类型转换后的元素放到正确的位上
3. 将新元素添加到底层数组里。

如果向整数集合添加新元素时可能会引起升级，则时间复杂度为O(N)。

1.6 压缩列表

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序性数据结构。

zlbytes用来记录压缩列表占用的内存字节数；zltail用来记录压缩列表表尾节点距离压缩列表的起始地址有多少字节。

压缩列表的每个节点又是由三部分组成的

其中previous_entry_length用来记录前一个结点的长度。

（连续更新部分已省略）

2. Redis对象

当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

每个对象都为以下结构

typedef struct redisObjet{
    //类型
    unsigned type;
    //编码方式
    unsigned encoding;
    //指向底层实现数据结构的指针
    void *ptr;
    //引用计数
    int refount;
    //最后一次被命令程序访问的时间
    unsigned lru;
}

2.1 类型与编码

对于Redis数据库保存的键值对来说，键对象总是一个字符串对象，而值对象可以是字符串对象、列表对象、有序集合对象、哈希对象、集合对象的其中一种

类型常量	对象的名称
REDIS_STRING	字符串对象
REDIS_LIST	列表对象
REDIS_HASH	哈希对象
REDIS_SET	集合对象
REDIS_ZSET	有序集合对象

可以用type命令查询数据库键所对应的对象类型

redis > SET msq "hello world"
OK
redis > TYPE msg
string

对象的ptr指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定。encoding属性记录了对象所使用的的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现。(除了字符串对象有三种底层实现外，其余都为两种)

可以使用OBJECT ENCODING命令来查看一个数据库键的值对象的编码:

redis> SET msg "hello world"
OK
redis> OBJECT ENCODING msg
"embstr"

2.2 字符串对象

字符串对象的编码可以是int、raw或者embstr。

如下图所示，是用int编码的字符串对象

如下图所示，是用raw编码的字符串对象

如下图所示，是用embstr编码的字符串对象

embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。

字符串命令的实现

另外需要注意，字符串对象时Redis五种类型的对象中唯一一种会被其他四种对象嵌套的对象。

2.3 列表对象

列表对象的编码可以是ziplist或者linkedlist

ziplist编码的numbers列表对象

linkedlist编码的numbers列表对象

列表命令的实现

2.4 哈希对象

哈希对象的编码可以是ziplist或者hashtable。

如果编码方式是ziplist，那么每当有新的键值对要加入到哈希对象时，程序会先将键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾。

如果编码方式方式是hashtable，则字典的每个键都是字符串对象，每个值也都是字符串对象。

哈希命令的实现

2.5 集合对象

集合对象的编码可以是intset或者hashtable。注，当使用hashtable作为编码方式时，value没有值

集合命令的实现

2.6 有序集合对象

有序集合对象的编码可以是ziplist或者skiplist。

ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表结点来保存，第一个结点保存元素的成员，第二个结点则保存元素的分值。压缩列表内的集合元素按分值从小到大进行排序。

skiplist编码的有序集合对象使用跳表作为底层实现，除了跳表之外，还有一个dict字典为有序集合创建了一个从成员到分值的映射。这样既可保证可以使用O(1)的复杂度查找成员分值，也可以保留跳表执行范围型操作的优点。

下图中重复展示了各个元素的成员和分值，但在实际中，字典和跳跃表会共享元素的成员和分值，并不会造成任何数据重复，不会因此而浪费任何内存。

有序集命令的实现方法

2.7 内存回收

Redis的对象中有一属性refcount用来记录引用数目。使用引用计数法来统计对象被多少个程序所使用的，如果引用计数变为0，则被回收。因此对象的整个生命周期可以划分为创建对象、操作对象、释放对象三个阶段。

2.8 对象共享

Redis在初始化服务器时，创建一万个字符串对象，这些对象包含从0到9999的所有证书值，当服务器需要用到0到9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。

在Redis中，让多个键共享同一个值对象需要执行以下两个步骤：

1. 将数据库键的值指针指向一个现有的值对象
2. 将被共享的值对象的引用计数+1

2.9 对象空转时长

redis对象中的lru属性记录了对象最后一次被命令程序访问的时间，使用OBJECT IDLETIME命令可以打印出给定键的空转时长。

---

• ← Previous Post
• Next Post →