Redis数据结构详解

Redis 常见数据结构有五种：String、List、Hash、Set、Zset。这些数据结构都是基于redis自主实现的结构，不熟悉的读者可以参考这篇博客：基本数据结构-CSDN博客

redisObject

Redis 中所有的基本结构都会被封装为 redisObject，redisObject的定义如下：

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：对象类型，分别是string、hash、list、set、zset占四个比特位；

/*-----------------------------------------------------------------------------
 * Data types
 *----------------------------------------------------------------------------*/

/* A redis object, that is a type able to hold a string / list / set */

/* 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. */

/* The "module" object type is a special one that signals that the object
 * is one directly managed by a Redis module. In this case the value points
 * to a moduleValue struct, which contains the object value (which is only
 * handled by the module itself) and the RedisModuleType struct which lists
 * function pointers in order to serialize, deserialize, AOF-rewrite and
 * free the object.
 *
 * Inside the RDB file, module types are encoded as OBJ_MODULE followed
 * by a 64 bit module type ID, which has a 54 bits module-specific signature
 * in order to dispatch the loading to the right module, plus a 10 bits
 * encoding version. */
#define OBJ_MODULE 5    /* Module object. */
#define OBJ_STREAM 6    /* Stream object. */

• encoding：底层编码方式，共有十一种，占4个比特位；

/* 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 */

• lru:LRU_BITS：该对象最后一次被访问的时间。
• refcount：对象的引用计数，为零时代表无人引用，可以被回收。
• ptr：指向实际存储数据的内存。

 Redis 中会根据存储的数据类型不同，选择不同的编码方式，共包含 11 种不同类型:

每种类型数据类型的使用的编码如下：

String

String数据结构由三种编码方式：RAW、EMBSTR 、Int

String基本编码方式是 RAW, 基于简单动态字符串 (SDS) 实现，存储上限为 512mb。当编码方式为 RAW 时，redisObject的结构如下：

如果存储的 SDS 长度小于 44 字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续空间。申请内存时只 需要调用一次内存分配函数，效率更高。

如果存储的字符串是整数值，并且大小在 LONG MAX 范围内，则会采用 INT 编码：直接将数据保存在 RedisObject 的 ptr 指针位置 (刚好 8 字节), 不再需要 SDS 了。

List 

List是一个双端链表结构，在redis的 3.2 版本之前采用 ZipList LinkedList 来实现 List，当元素数量小于 512 字节并且元素小于 64 字节时采用 ZipList 编码，超过采用 LinkedList 编码。在 3.2 版本之后，Redis 统一采用 QuickList 来实现。大致结构如下：

Set

Set 是 Redis 中的单列集合，满足下列特点：

• 不保证有序性
• 保证元素唯一，可以判断元素是否存在
• 求交集、并集、差集

Redis采用的是 IntSet 与 HT 编码实现 Set :

• 为了查询效率和唯一性，set 采用 HT 编码 (Dict)。Dict 中的 key 用来存储元素，value 统一为 null
• 当存储的所有数据都是整数，并且元素数量不超过 set-maxx-intset-entries 时，Set 会采用 IntSet 编码，以节省内存。

/* Factory method to return a set that *can* hold "value". When the object has
 * an integer-encodable value, an intset will be returned. Otherwise a regular
 * hash table. */
robj *setTypeCreate(sds value) {
    //判断value是否是数值类型 long long
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)
        //如果是数值类型，则采用IntSet编码
        return createIntsetObject();
    //否则采用默认HT编码
    return createSetObject();
}

ZSet

ZSet就是SortedSet，其中每一个元素都需要指定一个score值和member值，并且可以根据score排序，member必须唯一同时可以根据member查询分数。

因此，zset 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。哪种编码结构可以满足？

• skipList: 可以排序，并且可以同时存储 score 和 ele 值 (member)
• HT (Dict): 可以键值存储，并且可以根据 key 找 value

 Redis的选择是 skipList+Ht，Redis封装了一份zset结构：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

在 zset 中存储跳表与哈希表的指针，再通过 ptr 指向 zset。而当元素数量不多时，HT 和 SkipList 的优势不明显，而且更耗内在存。因此 zset 还会采用 ZipList 结构来节省内存，不过需要 同时满足两个条件:

• 元素数量小于 zset_max_ziplist_entries, 默认值 128
• 每个元素都小于 zset_max_ziplist_value 字节，默认值 64

Hash

Hash 结构与 Redis 中的 Zset 非常类似，都是键值存储 ，都需求根据键获取值，键必须唯一

而区别如下：zset 的键是 member, 值是 score。hash 的键和值都是任意值 zset 要根据 score 排序；hash 则无需排序

因此，Hash 底层采用的编码与 Zset 也基本一致，只需要把排序有有关的 SkipList 去掉即可

• Hash 结构默认采用 ZipList 编码，用以节省内存。ZipList 中相邻的两个 entry 分别保存 field 和 value
• 当数据量较大时，Hash 结构会转为 HT 编码，也就是 Dict, 触发条件有两个:
• ZipList 中的元素数量超过了 hash-max-ziplist-entries (默认 512)
• ZipList 中的任意 entry 大小超过了 hash-max-ziplist-value (默认 64 字节)