Redis-底层数据结构篇

本文主讲Redis中常用数据类型的底层数据结构，对这些底层数据结构做分析

Redis常用的数据类型就String，List，Hash,Set,ZSet五个，这些都是键值对的数据形式

键值对的存储原理实际上不需要思考我们都知道怎么做，Redis作为一款极快的数据库，为了保证快，肯定是通过哈希表（空间换时间）来实现快的，哈希表的本质就是一个数组，这个数组里面的元素叫做哈希桶

这个哈希桶里面存储的是键值对数据的指针，通过指针来找到键值对数据，而不是直接存储键值对值瘢痕，这样做的目的是为了保证无论值是什么格式的，都可以通过指针来定位，通过下面的图可以看出

String

String的底层一直是SDS，SDS也称为简单动态字符串

那么为什么String没有使用Redis本身通过C语言实现的char * 来实现字符串，而是要通过SDS实现呢？

C语言字符串缺陷

• C语言中，字符串是通过最后的\0来确认字符串是否结束的，如果我存储了zx\0xiao,统计出来的字符串长度为2，不准。另一方面是，C语言并没有记录字符串长度，也就是说，要获取字符串长度需要O（n）的时间复杂度。
• 我们知道C语言的内存是需要自己管理的，但是C语言的字符串相关函数都不太安全，很容易导致缓存区溢出等问题导致进程终止
• 由于C语言的字符串是通过'\0'l来识别字符串结束的，因此无法存储二进制数据

SDS结构设计

• 通过len记录字符串长度，完美解决C语言的字符串无法正确记录字符串长度的问题，并且时间复杂度为O(1)
• alloc这个字段是用来计算这个字符串需要分配的空间大小，实现合理的空间分配，并且在修改字符串的时候通过动态更新字符串分配空间来解决修改时候的缓冲区溢出问题
• 通过buf[]来存储实际数据，就可以存储二进制数据了
• flags这个字段中主要是len和alloc的最大值不同，原来动态分配不同flags类型实现节省空间的作用

List

LIst在Redis的低版本中使用的是双向链表+压缩列表中实现的，数据量小的时候用压缩链表，数据量大的时候使用双向链表，后续统一改为quicklist实现

双向链表

双向链表的本质实际上和java中的链表是一致的，这里我们就不过多讲解了，我们只做分析

优点

既然使用了双向链表，那么头尾节点的获取时间复杂度是O(1)，并且节点可以存储任意数据类型的数据，因为节点存储的实际上是指针，通过指针来保存节点的值。

缺点

链表中节点多的情况下，希望随机获取部分节点的时候(不连续)。耗时长

一方面是由于随机获取节点需要做遍历。另一方面是节点在内存中存储不连续。因此无法利用CPU缓存。这里涉及到了CPU的缓存策略。CPU的缓存是取一整块数据做缓存的，并且根据局部性原理，CPU会预先把这块数据周围的数据提前做缓存，但是由于链表节点的不连续性，相当于白做缓存了。

还有一个缺点是保存一个节点要分配很多信息，前后节点指针等等，内存开销大

压缩列表

压缩列表是一种内存紧凑型的数据结构，这种结构主要是为了保证内存分配的连续，最大化利用CPU缓存的能力提高响应速度

压缩列表结构设计

• zlbytes，记录整个压缩列表占用对内存字节数；
• zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
• zllen，记录压缩列表包含的节点数量；
• zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）。

通过前三个字段的值，可以在O（1）的时间复杂度在搜索到头尾节点，但是其他节点的时间复杂度是O（n），因此不适合存储很多数据

压缩列表节点包含三部分内容：

• prevlen，记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
• encoding，记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
• data，记录了当前节点的实际数据，类型和长度都由 encoding 决定；

prelen取决于前一个节点的长度，254字节是边界，大于254的话，prelen需要5个字节空间，小于就1个字节。并且encoding也是根据数据的类型需要对于进行长度分配。引申出一个问题

连锁更新

假设我删除或新增了部分数据，会prelen从1个字节的分配改为5个字节，那么后面全部的空间都需要重新分配调整，导致性能大大下降

总结

压缩列表适合小数据量下的链表操作，虽然查找元素的时间复杂度是O（n），但是由于数据量小加上利用上了CPU缓存，本质上更加高效，并且内存上更加节省，即使发生连锁更新这种极端情况的开销也是在可以接受的范围内

记忆:一排书架上放书，好找。但是书之间的厚度不一，如果插入一本书超出书架，就要扩大空间并重新放后面的书。耗时up

quicklist

双向链表的问题在于内存不连续和内存消耗大，压缩列表的核心问题在于连锁更新和大数据时候的查询慢。

quicklist通过把 双向链表 + 压缩列表组合完美解决两者的缺点。quicklist是一个链表，每个节点存储这一个压缩链表。

通过控制每个链表节点的压缩链表大小来规避连锁更新的问题，提高访问性能

思考 为什么quicklist的每个节点不存储listpack🤔

这实际上是一个历史残留问题，早期的Redis，全部小聚合对象都是使用压缩列表在存储，但是后期发生压缩列表在哈希场景下性能和开销存在问题，才优化出listpack。list的quicklist中还没更新为listpack主要是还没来得及实现，也不太有必要，毕竟现在的quicklist已经解决连锁更新带来的问题了。

Hash

Hash类型的底层在低版本中是通过压缩链表 + 哈希表实现的

数量量小且值小就走压缩链表，超过的就走哈希表，redis7.0中统一使用listpack实现

哈希表

哈希表的本质是数组，每个元素存储指向哈希表节点的指针。每个节点存储key，value，next三个指针，next这个指针是用来解决哈希冲突的，通过单向链表解决哈希冲突。这一操作也称为链式哈希。数量量大 -》哈希冲突大 -》 链式哈希查询耗时大

因此需要对哈希表的大小进行处理 这一操作称为rehash

Redis使用一个dictht结构体表示哈希表，实际使用哈希表的时候，是使用dictht中的dict结构体。dict结构体里面有两个dictht结构体。一个用来正常使用。一个是备用，只会在rehash的时候使用。rehash步骤如下

• 给哈希表2分配空间，一般是表1的2倍空间
• 表1数据迁移到表2
• 置换表1表2的概念。

这里表1数据迁移到表2，在数据量大的情况下会导致Redis阻塞。于是有了一个渐进式rehash的概念

渐进式 rehash 步骤如下：

• 给「哈希表 2」 分配空间；
• 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；可以理解为被操作时触发迁移。
• 操作次数到了一定程度，表1剩余的数据量可以一次性迁移，触发一次性迁移操作

rehash的触发条件与负荷因子有关

对于这里的触发条件，记忆化理解

1. 节点 = 表大小，如果有空(没有做bgsave和bgrewitreaof)，那就rehash一下
2. 节点 = 5 * 表大小，哈希冲突太严重了，相当于每个位置有5个冲突，强制rehash

listpack

个人感觉listpack本质是基本就是照抄压缩列表，在这个基础上修正了连锁更新这个问题，因此整个链表都通过listpack去做就好了

len中记录data+encoding的长度，并且节点中没有字段是会根据前一个节点进行动态更新的了，避免了连锁更新的问题。

Set

Set 类型的底层数据结构是由哈希表或整数集合实现的：

元素是整数且小于512个用整数集合，不满足就用哈希表

整数集合

掠过，个人感觉这个设计实际上好像有点太个性化了，只是单独为了整数这种数据来单独做处理，并不具备设计上的思考，只是单纯极致内存开发的数据结构

ZSet

跳表

跳表是在链表的基础上，通过多层链表进行优化，实现快速定位数据。核心目标是在有序链表的基础上通过 “分层索引” 机制，实现近似二分查找的时间复杂度

跳表的数据结构如下

跳表的层次关系是通过zskiplistLevel实现的，存储着跨度和前向指针记录，跨度实际上就是记录节点在跳表中的排位

跳表的查询过程如下

• 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
• 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。

如果两个条件都不满足就会到下一层进行查找

跳表节点层数设置最好设置为相邻的两层，节点数为2 ： 1，保证近似二分查找的时间复杂度

用跳表而不是平衡树的原因出于以下三点考量

• 内存，平衡树每个节点要存储2个指针，跳表每个节点存储的指针数为 1/（1 - p） 如果是四层，那么p是1/4，每个节点平均是1.33个指针，更省内存
• 范围查询有优势，跳表有指针，范围查询性能简单，平衡树要找到某个最小值之后，按照中序遍历的顺序找实际上是毕竟麻烦的操作
• 算法实现难度来说，跳表的插入删除只需要修改指针，树还需要考虑平衡等