1.redis数据结构：一切皆redisObject

发表于 | 分类于 |
字数统计: 1.2k | 阅读时长 ≈ 6

​1. 如何阅读数据结构相关的源码

阅读redis数据结构相关的源码，可以从命令定义的地方看，这里就是所有命令的操作入口函数，点进去就知道每个命令底层是基于什么数据结构实现的了。commands.def文件里面redisCommandTable就是所有的命令的定义了。

1
2
3
4
5
struct COMMAND_STRUCT redisCommandTable[] = {
/* bitmap */
{MAKE_CMD("bitcount","Counts the number of set bits (population counting) in a string.","O(N)","2.6.0",CMD_DOC_NONE,NULL,NULL,"bitmap",COMMAND_GROUP_BITMAP,BITCOUNT_History,1,BITCOUNT_Tips,0,bitcountCommand,-2,CMD_READONLY,ACL_CATEGORY_BITMAP,BITCOUNT_Keyspecs,1,NULL,2),.args=BITCOUNT_Args},
....
}

2. 一切皆redisObject

1
2
3
4
5
6
7
8
9
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;
};

redis的所有数据是放在一个大的hash table（redis中叫dict）里面的，这个hash table里面key是string（redis里面的sds），value就是这个redisObject。这个value是一个抽象的数据结构，底层有不同的实现（甚至会有多个数据结构组成，比如zset的skiplist编码就是通过dict和skiplist一起实现的），统一封装成了一个redisObject的对象。

  • unsignedtype:4;有下面几种，用来区分这个对象是什么，我们说redis支持ZSET，就是这个字段定义的。

    1
    2
    3
    4
    5
    6
    7
    8
    #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. *
    #define OBJ_MODULE 5    /* Module object. */
    #define OBJ_STREAM 6    /* Stream object. */
    #define OBJ_TYPE_MAX 7  /* Maximum number of object types */

  • 每个redisObject底层可以有多种实现方式，这个是用unsigned encoding:4;字段表示的，比如ZSET类型的数据结构可能有LISTPACK和SKIPLIST的实现。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #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  /* No longer used: old hash encoding. */
    #define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
    #define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
    #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 listpacks */
    #define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
    #define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
    #define OBJ_ENCODING_LISTPACK_EX 12 /* Encoded as listpack, extended with metadata */

  • void *ptr;这是一个通用的指针，这里就是实际指向的底层的数据结构的对象了。

  • int refcount;这个是对这个对象的引用计数，创建对象计数设置为1，减少到0，对象会被释放，不同encoding调用不同的释放函数。

  • unsigned lru:LRU_BITS;这是用来实现lru的，这里不详细说了，后面专门介绍。

3. redisObject的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
​
/* Redis object implementation */
void decrRefCount(robj *o); 
void decrRefCountVoid(void *o);
void incrRefCount(robj *o);
robj *makeObjectShared(robj *o);
void freeStringObject(robj *o);
void freeListObject(robj *o);
void freeSetObject(robj *o);
void freeZsetObject(robj *o);
void freeHashObject(robj *o);
void dismissObject(robj *o, size_t dump_size);
robj *createObject(int type, void *ptr);
void initObjectLRUOrLFU(robj *o);
robj *createStringObject(const char *ptr, size_t len);
robj *createRawStringObject(const char *ptr, size_t len);
robj *createEmbeddedStringObject(const char *ptr, size_t len);
robj *tryCreateRawStringObject(const char *ptr, size_t len);
robj *tryCreateStringObject(const char *ptr, size_t len);
robj *dupStringObject(const robj *o);
int isSdsRepresentableAsLongLong(sds s, long long *llval);
int isObjectRepresentableAsLongLong(robj *o, long long *llongval);
robj *tryObjectEncoding(robj *o);
robj *tryObjectEncodingEx(robj *o, int try_trim);
robj *getDecodedObject(robj *o);
size_t stringObjectLen(robj *o);
robj *createStringObjectFromLongLong(long long value);
robj *createStringObjectFromLongLongForValue(long long value);
robj *createStringObjectFromLongLongWithSds(long long value);
robj *createStringObjectFromLongDouble(long double value, int humanfriendly);
robj *createQuicklistObject(int fill, int compress);
robj *createListListpackObject(void);
robj *createSetObject(void);
robj *createIntsetObject(void);
robj *createSetListpackObject(void);
robj *createHashObject(void);
robj *createZsetObject(void);
robj *createZsetListpackObject(void);
robj *createStreamObject(void);
robj *createModuleObject(moduleType *mt, void *value);
int getLongFromObjectOrReply(client *c, robj *o, long *target, const char *msg);
int getPositiveLongFromObjectOrReply(client *c, robj *o, long *target, const char *msg);
int getRangeLongFromObjectOrReply(client *c, robj *o, long min, long max, long *target, const char *msg);
int checkType(client *c, robj *o, int type);
int getLongLongFromObjectOrReply(client *c, robj *o, long long *target, const char *msg);
int getDoubleFromObjectOrReply(client *c, robj *o, double *target, const char *msg);
int getDoubleFromObject(const robj *o, double *target);
int getLongLongFromObject(robj *o, long long *target);
int getLongDoubleFromObject(robj *o, long double *target);
int getLongDoubleFromObjectOrReply(client *c, robj *o, long double *target, const char *msg);
int getIntFromObjectOrReply(client *c, robj *o, int *target, const char *msg);
char *strEncoding(int encoding);
int compareStringObjects(const robj *a, const robj *b);
int collateStringObjects(const robj *a, const robj *b);
int equalStringObjects(robj *a, robj *b);
unsigned long long estimateObjectIdleTime(robj *o);
void trimStringObjectIfNeeded(robj *o, int trim_small_values);
#define sdsEncodedObject(objptr) (objptr->encoding == OBJ_ENCODING_RAW || objptr->encoding == OBJ_ENCODING_EMBSTR)
​

4. decrRefCount

1
2
3
4
5
6
7
8
9
​
void decrRefCount(robj *o); // 减少引用数量，为0删除
void decrRefCountVoid(void *o); // 同上
void incrRefCount(robj *o); // 增加引用数量
robj *makeObjectShared(robj *o); // 创建一个永远存在的对象
​
#define OBJ_SHARED_REFCOUNT INT_MAX     /* Global object never destroyed. */
#define OBJ_STATIC_REFCOUNT (INT_MAX-1) /* Object allocated in the stack. */
#define OBJ_FIRST_SPECIAL_REFCOUNT OBJ_STATIC_REFCOUNT

对redisObject的引用数量的维护，还有一个增加引用数量的接口incrRefCount，以及另外一个没有再用的接口decrRefCountVoid。

引用有3种：

  • OBJ_SHARED_REFCOU NT是全局对象，永远不会被删除
  • OBJ_STATIC_REFCOUNT是栈上的对象
  • 其余的都是正常引用计数的对象

引用计数，可以用来共享对象，比如redis启动的时候，就会生成0-9999的共享对象，

还有一些协议共用的string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void createSharedObjects(void) {
    int j;
​
    /* Shared command responses */
    shared.ok = createObject(OBJ_STRING,sdsnew("+OK\r\n"));
    shared.emptybulk = createObject(OBJ_STRING,sdsnew("$0\r\n\r\n"));
    shared.czero = createObject(OBJ_STRING,sdsnew(":0\r\n"));
    shared.cone = createObject(OBJ_STRING,sdsnew(":1\r\n"));
    shared.emptyarray = createObject(OBJ_STRING,sdsnew("*0\r\n"));
    shared.pong = createObject(OBJ_STRING,sdsnew("+PONG\r\n"));
    shared.queued = createObject(OBJ_STRING,sdsnew("+QUEUED\r\n"));
    shared.emptyscan = createObject(OBJ_STRING,sdsnew("*2\r\n$1\r\n0\r\n*0\r\n"));
    shared.space = createObject(OBJ_STRING,sdsnew(" "));
    shared.plus = createObject(OBJ_STRING,sdsnew("+"));
    .....
}
codelover wechat
原创公众号
-----若有不妥，敬请斧正-----