Redis经典五大类型源码及底层实现

Redis经典五大类型源码及底层实现分析

1、一些题目

  1. redis的zset底层实现？
  2. redis的跳表和压缩列表说一下，解决了哪些问题，时间复杂度和空间复杂度如何？
  3. redis的zset使用的是什么数据结构？

Redis数据类型的底层数据结构

  • SDS动态字符串
  • 双向链表
  • 压缩列表ziplist
  • 哈希表hashtable
  • 跳表skiplist
  • 整数集合intset
  • 快速列表quicklist
  • 紧凑列表listpack

源码位置

https://github.com/redis/redis

image-20231126200742850

2、Redis源代码核心部分文件名概览

2.1、Redis基本的数据结构-骨架

  • Redis对象object.c

  • 字符串t_string.c

  • 列表t_list.c

  • 字典t_hash.c

  • 集合及有序集合t_set.c和t_zset.c

  • 数据流t_stream.c

    Streams的底层实现结构listpack.c和rax.c，了解

  • 简单动态字符串sds.c

  • 整数集合intset.c

  • 压缩列表ziplist.c

  • 快速链表quicklist.c

  • listpack

  • 字典dict.c

2.2、Redis数据库的实现

  • 数据库的底层实现db.c
  • 持久化rdb.c和aof.c

2.3、Redis服务端和客户端实现

  • 事件驱动ae.c和ae_epoll.c
  • 网络连接anet.c和networking.c
  • 服务端程序server.c
  • 客户端程序redis-cli.c

其他的

  • 主从复制replication.c
  • 哨兵sentinel.c
  • 集群cluster.c
  • 其他数据结构，如hyperloglog.c、geo.c等
  • 其他功能，如pub/sub、Lua脚本

3、我们平时说redis是字典数据库KV键值对到底是什么？

怎样实现键值对(key-value）数据库的

  • key—般都是String类型的字符串对象

  • 而value类型则为redis对象(redisObject)

    value可以是字符串对象，也可以是集合数据类型的对象，比如List对象、Hash对象、Set对象和Zset对象

image-20231126203330006

Redis定义了redisObjec结构体来表示string、hash、list、set、zset等数据类型

  • Redis中每个对象都是一个redisObject结构

  • 字典和KV

    每个键值对都会有一个dictEntry

    源码位置:dict.h

    image-20231126205804807

    重点:从dictEntry到RedisObject

    找到server.h

    typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

    image-20231126210643834

    就是底层给定义的是dictEntry实际上给用户使用的是RedisObject

  • 这些键值对是如何保存进Redis并进行读取操作，O(1)复杂度

  • redisObject +Redis数据类型+Redis所有编码方式（底层实现)三者之间的关系

    image-20231206195654113

4、5大结构底层C语言源码分析

4.1、redis数据类型与数据结构总纲图

  • SDS动态字符串
  • 双向链表
  • 压缩列表ziplist
  • 哈希表hashtable
  • 跳表skiplist
  • 整数集合intset
  • 快速列表quicklist
  • 紧凑列表listpack

redis6的时候的底层模型与结构

String = SDS动态字符串
Set = intset + hashtable
ZSet = skipList + zipList
List = quicklist + zipList
Hash = hashtable + zipList

image-20231206202543717

redis7的时候的底层模型与结构

String = SDS动态字符串
Set = intset + hashtable
ZSet = skipList + listpack紧凑列表
List = quicklist 
Hash = hashtable + listpack紧凑列表

image-20231206201602085

4.2、从set hallo world说起

每个键值对都会有一个dictEntry

? set hello word为例，因为Redis是KV键值对的数据库，每个键值对都会有一个dictEntry(源码位置:
dict.h)，里面指向了key和value的指针，next指向下一个dictEntry。

? key是字符串，但是 Redis没有直接使用C的字符数组，而是存储在redis自定义的SDS中。

? value 既不是直接作为字符串存储，也不是直接存储在 SDS中，而是存储在redisobject中。

? 实际上五种常用的数据类型的任何一种，都是通过redisobject来存储的。

image-20231210110034915

  • 看类型 ：type键
  • 看编码：object encoding hello

image-20231210105638209

4.3、redisObjec结构的作用

? 为了便于操作，Redis采用redisObjec结构来统一五种不同的数据类型，这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。同时，为了识别不同的数据类型，redisObjec中定义了type和encoding字段对不同的数据类型加以区别。简单地说，redisObjec就是string、hash、list、set、zset的父类，可以在函数间传递时隐藏具体的类型信息，所以作者抽象了redisObjec结构来到达同样的目的。

server.h

typedef struct redisObject {
    unsigned type:4;	//对象的类型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET
    unsigned encoding:4; //具体的数据类型的编码方式：比如String就有三种编码方式：int embstr raw（即同一种数据类型可能有不同的编码方式）
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount; //引用计数。当refcount为0的时候，表示该对象已经不被任何对象引用，则可以进行垃圾回收了
    void *ptr; //指向对象实际的数据结构
} robj;

String就有三种编码方式：int embstr（嵌入式字符串） raw（即同一种数据类型可能有不同的编码方式）

编码类型：

image-20231210111436475

4.4、经典5大数据结构解析

4.4.1、各个类型的数据结构的编码映射和定义

object.c

char *strEncoding(int encoding) {
    switch(encoding) {
    case OBJ_ENCODING_RAW: return "raw";
    case OBJ_ENCODING_INT: return "int";
    case OBJ_ENCODING_HT: return "hashtable";
    case OBJ_ENCODING_QUICKLIST: return "quicklist";
    case OBJ_ENCODING_ZIPLIST: return "ziplist";
    case OBJ_ENCODING_LISTPACK: return "listpack";
    case OBJ_ENCODING_INTSET: return "intset";
    case OBJ_ENCODING_SKIPLIST: return "skiplist";
    case OBJ_ENCODING_EMBSTR: return "embstr";
    case OBJ_ENCODING_STREAM: return "stream";
    default: return "unknown";
    }
}
4.4.2、Debug Object key

image-20231210112500776

type 类型
encoding 编码，此处就是int
lru 最近被访问的时间
refcount 等于1，当前对象被引用的次数
ptr value的值，也就是17

Redis Debug Object命令是—个调试命令，它不应被客户端所使用。但是可以在配置文件中130-136行手动打开它

image-20231210142436865

image-20231210142541413

image-20231210142357245

  • value at:内存地址；
  • refcount:引用次数；
  • encoding:物理编码类型；
  • serializedlength:序列化后的长度〈注意这里的长度是序列化后的长度，保存为rdb文件时使用了该算法，不是真正存贮在内存的大小),会对字串做一些可能的压缩以便底层优化；
  • lru:记录最近使用时间戳；
  • lru_seconds_idle:空闲时间；
4.4.3、String数据结构介绍

3大物理编码方式

  • int

    保存long型(长整型)的64位(8个字节)有符号整数

    9223372036854775807 最多19位

    只有整数才会使用int，如果是浮点数，Redis，内部其实先将浮点数转化为字符串值，然后再保存。比如3.1415就会显示embstr类型

  • embstr 嵌入式字符串

    代表embstr 格式的SDs(Simple Dynamic String简单动态字符串),保存长度小于44字节的字符串

    EMBSTR顾名思义即: embedded string，表示嵌入式的string

  • raw 未经加工的

    保存长度大于44家节的字符串

案例测试

image-20231210144630371

? Redis没有直接复用C语言的字符串，而是新建了属于自己的结构-----SDS
? 在Redis数据库里，包含字符串值的键值对都是由SDS实现的(Redis中所有的键都是由字符串对象实现的即底层是由SDS实现，Redis中所有的值对象中包含的字符串对象底层也是由SDS实现)。

image-20231210145123314

SDS简单动态字符串

sds.h源码分析

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

image-20231210145539969

Redis中字符串的实现,SDS有多种结构（ sds.h）：

sdshdr5、(2^5=32byte)
sdshdr8、(2^8=256byte)
sdshdr16、(2^16=65536byte=64KB)
sdshdr32、(2^32byte=4GB)
sdshdr64，2的64次方byte=17179869184G用于存储不同的长度的字符串。
  • len表示 SDS的长度，使我们在获取字符串长度的时候可以在О(1)情况下拿到，而不是像∈那样需要遍历一遍字符串。
  • alloc可以用来计算 free就是字符串已经分配的未使用的空间，有了这个值就可以引入预分配空间的算法了，而不用去考虑内存分配的问题。
  • buf 表示字符串数组，真存数据的。

Redis为什么重新设计一个SDS数据结构?

C语言中字符串的展示：R e d i s

? C语言没有Java里面的String类型，只能是靠自己的char[]来实现，字符串在C语言中的存储方式，想要获取「Redis」的长度，需要从头开始遍历，直到遇到O’为止。所以，Redis 没有直接使用C语言传统的字符串标识，而是自己构建了一种名为简单动态字符串SDS(simpledynamic string）的抽象类型，并将SDS作为 Redis的默认字符串。

C语言 SDS
字符串长度处理 需要从头开始遍历，直到遇到’O’为止，时间复杂度O(N) 记录当前字符串的长度，直接读取即可，时间复杂度O(1)
内存重新分配 分配内存空间超过后，会导致数组下标越级或者内存分配溢出 空间预分配
sDS修改后，len长度小于1M，那么将会额外分配与len相同长度的未使用空间。如果修改后长度大于1M，那么将分配1M的使用空间。
惰性空间释放
有空间分配对应的就有空间释放。SDS缩短时并不会回收多余的内存空间，而是使用free字段将多出来的空间记录下来。如果后续有变更操作，直接使用free 中记录的空间，减少了内存的分配。
二进制安全 二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如‘O’等。前面提到过，C中字符串遇到‘lO’会结束，那‘O’之后的数据就读取不上了 根据len长度来判断字符串结束的，二进制安全的问题就解决了

源码分析

当我们set k1 v1底层发生了什么?调用关系

打开源码文件t_string.c 286行的一个方法

/* SET key value [NX] [XX] [KEEPTTL] [GET] [EX <seconds>] [PX <milliseconds>]
 *     [EXAT <seconds-timestamp>][PXAT <milliseconds-timestamp>] */
void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = OBJ_NO_FLAGS;

    if (parseExtendedStringArgumentsOrReply(c,&flags,&unit,&expire,COMMAND_SET) != C_OK) {
        return;
    }

    c->argv[2] = tryObjectEncoding(c->argv[2]);
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

我们使用set时调用了setCommand方法，然后使用tryObjectEncoding方法进行编码转换，然后再调用setGenericCommand写入数据。

示例：

set k1 123

当字符串键值的内容可以用一个64位有符号整形来表示时，Redis会将键值转化为long型来进行存储，此时即对应OBJ_ENCODING_INT编码类型。

内部的内存结构表示如下:

image-20231210175416742

Redis启动时会预先建立10000个分别存储0~9999的 redisObject 变量作为共享对象，这就意味着如果set字符串的键值在0~10000之间的话，则可以直接指向共享对象而不需要再建立新对象，此时健值不占空间!

set k1 123

set k2 123

image-20231210190854285

类似的在java中

String str1 ="123";
String str2 = str1;

总结

? 只有整数才会使用int，如果是浮点数，Redis 内部其实先将浮点数转化为字符串值，然后再保存embstr 与 raw类型底层的数据结构其实都是SD5(简单动态字符串，Redis内部定义sdshdr一种结构)。

int Long类型整数时，RedisObjet中的ptr指针直接赋值为整数数据，不再额外的指针再指向整数了，节省了指针的空间开销。
embstr 当保存的是字符串数据且字符串小于等于44字节时，embstr类型将会调用内存分配函数，只分配一块连续的内存空间，空间中依次包含redisObject与sdshdr两个数据结构，让元数据、指针和SDS是一块连续得到内存区域，这样可避免内存碎片。
raw 当字符串大于44字节时，SDS的数据量变多变大了，SDS和RedisObject布局分家各过各的，会给SDS分配多的空间并用指针指向SDS结构，raw类型将会调用两次内存分配函数，分配两块内存空间，一块用于包含redisObject结构，而另一块用于包含sdshdr结构。

image-20240111154512412

4.4.4、Hash数据结构介绍
redis6
  • ziplist
  • hashtable

案例

在虚拟机中拉取一个redis6.0.8版本的镜像

image-20240111160647422

根据此镜像启动一个容器redis6

image-20240111163402730

查看redis6的关于hash的配置

image-20240111163729879

再对比一下redis7的配置

image-20240111163853920

Hash类型键的字段个数小于 hash-max-ziplist-entries 并且每个字段名和字段值的长度小于 hash-max-ziplist-value时，Redis才会使用OB〕_ENCODING_ZTPLIST来存储该键，前述条件任意一个不满足则会转换为OBJ_ENCODING_HT的编码方式

更改一下规格

image-20240111171149394

演示转换

image-20240111171607743

结构

hash-max-ziplist-entries:使用压缩列表保存时哈希集合中的最大元素个数。

hash-max-ziplist-value:使用压缩列表保存时哈希集合中单个元素的最大长度。

结论

  1. 哈希对象保存的键值对数量小于512个；

  2. 所有的键值对的键和值的字符串长度都小于等于64字节时用ziplist，超过了就用hashtable

  3. ziplist升级到hashtable可以，反过来降级不可以

    一旦压缩列表转为了哈希表，hash类型就会一直用哈希表进行保存而不会再转回压缩列表了。在节省内存空间方面哈希表就没有压缩列表高效了。

流程

image-20240111172426277

源码分析

找到对应的源码文件

t_hash.c

在Redis 中, hashtable被称为字典(dictionary)，它是一个数组+链表的结构

OBJ_ENCODING_HT编码分析：

? 0BJ_ENCODING_HT这种编码方式内部才是真正的哈希表结构，或称为字典结构，其可以实现0(1)复杂度的读写操作，因此效率很高。在Redis内部，从OBJ_ENCODING_HT类型到底层真正的散列表数据结构是一层层嵌套下去的，组织关系见面图:

image-20240112103053397

image-20240112103039819

ziplist.c

? Ziplist压缩列表是一种紧凑编码格式，总体思想是多花时间来换取节约空间，即以部分读写性能为代价，来换取极高的内存空间利用率,==因此只会用于字段个数少，且字段值也较小的场景。==压缩列表内存利用率极高的原因与其连续内存的特性是分不开的。

  • ? ziplist为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组；
  • ? ziplist是一个经过特殊编码的双向链表，它不存储指向前一个链表节点prev和指向下一个链表节点的指针next而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率，节约内存，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面

image-20240114155216031

ziplist各个组成单元的意思

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

zlentry实体结构解析

typedef struct zlentry {
	unsigned int prevrawlensize; /*上一个链表节点占用的长度*/
  	unsigned int prevrawlen;/*存储上一个链表节点的长度数值所需要的字节数
*/
	unsigned int lensize;/*存储当前链表节点长度数值所需要的字节数*/	
	unsigned int len;/*当前链表节点占用的长度*/
	unsigned int headersize;/*当前链表节点的头部大小( prevrawlensize + lensize)，即非数据域的大小*/
	unsigned char encoding;/*编码方式*/
	unsigned char*p;/*压缩链表以字符串的形式保存，该指针指向当前节点起始位置*/
}zlentry;

ziplist存取情况：

先举个例子，hset user01包含id、cname、age三个entry

image-20240115105506707

对应的存取情况

image-20240115105613992

这里主要关心3个数据即可

  • prevlen：记录前一个节点的长度；
  • encoding：当前节点实际数据类型和长度；
  • data：记录当前节点的实际数据；

**zlentry解析：**压缩列表zlentry节点结构，每一个zlentry由前一个节点的长度、encoding和entry-data三部分组成

image-20240115110053934

image-20240115110428357

为什么zlentry这门设计？数组和链表数据结构对比

? privious_entry_length，encoding长度都可以根据编码方式推算，真正变化的是content，而icontent长度记录在encoding里，因此entry的长度就知道了。entry总长度= privious_entry_length字节数+encoding字节数+content字节数。

image-20240115110855601

为什么entry这么设计?记录前一个节点的长度?

链表在内存中，一般是不连续的，遍历相对比较慢，而ziplist可以很好的解决这个问题。如果知道了当前的起始地址，因为entry是连续的，entry后一定是另一个entry，想知道下一个entry的地址，只要将当前的起始地址加上当前entry总长度。如果还想遍历下一个entry，只要继续同样的操作。

已经有链表了为什么还要来一个压缩列表？

  1. 普通的双向链表会有两个指针，在存储数据很小的情况下，我们存储的实际数据的大小可能还没有指针占用的内存大，得不偿失。ziplist是一个特殊的双向链表没有维护双向指针:previous next，而是存储上一个entry的长度和当前entry的长度，通过长度推算下一个元素在什么地方。牺牲读取的性能，获得高效的存储空间，因为(简短字符串的情况)存储指针比存储entry长度更费内存。这是典型的“时间换空间”。
  2. 链表在内存中一般是不连续的，遍历相对比较慢而ziplist可以很好的解决这个问题，普通数组的遍历是根据数组里存储的数据类型找到下一个元素的(例如int类型的数组访问下一个元素时每次只需要移动一个sizeof(int)就行)，但是ziplist的每个节点的长度是可以不一样的，而我们面对不同长度的节点又不可能直接sizeof(entry)，所以ziplist只好将一些必要的偏移量信息记录在了每一个节点里，使之能跳到上一个节点或下一个节点。备注:sizeof实际上是获取了数据在内存中所占用的存储空间，以字节为单位来计数。
  3. 头节点里有头节点里同时还有一个参数len，和string类型提到的 SDS类似，这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表，直接拿到len值就可以了，这个时间复杂度是O(1)
ziplist总结
  • ziplist为了节省内存:采用了紧凑的连续存储。
  • ziplist是一个双向链表，可以在时间复杂度为O(1)下从头部、尾部进行pop或push.
  • 新增或更新元素可能会出现连锁更新现象(致命缺点导致被listpack替换)。
  • 不能保存过多的元素，否则查询效率就会降低，数量小和内容小的情况下可以使用。
redis7

  • listpack紧凑列表

  • hashtable

  • hash-max-listpack-entries:使用压缩列表保存时哈希集合中的最大元素个数。

  • hash-max-listpack-value:使用压缩列表保存时哈希集合中单个元素的最大长度。

Hash类型键的字段个数小于hash-max-listpack-entries且每个字段名和字段值的长度小于hash-max-listpack-value时，Redis才会使用OB〕_ENCODING_LISTPACK来存储该键，前述条件任意一个不满足则会转换为OBJ_ENCODING_HT的编码方式

实例验证：

更改一下原配置大小

image-20240115113923813

添加数据user02第一次只加两个，显示类型是listpack，再加两个就是hashtable

image-20240115114346861

明明有ziplist了，为什么出来一个listpack紧凑列表?

压缩列表的连锁更新问题

? 压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的prevlen占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。
? 案例说明:压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患

假设一个压缩列表中有多个连续的、长度在250-253之间的节点

image-20240117153931022

这些节点长度值小于254字节，所以prevlen属性需要用1字节的空间来保存这个长度值。

这时，如果将一个长度大于等于254字节的新节点加入到压缩列表的表头节点，即新节点将成为entry1的前置节点。

image-20240117154134434

因为entry1节点的prevlen属性只有1个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作并将entry1节点的prevlen属性从原来的1字节大小扩展为5字节大小。

这个时候连续更新的问题出现

image-20240117154826241

image-20240117154900559

image-20240117154925126

image-20240117154940094

entry1节点原本的长度在250~253之间，因为刚才的扩展空间，此时entry1节点的长度就大于等于254，因此原本entry2节点保存entry1节点的prevlen属性也必须从1字节扩展至5字节大小。entry1节点影响entry2节点，entry2节点影响entry3节载点…….一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」

listpack结构

listpack由4部分组成: total Bytes、Num Elem、Entry以及End

image-20240117155440224

total bytes 为整个listpack的空间大小，占用4个字节，每个listpack最多占用4294967295Bytes.
num-elements 为listpack中的元素个数，即Entry的个数占用2字节
element-1~elements-N 为每个具体的元素
listpack-end-byte 为listpack结束标志，占用1个字节，内容为0xFF

image-20240117160052127

entry结构

  • 当前元素的编码类型entry-encoding
  • 元数据entry-data
  • 编码类型和元数据两个部分的长度entry-len
  • listpackEntry结构定义：listpack.h
/* Each entry in the listpack is either a string or an integer. */
typedef struct {
    /* When string is used, it is provided with the length (slen). */
    unsigned char *sval;
    uint32_t slen;
    /* When integer is used, 'sval' is NULL, and lval holds the value. */
    long long lval;
} listpackEntry;

ziplist内存布局和listpack内存布局对比

image-20240117163701237

和ziplist列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免ziplist引起的连锁更新问题，listpack 中的每个列表项不再像ziplist列表项那样保存其前一个列表项的长度。

image-20240117163845025

4.4.5、List数据结构介绍

对于redis6来说

list = quicklist+ziplist

对于redis7来说

list = quicklist

list用quicklist来存储，quicklist存储了一个双向链表，每个节点都是一个ziplist

image-20240120150044699

redis6

案例

输出list相关配置信息

image-20240117182122244

（1）ziplist压缩配置：list_compress-depth 0

表示一个quicklist两端不被压缩的节点个数。这里的节点个数是指quicklist双向链表的节点，而不是指的ziplist中的数据项个数。

参数list_compress-depth的取值含义：

  • 0:是个特殊值，表示都不压缩。这是Redis的默认值。
  • 1：表示quicklist两端各有1个节点不压缩，中间的节点压缩。
  • 2：表示quicklist两端各有2个节点不压缩，中间的节点压缩。
  • 3：表示quicklist两端各有3个节点不压缩，中间的节点压缩。

依次类推。。。

（2）ziplist中的entry配置：list-max-ziploist-size -2

? 当取正值时，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。

这时，它只能取到-1到-5这5个值，每个值含义如下：

  • -5：每个quicklist节点上的ziplist大小不能超过64kb。（注：1kb => 1024 bytes）
  • -4：每个quicklist节点上的ziplist大小不能超过32kb。
  • -3：每个quicklist节点上的ziplist大小不能超过16kb。
  • -2：每个quicklist节点上的ziplist大小不能超过8kb。（-2是redis的默认值）
  • -1：每个quicklist节点上的ziplist大小不能超过4kb。

结论：

redis6中，quicklist就是 双向链表+压缩列表 的组合，因为一个quicklist就是一个链表，而链表中的每一个元素又是一个压缩列表。

quicklist实际上是ziplist和linkedList的混合体，它将linkedList按段切分，每一段使用ziplist来紧凑存储，多个ziplist之间使用双向指针串接起来。

image-20240120151340907

源码分析

quicklist.h，head和tail指向双向列表的表头和表尾

  • quicklist结构

    //redis7的quicklist.h
typedef struct quicklist {
    quicklistNode *head;//指向双向列表的表头
    quicklistNode *tail;//指向双向列表的表尾
    unsigned long count;        /* 所有的ziplist中一共存了多少个元素 */
    unsigned long len;          /* 双向链表的长度 */
    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

  • quicklistNode结构

    typedef struct quicklistNode {
    struct quicklistNode *prev;//前一个节点
    struct quicklistNode *next;//后一个节点
    //redis7中是：unsigned char *entry;
    unsigned char *zl;//是redis6中的，指向实际的ziplist
    size_t sz; /* 当前ziplist占用多少字节 */
    unsigned int count : 16;     /* 当前ziplist中存储了多少个元素，占16bit，最大65536 */
    unsigned int encoding : 2;   /* 是否采用了LZF压缩算法压缩字节，RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklistNode中的*zl指向一个ziplist，一个ziplist可以存放多个元素。

image-20240120153510255

redis7

输出list相关配置信息

image-20240120160731060

listpack紧凑列表，是用来代替ziplist的新数据结构，在7.0版本已经没有ziplist的配置了，6.0的数据类型作为过渡阶段在使用着。

实现：t_list.cl

void pushGenericCommand(client *c, int where, int xx) {
    int j;
    robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
    if (checkType(c,lobj,OBJ_LIST)) return;
    if (!lobj) {
        if (xx) {
            addReply(c, shared.czero);
            return;
        }
        lobj = createQuicklistObject();
        quicklistSetOptions(lobj->ptr, server.list_max_listpack_size,
                            server.list_compress_depth);//redis7版本，ziplist被listpack替换掉
        dbAdd(c->db,c->argv[1],lobj);
    }
    for (j = 2; j < c->argc; j++) {
        listTypePush(lobj,c->argv[j],where);
        server.dirty++;
    }
    addReplyLongLong(c, listTypeLength(lobj));
    char *event = (where == LIST_HEAD) ? "lpush" : "rpush";
    signalModifiedKey(c,c->db,c->argv[1]);
    notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
}

实现：object.c

robj *createQuicklistObject(void) {
    quicklist *l = quicklistCreate();
    robj *o = createObject(OBJ_LIST,l);
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}

redis7中quicklist就是listpack和linkedlist的结合体

4.4.6、set数据结构介绍

redis6和redis7都没有变，都一样的

Set的两种编码格式：

  • inset
  • hashtable

image-20240120164231876

image-20240120164331271

set-proc-title修改进程标题以显示一些运行时信息

Redis用intset或hashtable存储set。如果元素都是整数类型，就用intset存储。如果不是整数类型，就用hashtable（数组+链表的存储结构）。

image-20240120183521695

关于sadd命令的源码在t_set.c中

void saddCommand(client *c) {
    robj *set;
    int j, added = 0;

    set = lookupKeyWrite(c->db,c->argv[1]);
    if (checkType(c,set,OBJ_SET)) return;
    
    if (set == NULL) {
        set = setTypeCreate(c->argv[2]->ptr);
        dbAdd(c->db,c->argv[1],set);
    }

    for (j = 2; j < c->argc; j++) {
        if (setTypeAdd(set,c->argv[j]->ptr)) added++;
    }
    if (added) {
        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_SET,"sadd",c->argv[1],c->db->id);
    }
    server.dirty += added;
    addReplyLongLong(c,added);
}
int setTypeAdd(robj *subject, sds value) {
    long long llval;
    if (subject->encoding == OBJ_ENCODING_HT) {
        dict *ht = subject->ptr;
        dictEntry *de = dictAddRaw(ht,value,NULL);
        if (de) {
            dictSetKey(ht,de,sdsdup(value));
            dictSetVal(ht,de,NULL);
            return 1;
        }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) {
        if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
                /* Convert to regular set when the intset contains
                 * too many entries. */
                size_t max_entries = server.set_max_intset_entries;
                /* limit to 1G entries due to intset internals. */
                if (max_entries >= 1<<30) max_entries = 1<<30;
                if (intsetLen(subject->ptr) > max_entries)
                    setTypeConvert(subject,OBJ_ENCODING_HT);
                return 1;
            }
        } else {
            /* Failed to get integer from object, convert to regular set. */
            setTypeConvert(subject,OBJ_ENCODING_HT);

            /* The set *was* an intset and this value is not integer
             * encodable, so dictAdd should always work. */
            serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
            return 1;
        }
    } else {
        serverPanic("Unknown set encoding");
    }
    return 0;
}
4.4.7、zset数据结构介绍

ZSet的两种编码格式

  • redis6
    • ziplist
    • skiplist
  • redis7
    • listpack
    • skiplist

redis6关于zset的配置项

image-20240121162051899

redis7关于zset的配置项

image-20240121162021898

当有序集合中包含的元素数量超过服务器属性server.zset_max_ziplist_entries的值（默认值为128 ) ,或者有序集合中新添加元素的member的长度大于服务器属性 server.zset_max_ziplist_value的值（默认值为64）时，redis会使用跳跃表作为有序集合的底层实现。否则会使用ziplist作为有序集合的底层实现

image-20240121163009590

image-20240121163144477

image-20240121170218078

4.5、skiplist跳表分析

为什么引出跳表？

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高O(N)

解决方法：升维，用空间换时间

image-20240121171531327

优化1：

image-20240121171637280

从这个例子里，我们看出，加来一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是说查找效率提高了。

优化2：

画了一个包含64个结点的链表，按照前面讲的这种思路，建立了五级索引

image-20240121172318534

实际上跳表就是可以实现二分查找的有序链表

skiplist是一种空间换时间的结构，由于链表，无法进行二分查找，因此借鉴数据库索引的思想，提取出链表中关键节点(索引)，先在关键节点上查找，再进入下层链表查找，提取多层关键节点，就形成了跳跃表。

但是

由于索引也要占据一定空间的，所以，索引添加的越多，空间占用的越多

跳表 = 链表 + 多级索引

跳表时间+空间复杂度介绍

跳表的时间复杂度

时间复杂度是O(logN)

跳表查询的时间复杂度分析，如果链表里有N个结点，会有多少级索引呢?二分法查询。
按照我们前面讲的，两两取首。每两个结点会抽出一个结点作为上一级索引的结点，以此估算:

第一级索引的结点个数大约就是n/2；

第二级索引的结点个数大约就是n/4；

第三级索引的结点个数大约就是n/8，依次类推…

也就是说，第k级索引的结点个数是第k-1级索引的结点个数的1/2，那第k级索引结点的个数就是n/(2^k)

假设索引有h级，最高级的索引有2个结点。通过上面的公式,我们可以得到n(2h)=2，从而求得h=log2n-1

如果包含原始链表这一层，整个跳表的高度就是log2n.

image-20240121175945726

跳表的空间复杂度

首先原始链表长度为n,

两两取首，每层索引的结点数:n/2, n/4, n/8…，8，4,2每上升一级就减少一半，直到剩下2个结点,以此类推，如果我们把每层索引的结点数写出来，就是一个等比数列。

image-20240121180422054

这几级索引的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是O(n).也就是说，如果将包含n个结点的单链表构造成跳表，我们需要额外再用接近n个结点的存储空间。

思考三三取首，每层索引的结点数:n/3, n/9, n/27 …，9，3,1以此类推;
第一级索引需要大约n/3个结点，第二级索引需要大约n/9个结点。每往上一级，索引结点个数都除以3。为了方便计算，我们假设最高一级的索引结点个数是1。我们把每级索引的结点个数都写下来，也是一个等比数列

image-20240121180535288

通过等比数列求和公式，总的索引结点大约就是n/3+n/9+n/27+…+9+3+1=n/2。尽管空间复杂度还是O(n)，但比上面的每两个结点抽一个结点的索引构建方法，要减少了一半的索引结点存储空间。

所以空间复杂度是0(N)

优缺点

  • 优点
    • 跳表是一个最典型的空间换时间解决方案，而且只有在数据量较大的情况下才能体现出来优势。而且应该是读多写少的情况下才能使用，所以它的适用范围应该还是比较有限的
  • 缺点
    • 维护成本相对要高，在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是O(1)
    • 但是，新增或者删除时需要把所有索引都更新一遍，为了保证原始链表中数据的有序性，我们需要先找
      到要动作的位置，这个查找操作就会比较耗时最后在新增和删除的过程中的更新，时间复杂度也是O(log n)