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键值对来说，键总是字符串对象，而值才是上述五种类型其中一种。

• 编码 对象的ptr指针指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定。encoding属性记录了对象所使用的编码， 也即是说这个对象使用了什么数据结构作为对象的底层实现，可选的对象编码如下。

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

通过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常用的字符串对象命令

列表对象

源码文件：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 五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

注：常用命令如下：

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