redis数据结构(一) redisObject

Redis源码官方仓库,本文基于2020年9月8日时最新的release版本6.0.7,与《redis设计与实现(第二版》有部分不同。

Redis是由c实现的一个kv内存数据库。key和value都在内存中创建并维护,因此,Redis一定有着一套自己的内存管理机制。无论key还是value,在Redis中都是以redisObject的形式存在。

redisObject

我们先看一看redisObject的结构,位置是在src/server.h中。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    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;

以上变量名后跟冒号和数字,是c语言中的位域操作,在redisObject中,type:4表明type占4bit。在6.0.7版本中的LRU_BITS是24,因此lru属性是24bit,而1Byte(字节)=8bit。因此4+4+24恰好是32bits。

结构中各个成员含义如下:

type

记录了对象的类型,众所周知Redis中存在5种数据类型,也定义在src/server.h中。

/* The actual Redis Object */
#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */

像如上的5种数据类型一般是怎么使用的呢?Redis源码中有类似如下代码来创建一个redisObject:

robj *o = createObject(OBJ_STRING,sdsnewlen(NULL, newlen));

此时呢,o即是一个redisObject,对象oo->type就是OBJ_STRING。同理知另外四种类型。

type属性在源码种常常用在条件分支上,如if (ob->type == OBJ_STRING)或者if (checkType(client, o, OBJ_STRING))

PS: 由于Redis中的key一定是OBJ_STRING类型,因此一般所谓的字符串键or列表键,都是针对value而言。value对应的redisObject是什么类型,我们就称之为什么键。

encoding

对象的ptr指针指向对象的底层实现数据结构,即真正的值存放的位置。而encoding属性则是标识这些数据结构的属性。

encoding属性记录了对象所使用的编码,也即是说这个对象使用了什么数据结构作为对象的底层实现。目前来说,有以下编码(也定义在src/server.h中):

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

在《redis设计与实现》书中还只有8种编码,而最新的源码里面已经有10种了,其中,在3.2版本前后双端链表已经不再使用,取而代之的quicklist。而OBJ_ENCODING_STREAM是在5.0版本引入的。具体介绍可以看redis.cn

每种类型的对象都至少使用了两种不同的编码,下表中列出了每种类型的对象可以使用的编码:

类型编码对象
OBJ_STRINGOBJ_ENCODING_RAW使用简单动态字符串实现的字符串对象
OBJ_STRINGOBJ_ENCODING_INT使用整数值实现的字符串对象
OBJ_STRINGOBJ_ENCODING_EMBSTR使用embstr编码的简单动态字符串实现的字符串对象
OBJ_LISTOBJ_ENCODING_LINKEDLIST使用双端链表实现的列表对象,3.2版本后不再使用
OBJ_LISTOBJ_ENCODING_ZIPLIST使用压缩列表实现的列表对象
OBJ_LISTOBJ_ENCODING_QUICKLIST3.2版本引入的快速列表,用来取代双端链表
OBJ_SETOBJ_ENCODING_HT使用字典实现的集合对象
OBJ_SETOBJ_ENCODING_INTSET使用整数集合实现的集合对象
OBJ_ZSETOBJ_ENCODING_ZIPLIST使用压缩列表实现的有序集合对象
OBJ_ZSETOBJ_ENCODING_SKIPLIST使用跳跃表和字典实现的有序集合对象
OBJ_HASHOBJ_ENCODING_ZIPLIST使用压缩对象实现的哈希对象
OBJ_HASHOBJ_ENCODING_HT使用字典实现的哈希对象

lru

记录对象上次被访问的时间点,主要用于lru策略。当内存紧张时,淘汰对象所用。

Redis 对数据集占用内存的大小有「实时」的计算,当超出限额时,会淘汰超时的数据。

refcount

引用计数。由于c中没有自动回收机制,因此Redis自己实现了一套内存管理机制,采用的是引用计数法。

一般而言引用计数法会存在循环引用的问题,即AB两对象互相引用,但是在Redis中,所有对象都是redisObject,并且只有字符串对象会嵌套在其他四种对象之中,其余四种对象之间并不会互相引用,而由于Redis对于字符串对象存在对象共享的机制,因此两个对象永远不会存在互相引用的问题,所以不存在这个问题。

一起看下增/减引用的源码(定义在src/object.c中):

void incrRefCount(robj *o) {
    if (o->refcount < OBJ_FIRST_SPECIAL_REFCOUNT) {
        o->refcount++;
    } else {
        if (o->refcount == OBJ_SHARED_REFCOUNT) {
            /* Nothing to do: this refcount is immutable. */
        } else if (o->refcount == OBJ_STATIC_REFCOUNT) {
            serverPanic("You tried to retain an object allocated in the stack");
        }
    }
}

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;
        case OBJ_STREAM: freeStreamObject(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 是单进程单线程工作的,所以增加/减少引用的操作不必保证原子性,这在 memcache 中是做不到的(memcached 是多线程的工作模式,需要做到互斥)。

ptr

ptr就十分简单了,指向真正存放数据的数据结构。

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号