zhenlanghuo's Blog

Redis设计与实现（第一部分 数据结构与对象）

redis
2017/04/15

《Redis设计与实现》一书的重要内容摘抄，方便回看复习

1.简单动态字符串

要点

  • Rredis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。
  • 比起C字符串，SDS具有以下优点：
    • 1） 常数复杂度获取字符串长度（len属性保存长度）
    • 2） 杜绝缓冲区溢出（修改时对空间进行检查）
    • 3） 减少修改字符串长度时所需的内存重分配次数（空间预分配、惰性空间释放）
    • 4） 二进制安全（可以保存任意格式的二进制数据）
    • 5） 兼容部分C字符串函数

数据结构

简单动态字符串.png-8.5kB

1
2
3
4
5
6
7
8
9
10
11
12
13
struct sdshdr {
    
        //记录buf数组中已使用字节的数量
        //等于SDS所保存字符串的长度
        int len;
        
        //记录buf数组中未使用字节的数量
        int free;
        
        //字节数组，用于保存字符串
        char buf[];
        
} sdshdr;

2.链表

要点

  • 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。
  • 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表
  • 每个链表使用一个list结构来表示，这个结构带有表头结点指针、表尾节点指针，以及链表长度等信息。
  • 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表。
  • 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值

数据结构

链表.png-19.6kB

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
typedef struct listNode {
    
    //前置节点
    struct listNode *prev;
    
    //后置节点
    struct listNode *next; 
    
    //节点的值
    void *value;
    
} listNode;

typedef struct list {
    
    //表头节点
    listNode *head;
    
    //表尾节点
    listNode *tail;
    
    //链表所包含的节点数量
    unsigned long len;
    
    //节点值复制函数
    void (*free)(void *ptr);
    
    //节点值对比函数
    void (*match)(void *ptr,void *key);
    
} list;

3.字典

要点

  • 字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。
  • Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另外一个仅在rehash时使用。
  • 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
  • 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
  • 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成，而是渐进式地完成的。

数据结构

字典.png-37.6kB

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
//哈希表
typedef struct dictht {
    
    //哈希表数组
    dictEntry **table;
    
    //哈希表大小
    unsigned long size;
    
    //哈希表大小掩码，用于计算索引值
    //总是等于size=1
    unsigned long sizemark;
    
    //该哈希表已有节点的数量
    unsigned long used;
    
} dichth;

//哈希表节点
typedef struct dictEntry {
    
    //键
    void *key;
    
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
    
} dictEntry;

//字典
typedef struct dict {
    
    //类型特定函数
    dictType *type;
    
    //私有数据
    void *privatedata;
    
    //哈希表
    dictht ht[2];
    
    //rehash索引
    //当rehash不在进行时，值为-1
    int trehashidx;
    
} dict;

rehash & 渐进式rehash

rehash的步骤

  • 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（ht[0].used属性的值）：
    • 如果执行的扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的$2^n$;
    • 如果执行的收缩操作，那么ht[1]的大小为**第一个大于等于ht[0].used的$2^n$**。
  • 将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
  • 当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），**释放ht[0]，将ht[1]设置为ht[0]**，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

如果哈希表你保存了大量的键值对，要一次性将这些键值对进行rehash，庞大的计算量会导致服务器在一段时间内停止服务,因此需要渐进式rehash

渐进式rehash的步骤

  • 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
  • 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
  • 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
  • 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

4.跳跃表

要点

  • 跳跃表是有序集合的底层实现之一。
  • Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
  • 每个跳跃表节点的层高都是1至32之间的随机数。
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
  • 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

数据结构

跳跃表.png-36.3kB

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
typedef struct zskiplistNode {
    
    //后退指针
    struct zskiplistNode *backward;
    
    //分值
    double score;
    
    //成员对象
    robj *obj;
    
    //层
    struct zskiplistLevel {
        
        //前进指针
        struct zskiplistNode *forward;
        
        //跨度
        unsigned int span;
        
    } level[];
    
} zskiplistNode;

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

5.整数结合

要点

  • 整数集合是集合键的底层实现之一。
  • 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型（升级）。
  • 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
  • 整数集合只支持升级操作，不支持降级操作。

数据结构

整数集合.png-12.4kB

1
2
3
4
5
6
7
8
9
10
11
typedef struct intset {
    
    //编码方式
    uint32_t encoding;
    
    //集合包含的元素数量
    uint32_t length;
    
    //保存元素的数组(声明为int8_t类型的数组，但实际上数组的真正类型取决于encoding的值)
    int8_t contents[];
} intset;

6.压缩列表

要点

  • 压缩列表是一种为节约内存而开发的顺序型数据结构（连续的内存空间）。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表（要保证有序），或者从压缩列表中删除节点（要保证连续的内存空间），可能会引发连锁更新操作，但这种操作出现的几率并不高。

数据结构

压缩列表各个组成部分

压缩列表.png-6.8kB

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

压缩列表节点各个组成部分

压缩列表节点.png-5.4kB
每个压缩列表节点可以保存一个字节数组或者一个整数值，每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成

previous_entry_length

节点的 previous_entry_length 属性以字节为单位， 记录了压缩列表中前一个节点的长度。

previous_entry_length 属性的长度可以是 1 字节或者 5 字节：

  • 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节：前一节点的长度就保存在这一个字节里面。
  • 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE （十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。

在压缩列表中可以根据zltail属性得到表尾节点的起始地址，而根据previous_entry_length可以计算出前一个节点的起始地址，这就是压缩列表的从表尾向表头遍历操作的原理。

encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度

content

节点的 content 属性负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。

7.对象

要点

  • Redis 数据库中的每个键值对的键和值都是一个对象。
  • Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象， 每种类型的对象至少都有两种或以上的编码方式， 不同的编码可以在不同的使用场景上优化对象的使用效率。
  • 服务器在执行某些命令之前， 会先检查给定键的类型能否执行指定的命令， 而检查一个键的类型就是检查键的值对象的类型。
  • Redis 的对象系统带有引用计数实现的内存回收机制， 当一个对象不再被使用时， 该对象所占用的内存就会被自动释放。
  • Redis 会共享值为 0 到 9999 的字符串对象。
  • 对象会记录自己的最后一次被访问的时间， 这个时间可以用于计算对象的空转时间。

对象的类型与编码

Redis 使用对象来表示数据库中的键和值， 每次当我们在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void *ptr;

    // ...

} robj;

对象的类型

类型常量 对象的名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象

对于 Redis 数据库保存的键值对来说， 键总是一个字符串对象， 而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种

对象的编码

编码常量 对象的编码
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典

对象的 ptr 指针指向对象的底层实现数据结构， 而这些数据结构由对象的 encoding 属性决定。

encoding 属性记录了对象所使用的编码， 也即是说这个对象使用了什么数据结构作为对象的底层实现

不同类型和编码的对象

类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现的有序集合对象。

每种类型的对象都至少使用了两种不同的编码

CATALOG
  1. 1. 1.简单动态字符串
    1. 1.1. 要点
    2. 1.2. 数据结构
  2. 2. 2.链表
    1. 2.1. 要点
    2. 2.2. 数据结构
  3. 3. 3.字典
    1. 3.1. 要点
    2. 3.2. 数据结构
    3. 3.3. rehash & 渐进式rehash
      1. 3.3.1. rehash的步骤
      2. 3.3.2. 渐进式rehash的步骤
  4. 4. 4.跳跃表
    1. 4.1. 要点
    2. 4.2. 数据结构
  5. 5. 5.整数结合
    1. 5.1. 要点
    2. 5.2. 数据结构
  6. 6. 6.压缩列表
    1. 6.1. 要点
    2. 6.2. 数据结构
      1. 6.2.1. 压缩列表各个组成部分
      2. 6.2.2. 压缩列表节点各个组成部分
        1. 6.2.2.1. previous_entry_length
        2. 6.2.2.2. encoding
        3. 6.2.2.3. content
  7. 7. 7.对象
    1. 7.1. 要点
    2. 7.2. 对象的类型与编码
Total : 27
2023
2022
2020
2019
2018
2017
Mysql Go AVL 平衡二叉树 数据结构 同步异步 阻塞非阻塞 IO linux java redis storm shell 深入理解java虚拟机 分布式 分布式一致性算法 raft 动态规划 哈希 代理 负载均衡 URL重写 C++ mysql 深翻页 zk zookeeper go