Redis 设计与实现读书笔记

一、简单动态字符串 SDS

• 常数复杂度获取字符串长度
• 减少修改字符串时内存重新分配的次数
  • 空间预分配
  • 惰性空间释放
• 二进制安全（通过 len 字段读出来所有数据，不会对数据做任何处理，写的时候是什么样子，读的时候就是什么样子）
• 兼容 C 语言的字符串函数

比原始的 C 字符串操作更安全便捷

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

二、双向链表 List

应用于：列表键、慢查询、监视器等

三、字典 Hash

应用于：字典、数据库 redisDb 结构等

死磕 Redis5.0 字典

• 根据负载因子决定是否扩容（负载因子=总键值对数/箱子个数）

Rehash 简单总结

/* 字典结构定义 */
typedef struct dict { 
   dictType *type;  // 字典类型
   void *privdata;  // 私有数据
   dictht ht[2];    // 哈希表[两个][为了后续字典的扩展作Rehash之用]
   long rehashidx;   // 记录rehash 进度的标志，值为-1表示rehash未进行
   int iterators;   //  当前正在迭代的迭代器数
} dict;

/* Hash 表数据结构 */
typedef struct dictht { 
    dictEntry **table;   // 哈希表数组
    unsigned long size;  // 哈希表的大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used;  // 哈希表现有节点的数量
} dictht;

/* 哈希桶数据结构 */
typedef struct dictEntry { 
    void *key;     // 键定义
    // 值定义
    union { 
        void *val;    // 自定义类型
        uint64_t u64; // 无符号整形
        int64_t s64;  // 有符号整形
        double d;     // 浮点型
    } v;     
    struct dictEntry *next;  //指向下一个哈希表节点
} dictEntry;

四、跳跃表

用于：有序集合

死磕Redis5.0跳跃表

跳表具有如下性质：

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现

(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

(6) 通过一个随机函数，来决定将这个结点插入到哪几级索引中

五、整数集合

参考链接

集合键的底层实现，当集合只包含整数值元素，且数量不多的时候使用

typedef struct intset { unit32_t encoding; //编码方式 int16_t int32_t 或者 int64_t unit32_t length; //集合包含的元素数量 int8_t contents[]; //重点：保存元素的数数组（数字真正的类型取决于 encoding 属性） }intset;

升级操作（不支持降级）：

• 触发条件：当添加一个新的数据超出了当前编码类型的长度时
• 操作：扩容 + 将现有数据转化到其他的位置 + 添加新元素到末尾
• 优势：灵活、节省内存

六、压缩列表

用于实现：列表和字典类型

压缩列表的内部结构

压缩列表原理和应用分析

什么是压缩列表

应用：hash、list、zset 容器对象中，在元素个数较少的时候，会使用ziplist进行存储

遍历：通过 zltail 获取到队尾节点，之后根据偏移量获取上一个节点

更新：增加元素可能造成拓展内存或者重新分配内存

struct ziplist<T> { int32 zlbytes; // 整个压缩列表占用字节数 int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点 int16 zllength; // 元素个数 T[] entries; // 元素内容列表，挨个挨个紧凑存储 int8 zlend; // 标志压缩列表的结束，值恒为 0xFF } zlend //压缩列表的末端标记 struct entry { int<var> prevlen; // 前一个 entry 的字节长度 （通过这个进行遍历数据） int<var> encoding; // 元素类型编码和长度 optional byte[] content; // 元素内容 }

它有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同之处在于：

• 允许存储的数据大小不同
• 可以存储不同类型的数据

我们在遍历节点的之后就知道每个节点的长度(占用内存的大小)，就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。

七、Redis 对象

Redis的每种对象其实都由对象结构(redisObject) 与 对应编码的数据结构组合而成

redisObject 是 Redis 类型系统的核心, 数据库中的每个键、值, 以及 Redis 本身处理的参数

• 使用引用计数进行内存回收
• 使用对象共享节省内存

typedef struct redisObject {
    unsigned type:4;     // 类型 
    unsigned encoding:4; // 编码方式  
    unsigned lru:LRU_BITS; // LRU - 24位, 记录最末一次访问时间（相对于lru_clock）; 或者 LFU（最少使用的数据：8位频率，16位访问时间）
    int refcount; //引用计数 
    void *ptr; //指向底层数据结构实例 
} robj;

八、Redis DB结构

Redis中存在“数据库”的概念，该结构由redis.h中的redisDb定义。

• 当Redis 服务器初始化时，会预先分配 16 个数据库，所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中
• redisClient中存在一个名叫db的指针指向当前使用的数据库

typedef struct redisDb {
	int id; //id是数据库序号，为0-15（默认Redis有16个数据库）
	long avg_ttl; //存储的数据库对象的平均ttl（time to live），用于统计
	dict *dict; //存储数据库所有的key-value（重要）
	dict *expires; //存储key的过期时间（重要）
	dict *blocking_keys;//blpop 存储阻塞key和客户端对象
	dict *ready_keys;//阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象
	dict *watched_keys;//存储watch监控的的key和客户端对象
} redisDb;

Redis 过期键的删除策略

上面 redisDb 结构中的 expires 字典保存了数据库中所有键的过期时间，redis 使用下面两种方式删除过期数据

• 惰性删除，碰到过期键的时候才进行删除（CPU 友好型）
• 定期删除：每隔一段时间主动查找并删除一定数量过期 key （内存友好型）

九、事务

将多条命令请求打包，然后一次性、按顺序地执行多个命令的机制（服务器不会中断事务而去执行其他客户端的命令请求）

事务执行过程

• 客户端连接执行 multi 命令进入一个事务上下文。
• 接受命令，把命令存储进队列中。
• 接受到 exec 指令执行队列命令，接受到 discard 指令清空队列并推出事务上下文。

十、数据持久化

内存快照 RDB持久化

把内存中的数据以快照的方式写入二进制文件中，默认文件为 dump.rdb 。

Redis会单独创建（fork）一个子进程来进行持久化，会先将数据写入到 一个临时文件中，待持久化过程都结束了，再用这个临时文件替换上次持久化好的文件。

日志追加 aof

把增加、修改数据的命令通过 write 函数追加到文件尾部（默认为 appendonly.aof ），Redis重启时读取文件把数据写入内存。

重写机制：当AOF文件的大小超过所设定的阈值时，Redis就会启动AOF文件的内容压缩， 只保留可以恢复数据的最小指令集.可以使用命令bgrewriteaof。Redis会记录上次重写时的AOF大小，默认配置是当AOF文件大小是上次rewrite后大小的一倍且文件大于64M时触发

十一、Redis 集群常用集群方案

4 种 Redis 集群方案介绍 + 优缺点对比

• 主从模式
  • 需要人工干预把从机改为主机
• 哨兵模式
  • 每个主机都存了全量的数据，只有主机接受写操作
• redis代理分片用得最多的就是Twemproxy，由Twitter开源的Redis代理
  • 原理：Redis客户端把请求发送到Twemproxy，Twemproxy根据路由规则发送到正确的Redis实例，最后Twemproxy把结果汇集返回给客户端
  • 优点
    • 客户端像链接 redis 一样链接 Twemproxy，减少了客户端与Redis实例的连接数
  • 缺点
    • 无法平滑地扩容/缩容，因为路由规则的原因当业务需要增加 Redis 实例时工作量非常大（一致性 hash 算法增加 slot 需要迁移数据）
    • 每个请求都经过Twemproxy代理才能到达Redis服务器
• Redis Cluster（3.0 上）
  • 原理：Redis Cluster是一种服务器 Sharding 技术(分片和路由都是在服务端实现)，采用多主多从，每一个分区都是由一个Redis主机和多个从机组成，片区和片区之间是相互平行的，完全去中心化。
  • 优点
    • 完全去中心化，采用多主多从
  • 缺点：扩容需要迁移部分数据