【Redis 系列】redis 学习十六,redis 字典(map) 及其核心编码结构

本文涉及的产品
云数据库 Redis 版,标准版 2GB
推荐场景:
搭建游戏排行榜
云原生内存数据库 Tair,内存型 2GB
简介: 【Redis 系列】redis 学习十六,redis 字典(map) 及其核心编码结构

redis 是使用 C 语言编写的,但是 C 语言是没有字典这个数据结构的,因此 C 语言自己使用结构体来自定义一个字典结构

typedef struct redisDb

src\server.h 中的 redis 数据库 数据结构

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

redisDb 存放了 redis 数据库底层的数据结构:

  • dict

字典类型

  • expires

过期时间

  • blocking_keys

客户端等待数据的键 (BLPOP)

  • ready_keys

收到PUSH的键被阻塞

  • watched_keys

监控 MULTI/EXEC CAS 的键,例如事务的时候就会使用到

  • id

数据库的 id, 0 – 15

  • avg_ttl

统计平均的 ttl

  • expires_cursor

记录过期周期

  • defrag_later

存放 key 的列表

typedef struct dict

src\dict.h 字典的数据结构

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

dict 存放字典的数据结构

  • type

字典的类型

  • privdata

私有数据

  • ht

hash 表, 一个旧表,一个新表,是有当 hash 表扩容的时候,新表才会被使用到,也就是 ht[1]

typedef struct dictType

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

dictType 定义了多个函数指针,便于后续进行方法的实现和调用

例如 keyCompare 函数指针,他是一个指针,指向的是一个函数,这个函数有 3 个参数,和 1 个返回值:

3 个参数

  • privdata

具体的数据

  • key1

key1 这个键具体的值

  • key2

key2 这个键具体的值

这个指针 keyCompare 指向的函数作用是比较两个 key 的大小

typedef struct dictht

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

dictht 存放的是 hash 表使用到的数据结构

  • table

实际的 key-value 键值对

  • size

hashtable 的容量

  • sizemask

等于 size -1

  • used

hashtable 元素的个数

typedef struct dictEntry

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

dictEntry 为键值对的实际数据结构

  • key

key 值,实际上是一个 sds 类型的

  • v

value 值,是一个联合体

  • next

dictEntry 指针,指向下一个数据,主要是解决 hash 冲突的

例如上一篇我们介绍到的 hash,如下图中,key 就是 1,v 就是 (k3,v3) ,next 指向的就是 (k2,v2),一般默认情况 next 指向 NULL

上述联合体 v ,里面第 1 个元素是, void *val;

实际上这个元素才是指向真正的值,这个元素是一个指针,实际的数据结构是这个样子的

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;
  • type

类型,占 4 个 bit ,是用来约束客户端 api 的,例如 string 类型,embstr,hash,zset 等等

  • encoding

编码类型,占 4 个bit ,使用到的数字有 0 - 10,分别表示不同的数据类型

  • lru

lru 占 24 个bit ,3 个字节 , 内存淘汰算法

  • refcount

引用计数 , int 类型,占 4 个字节

  • ptr

实际的数据指针 , 64 位操作系统中, ptr 占 8个字节

bitmap 的小案例

设置一个 bitmap 的 key,作用为标记 11 号的在线用户

127.0.0.1:6379> SETBIT login:9:11 25 1
(integer) 0
127.0.0.1:6379> SETBIT login:9:11 26 1
(integer) 0
127.0.0.1:6379> SETBIT login:9:11 27 1
(integer) 0
127.0.0.1:6379> BITCOUNT login:9:11
(integer) 3
127.0.0.1:6379> strlen login:9:11
(integer) 4
  • BITCOUNT key [start end]

通过 BITCOUNT 可以看出 11 号在线人数 3 个人,login:9:11 占用字节数位 4 字节

127.0.0.1:6379> SETBIT login:9:12 26 1
(integer) 0
127.0.0.1:6379> SETBIT login:9:12 25 0
(integer) 0
127.0.0.1:6379> SETBIT login:9:12 27 1
(integer) 0
127.0.0.1:6379> STRLEN login:9:12
(integer) 4

通过 BITCOUNT 可以看出 12 号在线人数 2 个人,login:9:12 占用字节数位 4 字节

下面我们将取 login:9:11 和 login:9:12 的 与操作,来计算 11 号 和 12 号两天来都在线的人数

127.0.0.1:6379> BITOP and login:and login:9:11 login:9:12
(integer) 4
127.0.0.1:6379> BITCOUNT login:and
(integer) 2
  • BITOP operation destkey key [key …]

根据上述结果我们可以看出,11 号 和 12 号两天来都在线的人数为 2 人,验证 ok

我们再来看看11 号 和 12 号任意一天在线的人数

127.0.0.1:6379> BITOP or login:or login:9:11 login:9:12
(integer) 4
127.0.0.1:6379> BITCOUNT login:or
(integer) 3

根据上述结果我们可以看出,11 号 和 12 号任意一天在线的人数为 3 人,验证 ok

127.0.0.1:6379> type login:or
string
127.0.0.1:6379> OBJECT encoding login:or
"raw"
127.0.0.1:6379> OBJECT encoding login:9:12
"raw"
127.0.0.1:6379> OBJECT encoding login:and
"raw"

咱们来看看上述用到的 key ,在 redis 里面实际是什么数据类型吧,

  • OBJECT encoding [arguments [arguments …]]

可以看出上述都是 “raw” 类型, 也就是 redis 的 sds 类型

缓存行

咱们再来看一个小例子,redis 中设置一个字符串 key

127.0.0.1:6379> set name xiaoming
OK
127.0.0.1:6379> OBJECT encoding name
"embstr"

我们可以看出 name 的类型是 “embstr”,那么 “embstr” 底层是如何实现的呢?“embstr” 有能承载多少个字节的数据呢?

上述我们有说到 redis 里面存放键值对的地方在 dictEntry 结构体中,dictEntry 结构体中的val 指针指向的是一个 redisObject 结构体,是这样的

我们在一个 64 位的机器中,CPU 在内存中读取数据的是通过读取缓存行的方式来实现的

一个缓存行有 64 字节

一个 redisObject 结构体占 16 字节

那么就还剩 48 字节 可以使用,那么使用 redis 里面 哪一个 sds 数据结构来存放数据数据呢?

使用 hisdshdr8 类型,hisdshdr8 类型 sds 的前 3 个元素占用 3 个字节,那么剩下的 buf 存放数据就可以存放 45个字节(64 - 16 - 3)的数据了

如果你这么认为了,那么就有点粗心哦,因为 redis 为了兼容 C 语言的标准,会在字符串的后面加上 1 个 ‘\0’ ,他是占一个字节的因此最终“embstr” 实际能存放的字节数是:

44 字节

来回顾上一篇文章,可以看出

当数据占用空间在 0 - - 2^5-1 , 使用 hisdshdr5 数据类型

2^5 – 2^8-1 的占用空间的时候,使用 hisdshdr8 数据类型

小小的实践

我们在 redis 中设置一个 test 的值为一个 44字节 的内容,查看这个 key 的类型,是 embstr

127.0.0.1:6379> set test 99999999991111111111222222222233333333334444
OK
127.0.0.1:6379> OBJECT encoding test
"embstr"
127.0.0.1:6379> STRLEN test
(integer) 44

再来设置 test2 为 大于 44 字节的内容,再查看他的内容是 raw

127.0.0.1:6379> set test2 999999999911111111112222222222333333333344449
OK
127.0.0.1:6379> OBJECT encoding test2
"raw"

最后送上一张上述数据结构的关系图

参考资料:

欢-迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是小魔童哪吒,欢迎点赞关注收藏,下次见~

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
3月前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
70 1
|
3月前
|
NoSQL Java Redis
Redis系列学习文章分享---第十八篇(Redis原理篇--网络模型,通讯协议,内存回收)
Redis系列学习文章分享---第十八篇(Redis原理篇--网络模型,通讯协议,内存回收)
63 0
|
3月前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
70 0
|
29天前
|
缓存 NoSQL 关系型数据库
Redis学习总结
Redis学习总结
31 1
|
23天前
|
存储 Go 容器
Go从入门到放弃之map(字典)
Go从入门到放弃之map(字典)
|
2月前
|
存储 缓存 NoSQL
Redis 常用五种数据类型编码
Redis 常用五种数据类型编码
31 9
|
3月前
|
存储 NoSQL 安全
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
61 1
|
3月前
|
缓存 负载均衡 NoSQL
Redis系列学习文章分享---第十四篇(Redis多级缓存--封装Http请求+向tomcat发送http请求+根据商品id对tomcat集群负载均衡)
Redis系列学习文章分享---第十四篇(Redis多级缓存--封装Http请求+向tomcat发送http请求+根据商品id对tomcat集群负载均衡)
64 1
|
3月前
|
存储 缓存 NoSQL
Redis系列学习文章分享---第十三篇(Redis多级缓存--JVM进程缓存+Lua语法)
Redis系列学习文章分享---第十三篇(Redis多级缓存--JVM进程缓存+Lua语法)
70 1
|
2月前
|
存储 Java
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD