Redis对象机制分析

简介

Redis中提供的数据结构都使用了下面的redisObject进行包装，通过包装可以提供不同场景下使用不同的数据结构的实现。Redis的对象机制还使用了引用计数方式的内存回收机制。

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;

type值可选：

#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

encoding可选：

#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

结构的编码方案

String

编码策略如下：

• 若保存的为整数值，并且可以用long表示，使用int进行编码
• 若保存的为字符串值，并且长度大于32字节，使用SDS存储，编码格式为raw
• 若保存的为字符串值，并且长度小于32字节，使用embstr进行编码

embstr是对短字符串的优化编码，使用redisObject和sdshdr来表示字符串对象，embstr只调用一次内存分配函数来分配两个struct，raw编码使用两次内存分配函数分别完成分配。同理内存释放也如此。

List

编码策略如下：

• 列表对象字符串对象长度小于64字节，并且保存元素数量小于512，使用ziplist进行编码，否则使用linkedlist编码
• 上述两个阈值通过list-max-ziplist-value和list-max-ziplist-entries控制

Hash

编码策略如下：

• 保存的所有键值长度都小于64字节，并且键值对数量小于512个，满足这两个条件使用ziplist编码，否则使用hashtable编码
• 阈值由hash-max-ziplist-value和hash-max-ziplist-entries控制
• ziplist编码时，键值节点紧挨在一起，先添加的靠近表头
• hashtable编码时，键值对使用dictEntry存储，键使用StringObject，值使用StringObject

Set

编码策略如下：

• 集合对象保存的所有元素都是整数时，并且元素个数不超过512个，使用intset进行存储，否则使用hashtable存储
• 阈值通过set-max-intset-entries进行控制
• intset编码时，集合存储在整数集合中
• hashtable编码时，每个键都是StringObject，值为NULL

Zset

编码策略如下：

• 有序集合保存的元素数量小于128个，保存的所有成员长度都小于64字节，同时满足使用ziplist编码，否则使用skiplist编码，并使用hashtable进行辅助存储。
• 上述阈值使用zset-max-ziplist-entries和zset-max-ziplist-value来控制
• ziplist中有序集合元素按score从大到小排序。
• skiplist按照score从大到小保存了所有集合元素，支持范围查询等操作
  • 同时使用hashtable存储成员到score的映射（键为元素，值为score），通过hashtable可以在$O(1)$时间查到元素的score
  • skiplist和hashtable给你通过指针共享元素和score，因此不会浪费额外的内存。

为什么同时使用跳表 + 哈希表 来实现有序集合？

• 若只用hashtable实现，尽管可以在$O(1)$时间内找到元素对应的score，但是无法满足范围查找，例如ZRANGE等命令，hashtable完成排序至少需要$O(N * logN)$的时间以及$O(N)$的空间。
• 若只用skiplist实现，根据元素查找score的操作升到$O(logN)$的时间复杂度。