Redis 是我们工作中接触最多的非关系型数据库,我所在的公司也是 Redis 的深度用户,我们线上的大部分的业务都使用到了 Redis。与传统数据库不同的是 Redis 的数据是存在内存中的,所以存写速度非常快,因此 Redis 被广泛应用于缓存方向。值得注意的是,Redis 也经常用来做分布式锁。Redis 提供了多种数据类型来支持不同的业务场景。除此之外,Redis 支持事务 、持久化、LUA 脚本、LRU 驱动事件、多种集群方案。以前在使用 Redis 的时候,只是简单地使用它提供的基本数据类型和接口,并没有深入研究它底层的数据结构。最近打算重新学习梳理一下 Redis 方面的知识。
本篇是我学习 Redis 系列的开篇,主要内容讲述 Redis 概述及其相关内容,然后介绍一下 Redis 数据结构,最后介绍一下 Redis 对象以及应用场景。
Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。
Redis 是互联网技术领域使用最为广泛的存储中间件,它是「Remote Dictionary Service」的首字母缩写,也就是「远程字典服务」。Redis 以其超高的性能、完美的文档、简洁易懂的源码和丰富的客户端库支持在开源中间件领域广受好评。
Redis 是一个开源(BSD 许可),内存存储的数据结构服务器,可用作数据库,高速缓存和消息队列代理。它支持字符串、哈希表、列表、集合、有序集合、位图、hyperloglogs 等数据类型。内置复制、LUA 脚本、LRU 收回、事务以及不同级别磁盘持久化功能,同时通过 Redis Sentinel 提供高可用,通过 Redis Cluster 提供自动分区。
1、完全基于内存,绝大部分请求是纯粹的内存操作,非常快速。数据存在内存中,类似于 HashMap,HashMap 的优势就是查找和操作的时间复杂度都是 O(1);
2、数据结构简单,对数据操作也简单,Redis 中的数据结构是专门进行设计的;
3、采用单线程,避免了不必要的上下文切换和竞争条件,也不存在多进程或者多线程导致的切换而消耗 CPU,不用去考虑各种锁的问题,不存在加锁释放锁操作,没有因为可能出现死锁而导致的性能消耗;
4、使用多路 I/O 复用模型[1],非阻塞 IO;
5、使用底层模型不同,它们之间底层实现方式以及与客户端之间通信的应用协议不一样,Redis 直接自己构建了 VM 机制 ,因为一般的系统调用系统函数的话,会浪费一定的时间去移动和请求;
主要由以上几点造就了 Redis 具有很高的吞吐量。
Redis 基于 Reactor 模式开发了网络事件处理器,这个处理器被称为文件事件处理器。它的组成结构为 4 部分:多个套接字、IO 多路复用程序、文件事件分派器、事件处理器。因为文件事件分派器队列的消费是单线程的,所以 Redis 才叫单线程模型。那么,Redis 为什么是单线程的?因为 CPU 不是 Redis 的瓶颈。Redis 的瓶颈最有可能是机器内存或者网络带宽。既然单线程容易实现,而且 CPU 不会成为瓶颈,那就顺理成章地采用单线程的方案了。
Redis 文件事件处理器过程
Redis 4.0 开始就有多线程的概念了,比如 Redis 通过多线程方式在后台删除对象(在旧版中删除包含体积较大的键,可能造成服务器阻塞)、以及通过 Redis 模块实现的阻塞命令等。目前对于单线程 Redis 来说,性能瓶颈主要在于网络的 IO 消耗,因此 Redis 6.0 的多线程则增加了对 IO 读写的并发能力,用于更好的提升 Redis 的性能。
Redis 6.0 默认是否关闭多线程,那么开启多线程后,是否会存在线程并发安全问题?不会,Redis 的多线程部分只是用来处理网络数据的读写和协议解析,执行命令仍然是单线程顺序执行。
Redis 作为目前最流行的 Key-Value 类型的内存数据库,对于数据库的操作都在内存中进行,并可定期的将数据异步的持久化到磁盘之上。由于是纯内存的操作,因此它的性能比普通的关系型数据库高出很多,同时由于是单线程串行的执行指令,因此也避免了加锁和释放锁的开销。相比于 Memcache,Redis 的每个 value 值最大可存储 1GB,而 Memcache 只有 10MB,同时 Redis 在速度上也快于 Memcache,还可以持久化。Redis 最大的特点则是,它可以支持五种基本数据类型,分别是string(字符串),list(列表),hash(字典),set(集合)以及 zet(有序集合),下面具体介绍下它们的特点以及内部实现。
Redis 没有直接使用 C 语言传统的字符串表示(以空字符结尾的字符数组,以下简称 C 字符串), 而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型, 并将 SDS 用作 Redis 的默认字符串表示。
在 Redis 里面, C 字符串只会作为字符串字面量(string literal), 用在一些无须对字符串值进行修改的地方, 比如打印日志;当 Redis 需要的不仅仅是一个字符串字面量, 而是一个可以被修改的字符串值时, Redis 就会使用 SDS 来表示字符串值:比如在 Redis 的数据库里面, 包含字符串值的键值对在底层都是由 SDS 实现的。
SDS 的内部数据结构:
typedef struct sdshdr {
// 记录 buf 数组中已使用字节的数量:等于 SDS 所保存字符串的长度
int len;
// 记录 buf 数组中未使用字节的数量
int free;
// 字节数组,用于保存字符串
char buf[];
};
可见,其底层是一个 char 数组。buf 最大容量为 512M,里面可以放字符串、浮点数和字节。为什么没有直接使用数组,而是包装成了这样的数据结构呢?因为 buf 会有动态扩容和缩容的需求。如果直接使用数组,那每次对字符串的修改都会导致重新分配内存,效率很低。
buf 的扩容过程如下:
重点回顾:
链表提供了高效的节点重排能力, 以及顺序性的节点访问方式, 并且可以通过增删节点来灵活地调整链表的长度。
作为一种常用数据结构, 链表内置在很多高级的编程语言里面, 因为 Redis 使用的 C 语言并没有内置这种数据结构, 所以 Redis 构建了自己的链表实现。
链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表:当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现。除了链表键之外, 发布与订阅、慢查询、监视器等功能也用到了链表, Redis 服务器本身还使用链表来保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer)。
list 的内部数据结构:
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsigned long len;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
} list;
list 结构为链表提供了表头指针 head 、表尾指针 tail , 以及链表长度计数器 len , 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数。
listNode 的内部数据结构:
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
多个 listNode 可以通过 prev 和 next 指针组成双端链表。
重点回顾:
字典, 又称符号表(symbol table)、关联数组(associative array)或者映射(map), 是一种用于保存键值对(key-value pair)的抽象数据结构。在字典中, 一个键(key)可以和一个值(value)进行关联(或者说将键映射为值), 这些关联的键和值就被称为键值对。字典中的每个键都是独一无二的, 程序可以在字典中根据键查找与之关联的值, 或者通过键来更新值, 又或者根据键来删除整个键值对, 等等。
字典经常作为一种数据结构内置在很多高级编程语言里面, 但 Redis 所使用的 C 语言并没有内置这种数据结构, 因此 Redis 构建了自己的字典实现。
字典在 Redis 中的应用相当广泛, 比如 Redis 的数据库就是使用字典来作为底层实现的, 对数据库的增、删、查、改操作也是构建在对字典的操作之上的。除了用来表示数据库之外, 字典还是哈希键的底层实现之一:当一个哈希键包含的键值对比较多, 又或者键值对中的元素都是比较长的字符串时, Redis 就会使用字典作为哈希键的底层实现。
dict 的内部数据结构:
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
dictht 的内部数据结构:
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
dictEntry 的内部数据结构:
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
重点回顾:
跳跃表(skiplist)是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针, 从而达到快速访问节点的目的。在大部分情况下, 跳跃表的效率可以和平衡树相媲美, 并且因为跳跃表的实现比平衡树要来得更为简单, 所以有不少程序都使用跳跃表来代替平衡树。
Redis 使用跳跃表作为有序集合键的底层实现之一:如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员(member)是比较长的字符串时, Redis 就会使用跳跃表来作为有序集合键的底层实现。和链表、字典等数据结构被广泛地应用在 Redis 内部不同, Redis 只在两个地方用到了跳跃表, 一个是实现有序集合键, 另一个是在集群节点中用作内部数据结构, 除此之外, 跳跃表在 Redis 里面没有其他用途。
Redis 的跳跃表由 zskiplistNode 和 zskiplist 两个结构定义,其中 zskiplistNode 结构用于表示跳跃表节点,而 zskiplist 结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。
zskiplist 的内部数据结构:
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
zskiplistNode 的内部数据结构:
typedef struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
Redis跳跃表
重点回顾:
整数集合(intset)是集合键的底层实现之一:当一个集合只包含整数值元素, 并且这个集合的元素数量不多时, Redis 就会使用整数集合作为集合键的底层实现。
整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素。
intset 的内部数据结构:
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
int16_t类型的整数集合
重点回顾:
压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做列表键的底层实现。另外, 当一个哈希键只包含少量键值对, 并且每个键值对的键和值要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做哈希键的底层实现。
压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值。
Redis压缩列表结构
重点回顾:
Redis 并没有直接使用这些数据结构来实现键值对数据库, 而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象, 每种对象都用到了至少一种我们前面所介绍的数据结构。通过这五种不同类型的对象, Redis 可以在执行命令之前, 根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是, 我们可以针对不同的使用场景, 为对象设置多种不同的数据结构实现, 从而优化对象在不同场景下的使用效率。
Redis 使用对象来表示数据库中的键和值,每次当我们在 Redis 的数据库中新创建一个键值对时,我们至少会创建两个对象,一个对象用作键值对的键(键对象),另一个对象用作键值对的值(值对象)。
举个例子,以 “ SET msg “hello world” ” 命令在数据库中创建了一个新的键值对,其中键值对的键是一个包含了字符串值 “msg” 的对象,而键值对的值则是一个包含了字符串值 “hello world” 对象。
Redis 中每个对象都由一个 redisObject 结构表示,该结构中和保存数据有关的三个属性分别是 type 属性、 encoding 属性和 ptr 属性:
typedef struct redisObject {
// 数据类型:就是我们熟悉的 string、hash、list 等五种数据类型
unsigned type:4;
// 内部编码:其实就是数据结构
unsigned encoding:4;
// 指向底层实现数据结构的指针:指向以 encoding 的方式实现这个对象的实际地址
void *ptr;
// 当前对象可以保留的时长
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 对象引用计数:用于 GC
int refcount;
} robj;
类型
对象的 type 属性记录了对象的类型。对于 Redis 数据库保存的键值对来说,键总是一个字符串对象,而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象其中一种。
TYPE 命令返回的结果为数据库键对应的值对象的类型。
# 键为字符串对象,值为字符串对象
redis> SET msg "hello world"
"OK"
redis> TYPE msg
"string"
# 键为字符串对象,值为列表对象
redis> RPUSH numbers 1 3 5
"3"
redis> TYPE numbers
"list"
# 键为字符串对象,值为哈希对象
redis> HMSET profile name Tom age 25 career Programmer
"OK"
redis> TYPE profile
"hash"
# 键为字符串对象,值为集合对象
redis> SADD fruits apple banana cherry
"3"
redis> TYPE fruits
"set"
# 键为字符串对象,值为有序集合对象
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
"3"
redis> TYPE price
"zset"
编码和底层实现
对象的 ptr 指针指向对象的底层实现数据结构, 而这些数据结构由对象的 encoding 属性决定。
每种类型的对象都至少使用了两种不同的编码。
通过 encoding 属性来设定对象所使用的编码, 而不是为特定类型的对象关联一种固定的编码, 极大地提升了 Redis 的灵活性和效率, 因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码, 从而优化对象在某一场景下的效率。
举个例子, 在列表对象包含的元素比较少时, Redis 使用压缩列表作为列表对象的底层实现:因为压缩列表比双端链表更节约内存, 并且在元素数量较少时, 在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中;随着列表对象包含的元素越来越多, 使用压缩列表来保存元素的优势逐渐消失时, 对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面;
字符串对象的编码可以是 int 、 raw 或者 embstr 。
如果一个字符串对象保存的是整数值, 并且这个整数值可以用 long 类型来表示, 那么字符串对象会将整数值保存在字符串对象结构的 ptr属性里面(将 void 转换成 long ), 并将字符串对象的编码设置为 int 。
如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度大于 39 字节(在 Redis 3.2 版本之后,变成了 44 字节为分界), 那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值, 并将对象的编码设置为 raw 。
如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度小于等于 39 字节, 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。
常用命令:set、get、decr、incr、mget 等。
常见应用:缓存、限流、计数器、分布式锁、分布式 Session 等。
列表对象的编码可以是 ziplist 或者 linkedlist 。
ziplist 编码的列表对象使用压缩列表作为底层实现, 每个压缩列表节点(entry)保存了一个列表元素。当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做列表键的底层实现。
linkedlist 编码的列表对象使用双端链表作为底层实现, 每个双端链表节点(node)都保存了一个字符串对象, 而每个字符串对象都保存了一个列表元素。当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现。
常用命令:lpush、rpush、lpop、rpop、lrange 等。
常见应用:微博关注人时间轴列表、简单队列、文章列表。
哈希对象的编码可以是 ziplist 或者 hashtable 。
ziplist 编码的哈希对象使用压缩列表作为底层实现, 每当有新的键值对要加入到哈希对象时, 程序会先将保存了键的压缩列表节点推入到压缩列表表尾, 然后再将保存了值的压缩列表节点推入到压缩列表表尾。当一个哈希键只包含少量键值对, 并且每个键值对的键和值要么就是小整数值, 要么就是长度比较短的字符串, 那么 Redis 就会使用压缩列表来做哈希键的底层实现。
hashtable 编码的哈希对象使用字典作为底层实现, 哈希对象中的每个键值对都使用一个字典键值对来保存。当一个哈希键包含的键值对比较多, 又或者键值对中的元素都是比较长的字符串时, Redis 就会使用字典作为哈希键的底层实现。
常用命令:hget、hset、hgetall 等。
常见应用:存储用户信息、用户主页访问量、组合查询。
集合对象的编码可以是 intset 或者 hashtable 。
intset 编码的集合对象使用整数集合作为底层实现, 集合对象包含的所有元素都被保存在整数集合里面。当一个集合只包含整数值元素, 并且这个集合的元素数量不多时, Redis 就会使用整数集合作为集合键的底层实现。
hashtable 编码的集合对象使用字典作为底层实现, 字典的每个键都是一个字符串对象, 每个字符串对象包含了一个集合元素, 而字典的值则全部被设置为 NULL 。
常用命令: sadd、spop、smembers、sunion 等。
常见应用:赞、踩、标签、好友关系。
有序集合的编码可以是 ziplist 或者 skiplist 。
ziplist 编码的有序集合对象使用压缩列表作为底层实现, 每个集合元素使用两个紧挨在一起的压缩列表节点来保存, 第一个节点保存元素的成员(member), 而第二个元素则保存元素的分值(score)。压缩列表内的集合元素按分值从小到大进行排序, 分值较小的元素被放置在靠近表头的方向, 而分值较大的元素则被放置在靠近表尾的方向。
skiplist 编码的有序集合对象使用 zset 结构作为底层实现, 一个 zset 结构同时包含一个字典和一个跳跃表。zset 结构中的 zsl 跳跃表按分值从小到大保存了所有集合元素, 每个跳跃表节点都保存了一个集合元素:跳跃表节点的 object 属性保存了元素的成员, 而跳跃表节点的 score 属性则保存了元素的分值。通过这个跳跃表, 程序可以对有序集合进行范围型操作, 比如 ZRANK 、ZRANGE 等命令就是基于跳跃表 API 来实现的。如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员(member)是比较长的字符串时, Redis 就会使用跳跃表来作为有序集合键的底层实现。
常用命令:zadd、zrange、zrem、zcard 等。
常见应用:排行榜。
[1]. 《Redis设计与实现》,第一部分 数据结构与对象 [2]. 图解Redis之数据结构篇
[1]. 多路 I/O 复用模型:多路 I/O 复用模型是利用 select、poll、epoll 可以同时监察多个流的 I/O 事件的能力,在空闲的时候,会把当前线程阻塞掉,当有一个或多个流有 I/O 事件时,就从阻塞态中唤醒,于是程序就会轮询一遍所有的流(epoll 是只轮询那些真正发出了事件的流),并且依次顺序的处理就绪的流,这种做法就避免了大量的无用操作。 这里 “多路” 指的是多个网络连接,“复用” 指的是复用同一个线程。采用多路 I/O 复用技术可以让单个线程高效的处理多个连接请求(尽量减少网络 IO 的时间消耗),且 Redis 在内存中操作数据的速度非常快,也就是说内存内的操作不会成为影响 Redis 性能的瓶颈。 [2]. 1byte:SDS 遵循 C 字符串以空字符结尾的惯例, 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面, 并且为空字符分配额外的 1 字节空间, 以及添加空字符到字符串末尾等操作都是由 SDS 函数自动完成的, 所以这个空字符对于 SDS 的使用者来说是完全透明的。 [3]. 渐进式:1、因为在进行渐进式 rehash 的过程中,字典会同时使用 ht[0] 和 ht[1] 两个哈希表,所以在渐进式 rehash 进行期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行。2、在渐进式 rehash 执行期间,新添加到字典的键值对一律会被保存到 ht[1] 里面,而 ht[0] 则不再进行任何添加操作:这一措施保证了 ht[0] 包含的键值对数量会只减不增,并随着 rehash 操作的执行而最终变成空表。
source: https://morning-pro.github.io/archives/8fb486e9.html