6. 缓存数据库

数据库

6. 缓存数据库

Redis介绍

Redis 是完全开源免费的，遵守BSD协议，是一个高性能的key-value数据库。

Redis 与其他 key - value 缓存产品有以下三个特点：

Redis支持数据的持久化，可以将内存中的数据保存在磁盘中，重启的时候可以再次加载进行使用。
Redis不仅仅支持简单的key-value类型的数据，同时还提供list，set，zset，hash等数据结构的存储。
Redis支持数据的备份，即master-slave模式的数据备份。

Redis特点

速度快，因为数据存在内存中，类似于HashMap，HashMap的优势就是查找和操作的时间复杂度都是O(1)
支持丰富数据类型，支持string，list，set，sorted set，hash
支持事务，操作都是原子性，所谓的原子性就是对数据的更改要么全部执行，要么全部不执行
丰富的特性：可用于缓存，消息，按key设置过期时间，过期后将会自动删除

Redis和Memcached区别

memcached所有的值均是简单的字符串，redis作为其替代者，支持更为丰富的数据类型
redis的速度比memcached快很多
redis可以持久化其数据
Redis支持数据的备份，即master-slave模式的数据备份。
使用底层模型不同，它们之间底层实现方式以及与客户端之间通信的应用协议不一样。Redis直接自己构建了VM 机制，因为一般的系统调用系统函数的话，会浪费一定的时间去移动和请求。
value大小：redis最大可以达到1GB，而memcache只有1MB

Redis内部数据结构

字符串

Redis的字符串叫做[SDS]，即Simple Dynamic String。它的结构是一个带长度信息的字节数组

struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}

content存储真正的字符串内容，capacity表示所分配数组的长度，len表示字符串的实际长度
SDS使泛型用T，是因为当字符串比较短时，len和capacity可以使用byte和short来表示
Redis的字符串有两种存储方式，当长度特别短使用EMB形式存储，当长度超过44时，使用raw形式存储
字符串在长度小于 1M 之前，扩容空间采用加倍策略，也就是保留 100% 的冗余空间。当长度超过 1M 之后，为了避免加倍后的冗余空间过大而导致浪费，每次扩容只会多分配 1M 大小的冗余空间。

字典

字典，是一种用于保存键值对的抽象数据结构，Redis中的hash结构、zset中value和score值的映射关系、Redis所有的key和value、带过期时间的key都是使用字典（dict）这个数据结构。

字典使用哈希表来作为底层实现，每个字典带有两个哈希表，一个平时使用，另外一个仅在进行渐进式搬迁时使用，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。

扩容：

如果服务器没有正在执行bgsave令，并且哈希表中的元素个数大于等于一维数据的长度，自动开始对dict进行扩容扩容至2倍
如果服务器正在执行bgsave命令，并且哈希表中的元素个数大于等于一维数据的长度的5倍，才进行强制扩容

缩容：

当元素个数低于数组长度的 10%，Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容不会考虑 Redis 是否正在做 bgsave。

SAVE和BGSAVE的区别：

SAVE 保存是阻塞主进程，客户端无法连接redis，等SAVE完成后，主进程才开始工作，客户端可以连接
BGSAVE 是fork一个save的子进程，在执行save过程中，不影响主进程，客户端可以正常链接redis，等子进程fork执行save完成后，通知主进程，子进程关闭。很明显BGSAVE方式比较适合线上的维护操作，两种方式的使用一定要了解清楚在谨慎选择。

压缩列表

zset 和 hash 容器对象在元素个数较少的时候，采用压缩列表 (ziplist) 进行存储。压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

zlbytes：4字节，记录整个压缩列表占用内存的字节数
zltail：4字节，记录压缩列表尾部节点距离起始地址的偏移量
zllen：2字节，记录压缩列表包含的节点数量
entry：不定，列表中的每个节点
zlend：1字节，特殊值0xFF，标记压缩列表的结束

增加元素：

因为 ziplist 都是紧凑存储，没有冗余空间。意味着插入一个新的元素就需要调用 realloc 扩展内存。取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。
如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。

级联更新：

当前某个 entry 之前的节点从小于254字节，变成大于等于254字节，那么当前entry 的 previous_entry_length 从1字节变成5字节。如果因为从1字节变成5字节，使自己跨越了从小于254字节，到过了254字节这条线，就又会引起下一个节点的扩容。
最坏的情况是：所有entry都是刚好处于250-253字节之间，然后在链表头插入一个大于等于254字节的entry，此时会触发全链级联更新。
删除中间的某个节点也可能会导致级联更新

快速列表

考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

typedef struct quicklist {
    quicklistNode *head;        // 指向quicklist的头部
    quicklistNode *tail;        // 指向quicklist的尾部
    unsigned long count;        // 列表中所有数据项的个数总和
    unsigned int len;           // quicklist节点的个数，即ziplist的个数
    int fill : 16;              // ziplist大小限定，由list-max-ziplist-size给定
    unsigned int compress : 16; // 节点压缩深度设置，由list-compress-depth给定
} quicklist;

quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个 ziplist。ziplist 的长度由配置参数list-max-ziplist-size决定。
quicklist 默认的压缩深度是 0，也就是不压缩。压缩的实际深度由配置参数list-compress-depth决定。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

跳跃列表

Redis 的 zset 是一个复合结构，一方面它需要一个 hash 结构来存储 value 和 score 的对应关系，另一方面需要提供按照 score 来排序的功能，还需要能够指定 score 的范围来获取 value 列表的功能，这就需要另外一个结构「跳跃列表」。

图中只画了四层，Redis 的跳跃表共有 64 层，意味着最多可以容纳 2^64 次方个元素。每一个 kv 块对应的结构如下面的代码中的zslnode结构，kv header 也是这个结构，只不过 value 字段是 null 值——无效的，score 是 Double.MIN_VALUE，用来垫底的。kv 之间使用指针串起来形成了双向链表结构，它们是有序排列的，从小到大。不同的 kv 层高可能不一样，层数越高的 kv 越少。同一层的 kv 会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。

Redis应用

分布式锁

Redis为单进程单线程模式，采用队列模式将并发访问变成串行访问，且多客户端对Redis的连接并不存在竞争关系。redis的SETNX命令可以方便的实现分布式锁。

分布式锁本质上要实现的目标就是在 Redis 里面占一个“茅坑”，当别的进程也要来占时，发现已经有人蹲在那里了，就只好放弃或者稍后再试。

占坑一般是使用 setnx(set if not exists) 指令，只允许被一个客户端占坑。先来先占，用完了，再调用 del 指令释放茅坑。

setNX（SET if Not eXists 如果不存在，则 SET）

当 key 不存在，将 key 的值设为 value 。
若给定的 key 已经存在，则 SETNX 不做任何动作。

如果一个持有锁的客户端失败或崩溃了不能释放锁，该怎么解决？

如果一个客户端持有的锁超时了，任何客户端都可以检测超时并删除该锁，那么这里就会存在竞态关系，

C0操作超时了，但它还持有着锁，C1和C2读取lock.foo检查时间戳，先后发现超时了。 
C1 发送DEL lock.foo 
C1 发送SETNX lock.foo 并且成功了。 
C2 发送DEL lock.foo 
C2 发送SETNX lock.foo 并且成功了。 
这样一来，C1，C2都拿到了锁！

所以使用执行下面的命令解决上面问题

GETSET lock.foo <current Unix time + lock timeout + 1>

通过GETSET，C1拿到的时间戳如果是超时的，那就说明中间锁超时并且中间没有被其他客户端抢先获得锁，因此C1拿到锁。如果在C1之前，有个叫C2的客户端比C1快一步执行了上面的操作，那么C1拿到的时间戳是个未超时的值，这时C1没有如期获得锁，需要再次等待或重试。尽管C1没拿到锁，但它改写了C2设置的锁的超时值，不过这一点非常微小的误差带来的影响可以忽略不计。

延时队列

延时队列可以通过 Redis 的 zset(有序列表) 来实现。我们将消息序列化成一个字符串作为 zset 的value，这个消息的到期处理时间作为score，然后用多个线程轮询 zset 获取到期的任务进行处理，多个线程是为了保障可用性，万一挂了一个线程还有其它线程可以继续处理。因为有多个线程，所以需要考虑并发争抢任务，确保任务不能被多次执行。

位图

Redis 提供了位图统计指令 bitcount 和位图查找指令 bitpos，bitcount 用来统计指定位置范围内 1 的个数，bitpos 用来查找指定范围内出现的第一个 0 或 1。比如我们可以通过 bitcount 统计用户一共签到了多少天，通过 bitpos 指令查找用户从哪一天开始第一次签到。如果指定了范围参数[start, end]，就可以统计在某个时间范围内用户签到了多少天，用户自某天以后的哪天开始签到。

HyperLogLog

HyperLogLog 数据结构是 Redis 的高级数据结构，HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了

布隆过滤器

布隆过滤器是一个神奇的数据结构，可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。

redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。

每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都位 1，只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。如果都是 1，这并不能说明这个 key 就一定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。

redis 布隆过滤器主要就两个命令：

bf.add 添加元素到布隆过滤器中：bf.add urls https://baidu.com
bf.exists 判断某个元素是否在过滤器中：bf.exists urls https://baidu.com

布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：

error_rate：允许布隆过滤器的错误率，这个值越低,需要的存储空间就越大，对于不需要过于精确的场合，error_rate设置稍大一点也无伤大雅。
initial_size：布隆过滤器可以储存的元素个数，估计的过大，会浪费存储空间，估计的过小，就会影响准确率。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

代码三个参数的含义：

第一个值是布隆过滤器的名字。
第二个值为 error_rate 的值。
第三个值为 initial_size 的值。

Redis单进程单线程方式

注意：这里我们一直在强调的单线程，只是在处理我们的网络请求的时候只有一个线程来处理，一个正式的Redis Server运行的时候肯定是不止一个线程的，这里需要大家明确的注意一下！例如Redis进行持久化的时候会以子进程或者子线程的方式执行（具体是子线程还是子进程待读者深入研究）；例如我在测试服务器上查看Redis进程，然后找到该进程下的线程

因为Redis是基于内存的操作，CPU不是Redis的瓶颈，Redis的瓶颈最有可能是机器内存的大小或者网络带宽。既然单线程容易实现，而且CPU不会成为瓶颈，所以就采用单线程

单进程单线程好处

代码更清晰，处理逻辑更简单
不用去考虑各种锁的问题，不存在加锁释放锁操作，没有因为可能出现死锁而导致的性能消耗
不存在多进程或者多线程导致的切换而消耗CPU

单进程单线程弊端

无法发挥多核CPU性能，不过可以通过在单机开多个Redis实例来完善；

其他一些优秀的开源软件采用的模型

多进程单线程模型：Nginx （Nginx有两类进程，一类称为Master进程(相当于管理进程)，另一类称为Worker进程（实际工作进程））
单进程多线程模型：MySQL、Memcached、Oracle（ Windows版本）；

多路I/O复用模型

多路I/O复用模型是利用 select、poll、epoll 可以同时监察多个流的 I/O 事件的能力，在空闲的时候，会把当前线程阻塞掉，当有一个或多个流有 I/O 事件时，就从阻塞态中唤醒，于是程序就会轮询一遍所有的流（epoll 是只轮询那些真正发出了事件的流），并且只依次顺序的处理就绪的流，这种做法就避免了大量的无用操作。
这里“多路”指的是多个网络连接，“复用”指的是复用同一个线程。采用多路 I/O 复用技术可以让单个线程高效的处理多个连接请求（尽量减少网络 IO 的时间消耗），且 Redis 在内存中操作数据的速度非常快，也就是说内存内的操作不会成为影响Redis性能的瓶颈，主要由以上几点造就了 Redis 具有很高的吞吐量。

我们知道Redis是用”单线程-多路复用IO模型”来实现高性能的内存数据服务的，这种机制避免了使用锁，但是同时这种机制在进行sunion之类的比较耗时的命令时会使redis的并发下降。因为是单一线程，所以同一时刻只有一个操作在进行，所以，耗时的命令会导致并发的下降，不只是读并发，写并发也会下降。而单一线程也只能用到一个CPU核心，所以可以在同一个多核的服务器中，可以启动多个实例，组成master-master或者master-slave的形式，耗时的读命令可以完全在slave进行。

Redis快的主要原因

完全基于内存
采用单线程,避免了不必要的上下文切换和竞争条件
数据结构简单，对数据操作也简单
使用多路 I/O 复用模型

Redis主从复制

过程原理：

当从库和主库建立MS关系后,会向主数据库发送SYNC命令
主库接收到SYNC命令后会开始在后台保存快照(RDB持久化过程),并将期间接收到的写命令缓存起来
当快照完成后,主Redis会将快照文件和所有缓存的写命令发送给从Redis
从Redis接收到后,会载入快照文件并且执行收到的缓存的命令
之后,主Redis每当接收到写命令时就会将命令发送从Redis，从而保证数据的一致

缺点：所有的slave节点数据的复制和同步都由master节点来处理,会照成master节点压力太大,使用主从从结构来解决

Redis两种持久化方式优缺点

RDB 持久化可以在指定的时间间隔内生成数据集的时间点快照（point-in-time snapshot）
AOF 持久化记录服务器执行的所有写操作命令，并在服务器启动时，通过重新执行这些命令来还原数据集。
Redis 还可以同时使用 AOF 持久化和 RDB 持久化。当redis重启时,它会有限使用AOF文件来还原数据集,因为AOF文件保存的数据集通常比RDB文件所保存的数据集更加完整

RDB的优点：

RDB 是一个非常紧凑（compact）的文件，它保存了 Redis 在某个时间点上的数据集。这种文件非常适合用于进行备份：比如说，你可以在最近的 24 小时内，每小时备份一次 RDB 文件，并且在每个月的每一天，也备份一个 RDB 文件。这样的话，即使遇上问题，也可以随时将数据集还原到不同的版本。
RDB 非常适用于灾难恢复（disaster recovery）：它只有一个文件，并且内容都非常紧凑，可以（在加密后）将它传送到别的数据中心，或者亚马逊 S3 中。
RDB 可以最大化 Redis 的性能：父进程在保存 RDB 文件时唯一要做的就是 fork 出一个子进程，然后这个子进程就会处理接下来的所有保存工作，父进程无须执行任何磁盘 I/O 操作。
RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快

Redis常见的性能问题都有哪些？如何解决？

Master写内存快照，save命令调度rdbSave函数，会阻塞主线程的工作，当快照比较大时对性能影响是非常大的，会间断性暂停服务，所以Master最好不要写内存快照。
Master AOF持久化，如果不重写AOF文件，这个持久化方式对性能的影响是最小的，但是AOF文件会不断增大，AOF文件过大会影响Master重启的恢复速度。Master最好不要做任何持久化工作，包括内存快照和AOF日志文件，特别是不要启用内存快照做持久化,如果数据比较关键，某个Slave开启AOF备份数据，策略为每秒同步一次。
Master调用BGREWRITEAOF重写AOF文件，AOF在重写的时候会占大量的CPU和内存资源，导致服务load过高，出现短暂服务暂停现象。
Redis主从复制的性能问题，为了主从复制的速度和连接的稳定性，Slave和Master最好在同一个局域网内

Redis提供6种数据淘汰策略

volatile-lru：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰
volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰
volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰
allkeys-lru：从数据集（server.db[i].dict）中挑选最近最少使用的数据淘汰
allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
no-enviction（驱逐）：禁止驱逐数据

Redis设置过期时间的原理

Redis 提供的诸多命令中，EXPIRE、EXPIREAT、PEXPIRE、PEXPIREAT 以及 SETEX 和 PSETEX 均可以用来设置一条 Key-Value 对的过期时间。

Redis 会将每个设置了过期时间的 key 放入到一个独立的字典中，过期键的处理就是把过期键删除，这里的操作主要是针对过期字段处理的。

Redis中有三种处理策略：定时删除、惰性删除和定期删除

定时删除：在设置键的过期时间的时候创建一个定时器，当过期时间到的时候立马执行删除操作。不过这种处理方式是即时的，不管这个时间内有多少过期键，不管服务器现在的运行状况，都会立马执行，所以对CPU不是很友好。但是这在最大程度上释放了内存，所以这种方式算是一种内存优先优化策略。
惰性删除：惰性删除策略不会在键过期的时候立马删除，而是当外部指令获取这个键的时候才会主动删除。处理过程为：接收get执行、判断是否过期、执行删除操作、返回nil（空）。
定期删除：定期删除是设置一个时间间隔，每个时间段都会检测是否有过期键，如果有执行删除操作。

定时扫描策略

Redis 默认会每秒进行十次过期扫描，过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略。

从过期字典中随机 20 个 key；
删除这 20 个 key 中已经过期的 key；
如果过期的 key 比率超过 1/4，那就重复步骤 1；

同时，为了保证过期扫描不会出现循环过度，导致线程卡死现象，算法还增加了扫描时间的上限，默认不会超过 25ms。

缓存解决方案分析

缓存雪崩

缓存雪崩是指缓存中数据大批量到过期时间，而查询数据量巨大，引起数据库压力过大甚至down机。从而形成一系列连锁反应，造成整个系统崩溃。一般有三种处理办法：

缓存数据的过期时间设置随机，防止同一时间大量数据过期现象发生。
一般并发量不是特别多的时候，使用最多的解决方案是加锁排队。
给每一个缓存数据增加相应的缓存标记，记录缓存的是否失效，如果缓存标记失效，则更新数据缓存。

缓存穿透

缓存穿透是指缓存和数据库中都没有的数据，而用户不断发起请求，如发起为id为“-1”的数据或id为特别大不存在的数据。这时的用户很可能是攻击者，攻击会导致数据库压力过大。

解决方案：

接口层增加校验，如用户鉴权校验，id做基础校验，id<=0的直接拦截；
从缓存取不到的数据，在数据库中也没有取到，这时也可以将key-value对写为key-null，缓存有效时间可以设置短点，如30秒（设置太长会导致正常情况也没法使用）。这样可以防止攻击用户反复用同一个id暴力攻击
采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的 bitmap 中，一个一定不存在的数据会被这个 bitmap 拦截掉，从而避免了对底层存储系统的查询压力

缓存击穿

缓存击穿是指缓存中没有但数据库中有的数据（一般是缓存时间到期），这时由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大，造成过大压力。和缓存雪崩不同的是，缓存击穿指并发查同一条数据，缓存雪崩是不同数据都过期了，很多数据都查不到从而查数据库。

解决方案：

设置热点数据永远不过期。
加互斥锁，互斥锁

缓存预热

缓存预热就是系统上线后，提前将相关的缓存数据直接加载到缓存系统。避免在用户请求的时候，先查询数据库，然后再将数据缓存的问题！用户直接查询事先被预热的缓存数据！

缓存预热解决方案：

直接写个缓存刷新页面，上线时手工操作下；
数据量不大，可以在项目启动的时候自动进行加载；
定时刷新缓存；

缓存更新

除了缓存服务器自带的缓存失效策略之外（Redis默认的有6中策略可供选择），我们还可以根据具体的业务需求进行自定义的缓存淘汰，常见的策略有两种：

定时去清理过期的缓存；
当有用户请求过来时，再判断这个请求所用到的缓存是否过期，过期的话就去底层系统得到新数据并更新缓存。

5. DataBase Design