Redis 底层数据结构大揭秘:五张图看透Redis数据结构

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: Redis的数据结构从用户层面看就是普通的字典,列表。但是其实在不同的情况下,Redis 会使用不同的底层数据结构进行优化,本文通过五张流程图对其进行了总结。

引言


这篇文章主要聊聊Redis具体功能数据结构的实现,主要针对常用的五种数据结构,stringhashlistsetzset的实现。


redis.c:180中存储了Redis支持所有的指令及其实现函数:


structredisCommandredisCommandTable[] = {
    {"get",getCommand,2,"r",0,NULL,1,1,1,0,0},
    {"set",setCommand,-3,"wm",0,NULL,1,1,1,0,0},
    {"setnx",setnxCommand,3,"wm",0,NULL,1,1,1,0,0},
//...}


第二个属性就是指令的具体实现函数,进入该函数即可阅读相应的指令的具体实现。


在调用具体的命令执行函数前,命令就被拆成一个个参数存放到相应的redisClient.argv中了,比如Redis命令set aaa "aaa"会被拆成数组{"set", "aaa", "aaa"}放在redisClient.argv中。


Redis数据库的真身


redisClient结构体中有一个db字段,它是redisDb类型,这个就是该redisClient目前选中的数据库,不论是哪种数据类型,都会调用setKey函数将自己设置进数据库中:

voidsetKey(redisDb*db, robj*key, robj*val) {
// 添加或覆写数据库中的键值对if (lookupKeyWrite(db,key) ==NULL) {
dbAdd(db,key,val);
    } else {
dbOverwrite(db,key,val);
    }
//...}
voiddbAdd(redisDb*db, robj*key, robj*val) {
//....intretval=dictAdd(db->dict, copy, val);
//... }

发现其实就是在往redisDbdict字典中加入kv,dict就是Redis自己实现的字典结构,其实现类似于高级语言中的hashmap,可见一个Redis数据库本质就是一个大字典,当你创建的不同的数据结构时,本质上都是在往这个大字典中写入kv。从setKey的签名可以看出,这个大字典中的每一个key和value都是robj类型,这是个什么东西呢?


redisObject


robj其实是redisObject的简称:

typedefstructredisObject {
// 类型unsignedtype:4;   // 4 bit 位域// 编码 (底层数据结构类型)unsignedencoding:4;
// 对象最后一次被访问的时间unsignedlru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */// 引用计数intrefcount;
// 指向实际值的指针  指向底层实现数据结构void*ptr;
} robj;

类型type代表了该robj对用户暴露的类型,就是引言中说的五种类型:

数据类型

type的值

string

REDIS_STRING

list

REDIS_LIST

hash

REDIS_HASH

set

REDIS_SET

zset

REDIS_ZSET


encoding代表底层实际使用的数据结构类型,而具体的底层数据结构实现存储在ptr字段中。


底层数据结构


底层数据结构是指不对用户暴露,仅仅作为底层实现的一些数据结构,Redis有如下的底层数据结构:


  • long:就是C语言中普通的long类型,当字符串可以编码成long类型的数字时,会采用这种结构
  • sds:就是Redis中的字符串类型
  • 所有的key的底层数据结构都是它
  • 字符串的底层数据结构,根据其内存摆放特点又有两种
  • raw:普通的sds
  • embstr:内存中位置紧跟在相应的redisObject后面,可以和redisObject一起分配与释放
  • dict:Redis自己实现字典,除了用于实现Redis内部的功能外,还用于hashset的底层数据结构
  • ziplist:在内存中连续排列的一个列表结构,可以存储字符串或者数字,和别的结构不一样的地方是,在代码中没有具体的结构体来表示,只有一些宏可以从代表ziplist的byte串取得具体属性的值,redis.c:246
  • list, hashzset数据结构的默认实现
  • 虽然是一个紧凑的数据结构,但却无法像数组一样随机访问,各种操作的时间复杂度和链表类似,在查询时需要一个一个元素往下走
  • 该编码相对比较复杂,网上有很多文章讲解,这里就不专门介绍了
  • list:Redis自己实现的一个双向链表,可用于list的底层数据结构
  • intset:整数集合,其实就是个从小到大排列的整数数组,如果set中所有的元素都是数字的话,可以用于set的底层数据结构
  • skiplist:跳表,可以和dict一起用于zset的底层数据结构,其中dict用于按成员取分值,而skiplist负责按分值取成员。


下面逐一通过图示五种数据结构是如何在上面这7种底层数据结构中作选择的。


string


set msg "hello"set number 12235


redis-string.png


hash


hset o1 f1 "aaa"

redis-hash.png

list


lpush languages python

redis-list.png


set


sadd names "Lily"


redis-set.png


zset


zadd page_rank 10 google.com


redis-zset.png


在使用ziplist作为底层数据结构时,score是以字符串的形式编码在里面,具体为什么要这么做,我也比较困惑,ziplist本身是支持存数字的。


这个skiplist + dict的结构其实是zset结构体:

typedefstructzset {
// 字典,键为成员,值为分值// 用于支持 O(1) 复杂度的按成员取分值操作dict*dict;
// 跳跃表,按分值排序成员// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作// 以及范围操作zskiplist*zsl;
} zset;


其中dict主要用于支持像zscore这样的按成员取分值的操作,而zsl跳跃表主要用于支持像zrange这样的按照分数取成员的操作。


End


作者:元青


微信公众号 「技乐书香」

相关实践学习
基于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
相关文章
|
22天前
|
存储 消息中间件 缓存
Redis 5 种基础数据结构?
Redis的五种基础数据结构——字符串、哈希、列表、集合和有序集合——提供了丰富的功能来满足各种应用需求。理解并灵活运用这些数据结构,可以极大地提高应用程序的性能和可扩展性。
27 2
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
43 5
|
1月前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
2月前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
59 8
|
2月前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
1月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
1月前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
5天前
|
存储 缓存 NoSQL
解决Redis缓存数据类型丢失问题
解决Redis缓存数据类型丢失问题
118 85
|
2月前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
82 6
|
2天前
|
缓存 监控 NoSQL
Redis经典问题:缓存穿透
本文详细探讨了分布式系统和缓存应用中的经典问题——缓存穿透。缓存穿透是指用户请求的数据在缓存和数据库中都不存在,导致大量请求直接落到数据库上,可能引发数据库崩溃或性能下降。文章介绍了几种有效的解决方案,包括接口层增加校验、缓存空值、使用布隆过滤器、优化数据库查询以及加强监控报警机制。通过这些方法,可以有效缓解缓存穿透对系统的影响,提升系统的稳定性和性能。