Redis

数据结构

链表:列表建的底层实现(头指针和尾指针的双端链表)

字典:哈希键的底层实现

• 使用链地址法(数组+单向链表)解决键冲突
• rehash(对哈希表伸缩操作,确保负载因子不会太大):将现有哈希表中键值对rehash到新哈希表里面,不是一次性完成,渐进式完成

跳表

• 平均O(logN),最坏O(N)
• 每个节点维持多个指向其他节点的指针(有序集合键的实现)
• 多个节点可包含相同分值,但每个节点对象唯一,分值相同,节点按照对象大小排序

整数集合

压缩列表(列表键和哈希键的实现),为节省内存而生

对象(Redis数据结构)

• 字符串
• 列表
• 哈希
• 集合
• 有序集合

数据库

默认创建16个数据库,默认使用0号数据库

切换数据库

• SELECT命令(原理:修改指针指向不同数据库)

键空间(保存所有键值对)

• 添加键:将新键值对保存到键空间
• 删除键
• 更新键
• 查询键

过期键删除策略

• 定时删除(过期键多,CPU压力大)
• 惰性删除(过期键多,磁盘压力大)
• 定期删除:上述两种方式折衷,难点是时长和频率
• Redis使用惰性删除和定期删除结合

持久化

RDB

• 创建

  • SAVE和BGSAVE命令

• 载入

  • 服务器启动自动检测自动载入

• 自动间隔保存

  • 设置save选项,每隔一段时间自动执行BGSAVE命令

• 服务器开启AOF,则优先使用AOF还原数据库状态

• 压缩的二进制文件

AOF

• 实现

  • 命令追加:写命令追加到缓冲区
  • 文件写入:将缓冲区内容写入AOF文件
  • 文件同步:对AOF文件同步

• 载入:创建伪客户端逐条写入

• 重写:读取数据库状态用新AOF文件替代老AOF文件(子进程).设置重写缓冲区,防止数据不一致

Sentinel

作用:监视主,若主下线,自动将某从升级主

故障转移

• 挑选某从升级为新主
• 向所有从发送新复制指令
• 继续监视下线主,重新上线成为新主的从

故障转移前提

• 一个主下线,监视下线主的各Sentinel投票选举领头Sentinel,由领头Sentinel对下线主执行故障转移

选举领头Sentinel算法

• 每个Sentinel都有投票权,会投给第一个要求投票给他的Sentinel,每次选举后计数器都会自增一次.若一个Sentinel获得投票超过半数则成为领头Sentinel,否则继续选举

复制

SLAVEOF命令或slaveof选项设置主从复制

复制包含两种操作

• 同步
• 命令传播

复制两种情况

• 初次复制
• 断线后重复制

旧版复制

• 同步(SYNC)

  • 1.从发送SYNC命令到主
  • 2.主执行BGSAVE生成RDB,缓冲池记录此刻开始写命令
  • 3.从接收RDB载入
  • 4.从接收缓冲池写命令与主保持数据库状态一致

• 命令传播

  • 主向从发送命令

• 缺陷

  • 断线重复制重新执行同步流程

新版复制

• PSYNC

  • 完整重同步:相当于初次复制

  • 部分重同步:将断线期间主执行写命令发送给从

    • 复制偏移量:主从均记录,断线重连后根据偏移量判断哪些数据丢失
    • 复制积压缓冲区:FIFO队列,命令传播期间,命令传播给从,积压缓冲区也会保存一份,断线重连后,若偏移量命令在积压缓冲区则执行部分重同步,否则执行完整重同步
    • 服务器运行ID

实现(了解)

• 设置主服务器地址和端口
• 建立套接字连接
• 发送PING命令
• 身份验证
• 发送从服务器端口
• 同步
• 命令传播

心跳检测

• 从默认每秒一次频率向主发送命令

• 作用

  • 检测主从网络连接状态
  • 辅助实现min-slaves选项
  • 检测命令丢失

集群

节点

• CLUSTER MEET命令使节点握手,加入到集群中

槽指派

• 集群整个数据库被分为16384个槽,每个节点维护槽的部分

执行命令

• 判断槽是否在改节点,在则直接执行命令,否则指引客户端转向正确节点

重新分片

• 将某个节点的槽改为指派给另一节点,可在线进行

复制

• 主节点处理槽,从节点复制主,主节点下线,从节点代替主处理命令

故障转移

• 每个节点定期向其他节点发送PING消息,若无响应标记疑似下线,半数以上主节点标记疑似下线,则广播通知标记为已下线

• 选举新主节点算法

  • 主节点下线,隶属于该主节点从会广播要求所有主节点投票,每个主节点有一次投票权,投给第一个向他发送投票请求的从节点,当某个从节点获得半数以上主节点投票则升级为新的主节点

Redis.png