基础篇(上)

键值数据库的基本架构

构造一个简单的键值数据库需要考虑的核心问题如下:

• 数据模型-可以存哪些数据?

基本的数据模型是key-value模型, 这里主要考虑value的类型.

• 操作接口-可以对数据做什么操作?

基本操作有 PUT, GET, DELETE, SCAN(根据一段key范围返回相应的value值), SET(新写/更新)等

• 键值对保存在内存还是外存?

内存快, 但是数据易丢失

• 采用什么访问模式?

一种是通过函数库调用, 一种是通过网络框架以socket通信的形式对外提供键值对操作
若采用第二种, 如何进一步设计IO模型, 使用单线程还是多线程进行网络连接, 请求解析, 数据处理等

• 采用什么索引形式?

一般而言，内存键值数据库（例如 Redis）采用哈希表作为索引，很大一部分原因在于，其键值数据基本都是保存在内存中的，而内存的高性能随机访问特性可以很好地与哈希表 O(1) 的操作复杂度相匹配。

• 不同操作的具体逻辑?

PUT, DELETE操作还需要操作内存空间

• 如何实现重启后快速提供服务?

一种是每个键值对都落盘, 会影响性能, 一种是周期性落盘, 但数据有丢失风险

结合以上思考, 构建一个基础的SimpleKV大致有下图的模块

Redis中的数据结构

Redis支持的数据类型有 String(字符串), List(列表), Hash(哈希), Set(集合), Sorted Set(有序集合).

底层数据结构

查找的时间复杂度

1. String类型, O(1)
2. 双向链表, O(N)
3. 压缩链表, O(N)

   压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。 在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

1. 哈希表, O(1)

2. 跳表, O(logN)

   跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，

3. 整数数组, O(N)

键值的数据结构

Redis 使用了一个哈希表来保存所有键值对. 哈希桶中的元素保存的并不是值本身，而是指向具体值的指针.
因此查找的时间复杂度是O(1).

哈希冲突的问题
Redis 解决哈希冲突的方式，就是链式哈希。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

1. 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
3. 释放哈希表 1 的空间。

渐进式rehash的设计使查找的均摊时间复杂度还是O(1). 因此对于String类型来说, 时间复杂度就是O(1)了.

不同操作的复杂度

结合底层数据结构以及键值的结构, 可以规避高复杂度操作

• 范围操作比较耗时, 应该使用SCAN代替RANGE, SCAN实现了渐进式遍历, 每次只返回有限数量的数据

总结

Redis 之所以能快速操作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的建议是：用其他命令来替代，例如可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。

当然，我们不能忘了复杂度较高的 List 类型，它的两种底层实现结构：双向链表和压缩列表的操作复杂度都是 O(N)。因此，我的建议是：因地制宜地使用 List 类型。例如，既然它的 POP/PUSH 效率很高，那么就将它主要用于 FIFO 队列场景，而不是作为一个可以随机读写的集合。

Redis中的IO模型

Redis是单线程, 主要是指Redis的网络IO和键值对读写是由一个线程来完成的, 这也是Redis对外提供键值存储服务的主要流程.
但Redis的其他功能, 比如持久化, 异步删除, 集群数据同步等, 是由额外的线程执行的.
Redis使用单线程主要是为了避免多线程编程模式面临的共享资源的并发访问控制问题.

单线程的Redis采用了多路复用的高性能I/O模型, 该模型允许内核中, 同时存在多个监听套接字和已连接套接字, 外来的请求会先放入事件队列, redis再根据事件的回调机制调用相应的处理函数, 不断处理出队的事件, 这样就提高了并发性, 避免了redis的单线程阻塞在某一个特定的客户端请求上.

AOF日志

AOF日志是写后日志(对比redo log就是写前日志),
优点: 避免记录错误命令, 不会阻塞当前的写操作
缺点: 可能阻塞下一个操作, 若刚执行完命令未写日志就宕机, 会丢失数据

可以看到写后日志的主要问题在于, 日志写入磁盘, 对此, AOF 配置项 appendfsync 提供了三个可选值

• Always，同步写回：每个写命令执行完，立马同步地将日志写回磁盘；
• Everysec，每秒写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，每隔一秒把缓冲区中的内容写入磁盘；
• No，操作系统控制的写回：每个写命令执行完，只是先把日志写到 AOF 文件的内存缓冲区，由操作系统决定何时将缓冲区内容写回磁盘。

此外, 若日志文件过大, 还会造成性能问题, 对此, redis提供了AOF重写机制, 会根据当前数据库现状创建新的AOF文件, 新日志文件会缩小

AOF重写是由后台子进程bgrewriteaof来完成的, 过程总结为
“一个拷贝”, 执行重写时, 主线程会fork出后台子进程;
“两处日志”, 重写过程中的写操作会同时写到旧的以及新日志的缓冲区中, 避免此时宕机数据丢失

AOF重写的触发时机
1. auto-aof-rewrite-min-size: 表示运行AOF重写时文件的最小大小，默认为64MB
2. auto-aof-rewrite-percentage: 这个值的计算方法是：当前AOF文件大小和上一次重写后AOF文件大小的差值，再除以上一次重写后AOF文件大小。也就是当前AOF文件比上一次重写后AOF文件的增量大小，和上一次重写后AOF文件大小的比值。
AOF文件大小同时超出上面这两个配置项时，会触发AOF重写。

RDB快照

Redis提供了内存快照的持久化方式, 快照文件就是RDB文件.

Redis 提供了两个命令来生成 RDB 文件，分别是 save 和 bgsave。

• save：在主线程中执行，会导致阻塞；
• bgsave：创建一个子进程，专门用于写入 RDB 文件，避免了主线程的阻塞，这也是 Redis RDB 文件生成的默认配置。

快照时数据能够被修改, 这是通过写时复制技术来实现的, 若快照过程中主线程要修改一块数据, 则这块数据会被复制一份, 然后bgsave子进程会将副本数据写入RDB文件.

但是快照的频率不好把握,
若频率太低, 则两次快照间宕机会有较多的数据丢失;
若频率太高, 则会产生额外开销(fork子进程阻塞, 以及频繁写盘带来磁盘压力等)

因此, Redis 4.0 中提出了一个混合使用 AOF 日志和内存快照的方法。简单来说，内存快照以一定的频率执行，在两次快照之间，使用 AOF 日志记录这期间的所有命令操作。

这样就避免了fork对主线程的影响, 也避免了AOF日志文件过大的情况.

最后，关于 AOF 和 RDB 的选择问题

1. 数据不能丢失时，内存快照和 AOF 的混合使用是一个很好的选择；
2. 如果允许分钟级别的数据丢失，可以只使用 RDB；
3. 如果只用 AOF，优先使用 everysec 的配置选项，因为它在可靠性和性能之间取了一个平衡。