相信平时工作中大家对于Redis基本的对象（如string、list、hash、set、zset）的使用都非常之熟练，但是对于其底层的实现可能有所忽略。前段时间一个面试官问我zset是用什么实现的，我记得是跳表（skiplist），但是对于为什么用跳表而不用红黑树，就回答不上来了。借此机会，对如上几种基本的数据对象的底层编码做个总结。

内容大多从各个Blog以及《Redis设计与实现》（有点老，小声bb）中总结的，后面附录了链接。【P{num}】表示此段内容在《Redis设计与实现》的页码。

另，redis中的key一定是一个字符串对象，而value可以是string对象、list对象、hash对象、set对象、zset对象等。我们一般说“使用redis的zset结构”是指“这个数据库key对应的value为zset对象”。

另，指令执行版本v3.2.2

Redis现有编码类型

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

string对象

> set  str01  123
OK
> OBJECT ENCODING str01
int
> set  str02  123DF
OK
> OBJECT ENCODING str02
embstr
> set  str03  123DFdhkjfkadhubcnkbfnebkdhjnbkhcavkbhejdakwghbcagvkebhwjavagkbhwnj
OK
> OBJECT ENCODING str03
raw

字符串对象的编码可以是int、embstr或raw。redisObject的指针指向简单动态字符串（simple dynamic string, SDS）。

1. 如果字符串对象保存的是整数，且这个整数可以用long类型开表示，那就编码为int类型；
2. 如果是字符串且长度<=44字节，编码为embstr（embedded string）；
3. 如果是长度大于44字节的字符串，编码为raw。

说说三者之间区别，int编码的范围是有符号long（64位），对于特定的方法如INCR、INCRBY、DECRBY，只能在int编码的对象上执行否则会报错。

> set x abc
OK
> INCR x
ERR value is not an integer or out of range

此外还要注意int编码对象的边界，INCR并不能永远正常执行下去，下面虽然看着有些奇怪，但INCR确实有可能越界。

> set y 9223372036854775805
OK
> INCR y
9223372036854778000
> INCR y
9223372036854778000
> INCR y
ERR increment or decrement would overflow

对于embstr、raw编码的字符串对象，两者的区别在于embstr会调用一次内存申请一整块内存，用以存储redisObject和ptr指向的sdshdr（SDS对象）。而raw则会分为两次去申请内存。反之，在释放内存时，embstr对象会释放一次，而raw对象需要分两次释放。【P65】。另外，embstr对象不具备任何修改函数，它是只读的。因此，如果embstr对象做了任何修改，它总会先变成一个raw字符串再做相应处理。int字符也可以通过APPEND等命令，使自己变为一个不符合约束（long）的raw对象[P67]。

list对象

在《Redis设计与实现》中说明到list的底层实现依赖于linkedlist（链表）和ziplist（压缩列表）。原先的说法是：

列表对象保存的所有字符串元素的长度都小于 64 字节并且保存的元素数量小于 512 个，使用 ziplist 编码；否则使用 linkedlist。

实际上在笔者所用的版本上已经是quicklist了。但是看了也不会亏，因为quicklist就是linkedlist和skiplist的结合版本。这里有同学写的很详细了，以下简单记录下自己的理解。

首先结合list对象的使用场景，它可以保证有序（写入和删除的顺序），可以在表的两端追加和删除数据，可以耗费O(N)的时间复杂度插入指定的位置或是删除指定的节点。那么最先想到结构是链表，但是链表的缺陷在于内存开销比较大且容易产生内存碎片（它的每个节点要额外维护两个指针；且双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片）。而ziplist由于是一整块连续内存，且每个节点只维护一个向前的指针，因此内存使用效率很高，ziplist的缺点也比较明显，它不利于扩展，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。因此原先的设计是通过一个阈值，将较大的ziplist转换为linkedlist，平衡内存利用率和处理效率。

那么我们看看quicklist是如何将linkedlist和ziplist结合起来，借用一张图可以看出，quicklist本质上还是一个双向链表，只不过链上节点保存了一个ziplist对象的引用（直白点：quicklist是ziplist链表）。

quicklist的存储结构

这种结合同时引入了一系列平衡问题。我们只从存储效率上分析一下：

• 每个quicklist节点上的ziplist越短，则内存碎片越多。内存碎片多了，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项，这就蜕化成一个普通的双向链表了。
• 每个quicklist节点上的ziplist越长，则为ziplist分配大块连续内存空间的难度就越大。这种情况的极端是整个quicklist只有一个节点，所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了。这么大的ziplist又需要整块的内存存储，降低了内存的利用率。

可见，一个quicklist节点上的ziplist要保持一个合理的长度。那到底多长合理呢？这可能取决于具体应用场景。实际上，Redis提供了一个配置参数list-max-ziplist-size（最新的版本这个参数改名为list-max-listpack-size），就是为了让使用者可以来根据自己的情况进行调整。参数说明详见redis.conf。

# lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

此外，由于list的使用特点（更频繁的操作list的头尾数据，中间数据操作较少），redis提供了list压缩配置list-compress-depth，例如改参数设置为2，表示quicklist两端各有2个（zipilist）节点不压缩。上图中绿色节点（数据指针指向quicklistLZF）就是被压缩的中间节点。参数详细说明如下。

# lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression.  The head and tail of the list
# are always uncompressed for fast push/pop operations.  settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
#    going from either the head or tail"
#    So: [head]->node->node->...->node->[tail]
#    [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
#    2 here means: don't compress head or head->next or tail->prev or tail,
#    but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0

hash

hash就比较简单了，它同样使用两种编码方式异构了hash对象——zipset和hashtable。同样的，hash对象编码选择受到配置项影响：

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

1. 对于ziplist，每当有新的键值对要加入到哈希对象时， 程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾， 因此：

• 保存了同一键值对的两个节点总是紧挨在一起， 保存键的节点在前， 保存值的节点在后；
• 先添加到哈希对象中的键值对会被放在压缩列表的表头方向， 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

2. 对于hashtable编码的哈希对象，它实际上使用字典dict.h/dict作为底层实现， 哈希对象中的每个键值对都使用一个字典键值对来保存：
   • 字典的每个键都是一个字符串对象， 对象中保存了键值对的键；
   • 字典的每个值都是一个字符串对象， 对象中保存了键值对的值。

Redis 中的字典由 dict.h/dict 结构表示：
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表，字典由两张哈希表构成，其中一张用来rehash
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

Redis 字典所使用的哈希表hashtable由 dict.h/dictht 结构定义：
typedef struct dictht {
    // 哈希表数组，桶
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表。链地址法，用来解决hash冲突
    struct dictEntry *next;
} dictEntry;

set

set的编码可以是 intset 或者 hashtable 。

intset 编码的集合对象使用整数集合作为底层实现，先来复习一下intset 的结构：

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

contents 数组是整数集合的底层实现： 整数集合的每个元素都是 contents 数组的一个数组项（item）， 各个项在数组中按值的大小从小到大有序地排列， 并且数组中不包含任何重复项。为了验证一下是不是真的有序，我们可以通过下面命令验证，此时SISMEMBER key member指令的时间复杂度为O(lgN)（通过二分查找）。

> sadd con 9
1
> sadd con 7
1
> sadd con 1
1
> OBject encoding con
intset
> SMEMBERS con
1
7
9

当set中的数据过多，或是成员长度较大就会转变为hashtable编码，此时set中的元素不再有序，SISMEMBER key member指令的时间复杂度为O(1)。

zset

zset由两种底层编码——ziplist和skiplist实现。简单数据用ziplist，复杂的用skiplist（具体参考下面两个参数说明）。

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

通过以下命令，可以看到zset编码的变化。

> zadd x 1 a
1
> OBject encoding x
ziplist
> zadd x 2 hdjakndiasdnjkasbdjkabsdkcjsnxasbjhknkcjaasdsdvhbjbjbjbjbjbjbjbjbjbkjbjkbvhjvhjbhjnasavcb
1
> OBject encoding x
skiplist

1. ziplist 编码的zset对象使用压缩列表作为底层实现， 每个集合元素使用两个紧挨在一起的压缩列表节点来保存， 第一个节点保存元素的成员（member）， 而第二个元素则保存元素的分值（score）。查看ziplist api可以知道，使用该种编码实现的zset对象的各种操作时间复杂度高，但是由于一般数据量非常小，所以是可以接受的。但是对于较大的数据量，使用ziplist的编码实现就不合适了。
2. skiplist 编码的有序集合对象使用 zset 结构作为底层实现， 一个 zset 结构同时包含一个字典和一个跳跃表：

typedef struct zset {

    zskiplist *zsl;

    dict *dict;

} zset;

zset 结构中的 zsl 跳跃表按分值从小到大保存了所有集合元素， 每个跳跃表节点都保存了一个集合元素： 跳跃表节点的 object 属性保存了元素的成员， 而跳跃表节点的 score 属性则保存了元素的分值。 通过这个跳跃表， 程序可以对有序集合进行范围型操作， 比如 ZRANK 、 ZRANGE 等命令就是基于跳跃表 API 来实现的。

除此之外， zset 结构中的 dict 字典为有序集合创建了一个从成员到分值的映射， 字典中的每个键值对都保存了一个集合元素： 字典的键保存了元素的成员， 而字典的值则保存了元素的分值。 通过这个字典， 程序可以用 O(1) 复杂度查找给定成员的分值， ZSCORE 命令就是根据这一特性实现的， 而很多其他有序集合命令都在实现的内部用到了这一特性。

有序集合每个元素的成员都是一个字符串对象， 而每个元素的分值都是一个 double 类型的浮点数。 值得一提的是， 虽然 zset 结构同时使用跳跃表和字典来保存有序集合元素， 但这两种数据结构都会通过指针来共享相同元素的成员和分值， 所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值， 也不会因此而浪费额外的内存。

至于为什么同时需要skiplist和dict两种结构，一是需要skiplist的排序功能，二是需要dict的O(1)查找功能。

此外，这里补充下skiplist实现特点（skiplist的通用实现可以看这里，redis的skiplist特点可以参考这里，写的都很棒棒！）。

跳表我觉得就像是多层级的一个目录，跳表里面最有意思的就是上层索引的实现。它通过 randomLevel() 方法随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数，redis是32层），且该方法有p 的概率返回 1、p^2的概率返回 2、p^3的概率返回 3...。通过该函数，可以在插入一个元素时，随机的该元素所在索引层级高度。

redis中randomLevel() 函数的实现如下:

// redis中p=1/4；MaxLevel=32
randomLevel()
    level := 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

zskiplist 结构的定义如下：

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

跳跃表节点的实现由 redis.h/zskiplistNode 结构定义：

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层。这里也解释了为什么不需要实现向下的指针，因为level是一个数组。
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

那么最关键的一个问题，为啥不用红黑树，却用跳表呢？

1. 在范围查询的角度，跳表和B+树类似，它最下面一层是串联、有序的元素集合，因此可以非常高效的实现。但是对于红黑树，虽然在查询、插入、删除的节点上，平均时间复杂度与跳表相似，但是它的范围查询需要先中序遍历整个树，再做处理。因此不用红黑树。
2. AVT平局每个节点需要两个指针，但是redis中的跳表每个节点平均需要1.33个指针。
3. 从算法实现难度上来比较，SkipList比平衡树要简单得多（🥶红黑树，你懂的）。

参考

Redis字符串类型内部编码剖析
*Redis内部数据结构详解(5)——quicklist
SkipList数据结构分析
*Redis SkipList数据结构分析)
*Redis设计与实现
redis.conf