• 通过这五种不同类型的对象，Redis 可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。适配场景
• 使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率，提升效率
• Redis 的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放，内存回收
• Redis 还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存，节约内存
• Redis 的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了 maxmemory 功能的情况下，空转时长较大的那些键可能会优先被服务器删除，内存回收
• 每次当我们在 Redis 的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。Redis 中的每个对象都由一个 redisObject 结构表示，该结构中和保存数据有关的三个属性分别是type 属性、encoding 属性和 ptr 属性：

redisObject 结构：
    typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    ….. 
}

• 对象的type 属性记录了对象的类型，REDISSTRING、REDISHASH、REDISLIST、REDISSET、REDIS_ZSET，对于 Redis 数据库保存的键值对来说，键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种
• 对象的encoding 属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，接下来会详细介绍下使用的数据编码
• 对象的ptr 指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding 属性决定
• 也就是一个对象包含自身的数据结构属性，实际使用的编码类型以及数据对象对实际数据编码的指针。

数据对象和数据结构

在 Redis 中会涉及很多数据结构，比如SDS，双向链表、字典、压缩列表、整数集合、跳跃表等。数据结构有如下几种：

每种类型的对象都至少使用了两种不同的编码，在内容长短发生变化的时候数据对象会自动切换适合的数据编码，且切换后不可逆

Redis 数据结构

在介绍数据对象与数据结构的转换关系之前，先来了解下 Redis 的几种数据结构：动态字符串、字典、链表、整数集合、压缩列表、跳跃表+字典。

动态字符串 SDS

SDS 的数据结构如下，包含三部分属性，len、free 以及 buf 数组，用来描述一个 SDS 的结构体：

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

动态字符串结构

示例如下图所示：

• free 属性的值为 5，表示这个 SDS 分配了 5 字节的未使用空间
• len 属性的值为 5，表示这个 SDS 保存了一个五字节长的字符串，需要注意的是长度不包含末尾的补 0
• buf 属性是一个 char 类型的数组，数组的前五个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存了空字符'\0'
  保留了 C 语言补 0 的习惯是为了方便复用 C 语言的一些函数。

动态字符串优点

SDS 的优势如下：

• 常数复杂度获取字符串长度，因为 SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为 O（1）
• 杜绝缓冲区溢出，SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小
• 减少修改字符串时带来的内存重分配次数，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联 ：在 SDS 中，buf 数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录
• 空间预分配策略，如果对 SDS 进行修改之后，SDS 的长度（也即是 len 属性的值）将小于 1MB，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS len 属性的值将和 free 属性的值相同，如果对 SDS 进行修改之后，SDS 的长度将大于等于 1MB，那么程序会分配 1MB 的未使用空间。也就是说 1M 以下倍增，1M 以上只增加 1M，防止存储过大对象，通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数
• 惰性空间释放策略，惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。SDS 也提供了相应的 API，在有需要时，我们可以真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费通过惰性空间释放策略，Redis 可以减少执行字符串缩短操作所需的内存重分配次数
• 二进制安全，SDS 的 API 都是二进制安全的（binary-safe），所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样，例如，使用 SDS 来保存包含空字符格式的数据格式就没有任何问题，因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据
  总而言之，动态字符串用额外的 free 和 len 空间来弥补了很多 C 语言性能上的问题。

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度，但是由于 C 语言没有链表的数据结构，所以 Redis 的链表是自己定义的结构。

链表结构

链表单节点的数据结构如下，包含三部分属性prev、next 以及 value，用来描述一个链表单节点的结构体：

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

示例如下图所示：

同时 Redis 为了方便的操作链表，提供了一个 list 结构来持有链表，也就是我们的链表结构，如下所示

在这里插入图片描述 list 结构为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数：

• dup 函数用于复制链表节点所保存的值
• free 函数用于释放链表节点所保存的值
• match 函数则用于对比链表节点所保存的值和另一个输入值是否相等

用代码来描述如下所示：

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;

链表结构优势

链表结构的优势其实在很多语言中都有体现，在 Redis 这里由于特殊的设计结构，又有些不一样的地方，总而言之如下：

• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O（1）
• 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点
• 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O（1）
• 带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O（1）
• 多态：链表节点使用 void*指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
• 正是由于这些优势，链表编码有广泛的用途：比如Redis 列表数据对象、发布与订阅、慢查询、监视器等

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构，字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对

• Redis 数据库就是一个字典模型，key 和 value 组成
• 同时hash 对象的底层实现之一也包括字典
  总而言之，字典有较为广泛的用途，但是同链表一样，C 语言没有字典这种数据结构，所以 Redis 自己实现了这种结构。

字典结构

字典是由哈希表加上一系列属性方法组成，而哈希表又是由哈希表节点加上一系列哈希表结构组成的：

哈希表节点

哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对，但是有链式结构：

typedef struct dictEntry {

    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

各个属性部分如下：

• key 属性保存着键值对中的键
• v 属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个 uint64t 整数，又或者是一个 int64t 整数。
• next 属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题

也就是说在相同键上的多个哈希表节点存在链式关系，有链表实现。

哈希表

哈希表结构定义如下，包括哈希表数组，哈希表大小【已用+未用】的变量，哈希表大小的掩码值，哈希表已有节点数量

typedef struct dictht {

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

} dictht;

各个属性部分如下：

• table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对
• size 属性记录了哈希表的大小，也即是 table 数组的大小
• used 属性则记录了哈希表目前已有节点（键值对）的数量
• sizemask 属性的值总是等于 size-1，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面
  其中 table 是我们这个结构的核心。
  

字典又是由哈希表和一系列属性和函数组成的，为了满足 Redis 快而增加的一些空间占用属性：

typedef struct dict {

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

} dict;

各个属性含义如下：

• type 属性和 privdata 属性是针对不同类型的键值对，而创建多态字典而设置的：type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一组用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同类型的特定函数。而 privadata 属性则保存了需要传给那些类型特定函数的可选参数。
• ht 属性是一个包含了两个项的数组，数组中每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0]哈希表，而 ht[1]哈希表只对 ht[0]哈希表进行 rehash 时使用。
• rehashidx 属性，与 rehash 相关，它积累了 rehash 目前的进度，如果没有进行 rehash，则它的值为-1

关于 rehash 算法在接下来的内容重点看，其中 ht 属性是较为核心的属性。

哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面：

• 使用字典设置的哈希函数，计算键 key 的哈希值 hash = dict->type->hashFunction(key);
• 使用哈希表的 sizemask 属性和哈希值，计算出索引值，index = hash & dict->ht[x].sizemask，根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]，

举个例子，假设 hash 计算结果为 8，且掩码为 3，则相与的结果为 0，所以被放到 ht[0]哈希表的字典索引 0 的位置

解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。Redis 的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题：

另外因为 dictEntry 节点组成的链表没有指向链表表尾的指针，为了考虑速度，程序总是将新节点添加到链表的表头位置（这样添加节点的时间复杂度为 O(1)）

rehash

随着操作的不断进行，哈希表保存的键值对会逐渐增多或减少，为了让哈希表负载因子【哈希表已保存节点数量/哈希表的 size，可以理解为 used/size】维持在一个合理范围之内，当哈希表保存的键值对太多或太少时，程序要对哈希表的大小进行相应的扩展或收缩。

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

1.为字典的 ht[1]哈希表分配空间，这个空间大小取决于要执行的操作

• 如果执行扩展操作，则 ht[1]的大小为第一个大于等于等于 ht[0].used*2 的 2^n；

• 如果执行收缩操作，则 ht[1]的大小为第一个大于等于 ht[0].used 的 2^n；当哈希表负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作
  
  2.将保存在 ht[0]中的所有键值对 rehash 到 ht[1]上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1]的指定位置上。
  
  3.当 ht[0]包含的所有键值对都迁移到 ht[1]之后，释放 ht[0]，将 ht[1]设置为 ht[0]，并在 ht[1]新创建一个空白哈希表，为下一次 rehash 做准备。
  
  以上就是 rehash 的全流程。当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

• 1）服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1

• 2）服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5。

BGSAVE 或 BGREWRITEAOF 操作是 Redis 的持久化操作，在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）【只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程】技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。

渐进式 rehash

Redis 中的 rehash 动作并不是一次性、集中式完成的，而是分多次、渐进式的完成的。这样做的目的是，如果服务器中包含很多键值对，要一次性的将这些键值对全部 rehash 到 ht[1]的话，庞大的计算量可能导致服务器在一段时间内停止服务。渐进式 Rehash 操作

1.为 ht[1]分配空间，让字典同时持有 ht[0]和 ht[1]两个哈希表。在字典中维持一个索引计数器变量 rehashidx，并将它置为 0，表示 rehash 工作开始。

2.在 rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定操作以外，还会顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]中，当 rehash 工作完成之后，程序将 rehashidx 属性的值+1。

3.随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都被 rehash 到 ht[1]上，这时将 rehashidx 属性设为-1，表示 rehash 完成。

渐进式 rehash 的好处在于其采取分而治之的方式，将 rehash 键值对所需要的计算工作均摊到字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量：

• 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在 ht[0]里面进行查找，如果没找到的话，就会继续到 ht[1]里面进行查找，诸如此类。
• 在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 ht[1]里面，而 ht[0]则不再进行任何添加操作，这一措施保证了 ht[0]包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表
• 这样又是一个以空间换取时间的案例。参考《Redis 的设计与实现》