Redis篇--数据结构篇8--Redis数据结构架构篇(全局键空间,key存储结构,值存储结构,对象头)

ops/2024/12/19 6:14:02/

Redis是一个高效的内存数据库,它的内部实现非常精巧,使用了多种数据结构来优化不同场景下的性能。

1、Redis的键(Key)存储结构

在Redis中,所有的键(Key)都是通过字典(Dictionary)形式来存储的,而字典的底层实现是哈希表(Hash Table)。

1.1、全局键空间(Global Key Space)

全局键空间(Global Key Space),也可以叫全局哈希表。在Redis中,所有的键(Key)都存储在一个全局哈希表(Hash Table)中。这个哈希表用于将键映射到对应的值。

Redis中的每一个数据都会包含键(Key)和值(Value)。

  • 键(Key):每个键是一个字符串,用于唯一标识一个唯一的值。
  • 值(Value):值可以是多种类型的数据结构,如字符串、列表、集合、哈希表、有序集合等。

当存储一个Hash类型的值时,Redis会先根据key在全局哈希表中找到该键的位置。之后在该位置上创建一个新的子哈希表(或压缩列表)来存储Hash对象的元素。

1.2、全局哈希表的作用

  • 快速查找:全局哈希表提供了O(1)的平均时间复杂度,使得Redis可以快速查找、插入和删除键。

  • 动态扩展:全局哈希表可以根据需要动态扩展或收缩,确保在不同负载下都能保持高效的性能。

  • 渐进式rehash:为了避免哈希表扩展或收缩时阻塞主线程,Redis实现了渐进式rehash,逐步将旧哈希表中的元素迁移到新哈希表中。

1.3、概念介绍

- 字典(Dictionary):Redis使用字典来存储键值对。字典是一个键到值的映射结构,支持快速查找、插入和删除操作。

- 哈希表(Hash Table):字典的底层实现是哈希表。每个哈希表由多个桶(bucket)组成,每个桶可以存储多个键值对。为了减少哈希冲突,Redis使用了拉链法(Separate Chaining),即当多个键的哈希值相同(发生冲突)时,它们会被存储在一个链表中。

- 渐进式 rehash:为了应对哈希表扩展或收缩时的性能问题,Redis实现了渐进式rehash。当哈希表需要扩容或缩容时,Redis不会一次性完成rehash操作,而是逐步将旧哈希表中的元素迁移到新哈希表中,从而避免阻塞主线程。

1.4、为什么全局键空间使用哈希表?

  • 快速查找:哈希表提供了O(1)的平均时间复杂度,适合频繁的查找操作。
  • 动态扩展:哈希表可以根据需要动态扩展或收缩,确保在不同负载下都能保持高效的性能。

2、Redis的值(Value)存储结构

2.1、字符串(String)

Redis的字符串是最基本的数据类型,底层实现有两种编码方式:

- raw编码:对于较长的字符串(通常超过44字节),Redis使用raw编码。raw编码的字符串是基于简单动态字符串(SDS,Simple Dynamic String)实现的。
SDS是Redis自己实现的字符串库,它比C语言的char更加高效和安全,支持动态扩展和长度记录。

- embstr编码:对于较短的字符串(通常小于44字节),Redis使用embstr编码。embstr编码将键和值一起存储在同一个分配的内存块中,减少了内存碎片化,并且在创建和销毁时更加高效。

2.2、列表(List)

Redis的列表有两种底层实现方式:

- ziplist编码:对于较短的列表(元素数量较少且元素本身较短),Redis使用ziplist编码。ziplist是一种压缩列表结构,它可以将多个小元素紧凑地存储在一起,减少内存开销。
ziplist的优点是节省内存,但缺点是操作效率较低,尤其是当列表变长时。

- linkedlist编码:对于较长的列表(元素数量较多或元素本身较长),Redis使用linkedlist编码。linkedlist是基于双向链表实现的,支持高效的插入和删除操作,但会占用更多的内存。

2.3、集合(Set)

Redis的集合也有两种底层实现方式:

- intset编码:对于只包含整数的集合,Redis使用intset编码。intset是一种有序整数集合,底层实现是数组。intset的优点是内存紧凑,查询速度快,但只能存储整数。

- hashtable编码:对于包含字符串或其他类型元素的集合,Redis 使用 hashtable 编码。hashtable 是基于哈希表实现的,支持高效的插入、删除和查找操作。

2.4、哈希表(Hash)

Redis的哈希表有两种底层实现方式:

- ziplist编码:对于较小的哈希表(字段数量较少且字段值较短),Redis使用ziplist编码。ziplist可以将多个键值对紧凑地存储在一起,减少内存开销。

- hashtable编码:对于较大的哈希表(字段数量较多或字段值较长),Redis使用hashtable编码。hashtable是基于哈希表实现的,支持高效的插入、删除和查找操作。

2.5、有序集合(Sorted Set)

Redis的有序集合有两种底层实现方式:

- ziplist编码:对于较小的有序集合(元素数量较少且元素本身较短),Redis使用ziplist编码。ziplist可以将多个元素紧凑地存储在一起,减少内存开销。

- skiplist编码:对于较大的有序集合(元素数量较多或元素本身较长),Redis使用skiplist编码。skiplist是一种跳跃表结构,支持高效的插入、删除和范围查询操作。跳跃表的时间复杂度为O(log N),适合处理大规模数据。

2.6、Redis的内存优化

为了提高内存利用率,Redis在不同场景下会根据数据的特点选择不同的编码方式。例如:

  • embstr编码:对于较短的字符串,Redis使用embstr编码,将键和值一起存储在同一个内存块中,减少内存碎片化。
  • ziplist编码:对于较小的列表、集合、哈希表和有序集合,Redis使用ziplist编码,将多个元素紧凑地存储在一起,减少内存开销。
  • intset编码:对于只包含整数的集合,Redis使用intset编码,利用数组的紧凑性来节省内存。
  • skiplist编码:对于较大的有序集合,Redis使用skiplist编码,确保在大规模数据下的高效操作。

3、实例场景理解

假设现在要往Redis中存储一个Hash类型的对象,如user1: {name: zhangsan}。

Redis具体的过程如下:

3.1、全局哈希表中查找位置

Redis首先会通过哈希算法在全局哈希表中查找该键key的位置。

3.2、查看位置的数据

找到键key的位置后,如果该位置已经是Hashtable结构,则直接在现有的Hash对象中处理新的字段;如果不是,则会先选择编码在创建一个新的Hash对象。

3.3、选择编码方式

如果该位置之前不存在对象。Redis会根据Hash对象的实际数据,选择合适的编码模式,在去创建对象。

  • 如果Hash对象的字段数量较少且字段值较短,Redis会使用ziplist编码来存储对象的字段和值。
  • 如果Hash对象的字段数量较多或字段值较长,Redis会使用hashtable编码。

3.4、创建Hash对象,插入hash值

确认了编码后,这里先假设是ziplist编码。Redis会在该位置上创建一个压缩列表,并将要存储的hash对象({name: zhangsan})的键和值插入到这个压缩列表中。

3.5、结构转换

当存储的Hash对象超出配置条件时(如:个数超过512,或存在大于64字节的value值),Redis会自动将ziplist转换为hashtable编码。这种转换是不可逆的,一旦被转换为hashtable编码,Redis不会再将其转换回ziplist编码。

Redis会使用ziplist编码条件,不满足其一则会转为hashtable:

  • 字段数量小于hash-max-ziplist-entries(默认 512)。
  • 每个字段和值的长度都小于 hash-max-ziplist-value(默认 64 字节)。

3.6、最终结构

该示例的最终结构:全局键哈希表结构中,该key的位置存储了一个子哈希表(或ziplist)。(即哈希表嵌套哈希表(或ziplist)的结构)。
实际最终结构:全局键哈希表结构中,每一个位置都可能是List,Set,Hash等结构中的一个实例结果。

4、查看数据的实际编码

可以使用DEBUG OBJECT或OBJECT ENCODING命令来查看数据的编码方式。
示例:
在这里插入图片描述
在这里插入图片描述

5、Redis键值对的内存分配

5.1、问题引入

先引入一个问题。设置key为aaa1,value为zhangsan1的数据,当查看其使用的内存大小,发现结果尽然是57个字节,是不是很意外?正常理解不应该是aaa1和zhangsan1加在一起是4+9=13字节吗?那Redis为什么会分配了57个字节呢?
示例如下:
在这里插入图片描述
查看key键值使用的内存命令:

MEMORY USAGE aaa1

5.2、对象头

在Redis中,每个键值对都由键(Key)和值(Value)两部分组成。每个键(Key)或每个值(Value)都有一个属于自己的对象头RedisHeader。每个对象头通常占用16字节左右。它不直接存储键或值的实际内容,而是提供了关于键或值的一些附加信息(如类型、编码、引用计数等)。
即:对于Redis的键或值的存储是使用不同的数据结构。而Redis会为每一个键或者值都创建一个对象头,记录key或者值的相关信息,通常占用16字节。

(1)、键(Key):每个键是一个字符串,用于唯一标识一个值。
(2)、值(Value):值可以是多种类型的数据结构,如字符串、列表、集合、哈希表、有序集合等。
(3)、RedisHeader包含以下字段

  • type:表示该值的数据类型(如string、list、set、hash、zset等)。
  • encoding:表示该值的具体编码方式(如raw、embstr、ziplist、linkedlist等)。不同的编码方式会影响内存的使用效率和操作性能。
  • refcount:表示该对象的引用计数。Redis使用引用计数来进行垃圾回收。当某个对象的引用计数为0时,Redis会释放该对象占用的内存。
  • lru:表示该对象的LRU(最近最少使用)时间戳,用于实现LRU淘汰策略。Redis会根据LRU时间戳来决定哪些对象可以被优先淘汰。

5.3、示例工作原理说明

假设我们有一个键aaa1和值zhangsan1,Redis的存储实现如下:

(1)、全局哈希表查找

  • Redis通过全局哈希表查找键aaa1的位置。如果键不存在,则在全局哈希表中创建一个新的条目。

(2)、创建key的对象头

  • 找到键aaa1的位置后,Redis会创建一个对象头来封装该键。这个对象头的type是string,encoding是embstr(因为aaa1这个键较短)。

(3)、创建value的对象头

  • Redis会创建另一个对象头来封装值zhangsan1。这个对象头的type也是string,encoding也是embstr(因为zhangsan1这个值较短)。

(4)、embstr编码的内存布局

  • 由于embstr编码将键和值一起存储在同一个分配的内存块中,Redis会在一次内存分配中为键和值分配足够的空间。这个内存块中包含了键和值的实际内容,以及它们的元数据(如类型、编码、引用计数等)。

(5)、哈希表的开销

  • 除了键和值的内存占用外,Redis还需要为哈希表的桶(bucket)分配内存。即使是一个非常小的哈希表,也会有一定的开销。

5.4、Redis内存使用的组成部分

当Redis存储一个键值对时,实际占用的内存不仅仅包括键和值本身,还包括以下几个方面的内存开销:

  • 键(Key)的内存开销:键的存储不仅包括键本身的字符串长度,还包括Redis内部用于管理键的数据结构(如embstr、SDS)。

  • 值(Value)的内存开销:值的存储不仅包括值本身的字符串长度,还包括Redis内部用于管理值的数据结构(如哈希表,双向链表等)。

  • 对象头:每个Redis对象的key和value都有一个对象头,用于存储对象的类型、编码方式等信息。对象头的大小取决于Redis的实现细节。

  • 分配器的对齐和碎片化:Redis使用内存分配器(如jemalloc或libc malloc)来管理内存。分配器可能会为了对齐或减少碎片化而分配比实际需要更多的内存。因此,实际分配的内存可能比理论上的最小值要大。

  • 内部数据结构的开销:Redis使用哈希表来存储键值对,哈希表本身也会占用一定的内存。

5.5、重新分析下示例中内存使用

(1)、键 aaa1:

  • 键的长度:4字节
  • 对象头:16字节
  • 哈希表的开销:不确定,但肯定有

(2)、值zhangsan1:

  • 值的长度:9字节
  • 对象头:16字节
  • embstr编码:将键和值一起存储,减少了内存碎片化,但实现还是SDS有内存消耗(记录长度,记录空间等开销)。

(3)、内存对齐和分配器的影响:
由于jemalloc的最小分配单元是16字节。因此,即使键和值的总长度只有13字节(4字节的键 + 9字节的值),jemalloc也会至少分配16字节的内存。

所以,应该开辟的内存大小=两个头对象(16*2)+embstr存储数据(至少16)+哈希表的开销(不确定)+SDS开销(至少4)。所以至少也是52字节的分配,如果在加上不确定的部分,也就差不多可以达到57了。


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

相关文章

Springboot3.x配置类(Configuration)和单元测试

配置类在Spring Boot框架中扮演着关键角色,它使开发者能够利用Java代码定义Bean、设定属性及调整其他Spring相关设置,取代了早期版本中依赖的XML配置文件。 集中化管理:借助Configuration注解,Spring Boot让用户能在一个或几个配…

电商环境下的财务ERP系统架构

先介绍一下自己的工作经历,2002年开始进入ERP实施行业,专注于O记EBS系统,正好赶上中国经济和信息化高度发展的阶段,先后实施过很多大国企和民企的大型ERP项目,在实施过程中逐渐对ERP系统的架构、模块设计有更深入的认识…

计算机网络——期末复习(1)背诵

背诵 交换机与路由器:交换机连接同一子网,利用帧中的目的物理地址转发帧,工作在数据链路层;路由器连接不同子网,利用IP数据报中的目的IP地址转发IP数据报,工作在网络层。五层的任务:&#xff0…

穷举vs暴搜vs深搜vs回溯vs剪枝专题一>全排列

题目&#xff1a; 解析&#xff1a; 代码&#xff1a; //用于返回最后的结果private List<List<Integer>> ret;//记录决策树元素的路径private List<Integer> path;//标记决策树元素&#xff0c;元素没有被使用为默认falseprivate boolean[] check;public…

ThinkRAG开源!笔记本电脑可运行的本地知识库大模型检索增强生成系统

ThinkRAG 大模型检索增强生成系统&#xff0c;可以轻松部署在笔记本电脑上&#xff0c;实现本地知识库智能问答。 该系统基于 LlamaIndex 和 Streamlit 构建&#xff0c;针对国内用户在模型选择、文本处理等诸多领域进行了优化。 1. 项目地址 ThinkRAG 在Github开源&#xf…

安防监控Liveweb视频汇聚融合平台助力执法记录仪高效使用

Liveweb平台可接入的设备除了常见的智能分析网关与摄像头以外 &#xff0c;还可通过GB28181协议接入执法记录仪&#xff0c;实现对执法过程的全程监控与录像&#xff0c;并对执法轨迹与路径进行调阅回看。那么&#xff0c;如何做到执法记录仪高效使用呢&#xff1f; 由于执法记…

crapy 爬虫框架的使用

1.scrapy框架安装 安装前先安装python3和pycharm 社区版 执行命令安装scrapy&#xff0c; pip install scrapy 2.创建项目 执行命令&#xff1a; scrapy startproject test_spider 如图&#xff1a; 3.使用pycharm大开项目并设置pipenv虚拟机环境 虚拟环境是为了依赖隔…

QT编译opencv

一.QT5.12编译 1.QT环境 QT5.12 Qt Creator 12.0.2 2.OpenCV文件 因为QT5.12版本qt最后支持到2021.12月&#xff0c;所以这里选择的opencv版本为2021.4月发布的opencv-3.4.16版本 官网下载地址&#xff1a;https://opencv.org/releases/ 最新版本&#xff1a;opencv-3.4.16.…