你不知道的Redis八-Redis底层数据结构解析

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
云解析 DNS,旗舰版 1个月
简介: 你不知道的Redis八-Redis底层数据结构解析

一、Redis存储的数据的数据结构


我们都只到Redis常用的数据结构为String,List,Hash,Set,Sorted Set。但这只是我们在用的时候键值对的表现形式,他们底层真正使用的数据结构为简单动态字符串,双向链表,压缩列表,哈希表,调表和整数数组

20201229140229711.png可以看到,String 类型的底层实现只有一种数据结构,也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型,都有两种底层实现结构。通常情况下,我们会把这四种类型称为集合类型,它们的特点是一个键对应了一个集合的数据


二、Redis中键和值得数据结构


1、redis键值的数据结构


因为redis本身要求获取速度快,那么时间复杂度肯定是O1,为了实现从键到值的快速访问,Redis 使用了一个哈希表来保存所有键值对。数据结构如下


20201229201917803.png

redis是由一个全局hash表存储所有键和值得关系。值存的为对象的地址。


2、hash冲突


既然使用hash表,那么就肯定会有hash冲突。Redis 解决哈希冲突的方式,和JAVA中的hash表解决方式一样,也是链式哈希。链式哈希也很容易理解,就是指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。


2020122920124886.png因此当Key特别大的时候,存在着链式查找的一个时间消耗。特别是当我们存在几千万key的时候,那这个时间消耗也是非常多的


3、rehash阻塞


为了解决hash冲突带来的链表长度太长,因此redis引入对hash的rehash操作

rehash 也就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突。


20201229202458744.png


具体操作


Redis 默认使用了两个全局哈希表:哈希表 1 和哈希表 2。一开始,当你刚插入数据时,默认使用哈希表 1,此时的哈希表 2 并没有被分配空间。随着数据逐步增多,Redis 开始执行 rehash,这个过程分为三步:


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


2、把哈希表 1 中的数据重新进行打散映射到hash表2中;


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


我们就可以从哈希表 1 切换到哈希表 2,用增大的哈希表 2 保存更多数据,而原来的哈希表 1 留作下一次 rehash 扩容备用


这个过程看似简单,但是第二步涉及大量的数据拷贝,如果一次性把哈希表 1 中的数据都迁移完,会造成 Redis 线程阻塞,无法服务其他请求。此时,Redis 就无法快速访问数据了。


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


4、渐进式rehash


简单来说就是在第二步拷贝数据时,Redis 仍然正常处理客户端请求,每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中;等处理下一个请求时,再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示:


这样就巧妙地把一次性大量拷贝的开销,分摊到了多次处理请求的过程中,避免了耗时操作,保证了数据的快速访问。


二、压缩列表


之前也说了,集合类型的底层数据结构主要有 5 种:整数数组、双向链表、哈希表、压缩列表和跳表。其中,哈希表刚才已经讲过,整数数组、双向链表也比较常见。那么我们具体看下压缩列表和跳表


20201230112957991.png



zlbytes:记录压缩列表占用的内存字节数,对压缩列表进行内存重分配或者计算zlen位置时使用,占用4个字节


Zltail:记录也锁列表未节点距离压缩列表的起始节点有多少字节,通过这个偏移量,程序无需便利整个压缩列表就可以确定表尾节点的位置 占用4个字节


Zllen:记录列表包含的节点数量,占用2个字节


Zllend:记录压缩列表的末端,占用1个字节


entry:压缩列表保存的数据,主要有以下属性


  • prev_len,表示前一个 entry 的长度。prev_len 有两种取值情况:1 字节或 5 字节。取值 1 字节时,表示上一个 entry 的长度小于 254 字节。虽然 1 字节的值能表示的数值范围是 0 到 255,但是压缩列表中 zlend 的取值默认是 255,因此,就默认用 255 表示整个压缩列表的结束,其他表示长度的地方就不能再用 255 这个值了。所以,当上一个 entry 长度小于 254 字节时,prev_len 取值为 1 字节,否则,就取值为 5 字节。
  • len:表示自身长度,4 字节;
  • encoding:表示编码方式,1 字节;
  • content:保存实际数据。


如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了。


三、跳表


有序链表只能逐一查找元素,导致操作起来非常缓慢,于是就出现了跳表。具体来说,跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位。

20190701193147288.png

如果我们使用上图所示的跳跃表,就可以减少查找所需时间为O(n/2),因为我们可以先通过每个节点的最上面的指针先进行查找,这样子就能跳过一半的节点。


比如我们想查找50,首先和20比较,大于20之后,在和40进行比较,然后在和70进行比较,发现70大于50,说明查找的点在40和50之间,从这个过程中,我们可以看出,查找的时候跳过了30。


跳跃表其实也是一种通过“空间来换取时间”的一个算法,令链表的每个结点不仅记录next结点位置,还可以按照level层级分别记录后继第level个结点。此法使用的就是“先大步查找确定范围,再逐渐缩小迫近”的思想进行的查找。跳跃表在算法效率上很接近红黑树。


四、Redis数据结构时间复杂度


a7941fced8c143d9ee78061c5853347b.png

五、Redis使用建议


第一,对于单元素操作,对于redis的使用尽量使用单元素操作。这种效率一般都比较高。


第二,范围操作,是指集合类型中的遍历操作,可以返回集合中的所有数据,这类操作一般都比较耗时,尽量避免


第三,统计操作,是指集合类型对集合中所有元素个数的记录,因为这些数据结构本身记录所有元素个数,时间复杂度为O(1)所以效率很高


第四,例外情况,是指某些数据结构的特殊记录,例如压缩列表和双向链表都会记录表头和表尾的偏移量。对于头插和尾插增删元素可以通过偏移量直接定位,所以时间复杂度也是O(1)。实现快速操

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
2月前
|
缓存 NoSQL Java
Redis深度解析:解锁高性能缓存的终极武器,让你的应用飞起来
【8月更文挑战第29天】本文从基本概念入手,通过实战示例、原理解析和高级使用技巧,全面讲解Redis这一高性能键值对数据库。Redis基于内存存储,支持多种数据结构,如字符串、列表和哈希表等,常用于数据库、缓存及消息队列。文中详细介绍了如何在Spring Boot项目中集成Redis,并展示了其工作原理、缓存实现方法及高级特性,如事务、发布/订阅、Lua脚本和集群等,帮助读者从入门到精通Redis,大幅提升应用性能与可扩展性。
60 0
|
8天前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
6天前
|
存储 缓存 NoSQL
Redis 过期删除策略与内存淘汰策略的区别及常用命令解析
Redis 过期删除策略与内存淘汰策略的区别及常用命令解析
13 0
|
2月前
|
存储 监控 NoSQL
redis数据结构-HyperLogLog
redis数据结构-HyperLogLog
34 1
|
2月前
|
存储 NoSQL 数据处理
redis数据结构-Bitmaps
redis数据结构-Bitmaps
30 0
|
2月前
|
存储 缓存 NoSQL
redis数据结构-hash
redis数据结构-hash
11 0
|
2月前
|
监控 网络协议 Java
Tomcat源码解析】整体架构组成及核心组件
Tomcat,原名Catalina,是一款优雅轻盈的Web服务器,自4.x版本起扩展了JSP、EL等功能,超越了单纯的Servlet容器范畴。Servlet是Sun公司为Java编程Web应用制定的规范,Tomcat作为Servlet容器,负责构建Request与Response对象,并执行业务逻辑。
Tomcat源码解析】整体架构组成及核心组件
|
2月前
|
存储 NoSQL Redis
redis 6源码解析之 object
redis 6源码解析之 object
58 6
|
22天前
|
存储 缓存 Java
什么是线程池?从底层源码入手,深度解析线程池的工作原理
本文从底层源码入手,深度解析ThreadPoolExecutor底层源码,包括其核心字段、内部类和重要方法,另外对Executors工具类下的四种自带线程池源码进行解释。 阅读本文后,可以对线程池的工作原理、七大参数、生命周期、拒绝策略等内容拥有更深入的认识。
什么是线程池?从底层源码入手,深度解析线程池的工作原理
|
26天前
|
开发工具
Flutter-AnimatedWidget组件源码解析
Flutter-AnimatedWidget组件源码解析

热门文章

最新文章

推荐镜像

更多
下一篇
无影云桌面