关于redis:Redis对象类型

前言

Redis是一种 key-value 型的数据库，key和 value 都是应用对象示意。执行 SET message HelloWorld 时，key是一个蕴含了字符串 message 的对象，value是一个蕴含了字符串 HelloWorld 的对象。本篇文章将对 Redis 中的对象类型进行学习。

注释

一. Redis 中的五种对象简介

Redis中的对象叫做redisObject，其构造如下所示。

typedef struct redisObject {
    // 对象类型
    unsigned type:4;
    // 对象底层应用的编码
    unsigned encoding:4;
    // 对象最初一次被应用的工夫
    unsigned lru:22;
    // 援用计数
    int refcount;
    // 指向对象底层数据结构的指针
    void *ptr;
} robj;

redisObject中的 type 字段示意以后对象的类型，type字段的取值共五种，表明 Redis 中共有五种对象，如下表所示。

每种类型的 Redis 对象在不同状况下会由不同的底层数据结构实现。Redis对象底层数据结构共八种，如下表所示。

type和 encoding 的对应关系能够由下表示意。

二. 字符串对象

字符串对象与底层数据结构对应关系如下。

• 如果一个字符串内容能够转换为 long 类型，则该字符串对象的底层数据结构为 long 类型的整数；
• 如果字符串不能转换为 long 类型，并且字符串长度小于等于 44 字节，则该字符串对象的底层数据结构为 embstr 编码的简略动静字符串；
• 如果字符串长度大于等于 45 字节，则该字符串对象的底层数据结构为 raw 编码的简略动静字符串。

embstr编码在分配内存时只须要调配一次，在开释内存时也只须要开释一次，与之作为比照的 raw 须要两次。同时 embstr 编码的字符串应用间断内存，能够躲避伪共享的产生从而能够更好的利用缓存劣势。

三. 列表对象

列表对象与底层数据结构对应关系如下。

• 列表对象存储的元素长度小于 64 字节，元素个数小于 512 个，则该列表对象底层数据结构应用压缩列表；
• 其它状况，该列表对象底层数据结构应用双端链表。

上面对压缩列表进行剖析。压缩列表是一种内存紧凑型的数据结构，因为应用间断的内存空间，能够躲避伪共享的产生从而能够更好的利用缓存劣势，压缩列表在元素长度不大或者元素个数不多时，会被列表对象采纳为底层数据结构。压缩列表的示意图能够示意如下。

struct ziplist<T> {
    // 整个压缩列表占用字节数
    int32 zlbytes;
    // 最初一个 entry 间隔压缩列表起始地位的字节数
    int32 zltail_offset;
    //entry 个数
    int16 zllength;
    //entry 数组
    T[] entries;
    // 压缩列表的完结标记，0xFF
    int8 zlend;
}

借助压缩列表的 zlbytes，zltail_offset 和zllength字段，定位到压缩列表的第一个 entry 和最初一个 entry 的工夫复杂度是 O(1)，然而查找entry 的工夫复杂度是 O(N)，所以压缩列表的元素个数不宜太多。entry 数据结构如下所示。

struct entry {
    // 前一个 entry 的字节
    int<var> prevlen;
    //entry 的内容的类型和长度
    int<var> encoding;
    //entry 的内容
    optional byte[] content;}

entry中的 prevlen 字段和 encoding 字段都是可变长度，它们依照如下规定变动。

• 如果前一个 entry 的长度小于 254 字节，则 prevlen 字段长度为 1 字节；
• 如果前一个 entry 的长度大于等于 254 字节，则 prevlen 字段长度为 5 字节；
• 如果以后 entry 的内容是整数，则 encoding 字段长度为 1 字节；
• 如果以后 entry 的内容是字符串，则依据字符串的大小的不同，encoding字段长度为 1 字节，2 字节或 5 字节。

插入数据时，依据插入数据的类型和大小的不同，prevlen字段和 encoding 字段会动态变化，这就是 Redis 应用压缩列表来节约空间的思维。然而相应的会产生如下的问题。

• 往压缩列表插入，更新和删除数据时，可能会导致某些 entry 的prevlen字段发生变化，极其状况下这个变动会向后逐级传递，造成压缩列表的级联更新；
• 压缩列表级联更新时，会屡次从新分配内存，使得压缩列表的性能好转。

因而鉴于压缩列表的个性，Redis中的列表对象在存储元素小于 64 字节，元素个数小于 512 个时才会应用压缩列表作为底层数据结构，为的就是防止级联更新的产生。

四. 哈希对象

哈希对象与底层数据结构对应关系如下。

• 哈希对象存储的元素的键和值的长度小于 64 字节，元素个数小于 512 时，该哈希对象底层数据结构应用压缩列表；
• 其它状况，该哈希对象底层数据结构应用字典。

上面对字典 dict 进行剖析。字典数据结构定义如下。

typedef struct dict {
  dictType *type;
  // 公有数据
  void *privdata;
  // 哈希表
  dictht ht[2];
  //rehash 时的索引
  int trehashids; 
} dict;

Redis中的字典是基于哈希表实现，并且一个字典中持有两张哈希表。哈希表 dictht 数据结构定义如下。

typedef struct dictht {
    // 节点数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，计算索引
    //sizemask = size - 1
    unsigned long sizemask;
    // 哈希表以后节点数
    unsigned long used;
} dictht;

和 Java 中的 HashMap 相似，哈希表中有一个存储元素的节点数组，每个键值对会被封装成一个 dictEntry 节点而后增加到节点数组中。哈希表节点 dictEntry 数据结构定义如下。

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下一个节点
    struct dictEntry *next;
} dictEntry;

当存在哈希抵触时，会转变为链表以解决哈希抵触，dictEntry中的 next 字段指向链表的下一个节点。

那么基于上述数据结构，Redis中的字典能够用下图进行示意。

字典持有两张哈希表，别离为 ht[0] 和ht[1]，在失常状况下，均会应用 ht[0]，ht[1] 不会被分配内存空间。当字典须要扩容或者缩容时，会对字典中的键值对进行 rehash 操作，此时会应用到ht[1]，具体规定如下。

• 先为 ht[1] 分配内存空间。如果是扩容，则 ht[1] 的size为大于等于 ht[0].used * 2 且同时为 2 的幂次方的最小值，如果是缩容，则 ht[1] 的size为大于等于 ht[0].used 且同时为 2 的幂次方的最小值；
• 将 ht[0] 中的键值对从新计算索引，而后寄存到 ht[1] 中；
• ht[0]的所有键值对全副寄存到 ht[1] 中后，开释 ht[0] 的内存空间，而后 ht[1] 变为ht[0]。

当字典中键值对特地多时，rehash会特地耗时，所以 Redis 采纳一种 渐进 rehash的形式来实现扩缩容，字典中的 trehashids 字段用于记录以后曾经 rehash 到的索引，Redis会逐渐将 ht[0] 中的键值对 rehash 到ht[1]上，并更新 trehashids 字段，与此同时 Redis 也会失常提供缓存性能，且如果有新增的键值对，也会间接寄存到 ht[1] 中，上述过程会继续到 ht[0] 上的键值对全副寄存到 ht[1]，此时开释ht[0] 的内存空间，而后 ht[1] 变为ht[0]。

五. 汇合对象

汇合对象与底层数据结构对应关系如下。

• 汇合对象存储的元素都是整数值，元素个数不超过 512 个时，该汇合对象底层数据结构应用整数汇合；
• 其它状况，该汇合对象底层数据结构应用字典。

六. 有序汇合对象

有序汇合对象与底层数据结构对应关系如下。

• 有序汇合对象存储的元素长度小于 64 字节，元素个数小于 128 个时，该有序汇合对象底层数据结构应用压缩列表；
• 其它状况，有序汇合对象底层数据结构应用跳表。

对于跳表数据结构，将在后续的文章中学习。

总结

Redis中一共有五种对象类型，每种对象类型会依据元素类型，元素大小和元素数量的不同而采纳不同的底层数据结构，所以可能搞明确 Redis 中的对象类型，也就搞明确了 Redis 中的数据结构。