Back

Redis的快与慢详解

Redis为何如此快以及它存在哪些慢操作

1、Redis是内存数据库,所有的操作都在内存中完成

2、高效的数据结构,键值对是按一定的数据结构进行组织的

Redis中的数据类型

Redis中的数据类型,也就是键值对中值的数据保存形式,包含String(字符串)、List(列表)、Hash(哈希)、Set(集合)、Sorted Set(有序集合)。

Redis中的数据结构

层数据结构一共有 6 种,分别是:简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

关于Redis中五种数据类型的底层实现:

1、String:简单动态字符串

2、List:双向链表、压缩列表

3、Hash:压缩列表、哈希表

4、Sorted Set:压缩列表、跳表

5、Set:哈希表、整数数组

其中String类型只有一种底层实现,其他四种都有两种底层实现,List、Hash、Sorted Set、Set这四种也被称为集合类型,也就是一个键对应了一个集合的数据。

Redis的键和值是如何关联的?

1、Redis使用了一个哈希表来保存所有的键值对,来实现键和值的快速访问。

2、一个哈希表,其实就是一个数组,数组的每个元素称为一个哈希桶,每个哈希桶中保存了键值对数据。

需要注意的是哈希桶中的元素保存的并不是值本身,而是指向具体值的指针。不管是String还是集合类型,哈希桶中的元素都是指向它们的指针。

img

哈希桶中键和值之间的结构组织

  • a:Redis使用一个哈希表保存所有键值对,一个哈希表实则是一个数组,数组的每个元素称为哈希桶。
  • b:哈希桶中的元素保存的不是值的本身,而是指向具体值的指针

哈希冲突问题

全局哈希表中保存了所有的键值对,哈希表的最大好处很明显,就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值,就可以知道它所对应的哈希桶位置,然后就可以访问相应的 entry 元素。

查找过程主要依赖于哈希计算和数据量的多少没有直接关系,但是当数据量增大时Redis会突然变慢。这主要是由于,哈希表的冲突问题和 rehash 可能带来的操作阻塞。

哈希冲突

哈希冲突是指,两个 key 的哈希值和哈希桶计算对应关系时,正好落在了同一个哈希桶中。

Redis通过链式哈希解决哈希冲突问题,其中链式哈希是指 同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接

img

当数据越来越多时,就会使得哈希冲突链过长,进而导致链上的元素查找时耗时,效率低。

所以Redis采用了rehash操作,rehash就是增加现有的哈希桶的数量,分散entry元素,减少单个桶中的元素数量。

rehash机制

为了使rehash操作更高效,Redis默认使用了两个全局的哈希表,哈希表1和哈希表2,刚插入数据时默认使用哈希表1,哈希表2中没有被分配空间。

当数据量增多时,Redis分三步来执行rehash:

1、给哈希表2分配更大的空间,例如是当前哈希表1大小的两倍

2、把哈希表1中的数据重新映射并拷贝到哈希表2中

3、释放哈希表1中的空间

用增大的哈希表 2 保存更多数据,而原来的哈希表 1 留作下一次 rehash 扩容备用。

rehash过程中产生的问题:数据迁移过程中涉及到大量的数据拷贝,如果一次性将哈希表1中的数据全部迁完,这将会阻塞Redis线程,使其无法服务其他的请求。

为了避免这个问题,Redis采用了渐进式rehash

渐进式rehash

渐进式rehash是指将集中迁移数据改为每当处理一个请求时就从哈希表1中的第一个索引位置开始,顺带将这个索引位置上的所有的entries拷贝到哈希表2中,等处理下一个请求时,再将哈希表1中的下一个索引位置的entries拷贝到哈希表2中。

注意:

于 String 类型来说,找到哈希桶就能直接增删改查了,但是,对于集合类型来说,即使找到哈希桶了,还要在集合中再进一步操作。

集合类型的底层数据结构和操作复杂度

整数数组和双向链表也很常见,它们的操作特征都是顺序读写,也就是通过数组下标或者链表的指针逐个元素访问,操作复杂度基本是 O(N),操作效率比较低;压缩列表和跳表我们平时接触得可能不多,但它们也是 Redis 重要的数据结构。

压缩列表:类似于数组,其中的每一个元素都对应保存一个数据,和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。

img

操作复杂度为O(1)或O(N)

跳表:表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位。数据量大时操作复杂度为O(logN)

img

复杂度四句口诀:

单元素操作是基础

范围操作非常耗时

统计操作通常高效

例外情况只有几个

一、单元素操作,是指每一种集合类型对单个数据实现的增删改查操作。例如,Hash 类型的 HGET、HSET 和 HDEL,Set 类型的 SADD、SREM、SRANDMEMBER 等

需要注意的是当这些命令对多个元素进行操作时,操作复杂度由元素个数决定

二、范围操作是指集合类型的遍历操作,可以返回集合中的所有数据。例如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS,操作复杂度一般为O(N),比较耗时,我们应该尽量避免。

扩展:Redis 从 2.8 版本开始提供了 SCAN 系列操作(包括 HSCAN,SSCAN 和 ZSCAN),这类操作实现了渐进式遍历,每次只返回有限数量的数据

三、统计操作,集合类型对集合中所有元素个数的记录。例如 LLEN 和 SCARD。这类操作复杂度只有 O(1)。

四、例外情况,例如压缩列表和双向列表都会记录表头和表尾的偏移量,对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说,它们是在列表的头尾增删元素,复杂度为O(1)

Redis的高性能IO模型

Redis是单线程的为什么这么快?

Redis是单线程的,主要是指Redis的网络IO和键值对读写是由一个线程来完成的,这也是Redis对外提供键值存储服务的主要流程。

Redis的其他服务比如持久化、异步删除、集群数据同步等其实是由额外的线程执行的。

严格来说Redis并不是单线程

Redis采用单线程的原因

多线程开销问题:在合理的资源分配的情况下,多线程可以增加系统中处理请求操作的实体资源,进而提升系统能够同时处理的请求数(吞吐率),但是实际情况是当刚开始增加线程数时,系统吞吐率会增加,但是再增加线程时,系统吞吐率会增长缓慢甚至下降。

原因是系统中通常会存在被多线程同时访问的共享资源,比如一个共享的数据结构,这时候为了保证数据的正确性,就会带来额外的开销。

以上问题也称为多线程编程模式面临的共享资源的并发访问控制问题。

Redis使用单线程快的原因

1、在内存中操作加上使用了高效的数据结构

2、使用了多路复用机制,可以并发处理大量的客户端请求,实现高吞吐率

首先,我们要弄明白网络操作的基本 IO 模型和潜在的阻塞点。毕竟,Redis 采用单线程进行 IO,如果线程被阻塞了,就无法进行多路复用了。

基本的IO模型和阻塞点

服务端为了处理客户端的请求,需要监听客户端请求(bind/listen)和客户端建立连接(accpet),从socket读取请求(recv)解析客户端发送请求(parse),根据请求读取键值数据(get),最后给客户端返回结果,即向socket中写回数据(send)

img

在网络IO操作中存在潜在的阻塞点分别是accept()和 recv(),也就是当Redis监听到客户端有连接请求但是一只未能成功建立连接时,就会阻塞在accept()函数里,进而导致其他的客户端无法与Redis建立连接。

同样,当Redis通过recv()从客户端获取数据时,如果数据一直没有到达,Redis也会一直阻塞在recv()上。

以上就是关于网络请求中基本的IO模型和潜在的阻塞点

socket网络模型支持的非阻塞模式

在 socket 模型中,不同操作调用后会返回不同的套接字类型。socket() 方法会返回主动套接字,然后调用 listen() 方法,将主动套接字转化为监听套接字,此时,可以监听来自客户端的连接请求。最后,调用 accept() 方法接收到达的客户端连接,并返回已连接套接字。

针对监听套接字,我们可以设置非阻塞模式:当 Redis 调用 accept() 但一直未有连接请求到达时,Redis 线程可以返回处理其他操作,而不用一直等待。

但是,你要注意的是,调用 accept() 时,已经存在监听套接字了。虽然 Redis 线程可以不用继续等待,但是总得有机制继续在监听套接字了。

虽然 Redis 线程可以不用继续等待,但是总得有机制继续在监听套接字上等待后续连接请求,并在有请求时通知 Redis。

同样也可以对已连接套接字设置非阻塞模式:Redis调用recv()后,如果已连接套接字上一直没有数据到达,Redis线程可以先处理其他的请求操作。

我们需要有机制去监听这些套接字,并在有数据到达时去通知Redis

这些机制就例如Linux中的IO多路复用机制

基于多路复用的高性能I/O模型

Linux中的IO多路复用机制是指一个线程处理多个IO流,也就是select/epoll机制。

在Redis只运行单线程的情况下,该机制允许内核中,同时存在多个监听套接字和已连接套接字。内核会一直监听这些套接字上的连接请求或数据请求。一旦有请求到达,就会交给 Redis 线程处理,这就实现了一个 Redis 线程处理多个 IO 流的效果。

FD代表多个套接字

Redis网络框架调用epoll机制,让内核监听这些套接字,此时Redis线程不会阻塞在某个特定的监听或者已连接套接字上(不会阻塞在客户端请求处理上),因此Redis可以同时和多个客户端连接并处理请求,从而提升了并发性。

img

select/epoll 提供了基于事件的回调机制,即针对不同事件的发生,调用相应的处理函数。

从而实现在请求到达时能够通知到Redis线程。

回调机制是如何工作的?select/epoll 一旦监测到 FD 上有请求到达时,就会触发相应的事件。

这些事件会被放进一个事件队列,Redis 单线程对该事件队列不断进行处理。这样一来,Redis 无需一直轮询是否有请求实际发生,这就可以避免造成 CPU 资源浪费。同时,Redis 在对事件队列中的事件进行处理时,会调用相应的处理函数,这就实现了基于事件的回调。因为 Redis 一直在对事件队列进行处理,所以能及时响应客户端请求,提升 Redis 的响应性能。

举例:医院分诊台的例子。

总结

本篇文章主要是介绍了Redis的数据结构和单线程的Redis为什么这么快的原因。主要内容包含Redis的键值对是如何关联的、哈希冲突问题和解决方案,rehash机制、渐进式rehash、集合类型的底层数据结构和操作复杂度、Redis的高性能网络IO模型、Redis基于Linux的多路复用机制来实现非阻塞模式等。

Built with Hugo
Theme Stack designed by Jimmy
© Licensed Under CC BY-NC-SA 4.0