# 缓存

Redis 是速度非常快的非关系型（NoSQL）内存键值数据库：

* 绝大部分请求是纯粹的内存操作
* 采用单线程，避免了不必要的上下文切换和竞争条件
* 非阻塞IO

## 1. 数据类型

### 常见数据类型

| 数据类型   | 可以存储的值      |
| ------ | ----------- |
| STRING | 字符串、整数或者浮点数 |
| LIST   | 列表          |
| SET    | 无序集合        |
| ZSET   | 有序集合        |
| HASH   | 包含键值对的无序散列表 |

### 存储结构

[扩展阅读：Redis底层数据结构](https://zhuanlan.zhihu.com/p/38380467)

Redis底层数据结构包括：简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表、对象。

#### 字典

Reids的字典采用链地址法来处理冲突。考虑到扩容时大量数据迁移带来的CPU繁忙(可能导致一段时间内停止服务)，所以Redis采用了**渐进式rehash**的方案：

Redis 的字典 dict 中包含两个哈希表 dictht，一个为数据表，一个为空表。每次对字典增删改查时，将数据表 dictht 上的键值对 rehash 到另一个 dictht 上面，完成之后释放空间并交换两个 dictht 的角色。Redis 采用分而治之的思想，将庞大的数据迁移工作平摊到每一次查询操作中，避免了服务中断。

#### 跳跃表

[扩展阅读：Redis-跳跃表](https://www.jianshu.com/p/c706d050d2f8)

跳跃表(SkipList)是有序集合(ZSet)的底层实现之一，是基于多指针有序链表实现的，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。查找、删除、添加等操作时间复杂度为O(logn).

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/XUpU7OnJ6sC9Va0Y.png)

在查找时，从上层指针开始查找，找到对应的区间之后再到下一层去查找。下图演示了查找 22 的过程。

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/9YYuBUzf1EH9kMnU.png)

与红黑树等平衡树相比，跳跃表具有以下优点：

* 支持范围查询
* 简单，容易实现
* 支持无锁操作

## 2. Redis与Memcache区别

|       | Redis               | Memcache |
| ----- | ------------------- | -------- |
| 数据类型  | 支持五种不同的数据类型         | 仅支持字符串类型 |
| 数据持久化 | 支持RDB 和 AOF 两种持久化策略 | 不支持      |
| 分布式   | 支持主从和分片             | 不支持      |

## 3. pipeline 与 mget 比较

### pipeline

一般情况下，Redis Client端发出一个请求后，通常会阻塞并等待Redis Server处理，Redis Server处理完后请求命令后会将结果通过响应报文返回给Redis Client. 当要连续执行多个命令时，主要的时延在于 RTT （Round-Trip Time），而且还要频繁调用系统 I / O 接口。

使用 Pipeline 可以将多个命令一次性写入到服务器，然后等待服务器返回结果。Pipeline可以同时执行多个命令，但是各个命令之间**不能有数据依赖**，因为 Pipeline 执行命令时不能保证执行顺序与写入时的命令顺序相同。

### mget

```
mset a "a1" b "b1" c "c1"
mget a b c
```

mget 和 mset 也是为了减少网络连接和传输时间设置的，当 key 的数目较多时， mget 和 mset 性能要高于 pipeline，但是 mget 和 mset 也仅限与同时对多个 key 进行操作。

## 4. 持久化机制

Redis 是内存型数据库，为了保证数据在断电后不会丢失，需要将内存中的数据持久化到硬盘上。

### RDB (Redis Database Backup)

* 保存某个时间点的全量数据快照
* 如果系统发生故障，将会丢失最后一次创建快照之后的数据
* 如果数据量很大，保存快照的时间会很长

两种数据保存方式

* SAVE：阻塞Redis服务器进程，直到RDB文件创建完毕
* BGSAVE：Fork一个子进程来创建RDB文件，不阻塞服务器进程

### AOF (Append Only Files)

* 将写命令添加到 AOF 文件的末尾
* 可以使用日志重写解决AOF文件不断增大的问题
* 使用 AOF 持久化需要设置同步选项，从而确定写命令同步到磁盘文件上的时机。有以下同步选项：

| 选项       | 同步频率         | 解释                                                        |
| -------- | ------------ | --------------------------------------------------------- |
| always   | 每个写命令都同步     | 会严重减低服务器的性能                                               |
| everysec | 每秒同步一次       | 比较合适，可以保证系统崩溃时只会丢失一秒左右的数据，并且 Redis 每秒执行一次同步对服务器性能几乎没有任何影响 |
| no       | 让操作系统来决定何时同步 | 不能给服务器性能带来多大的提升，而且也会增加系统崩溃时数据丢失的数量                        |

### RDB与AOF比较

|    | RDB             | AOF                  |
| -- | --------------- | -------------------- |
| 优点 | 全量数据快照，文件小，恢复快  | 可读性好，适合保存增量数据，数据不易丢失 |
| 缺点 | 无法保存最近一次快照之后的数据 | 文件体积大，恢复时间长          |

## 5. 数据过期策略

### LRU

[LeetCode 面试题 16.25. LRU缓存](https://leetcode-cn.com/problems/lru-cache-lcci/)

最近最少使用策略 (Least Recently Used)，优先淘汰最久未使用的数据，也就是上次被访问时间距离现在最久的数据。该策略可以保证内存中的数据都是热点数据，也就是经常被访问的数据，从而保证缓存命中率。

假设内存只能容纳3个页，内存按照栈的方式来描述访问时间，最上面的是最近访问的，最下面的最远时间访问的。 如果按照 7 0 1 2 0 3 0 4 的次序访问页:

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/I6ZRhkJWFVb37Swq.png)

以下是基于 双向链表 + HashMap 的 LRU 算法实现，对算法的解释如下：

* 访问某个节点时，将其从原来的位置删除，并重新插入到链表头部，这样就能保证链表尾部存储的就是最近最久未使用的节点
* 当节点数量大于缓存最大空间时就淘汰链表尾部的节点
* 为了使删除操作时间复杂度为 O(1)，使用HashMap 存储 Key 到节点的映射，通过 Key 就能以 O(1) 的时间得到节点，然后再以 O(1) 的时间将其从双向链表中删除

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/I6ZRhkJWFVb37S4K.png)

```java
public class LRU<K, V> {
    private HashMap<K, ListNode> map = new HashMap<>();
    private int count;
    private int capacity;
    private ListNode head, tail;

    // Double-linked list node.
    class ListNode {
        ListNode prev;
        ListNode next;
        K key;
        V value;

        ListNode() {}
        ListNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRU(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        ListNode node = map.get(key);
        if(node == null){
            return null;
        }
        // move the accessed node to the head
        this.moveToHead(node);
        return node.value;
    }

    public void set(K key, V value) {
        ListNode node = map.get(key);

        if(node == null){
            ListNode newNode = new ListNode(key, value);
            this.map.put(key, newNode);
            this.addNode(newNode);
            ++count;

            if(count > capacity){
                // pop the tail
                ListNode tail = this.popTail();
                this.map.remove(tail.key);
                --count;
            }
        }
        else {
            // update the value
            node.value = value;
            this.moveToHead(node);
        }
    }

    // Always add the new node right after head.
    private void addNode(ListNode node){
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    // remove an existing node from the linked list.
    private void removeNode(ListNode node){
        ListNode prev = node.prev;
        ListNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    // Move certain node in between to the head.
    private void moveToHead(ListNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    // Pop the current tail.
    private ListNode popTail(){
        ListNode res = tail.prev;
        this.removeNode(res);
        return res;
    }
}
```

### LFU

最不经常使用策略(Least Frequently Used)，优先淘汰一段时间内使用次数最少的数据。

### Redis 的数据过期策略

[扩展阅读：Redis的缓存淘汰策略LRU与LFU](https://www.jianshu.com/p/c8aeb3eee6bc)

| 策略              | 描述                         |
| --------------- | -------------------------- |
| volatile-lru    | 从已设置过期时间的数据集中挑选最近最少使用的数据淘汰 |
| volatile-lfu    | 从已设置过期时间的数据集中驱逐使用频率最少的键    |
| volatile-ttl    | 从已设置过期时间的数据集中挑选将要过期的数据淘汰   |
| volatile-random | 从已设置过期时间的数据集中任意选择数据淘汰      |
| allkeys-lru     | 从所有数据集中挑选最近最少使用的数据淘汰       |
| allkeys-lfu     | 从所有键中驱逐使用频率最少的键            |
| allkeys-random  | 从所有数据集中任意选择数据进行淘汰          |
| noeviction      | 禁止驱逐数据                     |

## 6. 应用场景

### 分布式锁

[扩展阅读：基于Redis的分布式锁实现](https://juejin.im/post/5cc165816fb9a03202221dd5#heading-17)

在单机场景下，可以使用语言的内置锁来实现进程同步。但是在分布式场景下，需要同步的进程可能位于不同的节点上，那么就需要使用分布式锁。

可以使用带NX参数的SET指令实现：

```
SET key value[EX seconds][PX milliseconds][NX|XX]
```

* EX seconds: 设定过期时间，单位为秒
* PX milliseconds: 设定过期时间，单位为毫秒
* NX: 仅当key不存在时设置值
* XX: 仅当key存在时设置值

### 消息队列

使用List作为队列，可以通过 lpush 和 rpop 写入和读取消息。

## 7. 缓存常见问题

### 缓存穿透

| 原因                     | 解决方案             |
| ---------------------- | ---------------- |
| 请求不存在的数据，该请求会穿透缓存到达数据库 | 对这些不存在的数据缓存一个空数据 |
|                        | 对这类请求进行过滤        |

### 缓存雪崩

在有缓存的系统中，系统非常依赖于缓存，缓存分担了很大一部分的数据请求。当发生缓存雪崩时，数据库无法处理这么大的请求，导致数据库崩溃。

| 原因              | 解决方案       |
| --------------- | ---------- |
| 系统刚启动，数据未加载到缓存中 | 进行缓存预热     |
| 缓存在同一时间大面积过期    | 合理设置缓存过期时间 |
| 缓存服务器宕机         | 使用分布式缓存    |

### 缓存一致性

缓存一致性要求数据更新的同时缓存数据也能够实时更新。

解决方案：

* 在数据更新的同时立即去更新缓存
* 在读缓存之前先判断缓存是否是最新的，如果不是最新的先进行更新

要保证缓存一致性需要付出很大的代价，缓存数据最好是那些对一致性要求不高的数据，允许缓存数据存在一些脏数据。

## 8. 高可用策略

### 主从同步

可以使用 slaveof host port 命令来让一个服务器成为另一个服务器的从服务器。

随着负载不断上升，主服务器可能无法很快地更新所有从服务器，为了解决这个问题，可以创建一个中间层来分担主服务器的复制工作。

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/I6ZRhkJWF1k37S4K.png)

#### 全同步过程

* Master创建快照文件，发送给Slave，并在发送期间使用缓冲区记录执行的写命令。快照文件发送完毕之后，Master开始向Slave发送存储在缓冲区中的写命令
* Slave丢弃所有旧数据，载入Master发来的快照文件
* Master将这期间的增量写命令发送给Slave

#### 增量同步过程

* Master接收到用户的操作指令（增删改查），判断是否需要传播到Slave
* Master将增删改的操作指令传播到其他Slave：
  * 对齐主从库
  * Master往响应缓存中写入指令，将缓存中的数据发送给Slave

#### Redis Sentinel

主从模式并不具备高可用性，当主节点出现问题，需要通过人工干预的方式把从节点设为主节点，还要通知应用程序更新主节点地址，这种方式非常繁琐，Redis引入了哨兵机制来解决这个问题：

* 监控：哨兵(sentinel) 会不断地检查你的Master和Slave是否运作正常
* 提醒：当被监控的某个 Redis出现问题时, 哨兵(sentinel) 可以通过 API 向管理员或者其他应用程序发送通知
* 自动故障迁移：当主数据库出现故障时自动将从数据库转换为主数据库

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/0tdPmZtIwumw5RBI.png)

### 分片

分片是指按照某种规则去划分数据，分散存储在多个节点上，降低单节点服务器的压力。

#### 哈希分布

将数据计算哈希值之后，按照哈希值分配到不同的节点上。例如有 N 个节点，数据的主键为 key，则将该数据分配的节点序号为：hash(key) % N.

**缺陷：**&#x5F53;节点数量变化时，几乎所有的数据都需要重新分布，将导致大量的数据迁移。

#### 一致性哈希

将哈希空间 \[0, 2^32 - 1] 看成一个哈希环，每个服务器节点都配置到哈希环上。每个数据对象通过哈希取模得到哈希值之后，存放到哈希环中顺时针方向第一个大于等于该哈希值的节点上。

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/I6ZRhkJWFk1a7S4K.png)

**节点宕机**

在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据。例如中节点C宕机，此时节点A、B、D不会受影响，只节点有C的数据被重定位到Node D。

**新增节点**

一致性哈希在增加或者删除节点时只会影响到哈希环中相邻的节点，例如下图中新增节点 X，只需要将它前一个节点 C 上的数据重新进行分布即可，对于节点 A、B、D 都没有影响。

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/7CxO9KPbMqL5tnx6.png)

**数据倾斜**

一致性哈希存在数据分布不均匀的问题，在节点数量很少且分布不均的情况下，各节点存储的数据量可能有很大的不同。

解决方式是通过增加**虚拟节点**，然后将虚拟节点映射到真实节点上。虚拟节点的数量比真实节点来得多，那么虚拟节点在哈希环上分布的均匀性就会比原来的真实节点好，从而使得数据分布也更加均匀。

![](https://github.com/Clloud/Notes/tree/b085adfa6214a665114ad10c2bf8bd4a4052a6ea/images/S3hwApzttaKxq1jB.png)