[TOC]

Redis 设计与实现

第1章：概览

第一部分：数据结构与对象

redis数据库里面的每个键值对都由对象组成，其中：

键总是一个字符串对象

值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象

第二部分：单机数据库的实现

第9章：数据库。介绍数据库的实现原理，说明了：

服务器保存键值对的方法

服务器保存键值对过期时间的方法

服务器自动删除过期键值对的方法

第10章：RDB持久化和第11章：AOF持久化。分别介绍Redis的两种持久化方式，说明了：

服务器根据数据库生成持久化文件的方法，服务器根据持久化文件还原数据库的方法

BGSAVE命令和BGREWRITEAOF命令的实现原理

第12章：事件。介绍文件事件和时间事件

文件事件：用于应答（accept）客户端的连接请求，接收客户端的命令请求，向客户端返回命令回复

时间事件：执行redis.c/serverCron函数，该函数保持Redis服务器正常运行，触发定时操作

第13章：客户端。介绍服务器维护和管理客户端状态的方法，客户端状态的属性，客户端的输入和输出缓冲区，服务器创建和销毁客户端状态的条件

第14章：服务器。介绍单机服务器的运作机制，服务器处理命令请求的步骤，serverCron函数，服务器初始化过程

第三部分：多机数据库的实现

第15章：复制。介绍Redis主从复制

第16章：Sentinel。说明Sentinel监视服务器的方法，判断服务器是否下线的方法，对下线服务器进行故障转移的方法。

第17章：集群。说明节点的构建方法，节点处理命令请求的方法，转发错误的实现，各节点通信的方法

第四部分：独立功能的实现

第18章：发布与订阅。PUBLISH、SUBSCRIBE、PUBSUB等命令

第19章：事务。MULTI、EXEC、WATCH等命令，说明Redis的事务对ACID性质的支持程度

第20章：Lua脚本。EVAL、EVALSHA、SCRIPT LOAD等命令，解释Redis服务器如何执行和管理用户传入的Lua脚本，服务器构建Lua环境的过程，主从服务器之间复制Lua脚本的方法

第21章：排序。SORT命令和命令选项（DESC、ALPHA、GET）以及不同选项执行的顺序

第22章：二进制位数组。GETBIT、SETBIT、BITCOUNT、BITOP命令

第23章：慢查询日志。SLOWLOG GET、SLOWLOG LEN、SLOWLOG RESET命令

第24章：监视器。如何将客户端变为监视器（monitor），服务器如何向监视器发送命令信息

第一部分：数据结构与对象

第2章：简单动态字符串（SDS）

Redis没有直接使用C字符串，在Redis里C字符串只会作为字符串字面量，用在无须修改字符串值的地方。当Redis需要一个可以被修改的字符串值时会使用SDS。SDS不仅可以用来保存字符串值，还能被用作缓冲区：AOF缓冲区、客户端状态中的输入缓冲区。

2.1：SDS的定义

每个sds.h/sdshdr结构表示一个SDS值：

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

SDS和C字符串一样，以空字符结尾。保存空字符的1字节不算在len属性里，SDS自动为空字符分配额外的1字节且将空字符添加到字符串末尾。所以这个空字符对用户完全透明。以空字符结尾的好处是SDS可以重用C字符串函数库里面的一部分函数。

2.2：SDS与C字符串的区别

2.2.1：常数复杂度获取字符串长度

C字符串不记录自身的长度信息，所以为获取其长度需要遍历一遍。

获取一个SDS的长度只要常数时间，设置和更新SDS长度的工作由SDS的API在执行时自动完成。

2.2.2：杜绝缓冲区溢出

C字符串假定用户已经分配足够多的内存，若该假定不成立，就会产生缓冲区溢出。

当SDS API需要修改SDS时，API会先检查SDS的空间是否满足，若不满足，API会自动扩展空间，然后执行修改。无须手动修改SDS的空间大小。

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

每次增长或缩短一个C字符串，程序都要对其数组进行一次内存重分配。

SDS通过未使用空间实现了空间预分配和惰性空间释放两种优化策略。

空间预分配：当需要对SDS进行空间扩展时，程序不仅分配必须的空间，而且还会分配额外的未使用空间。额外空间数量由以下公式决定：

若SDS的长度在修改后小于1MB，分配len大小的未使用空间，此时len=free。否则，分配1MB大小。

惰性空间释放：当SDS的API需要缩短字符串时，程序不立即释放其空间，而是使用free属性记录字节数量，等到将来使用。

此外，SDS提供了API让我们在需要时真正地释放SDS的未使用空间。

2.2.4：二进制安全

C字符串必须符合某种编码，且除了字符串末尾外，字符串里面不能包含空字符。这些限制使其只能保存文本数据，而不能保存图片、音频、视频、压缩文件等二进制数据。

所有SDS API都会以处理二进制的方式来处理buf数组（字节数组）里面的数据。SDS用len的值而不是空字符来判断字符串是否结束。

2.2.5：兼容部分C字符串函数

SDS遵循C字符串以空字符结尾的惯例，这使得保存文本数据的SDS可以重用一部分库定义的函数。

2.2.6：总结

C字符串	SDS
获取字符串长度的复杂度为O(N)	获取字符串长度的复杂度为O(1)
API不安全，可能会造成缓冲区溢出	API安全，不会造成缓冲区溢出
修改字符串长度N次必然执行N次内存重分配	修改字符串长度N次最多执行N次内存重分配
只能保存文本数据	可以保存文本数据或二进制数据
可以使用库中的所有函数	可以使用部分库中的函数

2.3：SDS API

函数	作用	时间复杂度
sdsnew	创建包含给定C字符串的SDS	O(N)，N为字符串长度
sdsempty	创建不包含任何内容的空SDS	O(1)
sdsfree	释放给定的SDS	O(N)，N为被释放SDS的长度
sdslen	返回SDS已使用空间字节数	len属性，O(1)
sdsavail	返回SDS未使用空间字节数	free属性，O(1)
sdsdup	创建一个给定SDS的副本（copy）	O(N)
sdsclear	清空SDS保存的字符串内容	惰性空间释放，O(1)
sdscat	将给定C字符串拼接到SDS字符串末尾	O(N)，N为给定C字符串的长度
sdscatsds	将给定SDS字符串拼接到另一个SDS末尾	O(N)，N为给定SDS字符串的长度
sdscopy	将给定C字符串复制到SDS里，覆盖SDS原有字符串	O(N)，N为给定C字符串的长度
sdsgrowzero	用空字符将SDS扩展至给定长度	O(N)，N为新增字节数
sdsrange	保留SDS给定区间内数据，其他数据被覆盖或清除	O(N)，N为被保留数据字节数
sdstrim	接受一个SDS和一个C字符串作为参数，从SDS左右两端分别移除所有在C字符串中出现过的字符	O(M*N)，M为SDS长度，N为C字符串长度
sdscmp	比较两个SDS字符串是否相同	O(N)，N为较短SDS的长度

2.4：重点回顾

Redis只会使用C字符串作为字面量，大多情况下，Redis使用SDS表示字符串。

SDS具有如下优点：

常数复杂度获取字符串长度
杜绝缓冲区溢出
减少修改字符串长度时所需的内存重分配次数
二进制安全
兼容部分C字符串库函数

第3章：链表

链表用在：列表键实现、发布与订阅、慢查询、监视器、保存客户端状态信息、构建客户端输出缓冲区等

3.1：链表和链表节点的实现

链表节点adlist.h/listNode

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

使用adlist.h/list来持有链表，使链表操作更方便

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;

dup、free、match成员用于实现多态链表所需的类型特定函数。

双端链表迭代器结构

typedef struct listIter {
    // 当前迭代到的节点
    listNode *next;
    // 迭代的方向
    int direction;
} listIter;

Redis链表实现特性：

双端、无环（表头节点的prev和表尾节点的tail都指向NULL，对链表的访问以NULL为终点）
带表头指针和表尾指针（list结构的head指针和tail指针）
带链表长度计数器（list结构的len属性）
多态：链表节点使用void*指针保存节点值，且可以通过list结构的dup、free、match属性为节点值设置类型特定函数，所以链表可以保存各种类型的值。

3.2：链表和链表节点的API

函数	作用
listSetDupMethod	将给定函数设置为链表的节点值复制函数
listGetDupMethod	返回链表当前正在使用的节点值复制函数
listSetFreeMethod	将给定函数设置为链表的节点值释放函数
listGetFree	返回链表当前正在使用的节点值释放函数
listSetMatchMethod	将给定函数设置为链表的节点值对比函数
listGetMatchMethod	返回链表当前正在使用的节点值对比函数
listLength	返回链表长度
listFirst	返回链表表头节点
listLast	返回链表表尾节点
listPrevNode	返回给定节点的前置节点
listNextNode	返回给定节点的后置节点
listNodeValue	返回给定节点当前保存的值
listCreate	创建一个不包含任何节点的新链表
listAddNodeHead	将一个新节点添加到链表表头
listAddNodeTail	将一个新节点添加到链表表尾
listInsertNode	将一个新节点添加到给定节点之前或之后
listSearchKey	查找并返回链表中包含给定值的节点
listIndex	返回链表在给定索引上的节点
listDelNode	从链表中删除给定节点
listRotate	将链表表尾节点弹出并插入到链表表头
listDup	复制一个给定链表的副本
listRelease	释放给定链表以及链表中的所有节点

第4章：字典

Redis数据库使用字典作为底层实现，对数据库的增删改查都基于字典的操作。

字典也是哈希键的底层实现之一。

4.1：字典的实现

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

4.1.1：哈希表

dict.h/dictht结构，其中table是一个数组，保存指向dict.h/dictEntry结构的指针，每个dictEntry保存一个键值对。

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

4.1.2：哈希表节点

dictEntry结构，保存键值对

typedef struct dictEntry{
    // 键
    viod *key;
    // 值，可以是一个指针、uint64_t整数或int64_t整数
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    // 指向下个哈希表节点，链地址法解决哈希冲突
    struct dictEntry *next;
}dictEntry;

4.1.3：字典

dict.h/dict结构

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

type和privdata属性针对不同类型的键值对，为创建多态字典设置：

type属性为指向dictType结构的指针，每个dictType保存一簇用于操作特定类型键值对的函数。
privdata属性保存需要传给类型特定函数的可选参数

typedef struct dictType{
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata,const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata,const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata,const void *key1,const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata,void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata,void *obj);
}dictType;

ht属性是一个包含两个项的数组，其中每项是一个dictht哈希表，ht[1]只会在对ht[0]进行rehash时使用。

rehashidx属性记录目前rehash的进度，若没有进行rehash，其值为-1。

4.2：哈希算法

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

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

当字典用于数据库或哈希键底层实现时，Redis使用MurmurHash2算法计算键的哈希值。该算法优点在于，即使输入的键是有规律的，算法仍有很好的随机分布性，且算法的计算速度非常快。

4.3：解决键冲突

Redis的哈希表使用链地址法来解决键冲突。

因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度，程序总将新节点添加到链表表头。

4.4：Rehash

随着操作不断执行，哈希表中的键值对会逐渐增多或减少，为了让哈希表的负载因子维持在合理范围，程序需要对哈希表大小进行扩展或收缩。rehash(重散列)步骤如下：

为字典的ht[1]哈希表分配空间，大小取决于执行的操作以及ht[0]当前包含的键值对数量（ht[0].used）
- 若执行扩展操作，ht[1]的大小为第一个大于等于ht[0].used2的*$2^n$；
- 若执行收缩操作，ht[1]的大小为第一个大于等于ht[0].used的$2^n$。
将ht[0]中的所有键值对rehash到ht[1]上：rehash指重新计算键的哈希值和索引值，然后将键值对放到ht[1]的指定位置。
当ht[0]包含的所有键值对都迁移到了ht[1]后（ht[0]变为空表），释放ht[0]，将ht[1]设为ht[0]，最后为ht[1]分配一个空白哈希表，为下一次rehash做准备。

哈希表的扩展与收缩

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

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

哈希表负载因子=哈希表已保存节点数量/哈希表大小：load_factor=ht[0].used/ht[0].size

在执行BGSAVE或BGREWRITEAOF命令时，需要创建当前服务器进程的子进程，且大多OS都采用写时复制技术优化子进程效率。所以在子进程存在期间，服务器会提高执行扩展操作的负载因子，从而尽可能避免在子进程存在期间进行哈希表扩展，避免不必要的内存写入操作，最大限度节约内存（写内存时会复制）

当负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

4.5：渐进式rehash

当扩展或收缩哈希表时，rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。原因在于如果哈希表保存的键值对数量很庞大时，要一次性将其rehash的话，可能会导致服务器在一段时间内停止服务。以下是哈希表渐进式rehash的步骤：

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
在字典中维持一个索引计数器变量rehashidx，并将其设为0，表示rehash工作开始
在rehash期间，每次对字典执行增删改查操作时，程序除了执行该指定操作，还会顺便将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，然后将rehashidx加一。
随着对字典不断操作，最终ht[0]所有键值对都会被rehash到ht[1]，这时程序将rehashidx设为-1，表示rehash操作完成。

渐进式rehash将rehash键值对所需的计算工作均摊到对字典的每个增删改查操作上，避免了集中式rehash带来的庞大计算量。

渐进式rehash执行期间的哈希表操作

因为在渐进式rehash期间，字典会同时使用ht[0]和ht[1]，所以在此期间，字典的删除、更新、查找操作会在两个哈希表上进行。例如，查找会先在ht[0]查找，没找到会在ht[1]继续查找。

另外，在渐进式rehash期间，新添加到字典的键值对会一律保存到ht[1]中，ht[0]上不进行任何添加操作，保证ht[0]包含的键值对数量不断减少，并随着rehash操作最终变为空表。

4.6：字典API

函数	作用
dictCreate	创建新字典O(1)
dictAdd	添加给定键值对O(1)
dictReplace	添加给定键值对，如果键已经存在，替换其值O(1)
dictFetchValue	返回给定键的值O(1)
dictGetRandomKey	随机返回一个键值对O(1)
dictDelete	删除给定键的键值对O(1)
dictRelease	释放字典以及字典中的所有键值对O(N)

第5章：跳跃表

有序数据结构，通过在每个节点中维持多个指向其他节点的指针来达到快速访问节点的目的。支持平均$O(logN)$、最坏$O(N)$复杂度的节点查找，还能通过顺序性操作来批量处理节点。Redis使用跳跃表作为有序集合键的底层实现之一。

Redis只在两个地方用到了跳跃表：实现有序集合键、在集群节点中用作内部数据结构

5.1：跳跃表的实现

Redis跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，前者表示跳跃表节点，后者保存跳跃表相关信息（节点数量、表头节点、表尾节点等）

5.1.1：跳跃表节点

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

层：跳跃表节点的level数组可包含多个元素，每个元素包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度。每次创建一个新的跳跃表节点时，都根据幂次定律（越大的数出现的概率越小）随机生成一个介于1到32之间的值作为level数组的大小，该大小为层的“高度”。
前进指针：每个层包含一个指向表尾方向的前进指针。
跨度：用于记录两个节点间的距离。指向NULL的所有前进指针跨度为0。跨度用来计算排位：在查找某个节点时，将沿途经过的层的跨度累计便得到目标节点在跳跃表中的排位
后退指针：用于反向访问跳跃表，只有一个。
分值和成员：分值为double类型，所有节点按分值从小到大排序；成员对象是一个指针，指向SDS对象。在同一跳跃表中，各节点保存的成员对象必须唯一，而分值可以相等：分值相等则按成员对象字典序排序
只会用到表头节点的各个层，其他属性不会被用到。

5.1.2：跳跃表

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

5.2：跳跃表API

函数	作用	时间复杂度
zslCreate	创建跳跃表	O(1)
zslFree	释放跳跃表及其所有节点	O(N)
zslInsert	将包含给定成员和分值的节点加入跳跃表	平均O(logN)，最坏O(N)
zslDelete	删除包含给定成员和分值的节点	平均O(logN)，最坏O(N)
zslGetRank	返回给定节点的排位	平均O(logN)，最坏O(N)
zslGetElementByRank	返回给定排位上的节点	平均O(logN)，最坏O(N)
zslIsInRange	给定一个范围，判断其是否包含在跳跃表的分值范围内	O(1)，通过表头节点和表尾节点
zslFirstInRange	给定一个范围，返回跳跃表中第一个分值在范围内的节点	平均O(logN)，最坏O(N)
zslLastInRange	给定一个范围，返回跳跃表中最后一个分值在范围内的节点	平均O(logN)，最坏O(N)
zslDeleteRangeByScore	给定一个范围，删除跳跃表中所有分值在范围内的节点	O(N)，N为被删节点数
zslDeleteRangeByRank	给定一个范围，删除跳跃表中所有排位在范围内的节点	O(N)，N为被删节点数

第6章：整数集合

当一个集合只包含整数值元素，且元素数量不多时，Redis使用整数集合作为集合键的底层实现。

6.1：整数集合的实现

整数集合可以保存int16_t、int32_t、或int64_t的整数值，并且会保证集合中无重复元素。

intset.h/intset结构：

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

整数集合的每个元素是contents数组的数据项，各项在数组中从小到大排列，且数组中无重复项。

虽然intset结构将contents声明为int8_t，但该数组并不保存任何int8_t类型的值，其真正类型取决于encoding的值：INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64。

6.2：升级

每当将一个新元素添加到整数集合中，且新元素类型比整数集合当前类型要长时，整数集合要进行升级，然后才能添加新元素。步骤如下：

根据新元素类型，扩展整数集合底层数组，并为新元素分配空间。（集合元素+新元素）
将底层数组当前所有元素转换成与新元素相同的类型，并将其放在正确的比特位上，且维持有序性。
将新元素添加进底层数组中，同时更改encoding属性和length属性。

升级后新元素摆放位置

引发升级的新元素的长度总比整数集合所有元素的长度都大，所以新元素的值要么大于所有元素，要么小于所有元素：大于则新元素放在底层数组末尾，小于则放在开头。

6.3：升级的好处

6.3.1：提高灵活性

因为C语言是静态类型语言，为了避免类型错误，不会将两种不同类型的数据放在同一个数据结构中。但是整数集合可以通过自动升级底层数组来存放新元素，所以能随意添加int16_t、int32_t、int64_t类型的数据。

6.3.2：节约内存

整数集合能添加三种不同类型的值，且能确保升级操作只会在有需要时进行，尽量节省内存。

6.4：降级

整数集合不支持降级操作，一旦升级，编码会一直保持升级后的状态。

6.5：整数集合API

函数	作用	时间复杂度
intsetNew	创建整数集合	O(1)
intsetAdd	添加给定元素到整数集合	可能会升级，O(N)
intsetRemove	移除给定元素	O(N)
intsetFind	查找给定元素	排好序了，O(logN)
intsetRandom	随机返回一个元素	O(1)
intsetGet	返回给定索引上的元素	O(1)
intsetLen	返回整数集合元素个数	O(1)
intsetBlobLen	返回整数集合占用字节数	O(1)

第7章：压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一：

当一个列表键只包含少量列表项，且每个列表项是小整数值或长度较短的字符串时
当一个哈希键只包含少量键值对，且每个键值对的键和值是小整数值或长度较短的字符串时

7.1：压缩列表的构成

压缩列表是redis为了节约内存开发的，是由一系列特殊编码的连续内存块组成的顺序型结构。一个压缩列表可以包含任意个节点（entry），每个节点保存一个字节数组或一个整数值。

压缩列表各组成部分如下：

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个压缩列表占用的字节数：在内存重分配或计算zlend时使用
zltail	uint32_t	4字节	记录表尾节点距离起始地址的字节数
zllen	uint16_t	2字节	记录压缩列表的节点数：当该值等于UINT16_MAX(65535)时，真实数量需要遍历整个列表得到；小于65535时可用
entryX	列表节点	不定	压缩列表节点的长度由节点保存的内容决定
zlend	uint8_t	1字节	特殊值0xFF(十进制255)，用于标记列表末端

7.2:压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或一个整数值：

字节数组的长度可以是：小于等于63($2^6-1$)、16383($2^{14}-1$)或($2^{32}-1$)字节。
整数值长度可以是：4位(0-12之间的无符号整数)、1字节或3字节有符号整数、int16_t、int32_t、int64_t类型的整数。

每个压缩列表节点都由previous_entry_length、encoding、content三部分组成。

7.2.1：previous_entry_length

记录前一个节点包含的字节数，该属性长度可以是1字节或5字节：

若前一节点字节数小于254，则该属性为1字节。
否则，该属性为5字节：第一个字节为0xEE(254)，之后四字节用于保存前一节点长度。

程序可以通过指针运算，根据当前节点的起始地址计算前一个节点的起始地址，且可以一直回溯到表头节点。

7.2.2：encoding

encoding属性记录节点的content属性所保存数据的类型和长度：

字节数组编码：

编码	编码长度	content属性保存的值
00bbbbbb	1字节	长度小于等于($2^6-1$)字节的字节数组
01bbbbbb xxxxxxxx	2字节	长度小于等于($2^{14}-1$)字节的字节数组
10____ aaaaaaaa bbbbbbbb cccccccc dddddddd	5字节	长度小于等于($2^{32}-1$)字节的字节数组

整数编码：

编码	编码长度	content属性保存的值
11000000	1字节	int16_t类型的整数
11010000	1字节	int32_t类型的整数
11100000	1字节	int64_t类型的整数
11110000	1字节	3字节有符号整数
11111110	1字节	1字节有符号整数
1111xxxx	1字节	使用这一编码的节点无content属性，xxxx四位保存(0,12)之间的值

7.2.3：content

节点的content属性保存节点的值，节点值可以是一个字节数组或整数，其类型和长度由节点的encoding属性决定。

7.3：连锁更新

每个节点的previous_entry_length属性都记录了前一个节点的长度，如果前一节点长度小于254字节，该属性需要一字节，否则需要5字节。当在压缩列表中插入或删除节点时，可能会对压缩列表节点的previous_entry_length属性执行空间重分配操作（由于内存连续，每次内存重分配需要复杂度O(N)），从而引起后面一系列节点的空间重分配操作，Redis将这种特殊情况下产生的连续多次空间扩展操作称为“连锁更新”。连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，每次内存重分配最坏复杂度为O(N)，所以连锁更新最坏复杂度为O(N方)。

尽管连锁更新复杂度较高，但它造成性能问题的几率很低：

压缩列表中要恰好有多个连续的、长度介于250字节到253字节之间的节点才有可能引发连锁更新。
即使出现连锁更新，只要数量不多，就不会对性能造成影响。

基于以上原因，ziplistPush等命令的平均复杂度仅为O(N)，实际中可以放心使用

7.4：压缩列表API

函数	作用	复杂度
ziplistNew	创建压缩列表	O(1)
ziplistPush	创建包含给定值的新节点，并将节点添加到表头或表尾	平均O(N)，最坏O(N方)
ziplistInsert	将包含给定值的新节点插入到给定地址	平均O(N)，最坏O(N方)
ziplistIndex	返回压缩列表给定索引上的节点	O(N)
ziplistFind	查找并返回包含给定值的节点	节点值可能为字节数组，需要O(N)复杂度来判断节点值是否和给定值相等，所以查找整个列表的复杂度为O(N方)
ziplistNext	返回给定节点的下一个节点	O(1)，每个节点占用字节数可以计算得到
ziplistPrev	返回给定节点的前一个节点	O(1)
ziplistGet	返回给定节点保存的值	O(1)
ziplistDelete	删除压缩列表中给定地址上的节点	平均O(N)，最坏O(N方)
ziplistDeleteRange	删除压缩列表在给定索引上的连续多个节点	平均O(N)，最坏O(N方)
ziplistBlobLen	返回压缩列表占用的内存字节数	O(1)
ziplistLen	返回压缩列表包含的节点数	节点数小于65535时O(1)，否则为O(N)

第8章：对象

在前面各章节中，介绍了Redis用到的所有数据结构：简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合、跳跃表。Redis基于这些数据结构创建了一个对象系统，包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象。Redis可以在执行命令前根据对象类型判断一个对象是否能执行给定命令；可以针对不同使用场景为对象设置多种数据结构的实现，优化对象使用效率。

Redis对象系统实现了基于引用计数的内存回收机制，当程序不再使用某对象时，其内存会被自动释放；Redis还实现了基于引用计数的对象共享机制，可以通过让多个数据库键共享同一个对象来节约内存；Redis对象带有访问时间记录信息，可用于计算数据库键的空转时间，在服务器启用maxmemory功能时，空转时长大的键会优先被删除。

8.1：对象的类型与编码

Redis使用对象来表示数据库中的键和值，每当创建一个键值对，至少会创建两个对象，一个用作键（键对象），一个用作值（值对象）。每个对象由redisObject结构表示，其中和保存数据有关的三个属性如下：

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

8.1.1:类型

类型可以是：REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET

键总是一个字符串对象，而值可以是五种对象的其中一种，因此当称呼一个键为“列表键”时，指“该数据库键所对应的值为列表对象”。TYPE命令返回数据库键所对应的值对象的类型。

8.1.2：编码和底层实现

对象的ptr指针指向对象的底层数据结构，这些数据结构由encoding属性决定。encoding属性的值可以是：

编码常量	编码对应的底层数据结构
REDIS_ENCODING_INT	long类型整数
REDIS_ENCODING_EMBSTR	embstr编码的简单动态字符串
REDIS_ENCODING_RAW	简单动态字符串
REDIS_ENCODING_HT	字典
REDIS_ENCODING_LINKEDLIST	双端链表
REDIS_ENCODING_ZIPLIST	压缩列表
REDIS_ENCODING_INTSET	整数集合
REDIS_ENCODING_SKIPLIST	跳跃表和字典

每种对象类型都至少使用了两种编码，即至少有两种底层实现：

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现的字符串对象
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用embstr编码的SDS实现的字符串对象
REDIS_STRING	REDIS_ENCODING_RAW	使用简单动态字符串(SDS)实现的字符串对象
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的列表对象
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端链表实现的列表对象
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的哈希对象
REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象
REDIS_SET	REDIS_ENCODING_INTSET	使用整数集合实现的集合对象
REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃表和字典实现的有序集合对象

通过OBJECT ENCODING命令可查看一个数据库键的值对象所使用的编码。

通过encoding属性设定对象所使用的编码，而不是为对象关联一种固定的编码，极大地提高了Redis的灵活性，Redis可以根据不同场景为对象设置合适的编码：

因为压缩列表比双端链表更节约内存，且元素较少时，在内存中连续存放的压缩列表可以更快载入缓存
随着列表对象包含的元素越来越多，使用压缩列表的优势消失时，对象的底层实现会转向双端链表。

8.2：字符串对象

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

如果一个字符串对象保存的是整数值，且可以用long类型来表示，那么字符串对象会将整数值保存在ptr属性中（将void*转换成long），并将编码设置为int。
如果字符串对象保存的是字符串值，且长度大于39字节，那么使用SDS来保存该字符串，且编码为raw。
如果字符串对象保存的是字符串值，且长度小于等于39，则使用embstr编码方式来保存。
embstr编码与raw编码一样，都使用redisObject和sdshdr来表示字符串对象。但raw编码会调用两次内存分配函数分别创建redisObject和sdshdr结构，而embstr调用一次内存分配函数来分配一块连续空间，空间依次包含redisObject和sdshdr结构。
embstr编码的内存分配和内存释放都只需要调用一次，且能利用缓存带来的优势。
可以用long double类型表示的浮点数在Redis中也作为字符串值来保存，编码为embstr或raw。
因为长度太大而无法用long表示的整数或无法用long double表示的浮点数用embstr或raw编码。

8.2.1：编码的转换

对于int编码的字符串对象，若向该对象执行某些命令（eg:append）使其不再是一个整数值，其编码变为raw。

另外，因为Redis没有为embstr编码的字符串对象编写任何修改程序，所以embstr编码的字符串对象是只读的。当对其进行修改时，程序会将其编码从embstr转换为raw，再进行修改。所以embstr编码的字符串在执行修改命令之后总会变成一个raw编码的字符串对象。

8.2.2：字符串命令的实现

命令	int编码	embstr编码	raw编码
SET	用int编码保存值	用embstr编码保存值	用raw编码保存值
GET	拷贝整数值，转换为字符串值，再向客户端返回	直接返回	直接返回
APPEND	将对象转换为raw编码，再按raw编码方式执行	转换为raw编码再执行	调用sdscatlen函数，将给定字符串追加到末尾
INCRBYFLOAT	取出整数值转换为long double，进行加法，将浮点数结果保存	取出字符串值并尝试将其转换为long double，进行加法，再将浮点数结果保存。若不能转换，向客户端返回错误	同embstr
INCRBY	对整数值进行加法，结果作为整数保存	不能执行，返回错误	同embstr
DECRBY	对整数值进行减法，结果作为整数保存	不能执行，返回错误	同
STRLEN	拷贝整数转换为字符串，返回字符串长度	调用sdslen，返回长度	同
SETRANGE	转换为raw编码，按raw编码执行	同int编码	将字符串给定索引上的值设置为给定字符
GETRANGE	拷贝整数值转换为字符串，取出给定索引上的字符	直接取出给定索引上的字符	同

8.3：列表对象

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

8.3.1：编码转换

当列表对象同时满足以下两个条件时，使用ziplist编码：

列表对象保存的所有字符串元素的长度都小于64字节；
列表对象保存的元素数量小于512个。不能满足这两个条件的列表对象使用linkedlist编码。

以上两个条件的上限值可以修改，配置文件中list-max-ziplist-value和list-max-ziplist-entries

当使用ziplist编码的列表对象不能满足条件时，会执行对象的编码转换操作，将保存在压缩列表中的所有列表元素转移到双端链表中，编码变为linkedlist。

8.3.2：列表命令的实现

命令	ziplist编码	linkedlist编码
LPUSH	调用ziplistPush，将新元素推入表头	调用listAddNodeHead，将新元素插入表头
RPUSH	调用ziplistPush，将新元素推入表尾	调用listAddNodeTail，将新元素插入表尾
LPOP	调用ziplistIndex定位表头，向用户返回节点保存的元素后调用ziplistDelete删除表头	调用listFirst定位表头，返回节点保存的元素后调用listDelNode删除表头
RPOP	调用ziplistIndex定位表尾，向用户返回节点保存的元素后调用ziplistDelete删除表尾	调用listLast定位表尾，返回节点保存的元素后调用listDelNode删除表尾
LINDEX	调用ziplistIndex定位指定节点，向用户返回节点保存的元素	调用listIndex定位指定节点，向用户返回节点保存的元素
LINSERT	插入新节点到表头或表尾时，使用ziplistPush；其他位置使用ziplistInsert。	调用listInsertNode
LREM	遍历压缩列表，调用ziplistDelete删除包含了给定元素的节点	遍历双端链表，调用listDelNode删除包含给定元素的节点
LTRIM	调用ziplistDeleteRange，删除压缩列表中所有不在指定索引范围内的节点	遍历双端链表，调用listDelNode删除链表中所有不在指定索引范围内的节点
LLEN	调用ziplistLen返回压缩列表的长度	调用listLength返回双端链表长度
LSET	先调用ziplistDelete删除指定索引上的节点，再调用ziplistInsert将包含给定元素的新节点插入到相同索引上	调用listIndex定位指定索引上的节点，然后通过赋值操作更新节点值