Redis源码、面试指南(3)数据对象类型编码(上)

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: Redis源码、面试指南(3)数据对象类型编码

三、数据类型的实现

在前面,我们陆续介绍了 Redis 用到的所有主要数据结构

Redis 并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象

对象类型及编码

源码文件:object.c

每次当我们在Redis的数据库中新创建一个键值对时,我们至少会创建两个对象,一个对象用作键值对的键(键对象),另一个对象用作键值对的值(值对象)

Redis中的每个对象都由一个redisObject结构表示:

typedef struct redisObject {
    // 对象类型
    unsigned type:4;
    // 底层编码
    unsigned encoding:4;
    // 对象最后一次被访问的时间(日后会说)
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 指向实际存储单元的指针
    void *ptr;
} robj;

之前在介绍跳表时也给出过该定义,不过当时没有详细说,接下来我们来仔细看看。

  • 类型 该属性记录对象的类型,可选常量如下:
类型常量 对象的名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象

注:对于Redis键值对来说,键总是字符串对象而值才是上述五种类型其中一种

  • 编码 对象的ptr指针指向对象的底层实现数据结构,而这些数据结构由对象的encoding属性决定。encoding属性记录了对象所使用的编码, 也即是说这个对象使用了什么数据结构作为对象的底层实现,可选的对象编码如下。
编码常量 编码所对应的底层数据结构
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典

每种对象都至少可以使用两种不同的编码,见下图:

通过encoding属性来设定对象所使用的编码,而不是为特定类型的对象关联一种固定的编码,极大地提升了 Redis 的灵活性和效率,因为 Redis可以根据不同的使用场景来为一个对象设置不同的编码,从而优化对象在某一场景下的效率。

举个例子,在列表对象包含的元素比较少时,Redis使用压缩列表作为列表对象的底层实现:

1)因为压缩列表比双端链表更节约内存,并且在元素数量较少时,压缩列表更合适;

2)元素数量增多或者单个元素过大时,对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面;

  • 空转时长(lru):该属性记录了对象最后一次被访问的时间。该值在Redis的内存过期值淘汰时被用到。如果服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru ,那么当内存到上限值时,空转时长较高的那部分键对象会优先被服务器释放,从而回收内存。
  • 引用计数 Redis在自己的对象系统中构建了一个引用计数技术实现的内存回收机制,通过这一机制,程序可以通过跟踪对象的引用计数信息,在适当的时候自动释放对象并进行内存回收

对象的引用计数信息会随着对象的使用状态而不断变化:

创建一个新对象时, 引用计数的值会被初始化为1

当对象被一个新程序使用时,它的引用计数值会被增一

当对象不再被一个程序使用时它的引用计数值会被减一

当对象的引用计数值变为0时,对象所占用的内存会被释放

修改引用对象计数器有专门的API,如下:

对象的整个生命周期可以划分为创建对象操作对象释放对象三个阶段。释放之前最后调用的API即是decRefcount:

void decrRefCount(robj *o) {
    if (o->refcount <= 0) redisPanic("decrRefCount against refcount <= 0");
    // 释放对象
    if (o->refcount == 1) {
        switch(o->type) {
        case REDIS_STRING: freeStringObject(o); break;
        case REDIS_LIST: freeListObject(o); break;
        case REDIS_SET: freeSetObject(o); break;
        case REDIS_ZSET: freeZsetObject(o); break;
        case REDIS_HASH: freeHashObject(o); break;
        default: redisPanic("Unknown object type"); break;
        }
        zfree(o);
    // 减少计数
    } else {
        o->refcount--;
    }
}
  • ptr,该指针指向实际存储的数据单元。

对象的引用计数属性带有**对象共享(只对整数值)**的作用。

举个例子,假设键A创建了一个包含整数值100的字符串对象作为值对象:


如果这时键B也要创建一个同样保存了整数值100的字符串对象作为值对象,那么服务器有以下两种做法

·为键 B 新创建一个包含整数值100的字符串对象;

·让键 A 和键 B 共享同一个字符串对象;

以上两种方法很明显是第二种方法更节约内存

在 Redis 中,让多个键共享同一个值对象需要执行以下两个步骤:

·将数据库键的值指针指向一个现有的值对象;

·将被共享的值对象的引用计数增一。

如果键A和键B指向同一对象,现如今的情况如下:

共享对象机制对于节约内存非常有帮助,数据库中保存的相同值对象越多,对象共享机制就能节约越多的内存

Redis会在初始化服务器时,创建一万个字符串对象,这些对象包含了从0到9999的所有整数值,当服务器需要用到值为0到9999的字符串对象时,服务器就会使用这些共享对象,而不是新创建对象。

为什么共享对象只对整数值,而不共享包含字符串的对象呢?

因为需要有一个验证时间!只有当共享目标和想要建立的键一样时,才会共享,于是整数只需要O(1),字符串需要O(n),列表或hash则需要O(n^2),这将造成CPU资源浪费

字符串对象

源码文件:t_string.c。

字符串对象是Redis数据库所有键值对的根本,因为键都是字符串对象。如下是Redis中string对象SET、SETEX等命令的底层API:

void setGenericCommand(redisClient *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    long long milliseconds = 0; /* initialized to avoid any harmness warning */
    // 取出过期时间
    if (expire) {
        // 取出 expire 参数的值
        // T = O(N)
        if (getLongLongFromObjectOrReply(c, expire, &milliseconds, NULL) != REDIS_OK)
            return;

        // expire 参数的值不正确时报错
        if (milliseconds <= 0) {
            addReplyError(c,"invalid expire time in SETEX");
            return;
        }
        // 不论输入的过期时间是秒还是毫秒
        // Redis 实际都以毫秒的形式保存过期时间
        // 如果输入的过期时间为秒,那么将它转换为毫秒
        if (unit == UNIT_SECONDS) milliseconds *= 1000;
    }
    // 如果设置了 NX 或者 XX 参数,那么检查条件是否不符合这两个设置
    // 在条件不符合时报错,报错的内容由 abort_reply 参数决定
    if ((flags & REDIS_SET_NX && lookupKeyWrite(c->db,key) != NULL) ||
        (flags & REDIS_SET_XX && lookupKeyWrite(c->db,key) == NULL))
    {
        addReply(c, abort_reply ? abort_reply : shared.nullbulk);
        return;
    }
    // 将键值关联到数据库
    setKey(c->db,key,val);
    // 将数据库设为脏
    server.dirty++;
    // 为键设置过期时间
    if (expire) setExpire(c->db,key,mstime()+milliseconds);
    // 发送事件通知
    notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"set",key,c->db->id);
    // 发送事件通知
    if (expire) notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,
        "expire",key,c->db->id);
    // 设置成功,向客户端发送回复
    // 回复的内容由 ok_reply 决定
    addReply(c, ok_reply ? ok_reply : shared.ok);
}

字符串对象的编码可以是int、raw、embstr

  • int编码,如果字符串对象的整数值可以被long类型表示,那么该整数值会被保存在ptr指针中编码格式跟实际参数类型不一样);
  • raw编码,如果字符串对象保存的是字符串,且大于39字节,那就使用SDS字符串保存;
  • embstr编码,如果该保存的字符串小于等于39字节,就用embstr格式保存。embstr是专门用来保存短字符串的一种优化编码方式,跟raw的区别在于,它只需要调用一次内存分配一块连续的内存空间,依次包含redisObject和sdshdr,而raw是分别调用两次内存分配来存放redisObject和sdshdr,embstr编码时实例如下图:


这样做有什么好处呢?

  1. embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次
  2. 释放embstr编码的字符串对象只需要调用一次内存释放函数,而释放raw编码的字符串对象需要调用两次内存释放函数。
  1. 因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面,所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势。

若利用命令set msg “hello”,其值对象如下图所示:


值得注意,long double类型的浮点数在Redis中也是作为字符串来保存的,比如6.666,那么会将其转换为字符串保存。在需要用到该浮点数的时候又会先将其从字符串转成浮点数再计算。

编码转换

int/embstr在特定的情况下会转换为raw编码的对象,且不可逆。

  • int编码的对象执行命令之后变成了字符串值,那就将从int转换为raw;
  • Redis没有为embstr编码的字符串对象编写任何相应的修改程序 (只有int编码的字符串对象和raw编码的字符串对象有这些程序),embstr编码的字符串对象实际上是只读的:当我们对embstr编码的字符串对象执行任何修改命令时,程序会先将对象的编码从embstr转换成raw,然后再执行修改命令;因为这个原因,embstr编码的字符串对象在执行修改命令之后,总会变成一个raw编码的字符串对象

注:Redis常用的字符串对象命令

image.png

image.png

列表对象

源码文件:t_list.c。

其底层编码是ziplist或linkedlist

  • ziplist编码,底层是压缩列表,每个entry保存一个列表项,有两个条件:列表对象保存的所有字符串元素的长度都小于 64 字节;列表对象保存的元素数量小于 512 个

下图是一个ziplist编码的实例:

两个条件的任意一个不能被满足时,**对象的编码转换操作就会被执行,**从ziplist转为linkedlist。转换过程见该函数:

void listTypeConvert(robj *subject, int enc) {
    listTypeIterator *li;
    listTypeEntry entry;
    redisAssertWithInfo(NULL,subject,subject->type == REDIS_LIST);
    // 转换成双端链表
    if (enc == REDIS_ENCODING_LINKEDLIST) {
        list *l = listCreate();
        listSetFreeMethod(l,decrRefCountVoid);
        // 遍历 ziplist ,并将里面的值全部添加到双端链表中
        li = listTypeInitIterator(subject,0,REDIS_TAIL);
        while (listTypeNext(li,&entry)) listAddNodeTail(l,listTypeGet(&entry));
        listTypeReleaseIterator(li);
        // 更新编码
        subject->encoding = REDIS_ENCODING_LINKEDLIST;
        // 释放原来的 ziplist
        zfree(subject->ptr);
        // 更新对象值指针
        subject->ptr = l;
    } else {
        redisPanic("Unsupported list conversion");
    }
}
  • linkedlist编码,底层是双端链表来保存SDS字符串对象;

下图是一个双端链表编码的实例:

注:字符串对象是 Redis 五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象

注:常用命令如下:

命令 ziplist 编码的实现方法 linkedlist 编码的实现方法
LPUSH 调用 ziplistPush 函数, 将新元素推入到压缩列表的表头。 调用 listAddNodeHead 函数, 将新元素推入到双端链表的表头。
RPUSH 调用 ziplistPush 函数, 将新元素推入到压缩列表的表尾。 调用 listAddNodeTail 函数, 将新元素推入到双端链表的表尾。

image.png

Redis源码、面试指南(3)数据对象类型编码(下):https://developer.aliyun.com/article/1508230

相关实践学习
基于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
相关文章
|
11天前
|
NoSQL Redis
Redis的数据淘汰策略有哪些 ?
Redis 提供了 8 种数据淘汰策略,分为淘汰易失数据和淘汰全库数据两大类。易失数据淘汰策略包括:volatile-lru、volatile-lfu、volatile-ttl 和 volatile-random;全库数据淘汰策略包括:allkeys-lru、allkeys-lfu 和 allkeys-random。此外,还有 no-eviction 策略,禁止驱逐数据,当内存不足时新写入操作会报错。
44 16
|
10天前
|
缓存 NoSQL 关系型数据库
大厂面试高频:如何解决Redis缓存雪崩、缓存穿透、缓存并发等5大难题
本文详解缓存雪崩、缓存穿透、缓存并发及缓存预热等问题,提供高可用解决方案,帮助你在大厂面试和实际工作中应对这些常见并发场景。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:如何解决Redis缓存雪崩、缓存穿透、缓存并发等5大难题
|
11天前
|
缓存 NoSQL 关系型数据库
Redis和Mysql如何保证数据⼀致?
在项目中,为了解决Redis与Mysql的数据一致性问题,我们采用了多种策略:对于低一致性要求的数据,不做特别处理;时效性数据通过设置缓存过期时间来减少不一致风险;高一致性但时效性要求不高的数据,利用MQ异步同步确保最终一致性;而对一致性和时效性都有高要求的数据,则采用分布式事务(如Seata TCC模式)来保障。
46 14
|
11天前
|
存储 NoSQL 算法
Redis分片集群中数据是怎么存储和读取的 ?
Redis集群采用哈希槽分区算法,共有16384个哈希槽,每个槽分配到不同的Redis节点上。数据操作时,通过CRC16算法对key计算并取模,确定其所属的槽和对应的节点,从而实现高效的数据存取。
39 13
|
11天前
|
存储 NoSQL Redis
Redis的数据过期策略有哪些 ?
Redis 采用两种过期键删除策略:惰性删除和定期删除。惰性删除在读取键时检查是否过期并删除,对 CPU 友好但可能积压大量过期键。定期删除则定时抽样检查并删除过期键,对内存更友好。默认每秒扫描 10 次,每次检查 20 个键,若超过 25% 过期则继续检查,单次最大执行时间 25ms。两者结合使用以平衡性能和资源占用。
34 11
|
11天前
|
监控 NoSQL 测试技术
【赵渝强老师】Redis的AOF数据持久化
Redis 是内存数据库,提供数据持久化功能,支持 RDB 和 AOF 两种方式。AOF 以日志形式记录每个写操作,支持定期重写以压缩文件。默认情况下,AOF 功能关闭,需在 `redis.conf` 中启用。通过 `info` 命令可监控 AOF 状态。AOF 重写功能可有效控制文件大小,避免性能下降。
|
11天前
|
存储 监控 NoSQL
【赵渝强老师】Redis的RDB数据持久化
Redis 是内存数据库,提供数据持久化功能以防止服务器进程退出导致数据丢失。Redis 支持 RDB 和 AOF 两种持久化方式,其中 RDB 是默认的持久化方式。RDB 通过在指定时间间隔内将内存中的数据快照写入磁盘,确保数据的安全性和恢复能力。RDB 持久化机制包括创建子进程、将数据写入临时文件并替换旧文件等步骤。优点包括适合大规模数据恢复和低数据完整性要求的场景,但也有数据完整性和一致性较低及备份时占用内存的缺点。
|
1月前
|
存储 缓存 NoSQL
数据的存储--Redis缓存存储(一)
数据的存储--Redis缓存存储(一)
|
1月前
|
消息中间件 缓存 NoSQL
Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。
【10月更文挑战第4天】Redis 是一个高性能的键值对存储系统,常用于缓存、消息队列和会话管理等场景。随着数据增长,有时需要将 Redis 数据导出以进行分析、备份或迁移。本文详细介绍几种导出方法:1)使用 Redis 命令与重定向;2)利用 Redis 的 RDB 和 AOF 持久化功能;3)借助第三方工具如 `redis-dump`。每种方法均附有示例代码,帮助你轻松完成数据导出任务。无论数据量大小,总有一款适合你。
76 6
|
11天前
|
存储 缓存 NoSQL
【赵渝强老师】基于Redis的旁路缓存架构
本文介绍了引入缓存后的系统架构,通过缓存可以提升访问性能、降低网络拥堵、减轻服务负载和增强可扩展性。文中提供了相关图片和视频讲解,并讨论了数据库读写分离、分库分表等方法来减轻数据库压力。同时,文章也指出了缓存可能带来的复杂度增加、成本提高和数据一致性问题。
【赵渝强老师】基于Redis的旁路缓存架构