最近读了《Redis 设计与实现》，知道了Redis在存储对象中做了很多的优化，利用各种不同的存储结构实现, 减少了内存消耗，加快了增删改查的速度。这里做一下记录，方便查看。

[TOC]

1. Redis对象的类型

Redis 支持五种类型的对象，在内部由一个 redisObeject 对象表示，数据定义如下：

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;

1. type 对应 Redis 中的五种基本数据类型：

2. Encoding对应的编码:

3. type 与 Encoding 的对应关系

2. 对象存储中的编码Encoding简单解释

2.1REDIS_STRING 类型的编码

如上面 type 与 Encoding 对应关系表所说。 String 类型根据不同的情况使用三种不同的编码格式进行存储：REDIS_ENCODING_INT,REDIS_ENCODING_EMBSTR,REDIS_ENCODING_RAW.下面介绍一下它们的异同，以及使用的优缺点：

REDIS_ENCODING_INT

Redis String int

使用条件： 整数集合intset是 Redis 用户保存整数值的集合抽象数据结构，它不会出现重复值。当一个集合只包含整数元素时，并且这个集合的元素数量不多时，Redis 会使用整数集合作为集合键的底层实现。
说明： intset.h/intset

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

encoding：这里的encoding指定了 contents 数组代表的格式。可以指定为：

INTSET_ENC_INT16: 指定contents数组的格式为 int16_t 类型
INTSET_ENC_INT32: 指定contents数组的格式为 int32_t 类型
INTSET_ENC_INT64: 指定contents数组的格式为 int64_t 类型

image

整数集合的升级：

当一个新的整数元素被加入到数组中时，如果它的位数比指定的 encoding 位数大，那么集合需要进行升级，然后才能将元素添加到整数集合中去。另外，Redis 整数集合中的元素只能升级，而不支持降级。另外整数集合在使用时，里面的元素会自动排序。

• 提升灵活性：可以随意将不同类型的元素添加到集合中，而不用担心类型错误
• 节约内存

REDIS_ENCODING_EMBSTR

REDIS_ENCODING_RAW

Redis String Embstr Raw

REDIS_ENCODING_EMBSTR 与 REDIS_ENCODING_RAW都是是SDS Simple Dynamic String 类型的，底层实现是一样的，这里先看下原理：

struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

image

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

• 空间预分配:
  • 当对SDS进行修改时，SDS的长度小于 1 MB，那么程序会额外分配与len属性相同的未使用空间，这是 free 与 len的值应该是相同
  • 当SDS大于 1 MB 时，SDS会分配 1MB的额外空间。如果进行修改后SDS的长度为 30 MB，那么buf数组的实际长度是 30 MB + 1 MB + 1 byte
• 惰性空间
  • 当SDS中的字符串缩短时，程序并不会立即使用内存重分配来回收缩短后的多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用

REDIS_ENCODING_EMBSTR 与 REDIS_ENCODING_RAW 的区别：

embstr 编码是专门用于保存短字符串的一种优化编码方法，这种编码和 raw编码一样，都使用redisObject结构 和 sdshdr 结构来表示字符串对象，但 raw编码会调用两次内存分配函数来分别创建redisObject结构与sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的内存空间，空间中依次包含redisObject 和 sdshdr 两个结构

2.2 REDIS_LIST 类型的编码

REDIS_ENCODING_ZIPLIST

Redis ZipList 压缩表

REDIS_ENCODING_LINKEDLIST

Redis中的LinkedList

节点的表示

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

链表的表示：

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;

image

特点：

• 双端链表，没有环
• 带有表头指针与表尾指针
• 带有链表长度计数器
• 多态：链表节点使用 void* 指针来保存节点值，并且可以通过list结构的dup，free，match三个属性为节点设置类型特定函数

2.3 REDIS_HASH 类型的编码

REDIS_ENCODING_ZIPLIST

REDIS_ENCODING_HT

Redis HT（hash table）

字典的哈希表：

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;

image

字典：

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

上图是 Redis 字典中的哈希表, Redis 中的字典是由容量为2的哈希表数组组成。 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

image

• 解决键冲突：Redis的字典采用链地址法解决键冲突

• Rehash：随着操作的进行，字典中的键值对会逐渐增多或者减少，为了让哈希表的负载因子维持在一个范围内，需要对于哈希表进行扩容或者收缩操作，这些可以通过Rehash来完成.

  例如扩容，会通过ht数组另一个位置的哈希表来完成：当ht[0]中的元素，需要进行扩容时，会首先扩容ht[1]中的哈希表的容量为2 * ht[0](保持2的n次幂)，然后将ht[0] 中的元素rehash为ht[1]中的元素，完成迁移。

• 渐进式Rehash

  进行上面所说的 Rehash 时，如果存在大量的键值对，不可能一次性，或者集中式的迁移（把在ht[0]的键值Rehash迁移到ht[1]）。因此需要渐进式的进行Rehash。

  例如上面的扩容，字典会同时维护这两个哈希表，每当对字典进行操作时，才会将ht[0]中某个哈希值对应的所有的键值Rehash到ht[1];

2.4 REDIS_SET 类型的编码

REDIS_ENCODING_INTSET

REDIS_ENCODING_HT

2.5 REDIS_ZSET 类型的编码

REDIS_ENCODING_ZIPLIST

Redis ZipList 压缩表

ZipList节点的组成：

image

• previous_entry_length: 记录压缩列表前一个节点的长度
• encoding：记录了节点的 content 属性所保存数据的类型以及长度：
• content：记录保存节点的值

压缩列表中的结构：

image

• **zlbytes **:当前列表所占用的内存字节数
• zltail：尾节点距离压缩列表起始位置的偏移量
• zllen：记录了压缩列表包含的节点数
• entryX：压缩列表中的节点
• zlend ：0xFF，用于标记压缩列表的末端

• 连锁更新

  每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

  • 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

考虑这样一种情况：

image

• 在一个压缩列表中，有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN 。
• 这时，如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点，那么 new 将成为 e1 的前置节点
• e1 的 previous_entry_length 属性仅长 1 字节，它没办法保存新节点 new 的长度，所以程序将对压缩列表执行空间重分配操作，并将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。
• 现在，麻烦的事情来了 —— e1 原本的长度介于 250 字节至 253 字节之间，在为 previous_entry_length 属性新增四个字节的空间之后，e1 的长度就变成了介于 254 字节至 257 字节之间，而这种长度使用 1 字节长的 previous_entry_length 属性是没办法保存的。
• 为了让 e2 的 previous_entry_length 属性可以记录下 e1 的长度，程序需要再次对压缩列表执行空间重分配操作，并将 e2 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。
• 正如扩展 e1 引发了对 e2 的扩展一样，扩展 e2 也会引发对 e3 的扩展，而扩展 e3 又会引发对 e4 的扩展……为了让每个节点的 previous_entry_length 属性都符合压缩列表对节点的要求，程序需要不断地对压缩列表执行空间重分配操作，直到 eN 为止。

压缩表的特点：

• 节约内存

缺点：

• 插入与删除操作时间复杂度O(n),最坏情况O(n)

• 查找时间复杂度O(n)

REDIS_ENCODING_SKIPLIST

Redis SkipList 跳跃表

跳跃表节点的实现是通过 redis.h/zskiplistNode 实现的：

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

} zskiplistNode;

跳跃表：

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

image

Redis中的的跳跃表包含以下结构：

• header：指向跳跃表的表头节点
• tail：指向跳跃表的表尾节点
• level：记录目前跳跃表内，层数最大节点的所在的层数
• length：记录跳跃表的长度，也是目前跳跃表所包含的元素

跳跃表节点，跳跃表节点Redis中的定义在上面：

• backward：后退指针，图中节点中的 BW。用于由表尾向表头搜索
• score：分值，跳跃表中的节点根据该值进行排序
• obj：各个节点保存的对象
• level：跳跃表中的核心，层次，每一层包含前进指针与跨度。

这里简单说下跳跃表：

漫画算法：什么是跳跃表？

浅析SkipList跳跃表原理及代码实现

1. 跳跃表的层次生成
   每个层次的节点由上一层的节点中产生，产生的方法，应该是对上一层的节点进行随机，随机决定当前节点是否需要显示在下一层。上面说因为跳跃表删除和添加的节点是不可预测的，很难使用一种有效的算法保证跳表的索引部分。

2. 跳跃表的查询

   • 查询由最高层开始，当查找到当前节点比查找节点大的时候，进行回退上一个节点

   • 回退到上一个节点后，level层次减少，由下一层的当前节点开始查找

3. 跳跃表的节点增加

   • 节点的增加，需要先查找到插入节点应该插入的位置
   • 然后决定该节点是否入选每个层次的节点中，构建节点在跳跃表需要显示的层次中

4. 跳跃表的节点删除

   • 节点的删除也是需要先查找到删除节点所在的位置
   • 除了删除当前的节点，还需要删除层次中所有的该节点

3. 对象对于存储结构的选择

上面介绍了一些 Redis 存储结构的一些基本概念，对于 Redis 而言，每种 Type 类型都有超过两种类型可以进行选择，那到底什么时候使用什么对象呢？这里对于 《Redis 设计与实现》所述做一些总结。这里先看下每种对象可以选择的数据存储结构。

• String

• List

• Hash

• Set

• ZSet

参考：
1. <<Redis 设计与实现>>
2. 漫画算法：什么是跳跃表？
3. 浅析SkipList跳跃表原理及代码实现