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


作者:元青


微信公众号 「技乐书香」

相关文章
|
17天前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
144 86
|
1月前
|
存储 缓存 NoSQL
【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
本文解析 Redisson 如何通过 Redis 实现分布式信号量(RSemaphore)与倒数闩(RCountDownLatch),利用 Lua 脚本与原子操作保障分布式环境下的同步控制,帮助开发者更好地理解其原理与应用。
91 0
|
2月前
|
存储 缓存 NoSQL
Redis核心数据结构与分布式锁实现详解
Redis 是高性能键值数据库,支持多种数据结构,如字符串、列表、集合、哈希、有序集合等,广泛用于缓存、消息队列和实时数据处理。本文详解其核心数据结构及分布式锁实现,帮助开发者提升系统性能与并发控制能力。
|
17天前
|
存储 缓存 NoSQL
Redis基础命令与数据结构概览
Redis是一个功能强大的键值存储系统,提供了丰富的数据结构以及相应的操作命令来满足现代应用程序对于高速读写和灵活数据处理的需求。通过掌握这些基础命令,开发者能够高效地对Redis进行操作,实现数据存储和管理的高性能方案。
57 12
|
15天前
|
存储 消息中间件 NoSQL
【Redis】常用数据结构之List篇:从常用命令到典型使用场景
本文将系统探讨 Redis List 的核心特性、完整命令体系、底层存储实现以及典型实践场景,为读者构建从理论到应用的完整认知框架,助力开发者在实际业务中高效运用这一数据结构解决问题。
|
24天前
|
存储 缓存 NoSQL
【Redis】 常用数据结构之String篇:从SET/GET到INCR的超全教程
无论是需要快速缓存用户信息,还是实现高并发场景下的精准计数,深入理解String的特性与最佳实践,都是提升Redis使用效率的关键。接下来,让我们从基础命令开始,逐步揭开String数据结构的神秘面纱。
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
221 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
49 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。