枪与玫瑰
枪与玫瑰

目录

《Redis设计与实现》简读

佐柱
   约 346 字   预计阅读 2 分钟 

《Redis设计与实现》核心要点简读

一、数据结构与对象

1. 简单动态字符串（SDS）

  • 优势：

    • 记录字符串长度，获取长度复杂度O(1)
    • 记录已分配内存空间，避免缓冲区溢出
    • 空间预分配和惰性释放机制
    • 二进制安全，不以\0判断结束
    • 兼容C字符串函数（以\0结尾）

  • 空间预分配与惰性释放：

    • 增长时：长度<1M分配2倍空间；长度≥1M分配+1M空间
    • 缩短时：不立即释放多余内存，记录在free属性中
    • 最佳实践：修改相同键的值时，尽量保持长度相近，避免频繁内存重分配

2. 链表

  • 特点：
    • 双向链表，获取前后节点复杂度O(1)
    • 无环，头尾指针指向NULL
    • 记录头尾节点，获取头尾节点复杂度O(1)
    • 记录链表长度，获取长度复杂度O(1)
    • 可存储多种类型数据

3. 字典

  • 实现机制：

    • 链地址法解决哈希冲突（相同索引时添加到链表头）
    • 两个哈希表ht[0]和ht[1]（ht[1]用于rehash）
    • 渐进式rehash：逐步将ht[0]数据迁移到ht[1]
    • 负载因子 = 已保存节点数/哈希表大小

  • rehash步骤：

    1. 扩展（无BGSAVE/BGREWRITEAOF且负载≥1，或有BGSAVE/BGREWRITEAOF且负载≥5）：为ht[1]分配≥当前节点数×2的内存
    2. 收缩（负载<0.1）：为ht[1]分配≥当前节点数的内存
    3. 逐步迁移ht[0]到ht[1]
    4. 释放ht[0]，ht[1]变为ht[0]

Redis哈希算法：MurmurHash2

4. 跳跃表

  • 用途：有序集合底层实现之一
  • 特点：
    • 节点按分值排序，分值相同时按对象大小排序
    • 每个节点可保存字节数组或整数值

5. 整数集合

  • 支持类型：

    • int16_t（-32768至32767）
    • int32_t（-2147483648至2147483647）
    • int64_t（-9223372036854775808至9223372036854775807）

  • 升级机制：

    1. 根据新元素类型扩展底层数组
    2. 转换现有元素类型并保持有序
    3. 添加新元素（小于所有元素放索引0，大于所有元素放索引length-1）

  • 最佳实践：向同一整数集合添加相同类型的整数，避免升级操作

6. 压缩链表

  • 用途：列表键和哈希键的底层实现之一
  • 特点：添加/删除节点可能造成连锁更新，最坏时间复杂度O(N²)

7. 对象与编码

Redis支持5种对象类型，每种类型有不同编码方式：

类型 编码 说明
REDIS_STRING REDIS_ENCODING_INT 整数值实现的字符串对象
REDIS_STRING REDIS_ENCODING_EMBSTR 小于32字节字符串的简单动态字符串实现
REDIS_STRING REDIS_ENCODING_RAW 大于32字节字符串的简单动态字符串实现
REDIS_LIST REDIS_ENCODING_ZIPLIST 元素长度<64字节且数量<513（默认）
REDIS_LIST REDIS_ENCODING_LINKEDLIST 双向链表实现
REDIS_HASH REDIS_ENCODING_ZIPLIST 元素长度<64字节且数量<513（默认）
REDIS_HASH REDIS_ENCODING_HT 字典实现
REDIS_SET REDIS_ENCODING_INTSET 整数值且数量<513（默认）
REDIS_SET REDIS_ENCODING_HT 字典实现
REDIS_ZSET REDIS_ENCODING_ZIPLIST 元素长度<64字节且数量<128（默认）
REDIS_ZSET REDIS_ENCODING_SKIPLIST 跳跃表+字典实现

查看对象编码命令：

TYPE key
OBJECT ENCODING key

8. 内存管理

  • 引用计数：对象计数为0时释放内存
  • 对象共享：初始化创建0-9999字符串对象，相同值共享
  • 空转时长：记录最后访问时间，maxmemory策略为volatile-lru/allkeys-lru时优先释放空转时间长的键

最佳实践：将简单字符串或重复率高的字符串映射到0-9999范围内的数字，节省内存

二、单机数据库的实现

1. 数据库

  • 默认数据库数：16（CONFIG GET databases）
  • 过期键策略：
    • 惰性删除：读取时发现过期才删除
    • 定期删除：定时遍历检查部分键的过期时间

主从模式注意事项：从服务器不会主动删除过期键，会将其当作正常键返回。主从模式不同于MySQL（主写从读），过期数据可能在一段时间内是脏数据。

2. RDB持久化

  • 特点：
    • 保存所有数据库数据
    • SAVE阻塞服务器，BGSAVE通过子进程非阻塞
    • 二进制压缩文件

3. AOF持久化

  • 特点：
    • 保存所有修改命令
    • 命令以Redis协议格式保存
    • 先存入AOF缓冲区，定期写入AOF文件
    • AOF重写：通过读取数据库生成更小的AOF文件

4. 事件处理

  • 事件类型：
    • 文件事件：基于Reactor模式的网络通信（读/写事件）
    • 时间事件：定时/周期事件（如serverCron每100ms执行一次）
  • 执行顺序：事件在文件和时间事件中轮询，不抢占

5. 客户端管理

  • 缓冲区：
    • 输入缓冲区：1GB
    • 输出缓冲区：固定16KB + 可变缓冲区（CONFIG GET client-output-buffer-limit）
  • 最大连接数：默认10000（受系统文件描述符限制，最大=文件描述符数-32）
  • 关闭条件：连接关闭、协议错误、CLIENT KILL、空转超时、缓冲区超限

可变输出缓冲区限制：

  • 普通客户端：无限制
  • PubSub客户端：超过32M或持续60s>8M
  • Slave客户端：超过256M或持续60s>64M

6. 服务器流程

  • 启动步骤：

    1. 初始化服务器状态
    2. 载入配置
    3. 初始化数据结构
    4. 还原数据库状态
    5. 执行事件循环

  • 命令执行流程：

    1. 客户端发送命令
    2. 服务器解析命令参数
    3. 查找并执行命令实现函数
    4. 返回命令回复

三、多机数据库的实现

1. 复制

  • 部分重同步（Redis 2.8+）：
    • 通过复制偏移量、复制挤压缓冲区、服务器运行ID实现
    • 从服务器每1秒发送REPLCONF ACK检测心跳和命令丢失

2. Sentinel（哨兵）

  • 工作原理：
    • 运行在特殊模式下的Redis服务器
    • 向主从服务器创建命令连接和订阅连接
    • 感知其他Sentinel存在，建立命令连接
    • 主观下线后相互询问，收集足够票数（>1/2）后判断客观下线

3. 集群

  • 核心机制：
    • 数据库分为16384个槽
    • 每个节点记录指派的槽
    • 命令请求检查键是否在节点槽中，否则返回MOVED或ASK
    • 重新分片由redis-trib负责
    • 从节点用于主节点故障时的选举

错误区别：

  • MOVED：键已转移至其他节点
  • ASK：槽正在转移过程中的临时错误

四、独立功能的实现

1. 发布与订阅

  • 类型：
    • 频道发布订阅
    • 模式发布订阅
  • 实现：
    • pubsub_channels字典：保存频道订阅关系
    • pubsub_patterns链表：保存模式订阅关系

2. 事务

  • 特点：
    • 打包多个命令，按顺序执行
    • 无回滚功能
    • WATCH命令：监视键是否被修改，若修改则拒绝事务提交

3. Lua脚本

  • 执行机制：
    • 内嵌Lua环境，修改函数适应Redis
    • 使用伪客户端执行Redis命令
    • 脚本字典：以SHA1校验和为键名
    • 超时处理：SCRIPT KILL或SHUTDOWN nosave

Redis创建Lua环境步骤：

  1. 创建基础Lua环境
  2. 载入函数库
  3. 创建Redis操作函数全局表
  4. 替换随机函数
  5. 创建排序辅助函数
  6. 创建错误报告函数redis.pcall
  7. 保护全局变量
  8. 保存到服务器状态

4. 排序

  • 实现：快速排序算法
  • 执行：将元素保存在数组中，再对数组排序

5. 慢查询日志

  • 默认设置：
    • 记录>10000us的命令（CONFIG GET slowlog-log-slower-than）
    • 保留128条（CONFIG GET slowlog-max-len）

五、Redis 4.0特性

1. 模块系统

  • 作用：扩展数据结构及功能
  • 示例：ReJSON模块 
    127.0.0.1:6379> JSON.SET test . '{"first": 1, "second": 2, "three": 3}'
OK
127.0.0.1:6379> JSON.GET test
"{\"first\":1,\"second\":2,\"three\":3}"

2. PSYNC 2.0

  • 改进：主从节点在条件允许下使用部分复制

3. 缓存驱逐策略优化（LFU）

  • 原理：根据访问计数和最近访问时间计算分值
  • 计数器函数： 
    uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

4. 非阻塞删除命令

  • 新增：
    • UNLINK（非阻塞DEL）
    • FLUSHDB ASYNC/FLUSHALL ASYNC

5. 混合RDB-AOF持久化

  • 特点：AOF重写文件同时包含RDB和AOF格式内容
    • RDB格式：记录已有数据
    • AOF格式：记录最近变化数据

6. 内存命令

  • 新命令：MEMORY HELP用于查看内存使用情况和进行管理

六、Redis 5.0特性

1. Stream（流）

2. SortedSet新增命令

命令 说明
ZPOPMAX 移除并弹出有序集合中分值最大的元素
ZPOPMIN 移除并弹出有序集合中分值最小的元素
BZPOPMAX 阻塞移除并弹出有序集合中分值最大的元素
BZPOPMIN 阻塞移除并弹出有序集合中分值最小的元素

重要提示：以上内容为《Redis设计与实现》核心要点的简明总结，适用于Redis 3.0-5.0版本。实际使用中，应参考官方文档了解最新特性和最佳实践。

更新于 2016-06-12
返回 | 主页