目录
2.5.1、为什么要用quicklist替代ziplist和linkedlist
1、Redis存储结构
- redisServer：redis服务端的抽象数据结构，默认情况下内部有16个redisDb。
- redisDb：redis数据库的抽象，每个redisDb内部包含1个dict字典和一个expires字典，dict字典保存所有键值对，expires字典保存键的过期时间。
- dict：redis字典，每个dict内部包含2个dictht(哈希表)，其中一个dictht正常存储数据；另一个dictht为空，在扩容时使用。
- dictht：哈希表，内含一个dictEntry数组，类似Java中HashMap的底层数组。可以把dictEntry数组理解成hash桶，然后通过链地址法解决hash冲突。
- dictEntry：redis中的key-value键值对节点，是redis存储实际数据的结构。
- redisObject：数据类型，常见的有String、hash、list、set、zset。
2、数据结构
2.1、简单动态字符串(SDS)
2.2.1、SDS数据结构
3.2版本前
struct sdshdr {
// 用于记录buf数组中已使用的字节的数量
int len;
// 用于记录buf数组中未使用的字节的数量
int free;
// 字节数组，用于储存字符串。
// 大小等于len+free+1，其中多余的1个字节是用来存储’\0’的
char buf[];
};3.2版本后
struct __attribute__ ((__packed__)) sdshdr5 {
//实际上这个类型redis不会被使用，因为没有剩余空间的字段，不方便扩容。他的内部结构也与其他sdshdr不同，直接看sdshdr8就好。
unsigned char flags; //一共8位，低3位用来存放真实的flags(类型),高5位用来存放len(长度)。
char buf[];//sds实际存放的位置
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;//表示当前sds的长度(单位是字节)
uint8_t alloc; //表示已为sds分配的内存大小(单位是字节)
//用一个字节表示当前sdshdr的类型，因为有sdshdr有五种类型，所以至少需要3位来表示
//000:sdshdr5，001:sdshdr8，010:sdshdr16，011:sdshdr32，100:sdshdr64。高5位用不到所以都为0。
unsigned char flags;
char buf[];//sds实际存放的位置
};
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[];
};2.2.2、编码
int、embstr、raw。
- int保存的是整数值对象，作为字符串保存
- raw会调用两次内存分配函数分别创建redisObject结构和sdshdr结构，内存不一定连续，释放时需要释放两次
- embstr编码只会调用一次内存分配函数来分配一个连续的内存空间，包含redisObject和sdshdr两个结构，释放时只需要释放一次
3.2版本前：embstr保存的是<=39字节的对象，raw保存的是大于39字节的对象。
embstr = redisObject + sdshdr(len + free + buf + 1) = 16 + 48(4 + 4 + 39 + 1) = 64
3.2版本后：embstr保存的是<=44字节的对象，raw保存的是大于44字节的对象。
embstr = redisObject + sdshdr(len + alloc + flags + buf) = 16 + 48(1 + 1 + 1 + 44 + 1) = 64
2.2.3、SDS与C字符串对比
C语言中使用char*字符数组表示字符串，'\0'来标记一个字符串的结束。
Redis将SDS作为默认字符串的底层标识结构，SDS中的len是int修饰的，所以限制SDS字符串容量为512MB。
Redis是C语言开发的，所以与C语言中的字符串相比，SDS有以下优势：
- 获取字符串长度高效
SDS结构包含len属性，获取字符串长度时间复杂度为O(1)
- C字符串获取字符串长度时间复杂度为O(N)
- 杜绝缓冲区溢出
C字符串未记录长度，在修改字符串时如果没有分配足够空间会导致缓冲区溢出；
SDS在修改字符串时会先判断字符串的长度是否足够，如果不够则会先扩展字符串空间。
- 减少修改字符串时带来的内存重分配次数
C字符串长度为字符长度+1，每次修改时都需要重新分配内存空间。
SDS使用free属性，允许空闲空间的存在，减少内存分配次数。
- 二进制安全
C字符串的字符只能保存文本数据，且以空字符结尾，所以字符串本身不能包含空字符，否则会被程序误认为是字符串结尾；
SDS的buf不保存字符，而是保存二进制数据，所以可以保存文本和二进制；通过len属性判断字符串是否结束。
- 兼容部分C字符串函数
C字符串可以使用所有<string.h>库中的函数；
SDS只可以使用一部分<string.h>库中的函数。
2.2、链表(Linkedlist)
2.2.1、链表数据结构(双向链表)
typedef struct listNode {
struct listNode *prev; // 前置结点
struct listNode *next; // 后置结点
void *value; // 节点值
} listNode;
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;2.2.2、特性
- 双向：获取某个结点的前置/后置节点的时间复杂度为O(1)
- 无环：表头结点的prev和表尾结点的next都指向NULL
- 表头表尾：获取表头/表尾的时间复杂度为O(1)
- 长度计数器：直接从list结构中获取
- 多态：通过void指针保存节点值，通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
2.3、跳表(Skiplist)
2.3.1、数据结构
一种有序数据结构，通过在每个结点中维护多个指向其他结点的指针，达到快速访问的目的。
跳表结点
typedef struct zskiplistNode {
sds ele; // 结点值
double score; // 分值
struct zskiplistNode *backward; // 后退指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度
} level[]; // 层
} zskiplistNode;跳表
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头结点和尾结点
unsigned long length; // 表中节点数量
int level; // 表中层数最大的结点的层数
} zskiplist;2.3.2、特点
- 跳表由很多层组成，每层都是一个有序链表；
- 最底层的编标包含所有元素；
- 跳表是一种随机化的数据结构，每个结点的层高都是1~32之间的随机数(抛硬币决定)；
- 如果一个元素出现在某一层的链表中，那么必然出现在该层之下的链表中；
- 每个结点包含两个指针，一个是指向同一层的下一个结点，一个是指向下一层的同个结点；
- 元素按结点分值从大到小排序，如果分值相同，则按成员对象大小排序。
2.3.3、增删查操作
插入
确定插入层数(抛硬币)，正面层数+1，反面停止，正面次数(记为m)即为插入层数。
将新元素根据结点分值，插入到跳表指定位置底层到m层。
删除
删除各个层指定值的结点，如果删除后只剩头尾两个结点，则删除这一层。
查询
查询结点，当前结点，下一个结点(为当前结点同一层的下一个结点)
1、从最高层第一个结点开始查找
2、如果查询结点等于当前结点，直接返回当前结点
3、如果查询结点小于当前结点，直接返回空
4、如果查询结点>当前层下一个结点，则设置当前结点 = 下一个结点，然后继续查找
5、如果查询结点>当前结点 且 查询结点<当前层下一个结点，则层数下移一层继续查找
2.4、压缩列表(Ziplist)
- 将数据按照一定规则编码在一块连续的内存区域，而不是对数据进行压缩，从而节省内存。
- 一个压缩列表可以包含多个结点，每个结点可以保存一个字节数组或一个整数值。
- 内存连续，在修改时需要重新分配内存。
- 查找首尾元素，时间复杂度为O(1)；查找中间元素，时间复杂度为O(N)。
- 压缩列表不能保存过多的元素，否则查询效率就会降低O(N)。
2.4.1、数据结构
| 字段 | 长度 | 说明 |
| zlbytes | 4 Byte | 用于记录整个压缩列表占用的内存字节数。在对压缩列表进行内存重分配或计算 zlend 的位置时使用 |
| zltail | 4 Byte | 记录尾结点距离压缩列表的起始地址有多少字节。通过该偏移量，无需遍历整个压缩列表就可以确定尾结点的地址 |
| zllen | 2 Byte | 压缩列表元素个数 |
| entryX | 不定 | 压缩列表包含的各个结点，结点的长度由结点保存的内容决定 |
| zlend | 1 字节 | 压缩列表结束标识，值等于0xFF |
| previous_entry_length | 1 Byte、5 Byte | 前一个节点的长度： 如果前一个节点的长度小于254字节，则需要1字节来保存前一个节点的长度； 如果前一个节点的长度大于等于254字节，则需要5字节来保存前一个节点的长度，第一个字节固定为0xfe(254)，后四个字节表示前一个节点的长度。 |
| encoding | 1Byte、2Byte、5Byte | 编码类型(字节数组、长度)： 数据是整数，则使用 1 字节的空间进行编码； 数据是字符串，根据字符串的长度大小，使用 1 字节/2字节/5字节的空间进行编码。 |
| content | 不定 | 结点数据，记录了当前节点的实际数据 |
2.4.2、连锁更新问题
- 问题场景：新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。
- 问题根源：压缩列表结点的previous_entry_length属性大小，可能根据前一个结点长度的变化而变化，前一个结点长度到达临界值时(254字节)，触发当前结点的空间扩展操作。
- 举例说明：
1、压缩列表有B->C->D->E四个结点，每个结点的长度都在253字节，均小于254字节，所以每个结点的previous_entry_length属性均占用1个字节；
2、将一个长度>=254字节的A结点，加入到压缩列表的表头位置，即A结点为B结点的前置结点；
3、对于B来说，前置结点A的长度>=254,所以B结点的previous_entry_length属性需要扩展为5个字节，此时B的结点长度为257字节；
4、对于C来说，前置结点B的长度>=254,所以C结点的previous_entry_length属性需要扩展为5个字节，此时C的结点长度为257字节；
5、....................
6、以此类推，如果压缩列表中元素很多，且每个结点原本的长度都在临界范围时(250~253字节)，则需要进行大量的空间扩展。
- 问题结果：空间扩展也就是重新分配内存，连锁更新场景下，压缩列表的内存空间需要多次重新分配，直接影响压缩列表的访问性能。
2.5、快表(Quicklist)
- 快表 = 压缩列表 + 双向链表。
- Redis3.2之前，采用ziplist和linkedlist实现列表；Redis3.2之后，采用quicklist实现列表。
2.5.1、为什么要用quicklist替代ziplist和linkedlist
- ziplist内部存储是一块连续空间，数据量大的场景下，需要很大一块内存空间，但内存中不一定有；
- linkedlist每个结点分配一块内存，可能造成大量的内存碎片。
2.5.2、快表
- 将链表按段切分，每一段使用压缩列表进行内存的连续存储，多个压缩列表通过prev和next指针组成的双向链表。它结合了压缩列表和链表的优势，进一步压缩了内存的使用量，提高了查询效率。
- quicklist默认单个ziplist长度为8KB，超出这个字节数，就会另起一个ziplist，ziplist的长度由配置参数 list-max-ziplist-size 决定。
快速列表
typedef struct quicklist {
quicklistNode *head; // 头结点
quicklistNode *tail; // 尾结点
unsigned long count; // 元素个数
unsigned long len; // quicklistNodes个数
int fill : 16; // 每个 quicklistNodes 节点中 ziplist 的长度
// 列表常被访问的是两端的数据，如果中间数据过多，会造成内存浪费，为了节省内存，则需要对中间节点进行压缩。compress 就代表了两端各有 compress 个节点不用压缩
unsigned int compress : 16; // 默认为0，表示不压缩。compress > 0, 进行压缩，但两端各有compress个节点不用压缩。
} quicklist;快速列表节点
typedef struct quicklistNode {
struct quicklistNode *prev; // 前置结点指针
struct quicklistNode *next; // 后置结点指针
unsigned char *zl; // 结点未被压缩，指向ziplist结构；结点被压缩，指向quicklistLZF结构。
unsigned int sz; // 整个 ziplist 的大小
unsigned int count : 16; // ziplist 中的节点数
unsigned int encoding : 2; // 表示结点是否被压缩：1-未压缩；2-已被压缩
unsigned int container : 2; // 预留字段，默认为2，表示使用ziplist结构保存数据
unsigned int recompress : 1; // 查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩
unsigned int attempted_compress : 1; // 测试时使用，无需理会
unsigned int extra : 10; // 预留字段
} quicklistNode;被压缩的列表
typedef struct quicklistLZF {
unsigned int sz; // 被压缩后占的字节数
char compressed[]; // 被压缩后的节点
} quicklistLZF;2.6、整数集合(Intset)
- 用于保存类型为int16_t、int32_t、int64_t的有序、元素不重复的整数值。
- 当一个集合中只包含整数，且这个集合中的元素数量不多时，Redis就会使用整数集合intset。
- 当新增的元素类型长度比原集合元素类型的长度要大时，intset就会升级，将集合中的所有元素升级(节省内存)成新元素的类型。
- intset只能升级不能降级。
typedef struct intset{
uint32_t encoding; //编码方式
uint32_t length; //集合包含的元素数量
int8_t contents[]; //保存元素的数组
}intset;升级过程
- 根据新元素类型，扩展整数集合底层数组的大小，并为新元素分配空间。
- 将底层数组现有的所有元素都转成与新元素相同类型的元素，并将转换后的元素放到正确的位置，放置过程中，维持整个元素顺序都是有序的。
- 将新元素添加到整数集合中(保证有序)。
2.7、字典(Dictionary)
- 可参考Java的HashMap数据结构辅助理解，底层为数组 + 链表。
- 用于保存键值对的抽象数据结构。底层为哈希表，一个哈希表里有多个哈希表结点，每个哈希表结点保存一个键值对。
2.7.1、字典
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // hash表
int rehashidx; // rehash 索引，当 rehash 不在进行时，值为 -1
} dict;2.7.2、hash表
typedef struct dictht {
dictEntry **table; // hash表数组(桶)，初始大小为4
unsigned long size; // hash表大小
unsigned long sizemask; // hash表大小掩码，用于计算索引值， = size - 1
unsigned long used; // 该hash表已有节点的数量
} dictht;2.7.3、hash表结点
typedef struct dictEntry {
void *key; // 键
union {
void *val;
uint64_t u64;
int64_t s64;
} v; // 值
struct dictEntry *next; // 指向下个哈希表节点，形成链表
} dictEntry;- key保存键，val保存值，值可以是指针，也可以是整数。通过链地址法解决哈希冲突(链表)。
- 新结点会添加到链表的表头位置。
2.7.4、扩容：采用渐进式rehash策略
假设当前使用的哈希表为ht[0]
rehash
- 为ht[1]分配一块新的内存(大小为原hash表的2倍)
- 对ht[0]中的每个数据的key进行再hash，将数据放入ht[1]中
- 释放ht[0]空间
- rehash过程中，会阻塞服务(如果数据量大，会导致Redis在一段时间内不能提供服务)
渐进式rehash
- 为ht[1]分配一块新的内存(大小为原hash表的2倍)
- 在字典中维持一个索引计数变量rehashidx(桶位置)，初始为0，表示渐进式rehash开始
- 对ht[0]的删改查操作，都会触发一次rehash，把ht[0]的中ht[0].table[rehashidx]位置的数据挪到ht[1]，然后设置rehashidx = rehashidx+1(表示下次将rehash下一个桶)
- 新增操作则会直接hash到ht[1]中
- 每次rehash函数最后会判断h[0].used==0，为true，则设置rehashidx = -1，结束渐进式rehash过程
以上内容为个人学习理解，如有问题，欢迎在评论区指出。
部分内容截取自网络，如有侵权，联系作者删除。