Redis

int len

int free

char buf[]

C

SDS

C

SDS

C

SDS

C

SDS

SDS API二进制安全但是仍然遵守C字符串以空字符串结尾的管理, 这样可以兼容部分C字符串函数

双端 prev next指针可以O(1)获取前置和后置结点

无环  head.prev = NULL tail.next = NULL

O(1)获取头尾结点

O(1) 通过len属性获取链表结点个数

多态 void\*保存结点值, 包括dup clear match函数的比较值都是void*  可以保存不同类型的值

struct ListNode *prev

struct ListNode *next

void *value

链表属性

链表结点函数

哈希表结点(dictEntry)

哈希表 (dictht)

字典(dict)

执行扩展操作的条件

收缩操作的必要条件

为字典的ht[1]哈希表分配空间, 分配的空间取决与执行的操作和ht[0].used的大小

将保存在ht[0]中的键值对rehash到ht[1]上

ht[0]所有的键值对迁移到ht[1]上以后释放ht[0] 将ht[1]置为ht[0], 并在ht[1]的位置上创建一个空白的哈希表

rehash的操作不是一次性集中式的完成, 而是分多次渐进式的完成的

为什么分多次渐进式的进行rehash

渐进式rehash的步骤

渐进式rehash期间的哈希表操作

struct zskiplistLevel level[]

后退指针(backward)

分值(score)

成员对象(obj)

head  tail

level

length

encoding

length

contents[]

当添加的新元素类型比整数集合所有元素的类型都要长时, 整数集合需要先升级, 才能将新元素添加到整数集合

升级步骤

升级的好处

记录压缩列表占用的内存字节数

记录压缩列表尾结点距离压缩列表的起始地址有多少字节, 可以通过这个偏移量直接访问尾结点

压缩列表包含的结点数量

压缩列表包含的各个结点

特殊值 0xFF(255) 标记压缩列表的末端

以字节为单位, 记录前一个结点的长度, 属性的长度可以是1 || 5 个字节

- 前一个结点的长度<254bytes  previous_entry_length属性长度是1字节, 前一个结点长度就保存在这个属性中
- 前一个结点的长度>=254bytes  previous_entry_length属性长度是5字节, 属性的第一字节被设置为0xFE(254), 而之后的四个字节保存前一个结点的长度

可以通过指针运算, 根据当前结点的起始地址计算前一个结点的起始地址

记录了结点的content属性所保存数据的类型和长度

保存结点的值, 结点值可以是一个字节数组, 或者整数, 类型和长度由encoding决定

抢购, 秒杀, 详情页, 点赞, 评论, 通过这个操作, 实现

- key:用户 value:代表365天的bit
- 365位bit表示这个人第几天登录
- 通过 bitcount 统计某个窗口的1就是登录的天数

- key: 时间日期 value:每个位代表一个用户, 为1就是这一天这个bit对应的用户登录
- 连续登录连续日期 & 统计1的数量就是连续登录的人数

type属性记录了对象的类型

type <数据库键>:

记录了对象所使用的编码, 也就是对象使用了什么数据结构作为对象的底层实现

每种类型的对象都使用了至少两种不同的编码

对象的ptr指针指向底层实现数据结构, 数据结构由对象的encoding属性决定

字符串对象保存的是整数值, 并且这个整数值可以用long类型来表示

保存字符串, 长度<=32字节

embstr编码通过调用一次内存分配一块连续的空间 依次包含redisObject和sdshdr两个结构

使用SDS来保存这个字符串值 长度>32字节

raw调用两次内存分配分别创建redisObject 和 sdshdr结构

使这个对象从保存整数值变成保存字符串值

embstr编码的字符串没有任何修改程序, 实际上是只读的

对这个对象修改的时候转换成raw(append)

ziplist编码的列表对象底层实现为压缩列表, 每个压缩列表结点保存一个列表元素,

-  linkedlist编码的列表对象底层实现为双端链表
-  每个双端链表结点保存了一个字符串对象, 字符串对象保存了一个列表元素

- 列表对象保存的所有字符串元素的长度都小于64字节
- 列表对象保存的元素数量小于512

ziplist编码的哈希对象底层使用压缩列表

- 新的键值对加入哈希对象, 先将保存了键的压缩列表结点推入压缩列表结尾
- 再将保存了值的压缩列表结点推入压缩列表结尾

hashtable编码的哈希对象使用字典作为底层实现, 哈希对象的每个键值对都由一个字典键值对来保存

- 字典的每个键都是一个字符串对象, 对象保存了键值对的键
- 字典的每个值都是一个字符串对象, 对象保存了键值对的值

- 哈希对象保存的所有键值对的键和值的字符串长度都<64字节
- 哈希对象保存的所有键值对的数量<512

使用整数集合作为底层实现,

使用字典作为底层实现, 
字典的每个键都是一个字符串对象, 
每个字符串对象包含一个集合元素, 
字典的值全部设为NULL

- 集合对象所有元素都是整数值
- 元素个数<=512

使用压缩列表作为底层实现

skiplist

- 有序集合元素数量<128
- 保存元素的成员长度都<64字节

被恶意攻击, 故意请求不存在key

接口层校验(如用户鉴权, id基础校验, id<=0拦截)

数据库缓存都没有的key的值设置成key-null键值对放入缓存,设置较短的过期时间 这样对这一个key的请求直接在缓存找到null返回, 防止对一个key的暴力攻击

布隆过滤器, 一定不存在的key被bitmap过滤掉, 避免了对DB的查询压力

分布式锁

一个热点key过期

之前没有被访问过, 也就没有被放入到缓存, 但是突然有大量并发的请求

设置热点key永远不过期

分布式锁

热点key大面积过期

设置热点key过期时间随机, 防止同一时间大量数据过期

缓存预热

分布式锁

- setnx 不存在设置 对应的是新建
- setxx 存在设置 对应的是更新
EX seconds: 设定过期时间，单位为秒
PX milliseconds: 设定过期时间，单位为毫秒
NX: 仅当key不存在时设置值
XX: 仅当key存在时设置值

setnx + setex

set (key,value, nx, px)

redlock

过期字典的键是一个指针, 指向了键空间的某个键对象

过期字典的值是一个long long类型的整数, 保存了键所指向的数据库键对象的过期时间
一个毫秒精度的UNIX时间戳

当客户端执行PEXPIREAT命令, 为一个数据库键设置过期时间, 服务器会在数据库的过期字典中关联给定的数据库键和过期时间

对有过期时间的key设置定时器, 到过期时间立即清除,
对内存友好, 但是占用大量CPU资源处理过期的数据, 影响缓存的响应时间和吞吐量

访问带有过期时间的key才会判断key是否过期, 过期则清除
节省CPU资源, 但是过期key占用大量内存, 极端情况, 过期key没有被再次访问, 不会被清除, 一直占据内存

每隔一定时间, 扫描一定数量的数据库的expire字典中一定数量的key(随机), 清除已经过期的
可以调整定时扫描的时间间隔和每次扫描的时间限制, 使得CPU和内存消耗平衡

复制AOF文件的时候会忽略过期键

但是Slaves连接到master时, Slaves不会独立删除过期key, 只有等到master传来删除过期key的指令才会删除

高并发场景, 一个线程删除了缓存, 还没来得及写数据库, 第二个线程读取了数据, 发现缓存不存在, 进入数据库读到了旧的数据, 读完将旧数据回写到redis, 但是这时第一个线程已经将新的值写到缓存, 新值被读到的旧值覆盖了, 缓存中存在脏数据

先将缓存修改为特殊值(-999),客户端读缓存发现是默认值, 休眠, 再次查Redis, 但是特殊值对业务有侵入, 休眠时间可能多次重复, 对性能有影响

延时双删, 先删除缓存, 再写数据库, 休眠一会再次删除缓存, 但是如果写操作很频繁, 同样会造成脏数据

数据库写完了, 删除缓存失败, 数据仍然不一致

给缓存设置过期时间, 过期时间内, 缓存数据不更新

将热点数据设置为永不过期, 但是在value中写入一个逻辑上的过期时间,另起一个后台线程,扫描这些key, 对于逻辑上过期的缓存, 进行更新

save(阻塞)

bgsave(非阻塞)

save m n

主从同步

整个redis数据库只包含一个文件dump.rdb, 方便持久化

容灾性好, 方便备份, RDB是紧凑单一的文件, 方便传输到远端的数据中心, 适合灾难恢复

通过父进程fork子进程+COW的方式由子进程完成保存快照的工作, 父进程不需要其他IO操作, 所以IO最大化

恢复大数据集时, 比AOF更快

redis宕机, 损失的可能是很长时间段的数据, 因为设置save m n 条件出发才会保存, 

数据集较大时, fork也会耗时很久, 不能响应客户端请求, AOF也需要fork, 但是可以通过重写日志文件的频率提高数据集的耐久度

AOF 持久化功能打开, 服务器执行完一个写命令, 会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区末尾

Redis服务器进程是一个事件循环, 循环中的文件事件负责接收客服端命令请求, 已经向客服端发生回复
时间事件负责执行向serverCron函数这样的定时运行函数
服务器每次结束一个事件循环前, 会调用flushAppendOnlyFile函数, 考虑是否需要将aof_buf缓冲区的内容写入和保存到AOF文件里面

appendfsync

创建新的AOF文件

遍历数据库

Redis将AOF重写程序放到子进程进行

子进程AOF重写, 父进程继续接受客户端请求可能会对服务器状态修改, 使得服务器当前状态和AOF重写后文件保存的数据库状态不同

AOF重写缓冲区

整个AOF后台重写过程, 只有信号处理阶段会阻塞服务器, 其他时候都不会阻塞父进程

子进程把内存的数据以RDB的形式追加到AOF文件的头部, 重写时间点后的指令依然追加日志

重写后依然追加日志,但是回复的时候先RDB恢复(RDB恢复更快), 再增量回复日志, 性能更好

1. 创建一个不带网络连接的伪客户端, 因为redis 命令只能在客户端上下文执行
2. 从AOF文件中分析并读取一条写命令
3. 伪客户端执行读出的写命令
4. 直到所有AOF文件中的写命令处理完

数据更好的备份, 不同的fsync(always, everysec, no) 策略达到不同的数据一致性, 后台线程进行同步, 主线程仍然处理客户端请求,

AOF是只进行日志追加的日志文件, 未执行完整的写入命令可以通过redis-check-aof工具修复

AOF文件体积过大时可以重写AOF文件, 缩小占用空间, 并且重写阶段客户端的新的请求, 可以写入aof_rewrite_buf, 最后追加进新的AOF文件, 最大程度保证数据的一致性

AOF是以协议格式保存, 更容易分析, 如果不小心进行flushall, 只要AOF没有重写, 可以导出AOF文件移除末尾的FlushAll, 回复FlushAll之前的状态

相同的数据集, AOF文件通常大于RDB文件的体积, 启动恢复过程较慢

根据是以的fsync策略, AOF速度慢于RDB

负责监控 redis master 和 slave 进程是否正常工作。

如果某个 redis 实例有故障，那么哨兵负责发送消息作为报警通知给管理员。

如果 master node 挂掉了，会自动转移到 slave node 上。

如果故障转移发生了，通知 client 客户端新的 master 地址。

Sentinel本质是特殊模式下的Redis服务器, 需要先初始化Redis服务器
功能不同, 初始化过程不同, 不需要使用数据库 无需载入RDB AOF文件

初始化一个sentinel.c/sentinelState结构 保存服务器中所有和Sentinel功能相关的状态

masters字典记录所有被Sentinel监视的主服务器的相关信息

每个被Sentinel监视的主服务器, Sentinel会创建两个连向主服务器的异步网络连接

默认十秒一次频率的向被监视的主服务器发送INFO命令, 获取主服务器信息

Sentinel发现主服务器有新的从服务器后, 除了创建相应的实例结构外, 还会创建连接到从服务器的命令连接和订阅连接

创建连接后 会以十秒一次的频率通过命令连接向从服务器发送INFO命令

默认 Sentinel以两秒一次的频率 通过命令连接向所有被监视的主从服务器放以下格式的命令

每个与Sentinel连接的服务器, Sentinel既通过命令连接向服务器的  _sentinel_ : hello频道发送信息, 又通过订阅连接从服务器的 _sentinel_ : hello频道接受信息

对于监视同一个服务器的多个Sentinel, 一个Sentinel发送的信息会被其他Sentinel接收到, 这些信息会被用于更新其他Sentinel对发送信息Sentinel的认知, 也会用于更新其他Sentinel对被监视服务器的认知

更新Sentinels字典

创建连向其他Sentinel的命令连接

默认 Sentinel会以每秒一次的频率向所有与他创建了命令连接的实例(主从服务器, Sentinel) 发送PING命令, 
通过实例返回的PING命令回复判断实例是否在线

如果一个实例在down_after_milliseconds毫秒内持续向Sentinel返回无效回复, 
Sentinel修改这个实例的flags属性, 打开SRI_S_DOWN标识, 标识实例进入主观下线

当Sentinel判断主服务为主观下线后, 为了确认这个主服务器是否真的下线, 
他会向同样监视这个主服务器的其他Sentinel询问, 看他们是否也认为这个主服务器下线了, 
当Sentinel接收到足够数量的已下线判断之后, Sentinel就会将从服务器判定为客观下线, 并对主服务器执行故障转移操作

当一个主服务器被判断为客观下线, 
监视这个主服务器的各个Sentinel会进行协商, 选举一个领头Sentinel, 
并由领头Sentinel对下线主服务器进行故障转移
基于raft算法

选出新的主服务器

让下线服务器的从服务器复制新的主服务器 SLAVEOF <newMaster_ip> <newMaster_port>

下线主服务器设置为新的主服务器的从服务器

将从服务器状态更新至和主服务器一致

主服务器状态被修改, 让主从服务器数据库状态回到一致

复制偏移量

复制积压缓冲区

服务器运行ID

+FULLRESYNC <runid> <offset> 表示执行完整重同步

+CONTINUE 表示执行部分重同步

-ERR

clusterNode

clusterState

CLUSTER ADDSLOTS [i,i+1,...,j] 将槽[i:j]指派给当前结点

clusterNode结构的slots 属性 和 numslot属性记录了结点负责处理哪些槽

slots属性是一个二进制位数组, 长度为 16384/8个字节, 包含16384个二进制位

槽从0~16383编号, 根据索引i上的二进制位是否为1判断结点是否处理槽i

每个结点会将自己的slots数组通过消息发送给集群中的其他节点

每个接收到slots数组的结点都会将数组保存到发送这个slots数组信息的对应结点的clusterState.nodes.clusterNode结构里

以集群中的每个结点都会知道数据库中的16384个槽分别被指派给了集群中的哪个结点

clusterState结构的slots数组记录了集群所有16384个槽的指派信息

clusterState.slots解决了clusterNode.slots无法法高效解决的问题

clusterNode.slots仍然是必要的

clusterNode.slots数组记录了clusterNode结构所代表的结点的槽指派信息
clusterState.slots数组记录了集群所有槽的指派信息

遍历所有的输入槽, 检查是否已经被指派(clusterState.slots[i]==NULL), 如果已经被指派则返回错误

再次遍历所有的输入槽,

执行完毕通过消息告诉集群中其他节点自己负责处理哪些槽, 让其他节点直到槽指派的更新

指派给自己, 就执行这个命令

没有指派给自己, 返回一个MOVED错误, 指引客户端转向至正确的结点, 并再次发送想要执行的命令

CRC16(key) & 16384, CRC计算key的校验和, &16384 计算一个介于0~16384的槽号

clusterState.slots[i] = clusterNode.myself 槽i由当前结点负责可以执行命令

clusterState.slots[i] != clusterNode.myself 不由当前结点负责,

结点发现键所在的槽不是由自己负责处理会返回一个MOVED错误
并通过键找到负责处理槽的结点的IP+PORT返回给用户, 指引客户端转向负责槽的结点

一个集群客户端通常与多个集群结点建立套接字连接, 结点转向实际上就是换一个套接字发送命令
如果客户端与想要转向的结点没有建立连接, 回显根据MOVED错误提供的ip port连接节点再转向

结点只能使用0号数据库, 单机数据库没有限制
结点会用clusterState结构中的slots_to_keys跳跃表保存槽和键之间的关系

scores: 槽号, member:键值

CLUSTER SETSLOT <slot> IMPORTING <source_id>

CLUSTER SETSLOT <slot> MIGRATING <target_id>

是, 将这些键迁移到目标结点

ASKING命令需要做的就是打开发送该命令的客户端的REDIS_ASKING 标识

针对访问了数据原本属于的结点, 但是已经迁移到新结点了, 打开这个标识访问正在被导入数据的结点, 只有带了这个标识, 新节点才会返回正在被带入的数据

客户端向节点发送一个关于槽i的命令,

(已经完成迁移)MOVED错误代表槽的负责权以及从一个结点转移到另一个结点了,

(正在迁移)ASK错误代表两个结点在迁移槽的时候使用的临时措施

CLUSTER REPLICATE <node_id>

clusterState.nodes字典中找到node_id对应的ClusterNode结构

将自己的clusterState.myself.slaveof 指针指向这个结构,

修改自己在clusterState.myself.flags中的属性, 打开REDIS_NODE_SLAVE标识 表示变为从节点

SLAVEOF <master_ip> <master_port> 对主节点进行复制

结点成为从节点 复制 主节点 这个信息变成消息发送给集群其他节点

集群中的所有结点都会在代表主节点clusterNode结构的slaves属性和numslaves属性记录正在复制这个主节点的从节点名单

集群每个结点都会定期向集群其他节点发送PING消息, 检测对方是否在线

接受PING消息的结点B没有在规定时间返回一个PONG消息, 发送PING消息的结点A会将接受PING消息的结点标记为疑似下线(probable fail)

ClusterNode.nodes中找到疑似下线的clusterNode结构, 将flags属性REDIS_NODE_PFAIL标识打开

超过半数以上负责槽的结点标记一个结点下线, 这个结点就下线了

从节点发现自己正在复制的主节点进入下线状态, 从节点对主节点进行故障转移

- 复制下线主节点的从节点里 会有一个从节点被选中
- 被选中的从节点执行SLAVEOF no one 命令成为新的主节点
- 新的主节点撤销所有下线主节点的槽指派, 并指派给自己
- 新的主节点向集群广播一条PONG消息, 集群其他节点直到这个节点变成主节点, 并且接管原来下线主节点负责的槽
- 新的主节点开始接收和自己负责处理的槽相关的命令请求, 故障转移完成

1. 开始故障转移, 集群配置纪元的值自增1
2. 对于每个配置纪元, 集群每个负责处理槽的主节点有一次投票的机会, 会投给第一个要求自己投票的从结点
3. 从节点发现正在复制的结点下线, 从结点会向集群广播一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息, 要求所有收到消息的有投票权的主节点向这个从节点投票
4. 拥有投票权的主节点会向第一个向自己发送消息的结点投票, 投完不能再投
5. 当一个从节点收到了集群中N个主节点中的 至少N/2+1 就成为了新的主节点
6. 没有从节点收到足够的票, 集群进入新的配置纪元继续选举直到选出主节点
7. 这个选取Sentinel领头相似都是基于Raft算法