Redis的存储原理和数据模型

ops/2024/9/23 2:41:24/

一、Redis是单线程还是多线程呢?

        我们通过跑redis的代码,查看运行的程序可以得知,Redis本身其实是个多线程,其中包括redis-server,bio_close_file,bio_aof_fsync,bio_lazy_free,io_thd_*,jemalloc_bg_thd等过程,其中的io_thd_*就是多线程的意思,包含多个接收io的线程。

        但是我们常说的Redis是单线程是什么意思呢?其实是说的是Redis在处理我们发送的命令是单线程的。也就意味着有前后顺序。

二、命令处理为什么是单线程?

        首先我们需要了解一下单线程的局限性:如果在单线程中碰到了一些耗时操作,比如cpu的大量计算和阻塞等待的io处理,那么整个线程就会被阻塞等待,大大降低效率,这样对Redis而言就会影响性能。

        那么针对这些问题,Redis有没有相关的处理方式,比如io密集型,cpu密集型。

1、io密集型

        磁盘io:对于 fork 进程,在子进程中持久化,我们通过异步刷盘来处理。

        网络io:对于服务多个客户,造成io密集型的话,我们采用reactor网络模型来处理。而对于数据请求或返回数据量比较大的话,我们需要开启io多线程来处理。

2、cpu密集型

在Redis中我们采用分治的方式数据结构切换渐进式数据迁移

分治的方式:将一个大的问题分成多个小问题进行处理。对于一个操作时间长的问题,我们将一段一段的进行处理。

数据结构的切换:在Redis中含有五种类型的结构,在每一种的结构中还有更小的结构,我们根据不同的情况使用这一不同的小结构,使效率最快。

渐进式数据迁移:类似于分治的第二种。

        那么为什么不采用多线程处理呢?由于我们含有五种数据类型,而且每种类型由多个数据结构实现,这样使我们加锁变得复杂,并且加锁粒度不好控制。那么使用单线程就可以避免多线程间频繁的上下文切换,减少线程切换额外带来的开销,从而提高处理速度。下面会讲解。

三、对象编码

        下面的图片中,共有五种数据类型:string,list,hash,set,zset。其中每一个类型都含有不同的数据结构,Redis会根据不同的情况选出不同的数据结构的。

        跳表:就是多层级的链表,一层一层的搜索,将时间复杂度降低到和二分查找一个速度。理想跳表下,可以模拟出二叉树的结构,和二叉树一个搜索速度(空间换时间)。但是这种情况需要重构,重构的时间太长。因此实现Redis的跳表:从节约内存出发,可以让这个结构更加扁平,把二叉堆变成四叉堆。

四、单线程为什么这么快?

1、采用了哪些机制

内存数据库:Redis数据库是内存数据库,是将数据直接存储到内存中的,这样的读取速度比存储在磁盘中的速度提高了近10倍。

数据组织方式:Redis是一个KV类型的,Redis把这一对直接放到hashtable里面。下面会着重讲解。

数据结构高效:多种数据结构,可以来回切换,使效率和占用内存保持平衡。

2、hashtable 

        在数据组织方式中使用了hashtable,我们所有的数据都是存放在这个里面。由于Redis存储是KV存储,我们根据K这个值来进行选定位置。对于使用了hash表,我们每次的set和get之前都要对这个Key值进行hash,对于一样的Key值,我们hash出来肯定是一样的,所以我们就可以做到O(1)的时间复杂度。

        但是当我们开辟出来的空间使用完毕,那么我们就会出现hash冲突,比如一共六个位置,这六个位置全部有数据了,那么我们再添加一个数据,此时这个数据肯定要发生hash冲突,当一个坑位中出现n个结点的时候,那么我们的查找速度就从O(1)降到O(n)。对于这种情况,我们需要进行扩容。

        负载因子 = used / size ; used是数组存储元素的个数,size是数组的长度。负载因子越小,冲突越小,负载因子越大,冲突越大。而redis的负载因子是1。

2.1、扩容

        当我们每个位置都已经满了还要插入数据,也就是负载因子>1 时,就需要进行扩容,并且是翻倍扩容。如果正在 fork (在 rdb、aof 复写以及 rdb-aof 混用情况下)时,会阻止扩容;但是此时若负载 因子 > 5 ,索引效率大大降低, 则马上扩容;

        扩容后我们的hash函数发生变化。hash(key) % size;那么我们hash后存储的位置可能发生变化。

2.2、缩容

        当我们的负载因子 < 0.1 则会发生缩容;缩容的规则是恰好包含used的2的n次方。举个例子:当存储的元素为9,那么包含该元素的为2的4次,也就是16。

2.3、渐进式rehash

        当我们扩缩容的时候,我们发现映射规则发生改变,因此需要重新进行hash,所以叫做rehash。

        当我们阅读Redis源码的时候,我们可以发现DB数据库中的hashtable是有两个哈希表的:ht[2](数组);默认情况下,Redis将数据存储在ht[0]中,那么为什么需要两个hashtable呢?

        我们在扩缩容之前是存放在ht[0]中的,当我们需要进行rehash时,我们就将数据存放在ht[1]中,当全部hash之后,我们就将ht[1]赋值给ht[0],将ht[1]置空。

        那为什么叫做渐进式rehash呢?因为当hashtable中的元素过多的时候,不能一次性rehash到ht[1]中去,这样就会一直占用redis,无法及时处理其他命令,所以需要渐进式rehash。

渐进的方法:1、分治思想。2、加入定时器

1、分治:我们每次rehash一个槽位,把这个操作放入到增删改查的后面去,一步一步的将全部数据转移到另一个哈希表中去。但是这种方法在数据很多的情况下有点慢。

2、定时器:我们在Redis不太忙的时候,弄一个定时器,每隔一段时间,执行一次rehash,每次最大执行一毫秒,每次步长为100个数组槽位。

处于渐进式rehash的时候,不会发生扩缩容。

3、数据结构高效

        我们在上面提到了很多的数据类型,比如string类型,在它的下面还有三种:int,raw,embstr。这三种用于分别存储不同类型的字符串。在这里有个面试题可以瞅一眼:为什么Redis中字符串选择64个字节作为分界线?为什么string类型中要以44为分界线?

        首先内存分配器都是按照大小为2的几次方(2,4,8,16,32,64....)进行分配的,同时cpu cache line(cpu缓存行)最小访问单位为64个字节,所以选择64个字节作为分界线。对于在string字符串中小于44字节选择embstr编码格式,大于44字节选择raw编码格式。其中embstr顾名思义就是嵌入式字符串,嵌入到redisObject中,而raw就是在redisObject中维持一个指向堆上的资源。

        我们通过查看存储string类型的源码可以发现是redisObject占据了16个字节,由于是64字节,所以需要sdshdr8(sdshdr8是Redis中用于表示简单动态字符串(SDS)的一个结构体类型)来存储,这里占用三个字节,这些全都是字符串的头部信息。因为string类型是一个二进制安全的字符串,但是为了兼容c的字符串库函数,字符串末尾要以'\0'作为分隔符,所以需要减去这一个长度。所以64-16-3-1 = 44。

4、做出优化

采用分治思想,把rehash进行分摊或者放入定时器中。然后将耗时阻塞的操作扔给其他线程处理。再然后对于不同的对象类型采用不同的数据结构实现。

五、redis的多线程工作原理

        对于大量的阻塞io和cpu计算,我们采用多线程工作的方法进行处理。下面的图就是redis的处理流程。

        当大量客户端连接上后,发送多个命令到服务端,我们的reactor服务器将这些任务分发到不同的线程中去。其中一次任务的处理流程是:read->decode->compute->encode->send。读取数据,解析,处理,加密,发送数据。具体的处理函数可以自行阅读源码。

         接下来让我们看看多线程是怎么运行的。下面这张图中的数组代表客户端发送来的任务。下面有四个线程,其中一个是主线程。我们还记得Redis处理任务是单线程,每个任务的处理都要走上面那幅图的流程。

        我们将任务分发给每个线程,让他们负责读数据,解析,加密,发送数据。而处理数据全部交给主线程进行处理。也就是说主线程只负责处理核心数据,而其他线程负责处理其他业务。

讲解完毕啦!https://github.com/0voice


http://www.ppmy.cn/ops/111748.html

相关文章

Kubernetes的3种数据持久化方式

Kubernetes的3种数据持久化方式 1. EmptyDir2. HostPath3. PersistentVolume (PV)💖The Begin💖点点关注,收藏不迷路💖 Kubernetes提供了几种数据持久化方式,以满足不同场景的需求: 1. EmptyDir 用途:临时数据存储,Pod内容器间共享。特点:生命周期与Pod相同,Pod删…

MySQl篇(数据类型)(持续更新迭代)

目录 常见类型一&#xff1a;数值类型 常见类型二&#xff1a;字符串类型 一、文本字符串类型 1. char & varchar 1.1. CHAR(M)类型 1.2. VARCHAR(M)类型 1.3. 两者应用 2. enum & set 二、二进制字符串类型 1. BINARY & VARBINARY类型 2. 二进制字符串和…

情感识别系统源码分享

情感识别检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vision …

Python3网络爬虫开发实战(14)资讯类页面智能解析

文章目录 一、详细页智能解析算法1.1 提取标题1.2 提取正文1.3 提取时间 二、列表页智能解析算法三、智能分辨列表页和详细页四、完整的库4.1 参考文献4.2 Project 页面智能解析就是利用算法从页面的 HTML 代码中提取想要的内容&#xff0c;算法会自动计算出目标内容在代码中的…

怎么去浮毛比较高效?热门除浮毛宠物空气净化器希喂、范罗士、有哈测评推荐

我朋友是呼吸科医生&#xff0c;他自己也养猫&#xff0c;成天成天的给我们那几个养宠物的朋友科普宠物毛发的各种危害。有人调侃他&#xff1a;“这么多危害&#xff0c;那你送出去别养了啊”。开玩笑&#xff0c;自己养大的猫跟亲生的有什么区别。看到还有蛮多朋友因为养宠物…

fuxa搭建与使用(web组态)

1. 安装Node.js -> npm安装 参考网址&#xff1a;https://blog.csdn.net/WHF__/article/details/129362462 一、安装运行 C:\WINDOWS\system32>node -v v20.17.0 C:\WINDOWS\system32>npm -v 10.8.2 二、环境配置 在安装路径&#xff08;D:\Program_Files\nodejs&a…

对目录的操作、获取文件信息

目录 一、目录操作 二、获取文件的相关信息 1、演示获取文件的相关信息 2、注意事项和细节 一、目录操作 需求&#xff1a; 1&#xff09;创建一级目录 d://aaa 2&#xff09;创建多级目录 d://bbb//ccc 3&#xff09;删除目录 d://aaa和d://bbb//ccc import os# 1&am…

计算机网络相关概念

名词解释&#xff1a; 1.ARPANET ARPANET&#xff08;Advanced Research Projects Agency Network&#xff09;是由美国国防部高级研究计划局&#xff08;ARPA&#xff09;在1969年启动的一个实验性计算机网络项目。它是世界上第一个分组交换网络&#xff0c;也是互联网的前身…