1 背景

分布式系统绕不开的核心之一的就是数据缓存,有了缓存的支撑,系统的整体吞吐量会有很大的提升。通过使用缓存,我们把频繁查询的数据由磁盘调度到缓存中,保证数据的高效率读写。 当然,除了在内存内运行还远远不够,我们今天就以具有代表性的缓存中间件Redis为例子,分析下,它是如何达到飞起的效率。

2 Redis高效性能分析

Redis之所以能够提供超高的执行效率,主要从以下几个维度来实现的:image

  • 存储模式:基于内存实现,而非磁盘
  • 数据结构:基于不同业务场景的高效数据结构
    • 动态字符串(REDIS_STRING):整数(REDIS_ENCODING_INT)、字符串(REDIS_ENCODING_RAW)
    • 双端列表(REDIS_ENCODING_LINKEDLIST)
    • 压缩列表(REDIS_ENCODING_ZIPLIST)
    • 跳跃表(REDIS_ENCODING_SKIPLIST)
    • 哈希表(REDIS_HASH)
    • 整数集合(REDIS_ENCODING_INTSET)
  • 线程模型: Redis 的网络 IO 以及键值对指令读写是由单个线程来执行的,避免了不必要的contextswitch和竞选
  • I/O 模型: 基于I/O多路复用模型,非阻塞的I/O模型
  • 恰单的数据编码: 根据实际数据类型,选择合理的数据编码

2.1 官网的性能报告

Redis官方站点中,有对Redis性能做了比较详细的压测,可以参考官方这一篇 How fast is Redis?, 在较高的配置基准下(比如 8C 16G +),在连接数为0~10000的时候,最高QPS可达到120000。Redis以超过60000个连接为基准,仍然能够在这些条件下维持50000个q/s,体现了超高的性能。下图中横轴是连接数,纵轴是QPS。image 下面这张图为data size 与整体吞吐量之间的趋向关系:image

这个大概可以得出一个容量预估,比如你的服务用户量是多少,预估峰值QPS是多少,集群需要配置多少个实例(虽然实例的多少不能线性计算),可以大致推算出去。

2.2 基于内存实现

Redis的读写操作都是在内存中实现了,相对其他的持久化存储(如MySQL、File等,数据持久化在磁盘上),性能会高很多。因为在们在操作数据的时候,需要通过 IO 操作先将数据读取到内存里,增加工作成本。

image

上面那张图来源于网络,可以看看他的金字塔模型,越往上执行效率越高,价格也就越贵。下面给出每一层的执行耗时对比:

  • 寄存器:0.3 ns
  • L1高速缓存:0.9 ns
  • L2高速缓存:2.8 ns
  • L3高速缓存:12.9 ns
  • 主存:120 ns
  • 本地二级存储(SSD):50~150 us
  • 远程二级存储:30 ms 这样可能不直观,我们举个L1和SSD的对比,如果L1耗时1s的话,SSD中差不多要15~45小时。 因为 CPU 内部集成了内存控制器,所以CPU直接控制了内存,给予通信上的最优带宽。上面的部分数据引用自《性能之巅:洞悉系统、企业与云计算》。

2.3 适配多元场景的高效数据结构

在 Redis 缓存中,常用的主要数据类型有五种,如下:

  • 字符串/REDIS_STRING:适用于 缓存、计数、共享Session、IP统计、分布式锁等。
  • 列表/REDIS_LIST: 链表、消息队列、栈、有序的对象列表(如朋友圈的点赞顺序列表、评论顺序列表)。
  • 哈希表/REDIS_HASH: 购物车信息、用户信息、Hash类型的(key, field, value)存储对象等。
  • 集合/REDIS_SET:无序的唯一的键值结构: 好友、关注、粉丝、感兴趣的人集合等。
  • 有序集合/REDIS_ZSET:访问排行榜、点赞排行、粉丝数排行等。

上面这5种Redis 支持的数据类型,能够满足不同业务场景下的数据结构需求。而对于这几类数据类型的区分和支持,目的无非也是为了效率,具体的业务中使用恰当的数据结构才能保证得到应有的效率。

这5种数据类型都有一种或者多种数据结构来支撑,底层数据结构有 7 种。关系如下:image 限免我们对这些数据结构一个个的分析。

2.3.1 SDS 简单动态字符串

Redis使用简单动态字符串(simple dynamic string,SDS)来表示字符串,Redis中字符串类型包含的数据结构有:整数(R_INT) 、 字符串(R_RAW)。我们以字符串为例子,常规的字符串,如 "Brand",如果要获取他的长度,需要从头开始遍历,直至遇到 \0 空字符代表结尾,如 C字符串。

C 字符串结构与 SDS 字符串结构 对比图 参照如下:image

  • free属性的值为0,表示这个SDS没有分配任何未使用空间。
  • len属性的值为5,表示这个SDS保存了一个5字节长度的字符串。
  • buf是一个char类型的数组,存储真实的字符串,数组的前五个字节分别保存了'B'、'r'、'a'、'n'、'd'五个字符,而最后一个字节则保存了空字符'\0',代表结尾。 注意:SDS遵循C字符串的惯例以空字符结尾,保存空字符的1字节不计算在SDS的len属性中。

比起C字符串,SDS具有以下优点:

  1. 度获取字符串长度时间复杂度为O(1) 。 C字符串不记录自身长度,获取C字符串长度时必须遍历整个字符串计数得到,复杂度是O(N) SDS字符串自身记录维护len长度属性,获得SDS字符串长度的复杂度是O(1)

  2. 杜绝缓冲区溢出。 C字符串不记录长度,由于两个C字符串在内存存储上紧邻,在执行字符串拼接strcat时,如果不提前分配足够空间,很可能发生修改s1的数据溢出到s2所在的空间中(缓冲区溢出)。 SDS杜绝了缓冲区溢出问题,它记录了长度,当修改SDS字符串之前,API都会检查SDS的空间是否满足修改的要求,不满足API会自动进行空间扩展

  3. 空间预分配,减少修改时的内存重分配次数 SDS 被修改后,程序不仅会为 SDS 分配所需要的空间,还会分配额外的未使用空间。这样,Redis可以减少连续执行字符串增长操作所需的内存重分配次数。 具体分配未使用空间如下2种方式:

  • 如修改后长度len小于1MB,就分配和len属性相同大小的未使用空间:free=len
  • 如修改后长度len大于等于1MB,就分配1M的未使用空间:free=1MB
  1. 惰性空间释放 惰性空间释放,缩短操作时:SDS避免了缩短字符串时所需的内存重分配操作,并为将来可能有的增长操作提供了优化。当SDS做缩短操作,不会立刻使用内存重分配来收回缩短后多出来的字节,而是保持在free属性里。将来如果需要 append 操作,则直接使用 free 中未使用的空间,减少了内存的分配步骤。 另外,SDS也提供了API手动进行释放SDS未使用空间,避免惰性释放策略会造成内存浪费。

  2. 二进制安全 C字符串的字符必须符合某种编码,除结尾空字符以外,字符串内部不允许有空字符串,存储有局限性。而在 Redis 中,不仅可以存储 String 类型的数据,也可能存储一些二进制数据。 二进制数据并不是规则的字符串格式,其中会包含一些特殊的字符如 '\0'。在 C 中遇到 '\0' 则表示字符串的结束,但SDS不是,它是以len长度标识结尾。

  3. 兼容部分C字符串函数。 SDS虽然是二进制安全的,但还是秉承C字符串以空字符结尾的特性,很多函数与C字符串一致不需要重写。

2.3.2 zipList 压缩列表

通过上面的数据结构关系图,可以看出,压缩列表是 List 、Hash、 Set 三种数据类型底层实现之一。 当我们的list列表数据量比较少的时候,且存储的数据轻量的(如小整数值、短字符串)时候, Redis 就会通过压缩列表来进行底层实现。ziplist 是由一系列特殊编码的连续内存块组成的顺序型的数据结构,在列表头有三个字段 zlbytes、zltail 和 zllen,列表中有多个entry,表尾还有一个 zlend,我们来具体拆解下:

  • zlbytes:表示列表占用字节数
  • zltail:列表尾的偏移量
  • zllen:列表尾的偏移量:列表中的 entry 个数
  • entry:存储区,可以包含多个节点,每个节点可以存放整数或者字符串。
  • zlend:表示列表结束。

参考代码如下:

struct ziplist<T> {
    // 列表占用字节数
    int32 zlbytes;
	// 列表尾的偏移量,用于快速定位到最后一个节点
    int32 zltail_offset; 
	// 列表entry元素个数
    int16 zllength; 
	// 元素内容列表
    T[] entries; 
	// 标志压缩列表的结束,值恒为 0xFF
    int8 zlend; 
}

image 如果查找定位首个元素或最后1个元素,可以通过表头zlbytes、zltail_offset元素快速获取,复杂度是 O(1)。但是查找其他元素时,就没有这么高效了,只能逐个查找下去,比如 entry n 的复杂度就是 O(N)。

Redis 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;

Redis 的链表实现的特性可以总结如下:

  • 双端:链表节点带有 prev 和 next 指针,获取某个节点的前一节点和后一节点的复杂度都是 O(1)。
  • 无环:表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问以 NULL 为终点。
  • 表头指针/表尾指针:通过 list 结构的 head 指针和 tail 指针,获取链表的表头节点和表尾节点的复杂度为 O(1)。
  • 链表长度计数器:通过 list 结构的 len 属性来对 list 的链表节点进行计数,获取节点数量的复杂度为O(1)。
  • 多态:链表节点使用 void* 指针来保存节点值,并通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。 使用链表的附加空间相对太高,因为64bit系统中指针是8个字节,所以prev和next指针需要占据16个字节,且链表节点在内存中单独分配,会加剧内存的碎片化,影响内存管理效率。 考虑到链表的以上缺点,Redis后续版本对列表数据结构进行改造,使用quicklist代替了ziplist和linkedlist。 作为ziplist 和 linkedlist 的混合体,它将 linkedlist 按段切分,每一段使用 ziplist 来紧凑存储,多个 ziplist 之间使用双向指针串接起来。image 这样,性能就的得到了更大的提升。

2.3.4 Hhash 字典

无论何种类型(string、list、hash、set、zset),Redis都是以一个Hash结构的形式来保存键值对的。整体是一个数组,数组中的每个元素都是一个独立的对象,被称为哈系桶,比如图中1 ~ n, 对应的entry保存着实际具体值的指针。image 上图中的全局哈希表,它的时间复杂度是 O(1),只需要计算每个键的哈希值,便知道对应的哈希桶位置,定位桶中的 entry ,并找到对应数据。这个执行效率就很高了。 为了解决可能存在的冲突,采用了链式哈希的做法,也就是同一个桶里面的元素使用链表保存。

2.3.5 intset 整数集合

如果你的集合只有整数值元素,并且数量是轻量的,这时候Redis会使用使用整数集合作为Redis集合的底层数据结构。参考如下代码:

typedef struct intset{
     // 编码格式
     uint32_t encoding;
     // 集合中的元素个数
     uint32_t length;
     // 保存元素数据
     int8_t contents[];
} intset;

我们拆解下:

  • encoding: 编码方式
  • length: 数组中元素个数,也就是数组的整体长度
  • contents[]: 整数集合,集合的每个元素都是数组的一个数组项(item)。具有以下特点:
    • 按值的大小增序排列
    • 不包含任何重复项

2.3.6 skipList 跳跃表

skiplist(即跳跃表)是一种有序数据结构,所以它也是ZSet数据类型中的一种,通过在每个节点中维持多个指向其他节点的指针,达到快速定位的目标。 跳跃表的平均的节点搜索,平均时间复杂度是 O(logN)、最差时间复杂度是 O(N),还可以通过顺序性操作来批量处理节点。 跳跃表是基于链表的改良,在它基础上,增加了多层级索引,通过索引不断跳转,最终定好位到真实的数据项。这个方式是不是让大家想到b+tree,理念上有点接近,如下图所示:image 可以看出,需要获取 68 这个元素需要经历3次查找,需要获取 97则需要经历4次查找。

2.4 单线程模型

Redis 的单线程主要是指Redis的网络IO和键值对读写是由一个线程来完成的,Redis在处理客户端的请求时包括获取 (socket 读)、解析、执行、内容返回 (socket 写) 等都由一个顺序串行的主线程处理,这就是所谓的“单线程”。这也是Redis对外提供键值存储服务的主要流程。 但Redis的其他功能, 比如持久化、异步删除、集群数据同步等等,其实是由额外的线程执行的。 可以这么说,Redis工作线程是单线程的。但是,整个Redis来说,是多线程的

2.4.1 为何是单线程?

那在主流程中使用单线程,主要是出于什么原因呢?

  • 整体吞吐量降低 适当的扩增线程,是为了有效的利用cpu的性能,让它跟内存达到一个利用的最优值。但频繁的Redis读写,如果没有对线程进行有效管理,不但对系统的吞吐量没有提升,反而可能导致下降。image

  • CPU上下文切换 在运行任务的时候,CPU需要把任务加载到CPU寄存器中进行计算,当切换到其他thread时,需要将当前上下文存储在系统内核中,以便后续重新执行计算时再次加载。 就像你做专心做一件事时,频繁切换,频繁被打断,这个代价是非常高的。image 如图中,切换上下文时,我们需要完成一系列工作,save context、switch、restore context等,这种操作越频繁越是耗费资源。

  • 共享资源的并发控制问题 引入了程序执行顺序的不确定性,带来了并发读写的一系列问题,增加了系统复杂度。同时可能存在线程切换、甚至加锁解锁、死锁造成的性能损耗。

  • 内存才是核心关注点 对于 Redis 框架来说, 主要的性能瓶颈是内存或者网络带宽,而非 CPU。

2.4.2 单线程的好处

  1. 避免线程创建过多导致的性能消耗,反而降低整体吞吐能力。
  2. 避免上下文切换引起的 CPU 额外的开销。
  3. 避免了线程之间的竞争问题,如加锁、解锁、死锁等,都会造成性能损耗。
  4. 无需额外考虑多线程带来的程序复杂度,代码更清晰,处理逻辑简单。

2.4.3 单线程是否有效利用CPU

官方这么说

大概意思是,Redis是完全的纯内存操作,执行速度是非常快的,CPU通常不会是瓶颈,因为大多数请求不会是CPU密集型的。参考 Redis真正的性能瓶颈在网络IO,也就是客户端和服务端之间的网络传输延迟,因此Redis选择了单线程的IO多路复用来实现它的核心网络模型。

2.5 I/O 多路复用模型

服务端网络编程常见的 I/O 模型有四种:同步阻塞IO(Blocking IO)、同步非阻塞IO(Non-blocking IO)、IO多路复用(IO Multiplexing)、异步IO(Asynchronous IO)。 Redis 采用的是 I/O 多路复用技术,并发的去处理连接,它的多路复用程序函数有 select、poll、epoll、kqueue。以 epoll (目前最新的也是最好的多路复用技术)函数为例,当客服端执行 read、write、accept、close 等操作命令时,它会将命令封装成一个个事件,然后利用 epoll 多路复用的特性来避免 I/O 阻塞。 下面我们看看普通 I/O 模型 和 Redis的 I/O 多路复模型的的区别,来分析Redis高频请求下如何保持高效执行。

2.5.1 普通 I/O 模型

先来看一下传统的阻塞 I/O 模型到底是如何工作的:当使用 read 或者 write 对某一个文件描述符(File Descriptor:FD)进行读写时,如果当前 FD 不可读或不可写,整个 Redis 服务就不会对其它的操作作出响应,导致整个服务不可用。 这也就是传统意义上的,也就是我们在编程中使用最多的阻塞模型:image 阻塞模型虽然开发中非常常见也非常易于理解,但是由于它会影响其他 FD 对应的服务,所以在需要处理多个客户端任务的时候,往往都不会使用阻塞模型。

2.5.2 I/O 多路复用

image多路 复用指的是:多个socket连接复用一个线程。这种模式下,内核不会去监视应用程序的连接,而是监视文件描述符。 当客户端发起请求的时候,会生成不同事件类型的套接字。而在服务端,因为使用了 I/O 多路复用技术,所以不是阻塞式的同步执行,而是将消息放入 socket 队列(参考下图的 I/O Multiplexing module),然后通过 File event Dispatcher 将其转发到不同的事件处理器上,如accept、read、send。image 综上,我们得出如下特性:

  • 单线程模式,内核持续监听 socket 上的连接及数据请求,一监听就交予Redis线程处理,达到单个线程处理多个I/O 流的效果。
  • epoll 提供了基于事件的回调机制。不同事件调用对应的事件处理器。Redis可以持续性的高效处理事件,性能同步提升。
  • Redis 不阻塞任一客户端发起的请求,所以可以同时和多个客户端连接并处理请求,聚币并发执行的能力。

3 高性能Redis总结

  • 基于内存实现,而非磁盘,大都是简单的存取操作,资源主要消耗在 IO 上,所以读取速度快。
  • 数据结构:基于不同业务场景的高效数据结构
    • 动态字符串(REDIS_STRING):整数(REDIS_ENCODING_INT)、字符串(REDIS_ENCODING_RAW)
    • 双端列表(REDIS_ENCODING_LINKEDLIST)
    • 压缩列表(REDIS_ENCODING_ZIPLIST)
    • 跳跃表(REDIS_ENCODING_SKIPLIST)
    • 哈希表(REDIS_HASH)
    • 整数集合(REDIS_ENCODING_INTSET)
  • 线程模型:Redis 的网络 IO 以及键值对指令读写是由单个线程来执行的,避免了不必要的contextswitch和竞选
  • I/O 模型:基于I/O多路复用模型,非阻塞的I/O模型
  • 恰单的数据编码:根据实际数据类型,选择合理的数据编码
  • Redis 本身是一个全局 哈希表,他的时间复杂度是 O(1),另外为了防止哈希冲突导致链表过长,执行 rehash 操作进行扩充,减少哈希冲突。
作者:|Hello-Brand|,原文链接: https://www.cnblogs.com/wzh2010/p/15886787.html

文章推荐

在项目中如何直接使用hystrix?

MySQL中读页缓冲区buffer pool

Go到底能不能实现安全的双检锁?

聊聊如何实现一个带幂等模板的Kafka消费者

drools中的条件 when

重新整理汇编—————寄存器的基本概念[二]

脚踏实地的Netty源码研究笔记(1)——开篇

kubeadm安装k8s 1.23.5

又一位大佬「归隐」,张勇卸任淘宝天猫董事长,管理者又该如...

盘点一个语音转换库

hikari连接池mysql连接空闲超8小时后自动断开问题

群晖下 gitea+drone+harbor实现CI/CD 发布到云服务器