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
相关文章
|
7天前
|
存储 缓存 关系型数据库
滴滴面试:单表可以存200亿数据吗?单表真的只能存2000W,为什么?
40岁老架构师尼恩在其读者交流群中分享了一系列关于InnoDB B+树索引的面试题及解答。这些问题包括B+树的高度、存储容量、千万级大表的优化、单表数据量限制等。尼恩详细解释了InnoDB的存储结构、B+树的磁盘文件格式、索引数据结构、磁盘I/O次数和耗时,以及Buffer Pool缓存机制对性能的影响。他还提供了实际操作步骤,帮助读者通过元数据找到B+树的高度。尼恩强调,通过系统化的学习和准备,可以大幅提升面试表现,实现“offer直提”。相关资料和PDF可在其公众号【技术自由圈】获取。
|
1天前
|
SQL 关系型数据库 MySQL
|
12天前
|
监控 Java easyexcel
面试官:POI大量数据读取内存溢出?如何解决?
【10月更文挑战第14天】 在处理大量数据时,使用Apache POI库读取Excel文件可能会导致内存溢出的问题。这是因为POI在读取Excel文件时,会将整个文档加载到内存中,如果文件过大,就会消耗大量内存。以下是一些解决这一问题的策略:
38 1
|
15天前
|
NoSQL Java API
美团面试:Redis锁如何续期?Redis锁超时,任务没完怎么办?
在40岁老架构师尼恩的读者交流群中,近期有小伙伴在面试一线互联网企业时遇到了关于Redis分布式锁过期及自动续期的问题。尼恩对此进行了系统化的梳理,介绍了两种核心解决方案:一是通过增加版本号实现乐观锁,二是利用watch dog自动续期机制。后者通过后台线程定期检查锁的状态并在必要时延长锁的过期时间,确保锁不会因超时而意外释放。尼恩还分享了详细的代码实现和原理分析,帮助读者深入理解并掌握这些技术点,以便在面试中自信应对相关问题。更多技术细节和面试准备资料可在尼恩的技术文章和《尼恩Java面试宝典》中获取。
美团面试:Redis锁如何续期?Redis锁超时,任务没完怎么办?
|
21天前
|
NoSQL 算法 Redis
Redis面试篇
Redis面试篇
31 5
|
2天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
15天前
|
存储 关系型数据库 MySQL
面试官:MySQL一次到底插入多少条数据合适啊?
本文探讨了数据库插入操作的基础知识、批量插入的优势与挑战,以及如何确定合适的插入数据量。通过面试对话的形式,详细解析了单条插入与批量插入的区别,磁盘I/O、内存使用、事务大小和锁策略等关键因素。最后,结合MyBatis框架,提供了实际应用中的批量插入策略和优化建议。希望读者不仅能掌握技术细节,还能理解背后的原理,从而更好地优化数据库性能。
|
18天前
|
存储 大数据 数据库
Android经典面试题之Intent传递数据大小为什么限制是1M?
在 Android 中,使用 Intent 传递数据时存在约 1MB 的大小限制,这是由于 Binder 机制的事务缓冲区限制、Intent 的设计初衷以及内存消耗和性能问题所致。推荐使用文件存储、SharedPreferences、数据库存储或 ContentProvider 等方式传递大数据。
26 0
|
20天前
|
缓存 NoSQL 算法
面试题:Redis如何实现分布式锁!
面试题:Redis如何实现分布式锁!
|
3月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。