缓存

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

• 绝大部分请求是纯粹的内存操作

• 采用单线程，避免了不必要的上下文切换和竞争条件

• 非阻塞IO

1. 数据类型

常见数据类型

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

存储结构

扩展阅读：Redis底层数据结构

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

字典

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

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

跳跃表

扩展阅读：Redis-跳跃表

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

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

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

• 支持范围查询

• 简单，容易实现

• 支持无锁操作

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缓存

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

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

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

• 访问某个节点时，将其从原来的位置删除，并重新插入到链表头部，这样就能保证链表尾部存储的就是最近最久未使用的节点

• 当节点数量大于缓存最大空间时就淘汰链表尾部的节点

• 为了使删除操作时间复杂度为 O(1)，使用HashMap 存储 Key 到节点的映射，通过 Key 就能以 O(1) 的时间得到节点，然后再以 O(1) 的时间将其从双向链表中删除

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

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

6. 应用场景

分布式锁

扩展阅读：基于Redis的分布式锁实现

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

可以使用带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 命令来让一个服务器成为另一个服务器的从服务器。

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

全同步过程

• Master创建快照文件，发送给Slave，并在发送期间使用缓冲区记录执行的写命令。快照文件发送完毕之后，Master开始向Slave发送存储在缓冲区中的写命令

• Slave丢弃所有旧数据，载入Master发来的快照文件

• Master将这期间的增量写命令发送给Slave

增量同步过程

• Master接收到用户的操作指令（增删改查），判断是否需要传播到Slave

• Master将增删改的操作指令传播到其他Slave：

  • 对齐主从库

  • Master往响应缓存中写入指令，将缓存中的数据发送给Slave

Redis Sentinel

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

• 监控：哨兵(sentinel) 会不断地检查你的Master和Slave是否运作正常

• 提醒：当被监控的某个 Redis出现问题时, 哨兵(sentinel) 可以通过 API 向管理员或者其他应用程序发送通知

• 自动故障迁移：当主数据库出现故障时自动将从数据库转换为主数据库

分片

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

哈希分布

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

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

一致性哈希

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

节点宕机

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

新增节点

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

数据倾斜

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

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