Redis 学习笔记（基础）[WIP]

1. 基本架构

一个键值数据库需要有哪些功能/结构/特性。

支持多种数据结构
PUT、GET、DELETE、SCAN
设置过期
索引结构
对外接口，Socket、动态链接库等等
存储方式，内存、硬盘（持久化）
高可用
横向扩展
功能可扩展性

2. 数据结构

Redis 接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。

Redis 的值有如下数据类型：

String（字符串）
List（列表）
Hash（哈希）
Set（集合）
Sorted Set（有序集合）

数据类型	数据结构
String	简单动态字符串
List	双向链表/压缩列表
Hash	压缩列表/哈希表
Set	整数数组/哈希表
Sorted Set	压缩列表/跳表

Redis 使用一个全局的哈希表来保存所有键值对，可以在 $O(1)$ 的时间内查找到键值对。

一个哈希表就是一个数组，数组元素为哈希桶，每个哈希桶存放一个链表，连接着哈希值映射到该桶中的多个键值对。

｜0｜1｜2｜3｜4｜5｜
    |       |
    |       ---> entry4
    |
    ---> entry1 ---> entry2 ---> entry3

哈希冲突及rehash

当哈希冲突过多时，链表过长，导致查找效率下降，Redis会对哈希表进行rehash。

为了 使 rehash 更高效，Redis 使用了两个全局哈希表：哈希表 1 和哈希表 2 。默认情况下使用哈希表 1 ，哈希表 2 没有分配空间，当键值对增多时，Redis开始进行rehash：

给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
释放哈希表 1 的空间。

然后使用哈希表 2 保存数据，下次rehash再使用哈希表 1 。

为 避免一次性拷贝大量数据造成 Redis 线程阻塞，Redis采用了渐进式rehash。

渐进式rehash

Redis可以保持处理用户请求，每处理一个请求，就顺带将哈希表 1 中的一个桶的所有entries拷贝到哈希表 2 中。这样就能把一次性大量拷贝的开销，分摊到了多次请求中，避免了耗时可能造成的阻塞。

数据结构的操作效率

整数数组 和 双向链表 都是顺序读写，操作复杂度都是 $O(N)$。

压缩列表

压缩列表表头有 列表长度（zlbytes）、列表尾偏移量（zltail）、列表中entry个数（zllen） 三个字段，表尾有一个 zlend 字段表示 列表结束。

1	\| zlbytes \| zltail \| zllen \| entry1 \| entry2 \| ... \| entryN \| zlend \|

查找表头、表尾元素的复杂度为 $O(1)$，查找其他元素的复杂度为 $O(N)$。

跳表

跳表是在 有序链表 的基础上增加了多级索引，通过索引位置的几次跳转，实现数据快速定位。

1 ----------------------> 27 -----------------------> 100 // 二级索引
↓                         ↓                           ↓
1 --------> 11 ---------> 27 ---------> 50 ---------> 100 // 一级索引
↓           ↓             ↓             ↓             ↓
1 --> 5 --> 11 --> 20 --> 27 --> 33 --> 50 --> 62 --> 100 --> 156 // 链表

跳表的查找复杂度为 $O(logN)$。

时间复杂度

数据结构的时间复杂度

数据结构	时间复杂度
哈希表	$O(1)$
跳表	$O(logN)$
双向链表	$O(N)$
压缩列表	$O(N)$
整数数组	$O(N)$

不同操作的时间复杂度

单元数操作是基础。每一种集合类型对单个数据实现的增删改查操作，复杂度由数据结构决定。
范围操作很耗时。返回一个范围内的数据，复杂度一般是 $O(N)$，应尽量避免，可以使用 2.8 版本之后的 HSCAN、SSCAN、ZSCAN 等命令进行渐进式遍历。
统计操作通常高效。集合类型对集合中的元素个数由记录，例如 LLEN、SCARD。
例外情况只有几个。压缩列表和双向列表的会记录表头和表尾的偏移量，对它们的操作复杂度只有 $O(1)$，例如 LPOP、RPOP、LPUSH、RPUSH。

问题

整数数组和压缩列表在查找时间复杂度方面并没有很大优势，为什么Redis还会把它作为底层数据结构？

主要有两方面原因：

内存利用率。Redis 是内存数据库，大量数据存储在内存中，整数数组和压缩列表结构比较紧凑，相比链表结构占用内存更少，可以提高内存利用率。
数组对CPU高速缓存支持更友好。集合元素较少时，使用内存紧凑的排列方式，可以利用CPU高速缓存，尤其在一个缓存行内（64字节）有更高效的访问效率。当元素数量超过阈值后，为避免复杂度太高，可以转为哈希表和跳表。

3. 高性能 IO 模型

Redis 的网络 IO 和键值对读写是由单个线程完成的；其他功能，例如持久化、异步删除、集群数据同步，是由额外的线程执行的。

Redis使用 IO多路复用，即一个线程处理多个 IO 流。

可能存在的瓶颈（来自Kaito）：

单个请求耗时会导致后续所有请求阻塞等待，包括以下几种：
- 操作bigkey，分配、释放内存（4.0推出了lazy-free，可以异步执行bigkey释放）
- 使用复杂度较高的命令，排序、union、查询全量数据
- 大量key集中过期
- 淘汰策略，内存超过Redis内存上线，每次写入都要淘汰一些key，导致耗时变长
- AOF 开启 always
- 主从同步生成 RDB 时的 fork
并发量大时，单线程处理客户端请求，无法利用多核（6.0推出了多线程，可利用多核CPU处理用户请求）

4. AOF（Append Only File）

Redis 的 AOF 是写后日志，先执行命令，把数据写入内存，然后再记录日志。

不会阻塞当前写操作，执行完命令还没来得及记日志就宕机的话，会有数据丢失的风险。

*3 --> 这个命令有三个部分
$3 --> 第一部分的长度
set --> 第一部分的内容
$5
hello
$5
world

三种写回策略

Always，同步写回，每个命令执行完立马写回磁盘
EverySec，每秒写回，写到AOF内存缓存，每秒写回一次
No，写到AOF内存缓存，由操作系统决定何时将其写回

日志重写

当日志文件过大时，可以对日志进行重写。可以把某些多条修改同一个键值对的命令合并为一条。

重写流程：

主线程 fork 出 bgrewriteaof 子进程，主线程在将新指令写入 AOF 缓存时，还会写入 AOF 重写缓存；
子进程将 fork 拷贝出来的内存快照写成命令日志；
写完后将AOF重写缓存中的日志写到这个新的日志中，然后就可以用这个新日志替换旧日志了。

其他要点

fork 使用的是操作系统的写时复制（Copy On Write）机制，并不会直接拷贝所有内存。但是会拷贝父进程的的内存页表，如果页表较大，可能导致阻塞。
主进程在提供服务时，如果操作的是bigkey，写时复制会导致内存分配；如果开启了内存大页（huge page）机制，内存分配会产生阻塞。（所以使用Redis通常要关闭内存大页，其对使用 fork 的程序不友好）
AOF 重写可以使用 bgrewriteaof 命令手动执行，也由两个配置项控制自动触发：
- auto-aof-rewrite-min-size：表示运行AOF重写的最小大小，默认为 64MB；
- auto-aof-rewrite-percentage：当前AOF文件大小和上一次重写后AOF文件大小的差值，除以上一次重写AOF文件大小，即增量和上一次全量的比值，默认为 100。
  AOF 文件大小同时满足这两个配置项，会自动触发 AOF 重写。

5. 内存快照 RDB

把某一时刻的内存数据以文件的形式写到磁盘上，即快照。这个快照文件即 RDB 文件（Redis DataBase 的缩写）。

在数据恢复时，可直接把 RDB 文件读入内存，很快完成恢复。

Redis 执行的是全量快照。

可以使用 save、bgsave 来生成 RDB 文件；save在主线程中执行，会阻塞；bgsave 会创建子进程专门进行 RDB 文件写入，不会阻塞。

快照进行时数据如何修改

使用 fork 创建子进程，该子进程会跟主线程共享所有内存数据；利用操作系统的写时复制技术，当主进程修改数据时，会重新分配空间生成该数据的副本，并使用该副本提供服务，bgsave 子进程仍然使用未修改的数据进行快照写入。

快照频率

频繁执行全量快照有两方面开销：

给磁盘带来压力
fork 本身可能阻塞主线程，如果频繁 fork 会导致主线程阻塞所以，如果有一个 bgsave 在运行，就不会启动第二个了

4.0 中提出了混合使用AOF和RDB的方法，即快照以一定的频率执行，在快照间以AOF的形式记录这期间的命令。实现：

避免了频繁 fork 对主线程的影响
减少了 AOF 文件大小，提高了数据恢复效率

在配置文件中设置：

1	aof-use-rdb-preamble yes

三点建议

数据不能丢失时，使用 AOF 和 RDB 混合方案
允许分钟级别的数据丢失，使用 RDB
只用 AOF 的话，优先使用 everysec，在可靠性和性能之间比较平衡

课后题：资源风险（Kaito）

考虑 fork 导致多大程度的写时复制，是否会造成 OOM，或者 swap 到磁盘上导致性能降低；
CPU 核数较少时，Redis的其他子进程会跟主线程竞争CPU，导致性能下降；
如果 Redis 进程绑定了 CPU，子进程会继承它的 CPU 亲和属性，与父进程争夺同一个 CPU 资源，导致效率下降。所以如果开启RDB和AOF，一定不要绑定CPU。

6. 主从同步

可靠性分两方面：

数据少丢失（由RDB、AOF保证）；
服务少中断（通过增加副本冗余量保证）

读写分离：主库、从库都可以执行读操作，主库限制性写操作，然后同步给从库。

如果都允许写，会造成各实例副本不一致，需要涉及加锁、协商等各种操作，产生巨额开销。

主从第一次同步

在从库实例上执行：

1	replicaof [主库ip] [主库port]

三个阶段

主从建立链接、协商同步，从库给主库发送 psync 命令，表示要进行数据同步，主库根据这个命令的参数来启动复制。psync 命令包含了主库的 runID 和复制进度 offset 两个参数。主库收到 psync 命令后，用 FULLRESYNC 响应命令带上两个参数，主库的 runID 和主库目前的复制进度 offset 给从库，从库会记住这两个参数。

runID：每个 Redis 实例启动时自动生成的一个随机 ID，唯一标识一个实例。第一次复制时从库不知道主库的 runID，使用 ?；
offset：第一次复制设置为 -1。

主库执行 bgsave 生成 RDB 文件，并发送给从库。从库收到 RDB 文件后，清空数据库并加载 RDB 文件。此时主库不会停止服务，但在内存中会有专门的 replication buffer，记录 RDB 文件生成后收到的所有写操作。
主库把 replication buffer 中的修改操作发送给从库执行。

主从级联

使用“主-从-从”模式分担主库压力。二级从库可以选择一个内存较高的从库进行同步。

主从间使用基于长连接的命令传播。

网络断开

2.8 前网络闪断会造成重新全量复制，2.8 后可以增量复制，实现继续同步。

（Kaito）主库除了将所有写命令传给从库之外，也会在 repl_backlog_buffer 中记录一份。当从库断线重连后，会发送 psync $master_runid $offset，主库就能通过 $offset 在 repl_backlog_buffer 中找到从库断开的位置，只发送 $offset 之后的增量给从库。

repl_backlog_buffer：为了解决从库断开后找到主从差异而设计的环形缓冲区。配置大一点，可以减少全量同步的频率。

replication buffer：客户端、从库与 Redis 通信时，Redis 都会分配一个内存 buffer 用于交互，把数据写进去并通过 socket 发送到对端。当对端为从库时，该 buffer 只负责传播写命令，通常叫做 replication buffer。这个 buffer 由 client-output-buffer-limit 参数控制，如果过小或者从库处理过慢，Redis 会强制断开这个链接。

耿腾的博客