【Redis】从数据结构走进Redis五大数据类型

数据结构

简单动态字符串（SDS）

Redis 是用 C 语言实现的，但是它没有直接使用 C 语言的 char* 字符数组来实现字符串，而是自己封装了一个名为简单动态字符串（simple dynamic string，SDS） 的数据结构来表示字符串。

C语言字符串

C 语言的字符串不足之处以及可以改进的地方：

• 获取字符串长度的时间复杂度为 O（N）；
• 字符串的结尾是以 “\0” 字符标识，字符串里面不能包含 “\0” 字符，因此不能保存二进制数据；
• 字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止。比如函数char *strcat(char *dest, const char* src);，可能会超出dest字符串长度。

结构设计

前三个属性len、alloc和flags都是结构体的头信息，只有buf字段才真正存储数据。

struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;   /* buf已保存的字符串字节数，不包含结束标示*/
uint8_t alloc; /* buf申请的总的字节数，不包含结束标示*/
unsigned char flags; /*不同SDS的头类型，用来控制SDS的头大小*/
char buf[];
}

结构中的每个成员变量分别介绍下：

• len，记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。

• alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。

• flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。这 5 种类型的主要区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

  除了设计不同类型的结构体，Redis 在编程上还使用了专门的编译优化来节省内存空间，即在 struct 声明了 __attribute__ ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

• buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。

flags字段的前3位用于表示SDS的类型：

• SDS_TYPE_5 (000): 使用5位存储长度信息，适用于长度较小的字符串。
• SDS_TYPE_8 (001): 使用1个字节（8位）存储长度信息。
• SDS_TYPE_16 (010): 使用2个字节（16位）存储长度信息。
• SDS_TYPE_32 (011): 使用4个字节（32位）存储长度信息。
• SDS_TYPE_64 (100): 使用8个字节（64位）存储长度信息。

动态扩容

当追加的字符串超过分配的空间时，会触发扩容机制：

• 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍 + 1（+1是为了保存一个结束标识'\0'）
• 如果新字符串大于1M，则新空间为扩展后字符串长度+ 1M + 1。称为内存预分配。

**示例：**初始有一个内容为"hi"的SDS，加上字符串",Amy"，新字符串长度小于1M，扩容为原本的2倍+1

整数集合（IntSet）

**整数集合是 Set 对象的实现方式之一。**具备长度可变、有序等特征，当一个 Set 对象只包含整数值元素，并且元素数量不大时，就会使用Intset这个数据结构作为底层实现。

结构设计

typedef struct intset {
uint32_t encoding; /* 编码方式，支持存放16位、32位、64位整数*/
uint32_t length;   /* 元素个数 */
int8_t contents[]; /* 整数数组，保存集合数据*/
} intset;

encoding的三种模式：

/* Note that these encodings are ordered, so:
* INTSET ENC INT16 <INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16(sizeof(int16_t)) /* 2字节整数，范围类似java的short*/
#define INTSET_ENC_INT32(sizeof(int32_t)) /* 4字节整数，范围类似java的int */
#define INTSET_ENC_INT64(sizeof(int64_t)) /* 8字节整数，范围类似java的long */

编码升级

当向intset中插入一个新整数且该整数超过了当前编码类型的范围时，intset会自动进行编码升级。

现在，假设有一个intset，元素为{5，10，20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节。我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。

以当前案例来说流程如下:

1. 升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组
2. 倒序依次将数组中的元素拷贝到扩容后的正确位置
3. 将待添加的元素放入数组末尾

字典（Dict）

Redis本身就是一个键值型的数据库，其核心就是通过高效的方式来存储和检索键值对。在Redis的内部，键值对的存储和管理依赖于一种叫做Dict（字典）的数据结构。

结构设计

Dict由三部分组成，分别是：哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)

哈希表：

typedef struct dictht {
// entry数组，数组中保存的是指向entry的指针
dictEntry **table;
// 哈希表大小，即哈希表桶（bucket）的数量
unsigned long size;
// 哈希表大小的掩码，等于size -1
unsigned long sizemask;
// 哈希表元素的个数
unsigned long used;
} dictht;

哈希节点：

typedef struct dictEntry {
void *key;	//键
union {
    void *val;
    uint64_t u64;
    int64_t s64;
    double d;
} v;		//值
//下一个Entry的指针
struct dictEntry *next;
} dictEntry;

字典：

typedef struct dict {
dictType *type; // dic类型，内置不同的hash函数
void *privdata; // 私有数据，在做特殊hash运算时用
dictht ht[2];   // 一个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用
long rehashidx; // rehash的进度，-1表示未进行
int16_t pauserehash;// rehash是否暂停，1则暂停，0则继续
} dict;

添加元素

当利用Dict添加元素时，Redis首先会根据key计算出hash值，然后利用哈希值对长度取余hash % size获取哈希表的下标。

当size的长度为2的倍数时，满足公式：hash % size == hash & (sizemask)。由于位运算可直接在内存进行操作，不需要转为十进制，所以性能更好。

**公式解释：**当哈希表的长度为2的倍数时，哈希表大小的掩码sizemask的二进制表示必然是多个1组成的1111，而1按位与任何数，都为数本身，所以可以达到对hash值取余的效果。

当有元素添加进来时，采用头插法插入元素，头插法的时间复杂度为 O(1)，能够在哈希冲突发生时迅速将新元素插入到链表中。

rehash

动态扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次增加键值对时都会检查负载因子（哈希表中元素的数量与哈希表桶数量的比值）LoadFactor = used/size，满足以下三 种情况时会触发哈希表扩容。

• 负载因子LoadFactor >= 1，并且服务器没有执行BGSAVE或者BGREWRITEAOF等后台进程；
• 负载因子LoadFactor > 5；

当Dict执行扩容时，需要扩容到第一个大于等于used + 1（哈希表中元素个数 + 1）的2 ^ n。

动态缩容

满足以下情况时，触发哈希表缩容。

• 负载因子LoadFactor < 0.1，会触发哈希表缩容

当Dict执行缩容时，需要缩容到第一个大于等于used（哈希表中元素个数）的2 ^ n，但不能小于初始大小4。

渐进式rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的:

1. 计算新hash表的size，值取决于当前要做的是扩容还是收缩:
   • 如果是扩容，则新size为第一个大于等于dict.ht[0].used+1的2^n
   • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n(不得小于4)
2. 按照新的size申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx=0，标示开始rehash
4. 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]桶上的所有元素rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]中。
5. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
6. 将rehashidx赋值为-1，代表rehash结束
7. 在rehash过程中，新增操作，则直接写入ht1]，查询、修改和删除则会在dict.ht{0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

Dict与HashMap

Dict

• 负载因子为5时扩容：较高的负载因子可以使得哈希表桶的数据更加紧凑，提高内存利用率；较高的负载因子可以减少扩容频率，减少资源消耗；在负载因子为 5 时，哈希表桶的链表相对较短，仍能保证相对较快的查找效率。
• 在负载因子较高时扩容，字典的空间利用率更高，这对于减少内存开销很有帮助。而在负载因子为5时，哈希冲突虽然较多，但Redis通过链表等机制处理冲突，依然能够保持较高的查询速度。
• 渐进式rehash：Redis在扩容时采用渐进式rehash（渐进式重新哈希），逐步将旧表中的键值对迁移到新表中，以避免扩容时阻塞Redis的正常操作。因此，Redis可以在负载因子较高时继续工作，并在扩容过程中平滑地处理大量数据。
• 单线程模型：Redis 是单线程处理模型，Dict 不需要处理线程安全问题。这使得 Dict 的操作可以更加简单和高效，因为不需要复杂的锁机制来同步多线程访问。
• 链地址法：

HashMap

• 负载因子为0.75时扩容：HashMap在设计时追求在插入和查找操作之间的平衡。负载因子为0.75时，哈希冲突率较低，查找和插入性能较高，同时又避免了内存的浪费。
• 即时扩容：与Redis不同，Java的HashMap在达到扩容阈值时会立即进行扩容操作，重新计算哈希值并将元素放置到新表中。这样做是为了保持插入和查找的性能，避免在高负载因子下，哈希冲突过多导致查询效率大幅下降。
• 多线程环境：HashMap 本身不是线程安全的，在多线程环境中使用时可能会出现并发修改异常或数据不一致问题。为此，Java 提供了 ConcurrentHashMap，它使用分段锁（Java 7 之前）或 CAS 操作（Java 8 之后）来实现线程安全的哈希表。
• 红黑树：

压缩列表（ZipList）

ZipList是一种特殊的“双端链表”，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作,并且该操作的时间复杂度为 0(1)。

结构设计

ZipList：

ZipListEntry：

ZipList中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用下面的结构：

• previous_entry_length：前一节点的长度，占1个或5个字节。
  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于254字节，则采用5个字节来保这个长度值，第一个字节为0xfe标记采用5字节，后四个字节才是真实长度数据
• encoding：编码属性，记录content的数据类型(字符串还是整数)以及长度，占用1个、2个或5个字节
• contents：负责保存节点的数据，可以是字符串或整数

encoding

ZipListEntry中的encoding编码分为字符串和整数两种，编码格式采用十六进制。

字符串

如果encoding是以"00"、"01"或者"10"开头，则证明content是字符串

例如，如果需要保存字符串"ab"和"bc"，abc的ASCII码从97依次递增

整数

如果encoding是以"11"开始，则证明content是整数，且encoding固定只占用1个字节

例如，如果需要保存整数"2"和"6"，省去content字段直接存储。

连锁更新问题

previous_entry_length：前一节点的长度，占1个或5个字节。

• 如果前一节点的长度小于等于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于254字节，则采用5个字节来保这个长度值，第一个字节为0xfe标记采用5字节，后四个字节才是真实长度数据

假设压缩列表有多个连续的、长度为250~253字节之间的entry，因此节点的previous_entry_length属性用1个字节即可表示，如图所示：

此时如果添加一个新的节点，长度超过了254字节，就会导致e1节点的previous_entry_length属性更新，采用5字节，从而导致后续的节点产生连锁更新的现象。

快速列表（QuickList）

压缩列表

压缩列表有以下缺点：

• ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低（找不到内存碎片）。
• ZipList存在连锁更新问题，元素越多越可能发生连锁更新问题。

结构设计

quickList：

typedef struct quicklist{
//quicklist的链表头
quicklistNode *head:
//quicklist的链表尾
quicklistNode *tail.
// 所有的压缩列表的总元素个数
unsigned long count;
// 压缩列表的个数
unsigned long len;
} quicklist;

限制大小

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制，默认值为-2。

• 如果值为正，则代表ZipList的允许的entry个数的最大值
• 如果值为负，则代表ZipList的最大内存大小，分5种情况

首位压缩

除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

• 0:特殊值，代表不压缩
• 1:标示QuickList的首尾各有1个节点不压缩，中间节点压缩
• 2:标示QuickList的首尾各有2个节点不压缩，中间节点压缩
• 以此类推

跳表（SkipList）

链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是O(N)，于是就出现了跳表。跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。

结构设计

zskiplist：

typedef struct zskiplist {
// 头尾节点指针
struct zskiplistNode *header, *tail;
// 节点数量
unsigned long length;
//最大的索引层级，默认是1
int level;
} zskiplist;

zskiplistNode：

typedef struct zskiplistNode {
sds ele;// 节点存储的值
doble score;// 节点分数，排序、查找用
struct zskiplistNode *backward;//前一个节点指针
struct zskiplistLevel {
    struct zskiplistNode *forward;//下一个节点指针
    unsigned long span; //索引跨度
} level[];// 多级索引数组
} zskiplistNode:

ZSet 对象要同时保存「元素」和「元素的权重」，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针（struct zskiplistNode *backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。

level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度用来记录两个节点之间的距离。

跨度实际上是为了计算这个节点在跳表中的排位。具体怎么做的呢？因为跳表中的节点都是按序排列的，那么计算某个节点排位的时候，从头节点点到该结点的查询路径上，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位。

举个例子，查找图中节点 3 在跳表中的排位，从头节点开始查找节点 3，查找的过程只经过了一个层（L2），并且层的跨度是 3，所以节点 3 在跳表中的排位是 3。

查询过程

查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件：

• 如果下一节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
• 如果下一节点的权重「等于」要查找的权重时，并且下一节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。
• 如果上面两个条件都不满足，或者下一个节点为空时，跳到当前节点的下一层。

如果需要查找「元素：abcd，权重：4」的节点，查找过程如下：

1. 先从头结点最高层开始，L2指向了「元素：abc，权重：3」节点，先查询该节点
2. 由于该层下一节点为NULL，所以跳到下一层，也就是「元素：abc，权重：3」节点的level[1]层
3. level[1]层的下一节点是「元素：abcde，权重：4」，当前的权重等于查找的权重，但是当前的元素大于查询的元素（abcde > abcd），所以跳转到下一层，也就是「元素：abc，权重：3」节点的level[0]层
4. 查询到「元素：abcd，权重：4」，正是要查询的节点，直接返回。

插入过程

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)。

具体的做法是，跳表在添加节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

插入一个新节点到跳表中，通常会涉及以下步骤：

1. 查找插入位置：
   • 如果下一节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
   • 如果下一节点的权重「等于」要查找的权重时，并且下一节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。
   • 如果上面两个条件都不满足，或者下一个节点为空时，跳到当前节点的下一层。
2. 随机生成层数：在跳表中，新节点的层数是随机生成的。层数越高，新节点的概率越低。
3. 插入新节点：
   • 更新与新节点相关的前驱节点和后继节点的指针，以保持跳表的正确性。
   • 如果插入的层数比当前跳表的最大层数要高，那么需要更新跳表的头节点层数。

删除过程

1. 查找删除位置：
   • 如果下一节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
   • 如果下一节点的权重「等于」要查找的权重时，并且下一节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。
   • 如果上面两个条件都不满足，或者下一个节点为空时，跳到当前节点的下一层。
2. 删除新节点：
   • 更新与原有节点相关的前驱节点和后继节点的指针，以保持跳表的正确性。
   • 如果删除后的层数比当前跳表的最大层数要低，那么需要更新跳表的头节点层数。

跳表与平衡树

• 从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
• 在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
• 从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。

listpack

listpack的目的是替代压缩列表，它的最大特点是 listpack 中每个节点不再包含前一个节点的长度，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

主要包含三个方面内容:

• encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码
• data，实际存放的数据:
• len，encoding+data的总长度:

可以看到，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

数据类型

常见数据类型

Redis 中比较常见的数据类型有下面这些：

• 5 种基础数据类型：String（字符串）、List（列表）、Hash（散列）、Set（集合）、Zset（有序集合）。
• 3 种特殊数据类型：HyperLogLog（基数统计）、Bitmap （位图）、Geospatial (地理位置)。

RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象。

Redis中会根据存储的数据类型不同，选择不同的编码方式。encoding的编码方式如下：

String

String 是最基本的key-value结构，key 是唯一标识，value 是具体的值。value不一定是字符串，也可以是数字(整数或浮点数)，value 最多可以容纳的数据长度是 512M。

• 其基本编码方式是RAW，基于简单动态字符串(SDS)实现，存储上限为512mb。
• 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。
• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码，直接将数据保存在RedisObject的ptr指针位置(刚好8字节)，不再需要SDS了。

List

List 结构类似一个双端链表，可以从首、尾操作列表中的元素。

• 在3.2版本之前，Redis采用LinkedList和ZipList编码来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码
• 在3.2版本之后，Redis统一采用QuickList编码来实现List

Set

Set 类型是一个无序并唯一的键值集合，它的存储顺序不会按照插入的先后顺序进行存储。

• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存。
• 为了查询效率和唯一性，Set采用HT编码(Dict)。Dict中的key用来存储元素，value统一为null

ZSet

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值。ZSet底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求，所以需要同时采用SkipList和HT这两种编码。

• SkipList：可以排序，并且可以同时存储score和ele值(member)
• HT：可以键值存储，并且可以根据key找value

当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此ZSet还会采用ZipList编码来节省内存，不过需要同时满足两个条件:

• 元素数量小于zset_max_ziplist_entries(默认值128)
• 每个元素都小于zset_max_ziplist_value(默认值64字节)

ZipList本身没有排序功能，而且没有键值对的概念，通过编码实现:

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry，element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

Hash

Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value

当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个:

• ZipList中的元素数量超过了hash-max-ziplist-entries(默认512)
• ZipList中的任意entry大小超过了hash-max-ziplist-value(默认64字节)