前言
Redis 性能为什么这么出色? 它与其他缓存中间件有什么区别?
Redis 底层使用了哪些数据结构支撑它如此高效的性能?
内部丰富的数据类型底层为什么都使用至少两种数据结构实现? 分别是什么?
如果合理的使用 Redis 才能发挥它最大的优势?
学习完《Redis 设计与实现》前面关于数据结构与对象的章节, 以上问题都能得到解答. 你也能了解到 Redis 作者如此的煞费苦心设计了这么多丰富的数据结构, 目的就是优化内存. 学完这些内容, 在使用 Redis 的过程中, 也会合理的使用以适应它内部的特点. 当然新版本的 Redis 支持了更多更丰富的特性, 该书基于 redis3 版本, 还没有涉及到那些内容.
概述
特点
c 语言开发, 性能出色, 纯内存操作, 每秒可处理超过 10w 读写(QPS)
多种数据结构, 单个最大限制可到 1GB(Memcached 只支持字符串, 最大 1M)
受物理内存限制, 不能作海量数据的读写. 适用于较小数据量的高性能操作和运算上
支持事务, 持久化
单线程模型(Memcached 是多线程)
支持的数据类型
- Sring
- List
- Set
- SortedSet
- hash
- Bitmap
- Hyperloglogs
- Geo
- pub/sub
Redis 为什么这么快
纯内存操作, 没有磁盘 io
单线程处理请求, 没有线程切换开销和竞争条件, 也不存在加锁问题
多路复用模型 epoll, 非阻塞 io(多路: 多个网络连接; 复用: 复用同一个线程) 多路复用技术可以让单个线程高效的处理多个连接请求
数据结构简单, 对数据操作也简单. 还做了自己的数据结构优化
Redis 为什么是单线程的
单线程已经很快了, 减少多线程带来的网络开销, 锁操作
后续的 4.0 版本在考虑多线程
单线程是指处理网络请求的时候只有一个线程, 并不是 Redis-server 只有一个线程在工作. 持久化的时候, 就是通过 fork 一个子线程来执行.
缺点: 耗时的命令会导致并发的下降, 比如 keys *
Redis 的回收策略
volatile-lru: 从过期的数据集 server.db[i].expires 中挑选最近最少使用的数据
volatile-ttl: 从过期的数据集 server.db[i].expires 中挑选将要过期的数据淘汰
volatile-random: server.db[i].expires 中挑选任意数据淘汰
allkeys-lru: 从数据集 (server.db[i].dict) 中挑选最近最少使用的数据淘汰
allkeys-random: 从数据集 (server.db[i].dict) 中任意选择数据淘汰
no-enviction(驱逐): 禁止驱逐数据
使用注意
Redis 单线程无法发挥多核 CPU 性能, 可以通过单机开多个 Redis 实例来完善
Redis 实现分布式锁: 先用 setnx(如果不存在才设置)争抢锁, 抢到后, expire 设置过期时间, 防止忘记释放.
Redis 实现一对多消息订阅: sub/pub 数据结构
Redis 实现延时消息队列: zadd 时间戳作为 score 消费的时候根据时间戳 + 延时时间做查询操作.
各大版本介绍
redis5 版本新增功能:
zpopmax zpopmin 以及阻塞变种: 返回集合中给定分值最大最小的数据数量
reids4 版本新增功能:
模块功能, 提供类似于插件的方式, 自己开发一个. so 模块, 并加装 作者本人提供了一个神经网络的 module. 可到 Redis-modules-hub 上查看更多的 module 模块功能使得用户可以将 Redis 用作基础设施, 并在上面构建更多功能, 这给 Redis 带来了无数新的可能性.
PSYNC: 解决了旧版本的 Redis 在复制时的一些不够优化的地方
缓存清理策略优化 新增 last frequently used 对已有策略进行优化
非阻塞 DEL FLUSHDB FLUSHALL 解决了之前执行这些命令的时候导致阻塞的问题 Flushdb async, flushall async, unlink(替代 del)
添加了 swapdb: 交换数据库
混合 RDB-AOF 的持久化格式
添加内存使用情况命令: MEMORY
数据结构
Redis 里面每个键值对都是由对象组成的
键总是一个字符串对象,
值则可以是以下对象的一种:
字符串对象
列表对象
哈希对象
集合对象
有序结合对象
简单动态字符串 SDS
数据结构
- struct sdshdr {
- uint8_t len; /* used, 使用的字节数 */
- uint8_t alloc; /* excluding the header and null terminator, 预分配总字节数, 不包括结束符 \ 0 的长度 */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[]; /*c 风格的字符, 包括结束符 \ 0*/
- };
位于 sds.h 文件
SDS 遵循 C 字符串以 \ 0 结尾的惯例, 存储在 buf 中(不同于 nginx 的底层实现, nginx 实现时不保存最后一个 \ 0)
但是不计算最后一个字符的长度到 len 中
保留 c 风格 buf 的好处是可以重用一部分 c 函数库的函数
分配和释放策略
空间预分配
用于优化 SDS 字符串增长操作, 以减少连续执行增长操作所需的内存重分配次数
扩展 SDS 空间时, 先检查未使用的空间是否足够, 如果足够直接使用, 如果不够, 不仅分配够用, 还预分配一些空间
预分配策略:
修改后的 SDS 长度(len 的值)<1MB, 预分配同样 len 大小的空间
修改后的 SDS 长度(len 的值)>= 1MB, 预分配 1MB 大小的空间
惰性空间释放
用于优化 SDS 字符缩短操作
缩短 SDS 空间时, 并不立即进行内存重分配释放空间, 而是记录 free 的字节数
SDS 提供相应 API, 有需要时真正释放空间
比 C 字符串的优势
获取字符串的长度时间复杂度由 O(N)降到 O(1)
避免缓冲区溢出
减少修改字符串时带来的内存重分配次数. 内存分配会涉及复杂算法, 且可能需要系统调用, 非常耗时.
二进制安全: c 语言的结束符限制了它只能保存文本数据, 不能保存图片, 音频等二进制数据
链表
数据结构
位于 adlist.h 文件
- typedef struct listNode {
- struct listNode *prev; // 前置节点
- struct listNode *next; // 后置节点
- void *value;// 节点值
- } listNode;
- typedef struct list {
- listNode *head; // 表头节点
- listNode *tail; // 表尾节点
- void *(*dup)(void *ptr); // 节点值复制函数
- void (*free)(void *ptr); // 节点值释放函数
- int (*match)(void *ptr, void *key); // 节点值对比函数
- unsigned long len; // 节点数量
- } list;
特点
双端队列, 可以获取某个节点前置节点和后置节点, 复杂度为 O(1)
无环
获取表头和表尾复杂度为 O(1)
带长度, 获取链表长度复杂度为 O(1)
多态: 使用 void * 保存节点值, 可保存不同类型的值
字典
数据结构
位于 dict.h 文件
哈希表
- // 哈希表
- typedef struct dictht {
- dictEntry **table; // 一个数组, 数组中每个元素都是指向 dictEntry 结构的指针
- unsigned long size; // table 数组的大小
- unsigned long sizemask; // 值总数 size-1
- unsigned long used; // 哈希表目前已有节点 (键值对) 的数量
- } dictht;
哈希节点
- // 每个 dictEntry 都保存着一个键值对, 表示哈希表节点
- typedef struct dictEntry {
- void *key; // 键值对的键
- // 键值对的值, 可以是指针, 整形, 浮点型
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- double d;
- } v;
- struct dictEntry *next; // 哈希表节点指针, 用于解决键冲突问题
- } dictEntry;
字典类型
每个字典类型保存一簇用于操作特定类型键值对的函数
- typedef struct dictType {
- // 计算哈希值的函数
- uint64_t (*hashFunction)(const void *key);
- // 复制键的函数
- void *(*keyDup)(void *privdata, const void *key);
- // 复制值的函数
- void *(*valDup)(void *privdata, const void *obj);
- // 对比键的函数
- int (*keyCompare)(void *privdata, const void *key1, const void *key2);
- // 销毁键的函数
- void (*keyDestructor)(void *privdata, void *key);
- // 销毁值的函数
- void (*valDestructor)(void *privdata, void *obj);
- } dictType;
字典
- // 字典
- typedef struct dict {
- dictType *type; // 不同键值对类型对应的操作函数
- void *privdata; // 需要传递给对应函数的参数
- dictht ht[2]; // ht[0]用于存放数据, ht[1]在进行 rehash 时使用
- long rehashidx; /* rehashing not in progress if rehashidx == -1, 目前 rehash 的进度 */
- unsigned long iterators; /* number of iterators currently running */
- } dict;
哈希算法
Redis 使用 MurmurHash2 算法计算键的 hash 值
哈希值与 sizemask 取或, 得到哈希索引
哈希冲突(两个或以上数量键被分配到哈希表数组同一个索引上): 链地址法解决冲突
rehash
对哈希表进行扩展或收缩, 以使哈希表的负载因子维持在一个合理范围之内
负载因子 = 保存的节点数(used)/ 哈希表大小(size)
rehash 步骤包括
为字典的 ht[1]哈希表分配空间, 大小取决于要执行的操作以及 ht[0]当前包含的键值对数量
扩展操作: ht[1]大小为第一个大于等于 ht[0].used 乘以 2 的 2 的 n 次幂
收缩操作: ht[1]大小为第一个大于等于 ht[0].used 的 2 的 n 次幂
将保存在 ht[0]的所有键值对 rehash 到 ht[1]上面: 重新计算键的哈希值和索引值
当所有 ht[0]的键值对都迁移到 ht[1]之后, 释放 ht[0], 将 ht[1]置为 ht[0], 并新建一个恐怖 hash 作为 ht[1]
自动扩展的条件
服务器没有执行 BGSave 命令或 GBRewriteAOF 命令, 并且哈希表的负载因子>= 1
服务器正在执行 BGSave 命令或 GBRewriteAOF 命令, 并且哈希表的负载因子>= 5
BGSave 命令或 GBRewriteAOF 命令时, 服务器需要创建当前服务器进程的子进程, 会耗费内存, 提高负载因子避免写入, 节约内存
自动收缩的条件
哈希表负载因子小于 0.1 时, 自动收缩
渐进式 rehash
ht[0]数据重新索引到 ht[1]不是一次性集中完成的, 而是多次渐进式完成(避免 hash 表过大时导致性能问题)
渐进式 rehash 详细步骤
为 ht[1]分配空间, 让自动同时持有两个哈希表
字典中 rehashidx 置为 0, 表示开始执行 rehash(默认值为 - 1)
rehash 期间, 每次对字典执行操作时, 顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]
全部 rehash 完毕时, rehashidx 设为 - 1
注意点
rehash 的所有操作会在两个哈希表进行
新增加的值一律放入 ht[1], 保证数据只会减少不会增加
跳跃表
跳跃表是一种有序数据结构, 通过在每个节点维持多个指向其他节点的指针, 达到快速访问节点的目的
时间复杂度: 最坏 O(N), 平均 O(logN)
大部分情况下, 效率可与平衡树媲美, 不过比平衡树实现简单
有序集合的底层实现之一
数据结构
位于 server.h 文件中
- // 跳跃表节点
- typedef struct zskiplistNode {
- sds ele; // 成员对象
- double score; // 分值, 从小到大排序
- struct zskiplistNode *backward; // 后退指针, 从表尾向表头遍历时使用
- struct zskiplistLevel {
- struct zskiplistNode *forward; // 前进指针
- unsigned long span; // 跨度, 记录两个节点之间的距离
- } level[]; // 层, 是一个数组
- } zskiplistNode;
- // 跳跃表相关信息
- typedef struct zskiplist {
- struct zskiplistNode *header, *tail; // 表头和表尾
- unsigned long length; // 跳跃表长度(包含节点的数量)
- int level; // 跳跃表内层数最大那个节点的层数(不包括表头节点层数)
- } zskiplist;
level 数组的大小在每次新建跳跃表的时候, 随机生成, 大小介于 1-32 直接
遍历操作只使用前进指针, 跨度用来计算排位(rank), 沿途访问的所有层跨度加起来就是节点的排位
多个节点可以包含相同的分支, 但每个节点成员对象是唯一的
整数集合
intset 是集合键的底层实现之一
当一个集合只包含整数值原素, 且数量不多时, 会使用整数集合作为底层实现
数据结构
位于 intset.h 文件
- typedef struct intset {
- uint32_t encoding; // 编码方式
- uint32_t length; // 长度
- int8_t contents[]; // 内容, 数组内容类型取决于 encoding 属性, 并不是 int8_t. 按照大小排序, 没有重复
- } intset;
升级
当我们要将一个新元素添加到整数集合里, 并且新元素的类型比整数集合现有所有的元素类型都要长时, 集合要先进行升级才能添加新数据
升级步骤包括三步:
根据类型, 扩展大小, 分配空间
将底层数组数据都转换成新的类型, 并反倒正确位置
新元素添加到底层数组里面
添加元素可能导致升级, 所以添加新元素的世界复杂度为 O(N)
不支持降级, 升级后将一直保持新的数据类型
升级的好处
提高灵活性
节约内存
压缩列表
ziplist 是列表键和哈希键的底层实现之一
Redis 为了节约内存而开发的顺序型数据结构
当列表键只包含少量列表项, 且每个列表项要么是小整数, 要么是短字符串, 就使用 ziplist 作为列表键底层实现
压缩列表遍历时, 从表位向表头回溯遍历
ziplist 没有专门的 struct 来表示
压缩列表的构成
属性 | 类型 | 长度 | 用途 |
---|---|---|---|
zlbytes | uint32_t | 4 字节 | 整个压缩列表占用的内存字节数 |
zltail | uint32_t | 4 字节 | 表尾节点距离压缩列表起始地址有多少字节,无需遍历就可得到表尾节点 |
zllen | uint16_t | 2 字节 | 节点数量,小于 65535 时是实际值,超过时需要遍历才能算出 |
entryN | 列表节点 | 不定 | 包含的各个节点 |
zlend | uint8_t | 1 字节 | 特殊值 0xFF, 末端标记 |
压缩列表节点的构成
previos_entry_length: 前一个节点的长度, 用于从表尾向表头回溯用
如果前面节点长度小于 254 字节, preivos_entry_length 用 1 字节表示
如果前面节点长度小于 254 字节, preivos_entry_length 用 5 字节表示, 第 1 个字节为 0xFE(254), 后面四个字节表示实际长度
encoding: 记录 content 的类型以及长度, encoding 分为两部分, 高两位和余下的位数, 最高两位的取值有以下情况:
最高两位取值 | 表示是数据类型 | encoding 字节数 | 余下的 bit 数 | 最大范围 |
---|---|---|---|---|
00 | 字符数组 | 一个字节 | 6bit | 63 位 |
01 | 字符数组 | 两个字节 | 14bit | 2^14-1 |
10 | 字符数组 | 五个字节 | 4*8,第一个字节余下的 6bit 留空 | 2^32-1 位 |
11 | 整数 | 1 个字节 | 000000 | int16_t 类型整数 |
11 | 整数 | 1 个字节 | 010000 | int32_t 类型整数 |
11 | 整数 | 1 个字节 | 100000 | int64_t 类型整数 |
11 | 整数 | 1 个字节 | 110000 | 24 位有符号整数 |
11 | 整数 | 1 个字节 | 111110 | 8 位有符号整数 |
11 | 整数 | 1 个字节 | xxxxxx | 没有 content,xxxx 本身就表示了 0-12 的整数 |
content: 保存节点的值
连锁更新
连续多个节点大小介于 254 左右的节点, 因扩展导致连续内存分配的情况. 不过在时间情况下, 这种情况比较少.
对象
概述
Redis 并没有直接使用前面的数据结构来实现键值对的数据库, 而是基于数据结构创建了一个对象系统, 每种对象都用到前面至少一种数据结构
每个对象都由一个 redisObject 结构来表示
- //server.h
- typedef struct redisObject {
- unsigned type:4; // 类型
- unsigned encoding:4; // 编码
- // 对象最后一个被命令程序访问的时间
- unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
- * LFU data (least significant 8 bits frequency
- * and most significant 16 bits access time). */
- int refcount; // 引用计数
- void *ptr; // 指向底层的数据结构指针
- } robj;
使用对象的好处
在执行命令之前, 根据对象类型判断一个对象是否可以执行给定的命令
针对不同厂家, Wie 对象设置多种不同的数据结构实现, 从而优化效率
实现了基于引用计数的内存回收机制, 不再使用的对象, 内存会自动释放
引用计数实现对象共享机制, 多个数据库共享同一个对象以节约内存
对象带有时间时间积累信息, 用于计算空转时间
Redis 中的对象
字符串对象
列表对象
哈希对象
集合对象
有序结合对象
对象的类型与编码
对象的类型
对象 | 对象 type 属性 | type 命令的输出 |
---|---|---|
字符串对象 | REDIS_STRING | string |
列表对象 | REDIS_LIST | list |
哈希对象 | REDIS_HASH | hash |
集合对象 | REDIS_SET | set |
有序集合对象 | REDIS_ZSET | zset |
对象的编码
编码决定了 ptr 指向的数据类型, 表明使用什么数据类型作为底层实现
每种类型对象至少使用两种不同的编码
通过编码, Redis 可以根据不同场景设定不同编码, 极大提高灵活性和效率
编码常量 | 对应的数据结构 | OBJECT ENCODING 命令输出 |
---|---|---|
REDIS_ENCODING_INT | long 类型的整数 | “int” |
REDIS_ENCODING_EMBSTR | embstr 编码的简单动态字符串 | “embstr” |
REDIS_ENCODING_RAW | 简单动态字符串 | “raw” |
REDIS_ENCODING_HT | 字典 | “hashtable” |
REDIS_ENCODING_LINKEDLIST | 双端链表 | “linkedlist” |
REDIS_ENCODING_ZIPLIST | 压缩列表 | “ziplist” |
REDIS_ENCODING_INTSET | 整数集合 | “intset” |
REDIS_ENCODING_SKIPLIST | 跳跃表和字典 | “skiplist” |
字符串对象
字符串对象的编码可以是
int
raw
embstr
浮点数在 Redis 中也是作为字符串对象保存, 涉及计算时, 先转回浮点数.
字符串对象内容 | 长度 | 编码类型 |
---|---|---|
整数值 | - | int |
字符串值 | 小于 32 字节 | embstr |
字符串值 | 大于 32 字节 | raw |
embstr 编码是专门用于保存短字符串的一种优化编码方式. 这种编码和 raw 编码一样, 都使用 redisObject 结构和 sdshdr 结构来表示对象. 区别在于:
raw 编码调用两次内存分配函数来分别创建 redisObject 和 sdrhdr 结构
embstr 则调用一次内存分配函数来创建一块连续空间, 里面包括 redisObject 和 sdrhdr
编码转换
int 编码和 embstr 编码的对象满足条件时会自动转换为 raw 编码的字符串对象
int 编码对象, 执行命令导致对象不再是整数时, 会转换为 raw 对象
embstr 编码没有相应执行函数, 是只读编码. 涉及修改时, 会转换为 raw 对象
字符串命令
Redis 中所有键都是字符串对象, 所以所有对于键的命令都是针对字符串键来构建的
- set
- get
- append
- incrbyfloat
- incrby
- decrby
- strlen
- strrange
- getrange
列表对象
列表对象的编码可以是
ziplist
linkedlist
编码转换
使用 ziplist 编码的两个条件如下, 不满足的都用 linkedlist 编码(这两个条件可以在配置文件中修改):
保存的所有字符串元素的长度都小于 64 字节
列表的元素数量小于 512 个
列表命令
- lpush
- rpush
- lpop
- rpop
- lindex
- llen
- linsert
- lrem
- ltrim
- lset
哈希对象
哈希对象的编码可以是
ziplist
hashtable
编码转换
使用 ziplist 需要满足两个条件, 不满足则都使用 hashtable(这两个条件可以在配置文件中修改)
所有键值对的键和值的字符串长度都小于 64 字节
键值对数量小于 512 个
哈希命令
- hset
- hget
- hexists
- hdel
- hlen
- hgetall
集合对象
集合对象的编码可以是:
intset: 所有元素保存在整数集合里
hashtale: 字典的值为 null
编码转换
集合使用 intset 需要满足两个条件, 不满足时使用 hashtable(参数可通过配置文件修改)
保存的所有元素都是整数值
元素数量不超过 512 个
集合命令
- sadd
- scard
- sismember
- smembers
- srandmember
- spop
- srem
有序结合对象
有序集合的编码可以是
ziplist: 每个元素使用两个紧挨在一起的节点表示, 第一个表示成员, 第二个表示分值. 分值小的靠近表头, 分值大的靠近表尾
skiplist: 使用 zset 作为底层实现, zset 结构同时包含了字典和跳跃表, 分别用于根据 key 查找 score 和分值排序或范围查询
- // 两种数据结构通过指针共享元素成员和分值, 不会浪费内存
- typedef struct zset {
- zskplist *zsl; // 跳跃表, 方便 zrank,zrange
- dict *dict; // 字典, 方便 zscore
- }zset;
编码转换
当满足以下两个条件时, 使用 ziplist 编码, 否则使用 skiplist(可通过配置文件修改)
保存的元素数量少于 128 个
成员长度小于 64 字节
有序集合命令
- zadd
- zcard
- zcount
- zrange
- zrevrange
- zrem
- zscore
类型检查和命令多态
Redis 的命令可以分为两大类:
可以对任意类型的键执行, 如
- del
- expire
- rename
- type
- object
只能对特定类型的键执行, 比如前面各种对象的命令. 是通过 redisObject 的 type 属性实现的
内存回收
Redis 通过对象的 refcount 属性记录对象引用计数信息, 适当的时候自动释放对象进行内存回收
对象共享
包含同样数值的对象, 键的值指向同一个对象, 以节约内存.
Redis 在初始化时, 创建一万个字符串对象, 包含从 0-9999 的所有整数值, 当需要用到这些值时, 服务器会共享这些对象, 而不是新建对象
数量可通过配置文件修改
目前不包含字符串的对象共享, 因为要比对字符串是否相同本身就会造成性能问题
对象空转时长
空转时长 = 现在时间 - redisObject.lru,lru 记录对象最后一次被访问的时间
当 Redis 配置了最大内存 (maxmemory) 时, 回收算法判断内存超过该值时, 空转时长高的会优先被释放以回收内存
参考命令
- # 设置字符串
- set msg "hello world"
- rpush numbers 1 2 3 4 5
- llen numbers
- lrange numbers 0 5
- # 获取键值使用的底层数据结构
- object encoding numbers
- # 查看对象的引用计数值
- object refcount numbers
- # 对象空转时长: value=now-object.lru
- object idletime numbers
参考文献
《Redis 设计与实现》
来源: https://juejin.im/post/5bc672296fb9a05cee1e11f2