优点
技术选型
- Redis
双写问题
架构部署模式
缓存穿透、击穿、血崩
使用规范
Redis 支持的数据类型以及底层实现
跳表实现
字典实现以及 Rehash
Redis 持久化
- RDB
- AOF
key 过期策略
内存淘汰策略
Redis LRU 的实现
Redis LFU 实现
参考

哪里用了缓存？为啥要用？不用行不行？如果用了以后可能会有什么不良的后果？

数据结构底层实现基本用法
持久化 RDB AOF
Key 过期、淘汰策略
Rehash 过程
分布式锁
Fail Over 过程
集群模式 16384 slot、选举过程 Raft 算法
参数配置
为什么快
与数据库数据一致性
优点
高性能

高并发
mysql 单机支撑到 2000QPS 也开始容易报警了

缓存与数据库双写不一致
缓存雪崩、缓存穿透、缓存击穿
缓存并发竞争

技术选型

Redis

Redis 内部使用文件事件处理器 file event handler ，这个文件事件处理器是单线程的，所以 Redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket，将产生事件的 socket 压入内存队列中，事件分派器根据 socket 上的事件类型来选择对应的事件处理器进行处理。

优点：

纯内存操作。
核心是基于非阻塞的 IO 多路复用机制。
C 语言实现，一般来说，C 语言实现的程序“距离”操作系统更近，执行速度相对会更快。
单线程反而避免了多线程的频繁上下文切换问题，预防了多线程可能产生的竞争问题。

Redis 6.0 开始引入多线程，Redis 的多线程部分只是用来处理网络数据的读写和协议解析，执行命令仍然是单线程。 之所以这么设计是不想 Redis 因为多线程而变得复杂，需要去控制 key、lua、事务、LPUSH/LPOP 等等的并发问题。

双写问题

Cache Aside Pattern

读的时候，先读缓存，缓存没有的话，就读数据库，然后取出数据后放入缓存，同时返回响应。
更新的时候，先更新数据库，然后再删除缓存。

架构部署模式

主从模式

复制过程

建立连接

从节点保存主节点 IP 和 port；
建立 socket 连接，负责后续的复制工作(接收 RDB 文件，接收命令传播)
主节点发送 ping 命令，检查 socket 是否能正常处理请求
身份验证；
从节点发送监听端口号给主节点

数据同步，从节点向主节点发送 psync 命令，决定全量还是部分复制
命令传播，从节点接收主节点发来的写命令

从服务器向主服务器发送 REPLCONF ACK 的心跳信息，replication_offset 是当前从服务器的复制偏移量。心跳检测用于检主从服务器的网络连接状态；检测命令丢失；防止主服务器在不安全情况下执行写命令。

复制办法：

全量复制

主节点收到全量复制请求，执行 bgsave 生成 RDB 文件，并使用一个缓冲区（复制缓冲区）记录从现在开始执行的写命令。
从节点接收 RDB 文件，清除原有旧数据，恢复至主节点执行 bgsave 时的状态
主节点复制缓冲区写命令到从节点，从节点执行这些命令
若从节点开启了 AOF，则触发 bgrewriteaof ，保证 AOF 文件与主节点一致

部分复制

部分复制的实现依赖三个重要的概念

复制偏移量 offset，主节点与从节点传递的字节数，判断是否一致，如果不同，则从复制挤压缓冲区种拿出数据复制给从节点，可以设定 repl-backlog-size 修改缓冲区的大小
复制积压缓冲区，由主节点维护的 FIFO 队列，默认 1MB，备份主节点最近发送给从节点数据。若主节点缓冲区中 offset 与从节点缓冲区中 offset 差距过大，就需要全量复制。
服务器运行 ID，Redis 启动时候会自动生成一个随机 ID（runid），当初次复制时，从节点保存主节点发过来的 runid；当断线重连时，从节点会将这个 runid 发给主节点，主节点再来判断是否进行部分复制。若 runid 和之前的相同，再去判断主从节点的复制缓冲区是否支持部分复制。

若 runid 不同，那么直接进行全量复制；若缓冲区 offset 差距过大，也全量复制

哨兵模式

哨兵模式基于主从复制，着眼于高可用，在 master 宕机时哨兵节点会自动将 slave 提升为 master，继续对外提供服务。

哨兵提供以下功能：

监控：哨兵会不断检查主节点、从节点是否运行正常
自动故障转移：当主节点不能正常工作，哨兵会选择将优先级最高的从节点升级为主节点，并将其它从节点从新的主节点进行复制
配置提供者：客户端初始化时，可以通过哨兵找到主节点的地址
通知：哨兵可以将故障转移的结果通知到客户端

定时任务
哨兵节点里面维护 3 个定时任务。

向主节点发送 info 命令获取最新的主从结构；
通过发布订阅功能获取其它哨兵节点的信息；
通过向其它节点发送 ping 命令进行心跳检测，判断是否下线。

主观下线
心跳检测任务中，若其它节点超过一定时间（down-after-milliseconds）没有正常回复，认为这个节点处于下线状态。

客观下线
哨兵节点对主节点客观下线之后，会通过 sentinel is-master-down-by-addr 命令询问其它哨兵节点该主节点的状态，若判断主节点下线的哨兵节点达到一定数值，则对主节点进行客观下线。客观下线时主节点才有的概念，客观下线用于后续的故障转移；而从节点或者哨兵节点发生故障，不会进行后续的客观下线和故障转移。
哨兵领导者节点：多个哨兵将会选举出一个哨兵作为领导者，由它进行后续的故障转移。选举算法为 Raft。

故障转移选举规则：

排查已经下线，不健康的从节点
选择优先级最高的，由参数 replica-priority 控制
若 2 一样，那么选择偏移量 offset 最大的
若 3 一样，选择 runid 最小的

集群模式

Redis Cluster 采用虚拟槽分区，将 Key 映射到 16384 个槽内。
CRC16(KEY) & 16383 来计算 key 属于哪个槽
其中 Master Node 负责处理客户端读写请求，Replica Node 负责对主节点复制。
集群的从节点在默认情况下只会对主节点进行复制，但是不会处理客户端发送的任何命令请求；每当从节点接收到命令请求的时候，它只会向客户端发送转向消息

缓存穿透、击穿、血崩
穿透：缓存中没有，数据库中也没有

解决方案：
布隆过滤器，向布隆过滤器中添加一个元素 key 时，我们通过多个 hash 函数，算出对应的值，然后将这个值所在的方格置为 1。查询的时候也是计算 Hash 值，若有一个格子不为 1，那么说明元素肯定不在数组中。布隆过滤器可以判断某个数据一定不存在，但是无法判断一定存在。
对空结果进行缓存返回

击穿：查询一个热点 key 的时候，由于 key 过期导致查询走到数据库中，造成数据库的压力大。

解决方案：

互斥访问，拿不到锁的进行等待，等获取到锁时已有缓存
热点 Key 不过期
降级策略
热点 Key 放到不同的服务器上面
加入二级缓存，提前加载 key 到内存中

血崩：某一时刻，大规模的 key 失效，导致请求全部走到数据库中，造成数据库压力大。

解决方案：

key 过期时间可以在原有时间上面增加一个随机值
限流
二级缓存

上面对应缓存问题的解决方案，可以互用；比如缓存雪崩，也可以使用互斥访问、降级策略等办法减少对数据库的压力，从而缓解存在的问题。

使用规范

必须
- 由小写字母、数字、英文点号、英文半角冒号组成，必须英文字母开头
- 格式：业务名、表名做前缀，冒号分隔，比如 mobileserver:userfreepasswordinfo:freepasswordtype
- 控制 key 长度，不该使用过长或含义不清的名称，上面可使用 mobileserver:userfreewd:freewdtype
- 不包含特殊字符：空格、换行、单双引号、下划线以及其他转义字符
- 设置过期时间
- 设置最大内存及最大内存淘汰策略（maxmemory-policy）参数。
- 客户端使用连接池
禁止
- 禁止命令：keys、flushall、flushdb、CONFIG
- 禁止 Big Key。如果 1MB 的 key 每秒重复写入 10 次，就会导致写入网络 IO 达 10MB。非字符串的 bigkey，不要使用 del 删除，使用 hscan、sscan、zscan 方式渐进式删除，同时要注意防止 bigkey 过期时间自动删除问题（例如一个 200 万的 zset 设置1小时过期，会触发 del 操作，造成阻塞）。
建议
- 所有 key 命名在同一个实体类中定义，方便管理，比如：RedisConstant.java
- hash、list、set、zset 元素个数不要超过 5000
- 使用合适的数据类型。常见的如：String 可以用作普通的 K-V、计数类；Hash 可以用作对象如商品、经纪人等，包含较多属性的信息；List 可以用作消息队列、粉丝/关注列表等；Set 可以用于推荐；SortedSet 可以用于排行榜等。
- 冷热数据分离，使用不频繁的用 MySQL 代替
- 必须要存储的大文本数据应该压缩后存储
- 高并发下建议客户端添加熔断功能(例如 netflix、hystrix)
- 不建议过多使用 Redis 事务功能，它不支持回滚

Redis 支持的数据类型以及底层实现

Redis 采用 对象 redisObject 来表示数据库中的键和值，当在 Redis 数据库中新建一个键值对时，会至少创建两个对象——键对象与值对象。
以 set msg “hello world”为例，键对象是一个包含了字符串值 msg 的对象，它一定是 String 类型，即 type = String；
值对象是包含了 hello world 值的对象，它的 type 可以为 String、List、Hash、Set、ZSet。所以一般来说，Redis 支持的数据类型 type，实际描述的是 Redis 值对象的类型

/*src/redis.h/redisObject */
typedef struct redisObject {
    // 刚刚好32 bits
    // 对象的类型，字符串/列表/集合/哈希表
    unsigned type:4;
    // 未使用的两个位
    unsigned notused:2; /* Not used */
    // 编码的方式，Redis 为了节省空间，提供多种方式来保存一个数据
    // 譬如：“123456789” 会被存储为整数123456789
    unsigned encoding:4;
    // 当内存紧张，淘汰数据的时候用到
    unsigned lru:22; /* lru time (relative to server.lruclock) */
    // 引用计数
    int refcount;
    // 数据指针，指向真正的数据
    void *ptr;
} robj;

其次，Redis 值对象可以指定不同的编码方式 encoding，一种对象类型，可以有多种编码方式实现。

String

使用简单动态字符（SDS）串保存 String 类型的 value。

SDS 有专门的结构记录已使用的空间长度，所以能够在 O(1) 时间获取到值的长度。
预分配空间为将来的 value 值增长做保留，使得修改 value 值的时候可以不用重新分配内存

List

保存的元素顺序基于插入顺序；当数据量比较小或者存放的较短的字符串的时候，Redis 会使用 ZipList 保存元素

struct ziplist<T> {
  int32 zlbytes; // 整个压缩列表占用字节数
  int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
  int16 zllength; // 元素个数
  T[] entries; // 元素内容列表，挨个挨个紧凑存储
  int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

ZipList 可以方便查找第一个元素和最后一个元素，元素列表 entries 采用数组方式存储；ZipList 是一整块连续的内存，但是每次修改操作都会进行内存的 realloc，性能较差，所以适用于数据量比较小的场合。

ZipList entry 的具体内容：

在 Redis 3.2 版本之后，当数据量比较大的时候，Redis 采用 QuickList 保存 List 数据结构的元素，QuickList 其实就是 LinkList 和 ZipList 的结合体。QuickList 元素有前后指针可以进行双向遍历，每个节点都是一个 ZipList，在空间存储上效率较高。

Hash

Redis 字典用途有两个，首先实现数据库键空间（Key space），Redis 是一个保存键值对的数据库，数据库的键值对由字典保存，每个数据库都有一个对应的字典，这个字典被称之为键空间（key space）。
其次字典还作为 Hash 类型键的底层实现之一，Hash 类型的 value 底层存储结构可以是 ZipList 或者字典，当哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节 and 哈希对象保存的键值对数量小于 512 个时使用 ZipList，否则使用字典
可以设定 hash_max_ziplist_entries 和 hash_max_ziplist_value 的值控制两者的存储转换。

Hash 对象的 ZipList 编码实现

Hash 对象 hashtable 编码实现

Hash 对象的 hashtable 编码实现也是用到了字典dict，哈希对象中的每个键值对都使用一个字典键值对保存。
Redis 使用对象（RedisObject）表示数据库中的键与值，分别对应键对象和值对象，键对象总是一个字符串对象，而值对象根据编码方式不同，可以有不同实现（字符串对象、列表对象、哈希对象、集合对象、有序集合对象等）。
举个例子 HSET profile age 25，那么键对象就是一个包含了 profile 字符串的对象，值对象就是包含了 age-25 字典的对象。
如果用 hashtable 作为编码，那么 Redis 值对象对应的存储实现如下，ptr 指针也是指向 dict 字典。

Set

保存的元素唯一，无序，当保存的元素时整数值并且元素数量不超过 512 个时，使用 intset 保存元素，否则使用 hashtable 保存元素。

整数集合 intset：用于保存整数值的数据结构，可以保存 int16，int32，int64 类型的整数值。数据项按照顺序排列，不会出现重复元素。 ```java typedef struct intset{ //编码方式 uint32_t encoding; //集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[];

}intset;


- HashTable 保存元素时，此时 key 为 set 的值 ，value = null
<a name="VWml0"></a>
### intSet 升级与降级
TODO
<a name="hcv4x"></a>
## ZSet
与 Set 类型，不同的是元素还关联一个 float 类型的 score，元素以 score 进行排序。另外与 Set 不同的是它支持取出一个范围内的元素（top 10，bottom 10）
```java
 /*
 * 有序集合
 */
typedef struct zset {
    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;
    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;
} zset;

当数据量较小时，使用 ZipList 实现，否则使用 SkipList + Dict 保存元素

SkipList 是一种有序的数据结构，每个节点维护多个指向其它节点的指针，可以在小于 O(N) 的时间复杂度情况下找到数据

ZSET 不使用 AVL 树的原因：

范围查找难度相比跳表大
插入删除节点引发树的调整，而跳表只需要改变指针

Bitmap

它并不是一种实际的数据类型，而是基于 String 类型的一种位操作，String 最大支持长度为 512MB，所以支持的位操作可以达到 2^32 个。
使用位图的好处在于它能够使用极小的空间传递更多的信息

HyperLogLogs

一种计算概率的数据结构，用于估计集合的基数，

Stream

跳表实现

跳跃表 SkipList 是一种有序数据结构，通过在每个节点中维持多个指向其它节点的指针，达到快速访问节点的目的
平均时间复杂度 O（logN），在大部分情况下，跳跃表的效率与平衡树相近，由于跳跃表实现的简易性，所以 Redis 使用跳表代替平衡树。
ZSET 存储元素，使用了哈希表以及、SkipList 作为底层实现。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

zskiplist 数据结构

执行添加命令，ZADD o1 1.0 o2 2.0 o3 3.0 ，具体节点信息展示如下：

Redis 跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义；其中 zskiplist 保存跳表的整体信息，zskiplistNode 表示具体的跳表节点
zskiplist 跳表的整体属性介绍：

typedef struct zskiplist {
    // 头节点，尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量（不算表头）
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

zskiplistNode 跳表节点的属性介绍：

查找过程

跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。
如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。

插入过程

搜索当前节点的插入位置，搜索过程和上面遍历过程一样
生成插入节点，随机生成 1~32 之间的值作为节点的 level
重排前进指针
重排后退指针
Q&A

为什么层数最大是 32

当层数有 32 层时，第 0 层的节点将有 2^64 个，够用。

zset 为什么不使用平衡树

使用平衡时时，节点变化时，重平衡操作比较复杂，而跳表实现简单。
跳表支持范围查询

字典实现以及 Rehash

Redis 字典 dict 用途有两个，首先实现数据库键空间（Key space），Redis 是一个保存键值对的数据库，数据库的键值对由字典保存，每个数据库都有一个对应的字典，这个字典被称之为键空间（key space）。
其次字典 dict 还作为 Hash 类型键的底层实现之一，当 Hash 类型的键使用 hashtable 编码时，也使用 dict 进行存储。
Redis 采用链地址法解决 key hash 冲突问题，以头插的方式插入到冲突节点的前面。

底层源码
单机 Redis 默认有 16 个 redisDb ，通过 select(n) 选择使用哪个 redisDb cluster 模式下只有一个 redisDb，每个 redisDb 里面都有一个字典 dict，用于保存 set 进来的键值对。

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

字典 dict 里面包含两个 dictht，ht[0]，ht[1]，ht[1] 用于渐进式 rehash；

typedef struct dict {
    dictType *type; // 字典类型
    void *privdata; // 私有数据
    dictht ht[2];  // 哈希表[两个]
    long rehashidx; // 记录rehash 进度的标志，值为-1表示rehash未进行
    unsigned long iterators; //  当前正在迭代的迭代器数
} dict;
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

哈希表 dictht 里面包含一个 table，里面的节点就是哈希表节点 dicEntry，dictEntry 里面保存着元素的地址 *val，和指向下一个 dictEntry 的指针，这个指针将哈希值相同的键值对连接在一起。

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; // 有符号整形
        double d; // 浮点型
    } v;
    struct dictEntry *next; //指向下一个哈希表节点
} dictEntry;

所以 Redis Key 的分布，可以用下图表示：

rehash 过程
当哈希表 dict 需要扩展或者收缩时，Redis 会进行 rehash 操作，即将 h[0] 里面的元素移到 h[1]
rehash 的过程不是一次性的，而是将 rehash 所需的计算工作分摊到每次对字典进行增删改查的操作上。
字典维护 rehashidx 字段，从 0 开始，每次将 rehashidx 上面的键值对 rehash 到 ht[1]，然后 rehashidx++，最终 ht[0] 所有键值对移到 ht[1]，那么 rehashidx = -1，表示 rehash 完成。
渐进式 rehash 过程中，Redis 会同时使用 ht[0] 和 ht[1] 两张表，delete，find，update 操作会在两个哈希表上运行。rehash 过程中，新增的键值对保存到 ht[1]，保证 rehash 执行完成时，ht[0] 为空表，然后将 ht[1] = ht[0]。

Rehash 时机
负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
当服务器没有执行 BGSAVE or BGREWRITEAOF 命令时，若负载因子 >=1，哈希表将会执行扩展操作；
当服务器执行 BGSAVE or BGREWRITEAOF 命令时，若负载因子 >= 5，哈希表将会执行扩展操作。

Redis 持久化

官方文档：http://redisdoc.com/topic/persistence.html

RDB

数据生成 rdb 结尾的快照文件，采用二进制 + 数据压缩的方式写磁盘，体积小恢复快，适合全量复制。

手动触发

save，阻塞 Redis 服务器不能处理任何请求，禁止使用
bgsave，创建子进程，让子进程创建快照；同一时刻只会有一个 bgsave 命令执行，避免产生竞态条件

自动触发
配置文件 save m n，m 秒内发生 n 次变化时，触发 bgsave；save m n 可以多行，主要满足一条即可触发。Redis的 save m n，是通过serverCron函数、dirty 计数器、和 lastsave 时间戳来实现的。每隔100ms，执行serverCron函数；在serverCron函数中，遍历save m n配置的保存条件，只要有一个条件满足，就进行 bgsave。对于每一个save m n条件，只有下面两条同时满足时才算满足：当前时间 - lastsave > m，dirty >= n
- serverCron 100ms 执行一次
- dirty 记录上一次 save 服务器执行修改命令次数
- lastsave 表示上次 bgsave 时间。
主从复制场景
shutdown 命令

RDB 文件结构

(大写表示常量，小写表示变量)
REDIS 常量，表示 RDB 文件
db_version 4 字节，版本号
databases 包含 0 或多个数据库
- SELECTDB，1 字节，表示接下来是个数据库号码
- db_number
- key_value_pairs，键值对数据
  - EXPIRETIME_MS
  - ms，毫秒为单位
  - type，value 的类型，对象类型，底层编码
  - key，字符串对象，编码方式和 REDIS_RDB_TYPE_STRING 类型的 value 一样
  - value
EOF 常量，1 字节，RDB 正文内容结束
check_sum，8 字节无符号整数，前 4 部分计算得出，检查 RDB 是否有损坏

AOF
Append Only File，主线程写命令记录缓冲区再追加到日志文件，生成 aof 结尾的文件，纯文本格式
支持秒级持久化，兼容性好，但文件大，恢复速度慢。开启 AOF，appendonly yes，默认是 no

持久化
AOF 持久化包括命令追加、文件写入、文件同步三个步骤。
命令追加

执行完写命令后，写命令会追加到 aof_buf 缓冲区末尾

文件写入与同步

appendfsync 选项值控制 flushAppendOnlyFile 函数的行为，即控制写入到磁盘的时机。

always，写入 aof_buf 后立刻调用系统命令 fsync 同步到 AOF 文件中
no，写入 aof_buf 后调用 write 操作，操作系统自己进行 fsync 同步，时间不可控，堆积数据多
everysec，写入 aof_bug 后调用 write 操作，子线程每秒 fsync 同步到 AOF 文件中

AOF 后台文件重写

主要原理就是 Redis 创建一个新的 AOF 文件，用一条命令代替之前记录这个键值对操作的多个命令，去除过期键值对，使用子进程写入到新的 AOF 文件中，然后替换。
使用子进程而不是子线程，是为了避免产生锁竞争的问题，保证数据的安全性。
为了避免重写过程中数据库状态和 AOF 状态的不一致，使用 AOF 重写缓冲区保存写命令；子进程完成 AOF 重写操作后，会通知父进程，然后父进程将 AOF 重写缓冲区里面的数据写入到新的 AOF 文件，并替换原有文件。

触发机制
手动触发，执行 bgrewriteaof 命令
自动触发，设定触发阈值
- auto-aof-rewrite-min-size：执行 AOF 重写时，文件的最小体积，默认值为64MB。
- auto-aof-rewrite-percentage：执行 AOF 重写时，当前 AOF大小(即 aof_current_size) 和上一次重写时 AOF 大小(aof_base_size)的比值。

key 过期策略

删除到达过期时间的 Key，一般有以下几种实现

定时检查删除

为每个 Key 创建一个定时器，到达删除时间进行删除操作。
但是这样会占用大量 CPU 的资源去处理过期数据

惰性检查删除

访问 Key 的时候，再去判断 Key 是否过期，若已过期则删除。
对内存不太友好，若 Key 一直没访问，就永远不会删除

定期检查删除

隔一段时间，扫描 Redis 过期字典 expires中的 Key，清除一部分过期的 Key。属于前两种方法的折中。

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* 过期字典 Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

可以通过设置 hz 参数，控制定期删除的频率。 hz 10 表示每秒运行 10 次
当服务器运行在复制模式下时，从服务器的过期键删除策略由主服务器控制，由主服务器发送 DEL 命令才会删除；就算从服务器发现已经过期，也不会主动删除。
Redis 采用惰性检查删除 + 定期检查删除实现 Key 的过期

内存淘汰策略

通过设置 maxmemory-policy 来设置内存淘汰策略；若没有设置 maxmemory ，在 64 位系统上将没有内存限制；32 位系统默认为 3GB

noeviction：默认策略，不会剔除任何数据，拒绝所有写入操作并返回客户端错误信息”(error) OOM command not allowed when used memory”，此时Redis只响应读操作，不建议使用。
从所有结果集中淘汰
- allkeys-random：从所有 Key 中随机挑选 Key 进行淘汰
- allkeys-lru （Least Recently Used）：从所有 Key 中，挑选最近使用时间距离现在最远的 Key 进行淘汰
- allkeys-lfu：Redis 4.0 开始支持，从所有 Key 中，挑选使用频率最低的 Key 进行淘汰
设置了过期时间中淘汰
- volatile-random:随机删除过期键，直到腾出足够空间为止。
- volatile-lru：即超过最大内存后，在过期键中使用 LRU 算法进行key 的剔除，保证不过期数据不被删除，但是可能会出现 OOM 问题。
- volatile-lfu
- volatile-ttl：根据键值对象的ttl属性，删除最近将要过期数据。如果没有，回退到noeviction策略。

Redis LRU 的实现

typedef struct redisObject {
    ...
    unsigned lru:LRU_BITS; //LRU_BITS为24bit
    ...
} robj;
robj *lookupKey(redisDb *db, robj *key, int flags) {
    ...
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { //如果配置的是lfu方式，则更新lfu
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK();//否则按lru方式更新
            }
    ...
}

每个 redisObject 都有一个 24 bit 的 lru 字段，保存的是时间戳，每次 get 之后都会更新这个 lru 的值。
Redis 首先将随机选出 server.maxmemory_samples 个 Key 放到 pool 中直到 pool 满，下次随机选出来的 key 的 lru 的值要小于 pool 中的最小值才能继续放到 pool 中。
淘汰的时候将 pool 中 lru 值最小的 key 进行淘汰。这是一种近似 LRU 的算法，因为内存的限制，不可能完全的把所有 Key 遍历，然后找到最小的 lru 的 Key。

Redis LFU 实现

Redis 也是使用近似 LFU 的算法实现 LFU 功能，通过使用 Morris counter 去评估 Redis 对象的访问频次。
lfu-log-factor 10，计数器的增长速度，值越大 counter 增长越慢
lfu-decay-time 1 ，以分钟为单位的数值，用于调整 counter 的减少速度
Approximate counting algorithm
Using Redis as an LRU cache
Approximate counting algorithm

参考

Redis为什么默认16个数据库？ https://www.51cto.com/article/605020.html

Redis

优点

技术选型

Redis

双写问题

架构部署模式

主从模式

哨兵模式

集群模式

缓存穿透、击穿、血崩

使用规范

Redis 支持的数据类型以及底层实现

String

List

Hash

Set

Bitmap

HyperLogLogs

Stream

跳表实现

zskiplist 数据结构

查找过程

插入过程

Q&A

字典实现以及 Rehash

Redis 持久化

RDB

手动触发

自动触发

RDB 文件结构

AOF

持久化

AOF 后台文件重写

触发机制

key 过期策略

内存淘汰策略

Redis LRU 的实现

Redis LFU 实现

参考