在计算机领域，缓存在程序设计过程中扮演着重要角色。浏览器的资源缓存策略是影响 web 网站性能的一个关键因素；mysql 的 Buffer Pool 极大的提高了数据库的查询效率；redis 作为被广泛应用的缓存数据库，提供了丰富的数据结构和缓存策略来满足开发者的需求。缓存在现代计算机系统中无处不在，是一个非常深入、广泛的话题，本文的目的是从众多已有的系统设计中，提取出有关系统缓存设计的精要，主要从三个方面展开：

• 多级缓存

• 缓存淘汰策略

• 缓存安全

在讨论这些话题的同时，笔者会结合很多实际的例子阐述，其中会涉及到 PHP 源码、redis 源码、浏览器的缓存策略、mysql 数据存储设计、缓存淘汰算法等偏底层的内容，如果你是一个比较资深的开发工程师，对这些内容都比较了解，本文将非常适合您。为了照顾初学者，涉及到难懂重要的知识点笔者也将会尽可能的描述清楚。本文篇幅有点长，请读者做好心理预期！

1.多级缓存

1.1 存储器层次结构

计算机使用不同的存储技术对数据进行访问，时间差异很大。速度较快的技术每个字节的成本要比速度较慢的技术高，而且容量较小。CPU 和主存(内存)之间的速度差距在增大。基于这种特性，所有的现代计算机系统都使用了金字塔式的存储器层次结构。如下图所示：

从高层往低层走，存储设备变得更慢、更便宜、容量更大。最高层(L0)是少量快速的 CPU 寄存器，CPU 可以在一个时钟周期内访问它们 (一个时钟周期通常小于 1ns)；接下来是一个或多个中小型 SRAM 高速缓存存储器，可以在几个 CPU 时钟周期内访问它们；然后是一个大的基于 DRAM 的主存，可以在几十到几百个 CPU 时钟周期内访问它们；接下来是慢速但是容量很大的本地磁盘(通常是 SSD)；最后有些系统甚至包括了一层附加的网络文件系统(Network File System,NFS)，比如说腾讯云提供的 CFS 服务就可以通过挂载到多个服务器实现分布式的数据共享。

下面我们从 CPU 的角度以具体的数据来量化对比 CPU、磁盘、网络的速度，对计算机各个组件不同的速度差异有个更直观的认识。

CPU 和内存之间的瓶颈被称为冯诺依曼瓶颈, 它们之间至少有着几百倍的速差，可以想象成天上人间，天上一天，地下一年。普通的磁盘读取数据就更慢了，寻址时间 10ms，对比 CPU 的基本单位时长是 10 个月，可以生一次孩子了！所以说 IO 设备是计算机系统的瓶颈。以此想到我们网络中的 API 请求，动不动就是一百多毫秒，对比 CPU 的基本单位就是十几年！

相信通过以上描述，读者对计算机组件之间数据处理速度有了深入的印象。

1.2 局部性原理

一个编写良好的计算机程序通常具有良好的局部性(locality)。也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理(principle of locality)，是一个持久的概念，对硬件和软件系统的设计和性能都有着极大的影响。

局部性通常有两种不同的形式: 时间局部性(temporal locality) 和 空间局部性(spatial locality)。

• 时间局部性：被引用过一次的内存位置很可能在不远的将来再被多次引用。

• 空间局部性：如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

Mysql 数据库 Innodb 引擎的设计就很好的考虑了局部性原理。

Innodb 引擎以页的形式组织数据，页的默认大小是 16KB,存放用户数据记录的页叫“数据页”，为了实现数据更快的查找，InnoDB 使用 B+树的结构组织存放数据，最下层的叶子节点存放“数据页”，在“数据页”的上层抽出相应的“目录页”，最终形成的基本结构如下图所示：

数据页中记录是连续存放的，当需要访问某个页的数据时，就会把完整的页的数据全部加载到内存中，也就是说即使我们只需要访问一个页的一条记录，那也需要先把整个页的数据加载到内存中。这就利用了局部性原理中的“空间局部性”。将整个页加载到内存中后就可以进行读写访问了，在进行完读写访问之后并不着急把该页对应的内存空间释放掉，而是将其缓存到 Buffer Pool 中，这样将来有请求再次访问该页面时，就可以省去磁盘 IO 的开销了，这又利用了局部性原理中的“时间局部性”。

局部性原理是系统缓存设计中非常重要的理论基石，下文还会多次提到。

1.3 Cpu 高速缓存

本节我们来聊一聊 Cpu 高速缓存，Cpu 高速缓存是影响程序性能的一个关键因素。

1.3.1 什么是 Cpu 高速缓存?

笔者直接引用维基百科中对 Cpu 高速缓存的描述：

在计算机系统中，CPU 高速缓存（英语：CPU Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于 CPU 寄存器。其容量远小于内存，但速度却可以接近处理器的频率。 当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。 缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。 在处理器看来，缓存是一个透明部件。因此，程序员通常无法直接干预对缓存的操作。但是，确实可以根据缓存的特点对程序代码实施特定优化，从而更好地利用缓存。

1.3.2 为什么需要有 Cpu 高速缓存?

上文中我们提到冯诺依曼瓶颈。随着工艺的提升，最近几十年 CPU 的频率不断提升，而受制于制造工艺和成本限制，目前计算机的内存在访问速度上没有质的突破。因此，CPU 的处理速度和内存的访问速度差距越来越大，这种情况下传统的 CPU 直连内存的方式显然就会因为内存访问的等待，导致计算资源大量闲置，降低 CPU 整体吞吐量。同时又由于内存数据访问的热点集中性，在 CPU 和内存之间用较为快速而成本较高（相对于内存）的介质做一层缓存，就显得性价比极高了。

1.3.3 Cpu 高速缓存架构

早期计算机系统的存储器层次结构只有三层：CPU 寄存器、DRAM 主存储器和磁盘存储。由于 CPU 和主存之间逐渐增大的差距，系统设计者被迫在 CPU 寄存器文件和主存之间插入了一个小的 SRAM 高速缓存存储器，称为 L1 高速缓存(一级缓存),如下图所示。L1 高速缓存的访问速度几乎和寄存器相差无几。

随着 CPU 和主存之间的性能差距不断增大，系统设计者在 L1 高速缓存和主存之间又插入了一个更大的高速缓存，称为 L2 高速缓存，可以在大约 10 个时钟周期内访问到它。现代的操作系统还包括一个更大的高速缓存，称为 L3 高速缓存,在存储器的层次结构中，它位于 L2 高速缓存和主存之间，可以在大约 50 个周期内访问到它。下图是简单的高速缓存架构：

数据的读取和存储都经过高速缓存，CPU 核心与高速缓存有一条特殊的快速通道；主存与高速缓存都连在系统总线上（BUS），这条总线还用于其他组件的通信。

1.3.4 PHP7 数组的设计

关于 Cpu 高速缓存的应用，PHP7 数组的设计是一个非常经典的案例。在 PHP 中数组是最常用的一种数据类型，提升数组的性能会使程序整体性能得到提升。我们通过对比 PHP7 和 PHP5 数组的设计，来学习一下 PHP 设计者为了提升 PHP 数组的性能，都进行了哪些思考。

我们先来总结一下 PHP 数组的特性：

• php 中的数组是一个字典 dict，存储着 key-value 对，通过 key 可以快速的找到 value,其中 key 可以是整形，也可以是字符串（hash array 和 packed array）。

• 数组是有序的：插入有序、遍历有序。

PHP 中数组使用 hashTable 实现，我们先来了解一下什么是 hashTable。

hashTable 是一种通过某种 hash 函数将特定的 key 映射到特定 value 的一种数据结构，它维护着键和值的一一对应关系，并且可以快速的根据键找到值(o(1)). 一般 HashTable 的示意图如下:

1) key: 通过key可以快速找到value。一般可以为数字或者字符串。2) value: 值可以为复杂结构3) bucket: 桶，HashTable存储数据的单元，用来存储key/value以及其他辅助信息的容器4) slot:槽，HashTable有多少个槽，一个bucket必须属于具体的某一个slot，一个slot可以有多个   bucket5) 哈希函数:一般都是自己实现（time33），在存储的时候，会将key通过hash函数确定所在的slot6) 哈希冲突: 当多个key经过哈希计算后，得到的slot位置是同一个，那么就会冲突，一般这个时候会有   2种解决办法:链地址法和开放地址法。其中php采用的是链地址法，即将同一个slot中的bucket通过   链表连接起来复制代码

为了实现数组的插入有序和遍历有序，PHP5 使用 hashTable + 双链表实现数组，如下图是将 key 分别为：“a”,"b","c","d",值为“1”,"2","3","4" 插入到数组中后的效果：

上图中 b,c,d 所在的 bucket 被存分配到了同一个 slot，为了解决 hash 冲突，slot 中多个 bucket 通过双向链表关联，称为局部双向链表；为了实现有序，slot 之间也通过双向链表关联，称为全局双向链表。

了解 php5 数组的实现原理之后，我们发现其中影响性能的两个关键点：

1. 频繁的内存分配！每向数组中添加一个元素，都需要申请分配一个 bucket 大小的内存，然后维护多个指针。虽然 php 是基于内存池的管理方式(预先申请大块内存进行按需分配)，但是内存分配带来的性能损耗是不可忽略的。

2. Cpu 高速缓存命中率低！因为 bucket 与 bucket 之间是通过链表指针连接的，bucket 随机分配，内存基本不连续，导致 Cpu cache 降低，不能给遍历数组带来性能提升。

针对以上两点，php7 对 hashTable 的设计进行了改造。既然是字典，还是要使用 hashTable,但 php7 数组的实现去掉了 slot，bucket 的分配使用了连续内存；bucket 间不再使用真实存在的指针进行维护，bucket 只维护一个在数组中的索引，bucket 与 bucket 之间通过内存地址进行关联，如下图所示:

PHP7 中数组是如何解决 hash 冲突的？

PHP7 对 zval 进行了改造，zval 中有一个 u2 的 union 联合体，占用 4 字节大小，存放一些辅助信息。PHP7 数组中的 value 也是一个个的 zval 指针，当发生 hash 冲突时，zval 中 u2 部分存放的 next 指针存放指向下一个 bucket 数组中的索引，通过这样一种逻辑上的链表就巧妙解决 hash 冲突。关于 PHP7 中 zval 的设计，推荐大家阅读鸟哥的文章：深入理解 PHP7 内核之 zval

可以看到，php7 中 hashTable 对性能提升最重要的改动是 bucket 的分配使用了连续内存。这样不仅省去了数组元素插入时频繁的内存分配开销；遍历数组也只需要一个 bucket 一个 bucket 的访问就好了，Cpu 高速缓存命中率非常高，极大的提升了数组性能；符合局部性原理。

更多关于 PHP5 和 PHP7 数组的设计细节，推荐大家研究这篇文章：【PHP7 源码学习】系列之数组实现

1.4 浏览器的多级缓存机制

举一个多级缓存的应用案例：浏览器对我们生活的影响是不言而喻的，现代的浏览器已经不同往昔了，快速的信息加载，顺畅的用户交互，这一切都得益于网络技术的普及、H5 标准特性的推广应用，当然还有一个重要因素，那就是浏览器的缓存策略。本节我们就来简单介绍一下浏览器的多级缓存机制。

对于一个数据请求来说，可以分为发起网络请求、后端处理、浏览器响应三个步骤。浏览器缓存可以帮助我们在第一和第三步骤中优化性能。比如说直接使用缓存而不发起请求，或者发起了请求但后端存储的数据和前端一致，那么就没有必要再将数据回传回来，这样就减少了响应数据。

浏览器有四种缓存级别，它们各自都有优先级。

• Service Worker

• Memory Cache

• Disk Cache

• Push Cache

当依次查找缓存且都没有命中的时候，才会去请求网络。

1.4.1 Service Worker

Service Worker 是运行在浏览器背后的独立线程，一般可以用来实现缓存功能。使用 Service Worker 的话，传输协议必须为 HTTPS。因为 Service Worker 中涉及到请求拦截，所以必须使用 HTTPS 协议来保障安全。Service Worker 的缓存与浏览器其他内建的缓存机制不同，它可以让我们自由控制缓存哪些文件、如何匹配缓存、如何读取缓存，并且缓存是持续性的。

Service Worker 实现缓存功能一般分为三个步骤：首先需要先注册 Service Worker，然后监听到 install 事件以后就可以缓存需要的文件，那么在下次用户访问的时候就可以通过拦截请求的方式查询是否存在缓存，存在缓存的话就可以直接读取缓存文件，否则就去请求数据。

当 Service Worker 没有命中缓存的时候，我们需要去调用 fetch 函数获取数据。也就是说，如果我们没有在 Service Worker 命中缓存的话，会根据缓存查找优先级去查找数据。但是不管我们是从 Memory Cache 中还是从网络请求中获取的数据，浏览器都会显示我们是从 Service Worker 中获取的内容。

1.4.2 Memory Cache

Memory Cache 也就是内存中的缓存，主要包含的是当前页面中已经抓取到的资源,例如页面上已经下载的样式、脚本、图片等。读取内存中的数据肯定比磁盘快，内存缓存虽然读取高效，可是缓存持续性很短，会随着进程的释放而释放。 一旦我们关闭 Tab 页面，内存中的缓存也就被释放了。

当我们访问过页面以后，再次刷新页面，可以发现很多数据都来自于内存缓存

内存缓存中有一块重要的缓存资源是 preloader 相关指令（例如<link rel="prefetch">）下载的资源。众所周知 preloader 的相关指令已经是页面优化的常见手段之一，它可以一边解析 js/css 文件，一边网络请求下一个资源。

需要注意的事情是，内存缓存在缓存资源时并不关心返回资源的 HTTP 缓存头 Cache-Control 是什么值，同时资源的匹配也并非仅仅是对 URL 做匹配，还可能会对 Content-Type，CORS 等其他特征做校验。

为什么浏览器数据不都存放在内存中？

这个问题就算我不回答，读者肯定也都想明白了，计算机中的内存一定比硬盘容量小得多，操作系统需要精打细算内存的使用，所以能让我们使用的内存必然不多。谷歌浏览器是公认的性能出众的，但是它占用的内存也是很大的。

1.4.3 Disk Cache

Disk Cache 也就是存储在硬盘中的缓存，读取速度慢点，但是什么都能存储到磁盘中，比之 Memory Cache 胜在容量和存储时效性上。

在所有浏览器缓存中，Disk Cache 覆盖面基本是最大的。它会根据 HTTP Herder 中的字段判断哪些资源需要缓存，哪些资源可以不请求直接使用，哪些资源已经过期需要重新请求。并且即使在跨站点的情况下，相同地址的资源一旦被硬盘缓存下来，就不会再次去请求数据。绝大部分的缓存都来自 Disk Cache。

浏览器会把哪些文件丢进内存中？哪些丢进硬盘中？

关于这点，网上说法不一，不过有些观点比较靠得住：对于大文件来说，大概率是不存储在内存中的，另外如果当前系统内存使用率高的话，文件优先存储进硬盘。

1.4.4 Push Cache

Push Cache（推送缓存）是 HTTP/2 中的内容，当以上三种缓存都没有命中时，它才会被使用。它只在会话（Session）中存在，一旦会话结束就被释放，并且缓存时间也很短暂，在 Chrome 浏览器中只有 5 分钟左右，同时它也并非严格执行 HTTP 头中的缓存指令。

Push Cache 在国内能够查到的资料很少，也是因为 HTTP/2 在国内不够普及。这里推荐阅读 Jake Archibald 的 HTTP/2 push is tougher than I thought 这篇文章，文章中的几个结论是：

• 所有的资源都能被推送，并且能够被缓存,但是 Edge 和 Safari 浏览器支持相对比较差

• 可以推送 no-cache 和 no-store 的资源

• 一旦连接被关闭，Push Cache 就被释放

• 多个页面可以使用同一个 HTTP/2 的连接，也就可以使用同一个 Push Cache。这主要还是依赖浏览器的实现而定，出于对性能的考虑，有的浏览器会对相同域名但不同的 tab 标签使用同一个 HTTP 连接。

• Push Cache 中的缓存只能被使用一次

• 浏览器可以拒绝接受已经存在的资源推送

• 你可以给其他域名推送资源

如果以上四种缓存都没有命中的话，那么只能发起请求来获取资源了。

浏览器的多级缓存机制到这里就介绍完了，大家可以看到，浏览器多级缓存机制的实现思路，和我们前边说到的计算机系统多级缓存的知识是相呼应的，并且也满足局部性原理。浏览器缓存还有更多值得我们深入学习的内容，感兴趣的读者可以研究一下这篇文章：深入理解浏览器的缓存机制

2. 缓存淘汰策略

根据金字塔存储器层次模型我们知道：CPU 访问速度越快的存储组件容量越小。在业务场景中，最常用的存储组件是内存和磁盘，我们往往将常用的数据缓存到内存中加快数据的读取速度，redis 作为内存缓存数据库的设计也是基于这点考虑的。但是服务器的内存有限，不可能不断的将数据存入内存中而不淘汰。况且内存占用过大，也会影响服务器其它的任务，所以我们要做到通过淘汰算法让内存中的缓存数据发挥最大的价值。

本节将介绍业务中最常用的三种缓存淘汰算法:

• Least Recently Used（LRU）淘汰最长时间未被使用的页面，以时间作为参考

• Least Frequently Used(LFU)淘汰一定时期内被访问次数最少的页面，以次数作为参考

• 先进先出算法（FIFO）

笔者会结合 Redis、Mysql 中缓存淘汰的具体实现机制来帮助读者学习到，Mysql 和 Redis 的开发者是怎样结合各自的业务场景，对已有的缓存算法进行改进来满足业务需求的。

2.1 Least Recently Used（LRU）

LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。该思想非常契合业务场景 ，并且可以解决很多实际开发中的问题，所以我们经常通过 LRU 的思想来作缓存，一般也将其称为 LRU 缓存机制。

2.1.1 LRU 缓存淘汰算法实现

本节笔者以 leetcode 上的一道算法题为例，使用代码(Go 语言)实现 LRU 算法，帮助读者更深入的理解 LRU 算法的思想。

leetcode 146: LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例：

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 复制代码

我们采用 hashmap+双向链表的方式进行实现。可以在 O(1)时间内完成 put 和 get 操作，同时也支持 O(1) 删除第一个添加的节点。

使用双向链表的一个好处是不需要额外信息删除一个节点，同时可以在常数时间内从头部或尾部插入删除节点。

一个需要注意的是，在双向链表实现中，这里使用一个伪头部和伪尾部标记界限，这样在更新的时候就不需要检查是否是 null 节点。

代码如下：

type LinkNode struct {    key, val  int    pre, next *LinkNode}
type LRUCache struct {    m          map[int]*LinkNode    cap        int    head, tail *LinkNode}
func Constructor(capacity int) LRUCache {    head := &LinkNode{0, 0, nil, nil}    tail := &LinkNode{0, 0, nil, nil}    head.next = tail    tail.pre = head    return LRUCache{make(map[int]*LinkNode), capacity, head, tail}}复制代码

这样就初始化了一个基本的数据结构,大概是这样：

接下来我们为 Node 节点添加一些必要的操作方法，用于完成接下来的 Get 和 Put 操作：

func (this *LRUCache) RemoveNode(node *LinkNode) {    node.pre.next = node.next    node.next.pre = node.pre}
func (this *LRUCache) AddNode(node *LinkNode) {    head := this.head    node.next = head.next    head.next.pre = node    node.pre = head    head.next = node}
func (this *LRUCache) MoveToHead(node *LinkNode) {    this.RemoveNode(node)    this.AddNode(node)}复制代码

因为 Get 比较简单，我们先完成 Get 方法。这里分两种情况考虑：

• 如果没有找到元素，我们返回-1。

• 如果元素存在，我们需要把这个元素移动到首位置上去。

func (this *LRUCache) Get(key int) int {    cache := this.m    if v, exist := cache[key]; exist {        this.MoveToHead(v)        return v.val    } else {        return -1    }}复制代码

现在我们开始完成 Put。实现 Put 时，有两种情况需要考虑。

• 假若元素存在，其实相当于做一个 Get 操作，也是移动到最前面（但是需要注意的是，这里多了一个更新值的步骤）。

• 假若元素不存在，我们将其插入到元素首，并把该元素值放入到 map 中。如果恰好此时 Cache 中元素满了，需要删掉最后的元素。

处理完毕，附上 Put 函数完整代码。

func (this *LRUCache) Put(key int, value int) {    tail := this.tail    cache := this.m    if v, exist := cache[key]; exist {        v.val = value        this.MoveToHead(v)    } else {        v := &LinkNode{key, value, nil, nil}        if len(cache) == this.cap {            delete(cache, tail.pre.key)            this.RemoveNode(tail.pre)        }        this.AddNode(v)        cache[key] = v    }}复制代码

至此，我们就完成了一个 LRU 算法，附上完整的代码：

type LinkNode struct {    key, val  int    pre, next *LinkNode}
type LRUCache struct {    m          map[int]*LinkNode    cap        int    head, tail *LinkNode}
func Constructor(capacity int) LRUCache {    head := &LinkNode{0, 0, nil, nil}    tail := &LinkNode{0, 0, nil, nil}    head.next = tail    tail.pre = head    return LRUCache{make(map[int]*LinkNode), capacity, head, tail}}
func (this *LRUCache) Get(key int) int {    cache := this.m    if v, exist := cache[key]; exist {        this.MoveToHead(v)        return v.val    } else {        return -1    }}
func (this *LRUCache) RemoveNode(node *LinkNode) {    node.pre.next = node.next    node.next.pre = node.pre}
func (this *LRUCache) AddNode(node *LinkNode) {    head := this.head    node.next = head.next    head.next.pre = node    node.pre = head    head.next = node}
func (this *LRUCache) MoveToHead(node *LinkNode) {    this.RemoveNode(node)    this.AddNode(node)}
func (this *LRUCache) Put(key int, value int) {    tail := this.tail    cache := this.m    if v, exist := cache[key]; exist {        v.val = value        this.MoveToHead(v)    } else {        v := &LinkNode{key, value, nil, nil}        if len(cache) == this.cap {            delete(cache, tail.pre.key)            this.RemoveNode(tail.pre)        }        this.AddNode(v)        cache[key] = v    }}复制代码

2.1.2 Mysql 缓冲池 LRU 算法

在使用 Mysql 的业务场景中，如果使用上述我们描述的 LRU 算法来淘汰策略，会有一个问题。例如执行下面一条查询语句：

select * from table_a;复制代码

如果 table_a 中有大量数据并且读取之后不会继续使用,则 LRU 头部会被大量的 table_a 中的数据占据,这样会造成热点数据被逐出缓存从而导致大量的磁盘 IO。所以 Mysql 缓冲池采用 the least recently used（LRU）算法的变体，将缓冲池作为列表进行管理。

Mysql 的缓冲池

缓冲池（Buffer Pool）是主缓存器的一个区域，用于缓存索引、行的数据、自适应哈希索引、插入缓存（Insert Buffer）、锁 还有其他的内部数据结构。Buffer Pool 的大小是可以根据我们实际的需求进行更改，那么 Buffer Pool 的 size 取多少比较合适?MySQL 官网上是这么介绍，在专用服务器上（也就是服务器只承载一个 MySQL 实例），会将 80%的物理内存给到 Buffer Pool。Buffer Pool 允许直接从内存中读常用数据去处理，会加快很多的速度。为了提高大容量读取操作的效率，Buffer Pool 被分成可以容纳多行的页面。为了提高缓存管理的效率，Buffer Pool 被实现为页面对应的链接的列表（a linked list of pages）。

Mysql 数据库 Buffer Pool 结构：

当需要空间将新页面缓存到缓冲池的时候，最近最少使用的页面将被释放出去，并将新的页面加入列表的中间。这个中间点插入的策略将列表分为两个子列表：

• 头部是存放最近访问过的新页面的子列表

• 尾部是存放那些最近访问较少的旧页面的子列表

该算法将保留 new sublist（也就是结构图中头部）中大量被查询使用的页面。而 old sublist 里面较少被使用的页面作为被释放的候选项。

理解以下几个关键点是比较重要的：

• 3/8 的缓冲池专用于 old sublist（也就是 3/8 来保存旧的页面，其余部分用来存储热数据，存储热数据的部分相对大一些，当然这个值可以自己去调整，通过 innodb_old_blocks_pct，其默认值是 37，也就是 3/8*100，上限 100，可调整 5-95，可以改小一些，但是调整后尽量保证这个比例内的数据也就是 old sublist 中的数据只会被读取一次，若不是了解非常业务数据负载建议不要去修改。）

• 列表的中点是新子列表的尾部与旧子列表的头部相交的边界。

• 当 InnoDB 将页面读入缓冲池时，它最初将其插入中点（旧子列表的头部）。一个页面会被读取是因为它是用户指定的操作（如 SQL 查询）所需，或者是由 InnoDB 自动执行的预读操作的一部分 。

• 访问旧子列表中的页面使其 “ 年轻 ”，将其移动到缓冲池的头部（新子列表的头部）。如果页面是被需要比如（SQL）读取的，它会马上访问旧列表并将页面推入新列表头部。如果预读需要读取的页面，则不会发生对旧列表的 first access。

• 随着数据库的运行，在缓冲池的页面没有被访问则向列表的尾部移动。新旧子列表中的页面随着其他页面的变化而变旧。旧子列表中的页面也会随着页面插入中点而老化。最终，仍未使用的页面到达旧子列表的尾部并被释放。默认情况下，页面被查询读取将被立即移入新列表中，在 Buffer Pool 中存在更长的时间。

通过对 LRU 算法的改进，InnoDB 引擎解决了查询数据量大时，热点数据被逐出缓存从而导致大量的磁盘 IO 的问题。

2.1.3 Redis 近似 LRU 实现

由于真实 LRU 需要过多的内存（在数据量比较大时）；并且 Redis 以高性能著称，真实的 LRU 需要每次访问数据时都做相关的调整，势必会影响 Redis 的性能发挥；这些都是 Redis 开发者所不能接受的，所以 Redis 使用一种随机抽样的方式，来实现一个近似 LRU 的效果。

在 Redis 中有一个参数，叫做 “maxmemory-samples”，是干嘛用的呢？

 1 # LRU and minimal TTL algorithms are not precise algorithms but approximated  2 # algorithms (in order to save memory), so you can tune it for speed or  3 # accuracy. For default Redis will check five keys and pick the one that was  4 # used less recently, you can change the sample size using the following  5 # configuration directive.  6 #  7 # The default of 5 produces good enough results. 10 Approximates very closely  8 # true LRU but costs a bit more CPU. 3 is very fast but not very accurate.  9 # 10 maxmemory-samples 5复制代码

上面我们说过了，近似 LRU 是用随机抽样的方式来实现一个近似的 LRU 效果。这个参数其实就是作者提供了一种方式，可以让我们人为干预样本数大小，将其设的越大，就越接近真实 LRU 的效果，当然也就意味着越耗内存。（初始值为 5 是作者默认的最佳）

左上图为理想中的 LRU 算法,新增加的 key 和最近被访问的 key 都不应该被逐出。可以看到,Redis2.8 当每次随机采样 5 个 key 时，新增加的 key 和最近访问的 key 都有一定概率被逐出；Redis3.0 增加了 pool 后效果好一些(右下角的图)。当 Redis3.0 增加了 pool 并且将采样 key 增加到 10 个后，基本等同于理想中的 LRU(虽然还是有一点差距)。

Redis 中对 LRU 代码实现也比较简单。Redis 维护了一个 24 位时钟，可以简单理解为当前系统的时间戳，每隔一定时间会更新这个时钟。每个 key 对象内部同样维护了一个 24 位的时钟，当新增 key 对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行 LRU，那么首先拿到当前的全局时钟，然后再找到内部时钟与全局时钟距离时间最久的（差最大）进行淘汰，这里值得注意的是全局时钟只有 24 位，按秒为单位来表示才能存储 194 天，所以可能会出现 key 的时钟大于全局时钟的情况，如果这种情况出现那么就两个相加而不是相减来求最久的 key。

struct redisServer {       pid_t pid;        char *configfile;        //全局时钟       unsigned lruclock:LRU_BITS;        ...};复制代码

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    /* key对象内部时钟 */    unsigned lru:LRU_BITS;    int refcount;    void *ptr;} robj;复制代码

总结一下：Redis 中的 LRU 与常规的 LRU 实现并不相同，常规 LRU 会准确的淘汰掉队头的元素，但是 Redis 的 LRU 并不维护队列，只是根据配置的策略要么从所有的 key 中随机选择 N 个（N 可以配置）,要么从所有的设置了过期时间的 key 中选出 N 个键，然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。

2.2 Least Frequently Used(LFU)

LFU（Least Frequently Used）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。LFU 的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。LFU 需要记录所有数据的访问记录，内存消耗较高；需要基于引用计数排序，性能消耗较高。在算法实现复杂度上，LFU 要远大于 LRU。

2.2.1 LFU 缓存淘汰算法实现

本节笔者以 leetcode 上的一道算法题为例，使用代码实现 LFU 算法，帮助读者更深入的理解 LFU 算法的思想。

leetcode 460: LFU 缓存

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 示例： LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到 key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4 复制代码

上一节我们聊到 LRU 算法，LRU 的实现是一个哈希表加上一个双链表，比较简单。而 LFU 则要复杂多了，需要用两个哈希表再加上 N 个双链表才能实现 我们先看看 LFU 的两个哈希表里面都存了什么。

第一个哈希表是 key-value 的哈希表(以下简称 kv 哈希表)

这里的 key 就是输入的 key，没什么特别的。关键是 value，它的 value 不是一个简单的 value，而是一个节点对象。 节点对象 Node 包含了 key，value，以及频率，这个 Node 又会出现在第二个哈希表的 value 中。 至于为什么 Node 中又重复包含了 key，因为某些情况下我们不是通过 k-v 哈希表拿到 Node 的，而是通过其他方式获得了 Node，之后需要用 Node 中的 key 去 k-v 哈希表中做一些操作，所以 Node 中包含了一些冗余信息。

第二张哈希表，频率哈希表，这个就要复杂多了

这张哈希表中的 key 是频率，也就是元素被访问的频率(被访问了 1 次，被访问了两次等等)，它的 value 是一个双向链表 刚才说的 Node 对象，现在又出现了，这里的 Node 其实是双向链表中的一个节点。 第一张图中我们介绍了 Node 中包含了一个冗余的 key，其实它还包含了一个冗余的频率值，因为某些情况下，我们需要通过 Node 中的频率值，去频率哈希表中做查找，所以也需要一个冗余的频率值。

下面我们将两个哈希表整合起来看看完整的结构:

k-v 哈希表中 key1 指向一个 Node，这个 Node 的频率为 1，位于频率哈希表中 key=1 下面的双链表中(处于第一个节点)。

根据上边的描述就可以定义出我们要使用到的数据结构和双链表的基本操作代码(使用 Go 语言)：

type LFUCache struct {    cache               map[int]*Node	freq                map[int]*DoubleList	ncap, size, minFreq int}
//节点nodetype Node struct {	key, val, freq int	prev, next     *Node}
//双链表type DoubleList struct {	tail, head *Node}
//创建一个双链表func createDL() *DoubleList {	head, tail := &Node{}, &Node{}	head.next, tail.prev = tail, head
	return &DoubleList{		tail: tail,		head: head,	}}
func (this *DoubleList) IsEmpty() bool {	return this.head.next == this.tail}
//将node添加为双链表的第一个元素func (this *DoubleList) AddFirst(node *Node) {	node.next = this.head.next	node.prev = this.head
	this.head.next.prev = node	this.head.next = node}
func (this *DoubleList) RemoveNode(node *Node) {	node.next.prev = node.prev	node.prev.next = node.next
	node.next = nil	node.prev = nil}
func (this *DoubleList) RemoveLast() *Node {	if this.IsEmpty() {		return nil	}
	lastNode := this.tail.prev	this.RemoveNode(lastNode)
	return lastNode}复制代码

下边我们来看一下 LFU 算法的具体的实现吧，get 操作相对简单一些，我们就先说 get 操作吧。 get 操作的具体逻辑大致是这样：

• 如果 key 不存在则返回-1

• 如果 key 存在，则返回对应的 value，同时:将元素的访问频率+1 将元素从访问频率 i 的链表中移除，放到频率 i+1 的链表中如果频率 i 的链表为空，则从频率哈希表中移除这个链表

第一个很简单就不用说了，我们看下第二点的执行过程：

假设某个元素的访问频率是 3，现在又被访问了一次，那么就需要将这个元素移动到频率 4 的链表中。如果这个元素被移除后，频率 3 的那个链表变成空了(只剩下头结点和尾节点)就需要删除这个链表，同时删除对应的频率(也就是删除 key=3),我们看下执行过程：

LFU 中 Get 方法代码实现：

func (this *LFUCache) Get(key int) int {    if node, ok := this.cache[key]; ok {		this.IncrFreq(node)		return node.val	}
	return -1}
func(this *LFUCache) IncrFreq(node *Node) {	_freq := node.freq	this.freq[_freq].RemoveNode(node)	if this.minFreq == _freq && this.freq[_freq].IsEmpty() {		this.minFreq++		delete(this.freq, _freq)	}	node.freq++
	if this.freq[node.freq] == nil {		this.freq[node.freq] = createDL()	}	this.freq[node.freq].AddFirst(node)}复制代码

put 操作就要复杂多了，大致包括下面几种情况

• 如果 key 已经存在，修改对应的 value，并将访问频率+1 将元素从访问频率 i 的链表中移除，放到频率 i+1 的链表中如果频率 i 的链表为空，则从频率哈希表中移除这个链表

• 如果 key 不存在缓存超过最大容量，则先删除访问频率最低的元素，再插入新元素新元素的访问频率为 1，如果频率哈希表中不存在对应的链表需要创建缓存没有超过最大容量，则插入新元素新元素的访问频率为 1，如果频率哈希表中不存在对应的链表需要创建

我们在代码实现中还需要维护一个 minFreq 的变量，用来记录 LFU 缓存中频率最小的元素，在缓存满的时候，可以快速定位到最小频繁的链表，以达到 O(1) 时间复杂度删除一个元素。 具体做法是:

• 更新/查找的时候，将元素频率+1，之后如果 minFreq 不在频率哈希表中了，说明频率哈希表中已经没有元素了，那么 minFreq 需要+1，否则 minFreq 不变。

• 插入的时候，这个简单，因为新元素的频率都是 1，所以只需要将 minFreq 改为 1 即可。

我们重点看下缓存超过最大容量时是怎么处理的:

LFU 中 Put 方法代码实现：

func (this *LFUCache) Put(key int, value int)  {    if this.ncap == 0 {		return	}	//节点存在    if node, ok := this.cache[key]; ok {		node.val = value		this.IncrFreq(node)	} else {		if this.size >= this.ncap {			node := this.freq[this.minFreq].RemoveLast()			delete(this.cache, node.key)			this.size--		}		x := &Node{key: key, val: value, freq: 1}		this.cache[key] = x		if this.freq[1] == nil {			this.freq[1] = createDL()		}		this.freq[1].AddFirst(x)		this.minFreq = 1		this.size++	}}复制代码

通过对一道 LFU 基本算法的分析与实现，相信读者已经领悟到了 LFU 算法的思想及其复杂性。很多算法本身就是复杂的，不但要整合各种数据结构，还要根据应用场景进行分析，并不断改进。但是算法确确实实的解决很多实际的问题，我们已经知道了缓存的重要性，但一个好的缓存策略除了要充分利用各种计算机存储组件，良好的算法设计也是必不可少的。所以我们再来总体回顾一下本节 LFU 算法的实现吧：

type LFUCache struct {    cache               map[int]*Node	freq                map[int]*DoubleList	ncap, size, minFreq int}
func(this *LFUCache) IncrFreq(node *Node) {	_freq := node.freq	this.freq[_freq].RemoveNode(node)	if this.minFreq == _freq && this.freq[_freq].IsEmpty() {		this.minFreq++		delete(this.freq, _freq)	}	node.freq++
	if this.freq[node.freq] == nil {		this.freq[node.freq] = createDL()	}	this.freq[node.freq].AddFirst(node)}

func Constructor(capacity int) LFUCache {    return LFUCache{		cache: make(map[int]*Node),		freq:  make(map[int]*DoubleList),		ncap:  capacity,	}}

func (this *LFUCache) Get(key int) int {    if node, ok := this.cache[key]; ok {		this.IncrFreq(node)		return node.val	}
	return -1}

func (this *LFUCache) Put(key int, value int)  {    if this.ncap == 0 {		return	}	//节点存在    if node, ok := this.cache[key]; ok {		node.val = value		this.IncrFreq(node)	} else {		if this.size >= this.ncap {			node := this.freq[this.minFreq].RemoveLast()			delete(this.cache, node.key)			this.size--		}		x := &Node{key: key, val: value, freq: 1}		this.cache[key] = x		if this.freq[1] == nil {			this.freq[1] = createDL()		}		this.freq[1].AddFirst(x)		this.minFreq = 1		this.size++	}}
//节点nodetype Node struct {	key, val, freq int	prev, next     *Node}
//双链表type DoubleList struct {	tail, head *Node}
//创建一个双链表func createDL() *DoubleList {	head, tail := &Node{}, &Node{}	head.next, tail.prev = tail, head
	return &DoubleList{		tail: tail,		head: head,	}}
func (this *DoubleList) IsEmpty() bool {	return this.head.next == this.tail}
//将node添加为双链表的第一个元素func (this *DoubleList) AddFirst(node *Node) {	node.next = this.head.next	node.prev = this.head
	this.head.next.prev = node	this.head.next = node}
func (this *DoubleList) RemoveNode(node *Node) {	node.next.prev = node.prev	node.prev.next = node.next
	node.next = nil	node.prev = nil}
func (this *DoubleList) RemoveLast() *Node {	if this.IsEmpty() {		return nil	}
	lastNode := this.tail.prev	this.RemoveNode(lastNode)
	return lastNode}复制代码

2.2.2 Redis LFU 淘汰策略

一般情况下，LFU 效率要优于 LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题，在如下情况下：

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|复制代码

会将数据 D 误认为将来最有可能被访问到的数据。

Redis 作者曾想改进 LRU 算法，但发现 Redis 的 LRU 算法受制于随机采样数 maxmemory_samples，在 maxmemory_samples 等于 10 的情况下已经很接近于理想的 LRU 算法性能，也就是说，LRU 算法本身已经很难再进一步了。

于是，将思路回到原点，淘汰算法的本意是保留那些将来最有可能被再次访问的数据，而 LRU 算法只是预测最近被访问的数据将来最有可能被访问到。我们可以转变思路，采用 LFU(Least Frequently Used)算法，也就是最频繁被访问的数据将来最有可能被访问到。在上面的情况中，根据访问频繁情况，可以确定保留优先级：B>A>C=D。

在 LFU 算法中，可以为每个 key 维护一个计数器。每次 key 被访问的时候，计数器增大。计数器越大，可以约等于访问越频繁。

上述简单算法存在两个问题：

• 在 LRU 算法中可以维护一个双向链表，然后简单的把被访问的节点移至链表开头，但在 LFU 中是不可行的，节点要严格按照计数器进行排序，新增节点或者更新节点位置时，时间复杂度可能达到 O(N)。

• 只是简单的增加计数器的方法并不完美。访问模式是会频繁变化的，一段时间内频繁访问的 key 一段时间之后可能会很少被访问到，只增加计数器并不能体现这种趋势。 第一个问题很好解决，可以借鉴 LRU 实现的经验，维护一个待淘汰 key 的 pool。第二个问题的解决办法是，记录 key 最后一个被访问的时间，然后随着时间推移，降低计数器。

我们前边说过 Redis 对象的结构：

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or                            * LFU data (least significant 8 bits frequency                            * and most significant 16 bits access time). */    int refcount;    void *ptr;} robj;复制代码

在 LRU 算法中，24 bits 的 lru 是用来记录 LRU time 的，在 LFU 中也可以使用这个字段，不过是分成 16 bits 与 8 bits 使用：

       16 bits      8 bits      +----------------+--------+      + Last decr time | LOG_C  |      +----------------+--------+复制代码

高 16 bits 用来记录最近一次计数器降低的时间 ldt，单位是分钟，低 8 bits 记录计数器数值 counter。

Redis4.0 之后为 maxmemory_policy 淘汰策略添加了两个 LFU 模式：

• volatile-lfu：对有过期时间的 key 采用 LFU 淘汰算法

• allkeys-lfu：对全部 key 采用 LFU 淘汰算法

还有 2 个配置可以调整 LFU 算法：

lfu-log-factor 10lfu-decay-time 1复制代码

• lfu-log-factor 可以调整计数器 counter 的增长速度，lfu-log-factor 越大，counter 增长的越慢。

• lfu-decay-time 是一个以分钟为单位的数值，可以调整 counter 的减少速度

源码实现

在 lookupKey 中：

robj *lookupKey(redisDb *db, robj *key, int flags) {    dictEntry *de = dictFind(db->dict,key->ptr);    if (de) {        robj *val = dictGetVal(de);
        /* Update the access time for the ageing algorithm.         * Don't do it if we have a saving child, as this will trigger         * a copy on write madness. */        if (server.rdb_child_pid == -1 &&            server.aof_child_pid == -1 &&            !(flags & LOOKUP_NOTOUCH))        {            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {                updateLFU(val);            } else {                val->lru = LRU_CLOCK();            }        }        return val;    } else {        return NULL;    }}复制代码

当采用 LFU 策略时，updateLFU 更新 lru：

/* Update LFU when an object is accessed. * Firstly, decrement the counter if the decrement time is reached. * Then logarithmically increment the counter, and update the access time. */void updateLFU(robj *val) {    unsigned long counter = LFUDecrAndReturn(val);    counter = LFULogIncr(counter);    val->lru = (LFUGetTimeInMinutes()<<8) | counter;}复制代码

降低 LFUDecrAndReturn

首先，LFUDecrAndReturn 对 counter 进行减少操作：

/* If the object decrement time is reached decrement the LFU counter but * do not update LFU fields of the object, we update the access time * and counter in an explicit way when the object is really accessed. * And we will times halve the counter according to the times of * elapsed time than server.lfu_decay_time. * Return the object frequency counter. * * This function is used in order to scan the dataset for the best object * to fit: as we check for the candidate, we incrementally decrement the * counter of the scanned objects if needed. */unsigned long LFUDecrAndReturn(robj *o) {    unsigned long ldt = o->lru >> 8;    unsigned long counter = o->lru & 255;    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;    if (num_periods)        counter = (num_periods > counter) ? 0 : counter - num_periods;    return counter;}复制代码

函数首先取得高 16 bits 的最近降低时间 ldt 与低 8 bits 的计数器 counter，然后根据配置的 lfu_decay_time 计算应该降低多少。

LFUTimeElapsed 用来计算当前时间与 ldt 的差值：

/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) for the LFU implementation. */unsigned long LFUGetTimeInMinutes(void) {    return (server.unixtime/60) & 65535;}
/* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */unsigned long LFUTimeElapsed(unsigned long ldt) {    unsigned long now = LFUGetTimeInMinutes();    if (now >= ldt) return now-ldt;    return 65535-ldt+now;}复制代码

具体是当前时间转化成分钟数后取低 16 bits，然后计算与 ldt 的差值 now-ldt。当 ldt > now 时，默认为过了一个周期(16 bits，最大 65535)，取值 65535-ldt+now。

然后用差值与配置 lfu_decay_time 相除，LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去 n 个 lfu_decay_time，则将 counter 减少 n，counter - num_periods。

增长 LFULogIncr

增长函数 LFULogIncr 如下：

/* Logarithmically increment a counter. The greater is the current counter value * the less likely is that it gets really implemented. Saturate it at 255. */uint8_t LFULogIncr(uint8_t counter) {    if (counter == 255) return 255;    double r = (double)rand()/RAND_MAX;    double baseval = counter - LFU_INIT_VAL;    if (baseval < 0) baseval = 0;    double p = 1.0/(baseval*server.lfu_log_factor+1);    if (r < p) counter++;    return counter;}复制代码

counter 并不是简单的访问一次就+1，而是采用了一个 0-1 之间的 p 因子控制增长。counter 最大值为 255。取一个 0-1 之间的随机数 r 与 p 比较，当 r<p 时，才增加 counter，这和比特币中控制产出的策略类似。p 取决于当前 counter 值与 lfu_log_factor 因子，counter 值与 lfu_log_factor 因子越大，p 越小，r<p 的概率也越小，counter 增长的概率也就越小。增长情况如下：

# +--------+------------+------------+------------+------------+------------+# | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |# +--------+------------+------------+------------+------------+------------+# | 0      | 104        | 255        | 255        | 255        | 255        |# +--------+------------+------------+------------+------------+------------+# | 1      | 18         | 49         | 255        | 255        | 255        |# +--------+------------+------------+------------+------------+------------+# | 10     | 10         | 18         | 142        | 255        | 255        |# +--------+------------+------------+------------+------------+------------+# | 100    | 8          | 11         | 49         | 143        | 255        |# +--------+------------+------------+------------+------------+------------+复制代码

可见 counter 增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter 增长的越来越慢。

新生 key 策略

另外一个问题是，当创建新对象的时候，对象的 counter 如果为 0，很容易就会被淘汰掉，还需要为新生 key 设置一个初始 counter，createObject:

robj *createObject(int type, void *ptr) {    robj *o = zmalloc(sizeof(*o));    o->type = type;    o->encoding = OBJ_ENCODING_RAW;    o->ptr = ptr;    o->refcount = 1;
    /* Set the LRU to the current lruclock (minutes resolution), or     * alternatively the LFU counter. */    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;    } else {        o->lru = LRU_CLOCK();    }    return o;}复制代码

counter 会被初始化为 LFU_INIT_VAL，默认 5。

总结一下：Redis 的 LFU 缓存淘汰策略复用了 redis 对象中的 24 bits lru, 不过分成了分成 16 bits 与 8 bits 使用，高 16 bits 用来记录最近一次计数器降低的时间 ldt，单位是分钟，低 8 bits 记录计数器数值 counter。Redis 对象的计数器并不是线性增长的，而是提供了 lfu-log-factor 配置项来控制技术器的增长速度。为了解决历史数据影响将来数据的“缓存污染”问题，Redis 对象的计数会根据 lfu_decay_time 配置项随时间做调整。redis 为每一个新增的 key 都设置了初始 counter，目的是防止新增的 key 很容易就被淘汰掉。

2.3 先进先出算法（FIFO）

FIFO（First in First out），先进先出。在 FIFO Cache 设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。实现方法很简单，只要使用队列数据结构即可实现。

因为缓存命中率比较低，FIFO 缓存策略通常不会在项目中使用。客观唯心主义的理论：存在即合理，下边笔者就描述一下 FIFO 队列在 Redis 主从复制过程中的应用。

在 Redis 主从结构中，主节点要将数据同步给从节点，从一开始主从建立连接到数据同步一共分为三个阶段：

第一阶段首先建立连接，然后第二阶段主节点发送 rdb 文件给从节点同步全量数据；我们主要看第三阶段主节点反复同步增量数据给从节点的过程是什么样的。

从节点和主节点建立连接时，主节点服务器会维护一个复制积压缓冲区来暂存增量的同步命令；当从节点向主节点要求同步数据时，主节点根据从节点同步数据的 offset 将数据增量的同步给从节点，反复进行。

复制积压缓冲区是一个先进先出(FIFO)的环形队列，用于存储服务端执行过的命令，每次传播命令，master 节点都会将传播的命令记录下来，保存在这里。

复制积压缓冲区由两部分组成：偏移量和字节值。字节值是 redis 指令字节的存储（redis 指令以一种 Redis 序列化文本协议的格式存储），偏移量 offset 就是当前字节值在环形队列中的偏移量。

主节点维护了每个从节点的 offset，这样每次同步数据时，主节点就知道该同步哪一部分数据给从节点了。通过这样一个复制积压缓冲区，Redis 的主从架构实现了数据的增量同步，想要了解更多主从同步细节的读者可以参考我的另一篇博客：Redis 高可用——主从复制

2.4 FIFO、LRU、LFU 缓存淘汰策略对比

本节花费了大量篇幅介绍缓存淘汰策略，我们再来从缓存命中率、实现复杂度、存储成本、缺陷这四个方面来对这三种缓存策略做一个对比：

Redis、Mysql 的缓存设计都考虑了本节讲到的缓存淘汰策略的思想，并结合自身的业务场景进行了改进实现。缓存淘汰策略没有十全十美的，根据具体的业务和需求选择合适缓存淘汰算法，提升缓存命中率是我们学习本节的目的。

3. 缓存安全

缓存安全是非常热点的话题，大多数企业在的架构师在设计缓存系统时都会考虑“缓存安全”相关的问题，尤其是当服务到达一定量级之后，“缓存安全”就是一个不得不考虑的问题了。另外在面试过程中，“缓存安全”相关的问题也是热点，因为懂得这些太重要了，每一个问题产生的原因可能是什么？有效的解决方案有哪些？怎样避免这些问题的产生？这些都是一个合格的程序员应该知道的。

本节就结合 redis 缓存中间件的使用，和大家一块谈谈“缓存安全”中最常见的问题。并介绍相关的解决方案和规避方法。

3.1 缓存预热

俗话说万事开头难，对于应用了 redis 缓存中间件的系统来说也会存在这样的问题。当系统并发很高，并采用了主从架构的时候，服务启动就是一件很困难的事情！究其原因，系统刚启动时，缓存中没有数据，那么服务启动就需要大量的访问数据库，并瞬间产生大量的缓存数据，主从之间吞吐量增大，数据同步频度增加，可能服务刚启动不久就会宕机。

解决方案也很简单，我们最好先统计出访问频度比较高的热点数据，根据统计结果将数据分类，让 redis 缓存服务优先加载那些访问频度高的热点数据。当然了，这个过程最好做成“预加载”，在服务启动之前先加载了热点数据，手工执行方案难以实现时，可以借助脚本或者 CDN 的方式进行。

总结来讲：缓存预热就是系统启动前，提前将相关的缓存数据直接加载到缓存系统。避免用户请求的时候，先查询数据库，然后再将数据缓存的问题，让用户直接查询被预热的缓存数据。

3.2 缓存雪崩

缓存雪崩是缓存服务中经常遇见的问题，下边是一个缓存雪崩事故发生的大致过程：

• 系统平稳运行中，忽然数据库连接量激增

• 应用服务器无法及时处理请求，客户端开始大量出现 408、500 错误页面

• 客户反复刷新页面尝试获取数据，导致服务端数据库访问激增，数据库崩溃

• 数据库崩溃以后，应用服务器也就随之崩溃了

• 尝试重启服务器无效，这时候 redis 服务器崩溃，雪崩开始出现，redis 集群开始崩溃

• 重启数据库无效，因为流量太高，数据库启动即崩溃

排查上述缓存雪崩问题出现的原因，我们就会得到这样一个结论：

产生“缓存雪崩”的根本原因是：在一个较短的时间内，缓存中较多的 key 集中过期了。

我们可以使用这个结论来解释一下上述现象发生的过程。缓存中大量的 key 同时过期以后，redis 缓存无法命中，请求就会到达数据库；如果并发量很大，数据库根本无法及时处理，Redis 的请求就会被积压，并逐渐出现超时现象；数据库随着流量的激增崩溃了，这个时候重启服务器是没有意义的，因为系统的关键问题是缓存中无可用数据，Redis 的服务器资源被占用，服务器也随着崩溃，集群崩塌，应用服务器也会随着客户端的请求增加而崩溃。出现了这个局面以后，我们重启服务器、redis 和数据库都是没有意义的！下面缓存雪崩的简单示意图：

如果“缓存雪崩”问题已经发生了，应该怎样解决呢？下边列举一些有效的方案：

• 页面静态化处理，一旦使用了页面静态化，客户端的数据就不用从缓存中获取了，这样可以减轻缓存的压力，缺点是数据更新不及时。

• 构建多级缓存，构建多级缓存可以给每一级的缓存提供更多的数据保障，比如在 redis 和 mysql 数据库中间再加上一层 ehcache 缓存，当缓存中大量 key 过期时，ehcache 缓存可以替 mysql 数据库暂时抵挡一部分流量。构建多级缓存会增加系统的复杂性。

• 优化 mysql。比如给 mysql 增加 buffer pool,这样当大量流量到达 mysql 时，mysql 的吞吐量可以支撑并发，不至于马上崩溃，也能防止雪崩现象发生。

• 监控 redis 的性能指标。根据分析我们知道，“雪崩”伴随着的肯定 CPU 占用率急剧上升，同时客户端请求的平均响应时间也会增大，对这些性能指标进行监控能帮助我们更早的发现问题。

• 限流、降级。这是从客户端的角度来考虑，牺牲一部分客户体验，限制一些客户端请求，能有效的降低应用服务器的压力。待系统平稳运行后再逐渐恢复。

既然我们知道了“缓存雪崩”产生的原因是一个较短的时间内，大量的热点 key 集中过期导致的，我们有必要学习一些方法来预防“缓存雪崩”的发生。最有效的方法就是根据业务数据将缓存的有效期错峰，数据的过期时间采用固定时间 + 随机时间戳的方式，稀释集中到期 key 的数量，甚至说超热的数据，采用永久 key 也是可以的。还记得我们第二部分提到的缓存淘汰策略吗？将 LRU 切换为 LFU 淘汰策略，也是可以有效预防“缓存雪崩”的。如果你认为问题还是不太好解决，想要采用手动维护的方式也是可以的，可以定期对访问数据做统计，给热点数据续租过期时间也是可以的。

总结来讲：缓存雪崩就是瞬间过期数据量太大，给数据库服务器造成压力。如果能够有效避免过期时间集中，就可以有效防止雪崩问题的出现，再配合其它策略的一起使用，并监控服务器的运行数据并做及时的调整，基本是可以防止“缓存雪崩”情况发生的。

3.3 缓存击穿

了解了缓存雪崩之后，我们不妨思考这样一个问题：造成缓存雪崩的原因是大量的热点 key 在集中过期，假如一个超热的 key 过期，会不会也造成这种问题呢？

答案是肯定的！我们试想这样的场景，双 11 秒杀活动一台 mac 电脑 99 元，秒杀活动一开始，几百万的 QPS 上来了，缓存数据过期了，这么大的访问量达到了数据库，数据库肯定挂了！这就是我们本节要讲的“缓存击穿”。

对比“缓存雪崩”我们会发现，“缓存击穿”和“缓存雪崩”在很多现象上来说是比较相似的，而且我们上节说到的解决“缓存雪崩”的方案拿到这里，大都是能够适用的。和“缓存雪崩”不同的是，“缓存击穿”发生后，redis 的内存和 CPU 并不会有异常，也不会造成应用服务器的崩溃，也就是说“缓存击穿”不太容易发生，造成的后果也没有“缓存雪崩”严重。但是在“秒杀”场景下确确实实会存在这样的问题。

我们还是先来说一下如何解决和预防“缓存击穿”的问题吧。一般来讲，“缓存击穿”的问题发生前都是可以预见的，比如“秒杀”活动开始前后，肯定会有大量的客户端请求，那么当系统中高热的缓存 key 过期后，手动的加载到 redis 肯定是可以的。再或者活动期间我们就使用永久的 key，并配置 LFU 的缓存淘汰策略，也是可以解决这个问题的。当然还有其它的一些解决方案，就比如作者之前曾分析过 12306 是怎样承受高并发流量的，其中使用了本地缓存配合 redis 缓存的多级缓存方式，这种方式对于解决缓存击穿也是有效的，只要本地缓存和 redis 中的缓存不要同时过期就行，大量的流量也不会压到数据库。

总结一下：缓存过期就是单个高热数据过期的瞬间，数据访问量较大，未命中 redis 后，流量到达了数据库。应对策略是以预防为主，配合监控及时调整就可以，主要是在设计缓存系统时要考虑到这个问题。

3.4 缓存穿透

本小节我们来讨论一下“缓存穿透”，首先“缓存穿透”和“缓存击穿”是不一样的，“缓存穿透”经常被黑客利用，目的是为了拖垮我们的服务器。

我们看一下发生“缓存穿透”是一种什么样的现象：系统平稳运行时，有了突发流量，Redis 缓存的命中率开始下降，内存并没有什么异常，但是 CPU 开始激增，数据库访问也开始激增，直到数据库崩溃。

追查问题发生的本质原因竟然是客户端访问的 key 在 Redis 缓存中不存在，并且数据库中也没有相关数据，基本上都是这样的 key，似乎有人故意而为之。遇到这种情况，开发者一定要提高警惕，很有可能是出现了黑客攻击！

查到问题以后，我们该如何解决呢？大部分人最先想到的就是既然黑客知道我们缓存中没有 key，那么就将 key 缓存到 Redis 中，value 是 NULL 就可以了。如果你这么想，只能说明你太年轻了，首先黑客不至于傻到使用相同的 key 做攻击，再者大量的无效 key 缓存到 redis 内存中，redis 就失去了缓存的意义了。当然，如果你发现这些请求都来自同一个 ip 或者客户端，可以临时的设置黑名单将攻击流量拒之门外，但是黑客一般都会采用 DDos（分布式拒绝服务攻击），这种方法往往是无效的。

面对这样一种困境，业内最常用的方案是使用“布隆过滤器”。虽然有一定的误判概率，但是只要参数设置的合理，确实能够有效地解决问题。

布隆过滤器是什么？

可以把布隆过滤器理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别的不精确，只要参数设置的合理，它的精确度是可以得到保障的。当布隆过滤器说某个值不存在时，这个值可能不存在；但是它只要说某个值不存在，这个值就肯定不存在。

布隆过滤器的实现原理

每个布隆过滤器对应到 Redis 的数据结构里边就是一个大型的位数组和几个不一样的无偏 hash 函数（能够把元素的 hash 值算的比较均匀，让函数被 hash 映射到位数组中的位置比较随机）。如果所示，f、g、h 就是这样的 hash 函数。

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash，先算得一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置，再把位数组的这几个位置都设置为 1。 向布隆过滤器中询问 key 是否存在时，跟添加一样，也会把 key 通过 hash 得到的几个位置都算出来，看看数组中这几个位置是否都为 1，只要有一个位置为 0，那么说明这个值在布隆过滤器中是不存在的。

除了布隆过滤器这种方案，笔者认为，对业务中的 key 进行加密也是很有必要的，因为只要业务中的 key 如果是有规律可循的，黑客一般是不会知道的，我们就可以通过 key 的判断将黑客的攻击流量抵挡到 redis 缓存服务器前边。此外缓存数据的监控一定要做好，能够及时地发现缓存命中率下降，就能够越早地采取措施。

总结一下：“缓存穿透”是客户端访问了缓存和数据库中都不存在的数据，大量的这种访问会击垮数据库，当运维人员监控到这种情况时，一定要及时给出报警信息，根据上边提到的措施进行有效处理。

3.5 性能指标监控

前边几个小节，我们在讨论各种缓存隐患时，反复的强调做好监控的重要性。这里笔者单独抽出一个小节来总结一下在平时的缓存系统业务场景中，我们应该监控哪些性能指标，有哪些命令能够帮助我们分析问题，这些措施和技能对于保证我们的系统安全是非常有用的。

对于性能指标监控，笔者这里列出五大类，分别以表格的形式呈现。

• 性能指标：Performance

• 内存指标：Memory

• 基本活动指标：Basic activity

• 错误指标：Error

以上所列举的都是服务中比较重要的指标，监控 redis 的这些指标有一些开源的工具，例如：Cloud Insight Redis、Prometheus、Redis-stat、Redis-faina。但是这些工具在我们比较定制化的业务中，往往不能起到太大效果，往往企业会针对自己的业务开发自己的监控服务。

Redis 提供了一些命令也能帮助我们排查问题。比如 showlog、monitor；此外 redis 还提供了 benchmark 指令，通过使用它我们可以得到 redis 的吞吐量、缓存命中率这些性能指标数据。

4.后记

这篇文章断断续续的整理了半个月，笔者参考了大量的资料才提炼出了以上内容。文章中很多地方确实不够深入，也有一些空洞的理论，加上笔者本身工作经验不是很丰富，关于 mysql、redis 和 php，很多底层的知识也没有研究到位，文章中难免有表达不恰当和错误之处，希望读者查找出以后一定在留言区进行指正。

回过头来看这篇文章，笔者在这里大谈“缓存”确实有点大言不惭，但是都是我的心血，也就当是我的一篇学习笔记了。

涉及到“缓存”相关的系统设计和应用绝不仅仅是我提到的这些，比如：缓存数据结构的选择和压缩、多级缓存之间的数据同步等等，这些都没有谈到，如果将来有机会，希望能深入的学习一下这些知识，再对文章做一些补充。

原文链接：https://juejin.cn/post/6844904136207499277

最后小编还给大家整理了一份面试文档，有需要的添加小助理 vx：mxzFAFAFA 来获取！！