redis数据结构的底层实现

news/2024/3/29 3:25:58/文章来源:https://blog.csdn.net/qq_43216019/article/details/129225687

文章目录

      • 一.引言
      • 二.redis的特点
      • 三.Redis的数据结构
        • a.字符串
        • b.hash
        • c.list
        • d.set
        • e.zset(有序集合)

一.引言

redis是一个开源的使用C语言编写、支持网络、可基于内存亦可持久化的日志型、key-value的NoSQL数据库。

通常使用redis作为缓存中间件来降低数据库的压力,除此之外,redis还有很多使用场景,比如分布式锁、计数、队列等等。

二.redis的特点

  • 读写速度快。每秒10w次左右。原因
    • 数据存储在内存中,访问速度快
    • 采用单线程的架构,避免上下文的切换和多线程带来的竞争,不存在加锁和释放锁的操作,减少了CPU的消耗
    • 采用了非阻塞IO多路复用机制
  • 数据结构丰富。redis不仅仅支持简单的key-value类型的数据,同时还提供list、set、zset、hash等数据结构
  • 支持持久化。RDB和AOF两种持久化策略
  • 支持高可用。可以使用主从复制,并且提供哨兵机制,保证服务器的高可用
  • 客户端语言多。涵盖了所有主流编程语言

三.Redis的数据结构

常见的五种数据类型:string、list、set、zset、hash

redis的这些数据结构,在底层都是使用redisObject来进行表示的。redisObject有三个重要的属性,分别是type、encoding、ptr。

type代表保存的value的类型。通常有以下五种:

  • 字符串REDIS_STRING
  • 列表 REDIS_LIST
  • 集合 REDIS_SET
  • 有序集合 REDIS_ZSET
  • 字典 REDIS_HASH

encoding表示保存的value的编码,通常有以下几种:

  • 字符串:REDIS_ENCODING_RAW
  • 整数:REDIS_ENCODING_INT
  • 哈希表:REDIS_ENCODING_HT
  • zipmap:REDIS_ENCODING_ZIPMAP
  • 双端链表:REDIS_ENCODING_LINKEDLIST
  • 压缩列表:REDIS_ENCODING_ZIPLIST
  • 整数集合:REDIS_ENCODING_INTSET
  • 跳跃表:REDIS_ENCODING_SKIPLIST

ptr是一个指针,指向实际保存的value的数据结构

数据类型和编码方式是有一定关系的,所以数据类型和编码方式是可以确定底层采用什么数据结构的。

img

a.字符串

字符串对象的encoding有三种,分别是:int、raw、embstr

常用命令有:set、get、decr、incr、mget

底层不是使用c语言的字符串动态类型,而是自己开发了一种数据类型SDS(Simple Dynamic String:动态字符串)进行存储:

struct sdshdr{int len;/*字符串长度*/int free;/*未使用的字节长度*/char buf[];/*保存字符串的字节数组*/
}

SDS与C语言的字符串有什么区别?

  • C语言获取字符串长度是从头到尾遍历,时间复杂度是O(n),而SDS有len属性记录字符串长度,时间复杂度尾O(1)
  • 避免缓冲区溢出。SDS在需要修改时,会先检查空间是否满足大小,如果不满足,则先拓展至所需大小再进行修改操作。
  • 空间预分配。当SDS需要进行扩展时,redis会为SDS分配好内存,并且根据特定的算法分配多余的free空间,避免连续执行字符串带来的内存分配的消耗
  • 惰性释放。如果需要缩短字符串,不会立即回收多余的内存空间,而是用free近路剩余的空间,以便下次扩展时使用,避免了再次分配内存的操作
  • 二进制安全。c语言存储字符串是采用N+1的字符串数据,末尾使用‘\0’标识字符串的结束,如过我们存储的字符串中出现‘\0’,那么就会出现识别出错,而SDS因为记录了字符串的长度len,则没有这个问题。

redis规定了字符串的长度不得超过512M

b.hash

哈希对象的编码方式有两种:ziplist和hashtable

当哈希对象保存的键值对数量小于512,并且所有键值对的长度都小于64自己饿时,使用ziplist存储;否则使用hashtable存储。

redis中的hashtable跟java中的hashMap类似,都是通过数组+链表的实现方式解决部分的哈希冲突。

typedf struct dict{dictType *type;//类型特定函数,包括一些自定义函数,这些函数使得key和value能够存储void *private;//私有数据dictht ht[2];//两张hash表 int rehashidx;//rehash索引,字典没有进行rehash时,此值为-1unsigned long iterators; //正在迭代的迭代器数量
}dict;typedef struct dictht{//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码,用于计算索引值//总是等于 size-1unsigned long sizemask;//该哈希表已有节点的数量unsigned long used; 
}dictht;typedf struct dictEntry{void *key;//键union{void val;unit64_t u64;int64_t s64;double d;}v;//值struct dictEntry *next;//指向下一个节点的指针
}dictEntry;

img

扩容和收缩的过程:

  • 如果执行扩展操作,会基于哈希表创建一个大小等于ht[0].used*2n的哈希表(每次都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表)。相反如果执行的是收缩操作,每次收缩是根据已使用精简缩小一倍创建一个新的哈希表。
  • 重新利用hash算法,计算索引值,然后将键值对放到新的哈希表位置上。
  • 所有键值对都迁徙完毕后,释放原哈希表的内存空间。

在redis执行扩容和收缩的规则是:

  • 服务器目前没有执行bgsave或bgrewrite命令,并且负载因子大于等于1
  • 服务器目前没有执行bgsave或bgrewrite命令,并且负载因子大于等于5

负载因子=哈希表已保存节点数量/哈希表大小

渐进式rehash

扩容和收缩不是一次性集中式完成,而是通过多次逐渐地完成的。为什么要采用这种方式呢?在键值对数量达到几十万,几百万的键值对要一次性进行rehash,势必会导致redis性能严重下降,自然而然地redis开发者就想到采用渐进式rehash,过程如下:

  • 使用rehashindex字段保存迁移的进度,从0开始
  • 在迁移过程中ht[0]和ht[1]同时保存数据,ht[0]指向旧哈希表,ht[1]指向新hash表,每次对字典进行添加、删除、查找或更新操作是,程序除了执行指定的操作外,还会顺带将ht[0]的元素迁移到ht[1]中
  • 迁移完成后,rehashindex设置为-1
  • rehash完成后,ht[0]指向的旧表会被释放,之后会将新表的持有权交给ht[0],再重置ht[1]指向NULL

渐进式rehash的优缺点

优点:

  • rehash操作分散到每一个字典操作和定时函数上,避免了一次性集中式rehash带来的服务器压力

缺点:

  • rehash期间需要使用两个hash表,内存占用稍大

常用命令

hget、hset、hgetall

c.list

列表对象的编码有两种,分别是:ziplist、linkedlist。当列表的长度小于512,并且所有元素的长度都小于64字节时,使用ziplist存储;否则使用linkedlist存储

redis中的linkedlist类似于java的linkedlist,是一个双向链表,插入和删除操作效率比较快,时间复杂度是O(1)

typedef struct listNode {struct listNode *prev;struct listNode *next;void *value;
} listNode;typedef struct listIter {listNode *next;int direction;
} listIter;typedef struct list {listNode *head;listNode *tail;void *(*dup)(void *ptr);void (*free)(void *ptr);int (*match)(void *ptr, void *key);unsigned long len;
} list;

常用命令:

lpush、rpush、lpop、rpop、lrange

d.set

特点:无序、不重复,跟java的hashset类似。它的编码有两种,分别是intset和hashtable。如果value可以转换成整数值,并且长度不超过512的话就使用intset存储,否则采用hashtable

typedef struct intset{uint32_t encoding;//编码方式uint32_t length;//集合包含的元素数量int8_t contents[];//保存元素的数组
}intset;

encoding的值有三种,分别是INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64,代表着整数的取值范围。redis会根据添加进来的元素的大小,选择不同的类型进行存储。尽可能地节省内存空间。

INTSET_ENC_INT16–>INTSET_ENC_INT32–>INTSET_ENC_INT64的升级过程:

  • 根据新元素的类型扩展数组contents的空间
  • 从尾部将数据插入
  • 根据新编码格式重置之前的值,因为这是的contents存在着两种编码的值。从插入的数据的位置,也就是尾部,从后到前将之前的数据按照新的编码格式进行移动和设置。从后往前是为了防止数据被覆盖

优点:节省内存;缺点:升级会消耗系统资源。而且升级是不可逆的,一旦升级,编码就会一直保存升级后的状态

set常见的命令有:

sadd、spop、smembers、sunion

redis为set类型提供了求交集、并集、差集的操作,可以非常方便地实现比如共同关注、共同爱好、共同好友等功能

e.zset(有序集合)

zset和set一样是不可重复的,区别在于多了score值,用来代表排序的权重。也就是当你需要一个有序的,不可重复的集合列表时,就可以考虑使用这种数据类型。

zset的编码方式有两种,分别是:ziplist、skiplist。当zset的长度小于128,并且所有元素的长度都小于64字节时,使用ziplist存储,否则使用skiplist存储。

img

跳远表的数据结构设计如上,设计的好处是什么呢?

查询的时候可以减少时间复杂度,如果是链表,我们要插入并且保持有序的话,那就要从头节点开始遍历,遍历到合适的位置,然后插入,如果这样性能肯定是不理想的。

而使用跳表可以像二分查找一样定位到插入的点,查找过程:

  • L4,查询87,查询一次
  • L3,查询到在24、87之间,需要查询2次
  • L2,查询到48,查询1次
  • L1,查询到37、48,查询两次,确定插入点在37、48之间

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_74294.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STC单片机启动看门狗定时器介绍和使用

STC单片机启动看门狗定时器介绍 ✨这里以STC8系列为例。 📑看门狗复位(WDT_CONTR) WDT_FLAG:看门狗溢出标志 看门狗发生溢出时,硬件自动将此位置 1,需要软件清零。EN_WDT:看门狗使能位 0:对单片机无影响 1:启动看门狗定时器。 注意:看门狗定时器可使用软件方式启动,…

CXL互联标准简介及相关资料

毕设是实现CXL的type3扩展内存设备,因为CXL技术非常新,2019年推出,本专栏也是记录CXL的相关知识与一些浅薄的理解 文章目录CXL出现的背景CXL是什么其他互联总线介绍CXL胜出的原因CXL内容简介包含三种协议 CXL.io/cache/memory支持三种设备类型…

Reids实战—黑马点评(三)秒杀篇

Reids实战—黑马点评(三)秒杀篇 来自黑马的redis课程的笔记 【黑马程序员Redis入门到实战教程,深度透析redis底层原理redis分布式锁企业解决方案黑马点评实战项目】 目录Reids实战—黑马点评(三)秒杀篇一、全局唯一I…

DevOps实战50讲-(1)彻底理解DevOps

持续坚持原创输出,点击蓝字关注我吧软件质量保障:所寫即所思|一个阿里质量人对测试的所感所悟。浅谈软件开发流程软件开发流程是从需求分析、设计、编码、测试到上线等一系列环节的步骤和活动。通常来说,软件开发流程可以分为以下几个阶段&am…

Python 多进程多线程线程池进程池协程

目录 一、线程与进程很简单的介绍 1.1 线程与进程的区别 二、多进程Process 2.1 多进程与多线程的区别 2.2 多进程为啥要使用队列 2.3 控制进程运行顺序 2.3.1 join , 2.3.1 daemon 守护进程 2.4 进程id 2.5 进程 存活状态is_alive() 2.5 实现自定义多…

计算机图形学:liang算法和Cyrus-Beck算法

其中Cyrus-Beck算法呢,是计算一根直线一个多边形的交线段;liang算法是Cyrus的一个特例,即多边形刚好是矩形;先看看Cyrus算法的思路【从别的博客找的图片】:这很容易理解,点积>0时就可能中内部嘛&#xf…

Pyinstaller 打包EXE(七) 百篇文章学PyQT

本文章是百篇文章学PyQT6的第七篇,本文讲述如何使用Pyinstaller打包UI界面和代码,将程序打包成EXE来更为方便的进行部署,在写博客和学习的过程中会遇到很多问题,例如:PyQT6在网上很多博客都是PyQT5、或者PyQT4大部分都…

Amazon S3 服务15岁生日快乐!

2021年3月14日,作为第一个发布的服务,Amazon S3 服务15周岁啦!在中国文化里,15岁是个临界点,是从“舞勺之年”到“舞象之年”的过渡。相信对于 Amazon S3 和其他的云服务15周岁也将是其迎接更加美好未来的全新起点。亚…

java面试题-JVM内存结构

整体结构:1.说说JVM内存整体的结构?线程私有还是共享的?JVM(Java Virtual Machine)内存可以分为以下几个部分:程序计数器(Program Counter Register):是线程私有的&#…

深入浅出解析ChatGPT引领的科技浪潮【AI行研商业价值分析】

Rocky Ding写在前面 【AI行研&商业价值分析】栏目专注于分享AI行业中最新热点/风口的思考与判断。也欢迎大家提出宝贵的意见或优化ideas,一起交流学习💪 大家好,我是Rocky。 2022年底,ChatGPT横空出世,火爆全网&a…

Linux学习(8.6)文件与目录的默认权限与隐藏权限

目录 文件与目录的默认权限与隐藏权限 文件的默认权限:umask chattr (配置文件隐藏属性) lsattr (显示文件隐藏属性) 文件特殊权限: SUID, SGID, SBIT 观察文件类型:file 以下内容转载自鸟哥的Linux私房菜 文件与目录的默认权限与隐藏权…

【架构师】零基础到精通——架构发展

博客昵称:架构师Cool 最喜欢的座右铭:一以贯之的努力,不得懈怠的人生。 作者简介:一名Coder,软件设计师/鸿蒙高级工程师认证,在备战高级架构师/系统分析师,欢迎关注小弟! 博主小留言…

【20230225】【剑指1】分治算法(中等)

1.重建二叉树class Solution { public:TreeNode* traversal(vector<int>& preorder,vector<int>& inorder){if(preorder.size()0) return NULL;int rootValuepreorder.front();TreeNode* rootnew TreeNode(rootValue);//int rootValuepreorder[0];if(preo…

redis秒杀

redis优惠券秒杀 为什么订单表订单ID不采用自增长&#xff1f; id规律性太明显&#xff0c;容易被用户猜测到&#xff08;比如第一天下订单id10&#xff0c;第二天下订单id100&#xff0c;在昨天的1天内只卖出90商品&#xff09;受单表数据量限制&#xff08;订单数据量大&am…

从零开始学习iftop流量监控(找出服务器耗费流量最多的ip和端口)

一、iftop是什么iftop是类似于top的实时流量监控工具。作用&#xff1a;监控网卡的实时流量&#xff08;可以指定网段&#xff09;、反向解析IP、显示端口信息等官网&#xff1a;http://www.ex-parrot.com/~pdw/iftop/二、界面说明>代表发送数据&#xff0c;< 代表接收数…

chatGPT模型原理

文章目录简介BertGPT 初代GPT-2GPT-3chatGPT开源ChatGPT简介 openai 的 GPT 大模型的发展历程。 Bert 2018年&#xff0c;自然语言处理 NLP 领域也步入了 LLM 时代&#xff0c;谷歌出品的 Bert 模型横空出世&#xff0c;碾压了以往的所有模型&#xff0c;直接在各种NLP的建模…

EasyRecovery16MAC苹果版本Photo最新版数据恢复软件

无论是在工作学习中&#xff0c;还是在生活中&#xff0c;Word、Excle等办公软件都是大家很常用的。我们在使用电脑的过程中&#xff0c;有时会因自己的误删或电脑故障&#xff0c;从而导致我们所写的文档丢失了。出现这样的大家不要着急&#xff0c;今天小编就给大家推荐一款可…

FreeRTOS优先级翻转

优先级翻转优先级翻转&#xff1a;高优先级的任务反而慢执行&#xff0c;低优先级的任务反而优先执行优先级翻转在抢占式内核中是非常常见的&#xff0c;但是在实时操作系统中是不允许出现优先级翻转的&#xff0c;因为优先级翻转会破坏任务的预期顺序&#xff0c;可能会导致未…

YOLOv5模型学习记录

新年伊始&#xff0c;YOLOv8横空出世&#xff0c;这个还未开源时便引发界内广泛热议的目标检测算法&#xff0c;一经问世便再次引发热潮&#xff0c;而作为与其师出同源的YOLOv5&#xff0c;自然要拿来与其比较一番。接下来我们便来学习一下吧。 模型结构 首先便是模型结构了…

Rasa 3.x 学习系列-摆脱意图:一种新的对话模式

Rasa 3.x 学习系列-摆脱意图:一种新的对话模式 在2019年的一篇文章中,Alan Nichol写道 :是时候摆脱意图了。一年后,Rasa发布了Rasa中的第一个无意图(或“端到端”)对话模型。现在,我们宣布迈出了一个重要的步伐,将LLM的强大功能带入Rasa的对话管理中。 首先,意图非常…