Redis源码阅读(九) 对象系统

发表于 | 更新于 | 分类于

Redis定义了一些基本了数据类型，如简单动态字符串、字典、跳跃表、压缩列表等等，但并未使用这些结构作为对象存储，而是定义了一套对象系统，底层使用这些数据结构进行存储，这个对象系统包括了字符串对象、列表对象、哈希对象、集合对象、有序集合对象，Redis针对不同的使用场景，设置不同的数据结构，优化其使用效率。

Redis通过对象引用计数进行内存的自动回收，并通过引用计数实现对象共享机制，Redis对象还保存了最近一次访问的时间(或历史访问频率)，通过LRU(LFU)算法对其进行优化。

1. redis对象定义

  • redis对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct redisObject {                                                                            
    // 4bit，表示对象类型, OBJ_STRING ...                                                              
    unsigned type:4;                                                                                    
    // 4bit，表示编码类型, OBJ_ENCODING_RAE ...                                                        
    unsigned encoding:4;                                                                                
    // LRU最后一次被访问的时间; LFU历史访问频次                                                                            
    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;

2. 对象类型

redis对象使用type(4bit)字段表示该对象的类型，Redis数据库中键总是一个字符串对象，而值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象和模块对象。

常量 对象 TYPE命令输出
OBJ_STRING 0 字符串对象 “string”
OBJ_LIST 1 列表对象 “list”
OBJ_SET 2 集合对象 “set”
OBJ_ZSET 3 有序集合对象 “zset”
OBJ_HASH 4 哈希对象 “hash”
OBJ_MODULE 5 模块对象（特殊的类型） 模块名称

3. 对象编码

redis对象的ptr属性指向底层的数据结构，这些数据结构由encoding属性决定。

常量 底层数据结构 encoding 命令输出 备注
OBJ_ENCODING_RAW 0 简单动态字符串 “raw”
OBJ_ENCODING_INT 1 long类型的整数 “int”
OBJ_ENCODING_HT 2 字典 “hashtable”
OBJ_ENCODING_ZIPMAP 3 压缩字典 —- 不会单独使用
OBJ_ENCODING_LINKEDLIST 4 双端链表 —- 不再用于列表对象
OBJ_ENCODING_ZIPLIST 5 压缩列表 “ziplist”
OBJ_ENCODING_INTSET 6 整数集合 “intset”
OBJ_ENCODING_SKIPLIST 7 跳跃表 “skiplist”
OBJ_ENCODING_EMBSTR 8 embstr类型sds “embstr”
OBJ_ENCODING_QUICKLIST 9 快速列表 “quicklist”

每种对象都存在不同的编码方式。

对象类型 编码类型 描述
STRING INT 使用数值存储
STRING EMBSTR 不被修改的字符串，并且不能超过44字节
STRING RAW 超过44字节的一般字符串
LIST QUICKLIST 列表对象的编码仅使用QUICKLIST
HASH HT 字典编码的哈希对象
HASH ZIPLIST 压缩列表编码的哈希对象
SET HT 字典编码的集合对象
SET INTSET 整数集合编码的集合对象
ZSET QUICKLIST 跳跃表编码有序集合对象
ZSET ZIPLIST 压缩列表编码有序集合对象

4. 内存优化

4.1 引用计数

C语言没有垃圾回收机制(GC)，所以Redis自己实现了基于引用计数的内存回收，通过跟踪引用计数，在适当的时候释放内存空间，优化性能。

对象的引用计数会随对象的使用而发生改变

  • 创建新对象时，引用计数+1
  • 对象被使用时，引用计数+1
  • 对象不在被使用时，引用计数-1
  • 引用计数减为0时，释放占用内存空间
  • [0, 10000)范围的整数引用计数设为INT_MAX，用做整数共享
函数 作用
incrRefCount 对象引用计数+1
decrRefCount 对象引用计数-1，当计数为0时，根据其编码释放底层内存空间
resetRefCount 对象引用计数设置为0，但不释放内存，通常用在 创建对象后调用会增加引用计数的函

4.2 对象共享

Redis通过引用计数实现了对象共享的机制，如[0, 10000)范围的数字就是共享整数，若redis中的值在此范围内，则会通过指针指向这些整数。

当服务器将共享对象设置为值的时候，需要检查共享对象和目标对象是否完全相同，只有完全相同才会进行共享，检查对象完全相同的代价取决于对象的复杂程度，基础类型耗时很少，但越复杂的对象则需要越大的代价，尽管可以节省内存，但CPU耗时会增加，所以Redis目前只共享整数

4.3 命令

Redis使用了LRU和LFU算法记录对象被访问的情况，默认开启LRU算法，LFU算法需通过配置文件开启。

使用OBJECT命令可以获取对象内存有关的信息。

1
2
3
4
5
6
# 获取对象的信息
-OBJECT [refcount|encoding|idletime|freq] key
	- refcount：获取对象的引用计数
	- encoding：获取对象的编码类型
	- idletime：获取对象已经存在的时间，LFU算法下不可使用
	- freq：获取对象被访问的频次，LFU算法下可用

使用TYPE命令可以获取对象的类型

1
2
# 获取key对象的类型，string, list, set, zset, hash
-TYPE key

5. 源码剖析

  • 减少对象引用计数，当引用计数为0时释放该对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void decrRefCount(robj *o) {
    if (o->refcount == 1) {
        switch(o->type) {
        case OBJ_STRING: freeStringObject(o); break;
        case OBJ_LIST: freeListObject(o); break;
        case OBJ_SET: freeSetObject(o); break;
        case OBJ_ZSET: freeZsetObject(o); break;
        case OBJ_HASH: freeHashObject(o); break;
        case OBJ_MODULE: freeModuleObject(o); break;
        default: serverPanic("Unknown object type"); break;
        }
        zfree(o);
    } else {
        if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
        if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--;
    }
}
  • 创建一个redis对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
robj *createObject(int type, void *ptr) {
    // 分配内存空间
    robj *o = zmalloc(sizeof(*o));
    // 对象类型
    o->type = type;
    // 对象编码
    o->encoding = OBJ_ENCODING_RAW;
    // 对象实际存储指针
    o->ptr = ptr;
    // 对象引用计数
    o->refcount = 1;

    /* Set the LRU to the current lruclock (minutes resolution), or
     * alternatively the LFU counter. */
    // 使用LRU或者LFU算法,用于内存淘汰
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    return o;
}
  • 创建一个quicklist列表对象
1
2
3
4
5
6
7
8
9
robj *createQuicklistObject(void) {
    // 创建新的quicklist
    quicklist *l = quicklistCreate();
    // 创建列表对象
    robj *o = createObject(OBJ_LIST,l);
    // 编码方式QUICKLIST
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
}
  • 创建一个dict集合对象
1
2
3
4
5
6
7
8
9
robj *createSetObject(void) {
    // 创建一个字典
    dict *d = dictCreate(&setDictType,NULL);
    // 创建集合对象
    robj *o = createObject(OBJ_SET,d);
    // 编码方式OBJ_ENCODING_HT
    o->encoding = OBJ_ENCODING_HT;
    return o;
}
  • 创建一个intset集合对象
1
2
3
4
5
6
7
8
9
robj *createIntsetObject(void) { // 创建一个整数结合
    // 创建整数集合
    intset *is = intsetNew();
    // 创建集合对象
    robj *o = createObject(OBJ_SET,is);
    // 编码方式OBJ_ENCODING_INTSET
    o->encoding = OBJ_ENCODING_INTSET;
    return o;
}
  • 创建一个ziplist哈希对象
1
2
3
4
5
6
7
8
9
robj *createHashObject(void) {
    // 创建ziplist
    unsigned char *zl = ziplistNew();
    // 创建哈希对象
    robj *o = createObject(OBJ_HASH, zl);
    // 编码方式 OBJ_ENCODING_ZIPLIST
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}
  • 创建一个skiplist有序集合对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
robj *createZsetObject(void) {
    // 分配内存空间
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;

    // 创建哈希表
    zs->dict = dictCreate(&zsetDictType,NULL);
    // 创建跳跃表
    zs->zsl = zslCreate();
    // 创建有序集合对象
    o = createObject(OBJ_ZSET,zs);
    // 编码方式 OBJ_ENCODING_SKIPLIST
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}
  • 创建一个ziplist有序集合对象
1
2
3
4
5
6
7
8
9
robj *createZsetZiplistObject(void) {
    // 创建ziplist
    unsigned char *zl = ziplistNew();
    // 创建有序集合对象
    robj *o = createObject(OBJ_ZSET,zl);
    // 编码方式OBJ_ENCODING_ZIPLIST
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}