写点什么

五张图带你看透 Redis 数据结构

  • 2023-05-03
    湖南
  • 本文字数:1954 字

    阅读完需:约 6 分钟

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


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

struct redisCommand redisCommandTable[] = {    {"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 函数将自己设置进数据库中:

void setKey(redisDb *db, robj *key, robj *val) {
// 添加或覆写数据库中的键值对 if (lookupKeyWrite(db,key) == NULL) { dbAdd(db,key,val); } else { dbOverwrite(db,key,val); }
//...}
void dbAdd(redisDb *db, robj *key, robj *val) {
//.... int retval = dictAdd(db->dict, copy, val);
//... }
复制代码

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

redisObject

robj其实是 redisObject 的简称:

typedef struct redisObject {
// 类型 unsigned type:4; // 4 bit 位域
// 编码 (底层数据结构类型) unsigned encoding:4;
// 对象最后一次被访问的时间 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 引用计数 int refcount;
// 指向实际值的指针 指向底层实现数据结构 void *ptr;
} robj;
复制代码

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

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

底层数据结构

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

  • long就是 C 语言中普通的 long 类型,当字符串可以编码成long类型的数字时,会采用这种结构

  • sds:就是 Redis 中的字符串类型所有的 key 的底层数据结构都是它字符串的底层数据结构,根据其内存摆放特点又有两种raw:普通的sdsembstr:内存中位置紧跟在相应的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
复制代码


hash

hset o1 f1 "aaa"
复制代码


list

lpush languages python
复制代码


set

sadd names "Lily"
复制代码


zset

zadd page_rank 10 google.com
复制代码


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


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

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

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


作者:技乐书香

链接:https://juejin.cn/post/7206260789770059813

来源:稀土掘金

用户头像

还未添加个人签名 2021-07-28 加入

公众号:该用户快成仙了

评论

发布
暂无评论
五张图带你看透Redis数据结构_做梦都在改BUG_InfoQ写作社区