Node.js 缓存之 LRU Cache 高效实现|key|lru|内存|哈希表|链表

前言

网易新闻移动端站点部分页面是通过 Vue SSR 服务来渲染的，在得到同构、SEO、内容到达时间这些收益的同时，不得不面对 Vue SSR 服务带来的性能问题，Vue 创建组件实例和虚拟 DOM 节点的性能开销，是远远大于Handlebars 这种基于字符串拼接模板的。

在优化性能的过程中，与同事聊到用空间换时间来提升性能的时候，同事丢来一句: “性能不够，缓存来凑”，虽是一句调侃，却可以看出缓存是提升性能的利器。我们引入了 LRU Cache 对页面和页面组件做不同的缓存策略，改善服务负载能力，缩短响应时间，提升系统性能。本文会和大家一起学习高效 LRU Cache 背后的原理和技术实现，便于在相关场景更好地去应用。

缓存介绍

1、缓存的作用
缓存一般用来暂存数据处理结果，为下次访问提供使用。很多时候，数据的处理、数据的获取非常费时，频繁的数据请求或处理会消耗大量资源，缓存就是将这些处理后的数据存储起来，当再次请求此数据时，直接从缓存中获取而不重新进行数据获取或处理，从而降低资源的消耗提高响应速度。

2、缓存的分类
缓存分本地缓存和分布式缓存。本地缓存是应用中的组件，与应用耦合，在应用同一个进程中请求非常快，适合无需进程相互通知的场景。分布式缓存是与应用分离的缓存服务，比如 redis，是一个独立的服务，与本地应用隔离，多个应用可以共享缓存。

3、缓存的删除规则
在使用缓存时通常是有存储空间的限制，不论是内存缓存、文件缓存或者是独立的缓存数据库，当存储达到上限的时候是需要删除一部分数据来存放新的数据，我们将依照什么规则来删除呢? 常见的删除规则算法有：FIFO(先进先出算法规则)、LRU(最近最久未使用算法规则)、LFU(最近最少使用算法规则)。

LRU 是我平常用的最多的一种，现在我们一起来了解 LRU 缓存算法规则背后精巧的技术实现。

LRU 缓存高效实现

LRU(Least Recently Used) 缓存算法实现思想是：假设一个数据在最近时间内未被访问，那么在将来被访问的可能性也更小，当数据达到上限时优先删除最近时间内未被访问的数据。

1、快速理解LRU删除算法规则
我们把 LRU 缓存想象成一个有头和尾的有序格子，新数据和最近被访问的数据的格子移动到格子末尾，而处于格子头部的在数据达到上限时将被删除，如下图所示:

为了加深对 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 valuedelete(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 精巧的技术实现，都为以后淘汰不常被访问的、保留最新最频繁被访问这样的业务场景提供了实现思路。