《Redis设计与实现》读书笔记
2022-10-12 15:19:28 0 举报AI智能生成
Redis
作者其他创作
大纲/内容
第1章 引言
第一部分 数据结构与对象
数据结构
第2章 简单动态字符串
2.1 SDS定义
2.2 SDS与C字符串的区别
获取字符串长度的时间复杂度为O(1)
C字符串获取字符串长度的时间复杂度是O(n)，SDS的是O(1)，
因为SDS定义结构有长度len属性，而C字符串需要重新计算。
因为SDS定义结构有长度len属性，而C字符串需要重新计算。
杜绝缓冲区溢出
C字符串存在内存溢出覆盖相邻区域内存的问题，SDS修改时会先检查空间大小是否满足需求，
如不够，则先进行空间扩展之后再执行。（空间扩展方案参考2.3）
如不够，则先进行空间扩展之后再执行。（空间扩展方案参考2.3）
减少修改字符串时带来的内存重分配次数
C字符串拼接操作时需要先扩展底层数组空间（否则“缓冲区溢出”）；
截断操作时要释放不再使用的空间（否则“内存泄露”）。
截断操作时要释放不再使用的空间（否则“内存泄露”）。
SDS内存分配
空间预分配
SDS进行字符串增长操作，程序会分配必要空间，
同时还分配额外的未使用空间，然后更新free属性值。
同时还分配额外的未使用空间，然后更新free属性值。
分配策略
若对SDS进行修改后，len<1MB，分配与len同样大小的未使用空间。
此时buf数组的实际长度为len+free+1byte（1为表示结束的空字符）
此时buf数组的实际长度为len+free+1byte（1为表示结束的空字符）
若对SDS进行修改后，len>=1MB，则分配1MB的未使用空间。
此时buf数组的实际长度为len+free(1M)+1byte。
此时buf数组的实际长度为len+free(1M)+1byte。
通过空间预分配，减少内存分配次数，将连续增长N次字符串由原来的必定N次重分配降低为最多N次。
当然，缺点是会有一定内存损耗，在当前成本下是可以接受的。
当然，缺点是会有一定内存损耗，在当前成本下是可以接受的。
惰性空间释放
SDS进行字符串缩短操作，程序不会立即使用内存分配来回收多出的空间，而是记录在free属性。
真正需要时，通过SDS提供的API释放。
比如什么具体场景？
redis的淘汰策略
二进制安全
C字符串不能包含空字符，导致只能存文本，不能存多媒体（图片、视频、音频、压缩文件等）类的二进制数据。
SDS依据len的属性值判断数组是否结束，所以buf内容可以是任何二进制数据。
仍在buf结尾加上'\0'，是为了方便调用C语言API对字符串进行处理，即兼容部分C字符串函数<string.h>。
仍在buf结尾加上'\0'，是为了方便调用C语言API对字符串进行处理，即兼容部分C字符串函数<string.h>。
2.3 SDS API
补充
在Redis中的应用
K-V键和值都可能是SDS
用作缓冲区，AOF持久化的缓冲区，以及客户端状态中的输入缓冲区
第3章 链表
3.1 链表和链表节点的实现
3.2 链表和链表节点的API
补充
在Redis中的应用
List
发布与订阅、慢查询、监视器
第4章 字典
4.1 字典的实现
字典(dict)
哈希表(dictht)
哈希表节点(dictEntry)
4.2 哈希算法
4.3 解决键冲突
4.4 rehash
4.5 渐进式hash
补充
在Redis中的应用
Redis数据库、Map
第5章 跳跃表
5.1 跳跃表的实现
补充
在Redis中的应用
zset
在集群节点中用作内部数据
第6章 整数集合
6.1 整数集合的实现
6.2 升级
6.3 升级的好处
6.4 降级
6.5 整数集合API
补充
在Redis中的应用
set
第7章压缩列表
7.1
补充
在Redis中的应用
List、Map
扩展
Redis HyperLogLog
HyperLogLog 是用来做基数统计的算法
什么是基数？
比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。
基数估计就是在误差可接受的范围内，快速计算基数。
基数估计就是在误差可接受的范围内，快速计算基数。
优点
在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定 的、并且是很小的。
每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。
缺点
只存储计算基数，不会存储元素本身。
命令
PFADD key element [element ...]
添加指定元素到 HyperLogLog 中。
PFCOUNT key [key ...]
返回给定 HyperLogLog 的基数估算值。
PFMERGE destkey sourcekey [sourcekey ...]
将多个 HyperLogLog 合并为一个 HyperLogLog。
Redis GEO
Redis GEO 主要用于存储地理位置信息，并对存储的信息进行操作，该功能在 Redis 3.2 版本新增。
命令
geoadd
添加地理位置的坐标。
geopos
获取地理位置的坐标。
geodist
计算两个位置之间的距离。
georadius
根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
georadiusbymember
根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合。
geohash
返回一个或多个位置对象的 geohash 值。
第8章 对象
8.1 对象的类型与编码
8.2 字符串对象
8.3 列表对象
8.4 哈希对象
8.5 集合对象
8.6 有序集合对象
8.7 类型检查与命令多态
8.8 内存回收
8.9 对象共享
8.10 对象的空转时长
第二部分 单机数据库的实现
第9章 数据库
服务器中的数据库
Redis服务器将所有数据库都保存在服务器状态redis.h/redisServer结构的db数组中，
db数组的每个项都是一个redis.h/redisDb结构，每个redisDb结构代表一个数据库。
db数组的每个项都是一个redis.h/redisDb结构，每个redisDb结构代表一个数据库。
struct redisServer {
// ...
//
一个数组，保存着服务器中的所有数据库
redisDb *db;
// ...
//服务器的数据库数量
int dbnum;
// ...
};
// ...
//
一个数组，保存着服务器中的所有数据库
redisDb *db;
// ...
//服务器的数据库数量
int dbnum;
// ...
};
初始化redis服务器时，根据dbnum决定创建多少个数据库。
dbnum默认值16
通过SELECT命令选择切换数据库。
生产中尽量避免使用这个命令，因为Redis没有提供查看当前数据库的功能，容易忘了当前是哪个数据库。
Redis客户端通过redisDb指针指向当前使用的数据库。
typedef struct redisClient {
// ...
//记录客户端当前正在使用的数据库
redisDb *db;
// ...
} redisClient;
数据库键空间
Redis是键值对数据库，所有的键值对都保存在redisDb的字典中，谓之“键空间”。
typedef struct redisDb {
// ...
//
数据库键空间，保存着数据库中的所有键值对
dict *dict;
// ...
} redisDb;
// ...
//
数据库键空间，保存着数据库中的所有键值对
dict *dict;
// ...
} redisDb;
键空间
键空间的键
即key，都是SDS字符串对象。
键空间的值
即value,可以是Redis的任意一种对象
Sting
List
Set
Zset
Map
命令
SET key value
新增、更新
DEL key
删除
FLUSHDB
清空数据库
慎用
RANDOMKEY
返回随机键
DBSIZE
返回数据库键数量
其他命令参考后述链接
键空间的读写维护操作
读一个键时，检查键是否过期，过期则删除。
读一个键后，根据读时命中与否，更新命中与不命中的次数。
INFO stats命令查看
keyspace_hits
命中次数
keyspace_misses
不命中次数
读一个键后，更新LRU（最后一次使用）时间，用于计算键闲置时间。
OBJECT idletime命令查看key闲置时间
修改一个键后，若该键被WATCH命令监视，将这个键标记为脏（dirty）。
让事务知道这个键已经被修改过。
让事务知道这个键已经被修改过。
修改一个键后，脏（dirty）计数器+1，这个计数器会触发服务器的持久化和复制操作。
若开启了数据库通知功能，修改键之后，服务器将按配置发送相应的数据库通知。
键生存或过期时间
设置键过期时间
EXPIRE
EXPIRE＜key＞＜ttl＞命令用于将键key的生存时间设置为ttl秒。
PEXPIRE
PEXPIRE＜key＞＜ttl＞命令用于将键key的生存时间设置为ttl毫秒。
EXPIREAT
EXPIREAT＜key＞＜timestamp＞命令用于将键key的过期时间设置为timestamp所指定的秒数时间戳。
PEXPIREAT
PEXPIREAT＜key＞＜timestamp＞命令用于将键key的过期时间设置为timestamp所指定的毫秒数时间戳。
EXPIRE、PEXPIRE和EXPIREAT三个命令都会转换成PEXPIREAT命令来执行。
SETEX
SETEX命令可以在设置一个字符串键的同时为键设置过期时间。只能用于字符串键。
保存过期时间
redisDb结构的expires字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典。
typedef struct redisDb {
// ...
//过期字典，保存着键的过期时间
dict *expires;
// ...
} redisDb;
移除过期时间
PERSIST
移除一个键的过期时间
数据结构上是移除了键关联的过期时间（expires）数据。
剩余生存时间
TTL
以秒为单位返回键的剩余生存时间
PTTL
PTTL命令则以毫秒为单位返回键的剩余生存时间
键的过期判定
检查给定键是否存在于过期字典：如果存在，那么取得键的过期时间。
检查当前UNIX时间戳是否大于键的过期时间：如果是的话，那么键已经过期；否则的话，键未过期。
过期删除策略
类型
定时删除
在设置键的过期时间的同时，创建一个定时器（timer，占用一个线程，睡眠过期时间），
让定时器在键的过期时间来临时，立即执行对键的删除操作。
让定时器在键的过期时间来临时，立即执行对键的删除操作。
优点
过期立即删除，实时性好。
缺点
CPU性能消耗大。每个定时器是一个任务线程。
惰性删除
放任键过期不管，但是每次从键空间中获取键时，
都检查取得的键是否过期，如果过期的话，就删除该键；
如果没有过期，就返回该键。
都检查取得的键是否过期，如果过期的话，就删除该键；
如果没有过期，就返回该键。
优点
CPU友好，不用浪费性能去删除非热点数据。
缺点
内存不友好，过期数据占用内存空间。
定期删除
每隔一段时间，程序就对数据库进行一次检查，删除里面的过期键。
至于要删除多少过期键，以及要检查多少个数据库，则由算法决定。
至于要删除多少过期键，以及要检查多少个数据库，则由算法决定。
优点
CPU友好，定期处理过期数据，不用频繁占用CPU。
缺点
实时性差。数据过期，还未被定期删除，但被读取的场景。
Redis过期删除策略（默认）
惰性删除和定期删除结合。
实现
惰性删除
由db.c/expireIfNeeded函数实现
定期删除
由redis.c/activeExpireCycle函数实现
AOF、RDB和复制对过期键的处理
RDB
生成
SAVE或BGSAVE命令是，过期键不会持久化。
载入
过期键在载入时会被忽略。
AOF
写入
重写
过期键在载入时会被忽略。
复制
主服务器在删除一个过期键之后，
通知从服务器删除这个过期键。
从服务器不会主动删除过期键。
通知从服务器删除这个过期键。
从服务器不会主动删除过期键。
内存淘汰机制
Redis通过设置maxmemory-policy参数定义内存使用达到阈值时的淘汰策略。
8种
noeviction
当内存不足以容纳新写入数据时，新写入操作会报错，读数据正常工作。
volatile-ttl
采用删除存活时间最短的键值对策略。
volatile-lru
最近最久未用淘汰策略
在所有有过期时间的 key 中使用 LRU 算法淘汰数据。
volatile-lfu
最近用次最少淘汰策略
在所有有过期时间的 key 中使用 LFU 算法淘汰数据。
volatile-random
在所有有过期时间的 key 中使用随机淘汰策略删除超时的键值对。
allkeys-lru
最近最久未用淘汰策略
在所有key（无论有没有过期时间） 中使用 LRU 算法淘汰数据。
allkeys-lfu
最近用次最少淘汰策略
在所有key（无论有没有过期时间）中使用 LFU 算法淘汰数据。
allkeys-random
在所有key（无论有没有过期时间）中使用随机淘汰策略删除所有的键值对。这个策略不常用。
第10章 RDB持久化
创建
命令
SAVE
SAVE命令会阻塞Redis服务器进程，
直到RDB文件创建完毕为止。
直到RDB文件创建完毕为止。
执行时服务器状态
Redis服务器会被阻塞，直到SAVE完成。
BGSAVE
BGSAVE命令会派生出一个子进程，
然后由子进程负责创建RDB文件，
服务器进程（父进程）继续处理命令请求。
然后由子进程负责创建RDB文件，
服务器进程（父进程）继续处理命令请求。
执行时服务器状态
SAVE命令会被服务器拒绝
BGSAVE命令会被服务器拒绝
BGREWRITEAOF
如果BGSAVE命令正在执行，
那么客户端发送的BGREWRITEAOF命令会被延迟到BGSAVE命令执行完毕之后执行。
那么客户端发送的BGREWRITEAOF命令会被延迟到BGSAVE命令执行完毕之后执行。
如果BGREWRITEAOF命令正在执行，
那么客户端发送的BGSAVE命令会被服务器拒绝。
那么客户端发送的BGSAVE命令会被服务器拒绝。
SAVE和BGSAVE底层调用rdb.c/rdbSave函数完成数据备份任务。
触发条件
触发RDB创建的方式和场景。
主动方式（3种）
SAVE命令触发
BGSAVE命令触发
设定规则触发
常见规则命令
SAVE 900 1
900秒内改变1条数据，自动生成RDB文件
SAVE 300 10
300秒内改变10条数据，自动生成RDB文件
SAVE 60 10000
60秒内改变1万条数据，自动生成RDB文件
注意
SAVE规则命令下，调用的是BGSAVE。
Redis允许用户通过设置服务器配置的save选项，
让服务器每隔一段时间自动执行一次BGSAVE命令。
让服务器每隔一段时间自动执行一次BGSAVE命令。
被动场景（3种）
全量复制
主从复制时，主会自动生成RDB文件。
debug reload
Redis中的debug reload提供debug级别的重启，
不清空内存的一种重启，这种方式也会触发RDB文件的生成。
不清空内存的一种重启，这种方式也会触发RDB文件的生成。
shut down
会触发RDB文件的生成。
载入
RDB文件的载入工作是在服务器启动时自动执行。
Redis并没有专门用于载入RDB文件的命令。
载入RDB文件的实际工作由rdb.c/rdbLoad函数完成。
载入RDB文件时，服务器处于阻塞状态。
若Redis开启了AOF，优先使用AOF。
RDB文件结构
二进制格式
特点
优点
数据载入快，适合大规模数据恢复。
缺点
因为不是实时同步，数据实时性不高。
第11章 AOF持久化
实现
三个步骤
命令追加（append）
需要配置文件redis.conf参数appendonly yes
表示开启AOF持久化
开启后redis会预留内存供缓存使用，默认大小1M
当AOF持久化功能处于打开状态时，
服务器在执行完一个写命令之后，
会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
服务器在执行完一个写命令之后，
会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
文件写入
Redis的服务器进程就是一个事件循环（loop），
这个循环中的文件事件负责接收客户端的命令请求，以及向客户端发送命令回复，
而时间事件则负责执行像serverCron函数这样需要定时运行的函数。
这个循环中的文件事件负责接收客户端的命令请求，以及向客户端发送命令回复，
而时间事件则负责执行像serverCron函数这样需要定时运行的函数。
在服务器每次结束一个事件循环之前，
它都会调用flushAppendOnlyFile函数，
考虑是否需要将aof_buf缓冲区中的内容写入和保存到AOF文件里面。
它都会调用flushAppendOnlyFile函数，
考虑是否需要将aof_buf缓冲区中的内容写入和保存到AOF文件里面。
文件同步（sync）
同步策略
参数配置appendfsync
always
每次修改数据立即同步到AOF文件。
实时性高，安全，但是效率较低。
实时性高，安全，但是效率较低。
追求安全
everysec
每秒同步一次，效率高，有1秒的数据偏差。（默认配置）
no
缓冲区满了才同步。效率高，数据安全度最低。
追求效率
AOF文件实现由主线程完成。
载入
步骤
1.创建不联网伪客户端（fake client）。
2.伪客户端逐条读取并执行AOF文件中命令直到结束。
重写
AOF不断保存被执行的命令，存在体积膨胀的问题。需要重写（rewrite）来优化体积。
命令
BGREWRITEAOF
原理
重写生成新AOF文件代替旧AOF文件。
问题
重写期间Redis继续新执行的命令如何同步。
解决方案
双缓冲区设计
重写期间，另预留一份重写缓冲区。
新命令除了追加到AOF缓冲区，还会追加到AOF重写缓冲区。
新命令除了追加到AOF缓冲区，还会追加到AOF重写缓冲区。
重写完成后，将AOF重写缓冲区命令同步到新AOF文件。
执行完AOF重写缓冲区命令后，修改新AOF文件名覆盖旧AOF文件
覆盖操作是原子操作，避免覆盖过程中新执行命令导致不一致。
即这个过程，主线程阻塞，暂停执行新命令。
即这个过程，主线程阻塞，暂停执行新命令。
配置
auto-rewrite-min-size 64M
AOF文件超过64M开始第一次重写
生产环境建议这个值设置为5G，减少重写次数。
auto-aof-rewrite-percentage 100
第一次重写之后，每次体积较前一次体积加倍之后再开始重写。
AOF文件重写由子线程执行。
特点
优点
对比RDB，数据实时性更高。
缺点
载入需要执行全部命令，命令很多时，耗时长，效率低，且容易出BUG。
Redis建议持久化方案
生产环境建议RDB和AOF并行。RDB做灾备。
Redis持久化文件加载顺序
1.开启AOF，
且存在AOF文件，则Redis加载AOF文件。
但不存在AOF文件，Redis直接启动，不会考虑RDB。
且存在AOF文件，则Redis加载AOF文件。
但不存在AOF文件，Redis直接启动，不会考虑RDB。
2.未开启AOF，存在RDB则加载RDB，否则直接启动。
第12章 事件
文件事件
File Event
File Event
Redis 主进程中，主要处理客户端的连接请求与相应。
时间事件
Time Event
Time Event
fork 出的子进程中，处理如 AOF 持久化等定时操纵类任务。
分类
定时事件
指定时间触发一次指定程序。
周期事件
周期性执行执行程序。
例如AOF每秒同步一次。
第13章 客户端
第14章 服务器
第三部分 多机数据库的实现
第15章 复制
子主题
第16章 Sentinel
参考资料
Raft协议实战之Redis Sentinel的选举Leader源码解析
第17章 集群
第四部分 独立功能的实现
第18章 发布与订阅
补充
Redis Stream
Redis Stream 是 Redis 5.0 版本新增加的数据结构。
Redis 发布订阅 (pub/sub)功能的缺点是消息无法持久化。
Redis Stream 提供了消息的持久化和主备复制功能，可以让任何客户端访问任何时刻的数据，
并且能记住每一个客户端的访问位置，还能保证消息不丢失。
并且能记住每一个客户端的访问位置，还能保证消息不丢失。
第19章 事务
Redis通过MULTI、EXEC、WATCH等命令实现事务功能。
将多个命令打包，一次性、序列化的执行完毕。
事务执行过程中不会被中断。
事务执行过程中不会被中断。
例
特点
一次性
顺序性
排他性
不保证原子性
事务中有命令执行失败，不会回滚。
Redis的架构理念是简洁，事务回滚会导致复杂性，官方不支持，也没必要。
三个阶段
开始事务
MULTI
Redis遇到MULTI命令时开启事务状态。
命令入队
开始事务之后，Redis会将后续命令缓存进事务队列。
返回QUEUED表示命令加入队列成功。
返回QUEUED表示命令加入队列成功。
事务队列
每个Redis客户端都有自己的事务状态multiState
队列命令执行顺序FIFO（先入先出）
事务状态
包含一个事务队列，以及一个已入队命令计数器multiCmd
事务执行
EXEC
Redis在事务状态遇到EXEC命令后执行事务队列的命令，返回结果。
事务ACID性质
原子性（Atomicity）
不支持
一致性（Consistency）
支持
隔离性（Isolation
支持
持久性（Durability）
特定情况下支持
appendfsync选项的值为always时，事务也具有持久性。
命令
WATCH
格式 WATCH key value
WATCH "name" “Lily”
WATCH命令是乐观锁，不允许监控的value值被修改。
事务中若修改被WATCH的值，则会导致事务执行失败。
事务中若修改被WATCH的值，则会导致事务执行失败。
MULTI
开始事务
EXEC
执行事务
若事务队列有命令存在编译错误（语法错误），EXEC时，所有命令都不会执行。
若事务队列存在运行时异常，EXEC执行时，运行时异常会跑出错误信息，但其他命令继续执行。
DISCARD
放弃事务
UNWATCH
取消WATCH对所有key的监控
第20章 Lua脚本
第21章 排序
第22章 二进制位数组
第23章 慢查询日志
第24章 监视器
0 条评论
下一页
