内容整理基于《Redis设计与实现》一书

SDS

定义

源码路径sds.h/sdshdr

每个sdshdr表示一个SDS值

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

free的值为0，表示SDS没有未使用的空间

len的值为5，表示SDS保存了一个5字节长度的字符串

buf是一个char数组，前五个字节分别保存了R,E,D,I,S五个字符，最后一个字节则保存了空字符\0

SDS遵循C字符串以空字符\0结尾的习惯，保存空字符的1字节空间不计算在SDS的len属性中，并且为空字符分配额外的1字节空间以及添加空字符到字符串末尾等操作，都是有SDS自动完成的，这样的好处是，SDS可以直接重用一部分C字符串函数库里的函数。

该图展示一个存在5个未使用字节空间的SDS，所以他的free值为5

SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串，并且字符数组的最后一个元素总是空字符\0

C语言的字符串表示方式不能满足Redis对字符串在安全性、效率以及功能方面的要求

获取字符串长度

C语言字符串不记录自身的长度，所以要获取C字符串长度时需要遍历整个字符串，直到碰到空字符为止，复杂度为O(n)。

SDS在len中记录了SDS本身的长度，所以获取字符串长度的复杂度为O(1)。

设置和更新SDS长度的工作是由SDS的API执行时自动完成的，使用时无需进行手动配置。

避免缓冲区溢出

C字符串不记录自身长度，除了获取字符串长度复杂度高之外，还容易造成缓冲区溢出（buffer overflow)。

如<string.h>/strcat函数可以将src字符安从中的内容拼接到dest字符串末尾

char *strcat(char *dest,const chat *src);

strcat假定用户指定这个函数时，已经给dest分配了足够的内存，可以容纳src的所有内容，但是一旦假定不成立，就会阐释缓冲区溢出。

例如有两个内存紧邻的字符串s1和s2，s1保存了字符串Redis，s2保存了字符串MongoDB。
此时执行stract(s1," Cluster");将s1的内容改为“Redis Cluster”,但是s1分配的空间不足，s1的数据将溢出到s2所在的空间，导致s2被篡改。

当SDS API要对SDS进行修改时，会先检查SDS空间是否满足修改所需的要求，如果不满足，API会自动将SDS的空间扩展至执行修改需要的大小，然后执行修改操作。

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

每次增长或缩短一个C字符串，程序总要对保存这个C字符串的数组进行一次内存重分配操作：

增长字符串时需要通过内存重新分配来扩展底层数组的空间大小，否则可能导致缓冲区溢出
缩短字符串时，需要通过内存重新分配来释放字符串中不再使用的空间，否则会导致内存泄露

内存重新分配时涉及复杂算法，并且要执行系统调度，所以通常是比较耗时的操作

如果在一般程序中，修改字符串长度的情况不常出现，那么每次修改时都重新分配内存可以接受。

Redis作为数据库，数据修改频繁，如果每次都重新分配内存，会影响性能。

SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联，SDS中，buf数组的长度不一定就是字符数量加一，数组里面包含未使用的字节，这些字节的数量由free属性记录。

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

空间预分配

空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并需要对SDS进行空间扩展时，程序不仅会分配SDS修改所必须的空间，还会为SDS分配额外的未使用空间。

额外分配的未使用空间数量公式：

如果对SDS修改后，SDS的长度（len属性的值）小于1MB，那么程序分配和len属性一样大小的未使用空间，这时SDS的len属性值与free属性值相同，buf长度为2len+1(额外的一个字节用于保存空字符)
如果对SDS修改后，SDS的长度大于等于1MB，那么程序会分配1MB的未使用空间。比如，修改后SDS的len为30MB，那么free为1MB，buf长度为30MB+1MB+1byte

通过空间预分配，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

在扩展SDS空间之前，API会先检查未分配空间是否足够，如果足够，会直接使用未分配空间，无需进行内存重分配

这样就将连续增长N次所需的内存重分配次数从必定N次降低为最多N次

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API缩短SDS保存的字符串时，程序并不立即使用内存重分配来缩短多出来的字节，而是使用free属性来记录，等待将来使用。

通过惰性空间释放策略，SDS避免了缩短字符串时需要的内存重分配，以为将来有可能的增长操作提供了优化。

SDS也提供了相应的API，可以在需要的时候真正的释放SDS的未使用空间，避免造成内存浪费。

二进制安全

C字符串中的字符必须符合某种编码，并且除了字符串末尾外，字符串中不能包含空字符（\0），否则最先被程序入读的空字符会被误认为是字符串结尾，这些限制导致C字符串只能保存文本数据，无法存储图像，音频，视频等二进制数据。

SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对数据做任何限制、过滤等。数据写入时是什么样的，被读取出来也是什么样的。

兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但是它也遵循了C字符串以空字符结尾的惯例，这是为了让那些保存文本数据的SDS可以重用部分<string.h>库定义的函数，避免了不必要的代码重复。

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

链表

当Redis的List包含较多元素，或者列表中包含元素都是较长的字符串时，Redis就会采用链表作为底层实现。

除了List以外，发布与订阅、慢查询、监视器等功能也用到了链表,Redis服务器本身使用链表保存多个客户端的状态信息，使用链表构建客户端输出缓冲区（output buffer）

链表及实现

adlist.h/listNode

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

多个listNode可以通过prev和next指针组成双端链表

使用adlist.h/list来持有链表

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

list结构为链表提供了表头指针head，表尾指针tail，链表长度计数器len，dup、free、match则是用于实现多态链表所需的类型特定函数

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

Redis的链表特性：

双端：链表节点带有prev和next指针，获取某个节点的前置和后置节点的复杂度为O(1)
无环：表头节点的prev指针和表尾节点的next指针都指向null，对链表的访问以null为终点
带有表头指针和表尾指针：通过list结构的head指针和tail指针，获取链表头节点和尾结点的复杂度为O(1)
带有链表长度计数器，获取链表中节点数量的复杂度为O(1)
多态，连节点使用void* 指针来保存节点值，并可以通过list的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以保存各种不同类型的值

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或者映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。

一个键可以和一个值进行关联，这些关联的键和值就称为键值对

字典中的每个键都是独一无二的，可以在字典中根据键查找关联的值，或者更新值，也可以根据键删除整个键值对。

Redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查操作也是构建在对字典的操作之上的。

redis> set msg "hello word"

在数据库创建一个键为msg，值为hello word的键值对时，这个键值对就是保存在代表数据库的字典里。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，或者键值对中的元素都是比较长的字符串时，Redis会使用字典作为哈希键的底层实现。

字典的实现

哈希表

dict.h/dictht结构定义

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数组的哪个索引上面

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对

typedef struct dictEnrty{
    // 键
    void *key;
    // 值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    }v;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

key属性保存着键值对中的键，v属性保存着键值对中的值，其中值可以是一个指针，或者一个uint64_t整数，或者一个int64_t整数。

next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突问题

字典

dict.h/dict

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

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

type属性是一个纸箱dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同类型特定函数
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[0]哈希表，ht[1]哈希表只会在对ht[0]进行rehash的时使用。

rehashidx记录了rehash目前的进度，如果目前没有进行rehash，那么值为-1

哈希算法

将一个新的键添加到字典里时，需要根据键计算出哈希值和索引值，然后根据索引值，将新键值对的哈希表节点放到哈希表数组的指定索引上。

使用字典设置的哈希函数计算key的哈希值

hash = dict->type->hashFunction(key)

使用哈希表的sizemask属性和哈希值计算索引

根据情况，ht[x]可以是ht[0]或ht[1]

index = hash & dict->ht[x].sizemask

当字典被用作数据库底层实现时，或者用于哈希键的底层实现时，Redis使用MurmurHash2算法计算哈希值

解决键冲突

当两个或以上数量的键被分配到哈希表数组的同一个索引上，称这些键发生了冲突。

Redis的哈希表采用链式地址法解决冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以通过next指针构成一个单向链表，被分配到同一个索引上的节点通过单向链表连接

rehash

当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行对应的扩展或者收缩，可以通过执行rehash操作来完成

rehash步骤

为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（即ht[0].used的值）
1. 如果执行的是扩容操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2ⁿ
2. 如果执行的是缩容操作，那么ht[1]的大小为第一个大于等于ht[0].used的2ⁿ
将保存在ht[0]中的所有键值对rehash到ht[1]上，rehash指的是重新计算键的hash值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上
当ht[0]包含的所有键值对都迁移到ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备

rehash条件

当满足以下任一条件时，进行扩展操作：

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

负载因子计算公式

负载因子 = 哈希表已保存节点数量/哈希表大小

load_factor = ht[0].used / ht[0].size

根据BGSAVE命令或者BGREWRITEAOF命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同。

在执行BGSAVE命令或者BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，大多数操作系统采用些事复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展所需的负载因子，从而尽可能的避免在子进程存在期间进行哈希表扩展操作，可以避免不要的内存写入操作，最大限度节约内存。

当负载因子小于0.1时，进行收缩操作

渐进式rehash

在扩展或收缩哈希表时，需要将ht[0]里面的所有键值对rehash到ht[1]里面，但是rehash的动作不是一次性，集中式的完成的，而是分多次、渐进式的完成的。

这么做的原因在于，如果哈希表中存在的数据量特别大，要一次性将这些键值对全部rehash到ht[1]的话，庞大的数据量可能会导致服务器在一定时间内停止服务。

所以，为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]中的键值对全部rehash到ht[1]，而是分多次，渐进式的

渐进式rehash步骤

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
在字典表中维持一个索引计数器变量rehashidx，并将值设置为0，表示rehash工作正式开始
在rehash进行期间，每次对字典执行添加、删除、查找、更新操作时，除了执行指定的操作以外，还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成后，rehashidx的值加一
随着字典操作不断进行，最后ht[0]的所有键值对都会被rehash至ht[1]，这时将rehashidx设置为-1，表示rehash完成

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

在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除、查找、更新等操作会在两个哈希表上进行，会先在ht[0]进行查找，如果没有找到就会去ht[1]查找。

在渐进式rehash执行期间，新增加到字典的键值对一律会被保存到ht[1]中，ht[0]不进行任何添加操作，从而保证ht[0]中的键值对数量只减不增，随着rehash操作的执行最终变为空表。

跳跃表

跳跃表（skiplist）是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O(log n)、最坏O(n)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

大部分情况下，跳跃表的效率可以和平衡二叉树相媲美，并且因为跳跃表的实现比平衡二叉树要更简单，所以不少程序使用跳跃表代替平衡树。

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合的底层实现。

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

跳跃表的实现

跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，zskiplist结构则用于保存跳跃表节点的相关信息，如节点的数量，以及指向表头节点和表尾节点的指针等。

位于图片最左边的是zskiplist结构，包含以下属性

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

位于zskiplist结构右方的是四个zskiplistNode结构，包含以下属性

层（level）：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。
- 前进指针：用于访问位于位于表尾方向的其他节点
- 跨度：记录了前进指针所指向节点和当前节点的距离
- 上图中，连线上带有数字的街头就表示了前进指针，数字表示跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行
后腿（backward）指针：节点中用BW字样标记节点的后腿指针，它指向位于当前节点的前一个节点。后对指针在程序从表尾向表头遍历时使用
分值（score）：各节点中的1.0,、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
成员对象（obj）：各个节点中的o1、o2和o3是节点所保存的成员对象。

注意表头节点和其他节点的构造是一样的，表头节点也有后对指针、分值和对象，不过表头节点的这些属性不会被用到，所以在图中进行了省略

跳跃表节点

redis.h、zskiplistNode

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

1. 层

跳跃表节点的level数组恶意包含很多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层数越多，访问其他节点的速度越快。

每次创建一个新跳跃表节点的时候，程序会根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和31之间的值最为level数组的大小，这个大小就是层的高度。

图分别展示了三个高度为1层、3层和5层的节点，因为C语言的数组索引总是从0开始额定，所以节点第一层是level[0]

2. 前进指针

每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。

图中用虚线表示出了程序重表头向表尾方向遍历跳跃表中所有节点的路径

迭代程序首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中的第二个节点
在第二个节点时，程序沿着第二层的前进指针移动到第三个节点
在第三个节点时，程序沿着第二层的前进指针移动到表中的第四个节点
当程序继续沿着第四个节点的前进指针移动时，碰到了NULL，程序知道此时已经到达了跳跃表的表尾，于是结束此次遍历

3. 跨度

层额跨度（level[i].span属性）用于记录两个节点之间的距离：

两个节点之间的跨度越大，他们相距的就越远
指向NULL的所有前进指针跨度都为0，因为它们没有连向任何节点

初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样，遍历操作只使用前进指针就可以完成了。

跨度实际是用来计算排（rank）的：在查找某个节点的过程中，见沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

图中用虚线标记了跳跃表中查找分值为3.0、成员对象为o3的节点时，沿途经历的层：查找过程中只经历一个层，并且跨度为3，所以目标节点在跳跃表中的排位为3

图中用虚线标记了在跳跃表中查找分值为2.0、成员变量为o2的节点时，沿途经历的层：在查找节点的过程中，程序经历了两个跨度为1的节点，因此目标节点为跳跃表中的排位为2

4. 后退指针

节点的后退指针（backward属性）用于从表尾向表头方向访问节点：和可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

图中用虚线展示了从表尾向表头遍历跳跃表中所有的节点：首先通过跳跃表的tail指针访问表尾节点，然后通过后退指针访问倒数第二个节点，之后再沿着后退指针访问倒数第三个接单，再之后遇到指向null的后退指针，访问结束

5. 分值和成员

节点的分值（score属性）是一个double类型的浮点数，跳跃表中的所有节点都按照分值从小到大来排序。

节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值。

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以相同。

分值相同的节点，将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头），成员对象较大的节点则会排在后面（靠近表尾）。

图中所示跳跃表中，三个跳跃表节点都保存了相同的分值10.0，但是成员对象o1的节点顺序在o2和o3节点之前，o2的节点又在o3的节点前，由此可见，o1、o2、o3三个成员对象在字典中的排序为o1<=o2<=o3。

跳跃表

仅仅靠多个跳跃表节点就可以组成跳跃表

通过使用一个zskiplist结构来维持这些节点，程序可以更方便的对整个跳跃表进行处理，比如快速访问表头节点和表尾节点，或者快速的获取跳跃表节点的数量（跳跃表的长度）等信息

zskiplist结构定义

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

header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，定位表头和表尾节点的复杂度为O(1)。

通过使用length属性来记录节点的数量，程序可以在O(1)复杂度内返回跳跃表的长度。

level属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数（表头节点的层高不做计算）。

整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

整数集合的实现

整数集合是redis用于保存整数值的集合抽象数据结构，它可以保存的类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

intset,h/intset结构定义

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

contents数组：整数结合的底层实现：整数集合的每个元素都是centents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序排列，并且数组中不包含任何重复项。
length属性：记录了整数结合包含的元素数量，也就是contents数组的长度

虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值。

如果encoding属性的值为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组，数组中的每个项都是一个int16_t类型的整数值（-32768~32767）。
如果encoding属性的值为INTSET_ENC_INT32，那么contents就是一个int32_t类型的数组，数组中的每个项都是一个int32_t类型的整数值（-2147483648~2147483647）
如果encoding属性的值为INTSET_ENC_INT64，那么contents就是一个int64_t类型的数组，数组中的每个项都是一个int64_t类型的整数值（-9223372036854775808~9223372036854775807）

encoding属性值为INTSET_ENC_INT16，表示数组集合的底层实现为int16_t类型的数组，集合保存的都是int16_t类型的整数值
length属性值为5，表示数组集合包含5个元素
contents数组按从小到大的顺序保存着集合中的元素
每个元素都是int16_t类型的整数值，所以contents数组的大小等于sizeof(int16_t)*5 = 16*5 = 80位。
encoding属性值为INTSET_ENC_INT64，表示数组集合的底层实现为int64_t类型的数组，集合保存的都是int64_t类型的整数值
length属性值为4，表示数组集合包含4个元素
contents数组按从小到大的顺序保存着集合中的元素
每个元素都是int64_t类型的整数值，所以contents数组的大小等于sizeof(int64_t)*4 = 64*4 = 256位。

虽然contents数组中的值，只有-2675256175807981027是真正需要用int64_t类型来保存的，其他三个值都可以用int16_t类型来保存，但是根据整数集合的升级规则，当向底层为int16_t数组的整数集合中添加一个int64_t类型的整数值时，整数集合已有的所有元素都会被转换成int64_t类型。

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型又要长时，整数集合需要先进行升级，然后才能将新的元素添加到整数集合中。

升级整数集合并添加新元素分为三步进行：

根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
将底层数组现有的元素都转换成新元素的类型，并将转换后的元素放置到正确的位置上，放置元素的过程中，要维持底层数组的有序性不变
将新元素添加到底层数组中

下图展示了int16_t整数集合添加一个int32_t元素的扩展过程。

每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(n)。

升级后新元素的摆放位置

因为引发升级的新元素的长度总是比整数集合现有的所有元素长度都大，所以这个新元素的值要么大于所有现有元素，要么小于所有现有元素。

新元素小于所有现有元素时，会被放在底层数组的最开始位置（索引0）
新元素大于所有现有元素时，新元素会被放在底层元素的最末尾（索引length-1)

升级的好处

提升灵活性

C语言是静态类型语言，为了避免错误，我们通常不会将两种不同类型的值放在同一个数据结构里面。

例如一般只是用int16_t类型数组保存int16_t类型的值。

由于整数集合可以自动升级底层数据来适应元素，所以我们可以随意的将int16_t、int32_t、int64_t类型的数据添加到集合中，不用担心出现类型错误。

节约内存

要让一个数组可以同时保存int16_t、int32_t、int64_t三种类型的值，最简单的方法就是直接使用int64_t类型的数组作为整数集合的实现。但是这样做的话，如果只保存int16_t或int32_t类型的值，就会存在内存浪费的情况。

整数集合的做法可以让集合同时保存三种不同类型的值，又可以确保升级操作只会在需要的时候进行，可以尽量节省内存。

降级

数组集合不支持降级，一旦数组集合进行了升级，编码就会一直保持升级后的状态。

压缩列表

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

当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数，要么就是长度较短的字符串，那么Redsi就会使用压缩列表来做哈希键的底层实现

压缩列表的构成

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

一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

下图展示了压缩列表的各个组成部分

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配或者计算zlend的位置时使用
zltail	uint32_t	4字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无需遍历整个压缩列表就可以确定别为节点的地址
zllen	uint16_t	2字节	记录了压缩列表包含的节点数量：当这个属性小于UINT16_MAX(65535)时，这个属性的值就是压缩列表包含节点的数量，当这个值大于UINT16_MAX时，节点的真实数量需要遍历整个压缩列表才能计算得出
entryX	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内存决定
zlend	uint8_t	1字节	特殊值0xFF(十进制255)，用于标记压缩列表的末端

列表zlbytes属性的值为0x50(十进制80)，表示压缩列表的总长为80字节
列表zltail属性的值为0x3c（十进制60），表示如果有一个指针P指向压缩列表的起始地址，那么只要用这个指针P加上偏移量60，就可以计算出表尾节点entry3的地址
列表zllen属性值为0x3（十进制3），表示压缩列表包含3个节点。

列表zlbytes属性的值为0xd2(十进制210)，表示压缩列表的总长为210字节
列表zltail属性的值为0xb3（十进制179），表示如果有一个指针P指向压缩列表的起始地址，那么只要用这个指针P加上偏移量179，就可以计算出表尾节点entry5的地址
列表zllen属性值为0x5（十进制5），表示压缩列表包含5个节点。

压缩列表节点的构成

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

字节数组可以是一下三种长度中的一种：

长度小于等于63（2⁶-1）字节的字节数组
长度小于等于16383（2¹⁴-1）字节的字节数组
长度小于等于4294967295（2³²-1）字节的字节数组

整数值可以是一下六种长度中的一种：

4位长度，介于0至12之间的无符号整数
1字节长度的有符号整数
3字节长度的有符号整数
int16_t类型整数
int32_t类型整数
int64_t类型整数

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

previous_entry_length

节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个字节的长度。previous_entry_length属性的长度可以是1字节或5字节。

如果前一节点长度小于254字节，那么previous_entry_length属性的长度为1字节，前一个节点的长度就保存在这一个字节里
如果前一节点的长度大于等于254字节，那么previous_entry_length属性长度为5字节，其中属性的第一个字节会被设置为0xFE（十进制254），而之后的四个字节则会用于保存前一节点的长度。

图中展示了一个包含1字节长previous_entry_length属性的压缩节点，属性的值为0x05，表示前一个节点长度为5字节。

图中展示了一个包含5字节长previous_entry_length属性的压缩节点，属性的值为0xFE00002766，最高位的0XFE表示这是一个5字节长度的previous_entry_length属性，后面的四个字节0x00002766（十进制10086）是前一个节点的实际长度。

因为节点的previous_entry_length记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址计算出前一个节点的起始地址。

例如现在有一个指针c，c指向当前节点的起始地址，c-previous_entry_length，就是前一个节点的起始位置。

压缩列表的从表尾向表头遍历的操作就是使用这一原理实现的。

encoding

节点的encoding属性记录了节点的content属性锁保存的数据类型及长度

一字节、两字节或者五字节长，值的高位为00,01,10的是字节数组的编码，这种编码表示节点的content属性保存着字节数组，数组的长度由编码去除最高两位之后的其他位记录
一字节长，值的最高位以11开头的是整数编码，这种编码表示节点的content属性保存着整数值，整数值的类型和长度由去编码去除最高两位之后的其他位记录

字节数组编码

编码	编码长度	content属性保存的值
00bbbbbb	1字节	长度小于63字节的字节数组
01bbbbbb xxxxxxxx	2字节	长度小于等于16383字节的字节数组
10_ _ _ _ _ _ aaaaaaaa bbbbbbbb cccccccc dddddddd	5 字节	长度小于等于4294967295字节的字节数组

整数编码

编码	编码长度	content属性保存的值
11000000	1字节	int16_t类型整数
11010000	1字节	int32_t类型的整数
11100000	1字节	int64_t类型的整数
11110000	1字节	24位有符号整数
11111110	1字节	8位有符号整数
1111xxxx	1字节	使用这一编码的节点没有相应的content属性，因为编码本身xxxx四个位已经保存了一个介于0到12之间的值，所以无需content属性

content

节点的content属性负责保存节点的值，节点值可以是一个字节数组或者证书，值的类型和长度有节点的encoding属性决定。

previous_entry_length	encoding	content
...	00001011	"hello word"

编码最高两位00表示节点保存的是一个字节数组
编码后六位001011记录了字节数组的长度为11；
content属性保存着节点的值“hello word”

previous_entry_length	encoding	content
...	11000000	10086

编码11000000表示节点保存的是一个int16_t类型的整数值
content属性保存着节点的值10086

连锁更新

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

如果前一节点长度小于254字节，那么previous_entry_length属性的长度为1字节，前一个节点的长度就保存在这一个字节里
如果前一节点的长度大于等于254字节，那么previous_entry_length属性长度为5字节，其中属性的第一个字节会被设置为0xFE（十进制254），而之后的四个字节则会用于保存前一节点的长度。

现在，如果有这么一种情况：在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点e1到eN。

因为e1到eN的所有节点的长度都小于254字节，所以记录这些节点的长度都只需要1字节长的previous_entry_length属性。此时，如果将一个长度大于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的长度，程序需要再次对压缩列表执行空间重分配操作......为了让每个节点previous_netry_length属性都能符合压缩列表对节点的要求，程序要不断执行空间重分配操作，直到eN为止。

Redis将这种在特殊情况下产生的连续多次空间扩展操作称为连锁更新。

除了添加节点可能引发连锁更新外，删除节点也可能会引发连锁更新。

如图中entry开头的节点都是大小介于250到253字节的节点，big节点的长度大于等于254（需要5个字节保存），而small的节点长度小于254字节（需要1个字节保存），将small节点删除之后，原small之后的节点需要空间重分配来记录previous_entry_length，从而引发连锁更新。

因为连锁更新在最坏的情况下需要对压缩列表执行N次空间重分配操作，每次空间重分配的最坏复杂度为O(n)，所以连锁更新的最坏复杂度为O(n²)。

要注意的是，尽管连锁更新的复杂度较高，但是它真正造成性能的几率是很低的

首先，压缩列表要敲好有多个连续的、长度介于250到253字节之间的节点，连锁更新才有可能被引发，实际中这种场景并不多见
其次，即使出现连锁更新，只要被更新的节点不多，就会对性能造成影响，比如只对三五个节点进行连锁更新

因为以上原因，zilistPush等命令的平均时间复杂度仅为O(n)，实际中可以放心的使用这些函数，不必担心连锁更新影响压缩列表性能。

对象

前面介绍了Redis用到的所有主要数据结构，如简单动态字符串（SDS)、双端链表、字典、压缩列表、整数集合等。

Redis并没有直接使用这些数据结构来实现键值对数据库么事基于这些数据结构创建了一个对象系统，这个对象系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种之前提到的数据结构。

通过这些不同类型的对象，Redis可以在执行命令之前，根据对象类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。

Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放；redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享一个对象来节约内存。

Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转市场，在服务器启动了maxmemory功能的情况下，空转市场较大的那些键可能会被服务器优先删除。

对象的类型与编码

Redis使用对象来表示数据库中的键和值，每次我们在Redis的数据库中创建一个键值对的时候，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用做键值对的值（值对象）。

Redis中，每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性

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

类型

对象的type属性记录了对象的类型，这个属性的值可以是下表中列出的常量的其中一个。

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

对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值可以是上述对象中的任何一种。

TYPE命令的实现方式也与此类似，当对一个数据库键执行TYPE命令时，命令返回的结果为数据库键对应的值对象的类型，而不是键对象的类型。

对象	type属性值	`TYPE`命令输出
字符串对象	REDIS_STRING	"string"
列表对象	REDIS_LIST	"list"
哈希对象	REDIS_HASH	"hash"
集合对象	REDIS_SET	"set"
有序集合对象	REDIS_ZSET	"zset"

编码和底层实现

对象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编码的简单动态字符串实现的字符串对象
REDIS_STRING	REDIS_ENCODING_RAW	使用简单动态字符串实现的字符串对象
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命令可以查看一个数据库键的值对象的编码

底层数据结构	编码常量	`OBJECT ENCODING`命令输出
整数	REDIS_ENCODING_INT	"int"
embstr编码的简单动态字符串（SDS)	REDIS_ENCODING_EMBSTR	"embstr"
简单动态字符串	REDIS_ENCODING_RAW	"raw"
	REDIS_ENCODING_HT	"hashtable"
双端链表	REDIS_ENCODING_LINKEDLISK	"linkedlist"
压缩列表	REDIS_ENCODING_ZIPLIST	"ziplist"
整数集合	REDIS_ENCODING_INTSET	"intset"
跳跃表和字典	REDIS_ENCODING_SKIPLIST	"skiplist"

通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定编码，极大的提升了Redis的灵活性和效率，因为redis可以根据不同的场景为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

例如，在列表对象包含的元素较少时，redis使用压缩列表作为列表对象的底层实现

压缩列表比双端链表更节约内存，并且在元素数量较少时，在内存中以连续块方式保存的压缩列表比双端链表可以更快被载入到缓存中
随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失，对象就会将底层实现从压缩列表转向功能更强，更适合保存大量元素的双端链表上。

其他类型的对象也会通过使用多种不同的编码来进行类似的优化。

字符串对象

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

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象就会将整数值保存在字符串对象结构的ptr属性里（将void *转换成long），并将字符串对象的编码设置为int。

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw。

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串。

embstr编码是转变用于保存短字符串的一种优化编码方式，这种编码和raw编码一样，都使用redisObject结构和sdshdr结构来表示字符串对象。

raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构。

embstr编码通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构

embstr编码的字符串对象在执行命令时，产生的效果和raw编码的字符串对象执行命令时产生的效果是相同的。

使用embstr编码的字符串对象来保存短字符串值有以下好处：

embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次
释放embstr编码的字符串对象只需要调用一次内存释放函数
embstr编码的字符串对象的所有数据都保存在一块连续的内存里，所以这种编码的字符串对象相比raw编码的字符串对象能更好的利用缓存带来的优势

可以用long，double类型表示的浮点数在Redis总也是作为字符串值来保存的。如果要保存一个浮点数到字符串对象里面，那么程序会先将这个浮点数转换成字符串值，然后在保存转换所得的字符串值。

redis> set pi 3.14
OK
redis> OBJECT ENCODING pi
"embstr"

在有需要的时候，程序会将保存在字符串对象里的字符串值转换回浮点数，执行某些操作，再将执行操作所得的浮点数转换回字符串值，并继续保存在字符串对象里。

redis> INCRBYFLOAT pi 2.0
"5.14"
redis> OBJECT ENCODING pi
"embstr"

程序会首先去除字符串对象里面保存的字符串“3.14”，将它转换回浮点值3.14，然后将3.14和2.0相加得出的值5.14转换为字符串“5.14”，并将这个“5.14”保存到字符串对象里面。

值	编码
可以用long类型保存的整数	int
可以用long double类型保存的浮点数	embstr或raw
字符串值，或者因长度太大而没有办法用long类型表示的整数挥着浮点数	embstr或raw

编码的转换

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象。

对于int编码的字符串对象来说，如果我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象的编码将从int变为raw。

redis> set numner 10086
OK
redis> OBJECT ENCODING
"int"
redis> APPEND number "is a good number!"
(integer) 23
redis> GET number
"10086 is a good number!"
redis> OBJECT ENCODING number
"raw"

因为Redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int编码的字符串对象和raw编码的字符串对象有这些程序），所以embstr编码的字符串对象实际上是只读的。

当我们对embstr编码的字符串对象执行任何修改命令时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。因为这个原因embstr编码的字符串对象在执行修改命令之后，总会变成一个raw编码的字符串对象。

redis> SET msg "hello world"
OK
redis> OBJECT ENCODING msg
"embstr"
redis> APPEND msg " again!"
(integer) 18
redis> OBJECT ENCODING msg
"raw"

列表对象

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

ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（entry）保存了一个列表元素。

如果我们执行一下RPUSH命令，那么服务器将创建一个列表对象作为numbers键的值

redis> RPUSH numbers 1 "three" 5
(integer) 3

如果numbers键的值对象使用的ziplist编码，这个值的对象如图展示。

另一方面，linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，每个字符串对象都保存了一个列表元素。

如果前面的number创建的列表对象使用不是ziplist编码，而是linkedlist编码，那么numbers键的值对象应该如下图所示，

linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象，这种嵌套字符串对象的行为在后面的哈希对象。集合对象和有序集合对象中都会出现，字符串对象是Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的队形

为了简化字符串对象的表示，上图中使用了一个带有StringObject字样的格子来表示一个字符串对象，而StringObject字样下面的是字符串对象所保存的值

编码转换

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

列表对象保存的所有字符串元素的长度都小于64字节
列表对象保存的元素数量小于512个

不能满足这两个条件的列表对象需要使用linkedlist编码。

以上两个条件的上限是可以修改的，具体可以看配置文件中关于list-max-ziplist-value选项和list-max-ziplist-entries选项说明

队友使用ziplist编码的列表对象来说，当使用ziplist编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有列表元素都会被转移并保存到双端链表里，对象编码也会从ziplist变为linkedlist。

# 所有元素的长度都小于64字节
redis> RPUSH blah "hello" "word" "again"
(integer) 3
redis> OBJECT ENCODING blah
"ziplist"
# 将一个65字节长的元素推人列表对象中
redis> RPUSH blah “wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww”
(integer) 4
redis> OBJECT ENCODING blah
"linkedlist"

哈希对象

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

ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会将保存了键的亚索列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表推入到压缩列表表尾，因此：

保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后
先添加到哈希对象中的键值对会被放在压缩列表的头方向，后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向

redis> HSET profile name "Tom"

(integer) 1

redis> HSET profile age 25

(integer) 1

redis> HSET profile career "Programmer"

(integer) 1

如果profile键的值对象使用的是ziplist编码，那么这个对象将如图展示

hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存：

字典的每个键都是一个字符串对象，对象中保存了键值对的键
字典的每个值都是一个字符串对象，对象中保存了键值对的值

如果前面的profile键创建的不是ziplist编码的哈希对象，惹事hashtable编码的哈希对象，那么应该如下图所示

编码转换

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

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
哈希对象保存的键值对数量小于512个

不能满足这两个条件的哈希对象需要使用hashtable编码

这两个条件的上限值是可以修改的，具体可以看配置文件中关于hash-max-ziplist-value选项和hash-max-zuolist-entries选项的说明

对于使用ziplist编码的哈希对象来说，当使用zipllist编码所需的两个条件的任意一个不能被满足时，对象的编码转换操作就会被执行，原本保存在压缩列表里的所有键值对都会被转移并保存到字典里，对象的编码也会从ziplist变为hashtable

集合对象

集合对象的编码可以使intset或者hashtable

intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

redis> SADD numbers 1 3 5 
(integer) 3

hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部设置为NULL。

redis>SADD Dfruits "apple" "banana" "cherry"
(integer) 3

编码的转换

当集合对象可以同时满足一下两个条件时，对象使用intset编码：

集合对象保存的所有元素都是整数值
集合对象保存的元素数量不超过512个

不能满足这两个条件的集合对象都需要使用hashtable编码。

第二个条件的上限值是可以修改的，具体可以看配置文件中关于set-max-intset-entries选项的说明。

对于使用intset编码的集合对象来说，当使用intset编码所需的两个条件的任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在整数集合中的所有元素都会被转移并保存到字典中，并且对象的编码也会从intset变为hashtable

有序集合对象

有序结合对象的编码可以使ziplist或者skiplist。

ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的亚索列表节点来保存，第一个节点保存元素的成员（member），第二个元素保存元素的分值（score）。

压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，分值较大的元素被放置在靠近表尾的方向。

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表

typedef struct zset {
    zskiplist *zsl;
    dict *dict;
} zset;

zset结构中的zsl跳跃表按分值从小到大保存了所有有序集合元素，每个跳跃表节点都保存了一个集合元素。

跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性保存了元素的分值。

通过这个跳跃表，程序可以对有序集合进行范围型操作，比如ZRANK、ZRANGE等命令就是基于跳跃表API来实现的。

除此之外，zset结构中的dict字段为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素，字典的键保存了元素的成员，字段的值保存了元素的分值。通过这个字段，程序可以用O(1)复杂度查找给定成员的分值，ZSCORE命令的就是根据这一特性实现的，而很多其他有序集合命令都在实现的内部用到这一特性。

有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但是这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值，也不会因此而浪费额外的内存。

为什么有序集合需要同时使用跳跃表和字典来实现

理论上，有序集合可以单独使用字典或者跳跃表的其中一个数据结构来实现，但是无论单独使用字典还是跳跃表，在性能上对比同时使用字段和跳跃表都会有所降低。

如果只使用字典来实现有序集合，那么以O(1)复杂度查找成员分值的特性会被保留，但是因为字典保存的集合元素是无序的，所以执行范围型操作（如ZRANK、ZRANG等）命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序至少需要O(NlogN)时间复杂度以及二弟啊的O(N)内存空间（因为需要创建一个数组来保存排序后的元素）。

如果只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的有点都会被保留，但是没有字典，根据成员查找分值操作的复杂度将由O(1)上升为O(logN)。

所以为了让有序集合的查找和范围型操作都能尽快执行，Redis选择了同时使用两种数据结构来实现有序集合。

编码的转换

当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码

有序结合保存的元素数量小于128个
有序结合保存的所有元素成员长度都小于64字节

不能满足以上两个条件的有序集合对象将使用skiplist编码

以上两个条件的上限值是可以修改的，具体可看配置文件中关于zset-max-ziplist-entries选项和zset-max-ziplist-value选项的说明

对于使用ziplist编码的有序集合对象来说，当使用ziplist编码所需的两个条件中任意一个不能被满足时，就会执行对象的编码转换操作，原本保存在压缩列表里的所有集合元素都会被转移并保存到zset结构里，对象的编码也会从ziplist变为skiplist

类型检查与命令多态

Redis中用于操作键的的命令基本上可以分为两类

一种是可以对任何类型的键执行，如DEL、EXPIRE、RENAME、TYPE、OBJECT等

另一种命令只能对特定类型的键执行，如

SET、GET、APPEND、STRLEN等命令只能对字符串键执行
HDEL、HSET、HGET、HLEN等命令只能对哈希键执行
RPUSH、LPOP、LINSERT、LLEN等命令
SADD、SPOP、SINTER、SCARD等命令只能对集合键执行
ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行

类型检查的实现

为了确保只有指定类型的键可以执行某些特定命令，在执行一个类型特定的命令之前，Redis会先检查输入键的类型是否正确，然后再决定否执行给定的命令。

类型特定命令所进行的类型检查是通过redisObject结构的type属性来实现的

在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行所需的类型，如果是，服务器就会对键执行特定的命令
否则，服务器将拒绝执行命令，并向客户端返回一个类型错误

多态命令的实现

Redis除了会根据值对象的类型来判断键是否能够执行指定命令外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。

例如，列表对象有ziplist和linkedlist两种编码可用，其中前者使用压缩列表API来实现列表命令，后者使用双端链表API实现列表命令。

如果我们对一个键执行LLEN命令，那么服务器除了要确保执行命令的是列表键之外，还要根据键的值对象所使用额编码来选择正确的LLEN命名实现

如果列表对象的编码为ziplist，那么说明列表对象的实现为压缩列表，程序将使用ziplistLen函数返回列表的长度
如果对象的编码为linkedlist，说明列表对象的实现为双端队列，程序将使用listLength函数来返回双端链表的长度

graph TD A[客户端发送LLEN&ltkey>命令]-->B{服务器检查键key的值<br/>对象是否列表对象} B -->|是| C{编码对象是ziplish<br/>还是linkedlist} B -->|否| D[返回一个错误类型] C -->|ziplist编码| E[调用ziplistLen函数<br/>返回压缩列表长度] C -->|linkedlist编码| F[调用listLength函数<br/>返回双端链表长度]

内存回收

C语言不具备自动内存回收功能，所以Redis在自己的对象系统中构建了引用计数（reference counting）计数实现的内存回收机制，通过这一机制，程序可以通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。

typedef struct redisObject{
    // ...
	//	引用计数
    int refcount;
    // ...
} robj;

函数	作用
incrRefCount	将对象的引用数增加1
decrRefCount	将对象的引用数减少1，当对象的引用计数值等于0时，释放对象
resetRefCount	将对象引用计数设置为0，但并不释放对象，这个函数通常在需要重新设置对象的技术引用时使用

对象的引用计数信息会随着对象的使用状态而不断变化：

创建一个新对象时，引用计数的值会被初始化为1
当对象被一个新程序使用时，它的引用计数值会被增加1
当对象不再被一个程序使用时，它的引用计数值会被减少1
当对象的引用计数值变为0时，对象所占用的内存会被释放

对象的整个生命周期可以划分为创建对象，操作对象、释放对象三个阶段。

对象共享

除了用于实现引用计数内存回收机制外，对象的引用计数属性还带有对象共享的作用。

例如，键A创建了一个包含整数值100的字符串对象作为值对象，如果这是键B也要创建一个同样保存了整数100的字符串对象作为值对象，那么服务器有两种做法

为键B新创建一个包含整数值100的字符串对象
让键A和键B共享同一个字符串对象

第二种方法明显更节约内存

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

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

由图可见，除了对象的引用计数从之前的1变为2之外，其他属性都没有变化。

共享对象机制对于节约内存非常有帮助，数据库中保存的相同值对象越多，对象共享机制就能节约越多的资源。

假设数据库中保存了整数值100的键不止有A和两个，而是100个，那么服务器只需要用一个字符串对象的内存就可以保存原本需要100个字符串对象的内存才能保存的数据。

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

创建共享字符串对象的数量可以通过修改redis,h、REDIS_SHARD_INTEGERS常量来修改

这些共享对象不单单只有字符串键可以使用，那些在数据结构中嵌套了字符串对象的对象（linkedlist编码的列表对象，hashtable编码的哈希对象、hashtable编码的集合对象，zset编码的有序集合对象）都可以使用这些共享对象。

为什么不共享包含字符串的对象

因为只有在共享对象和目标对象完全相同的情况下，程序才会将共享对象用作键的值，共享对象保存的值越复杂，验证对象相同所需的复杂度越高，消耗的CPU时间越多

如果共享对象是保存整数值的字符串，验证的复杂度是O(1)
如果共享对象是保存字符串值的字符串，那么验证的复杂度是O(N)
如果共享对象是包含了多个值（或对象）的对象，比如列表对象或者哈希对象，那么验证的复杂度是O(N²)

对象的空转时长

redisObject结构还有一个为lru的属性，该属性记录了对象最后一次被命令程序访问的时间

typedef struct redisObject{
    // ...
    unsigned lru:22;
    // ...
} robj;

OBJECT IDLETIME命令可以打印出给定键的空转时长，这个空转时长是用过当前时间减去键的值对象的lru时间计算得出的。

OBJECT IDLETIME命令的实现是特殊的，这个命令在访问键的值对象是，不会修改值对象的lru属性

除了可以被OBJECT IDLETIME命令打印出来之外，键的空转时长还有另外一个作用，如果服务器打开了maxmemory选项，并且服务器使用的回收内存算法为 volatile-lru或者allkeys-lru，那么当服务器占用的内存数超过了maxmemory选项设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。

配置文件的maxmemory选项和maxmemory-policy选项说明介绍了关于这两个选项的更多信息

SDS

定义

SDS与C字符串的区别

获取字符串长度

避免缓冲区溢出

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

空间预分配

惰性空间释放

二进制安全

兼容部分C字符串函数

链表

链表及实现

Redis的链表特性：

字典

字典的实现

哈希表

哈希表节点

字典

哈希算法

解决键冲突

rehash

rehash步骤

rehash条件

渐进式rehash

渐进式rehash步骤

跳跃表

跳跃表的实现

跳跃表节点

1. 层

2. 前进指针

3. 跨度

4. 后退指针

5. 分值和成员

跳跃表

整数集合

整数集合的实现

升级

升级后新元素的摆放位置

升级的好处

提升灵活性

节约内存

降级

压缩列表

压缩列表的构成

压缩列表节点的构成

previous_entry_length

encoding

content

连锁更新

对象

对象的类型与编码

类型

编码和底层实现

字符串对象

编码的转换

列表对象

编码转换

哈希对象

编码转换

集合对象

编码的转换

有序集合对象

编码的转换

类型检查与命令多态

类型检查的实现

多态命令的实现

内存回收

对象共享

对象的空转时长

redis数据过期、内存淘汰、持久化

AbstractRoutingDataSource实现动态数据源切换