数据结构
Redis 提供了丰富的数据类型,常见的有五种数据类型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合)。
随着 Redis 版本的更新,后面又支持了四种数据类型:BitMap(2.2 版新增)、HyperLogLog(2.8 版新增)、GEO(3.2 版新增)、Stream(5.0 版新增)。
zset底层实现-跳表
跳表(Skip List)
是一种数据结构,它的核心思想是通过“跳跃”来加速查找、插入和删除操作。
想象你有一排有序的数字,比如 [1, 3, 5, 7, 9, 11],你想快速找到某个数,比如 7。如果用普通链表,一个个找过去(线性查找),最坏情况要查 6 次。如果是二叉搜索树,可以跳着找,效率高很多。跳表就是想让链表也能“跳着找”,通过增加多层索引来实现。
比如,假设底层链表是:[1 -> 3 -> 5 -> 7 -> 9 -> 11]
第一层索引可能是(随机选一部分节点,比如 3 和 9):[3 -> 9]
第二层索引可能是(再从第一层随机选,比如只有 9):[9]
完整结构就像这样:
层 2: [9]↓
层 1: [3 -> 9]↓ ↓
层 0: [1 -> 3 -> 5 -> 7 -> 9 -> 11]
- 从最高层(层 2)开始,只有 [9],9 > 7,跳不动,往下到层 1。
- 层 1 是 [3 -> 9],从 3 开始,3 < 7,往右跳到 9,9 > 7,跳不动,往下到层 0。
- 层 0 是 [1 -> 3 -> 5 -> 7 -> 9 -> 11],从 3 开始,3 < 7,跳到 5,5 < 7,跳到 7,找到!
每一层的索引不是真的去创建新结点,而是利用一个 level 数组
:
typedef struct zskiplistNode {//Zset 对象的元素值sds ele;//元素权重值double score;//后向指针struct zskiplistNode *backward;//节点的level数组,保存每层上的前向指针和跨度struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];
} zskiplistNode;
Redis 跳表在创建节点的时候,随机生成每个节点的层数:跳表在创建节点时候,会生成范围为[0-1]的一个随机数,如果这个随机数小于 0.25(相当于概率 25%),那么层数就增加 1 层,然后继续生成下一个随机数,直到随机数的结果大于 0.25 结束,最终确定该节点的层数。
跳表 vs B+树
- 代码简单:Redis 是内存数据库,跳表代码实现比 B+ 树简单得多,开发者希望尽量减少维护复杂数据结构的开销。
- 容易调整:ZSET 经常需要插入和删除元素,跳表的动态调整(随机层数)比 B+ 树的节点分裂/合并更轻量。
- Redis 数据在内存中,不需要优化磁盘I/O,因此 B+ 树的磁盘友好特性(叶子结点顺序排列,可一次读取)对 Redis 意义不大。
压缩列表和listpack
压缩列表
想象你有一堆小纸条,上面写着数字 [1, 2, 3]。传统链表会给每个数字单独包一个信封(节点),每个信封还有地址标签指向下一个,占空间多。压缩列表就像把这些数字直接顺序排列在一起节省空间。
压缩列表是一个字节数组,分为几个部分:
头部(元数据):
- zlbytes(4 字节):整个压缩列表的总字节数。
- zltail(4 字节):尾节点相对于起点的偏移量(方便从尾部访问)。
- zllen(2 字节):节点数量(如果超过 65535,就需要遍历计算真实数量)。
- entry1, entry2, …:实际存储的节点数据。
- zlend(1 字节):结束标记,固定为 0xFF。
节点(entry): 每个节点由三部分组成:
- previous_length:前一个节点的长度(变长编码,1 或 5 字节)。
- encoding:当前节点的编码类型和长度(变长编码)。
- content:实际数据内容。
压缩列表的缺点是会发生连锁更新的问题,因此连锁更新一旦发生,就会导致压缩列表占用的内存空间要多次重新分配,这就会直接影响到压缩列表的访问性能。
listpack
可以看到,listpack 没有压缩列表中记录前一个节点长度的字段了,listpack 只记录当前节点的长度,当我们向 listpack 加入一个新元素的时候,不会影响其他节点的长度字段的变化,从而避免了压缩列表的连锁更新问题。
哈希表扩容
两张哈希表,表1放数据;
表1满了给表2分空间(2倍),数据复制到表2,原表1释放,表2变表1;
新建空表2;
如果「哈希表 1 」的数据量非常大,那么在迁移至「哈希表 2 」的时候,因为会涉及大量的数据拷贝,此时可能会对 Redis 造成阻塞,无法服务其他请求。
渐进式更新:在 rehash 进行期间,每次哈希表元素进行新增、删除、查找或者更新操作时,Redis 除了会执行对应的操作之外,还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上,最终「哈希表 1 」变空表。
查找一个 key 的值的话,先会在「哈希表 1」 里面进行查找,如果没找到,就会继续到哈希表 2 里面进行找到。
String
- 多增加 len 表示当前字符串的长度:这样就可以直接获取长度了,复杂度 O(1);
- 自动扩展空间:当 SDS 需要对字符串进行修改时,首先借助于 len 和 alloc 检查空间是否满足修改所需的要求,如果空间不够的话,SDS 会自动扩展空间,避免了像 C 字符串操作中的溢出情况;
- 有效降低内存分配次数:C 字符串在涉及增加或者清除操作时会改变底层数组的大小造成重新分配,SDS 使用了 空间预分配 和 惰性空间释放 机制,简单理解就是每次在扩展时是成倍的多分配的,在缩容是也是先留着并不正式归还给 OS;
- 二进制安全:C 语言字符串只能保存 ascii 码,对于图片、音频等信息无法保存,SDS 是二进制安全的,写入什么读取就是什么,不做任何过滤和限制;
redis线程和IO多路复用
redis为什么选择单线程
- Redis 的大部分操作 都在内存中完成,并且采用了高效的数据结构,因此 Redis 瓶颈可能是机器的内存或者网络带宽,而并非 CPU,既然 CPU 不是瓶颈,那么自然就采用单线程的解决方案了;
- Redis 采用单线程模型可以 避免了多线程之间的竞争,省去了多线程切换带来的时间和性能上的开销,而且也不会导致死锁问题。
- Redis 采用了 I/O 多路复用机制 处理大量的客户端 Socket 请求,一旦有请求到达,就会交给 Redis 线程处理,这就实现了一个 Redis 线程处理多个 IO 流的效果。
IO 多路复用并不是开启一个新线程监听socket然后把任务给主线程
。I/O 多路复用(I/O Multiplexing)是一种技术,让一个线程(通常是主线程)可以同时监听多个 I/O 通道(如 socket),并在某个通道有事件(如数据可读或可写)时得到通知,然后处理这些事件。它并不是依赖“新线程”来监听,而是利用操作系统提供的机制(如 select、poll、epoll)在单线程内高效管理多个连接。
传统 I/O 多路复用(Redis 6.0 之前)
- 流程:
- 主线程用 epoll(或其他多路复用工具)监听所有客户端 socket。
- 当某个 socket 有数据可读时,epoll 通知主线程。
- 主线程读取数据、执行命令、返回结果,全程单线程完成。
- 特点:没有新线程,完全由主线程负责监听和处理。
Redis 6.0+ 的 I/O 多线程优化
- 流程:
- 主线程仍然用 I/O 多路复用(epoll)监听 socket,接受新连接。
- 主线程将 socket 分配给 I/O 线程。
- I/O 线程负责读取客户端数据,放入队列。
- 主线程从队列中取出命令,执行计算逻辑。
- 执行结果放回队列,I/O 线程发送给客户端。
- 特点:多了 I/O 线程来分担网络读写,但核心计算仍是主线程完成。
Redis 6.0 对于网络 I/O 采用多线程来处理。但是对于命令的执行,Redis 仍然使用单线程来处理,所以大家不要误解 Redis 有多线程同时执行命令。
redis事务
如果要保证 2 条命令的原子性的话,可以考虑用 lua 脚本;
redis 事务(使用 MULTI 和 EXEC )出错的情况不保证原子性;
redis持久化
redis 虽然是内存数据库,但也要能够处理重启、宕机或系统故障后恢复数据。
redis 有两种持久化方式:RDB 快照和 AOF 日志
RDB快照
RDB 快照就是将 某一时刻的键值对数据存储到磁盘 ,生成一个二进制文件(默认名为 dump.rdb)。
触发时机:
SAVE
命令手动触发:主线程直接生成 RDB 文件,会阻塞其他操作(不常用)BGSAVE
命令手动触发:fork 一个子进程生成 RDB 文件,主线程继续处理请求(常用)- 自动触发:
配置文件
中设置条件,底层其实是 BGSAVE
AOF日志
AOF 是通过 记录每条写命令(增删改)到日志文件(默认名为 appendonly.aof),在重启时重放这些命令来恢复数据。它记录的是操作过程,而不是数据快照。
同步策略(写磁盘的频率):
- appendfsync
always
:每条命令立即同步到磁盘,最安全但最慢。 - appendfsync
everysec
:每秒同步一次,性能和安全性平衡(默认)。 - appendfsync
no
:交给操作系统决定,性能最好但可能丢数据。
重写(rewrite):AOF 文件会不断变大,Redis 提供 BGREWRITEAOF 命令精简文件,只保留能重建当前状态的最小命令集。
对比
- AOF 文件占用空间大,因为要重现每条命令,所以恢复慢,优点就是即使丢失数据,丢失的也比较少
- RDB 占用空间小,恢复快,但可能丢失两次快照之间的修改