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数据库实现在线游戏中的游戏玩家积分排行榜功能。
相关文章
|
2月前
|
存储 缓存 NoSQL
Redis核心数据结构与分布式锁实现详解
Redis 是高性能键值数据库,支持多种数据结构,如字符串、列表、集合、哈希、有序集合等,广泛用于缓存、消息队列和实时数据处理。本文详解其核心数据结构及分布式锁实现,帮助开发者提升系统性能与并发控制能力。
|
4月前
|
存储 NoSQL 算法
Redis设计与实现——数据结构与对象
Redis 是一个高性能的键值存储系统,其数据结构设计精妙且高效。主要包括以下几种核心数据结构:SDS、链表、字典、跳跃表、整数集合、压缩列表。此外,Redis 对象通过类型和编码方式动态转换,优化内存使用,并支持引用计数、共享对象和淘汰策略(如 LRU/LFU)。这些特性共同确保 Redis 在性能与灵活性之间的平衡。
|
7月前
|
NoSQL 算法 安全
Redis原理—1.Redis数据结构
本文介绍了Redis 的主要数据结构及应用。
Redis原理—1.Redis数据结构
|
9月前
|
存储 消息中间件 缓存
Redis 5 种基础数据结构?
Redis的五种基础数据结构——字符串、哈希、列表、集合和有序集合——提供了丰富的功能来满足各种应用需求。理解并灵活运用这些数据结构,可以极大地提高应用程序的性能和可扩展性。
153 2
|
10月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
173 5
|
10月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
11月前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
223 64
|
存储 NoSQL 算法
「Redis」数据结构与对象
Redis数据结构与对象介绍
117 0
|
NoSQL 算法 Java
Redis进阶 - 数据结构:对象机制详解,一文深入底层分析
我们在前文已经阐述了Redis 5种基础数据类型详解,分别是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset),以及5.0版本中Redis Stream结构详解;那么这些基础类型的底层是如何实现的呢?Redis的每种对象其实都由对象结构(redisObject) 与 对应编码的数据结构组合而成, 本文主要介绍对象结构(redisObject) 部分。
Redis进阶 - 数据结构:对象机制详解,一文深入底层分析