Redis源码阅读笔记-对象及其类型和编码

总结之《Redis设计与实现》

对象

Redis中是使用对象来便是数据库中的键和值。

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// server.h
...
#define LRU_BITS 24
...

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;
  • type: 4 bits, 表示是什么类型的Redis Object。
  • encoding: 4 bits, 类型的编码,是指定使用type的编码方式。
  • *ptr: 指向底层实现数据结构的指针。
  • lru: 24 bits, 记录了该对象最后一次被命令程序访问的时间。
  • refcount: 引用计数。

类型

对象 对象type的属性值 TYPE命令的输出
字符串 OBJ_STRING 0 “string”
列表 OBJ_LIST 1 “list”
集合 OBJ_SET 2 “set”
有序集合 OBJ_ZSET 3 “zset”
哈希 OBJ_HASH 4 “hash”

类型的编码

编码常量 对应底层数据结构
OBJ_ENCODING_RAW 0 简单动态字符串,只有string类型才会使用这个encoding值
OBJ_ENCODING_INT 1 long类型的整数
OBJ_ENCODING_HT 2 字典dict
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 表示一种与robj嵌入的特殊sds字符串
OBJ_ENCODING_QUICKLIST 9 quicklist快速列表

字符串对象

类型 编码 对象
OBJ_STRING OBJ_ENCODING_RAW 0 使用SDS字符串实现的字符串对象
OBJ_STRING OBJ_ENCODING_INT 1 使用整数值实现的字符串对象(整数值类型为long
OBJ_STRING OBJ_ENCODING_EMBSTR 8 使用SDS字符串实现的字符串对象,主要区别为在内存中字符串与对象相邻

OBJ_ENCODING_INT

INT编码字符串对象.png

robj中,有一个属性refcount是用来保存引用计数,对于字符串对象,Redis会在初始化服务器时,创建1万个字符串对象,包含了 0 ~ 9999 的整数字,当需要使用到这些整数字符串对象,服务器就会使用这些共享对象,而不需要新建整数对象。

OBJ_ENCODING_EMBSTROBJ_ENCODING_RAW的区别

如果对象中保存的字符串长度小于OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44将会使用OBJ_ENCODING_EMBSTR编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//object.c
/* Create a string object with EMBSTR encoding if it is smaller than
* OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
* used.
*
* The current limit of 39 is chosen so that the biggest string object
* we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
// 如果长度小于OBJ_ENCODING_EMBSTR_SIZE_LIMIT,将会调用createEmbeddedStringObject()创建 OBJ_ENCODING_EMBSTR 编码的字符串对象
return createEmbeddedStringObject(ptr,len);
else
// 如果长度大于OBJ_ENCODING_EMBSTR_SIZE_LIMIT,将会调用createRawStringObject()创建 OBJ_ENCODING_RAW 编码的字符串对象
return createRawStringObject(ptr,len);
}

OBJ_ENCODING_EMBSTR编码是用于专门保存短字符串的优化方式,一样会使用SDS结构来保存字符串。但OBJ_ENCODING_RAW编码会调用两次内存分配函数来分别创建robj和SDS字符串。而OBJ_ENCODING_EMBSTR编码则通过调用一次内存分配函数来分配一个连续的空间,空间中依次包含robj和SDS字符串。

RAW编码字符串对象.png
EMBSTR编码字符串对象.png

OBJ_ENCODING_EMBSTR优点:

  • 降低内存分配/释放的次数。
  • 减少内存碎片,使得OBJ_ENCODING_EMBSTR编码的字符串更好得利用SDS缓存带来的优势。
  • 当对OBJ_ENCODING_EMBSTR编码的字符串对象中字符串做任何改变,都会使其转换成OBJ_ENCODING_RAW编码。

创建函数代码

  • robj *createStringObjectFromLongLong(long long value)创建OBJ_ENCODING_INT编码的字符串对象:

    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
    // object.c

    robj *createStringObjectFromLongLong(long long value) {
    robj *o;
    // 如果值在 0 ~ 9999 之间,则返回共享的整数字符串对象
    if (value >= 0 && value < OBJ_SHARED_INTEGERS) {
    // 如果值在 0 ~ 9999 之间,则返回共享的整数字符串对象
    incrRefCount(shared.integers[value]);
    o = shared.integers[value];
    } else {

    if (value >= LONG_MIN && value <= LONG_MAX) {
    // 如果值是在 long 的范围内,则直接保存long类型的整数值
    // 来创建整数字符串对象
    o = createObject(OBJ_STRING, NULL);
    o->encoding = OBJ_ENCODING_INT;
    o->ptr = (void*)((long)value);
    } else {
    // 如果值是在 long 的范围外,则使用SDS字符串来保存整数
    // 来创建整数字符串对象
    o = createObject(OBJ_STRING,sdsfromlonglong(value));
    }
    }
    return o;
    }
  • robj *createEmbeddedStringObject(const char *ptr, size_t len) 创建OBJ_ENCODING_EMBSTR编码的字符串对象:

    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
    /* Create a string object with encoding OBJ_ENCODING_EMBSTR, that is
    * an object where the sds string is actually an unmodifiable string
    * allocated in the same chunk as the object itself. */
    robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    // 申请robj、sdshdr和字符长度之和的内存
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    // sdshdr8 紧接着 robj
    struct sdshdr8 *sh = (void*)(o+1);

    // 初始化robj的属性值
    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    // 指向sds字符串结构
    o->ptr = sh+1;
    o->refcount = 1;
    // 设置lru访问时间
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
    o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    o->lru = LRU_CLOCK();
    }

    // sds字符串初始化
    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr) {
    memcpy(sh->buf,ptr,len);
    sh->buf[len] = '\0';
    } else {
    memset(sh->buf,0,len+1);
    }
    return o;
    }
  • robj *createRawStringObject(const char *ptr, size_t len)创建OBJ_ENCODING_RAW编码的字符串对象:

    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
    /* Create a string object with encoding OBJ_ENCODING_RAW, that is a plain
    * string object where o->ptr points to a proper sds string. */
    robj *createRawStringObject(const char *ptr, size_t len) {
    // 直接调用createObject()创建字符串对象
    return createObject(OBJ_STRING, sdsnewlen(ptr,len));
    }

    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;

    // 设置LRU程序访问时间
    /* Set the LRU to the current lruclock (minutes resolution), or
    * alternatively the LFU counter. */
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
    o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
    o->lru = LRU_CLOCK();
    }
    return o;
    }

列表对象

类型 编码 对象
OBJ_LIST OBJ_ENCODING_ZIPLIST 5 使用压缩列表创建的列表对象(在Redis 4.0.11代码中看,似乎没有使用该编码的列表对象了)
OBJ_LIST OBJ_ENCODING_QUICKLIST 9 使用快速列表创建的列表对象

在Redis 4.0.11代码中看,列表对象的底层实现,都采用快速列表(quicklist)实现了。

部分功能代码

  • robj *createQuicklistObject(void) 创建一个空的编码为OBJ_ENCODING_QUICKLIST的列表对象:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // object.c
    robj *createQuicklistObject(void) {
    // 创建一个空的快速链表
    quicklist *l = quicklistCreate();
    // 传入快速列表,创建列表对象,然后将编码指定为快速列表
    robj *o = createObject(OBJ_LIST,l);
    o->encoding = OBJ_ENCODING_QUICKLIST;
    return o;
    }
  • void listTypePush(robj *subject, robj *value, int where)value添加到列对象subject中,where控制是插入队列尾还是队列头:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // t_list.c

    void listTypePush(robj *subject, robj *value, int where) {
    // 判断subject是否为队列(4.0.11中所有队列的实现均为快速列表)
    if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
    // where 为 0 表示列表头,否则表示列表尾
    int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;

    // 将value解码
    // 实际上是判断value是哪种编码的字符串,如果是OBJ_ENCODING_INT类型的字符串
    // 则将其 整型值 转成一个sds字符串类型,并返回一个新的obj对象
    // 如果是 OBJ_ENCODING_EMBSTR 或 OBJ_ENCODING_RAW,则只是对value的引用值+1
    value = getDecodedObject(value);
    size_t len = sdslen(value->ptr);
    // 将value的值加入到快速列表中(头或尾)
    quicklistPush(subject->ptr, value->ptr, len, pos);
    // 判断value是否可以被释放
    // 如果value的refcount == 1, 将会调用对应释放函数
    // 如果value的refcount > 1, 则将其值减1
    decrRefCount(value);
    } else {
    serverPanic("Unknown list encoding");
    }
    }
  • robj *listTypePop(robj *subject, int where) 在队列subject中从where指定的头或者尾中弹出(pop)元素项,并返回:

    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
    robj *listTypePop(robj *subject, int where) {
    long long vlong;
    robj *value = NULL;

    // where 为 0 表示列表头,否则表示列表尾
    int ql_where = where == LIST_HEAD ? QUICKLIST_HEAD : QUICKLIST_TAIL;
    // 检查subject的编码是否为快速队列
    if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
    // 在快速队列中弹出一个元素项,并调用在快速列表的函数中调用listPopSaver()将返回值封装成robj
    // 如果元素项的值是(long long类型)整数,则写在vlong中,这时候需要自己将其组装成robj
    if (quicklistPopCustom(subject->ptr, ql_where, (unsigned char **)&value,
    NULL, &vlong, listPopSaver)) {
    if (!value)
    // 弹出的元素项是long long整数,封装成robj
    value = createStringObjectFromLongLong(vlong);
    }
    } else {
    serverPanic("Unknown list encoding");
    }
    return value;
    }

    void *listPopSaver(unsigned char *data, unsigned int sz) {
    return createStringObject((char*)data,sz);
    }

哈希对象

哈希对象的底层编码是压缩列表 (ziplist)和字典(dict,hashtable)。

类型 编码 对象
OBJ_HASH OBJ_ENCODING_ZIPLIST 5 压缩列表实现的哈希对象
OBJ_HASH OBJ_ENCODING_HT 2 字典(哈希表)实现的哈希对象

ZIPLISGT编码哈希对象.png

HT编码哈希对象.png

编码转换

在 Redis 4.0.11 中,当满足以下两条件之一时,OBJ_ENCODING_ZIPLIST编码的哈希对象,会转换成OBJ_ENCODING_HT编码的哈希对象:

  • 当哈希对象中键值对的数量大于OBJ_HASH_MAX_ZIPLIST_ENTRIES 512(该值可以通过配置hash-max-ziplist-entries改变)时,将进行编码转换。
  • 当哈希对象中的键字符串或者值字符串大于OBJ_HASH_MAX_ZIPLIST_VALUE 64(该值可以通过配置hash-max-ziplist-value改变)时,将进行编码转换。

默认情况下,Redis会使用OBJ_ENCODING_ZIPLIST编码,直至以上两种情况的其中一种发生。

PS: 从代码上看,目前只支持OBJ_ENCODING_ZIPLIST -> OBJ_ENCODING_HT,不支持OBJ_ENCODING_HT -> OBJ_ENCODING_ZIPLIST

部分功能代码

  • robj *createHashObject(void)创建一个空的哈希对象:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // object.c

    robj *createHashObject(void) {
    // 新建一个压缩列表
    unsigned char *zl = ziplistNew();
    // 创建一个哈希对象,并指定编码为压缩列表
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
    }
  • int hashTypeSet(robj *o, sds field, sds value, int flags) 将键field,值value添加到哈希对象o中:

    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    // t_hash.c

    /* Add a new field, overwrite the old with the new value if it already exists.
    * Return 0 on insert and 1 on update.
    *
    * By default, the key and value SDS strings are copied if needed, so the
    * caller retains ownership of the strings passed. However this behavior
    * can be effected by passing appropriate flags (possibly bitwise OR-ed):
    *
    * HASH_SET_TAKE_FIELD -- The SDS field ownership passes to the function.
    * HASH_SET_TAKE_VALUE -- The SDS value ownership passes to the function.
    *
    * When the flags are used the caller does not need to release the passed
    * SDS string(s). It's up to the function to use the string to create a new
    * entry or to free the SDS string before returning to the caller.
    *
    * HASH_SET_COPY corresponds to no flags passed, and means the default
    * semantics of copying the values if needed.
    *
    */
    #define HASH_SET_TAKE_FIELD (1<<0)
    #define HASH_SET_TAKE_VALUE (1<<1)
    #define HASH_SET_COPY 0
    // 将键`field`,值`value`添加到哈希对象`o`中,如果键`field`已经存在,将会用新值`value`覆盖旧值
    // flags的作用是标志是否要在函数中释放`filed`或者`value`
    int hashTypeSet(robj *o, sds field, sds value, int flags) {
    int update = 0;

    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
    // 如果hash对象是 压缩列表
    unsigned char *zl, *fptr, *vptr;

    // zl指向压缩列表
    zl = o->ptr;
    // 获取压缩列表中头元素向的位置
    fptr = ziplistIndex(zl, ZIPLIST_HEAD);
    if (fptr != NULL) {
    // 检查压缩列表中,是否已经包含键field
    fptr = ziplistFind(fptr, (unsigned char*)field, sdslen(field), 1);
    if (fptr != NULL) {
    // 如果键field已经存在,则在以下操作中更新对应的value
    /* Grab pointer to the value (fptr points to the field) */
    // vprt指向对应的值位置
    vptr = ziplistNext(zl, fptr);
    serverAssert(vptr != NULL);
    // 将更新标志位置为1
    update = 1;

    // 删除旧值
    /* Delete value */
    zl = ziplistDelete(zl, &vptr);
    // 添加新值
    /* Insert new value */
    zl = ziplistInsert(zl, vptr, (unsigned char*)value,
    sdslen(value));
    }
    }
    // 如果标志位 为 0,表示filed不在压缩队列中,需要插入
    // 如果标志位 为 1,表示已经更新,无须操作
    if (!update) {
    /* Push new field/value pair onto the tail of the ziplist */
    zl = ziplistPush(zl, (unsigned char*)field, sdslen(field),
    ZIPLIST_TAIL);
    zl = ziplistPush(zl, (unsigned char*)value, sdslen(value),
    ZIPLIST_TAIL);
    }
    o->ptr = zl;

    /* Check if the ziplist needs to be converted to a hash table */
    // 检查键值对的数量,看是否需要将底层实现转换编码为字典(哈希表)
    if (hashTypeLength(o) > server.hash_max_ziplist_entries)
    hashTypeConvert(o, OBJ_ENCODING_HT);
    } else if (o->encoding == OBJ_ENCODING_HT) {
    // 如果hash对象的编码为字典(哈希表)

    // 查找键filed是否已经存在,如果有这返回de
    dictEntry *de = dictFind(o->ptr,field);
    if (de) {
    // 值已经存在,把旧值释放掉
    sdsfree(dictGetVal(de));

    // 将新值value写入,通过flags判断是否需要释放value
    if (flags & HASH_SET_TAKE_VALUE) {
    dictGetVal(de) = value;
    value = NULL;
    } else {
    dictGetVal(de) = sdsdup(value);
    }
    update = 1;
    } else {
    // 插入新键值对

    sds f,v;
    // 通过flags判断是否需要释放field
    if (flags & HASH_SET_TAKE_FIELD) {
    f = field;
    field = NULL;
    } else {
    f = sdsdup(field);
    }

    // 通过flags判断是否需要释放value
    if (flags & HASH_SET_TAKE_VALUE) {
    v = value;
    value = NULL;
    } else {
    v = sdsdup(value);
    }
    // 往字典添加新键值对
    dictAdd(o->ptr,f,v);
    }
    } else {
    serverPanic("Unknown hash encoding");
    }

    /* Free SDS strings we did not referenced elsewhere if the flags
    * want this function to be responsible. */
    // 通过flags判断
    // 释放掉对应的failed或者value
    if (flags & HASH_SET_TAKE_FIELD && field) sdsfree(field);
    if (flags & HASH_SET_TAKE_VALUE && value) sdsfree(value);
    return update;
    }

集合对象

集合对象的底层编码是字典(dict,hashtable)和整数集合(intset)。

类型 编码 对象
OBJ_SET OBJ_ENCODING_HT 2 字典实现的集合对象
OBJ_SET OBJ_ENCODING_INTSET 6 整数集合实现的集合对象

HT编码集合对象.png

INTSET编码集合对象.png

编码转换

在 Redis 4.0.11 中,当满足以下两条件之一时,OBJ_ENCODING_INTSET编码的集合对象,会转换成OBJ_ENCODING_HT编码的集合对象:

  • 当集合中保存的元素,有1个不是整数时,OBJ_ENCODING_INTSET会转变为OBJ_ENCODING_HT
  • 当集合中保存的元素数量,超过OBJ_SET_MAX_INTSET_ENTRIES 512(可以通过设置set-max-intset-entries改变数值)时,OBJ_ENCODING_INTSET会转变为OBJ_ENCODING_HT

PS: 从代码上看,目前只支持OBJ_ENCODING_INTSET -> OBJ_ENCODING_HT,不支持OBJ_ENCODING_HT -> OBJ_ENCODING_INTSET

部分功能代码

  • robj *setTypeCreate(sds value) 通过值值value得类型来判断创建一个集合对象,这个方法并不会将值value放入到集合中:

    1
    2
    3
    4
    5
    6
    7
    robj *setTypeCreate(sds value) {
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
    // 判断值'value'是否为一个整数,如果是,则使用整数集合编码的集合对象
    return createIntsetObject();
    // 'value'值不是整数,使用字典编码的集合对象
    return createSetObject();
    }
  • int setTypeAdd(robj *subject, sds value) 将值value添加到集合subject中,如果值已经存在,函数返回0,否则返回1:

    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
    /* Add the specified value into a set.
    *
    * If the value was already member of the set, nothing is done and 0 is
    * returned, otherwise the new element is added and 1 is returned. */
    int setTypeAdd(robj *subject, sds value) {
    long long llval;
    if (subject->encoding == OBJ_ENCODING_HT) {
    // 如果集合编码是字典


    dict *ht = subject->ptr;
    // 往字典ht中添加键value
    // 如果键已经存在于ht, dictAddRaw()会返回NULL
    // 否则会返回一个哈希节点
    dictEntry *de = dictAddRaw(ht,value,NULL);
    if (de) {
    // 设置节点的键值
    // 由于是集合,所以字典节点的值设为NULL
    dictSetKey(ht,de,sdsdup(value));
    dictSetVal(ht,de,NULL);
    return 1;
    }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) {
    // 如果集合编码是 整数集合

    // 判断要插入的值value是否可以转成整数
    if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
    // 如果可以转成整数,则可以继续用 整数集合 编码

    uint8_t success = 0;
    // 尝试插入的键值
    // 如果成功则 success 为 1
    // 如果值已经存在,则success 为 0
    subject->ptr = intsetAdd(subject->ptr,llval,&success);
    if (success) {
    // 成功,检查集合对象中元素项的数量,如果超过限制,则转换编码为字典编码
    /* Convert to regular set when the intset contains
    * too many entries. */
    if (intsetLen(subject->ptr) > server.set_max_intset_entries)
    setTypeConvert(subject,OBJ_ENCODING_HT);
    return 1;
    }
    } else {
    // 如果不可以转成整数,则需要将编码转为 字典
    /* Failed to get integer from object, convert to regular set. */
    setTypeConvert(subject,OBJ_ENCODING_HT);

    // 转换后,字典插入键值
    /* The set *was* an intset and this value is not integer
    * encodable, so dictAdd should always work. */
    serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
    return 1;
    }
    } else {
    serverPanic("Unknown set encoding");
    }
    return 0;
    }

有序集合对象

有序集合对象的底层编码是压缩列表(ziplist)和跳跃表(skiplist)。

类型 编码 对象
OBJ_ZSET OBJ_ENCODING_ZIPLIST 6 压缩列表实现的有序集合对象
OBJ_ZSET OBJ_ENCODING_SKIPLIST 7 跳跃表实现的有序集合对象

压缩列表实现

压缩表内的集合元素按照分值从小到大排序,每个集合元素使用2个压缩表节点表示,第一个节点保存元素的成员(member),第二个节点保存元素的分值(score)。

ZIPLISGT编码有序集合对象.png

跳跃表实现

跳跃表的时序,是采用zset结构,zset中同时包含一个字典和一个跳跃表。

1
2
3
4
5
// server.h
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;

结构如图(图来之《Redis设计与实现》):

SKIPLIST编码有序集合对象.png

编码转换

在 Redis 4.0.11 中,当满足以下两条件之一时,OBJ_ENCODING_ZIPLIST编码的有序集合对象,会转换成OBJ_ENCODING_SKIPLIST编码的有序集合对象:

  • 有序集合中保存的元素数量大于等于OBJ_ZSET_MAX_ZIPLIST_ENTRIES 128(可以通过设置zset-max-ziplist-entries改变数值)时,OBJ_ENCODING_ZIPLIST会转变为OBJ_ENCODING_SKIPLIST;
  • 有序集合中保存的元素,有一个或以上的长度大于等于OBJ_ZSET_MAX_ZIPLIST_VALUE 64(可以通过设置zset-max-ziplist-value改变数值)时,OBJ_ENCODING_ZIPLIST会转变为OBJ_ENCODING_SKIPLIST

如果OBJ_ENCODING_SKIPLIST中的元素满足OBJ_ZSET_MAX_ZIPLIST_ENTRIES 128OBJ_ZSET_MAX_ZIPLIST_VALUE 64,也会编码为OBJ_ENCODING_ZIPLIST的。(PS: 在 Redis 4.0.11 中,只有执行ZINTERSTORE或者ZUNIONSTORE两个命令才会触发,因为在代码上看,zsetConvertToZiplistIfNeeded()函数只有在zunionInterGenericCommand()函数函数中有调用)。

部分功能代码

  • void zaddGenericCommand(client *c, int flags) ZADDZINCRBY命令的实现函数:

    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
    // t_zset.c

    /* This generic command implements both ZADD and ZINCRBY. */
    void zaddGenericCommand(client *c, int flags) {
    ...


    /* Lookup the key and create the sorted set if does not exist. */
    检查key是否在数据库中
    zobj = lookupKeyWrite(c->db,key);
    if (zobj == NULL) {
    // Key不在数据库中,则新建一个 有序集合对象

    if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
    if (server.zset_max_ziplist_entries == 0 ||
    server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
    { // 如果设置了”zset_max_ziplist_entries“为0,表示所有的有序集合对象 都以跳跃表实现
    // 检查输入的元素的字符长度是否超过了server.zset_max_ziplist_value,超过了则使用跳跃表编码的有序集合
    zobj = createZsetObject();
    } else {
    // 没有强制使用 跳跃表 编码
    // 而且
    // 输入的第一个元素字符长度小于server.zset_max_ziplist_value
    zobj = createZsetZiplistObject();
    }
    dbAdd(c->db,key,zobj);
    } else {
    if (zobj->type != OBJ_ZSET) {
    addReply(c,shared.wrongtypeerr);
    goto cleanup;
    }
    }

    ...
    }
  • int zsetAdd(robj *zobj, double score, sds ele, int *flags, double *newscore) 往有序集合对象zobj中添加分值为score的元素eleflags是传入的操作标识,同时也是函数结果标识;newscore如果不传入NULL,当使用ZADD_INCR的时候,会将新值写入newscore:

    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221

    // server.h
    /* Input flags. */
    #define ZADD_NONE 0
    #define ZADD_INCR (1<<0) /* Increment the score instead of setting it. */
    #define ZADD_NX (1<<1) /* Don't touch elements not already existing. */
    #define ZADD_XX (1<<2) /* Only touch elements already exisitng. */

    /* Output flags. */
    #define ZADD_NOP (1<<3) /* Operation not performed because of conditionals.*/
    #define ZADD_NAN (1<<4) /* Only touch elements already exisitng. */
    #define ZADD_ADDED (1<<5) /* The element was new and was added. */
    #define ZADD_UPDATED (1<<6) /* The element already existed, score updated. */

    // t_zset.c

    /* Add a new element or update the score of an existing element in a sorted
    * set, regardless of its encoding.
    *
    * The set of flags change the command behavior. They are passed with an integer
    * pointer since the function will clear the flags and populate them with
    * other flags to indicate different conditions.
    *
    * The input flags are the following:
    *
    * 对当前元素的分值进行增加,而不是更新操作。如果元素不存在,则以0当做之前的分值。
    * ZADD_INCR: Increment the current element score by 'score' instead of updating
    * the current element score. If the element does not exist, we
    * assume 0 as previous score.
    * 仅当元素不存在才执行操作
    * ZADD_NX: Perform the operation only if the element does not exist.
    * 仅当元素存在才执行操作
    * ZADD_XX: Perform the operation only if the element already exist.
    *
    * When ZADD_INCR is used, the new score of the element is stored in
    * '*newscore' if 'newscore' is not NULL.
    *
    * The returned flags are the following:
    * 返回结果的原因:
    *
    *
    * 给定的分值并不是一个数字
    * ZADD_NAN: The resulting score is not a number.
    * 元素是新增的
    * ZADD_ADDED: The element was added (not present before the call).
    * 元素的分值已经更新(说明元素不是新增的)
    * ZADD_UPDATED: The element score was updated.
    * 因为ZADD_NX和ZADD_XX的缘故,没有执行操作
    * ZADD_NOP: No operation was performed because of NX or XX.
    *
    * Return value:
    *
    * The function returns 1 on success, and sets the appropriate flags
    * ADDED or UPDATED to signal what happened during the operation (note that
    * none could be set if we re-added an element using the same score it used
    * to have, or in the case a zero increment is used).
    *
    * The function returns 0 on erorr, currently only when the increment
    * produces a NAN condition, or when the 'score' value is NAN since the
    * start.
    *
    * The commad as a side effect of adding a new element may convert the sorted
    * set internal encoding from ziplist to hashtable+skiplist.
    *
    * Memory managemnet of 'ele':
    *
    * The function does not take ownership of the 'ele' SDS string, but copies
    * it if needed. */
    // 函数返回1表示执行成功,0 表示失败,成功或者失败的理由可以参考flags的值
    int zsetAdd(robj *zobj, double score, sds ele, int *flags, double *newscore) {
    /* Turn options into simple to check vars. */
    // 如果incr不是0, 表示分值是相加操作
    int incr = (*flags & ZADD_INCR) != 0;
    // 如果nx不是0,则仅当元素不存在才执行操作
    int nx = (*flags & ZADD_NX) != 0;
    // 如果xx不是0,仅当元素存在才执行操作
    int xx = (*flags & ZADD_XX) != 0;
    *flags = 0; /* We'll return our response flags. */
    double curscore;

    // 判断传入的分值是否一个无效参数
    /* NaN as input is an error regardless of all the other parameters. */
    if (isnan(score)) {
    *flags = ZADD_NAN;
    return 0;
    }

    /* Update the sorted set according to its encoding. */
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
    // 编码为 压缩列表

    unsigned char *eptr;

    if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {
    // ele元素已经存在

    /* NX? Return, same element already exists. */
    if (nx) {
    // nx(则仅当元素不存在才执行操作)不为0
    // 原因写入flags
    *flags |= ZADD_NOP;
    return 1;
    }

    /* Prepare the score for the increment if needed. */
    if (incr) {
    // 分值相加操作

    score += curscore;
    if (isnan(score)) {
    *flags |= ZADD_NAN;
    return 0;
    }
    // 如果newscore不是NULL,写入newscore,让函数调用者可以得到最新的分值
    if (newscore) *newscore = score;
    }

    /* Remove and re-insert when score changed. */
    if (score != curscore) {
    // 分值变动了,将旧的节点删除,重新插入,使得重新排序
    zobj->ptr = zzlDelete(zobj->ptr,eptr);
    zobj->ptr = zzlInsert(zobj->ptr,ele,score);
    *flags |= ZADD_UPDATED;
    }
    return 1;
    } else if (!xx) {
    // ele元素不存在,且xx(仅当元素存在才执行操作)为0

    /* Optimize: check if the element is too large or the list
    * becomes too long *before* executing zzlInsert. */

    // 压缩列表的整数集合插入新节点
    zobj->ptr = zzlInsert(zobj->ptr,ele,score);

    // 检查整数集合的长度是否超出了“zset_max_ziplist_entries”而导致需要转换编码
    if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries)
    zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
    // 检查新插入元素ele的长度是否超出了“zset_max_ziplist_value”而导致需要转换编码
    if (sdslen(ele) > server.zset_max_ziplist_value)
    zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
    if (newscore) *newscore = score;
    *flags |= ZADD_ADDED;
    return 1;
    } else {
    *flags |= ZADD_NOP;
    return 1;
    }
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
    // 编码为 跳跃表

    zset *zs = zobj->ptr;
    zskiplistNode *znode;
    dictEntry *de;

    // 在字典中查找该元素ele是否已经存在
    de = dictFind(zs->dict,ele);
    if (de != NULL) {
    // ele已经存在

    /* NX? Return, same element already exists. */
    if (nx) {
    // nx(则仅当元素不存在才执行操作)不为0
    // 原因写入flags
    *flags |= ZADD_NOP;
    return 1;
    }
    curscore = *(double*)dictGetVal(de);

    /* Prepare the score for the increment if needed. */
    if (incr) {
    // 分值相加操作
    score += curscore;
    if (isnan(score)) {
    *flags |= ZADD_NAN;
    return 0;
    }

    // 如果newscore不是NULL,写入newscore,让函数调用者可以得到最新的分值
    if (newscore) *newscore = score;
    }

    /* Remove and re-insert when score changes. */
    if (score != curscore) {
    // 更新分值

    zskiplistNode *node;
    // 先删除旧的节点
    serverAssert(zslDelete(zs->zsl,curscore,ele,&node));
    // 重新以新的分值插入
    znode = zslInsert(zs->zsl,score,node->ele);
    /* We reused the node->ele SDS string, free the node now
    * since zslInsert created a new one. */
    node->ele = NULL;
    zslFreeNode(node);
    /* Note that we did not removed the original element from
    * the hash table representing the sorted set, so we just
    * update the score. */
    // 更新字典中的信息
    dictGetVal(de) = &znode->score; /* Update score ptr. */
    *flags |= ZADD_UPDATED;
    }
    return 1;
    } else if (!xx) {
    // ele存在于有序集合

    // 新建节点插入
    ele = sdsdup(ele);
    znode = zslInsert(zs->zsl,score,ele);
    serverAssert(dictAdd(zs->dict,ele,&znode->score) == DICT_OK);
    *flags |= ZADD_ADDED;
    if (newscore) *newscore = score;
    return 1;
    } else {
    *flags |= ZADD_NOP;
    return 1;
    }
    } else {
    serverPanic("Unknown sorted set encoding");
    }
    return 0; /* Never reached. */
    }

对象的内存回收

redisObject中的属性refcount是记录对象的引用计数

  • 对象初始化时refcount初始化为1;
  • 当对象被一个新(函数/请求/程序)使用时,refcount增1;
  • 当对象不再被一个(函数/请求/程序)使用时,refcount减1;
  • refcount为0时,所占用的内存会被释放。
函数 作用
void decrRefCount(robj *o) 引用计数减1,如果减1后等于0,则释放对象
void incrRefCount(robj *o) 引用计数增1
robj *resetRefCount(robj *obj) 将引用计数设为0,但不释放对象

使用refcount,可以实现对象共享,Redis会在初始化服务器时,创建1万个字符串对象,包含了 0 ~ 9999 的整数字,当需要使用到这些整数字符串对象,服务器就会使用这些共享对象,而不需要新建整数对象。