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

本文涉及的产品
云数据库 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
相关文章
|
6天前
|
缓存 NoSQL Java
Java高并发实战:利用线程池和Redis实现高效数据入库
Java高并发实战:利用线程池和Redis实现高效数据入库
24 0
|
8天前
|
存储 NoSQL Java
【面试宝藏】Redis 常见面试题解析
Redis 是内存数据结构存储系统,用作数据库、缓存和消息中间件,支持字符串、哈希、列表等数据类型。它的优点包括高性能、原子操作、持久化和复制。相比 Memcached,Redis 提供数据持久化、丰富数据结构和发布/订阅功能。Redis 采用单线程模型,但通过 I/O 多路复用处理高并发。常见的面试问题涉及持久化机制、过期键删除、回收策略、集群和客户端等。
34 4
|
9天前
|
存储 算法 NoSQL
百度面试:如何用Redis实现限流?
百度面试:如何用Redis实现限流?
26 2
|
4天前
|
NoSQL 关系型数据库 MySQL
实时计算 Flink版产品使用问题之如何确保多并发sink同时更新Redis值时,数据能按事件时间有序地更新并且保持一致性
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
|
7天前
|
安全 Java 数据安全/隐私保护
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(二)
15 0
|
7天前
|
JSON 安全 Java
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
Java基础4-一文搞懂String常见面试题,从基础到实战,更有原理分析和源码解析!(一)
19 0
|
8天前
|
SQL 分布式计算 NoSQL
使用Spark高效将数据从Hive写入Redis (功能最全)
使用Spark高效将数据从Hive写入Redis (功能最全)
|
8天前
|
存储 缓存 NoSQL
【面试宝藏】Redis 常见面试题解析其二
Redis 高级面试题涵盖了哈希槽机制、集群的主从复制、数据丢失可能性、复制机制、最大节点数、数据库选择、连通性测试、事务操作、过期时间和内存优化等。Redis 使用哈希槽实现数据分布,主从复制保障高可用,异步复制可能导致写操作丢失。集群最大支持1000个节点,仅允许单数据库。可通过 `ping` 命令测试连接,使用 `EXPIRE` 设置过期时间,`MULTI/EXEC` 等进行事务处理。内存优化包括合理数据类型、设置过期时间及淘汰策略。Redis 可用作缓存、会话存储、排行榜等场景,使用 `SCAN` 查找特定前缀键,列表实现异步队列,分布式锁则通过 `SET` 命令和 Lua 脚本实现。
22 5
|
10天前
|
分布式计算 NoSQL 大数据
MaxCompute产品使用合集之自定义udf连接云上vpc网络的redis获取数据的步骤是什么
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
|
12天前
|
存储 消息中间件 缓存
Redis--初级面试题
Redis--初级面试题