开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 大数据 -> Redis实现系列一（底层数据结构） -> 正文阅读

[大数据]Redis实现系列一（底层数据结构）

Redis实现系列一（底层数据结构）

作者：qystl
时间：2021.11.10

前言

本博客基于redis设计与实现第二版(书中基于redis 3.0版本)，因此大量图片示例等均来自这本书
另附上原作者对reids 3进行的中文注释版源码：github

想更多了解，请看原书

注：本文中所有命令示例运行环境为redis 5.0.14

1. 字符串

? 字符串可以说这是redis中最基础的实现，redis中存储的绝大多数key/value其实都是在存储字符串。redis是基于c语言编写，而却没有直接使用c中的字符串，而是自己构建了一个名为简单动态字符串的抽象类型（simple dynamic string，SDS） ，并将其用作redis的默认字符串表示。

? 在redis中c字符串只会作为字面量用作无须对字符串修改的地方，比如打印日志：

redisLog(REDIS_WARNING,"Redis is now ready to exit,bye bye")

? 而当redis使用一个可修改的字符串值的时候，就会使用SDS，例如：

127.0.0.1:6379> set msg "Redis"
OK

? 值得注意的是上面的命令会创建一个键值对，一个是键为msg的SDS，另一个就是值为Redis的SDS

另外SDS还被用做缓冲区，AOF模块中的缓冲区和客户端状态中的输入缓冲区，后面到这两个模块时会介绍

1.1 定义

//sds.h
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

free：表示buf中空余部分
len：表示buf中实际存储的部分，注意不包括多出的’\0’
buf：实际存储字符的数组

SDS保留了c中字符串以’\0’的惯例，这使得SDS可以使用部分的c函数，而不必全都自己实现相应的功能，而对于使用者而言，这个’\0’是完全透明和无感的。

1.2 SDS与c字符串区别（优点）

可以看见其实SDS和c本质都是字符数组，而SDS在此又多加了两个属性，即len和free，这就使得SDS更加灵活和便利，比如

常数级获取字符串的长度

SDS由于有len属性，所以仅需O(1)的时间就可以获取字符串长度
```
127.0.0.1:6379> STRLEN msg
(integer) 5
```
而c只能通过遍历数组，然后遇到的一个’\0’未结束来计算长度，strlen()函数就是这样实现的
杜绝缓冲和溢出

例：如果有两个c字符串，s1（“Redis”）和s2（“MongoDB”）

此时如果忘记给s1扩容而直接进行字符串拼接
```
strcat(s1," Cluster");
```
此时s1的内容就会溢出至s2上

而sds则会先判断buf的长度是否足够，如果不够会先扩容，然后进行存储

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

注意上面的sds扩容，可以发现free和len一致都是13，这是redis的扩容机制，redis为了防止字符串频繁修改带来的扩容问题，会在每次扩容时多扩展一部分

append操作：
- 如果是扩展后SDS的长度小于1MB，则会多扩展len作为free，即free=len
- 如果扩展后长度大于等于1MB，则多扩展1MB作为free
trim操作：
- 会将截取的部分作为free
此时如果再拼接，如果free够则会直接分配
1. 二进制安全
c使用’\0’作为字符串的结尾，因此在字符串中间不可以包含该字符

SDS则不会，因为SDS使用len来判断字符串是否结束，因此即便中间包含’\0’也不会产生影响

因此redis除了可以保存文本数据，还可以保存任意格式的二进制数据
1. 兼容部分c函数
之前提到过其实SDS和c字符串存储的本质是一致的，因此可以重用部分c语言的函数

总结：

1.3 SDS 主要API

2. 链表

? 链表作为一种常用的数据结构，由于c语言没有相应的实现，因此redis构建了自己的链表的实现。

? 链表在redis中的应用非常广泛，比如list类型的底层数据结构就是链表，此外，发布与订阅、慢查询、监视器等功能也使用了链表，后续会陆续对这些进行介绍。

注：在reids 3.2后不直接使用链表直接作为list类型的实现了，而是采用快速链表来作为list的实现

127.0.0.1:6379> EVAL "for i=1,10 do redis.call('rpush',KEYS[1],i)end" 1 integers
(nil)
127.0.0.1:6379> OBJECT encoding integers
"quicklist"

2.1 链表定义与实现

链表节点

//adlist.h
/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode

简单介绍下：void *，c语言中这种表示无类型指针，这种指针可以指向任意类型的数据，当用到具体类型的时候需要强转。

例：

int *a;
void *p;
p=a;
a=(int *)p

多个listNode就可以组成双端列表

虽然此时就可以直接使用了，但redis对其又进行封装，添加了部分属性

//adlist.h
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

    // 链表所包含的节点数量
    unsigned long len;

} list;

简单介绍下：void * (*dup)(void *ptr); 这是一个返回值为void *，参数为void * 类型的函数指针变量dup

可以看到list记录了链表的头节点和尾节点，并记录了包含的几点数量，意味着获取链表的长度以及获取头尾节点都是O(1)

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

所以redis实际的链表结构为：

总结：

redis的链表结构是双端链表
无环，头节点prev和尾节点next均为NULL
带有头尾节点，获取时间复杂度为O(1)
带有长度，获取时间复杂度为O(1)
多态，链表节点使用void * 指针，所以可以保存各种不同类型的值

2.2 相关API

3. 字典

? 在redis实现中将这个数据结构叫做字典，然而我更倾向于map（映射），本质是基于hash算法的键值对，类似java中的HashMap

? 由于redis是键值对数据库，因此可以将redis看作一个大的map

127.0.0.1:6379> set msg msg
OK

? 这个键值对就保存在代表数据库的map中

3.1 字典的实现

? redis的字典使用hash表作为底层实现

哈希节点

//dict.h
/*
 * 哈希表节点
 */
typedef struct dictEntry {
    
    // 键
    void *key;

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

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

} dictEntry;

简单介绍下 union，在c中这种类型叫共同体，和结构体的区别是，结构体的各个成员会占用不同的内存，互相之间没有影响，而共同体则是共用一段内存，长度等于最长成员的长度，同一时刻只能保存一个成员的值，如果对新的成员复制，则会把原来的成员覆盖掉

key是任意类型
值为v，可以是任意类型，当是int类型时，底层可能会用uint64_t和int64_t来存储
next，采用链表法来解决hash冲突问题

哈希表

//dict.h
/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

对哈希节点的封装

table：桶
size：哈希表大小（桶的大小）
sizemask：掩码，用来和hash值一起计算出索引，总等于size-1
used：已经存储的节点数

哈希表

例如将两个k0-v0和k1-v1两个键值对存进这个hash表

哈希表存储

注意：上面的哈希节点中只有next，因此每次发生hash冲突时，为了效率，k1-v1会直接插入到头部，而不是在尾部添加

字典

//dict.h
/*
 * 字典
 */
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

type：函数指针，代表特定函数
privdata：这些函数的可选参数
ht[2]：两个hash表，一个存储数据，另一个用作扩展空间时使用
rehashidx：扩展后需要重新计算索引，如果没出发rehash时，该值为-1
iterators：目前正在运行的安全迭代器的数量

//dict.h
/*
 * 字典类型特定函数
 */
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;

可以看到，redis在基础hash表的基础上又进行了一次封装，添加了一些特定函数，以及为哈希表的扩展做了准备（ht[2]，rehashidx）

下图展示了未进行rehash的字典

未进行rehash的字典

3.2 哈希算法

redis采用的hash算法是MurmurHash2算法（注意：在redis 4.0、5.0版本使用的siphash），如果感兴趣，请自行查找，我们这里仅关注执行步骤

//hash值
hash = dict->type->hashFunction(key);
//索引值,x根据情况可以是0或者1
index = hash & dict->ht[x].sizemark;

注意：理论上将一个值存储进hash表中所得的索引是通过%操作来实现的，但是redis使用的是&操作，这是可行且高效的（所以java中也是这么做的，具体请翻看HashMap源码），但仅当sizemark=(2 ^ n) - 1时两者是相等的，这就要求桶数组的size应该是2^n

hash冲突

? 当两个键的索引都在一个桶中的时候，此时就发生了hash冲突，redis采用链地址法来解决的，就是把所有冲突的键放入一个链表里，由于哈希节点里只有next，因此这个链表是单向列表，所以为了效率，会把新来的节点放在头部

此时新增k2-v2

当哈希表存储的节点超过或缩小一定数目时，就会触发rehash（扩展和收缩操作被包含在了rehash中），这是由负载因子决定的

3.3 rehash（扩展和收缩）

一般情况下，数据都会存储在ht[0]中，当达到一定的条件后就会触发哈希表的rehash

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

BGSAVE：用于在后台异步保存当前数据库到磁盘

? BGSAVE 命令执行之后立即返回 OK ，然后 Redis fork 出一个新子进程，原来的 Redis 进程(父进程)继续处理客户端请求，而子进程则负责将数据保存到磁盘，然后退出。

BGREWRITEAOF：用于异步执行一个 AOF（AppendOnly File）文件重写操作。

? 注意这个命令仅仅是告诉redis要进行重写，具体的AOF的重写操作是由redis自行触发的。

负载因子计算公式：

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

rehash执行步骤：

为ht[1]分配空间，具体大小为：
- 如果是扩展：ht[1].size = 2^n >= ht[0].used*2
- 如果是收缩：ht[1].size = 2^n >=ht[0].used
n都取最小值，例如used为3，那么扩展的size为8 ，收缩的size为4
将保存在ht[0]上的所有键值对rehash（重新计算索引）到ht[1]上，这个过程是迁移而不是复制
当ht[0]变为空表后，释放ht[0]，将ht[1]设为ht[0]，并未ht[1]创建一个新的空白哈希表，为下次rehash做准备

例如：

此时达到负载因子，触发rehash，计算新size为 2^3>=4*2 ，即为8

然后重新计算索引，并进行数据迁移至ht[1]

释放ht[0]，并将ht[1]设为ht[0]，为ht[1]新建空白哈希表

3.4 渐进式rehash

? 简单来说由于哈希表存储的数据量可能是极大的，如果一次性将所有数据都进行迁移，庞大的计算量可能会直接导致服务停止，因此为了避免这种情况，redis将数据的迁移放在了每次键值对的修改访问当中。

当rehash时：

为ht[1]分配空间
在字典中维持一个索引计数器，rehashindex=0，表示rehash正式开始
在rehash期间，每次添加、查找、删除或者更新操作时，程序除了完成相应的操作外，还会顺带将ht[0]中rehashindex索引上的数据迁移至ht[1]中，同时rehashindex+1
随着时间推移，所有数据都rehash到了ht[1]上，此时完成ht[0]和ht[1]的设置工作，并将rehashindex置为-1，表示完成

注意：在rehash期间的操作会同时使用两个哈希表，比如查找先会在ht[0]上查找，没找到则会查找ht[1]

3.5 主要API

4. 跳跃表

跳跃表是种有序数据结构，是基于有序链表的，是一种拿空间换时间的优化方法。

可以考虑有序列表的实现有两种，分别是数组和链表，而各有优劣

数组的访问比较快，然而插入和删除因为涉及挪动，因此访问O(1)，插入和删除O(n)
链表访问是O(n)，插入和删除是O(1)

那有没有什么办法弥补呢，跳跃表正基于此，使用二分的思想加速链表的访问，例如有这样一个有序链表L1

我们将一些节点设置为主要节点，从而提取出了第二条路径

此时箱方问55时可以看见，需要走过的长度就少了一半，如果多创建几层，这样访问节点的平均时间就是二分的时间即O(lgn)

比如此时想访问46

首先会在L4找，发现小于55
然后向下从L3中找，大于21，小于55
接着从L2的21节点向后寻找，发现大于37，小于55
最后在L1的37向后寻找，找到46

可以看到，跳跃表平均节点访问时间为O(lgn)，最坏情况O(n)

当然还有一些其他方面的问题，比如增加和删除节点后，关键节点怎么提取？还能否保证这种严格的二分？

关键节点怎么提取：跳跃表的设计者采用了抛硬币的办法，即随机决定新结点时候提取为关键节点

能否保证这种严格的二分：第一个问题就说明了，并不能，因为关键节点的提取是随机的，因此是可能存在最坏情况即O(n)的

跳跃表在redis中只有两种应用

有序集合zset
集群节点的内部数据结构

127.0.0.1:6379> ZADD zset 1 hehe 2 haha 3 xixi
(integer) 3
127.0.0.1:6379> OBJECT encoding zset
"ziplist"
127.0.0.1:6379> zadd zset 4 23763478263478623784678236478623487623876478262347826347823646278364782634786283746278364
(integer) 1
127.0.0.1:6379> OBJECT encoding zset
"skiplist"

注意：zset使用了两种结构，一种是压缩列表，另一种是跳跃表，转变触发条件后面会介绍

4.1 跳跃表的实现

跳跃表节点：

//redis.h
/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {

    // 成员对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

obj：具体的成员，是一个指针，指向一个字符串对象，而字符串对象保存一个SDS值
score：分值，注意使用double保存的
backward：后退指针
level[]：跳跃表层，层越多，访问速度越快，每次新创建时，程序会根据幂次定律随机生成一个介于1-32之间的值作为数组大小
- forward：前进指针
- span：跨度，用来记录两个节点间的距离，可以用作排位

注意：跳跃表要求成员唯一，按分值排序，分值可以相同，此时按成员字典序

跳跃表

//redis.h
/*
 * 跳跃表
 */
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

跳跃表对跳跃节点进行了封装

头尾指针：指向具体的跳跃节点
length：实际成员节点数（因为头节点是单独存在的）
level：这个跳跃表的层数

所以总体的跳跃表如下：

值得注意的有几点

头节点单独存在，且最多32层
length存储的是成员节点数，不包括头节点
可以看到跳跃表是可以从后往前遍历的，但是遍历的时间就是O(n)了
跳跃表的是有序的，跳跃表也正是基于此的（另外如果分值相同，则是按成员字典序）
跨度不包含起始，包含结束，仔细观察，跨度可以作为派位

比如起始到o3跨度为3，在跳跃表中o3的排位为3

再比如从起始到o2总跨度为2，因此o2的排位是2

现在我们模拟查找分值为2.0，成员为o2的节点

首先从L5开始，发现L5指向3.0大于2.0，于是从L4头部向后找，发现1.0小于2.0，到1.0节点

接着L4向后发现又到了3.0

向下从1.0的L3开始，同样过程，继续向下

从1.0的L2开始，发现正好等于2.0，成功找到

跳跃表API

5. 整数集合

? 整数集合（intset）是redis用来表示整数值集合的数据结构，用在set类型中

5.1 整数集合实现

//intset.h
typedef struct intset {
    
    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

encoding：表示整数的编码方式，有三种
- INTSET_ENC_INT16：表示int16_t类型的整数值，即两个字节int
- INTSET_ENC_INT32：表示int32_t类型的整数值，即四个字节int
- INTSET_ENC_INT64：表示int64_t类型的整数值，即八个字节int
length：元素数
contents：实际保存元素的数组，虽然声明为int8_t，但实际取决于实际类型

存储类型为int16_t，长度为5，因此contents数组大小占80位

存储类型为int64_t，长度为4，因此contents数组大小占256位

注意：虽然后三个只用int16_t就能存储，但第一个需要用int64_t存储，因此整体的类型就是int64_t

其实这么封装的主要原因是节约内存，同时也更加灵活

5.2 升级

可以看到intset有三种int类型的存储，因此可以根据存储的元素类型进行升级，例如现有的类型存不下，则会向上升级，这个过程分三步

根据新元素类型，扩展数组空间大小，并为新元素分配空间
将所有元素转换成新类型，并将转换后的元素放在正确的位置上（维持有序）
将新元素添加进去，然后修改length

例如现有一个intset

此时添加65565

第一步扩展空间，由于新的值需要int32_t，所以总空间大小位4*32共128位

第二部，将元素转换类型后，放在正确的位置上

第三步，添加新元素，length由3到4

需要注意的是，如果一个新的元素进来引发了升级，那么说明要么比所有值大，要么比所有值小，所以新增后总会在索引0或者length-1的位置

因为每次添加新元素都有可能引起升级，因此intset的时间复杂度是O(n)

另外，intset是不支持降级的，即一旦升级后，就会一直保持升级后的状态，如上面的情况，即使再将65535删除，类型也继续是int32_t

5.3 整数集合API

6. 压缩列表

? 压缩列表是redis为了节约内存而开发的，因此诸如hash类型、zset类型以及list都有应用压缩列表的地方。

127.0.0.1:6379> hset map a 100
(integer) 1
127.0.0.1:6379> OBJECT encoding map
"ziplist"

127.0.0.1:6379> ZADD zset 1 o1 2 o2 3 o3
(integer) 3
127.0.0.1:6379> OBJECT encoding zset
"ziplist"

//quicklist其实是链表+压缩列表的组合
127.0.0.1:6379> RPUSH list 3 1 4 5
(integer) 4
127.0.0.1:6379> OBJECT encoding list
"quicklist"

注意，hash类型和zset类型都有多种选择，因此当数据较少和较小时，为了节约内存会使用压缩列表，在某种条件下底层数据结构还是会进行切换的，具体下章会介绍到

6.1 压缩列表的构成

压缩列表

压缩列表没有使用结构体，而是通过宏来定位每个成员的地址

//ziplist.c
/*
 * ziplist 属性宏
 */
// 定位到 ziplist 的 bytes 属性，该属性记录了整个 ziplist 所占用的内存字节数
// 用于取出 bytes 属性的现有值，或者为 bytes 属性赋予新值
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
// 定位到 ziplist 的 offset 属性，该属性记录了到达表尾节点的偏移量
// 用于取出 offset 属性的现有值，或者为 offset 属性赋予新值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
// 定位到 ziplist 的 length 属性，该属性记录了 ziplist 包含的节点数量
// 用于取出 length 属性的现有值，或者为 length 属性赋予新值
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
// 返回 ziplist 表头的大小
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
// 返回指向 ziplist 第一个节点（的起始位置）的指针
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
// 返回指向 ziplist 最后一个节点（的起始位置）的指针
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
// 返回指向 ziplist 末端 ZIP_END （的起始位置）的指针
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

另外注意，zzlen当数量超过65535时，时间复杂度会上升至O(n)

示例：

zlbytes：0x50（80），意味着总长度80字节
zltail：0x3c（60），即最后一个节点的偏移量为60，p+60就是最后一个节点的地址
zllen：0x3（3）表示与压缩列表有三个节点

压缩列表节点

previous_entry_length：记录了前一个节点的长度，以字节为单位，通过该字段可实现向前遍历
- 如果前一个节点长度小于254字节，则这个字段占用一字节
- 否则这个字段占5个字节，第一个字节是标志设为0xFE(254)，剩下四字节保存长度
encoding：编码格式，同时也通过标志位来记录了长度
- 字节数组
  - 长度小于等于63（2^6-1）字节的字节数组
  - 长度小于等于2^14-1字节的字节数组
  - 长度小于等于2^32-1字节的字节数组
- 整数值
  - 4位长，0-12位之间的无符号整数
  - 1字节长的有符号整数
  - 3字节长的有符号整数
  - int16_t类型的整数
  - int32_t类型的整数
  - int64_t类型的整数
content：实际存数据的数组，类型由encoding决定

我们只需记得ziplist节点能最大能保存2^32-1字节的字节数组，或者8字节整形

previous_entry_length示例：

表示前一个节点位5个字节长

表示前一个节点0x00002766（10086）字节长

encoding示例

字节数组
整数

content示例：

? 根据上面的规则分析，这是长度小于63字节没具体长001011（11）字节长的字节数组

? 这个则是int16_t类型的整数，长度就是对应的2字节，值为10086

6.2 连锁更新

之前提到过previous_entry_length分别用1字节和5字节来存储前一个节点长度，其取决于前一个节点长度是否大于等于254字节，现在我们考虑一种极端情况，即目前存储的所有节点都是253个字节

此时在头部新增个节点长度大于等于254字节

由于原来e1的previous_entry_length是一个字节，此时则需要5个字节，那么e1也超过了254字节

从而发生一系列连锁反应

由于是连续地址，那么一次空间分配最坏时间复杂度就是O(n)，而如果发生上面的情况，那就发生了n次空间重分配，即最坏时间复杂度O(n^2)

当然这是最坏情况，通常发生几率还是很低的

首先，压缩列表恰好有多个长度介于250-253字节节点才会发生，实际不多见
另外，如果节点数量不多，也不会对性能造成任何影响

6.3 压缩列表API

7. 快速列表

此节参考以下几篇博客（并使用了部分图片）

https://www.yht7.com/news/88591

http://zhangtielei.com/posts/blog-redis-quicklist.html

之前提到过现在的list实现是quicklist（3.2版本后）

//例如现有一个list
127.0.0.1:6379> LRANGE list 0 -1
1) "3"
2) "1"
3) "4"
4) "5"

127.0.0.1:6379> OBJECT encoding list
"quicklist"

首先一点，为什么要新增quicklist，即原有的linkedlist和ziplist存在哪些问题

linkedlist：

双向链表便利在两端的push和pop操作，但是内存开销较大，每个节点都要多保存两个指针
双向链表的各个节点都是单独的内存块，地址不连续，节点多了容易产生内存碎片

ziplist：

ziplist是一个完整的内存块，存储效率高，但是不利于修改，每次数据变动都会引发一次内存的realloc（用于调整内存）
当ziplist长度很长的时候，大量的数据拷贝会进一步降低性能

于是结合双向链表和压缩列表的优点，quicklist出现了

quicklist实际就是链表+压缩列表

即将一些数据以ziplist保存，ziplist之间用双向链表连接

不过这样也产生了一个新的问题，即一个quicklist节点保存多长的ziplist合适呢？

太小比如ziplist中只保存一个数据，那么上面的结构就退化成了双向链表，且内存开销反而更大
太大，又存在ziplist的缺陷，修改效率低

redis配置

list-max-ziplist-size -2

这个配置即表示quicklist中ziplist最大长度，有五档可选

-5：大小不超过64kb
-4：32kb
-3：16kb
-2：8kb（默认）
-1：4kb（建议）

7.1 快速列表实现

快速列表

 * quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.
 * "count" is the number of total entries.
 * "len" is the number of quicklist nodes.
 * "compress" is: -1 if compression disabled, otherwise it"s the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * "fill" is the user-requested (or default) fill factor. 
 *

typedef struct quicklist {
    quicklistNode *head; //指向quicklist的头部
    quicklistNode *tail; //指向quicklist的尾部
    unsigned long count; //列表中所有数据项的个数总和
    unsigned int len;    //quicklist节点的个数，即ziplist的个数
    int fill : 16;       //ziplist数据项个数限制，由list-max-ziplist-size给定
    unsigned int compress : 16; //节点压缩深度设置，由list-compress-depth给定 0表示不压缩
} quicklist;

这里解释一下最后一个成员 compress，由于list经常当作队列使用，因此两端的数据访问是最频繁的，而相反，中间的部分访问频率相对较低，因此quicklist做了进一步优化，即支持中间部分无损压缩（lzf）

这个可以通过redis配置

list-compress-depth 0

0：默认，表示不压缩
1：表示两端各有一个节点不压缩，中间压缩
2：表示两端各有两个节点不压缩，中间压缩
以此类推，最大为2^16

快速列表节点

* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 12 bits, free for future use; pads out the remainder of 32 bits

typedef struct quicklistNode {
    struct quicklistNode *prev; //指向上一个ziplist节点
    struct quicklistNode *next; //指向下一个ziplist节点
    unsigned char *zl; //数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构
    unsigned int sz; //表示指向ziplist结构的总长度(内存占用长度)
    unsigned int count : 16; //表示ziplist中的数据项个数 占16bit
    unsigned int encoding : 2; //编码方式 RAW 1, LZF 2 占2bit，下面类似
    unsigned int container : 2;  //存放数据的方式 NONE 1, ZIPLIST 2
    unsigned int recompress : 1; // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
    unsigned int attempted_compress : 1; //测试相关，是否尝试压缩过
    unsigned int extra : 10; //扩展字段，留待使用
} quicklistNode;

可以看到，快速列表节点保存两种，一种是普通的ziplist结构，一种是压缩后的quicklistLZF

压缩的ziplist节点

 * quicklistLZF is a 4+N byte struct holding "sz" followed by "compressed".
 * "sz" is byte length of "compressed" field.
 * "compressed" is LZF data with total (compressed) length "sz"
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF

typedef struct quicklistLZF {
    unsigned int sz; // LZF压缩后占用的字节数
    char compressed[]; // 柔性数组，存放压缩后的ziplist字节数组
} quicklistLZF;

剩余源码部分请参考这篇博客

8. 对象

? 上面介绍了底层的数据结构，然而redis中没有直接使用，而是将类型与存储结构分离，通过对象封装，从而根据不同情况使用不同结构来进行优化，因此对于使用者来说，底层的数据结构其实是不可见的，且更换数据结构也不会影响类型的使用者。

? 此外这个对象还会维护一个引用计数器，用于内存回收，以及实现对象共享来进一步节约内存

? 最后redis对象带有访问时间记录，当服务器启动了maxmemory后，空转时间较大的对象会被优先删除

8.1 对象实现

/* The actual Redis Object */
/*
 * Redis 对象
 */
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
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;

tyep：数据类型，固定常量，左侧为实际对象，中间为对象取值，右侧为type命令输出值
encoding：底层实现对应的编码

除了上面的外，还有个 OBJ_ENCODING_QUICKLIST，另外REDIS_LIST只有一种编码，即OBJ_ENCODING_QUICKLIST

使用object encoding key可以查看对应的编码，例子在后续介绍具体对象类型时
lru：记录最近一次访问时间

可以通过object idletime获取到差值，另外这条命令不会刷新这个时间
```
127.0.0.1:6379> set msg hello
OK
127.0.0.1:6379> OBJECT idletime msg
(integer) 10
127.0.0.1:6379> OBJECT idletime msg
(integer) 14
127.0.0.1:6379> OBJECT idletime msg
(integer) 20

127.0.0.1:6379> get msg
"hello"
127.0.0.1:6379> OBJECT idletime msg
(integer) 2
```
这个空转时长的另外一个作用就是，当服务器开了maxmemory选项，且服务器的回收内存算法为volatile-lru或者allkeys-lru，那么当内存超过了最大内存设置的上限值，空转时长比较高的键会被优先释放，简单的说就是当内存不够时，服务器优先删除最久未使用键（lru是一种页面置换算法，可以用作缓存，实际是一回事）
refcount：被引用数量

当创建一个新对象时，引用计数会初始化为1，当被一个新程序引用时，引用数+1，反之-1，当这个数为0时，对象内存将被释放
ptr：实际存储的数据结构

注意：书中redis3.0的版本，而3.2后新增了OBJ_ENCODING_QUICKLIST编码用来对应快速列表，同时REDIS_* 都换成了OBJ_*，例如类型REDIS_STRING换成了OBJ_STRING，编码也是如此，但是对后续内容并没太大影响，因此之后将不做特别说明（list除外），并继续使用书中的类型和编码格式

相应的类型和编码源码可以查看3.2.8版本
https://github.com/menwenjun/redis_source_annotation/blob/master/object.c

8.2 字符串对象

字符串对应三种编码，分别是int、embstr，以及raw

如果字符串对象保存的是整数值，并且可以用long表示，则会将void*转换成long，并将编码设为int

int：

127.0.0.1:6379> set intstr 10086
OK
127.0.0.1:6379> OBJECT encoding intstr
"int"

? 注意：浮点类型的是用字符串保存的

127.0.0.1:6379> set doublestr 3.14
OK
127.0.0.1:6379> OBJECT encoding doublestr
"embstr"

当执行incr操作时，先转换为浮点数，计算完成后再将结果保存为字符串（有精度问题）

127.0.0.1:6379> INCRBYFLOAT doublestr 2.0
"5.14000000000000057"
127.0.0.1:6379> OBJECT encoding doublestr
"embstr"

embstr：

如果保存的是32字节及以下的字符串，则使用的是embstr编码，这是专门为短字符串优化的编码，底层也是使用SDS，区别在于这个编码会一次性的申请所有空间，而不是分别申请，再由ptr指向

127.0.0.1:6379> set embstr embstr_encoding
OK
127.0.0.1:6379> OBJECT encoding embstr
"embstr"

raw：

如果保存超过32字节字符串，则使用raw编码，这种编码和embstr的区别就是对象空间和sds是分开申请的

127.0.0.1:6379> set raw "zhe shi yi ge ce shi zi fu chuan bian ma de chuan ,shi yong raw"
OK
127.0.0.1:6379> OBJECT encoding raw
"raw"

embstr编码的优点

对象的创建缩短为一次，效率更高了
同样当释放的时候，也仅需释放一次
由于是用一块内存，可以更好的利用缓存带来的优势

编码转换：

int->raw ：只要不是一个int值后，就会转换为raw编码（但是同样即便新加的是整数也同样会转换），可通过incr等操作转换回来

127.0.0.1:6379> set intstr 10086
OK
127.0.0.1:6379> APPEND intstr 11
(integer) 7
127.0.0.1:6379> OBJECT encoding intstr
"raw"

那如果通过incr呢

127.0.0.1:6379> set intstr 10086
OK
127.0.0.1:6379> INCRBY intstr 12
(integer) 10098
127.0.0.1:6379> OBJECT encoding intstr
"int"
//可见，还是int

//但如果保存long最大范围呢
127.0.0.1:6379> set intstr 9223372036854775807
OK
127.0.0.1:6379> OBJECT encoding intstr
"int"
127.0.0.1:6379> INCR intstr
(error) ERR increment or decrement would overflow
//答案是不会进行编码转换，而是直接报错

//如果先转换完编码后再操作呢
127.0.0.1:6379> append intstr 1
(integer) 20
127.0.0.1:6379> OBJECT encoding intstr
"raw"
127.0.0.1:6379> INCR intstr
(error) ERR value is not an integer or out of range
//答案是不行，这里的实际原因是超范围

127.0.0.1:6379> set intstr 10086
OK
127.0.0.1:6379> append intstr 1
(integer) 6
127.0.0.1:6379> OBJECT encoding intstr
"raw"
127.0.0.1:6379> incr intstr
(integer) 100862
127.0.0.1:6379> OBJECT encoding intstr
"int"
//可以看到append后，虽然intstr变为了raw编码，但仍个自增，同时，这个操作会将编码转换为int

embstr->raw：redis没有为embstr编写任何的修改程序，因此embstr是只读的，想要修改会先转为raw，因此embstr的对象，在执行修改命令后总会转换为raw

127.0.0.1:6379> set embstr embstr_encoding
OK
127.0.0.1:6379> OBJECT encoding doublestr
"embstr"
127.0.0.1:6379> APPEND embstr a
(integer) 16
127.0.0.1:6379> OBJECT encoding embstr
"raw"

相关命令

8.3 列表对象

链表的当前编码只有一种，即OBJ_ENCODING_QUICKLIST

127.0.0.1:6379> rpush quicklist 1 2 3 4
(integer) 4
127.0.0.1:6379> OBJECT encoding quicklist
"quicklist"

列表命令（由于编码变了，以下仅作参考）

8.4 哈希对象

哈希对象有两种编码，ziplist和hashtable

当数据量较小，以及存储的字符串较小时，会使用ziplist，否则hashtable，具体的转换条件后续会详细介绍

ziplist编码：

127.0.0.1:6379> hset profile name Tom
(integer) 1
127.0.0.1:6379> hset profile age 25
(integer) 1
127.0.0.1:6379> hset profile career Programmer
(integer) 1
127.0.0.1:6379> OBJECT encoding profile
"ziplist"

ziplist会同时保存键和值在一个表中，每次先将键保存在表尾，再将值保存在表尾

hashtable编码：

每个键和值都是字符串对象，例如如果上面的例子用hashtable保存

编码转换：

当同时满足以下两个条件时，使用ziplist编码，不满足任意一个就会转换为hashtable，且一旦转换后，就不会再变了，因为频繁的数据转换反而会影响性能

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

//例如上述例子新增一个键值对
127.0.0.1:6379> hset profile changeht ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt
(integer) 1
127.0.0.1:6379> OBJECT encoding profile
"hashtable"

//此时删除
127.0.0.1:6379> HDEL profile changeht
(integer) 1
127.0.0.1:6379> OBJECT encoding profile
"hashtable"

长度大于512

//lua脚本，新建一个hash类型的numbers，添加了512个键和值都为i的键值对
127.0.0.1:6379> EVAL "for i=1,512 do redis.call('HSET',KEYS[1],i,i)end" 1 numbers
(nil)
127.0.0.1:6379> HLEN numbers
(integer) 512
127.0.0.1:6379> OBJECT encoding numbers
"ziplist"
127.0.0.1:6379> HSET numbers 513 513
(integer) 1
127.0.0.1:6379> OBJECT encoding numbers
"hashtable"

//此时如果删除一个键值对
127.0.0.1:6379> HDEL 513 513
(integer) 0
127.0.0.1:6379> OBJECT encoding numbers
"hashtable"
//可见即便重新满足条件，也不会在转换回ziplist

这两个值是可以配置的

hash-max-ziplist-value
hash-max-ziplist-entries

相关命令：

8.5 集合对象

set对象使用两种编码，intset和hashtable

这里其实有个问题，即为甚么set在数据量少的时候为什么不适用ziplist呢？

可能的一个原因是，set经常用作去重校验，因此无论数据量大小，遍历成了最常用的方式，而ziplist的遍历是O（n）级别，远不如hashtable的O（1）

而使用intset而不是ziplist存储整数的原因则在于，intset本质是一个整数数组，而ziplist则兼容了字符串，更加复杂一些，而且自适应的int型在少量数据的情况下，并没有比intset性能好更多，反而会在浪费一些无用的空间（比如表示前一个节点长度的previous_entry_length等字段），而set对象中使用intset的情景恰恰是小数据量时

intset：

127.0.0.1:6379> sadd numbers 1 3 5
(integer) 3
127.0.0.1:6379> OBJECT encoding numbers
"intset"

hashtable：

127.0.0.1:6379> SADD Dfruits apple banana cherry
(integer) 3
127.0.0.1:6379> OBJECT encoding Dfruits
"hashtable"

编码转换：

当同时满足以下两个条件时使用intset，否则将转换为hashtable，同样不可逆

集合保存的都是整数
元素数不超过512个，这个值可以由配置文件配置
```
set-max-intset-entries
```

//现有
127.0.0.1:6379> sadd numbers 1 3 5
(integer) 3
127.0.0.1:6379> OBJECT encoding numbers
"intset"

//此时新增个字符串
127.0.0.1:6379> SADD numbers seven
(integer) 1
127.0.0.1:6379> OBJECT encoding numbers
"hashtable"

//如果删除字符串
127.0.0.1:6379> SREM numbers seven
(integer) 1
127.0.0.1:6379> OBJECT encoding numbers
"hashtable"
//可见不会再转回intset

数量超出

//lua 创建一个512个元素为i的set
127.0.0.1:6379> EVAL "for i=1,512 do redis.call('SADD',KEYS[1],i)end" 1 integers
(nil)
127.0.0.1:6379> SCARD integers
(integer) 512
127.0.0.1:6379> OBJECT encoding integers
"intset"

//此时新增一个元素
127.0.0.1:6379> sadd integers 513
(integer) 1
127.0.0.1:6379> OBJECT encoding integers
"hashtable"

//删除不会转回
127.0.0.1:6379> srem integers 513
(integer) 1
127.0.0.1:6379> OBJECT encoding integers
"hashtable"

相关命令

8.6 有序集合对象

有序集合有两种编码，ziplist，和skiplist

? 有序集合使用ziplist的原理和set使用intset的目的其实是一样的，都是数据量小的时候ziplist的内存存储方式更优，而zset对象的source是浮点数，没法使用intset，而且ziplist存储的节点有序情况下，一些操作并不像set中无序那样每次都要遍历全部节点，因此ziplist完全可以胜任，而没必要类似intset专门新创造个数据结构存储。

ziplist：

127.0.0.1:6379> zadd price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3
127.0.0.1:6379> OBJECT encoding price
"ziplist"

skiplist：

跳跃表编码里，使用了zset结构体，除了跳跃表外，还使用了hashtable，将成员和source做了映射

/*
 * 有序集合
 */
typedef struct zset {

    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;

    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;

} zset;

为什么同时使用两种结构的原因是，zset中部分操作适合skiplist，而部分操作使用hashtable会更加便利（例如zrank和zrange等），因此同时使用，但是两种结构是通过指针来共享数据，并没有存储多份

将上面例子转为skiplist编码：

注意图示虽然分开画了，但实际数据是共享的

编码转换：

使用ziplist必须同时满足以下两个条件，否则将转换为skiplist编码

有序结合元素数不超过128
所有元素成员长度小于64字节

这两个条件可通过配置文件修改

zset-max-ziplist-entries
zset-max-ziplist-value

数目条件

127.0.0.1:6379> EVAL "for i=1,128 do redis.call('ZADD',KEYS[1],i,i)end" 1 numbers
(nil)
127.0.0.1:6379> ZCARD numbers
(integer) 128
127.0.0.1:6379> OBJECT encoding numbers
"ziplist"

//新增
127.0.0.1:6379> ZADD numbers 129 129
(integer) 1
127.0.0.1:6379> OBJECT encoding numbers
"skiplist"

127.0.0.1:6379> ZREM numbers 129
(integer) 1
127.0.0.1:6379> OBJECT encoding numbers
"skiplist"

长度

127.0.0.1:6379> zadd lenstr 1 first
(integer) 1
127.0.0.1:6379> object encoding lenstr
"ziplist"

//新增
127.0.0.1:6379> ZADD lenstr 2 ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
(integer) 1
127.0.0.1:6379> object encoding lenstr
"skiplist"

//删除
127.0.0.1:6379> ZREM lenstr ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
(integer) 1
127.0.0.1:6379> object encoding lenstr
"skiplist"

相关命令：

8.7 多态命令执行过程

8.8 对象共享

redis对象可以共享，例如俩个字符串指向的值一样，同时将这个对象的引用+1

? 注意这只是展示原理，实际是有所差别的，比如字符串是不共享的，共享的实际是整数字符串，同时共享的整数范围也是在初始化后就确定的，超出范围还是不会共享的

? 实际上redis会在初始化服务器时，创建一万个字符串对象，包含了从0-9999所有的整数值，所以当服务器需要用到值为0-9999的字符串对象时，服务器会共享，而不是创建新对象

127.0.0.1:6379> set shareobject 100
OK
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 2147483647
//可以看见，100一开始的引用计数就是int32_t的最大正整数

127.0.0.1:6379> set sameobject 100
OK
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 2147483647
127.0.0.1:6379> OBJECT refcount sameobject
(integer) 2147483647
//且即便再被共享，该值也不会变化

127.0.0.1:6379> del sameobject
(integer) 1
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 2147483647
//删除也不会引起这些值的变化

当超出缓存，只会新建

127.0.0.1:6379> set shareobject 10000
OK
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 1

127.0.0.1:6379> set sameobject 10000
OK
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 1
127.0.0.1:6379> OBJECT refcount sameobject
(integer) 1

字符串始终就不会共享，只会新建（思考一下也可以知道，如果共享字符串的话，验证起来是比较麻烦的，需要O（n）的时间复杂度，而如果共享的对象包含了多个值，那么光验证所需的时间就远大于共享带来的效益了）

127.0.0.1:6379> set shareobject testshare
OK
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 1

127.0.0.1:6379> set sameobject testshare
OK
127.0.0.1:6379> OBJECT refcount shareobject
(integer) 1
127.0.0.1:6379> OBJECT refcount sameobject
(integer) 1