原文地址：https://www.xilidou.com/2018/03/12/redis-data/

这周开始学习 Redis，看看Redis是怎么实现的。所以会写一系列关于 Redis的文章。这篇文章关于 Redis 的基础数据。阅读这篇文章你可以了解：

• 动态字符串（SDS）
• 链表
• 字典

三个数据结构 Redis 是怎么实现的。

SDS

SDS （Simple Dynamic String）是 Redis 最基础的数据结构。直译过来就是”简单的动态字符串“。Redis 自己实现了一个动态的字符串，而不是直接使用了 C 语言中的字符串。

sds 的数据结构：

1
2
3
4
5
6
7
8
9
10
11

struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

所以一个 SDS 的就如下图：

所以我们看到，sds 包含3个参数。buf 的长度 len，buf 的剩余长度，以及buf。

为什么这么设计呢？

• 可以直接获取字符串长度。
  C 语言中，获取字符串的长度需要用指针遍历字符串，时间复杂度为 O(n)，而 SDS 的长度，直接从len 获取复杂度为 O(1)。

• 杜绝缓冲区溢出。
  由于C 语言不记录字符串长度，如果增加一个字符传的长度，如果没有注意就可能溢出，覆盖了紧挨着这个字符的数据。对于SDS 而言增加字符串长度需要验证 free的长度，如果free 不够就会扩容整个 buf，防止溢出。

• 减少修改字符串长度时造成的内存再次分配。
  redis 作为高性能的内存数据库，需要较高的相应速度。字符串也很大概率的频繁修改。 SDS 通过未使用空间这个参数，将字符串的长度和底层buf的长度之间的额关系解除了。buf的长度也不是字符串的长度。基于这个分设计 SDS 实现了空间的预分配和惰性释放。

  1. 预分配
     如果对 SDS 修改后，如果 len 小于 1MB 那 len = 2 * len + 1byte。 这个 1 是用于保存空字节。
     如果 SDS 修改后 len 大于 1MB 那么 len = 1MB + len + 1byte。
  2. 惰性释放
     如果缩短 SDS 的字符串长度，redis并不是马上减少 SDS 所占内存。只是增加 free 的长度。同时向外提供 API 。真正需要释放的时候，才去重新缩小 SDS 所占的内存

• 二进制安全。
  C 语言中的字符串是以 ”\0“ 作为字符串的结束标记。而 SDS 是使用 len 的长度来标记字符串的结束。所以SDS 可以存储字符串之外的任意二进制流。因为有可能有的二进制流在流中就包含了”\0“造成字符串提前结束。也就是说 SDS 不依赖 “\0” 作为结束的依据。

• 兼容C语言
  SDS 按照惯例使用 ”\0“ 作为结尾的管理。部分普通C 语言的字符串 API 也可以使用。

链表

C语言中并没有链表这个数据结构所以 Redis 自己实现了一个。Redis 中的链表是：

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

非常典型的双向链表的数据结构。

同时为双向链表提供了如下操作的函数：

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

/*
 * 双端链表迭代器
 */
typedef struct listIter {

    // 当前迭代到的节点
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

/*
 * 双端链表结构
 */
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

    // 链表所包含的节点数量
    unsigned long len;

} list;

链表的结构比较简单，数据结构如下：

总结一下性质：

• 双向链表，某个节点寻找上一个或者下一个节点时间复杂度 O(1)。
• list 记录了 head 和 tail，寻找 head 和 tail 的时间复杂度为 O(1)。
• 获取链表的长度 len 时间复杂度 O(1)。

字典

字典数据结构极其类似 java 中的 Hashmap。

Redis的字典由三个基础的数据结构组成。最底层的单位是哈希表节点。结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

实际上哈希表节点就是一个单项列表的节点。保存了一下下一个节点的指针。 key 就是节点的键，v是这个节点的值。这个 v 既可以是一个指针，也可以是一个 uint64_t或者 int64_t 整数。*next 指向下一个节点。

通过一个哈希表的数组把各个节点链接起来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

dictht

通过图示我们观察：

实际上，如果对java 的基本数据结构了解的同学就会发现，这个数据结构和 java 中的 HashMap 是很类似的，就是数组加链表的结构。

字典的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

其中的dictType 是一组方法，代码如下：

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

/*
 * 字典类型特定函数
 */
typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);

    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);

    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);

} dictType;

字典的数据结构如下图：

这里我们可以看到一个dict 拥有两个 dictht。一般来说只使用 ht[0],当扩容的时候发生了rehash的时候，ht[1]才会被使用。

当我们观察或者研究一个hash结构的时候偶我们首先要考虑的这个 dict 如何插入一个数据？

我们梳理一下插入数据的逻辑。

• 计算Key 的 hash 值。找到 hash 映射到 table 数组的位置。

• 如果数据已经有一个 key 存在了。那就意味着发生了 hash 碰撞。新加入的节点，就会作为链表的一个节点接到之前节点的 next 指针上。

• 如果 key 发生了多次碰撞，造成链表的长度越来越长。会使得字典的查询速度下降。为了维持正常的负载。Redis 会对 字典进行 rehash 操作。来增加 table 数组的长度。所以我们要着重了解一下 Redis 的 rehash。步骤如下：

  1. 根据ht[0] 的数据和操作的类型（扩大或缩小），分配 ht[1] 的大小。
  2. 将 ht[0] 的数据 rehash 到 ht[1] 上。
  3. rehash 完成以后，将ht[1] 设置为 ht[0]，生成一个新的ht[1]备用。

• 渐进式的 rehash 。
  其实如果字典的 key 数量很大，达到千万级以上，rehash 就会是一个相对较长的时间。所以为了字典能够在 rehash 的时候能够继续提供服务。Redis 提供了一个渐进式的 rehash 实现，rehash的步骤如下：

  1. 分配 ht[1] 的空间，让字典同时持有 ht[1] 和 ht[0]。
  2. 在字典中维护一个 rehashidx，设置为 0 ，表示字典正在 rehash。
  3. 在rehash期间，每次对字典的操作除了进行指定的操作以外，都会根据 ht[0] 在 rehashidx 上对应的键值对 rehash 到 ht[1]上。
  4. 随着操作进行， ht[0] 的数据就会全部 rehash 到 ht[1] 。设置ht[0] 的 rehashidx 为 -1，渐进的 rehash 结束。

这样保证数据能够平滑的进行 rehash。防止 rehash 时间过久阻塞线程。

• 在进行 rehash 的过程中，如果进行了 delete 和 update 等操作，会在两个哈希表上进行。如果是 find 的话优先在ht[0] 上进行，如果没有找到，再去 ht[1] 中查找。如果是 insert 的话那就只会在 ht[1]中插入数据。这样就会保证了 ht[1] 的数据只增不减，ht[0]的数据只减不增。

原文地址：https://www.xilidou.com/2018/03/13/redis-data2/

上篇文章写了 Redis 基础数据结构的可变字符串、链表、字典。大家可以点击链接查看。今天我们继续研究 Redis 的基础数据结构。

• 整数集合
• 跳跃表
• 压缩列表

整数集合

当一个集合只包含整数，且这个集合的元素不多的时候，Redis 就会使用整数集合 intset 。首先看 intset 的数据结构：

1
2
3
4
5
6
7
8
9
10
11

typedef struct intset {
    
    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];
} intset;

其实 intset 的数据结构比较好理解。一个数据保存元素，length 保存元素的数量，也就是contents的大小，encoding 用于保存数据的编码方式。

通过代码我们可以知道，encoding 的编码类型包括了：

1
2
3

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

实际上我们可以看出来。 Redis encoding的类型，就是指数据的大小。作为一个内存数据库，采用这种设计就是为了节约内存。

既然有从小到大的三个数据结构，在插入数据的时候尽可能使用小的数据结构来节约内存，如果插入的数据大于原有的数据结构，就会触发扩容。

扩容有三个步骤：

1. 根据新元素的类型，修改整个数组的数据类型，并重新分配空间
2. 将原有的的数据，装换为新的数据类型，重新放到应该在的位置上，且保存顺序性
3. 再插入新元素

整数集合不支持降级操作，一旦升级就不能降级了。

跳跃表

跳跃表是链表的一种，是一种利用空间换时间的数据结构。跳表平均支持 O(logN)，最坏O(N)复杂度的查找。

跳表是由一个zskiplist 和 多个 zskiplistNode 组成。我们先看看他们的结构：

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

/* ZSETs use a specialized version of Skiplists */
/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {

    // 成员对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

/*
 * 跳跃表
 */
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

所以根据这个代码我们可以画出如下的结构图：

其实跳表就是一个利用空间换时间的数据结构，利用 level 作为链表的索引。

之前有人问过 Redis 的作者 为什么使用跳跃表，而不是 tree 来构建索引？作者的回答是：

1. 省内存。
2. 服务于 ZRANGE 或者 ZREVRANGE 是一个典型的链表场景。时间复杂度的表现和平衡树差不多。
3. 最重要的一点是跳跃表的实现很简单就能达到 O(logN)的级别。

压缩列表

压缩链表 Redis 作者的介绍是，为了尽可能节约内存设计出来的双向链表。

对于一个压缩列表代码里注释给出的数据结构如下：

zlbytes 表示的是整个压缩列表使用的内存字节数

zltail 指定了压缩列表的尾节点的偏移量

zllen 是压缩列表 entry 的数量

entry 就是 ziplist 的节点

zlend 标记压缩列表的末端

这个列表中还有单个指针：

ZIPLIST_ENTRY_HEAD 列表开始节点的头偏移量

ZIPLIST_ENTRY_TAIL 列表结束节点的头偏移量

ZIPLIST_ENTRY_END 列表的尾节点结束的偏移量

再看看一个 entry 的结构：

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

/*
 * 保存 ziplist 节点信息的结构
 */
typedef struct zlentry {

    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;

    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小
    unsigned int lensize, len;

    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;

    // 当前节点值所使用的编码类型
    unsigned char encoding;

    // 指向当前节点的指针
    unsigned char *p;

} zlentry;

依次解释一下这几个参数。

prevrawlen 前置节点的长度，这里多了一个 size，其实是记录了 prevrawlen 的尺寸。Redis 为了节约内存并不是直接使用默认的 int 的长度，而是逐渐升级的。
同理 len 记录的是当前节点的长度，lensize 记录的是 len 的长度。
headersize 就是前文提到的两个 size 之和。
encoding 就是这个节点的数据类型。这里注意一下 encoding 的类型只包括整数和字符串。
p 节点的指针，不用过多的解释。

需要注意一点，因为每个节点都保存了前一个节点的长度，如果发生了更新或者删除节点，则这个节点之后的数据也需要修改，有一种最坏的情况就是如果每个节点都处于需要扩容的零界点，就会造成这个节点之后的节点都要修改 size 这个参数，引发连锁反应。这个时候就是 压缩链表最坏的时间复杂度 O(n^2)。不过所有节点都处于临界值，这样的概率可以说比较小。

总结

至此Redis的基本数据结构就介绍完了。我们可以看到 Redis 对内存的使用真是“斤斤计较”，对于内存是使用特别节约。同时 Redis 作为一个单线程应用，不用考虑并发的问题，将很多类似 size 或者 length 的参数暴露出来，将很多 O(n) 的操作降低为 O(1)。大大提升效率。下一讲，将会介绍 Redis 是怎么通过这些数据结构向外提供服务。
Redis 的代码真是写的太棒了，简洁高效。值得大家学习。

Redis 的基础数据结构（三）对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/* Object types */
// 对象类型
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 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 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  /* E  dncoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

1
2
3
4
5
6
7
8

typedef struct zset{

    zskiplist *zsl;
    
    dict *dict

}zset;