Node.js 缓存之 LRU Cache 高效实现
网易新闻移动端站点部分页面是通过 Vue SSR 服务来渲染的，在得到同构、SEO、内容到达时间这些收益的同时，不得不面对 Vue SSR 服务带来的性能问题，Vue 创建组件实例和虚拟 DOM 节点的性能开销，是远远大于Handlebars 这种基于字符串拼接模板的。
在优化性能的过程中，与同事聊到用空间换时间来提升性能的时候，同事丢来一句: “性能不够，缓存来凑”，虽是一句调侃，却可以看出缓存是提升性能的利器。我们引入了 LRU Cache 对页面和页面组件做不同的缓存策略，改善服务负载能力，缩短响应时间，提升系统性能。本文会和大家一起学习高效 LRU Cache 背后的原理和技术实现，便于在相关场景更好地去应用。
1、缓存的作用
缓存一般用来暂存数据处理结果，为下次访问提供使用。很多时候，数据的处理、数据的获取非常费时，频繁的数据请求或处理会消耗大量资源，缓存就是将这些处理后的数据存储起来，当再次请求此数据时，直接从缓存中获取而不重新进行数据获取或处理，从而降低资源的消耗提高响应速度。
2、缓存的分类
缓存分本地缓存和分布式缓存。本地缓存是应用中的组件，与应用耦合，在应用同一个进程中请求非常快，适合无需进程相互通知的场景。分布式缓存是与应用分离的缓存服务，比如 redis，是一个独立的服务，与本地应用隔离，多个应用可以共享缓存。
3、缓存的删除规则
在使用缓存时通常是有存储空间的限制，不论是内存缓存、文件缓存或者是独立的缓存数据库，当存储达到上限的时候是需要删除一部分数据来存放新的数据，我们将依照什么规则来删除呢? 常见的删除规则算法有：FIFO(先进先出算法规则)、LRU(最近最久未使用算法规则)、LFU(最近最少使用算法规则)。
LRU 是我平常用的最多的一种，现在我们一起来了解 LRU 缓存算法规则背后精巧的技术实现。
LRU(Least Recently Used) 缓存算法实现思想是：假设一个数据在最近时间内未被访问，那么在将来被访问的可能性也更小，当数据达到上限时优先删除最近时间内未被访问的数据。
1、快速理解LRU删除算法规则
我们把 LRU 缓存想象成一个有头和尾的有序格子，新数据和最近被访问的数据的格子移动到格子末尾，而处于格子头部的在数据达到上限时将被删除，如下图所示:
' fill='%23FFFFFF'%3E%3Crect x='249' y='126' width='1' height='1'%3E%3C/rect%3E%3C/g%3E%3C/g%3E%3C/svg%3E)
为了加深对 LRU 缓存规则的理解，我们基于 JavaScript Map 对象来实现一个简单的 LRU 缓存：
class Cache {constructor(options = { max: 5 }) {this.max = options.max;this.cache = new Map();}set(key, value) {if (this.cache.has(key)) {this.cache.delete(key);}if (this.cache.size >= this.max) {this.cache.delete(this.cache.keys().next().value);}this.cache.set(key, value);}get(key) {if (this.cache.has(key)) {let val = this.cache.get(key);this.cache.delete(key);this.cache.set(key, val);return val;}return null;}}
没错，上面代码模拟出了 LRU 缓存。为什么用 JavaScript Map 对象就可以实现一个 LRU 缓存呢? 因为 Map 对象在保存键值对时，能记住键原始插入的顺序，让我们很容易找到最久未被访问(最早设置)的数据。
每次在设置和获取缓存时候都主动去改变当前 key 的插入顺序，这是关键。
this.cache.delete(key);this.cache.set(key, val);
当数据达到上限，我们找到最久未被使用(最早插入)的 key，删除它，并重新设置。
if (this.cache.size >= this.max) {this.cache.delete(this.cache.keys().next().value);}this.cache.set(key, value);
注： Map keys() 返回一个引用的迭代对象，它包含按照顺序插入 Map 对象中每个元素的 key 值。
基于刚实现的 LRU 缓存，我们来推测下面缓存 key 的 顺序：
const cache = new Cache({ max: 5 });cache.set('a', 0);cache.set('b', 1);cache.set('c', 2);cache.set('d', 3);cache.set('e', 4);cache.set('f', 5);cache.set('b', 6);
推测将得到的顺序如下图：
在浏览器控制台进行验证, 得到和推测的答案完全一致：
2、如何从零实现一个高效的 LRU 缓存
理解了 LRU 缓存算法规则，那如何来实现一个 高效的 LRU 缓存库呢? 我们将从三方面入手，首先定义基本要求，其次实现思路选择、原理剖析，最后代码实现。
2.1、基本要求
存储长度，一个可配置储存 key 特定长度的参数。
通用操作， 提供 get、set 方法，时间复杂度为 O(1)。
特殊操作， 空间达到上限后，删除最久未被访问的数据。
2.2、实现思路
时间戳方式，利用时间戳增加的规则，为每个缓存 的key 设置一个时间戳，每次访问都更新时间戳，当缓存达到上限时删除时间戳最小的缓存。在我们需要找最小的时间戳的时需要对所有缓存进行排序，时间复杂度O(n)。
链表方式，最新插入和最新读取的 key，都移动到链表尾部，达到上限从链表头部开始删数据，但是每次查询都需要遍历，时间复杂度为 O(n)。
哈希表 + 双链表 + 数组，通过哈希表来存储 key，解决快速查找时间复杂度问题。通过双链表来维护缓存的顺序，由于不必按顺序存储，链表在插入和删除的时候可以达到 O(1) 的复杂度，比线性表快得多，再结合数组通过下标查找速度快、随机访问性强的特点，实现一个时间复杂度为 O(1) 高效的 LRU 缓存。
哈希表 + 双链表 + 数组方式时间复杂度最低，我们来详细了解它的实现方式，对它做进一步拆解：
在哈希表中查找元素 key
如果 key 存在于哈希表中，它就存在于我们的缓存中
从哈希表中找到该对应元素的索引
将该元素移动到尾部
调整元素之间的前后指针
如果不在哈希表中
我们为这个元素创建一个新节点
将这个节点移动到尾部
将 key 和索引存放在哈希表中
调整新的指针关系
如果缓存空间不足
移除最近最少使用的元素节点，删除哈希表中的 key
调整元素之间的指针关系
以上拆解的过程中，缓存的在双链表中排序是最不容易理解部分，为了更好的去理解，将举例说明。在此之前我们先来看看什么是双链表。
链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。双链表是链表的另一种形式, 每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
如图：
理解了双链表数据结构，根据 LRU 缓存删除规则，对缓存在双链表里的排序举例来说明。
假如有一个长度为 5 的缓存空间，在双链表中会有下面几种场景。(每个场景都基于上一个场景的数据)
① 假设我依次设置了 5 个缓存内容，key 分别是： a，b，c，d，e。 因为没有超过缓存数据长度的上限，所以在缓存中的排序如下图：
② 当再设置一个 f 时，因为长度超过上限，a 是最早设置的，所以将 a 替换成 f，把 a 的下一个元素 b 设置为头，a 被替换成 f，f 是新的尾，如下图:
其实在双链表中它应该是：
③ 再获取 key 为 d 未过期的缓存(设置同理，同一个 key 都是最近访问)，这个时候对应的缓存顺序又该是什么呢?
获取缓存 key 为 d 的时候，将 缓存 key 为 d 的节点置为尾，并把 d 前后的节点 c、e 拼接起来，将原来尾节点 f 置为现在尾节点 d 的上一个节点。是不是有点绕，我们看看下图通过位置移动后的顺序，更好的来理解他们的前后关系。
④ 获取 key 为 f 的缓存，但是 key 为 f 的缓存过期了，在获取的那一刻将 f 置为空，同时拼接节点 f 前后的节点 e 和 d，如图所示：
⑤ 设置一个新的缓存 g，顺序又将是什么样的? g 将填充原来空闲出来的位置。如下图所示：
根据上面缓存在双链表里排序的例子我们发现，缓存的长度不变，位置不变，变的是头和尾标示、以及元素之间的指针关系。
我们来一起实现一个 LRU 缓存：
创建必要方法和属性
创建长度为 5 的 4 个数组列表，分别用来存储缓存 key、缓存内容、双链表 prev 指针、双链表 next 指针，一个空数组来存放过期的空闲位置
创建一个 keyMap 对象，用来存放缓存 key，和 key 对应的索引
创建两个指针，一个头，一个尾，用来标示双链表的头和尾
创建两个计数器，一个记录数据长度，一个记录填充长度
创建 set(key，value，ttl)方法设置缓存
创建 get(key) 方法获取缓存
创建 delete 删除方法
创建 clear 清除所有方法
创建 #createNewIndex 生成数组索引私有方法
创建 #moveToTail(index) 移动到尾部私有方法
创建 #connect(prev, next) 拼接节点 next、prev 指针私有方法
核心逻辑梳理
设置缓存
获取索引，设置数据或更新数据
调整指针关系
获取缓存
缓存过期，删除缓存，记录空闲位置索引，调整指针关系
命中缓存，返回缓存，调整指针关系
指针关系(移动到尾、前后节点拼接)
如果是当前的尾，指针不变
如果是头，将当前索引的下一个节点设置为头，将自己设置为尾，将原来尾的 next 指针指向自己，将自己的 prev 指针指向原来的尾
如果是其他位置，拼接当前节点前后节点的 next 、prev 指针， 及前节点的 next 指针指向后节点，后节点的 prev 指针指向前节点
获取索引
已有缓存(命中)的索引
数据长度超上限，返回头的索引
有空闲空间，返回空闲位置的索引
未填充满，返回数据长度的累计
2.3、代码实现
按照上面的梳理，将它转化为 JavaScript 代码：
class Cache {constructor(options) {const { max = 5, ttl = 0 } = options || {};this.max = max;if (!this.max) {throw new Error('长度必须大于0')}this.ttl = ttl || 0;// 存储 key 及 key 对应的索引this.keyMap = new Map();// 存放keythis.keyList = new Array(this.max).fill(null);// 存放valuethis.valList = new Array(this.max).fill(null);// 存放prev指针索引this.prev = new Array(this.max);// 存放next指针索引this.next = new Array(this.max);// 存放过期的索引this.free = [];// 双链表头索引this.head = 0;// 双链表尾索引this.tail = 0;// 计数this.size = 0;// 未达到上限的位置索引this.fill = 1;}set(key, value, ttl = this.ttl) {let index = this.keyMap.get(key);// 增加新内容if (index === undefined ) {index = this.#createNewIndex();this.keyList[index] = key;this.valList[index] = { value, expire: ttl ? Date.now() + ttl * 1000 : -1 };this.keyMap.set(key, index);// 设置双链表 next 和 prev 指针this.next[this.tail] = index;this.prev[index] = this.tail;this.tail = index;this.size ++;} else {// 老内容, 更新, 改变链表指针const oldVal = this.valList[index];if (value !== oldVal) {this.valList[index] = value;}this.#moveToTail(index);}}get(key) {const index = this.keyMap.get(key);const now = Date.now();let value = null;if (index !== undefined) {const result = this.valList[index];// 过期删除if (now > result.expire) {this.delete(key);} else {// 移动到尾(改变指针)value = result.value;this.#moveToTail(index);}}return value}delete(key) {let deleted = false;const index = this.keyMap.get(key);if (index !== undefined) {if (this.size === 1) {this.clear();} else {this.keyMap.delete(key);this.valList[index] = null;this.keyList[index] = null;this.free.push(index);this.size --;if (index === this.head) {// 指定新的头this.head = this.next[index];} else if (index === this.tail) {// 指定新的尾this.tail = this.prev[index];} else {// 串联置空节点前后节点指针this.#connect(this.prev[index], this.next[index]);}}}return deleted;}clear() {this.keyMap.clear();this.valList.fill(null);this.keyList.fill(null);this.head = 0;this.tail = 0;this.fill = 1;this.free = [];this.size = 0;}// 创建新的索引值, 用来关联key、value、prev指针、next指针#createNewIndex() {if (this.size === 0) {return this.tail;}if (this.size === this.max) {const head = this.head;const key = this.keyList[head];this.head = this.next[head];this.keyMap.delete(key);this.size --;return head;}if (this.free.length) {// 过期空闲的位置return this.free.pop();}return this.fill++;}#moveToTail(index) {if (index !== this.tail) {if (index === this.head) {this.head = this.next[index];} else {this.#connect(this.prev[index], this.next[index]);}this.#connect(this.tail, index);this.tail = index;}}#connect(prev, next) {this.prev[next] = prev;this.next[prev] = next;}}
缓存是提高系统性能有效的一种方法，比如 Web，无论是设置浏览器缓存、CDN 缓存、业务 Nginx 缓存、或是 SSR 服务中的页面缓存、页面组件缓存、数据接口缓存等，合理的利用缓存策略，就能极大的改善服务负载能力，提升系统性能。
学习了 LRU 缓存删除算法规则、双链表和数组这两种数据结构，借助数组可以用下标快速查找特点，结合哈希表、双链表各自的优点实现了一个含基本功能高效的 LRU 缓存库，所有操作中都没有循环遍历，整个操作时间复杂度为 O(1)。不论是 LRU 删除规则，还是 LRU 精巧的技术实现，都为以后淘汰不常被访问的、保留最新最频繁被访问这样的业务场景提供了实现思路。
