第一部分 数据结构与对象

2. 简单动态字符串

实现了一个类似于golang的切片, c++的vector. redis叫做SDS, 里面有

1
2
3
4
5

typedef struct sdshdr {
    int len; // 使用的空间
    int free; // 未使用的空间
    char buf[]; // 数组指针
} sdshdr;

原因

• redis使用len这种方式可以二进制安全, 不像是c字符串中’/0’就结束了, 有了len可以知道到哪里结束 空间分配
• 如果append后<1MB, 那么会变成原字符串+增加字符串+1地址空间
• 如果append后>1MB, 那么会+1MB空间, 而不是1地址空间

3. 链表

双向链表, 无环

4. 字典

结构

 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

/*字典*struct dict*里面有多个哈希表*struct dictht*,
哈希表里面有多个哈希节点*struct dictEntry*,
哈希节点里面存储的是键和值和指针, 指针指向下一个哈希节点.*/
typedef struct dict {
    dictType *type; // 类型
    void *privdata; // 私有数据
    dictht ht[2]; // 两个哈希表
    int rehashidx; // rehash索引
    int iterators; // 迭代器
} dict;

typedef struct dictht {
    dictEntry **table; // 哈希表, 可以理解成数组, 里面存储的是指针, 指向哈希节点(就是键值对)
    unsigned long size; // 大小
    unsigned long sizemask; // 掩码
    unsigned long used; // 使用
} dictht;

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

hash

添加的过程是使用hash函数, 输入键, 输出哈希值. 再通过掩码 & 来确定索引.(因为哈希表里面有多个哈希节点, 这个多个不是无数, 是有一定数量的, 比如4个的话, 掩码就是30011)

键冲突

在结构中, 我们说到哈希节点里面存储有指针, 指针指向下一个哈希节点, 这就是用来解决键冲突的.

rehash和渐进rehash

因为可以用链表解决冲突, 但太长的链表太慢了, 要想变快, 就要扩容. 扩容一般是翻倍, 结果要2^n.

根据负载因子(ht[0].used/ht[0].size).

• 如果没有执行bgsave, >1就要扩容了. < 0.1就会缩容.
• 在执行bgsave, >5才会扩容, 因为使用的写时复制, 如果这时候扩容, 就会疯狂复制, 防止内存扛不住

渐进rehash就是慢慢扩容

5. 跳跃表

6. 整数集合

6.1 结构

intset它会是自动排序的, 里面的元素都是从小到大的. 利用的是二分查找来进行插入和查找.

底层是使用int8_t数组实现, 因为是整数集合, 所以可以用int.

1
2
3
4
5

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 长度
    int8_t contents[]; // 内容
} intset;

6.2 升级

• 如果插入的元素比intset中的最大元素大, 那么就会升级, 会把每一个元素的所占空间都变成intset8, intset16, intset32, intset64.
  • 升级的过程是, 先创建一个新的intset, 然后把原来的intset的内容安元素的原来的位置放进去, 然后再放新的元素

7. 压缩列表

压缩列表是一种特殊的列表, 里面的元素可以是字符串, 整数, 二进制数据.

7.1 结构

一个压缩列表里面有多个字段 zlbytes, zltail, zllen, entry1, entry2, ... entryN, zlend

• zlbytes: 压缩列表的总长度
• zltail: 最后一个元素的偏移量
• zllen: 元素的个数
• entry1, entry2, … entryN: 元素
• zlend: 结束标志

一个entry的结构是 previous_entry_length, encoding, content

7.2 查找方式

• 从头开始查找
  • 因为是连续的数组结构体, 所以可以一个一个往下找
• 从尾开始查找
  • 因为有zltail, 所以可以从尾开始找
  • 并且还有previous_entry_length, 所以可以从尾开始找到上一个entry的长度
  • p = c - current_entry.previous_entry_length

8. 对象

对象就是redis中离使用者最近的数据结构. 同时某个对象底层会用到一个或多个上面的数据结构.

随着某个对象里面的元素的不同, 每个对象底层用的数据结构也会发生改变.

用type key命令: 键对应的值对象的类型

1
2
3
4

> SET msg "hello"
OK
> TYPE msg
"string"

用OBJECT ENCODING key命令: 键对应的值对象的编码方式

1
2
3
4

> SET msg "hello"
OK
> OBJECT ENCODING msg
"embstr"

下面的大类一共有5种, 对应对象的类型也是5种:

• REDIS_STRING字符串
  • REDIS_ENCODING_INT整数实现的字符串
  • REDIS_ENCODING_EMBSTRembstr编码的字符串
  • REDIS_ENCODING_RAW简单动态的字符串
• REDIS_LIST列表
  • REDIS_ENCODING_LINKEDLIST双端链表
    • 其他情况都使用这种
  • REDIS_ENCODING_ZIPLIST压缩列表
    • 所有字符串元素都是小于64字节的字符串
    • 列表元素个数小于512个
• REDIS_HASH哈希表
  • REDIS_ENCODING_HT字典
    • 其他情况都使用这种
  • REDIS_ENCODING_ZIPLIST压缩列表
    • 所有字符串元素都是小于64字节的字符串
    • 列表元素个数小于512个
• REDIS_SET集合
  • REDIS_ENCODING_HT字典
    • 其他情况都使用这种
  • REDIS_ENCODING_INTSET整数集合
    • 集合元素都是整数
    • 集合元素个数小于512个
• REDIS_ZSET有序集合
  • REDIS_ENCODING_SKIPLIST跳跃表
    • 其他情况都使用这种
  • REDIS_ENCODING_ZIPLIST压缩列表
    • 所有字符串元素都是小于64字节
    • 列表元素个数小于128个

第二部分 单机数据库的实现

9. 数据库

9.1 数据库的结构

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

// 代表redis服务
typedef struct redisServer{
  // ...
  redisDb *db; // 这是数组, 每个元素是一个redisDb结构体, 代表一个数据库
  // ...
}

// 正因为当前使用的数据库是这种用指针指向的, 所以作者特意说明操作前要先切换数据库.
typedef struct redisClient {
  // ...
  redisDb *db; // 指向当前客户端正在使用的数据库
  // ...
}

typedef struct redisDb {
  //...
  dict *dict; // 数据库的键空间, 指向一个字典
  dict *expires; // 数据库的过期键空间
  //...
}

9.2 生存时间

redis是可以设置生存时间的, 也就是过期时间. 可以根据4个命令来设置过期时间

• EXPIRE key seconds
• PEXPIRE key milliseconds
• EXPIREAT key timestamp // 秒UNIX时间戳
• PEXPIREAT key milliseconds-timestamp // 毫秒UNIX时间戳

这个四个函数都会变成一个时间戳, 然后存储在expires字典中, 这个字典里的内容的key是键, value是时间戳, 因为都是一模一样的哈希算法, 所以可以这样做.

9.3 删除策略

• 定时删除: 创建一个定时器, 每隔一段时间就检查一次过期键, 如果过期就删除
  • 优点: 删除及时
  • 缺点: 消耗CPU
• 惰性删除: 每次获取一个键的时候, 都会检查这个键是否过期, 如果过期就删除
  • 优点: 不消耗CPU
  • 缺点: 不及时, 浪费内存
• 定期删除: 每隔一段时间, 随机抽取一些键, 然后检查是否过期, 如果过期就删除
  • 这是以上两种的折中方案

10. RDB持久化

因为redis是内存数据库, 所以如果redis服务挂了, 那么数据就会丢失. 所以需要持久化. 有两个RDB持久化的命令, 分别是

• SAVE: 阻塞式, 会阻塞redis服务, 直到持久化完成
• BGSAVE: 非阻塞式, 会fork一个子进程, 然后在子进程中进行持久化操作

BGSAVE和BGREWRITEAOF不会同时进行, 因为会有大量写磁盘操作.

10.1 保存条件

用户可以通过设置save配置来设置持久化的条件, 也可以通过bgsave命令来进行持久化.

• save 900 1: 900秒内有1个键被修改
• save 300 10: 300秒内有10个键被修改
• save 60 10000: 60秒内有10000个键被修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct redisServer {
  // ...
  struct saveparam *saveparams; // 保存了所有save配置的数组
  // ...
};

// 记录了save配置的结构体
struct saveparam {
  time_t seconds;
  int changes;
};

10.2 dirty计数器和lastsave属性

1
2
3
4
5
6

struct redisServer {
  // ...
  long long dirty; // 记录了上次持久化后, 修改的次数
  time_t lastsave; // 记录了上次持久化的时间
  // ...
};

检查持久化条件

设置完了保存条件, 并且也记录了上次持久化的时间和修改次数, 那么就可以根据这些条件来检查是否需要持久化了.

默认情况下, redis会根据配置每隔100m会使用serverCron函数来检查一次持久化条件, 如果满足条件就会进行持久化操作.

10.3 RDB文件结构

10.3.1 database的字段结构

• SELECTDB: 1B, 看到这个就知道是选择数据库的开始, 一般是0376
• db_number: …B, 代表了数据库的编号, 自适应的
• key_value_pairs: …B, 代表了键值对

10.3.2 key_value_pairs的字段结构

• TYPE: 1B, 代表了值的类型, 有不同的类型, 但都是常量
• KEY: …B, 代表了键的内容, 一般都是字符串
• VALUE: …B, 代表了值的内容, 与TYPE所描述的一致

10.3.3 VALUE的编码

因为key都是常量, 书中讲述了各种编码方式

1. 字符串对象
2. 列表对象
3. 集合对象
4. 哈希表对象
5. 有序集合对象
6. INTSET编码的集合对象
7. ZIPLIST编码的列表、哈希表或者有序集合对象

11. AOF持久化

先不看了, 疑似就是把所有的操作都记录下来, 然后在重启的时候重新执行一遍.

12. 事件

到了我的老本行了, 事件驱动. redis基于Reactor模式.

好像最新版redis6.0变成多线程了, 就为了io的处理快一点. 看了一眼文章, 就是多线程收集socket来的命令, 然后放在一起, 主线程来一点点循环执行.

粗略的看了一下, 应该就是把两大类东西放到epoll或者select中, 一类是socket, 一类是时间事件.

• 等到有人链接或者要通信的时候, 就会触发事件, 然后执行相应的操作.
• 或者等到时间到了, 就会触发事件, 然后执行相应的操作.

13. 客户端

14. 服务器

第三部分 多机数据库的实现

第四部分 独立功能的实现