网络拾遗之Http缓存

前言

大家好，我是柒八九。在前天(周六)利用一天的时间，看了关于前端工程化的相关书籍和知识点，里面涉及到很多关于工程化的细节点和设计细节。但是其中有一点，说到关于「客户端缓存」

1. 本地缓存(localStorage/SessionStorage)
2. HTTP缓存策略(「强缓存」、「协商缓存」)。

而关于Http缓存，是在很早就打算总结的知识点。所以，正好借着对这块知识点的热乎劲，那就「撸起袖子加油干」。

然后，虽然针对客户端缓存有两种。但是「本地缓存」更多的是「代码层面」的一种缓存机制。和业务耦合很强。那些只是针对具体场景的应用。不在这篇文章的讨论范围内。

文章概要

1. 缓存：何时起作用
2. 缓存的常见淘汰机制
3. HTTP缓存策略
4. 缓存场景应用(Vue内部组件KeepAlive)

1. 缓存：何时起作用

先说结论：

❝「HTTP缓存」是作用于网站「导航阶段」的网络请求的「开始阶段」 1. 导航阶段 2. 网络请求阶段 ❞

何为导航？是指用户发出 URL 请求到页面「开始解析」的这个过程。

「网络请求阶段」包含我们前面讲到关于网络的一些知识点。

• DNS:网络拾遗之 DNS协议：网络世界的地址簿
• TCP:网络拾遗之TCP
• Request:这块主要针对HTTP协议，我们后期会有介绍
• Response:根据Content-Type 字段判断浏览器服务器返回的响应体数据是什么类型，然后浏览器会根据 Content-Type 的值来决定如何显示响应体的内容
  • 页面是如何生成的(宏观角度)
  • Chromium 最新渲染引擎--RenderingNG
  • RenderingNG中关键数据结构和它们的角色
  • 下载类型：请求会被提交给浏览器的下载管理器，同时该 URL 请求的导航流程就此结束
  • HTML：浏览器则会继续进行后续流程，而这个流程我们也很熟，在前面我们介绍过，

在上图中，我们已经将HTTP缓存的位置做了标注。

我们简单的讲述一下，在HTTP缓存之前所发生的流程。

• 用户输入：地址栏中输入一个「查询关键字」，此时分「两种情况」
  1. 搜索内容：地址栏会使用浏览器「默认的搜索引擎」，来合成新的带搜索关键字的 URL
  2. 符合 URL 规则：地址栏会根据规则，把内容加上协议，合成为完整的 URL
• 卸载「原页面」并「重定向」到新页面：（如果有原页面） 浏览器会将现有页面卸载掉并重定向到用户新输入的url页面，也就是图中Process Unload Event和Redirect流程
• 处理Service Worker：(如果有的话) 如果当前页面注册了Service Worker:主要用途是拦截、重定向和修改页面发出的请求，充当网络请求的仲裁者的角色。也就是图中Service Worker Init与Service Worker Fecth Event步骤
• 「HTTP Cache」: 这是该文的重点。

2. 缓存的常见淘汰机制

在缓存中，存在两种比较场景的淘汰机制

1. 「LRU」:Least Recently Used 也就是大家常说的「最近最少使用」，最近使用的数据是有用的，很久没使用过的数据是无用的，内存满了，先删除那些很久没用过的数据
2. 「LFU」:Least Frequently Used 每次淘汰那些「使用次数最少」的数据

今天，我们来实现纯手工硬撸一个「LRU」算法。正好该算法，也是LeetCode中比较中等的题。（如果不感兴趣，可以直接跳过看后面的部分。该部分是做为一个知识点的拓宽。就算前端有算法题，也很少涉及LRU/LFU的。）

话不多说，开搞。

题目描述

❝实现 LRUCache 类： 1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 3. void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出「最久未使用」的关键字。 「Note」: 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行 ❞

分析上面的要求，如果想让get/put方法的时间复杂度为O(1)，LRUCache这个数据结构必须具备如下：

1. LRUCache中的元素「必须有序」，以区分最近使用的和最久未使用的数据，当容量满了以后要「删除最久未使用」的那个元素腾位置。
2. 在LRUCache中「快速」找到某个key是否存在并得到对应的val
3. 每次访问LRUCache中的某个key,需要将这个元素变为最近使用的，也就是说LRUCache要支持在「任意位置快速插入和删除」元素

关键点：「有序」/「快速」/「任意位置插入和删除」。

从以往对数据结构了解，我们检索到两种数据结构可以分别满足上面的关键点部分点。

• 哈希表（Map）查找快，但是数据无固定顺序
• 链表有顺序之分，插入、删除快，但是查找慢

本着打不过就加入的原则，我们将这两种数据结构进行融合处理--形成一种新的数据结构：「哈希链表」LinkedHashMap，它是「双向链表」和「哈希表」的结合体。

代码实现

双链表的节点类：

class Node {
  constructor(key, val) {
        this.key = key;
        this.val = val;
        this.next = null; //指向后一个节点
        this.prev = null; //指向前一个节点
  }
}

利用上面的Node数据结构，构建一个「双链表」

class DoubleList {
  constructor(){
    // dummy头节点
    this.head = new Node(0,0);
     // dummy尾节点
    this.tail = new Node(0,0);
    // 首/尾指针 相互关联
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }
  
  // 在链表尾部添加节点x,时间复杂度为O(1)
  addLast(x){
    x.prev = this.tail.prev;
    x.next = this.tail;
    this.tail.prev.next =x;
    this.tail.prev = x;
    this.size++;
  }
  
  //删除链表中的x节点
  remove(x){
    x.prev.next = x.next;
    x.next.prev = x.prev;
    this.size--;
  }
  
  // 删除链表中第一个节点，并返回该节点
  removeFirst(){
    if(this.head.next === this.tail) return null;
    
    let first = this.head.next;
    this.remove(first);
    return first;
  }
  
}

我们实现的双链表，只能实现从「尾部」插入，也就是说靠近尾部的数据是最近使用的，靠近头部的数据是最久未使用的。

实现LRUCache

class LRUCache{
  constructor(capacity){
    this.cap = capacity;
    this.map = new Map();
    this.cache = new DoubleList();
  }
  
  // 将某个key 提升为最近使用
  makeRecently(key){
    let x = this.map.get(key);
    // 先从链表中删除这个节点
    this.cache.remove(x);
    // 重新插到队尾
    this.cache.addLast(x);
  }
  
  // 添加最近使用的元素
  addRecently(key,val){
    let x = new Node(key,val);
    // 链表尾部就是最近使用的元素
    this.cache.addLast(x);
    // 在map中添加key的映射
    this.map.set(key,x);
  }
  
  // 删除某一个key
  deleteKey(key){
    let x = this.map.get(key);
    // 从链表中删除
    this.cache.remove(x);
    //从map中删除
    this.map.delete(key);
  }
  
  //删除最久未使用的元素
  removeLeastRecently(){
    // 链表头部的第一个元素就是最久未使用的
    let deletedNode = this.cache.removeFirst();
    // 从map中删除对应的key
    let deletedKey = deletedNode.key;
    this.map.delete(deletedKey);
  }
  
  get(key){
    if(!this.map.has(key)) return -1;
    
    // 将数据提升为最近使用的
    this.makeRecently(key);
    return this.map.get(key).value;
  }
  
  put(key,val){
    if(this.map.has(key)){
      //删除旧的数据
      this.deleteKey(key);
      // 新插入的数据为最近使用的数据
      this.addRecently(key,val);
      return;
    }
    
    // 删除最久未使用的元素
    if(this.cap ===this.cache.size) 
        this.removeLeastRecently();
    
    // 添加为最近使用的元素
    this.addRecently(key,val);
  }
}

❝LRU算法的核心数据结构是使用「哈希链表」LinkedHashMap，首先借助链表的「有序性」是的链表元素维持插入的顺序，同时借助哈希映射的「快速访问能力」使得我们可以以O(1)时间复杂度访问链表中「任意元素」。 ❞

将如上的代码，在leetcode中是可以AC的。虽然，不是最优解。但是，其中涉及到思想是值得反复推敲的。

至于针对LFU我们就不在这里讨论了。

这里在唠叨几句，在上面的算法中，有些点，一带而过，主要是为了讲述LRU的主要实现思路，而一些比较常用且实用的算法技巧就没有展开来讲。我们这里做一个简单的提示。

• 处理链表相关题目时，新增的dumy节点，会节省很多边界情况
• 双指针的插入和删除，时刻注意prev/next节点的处理时机
• Map数据的操作，查询get()/删除delete()/设值set()/查数size

由于上面的代码过于繁琐，然后，为了能让大家对LRU真的有一个大致的了解，然后如果在面试中也遇到类似的题，可以「照猫画虎」的复刻出来。我直接copy一个简版的代码。

class LRUCache{
  constructor(capacity){
    this.map = new Map();
    this.capacity = capacity;
  }
  
  get(key){
    if(this.map.has(key)){
        let value = this.map.get(key);
        // 先删除原来位置数据
        this.map.delete(key); 
        // 在尾部追加数据，将key作为最新的值
        this.map.set(key, value);
        return value
    } else {
        return -1
    }
  }
  
  put(key,value){
     // 如果已有，那就要更新，即要先删了再进行后面的 set
    if(this.map.has(key)){
        this.map.delete(key);
    }
    this.map.set(key, value);
    // put 后判断是否超载
    if(this.map.size > this.capacity){
        // 将map的最前面的数据删除
        // map.keys()返回的是迭代器
        this.map.delete(
          this.map.keys().next().value
        );
    }
  }
}

3. HTTP缓存策略

❝「最好最快」的请求就是「没有请求」 ❞

浏览器对「静态资源」的缓存本质上是 HTTP 协议的缓存策略，其中又可以分为「强制缓存」和「协商缓存」。

❝两种缓存策略都会「将资源缓存到本地」 ❞

• 强制缓存策略根据「过期时间」决定使用本地缓存还是请求新资源：
• 协商缓存每次都会「发出请求」，经过「服务器进行对比」后决定采用本地缓存还是新资源。

具体采用哪种缓存策略，由 HTTP 协议的首部（ Headers ）信息决定。

在网络通信之生成HTTP消息中我们介绍过，消息头按照用途可分为「四大类」 1. 通用头：适用于请求和响应的头字段 2. 请求头：用于表示请求消息的附加信息的头字段 3. 响应头：用于表示响应消息的附加信息的头字段 4. 实体头：用于「消息体」的附加信息的头字段

我们对HTTP缓存用到的字段进行一次简单的分类和汇总。

❝ETag: 在「更新操作」中，有时候需要基于「上一次请求的响应数据」来发送下一次请求。在这种情况下，这个字段可以用来提供上次响应与下次请求之间的「关联信息」。上次响应中，服务器会通过 Etag 向客户端发送一个唯一标识，在下次请求中客户端可以通过 If-Match、If-None-Match、If-Range 字段将这个标识告知服务器，这样服务器就知道该请求和上次的响应是相关的。 这个字段的「功能和 Cookie 是相同」的，但 Cookie 是网景（Netscape）公司自行开发的规格，而 Etag 是将其进行标准化后的规格 ❞

Expires 和 Cache-control:max-age=x(强缓存)

❝Expires和 Cache-control:max-age=x 是「强制缓存」策略的关键信息，两者均是「响应首部信息」(后端返给客户端)的。 ❞

Expires 是 HTTP 1.0 加入的特性，通过指定一个「明确的时间点」作为缓存资源的过期时间，在此时间点之前客户端将使用本地缓存的文件应答请求，而不会向服务器发出实体请求。

Expires 的优点:

• 可以在缓存过期时间内「减少」客户端的 HTTP 请求
• 节省了客户端处理时间和提高了 Web 应用的执行速度
• 减少了「服务器负载」以及客户端网络资源的消耗

对应的语法

Expires: <http-date>

<http-date>是一个 HTTP-日期 时间戳

Expires: Wed, 24 Oct 2022 14:00:00 GMT

上述信息指定对应资源的「缓存过期时间」为 2022年8月24日 14点

❝Expires 一个「致命的缺陷」是：它所指定的时间点是以「服务器为准」的时间，但是「客户端进行过期判断」时是将「本地的时间与此时间点对比」。 ❞

如果客户端的时间与服务器存在「误差」，比如服务器的时间是 2022年 8月 23日 13 点，而客户端的时间是 2022年 8月 23日 15 点，那么通过 Expires 控制的缓存资源将会「失效」，客户端将会发送实体请求获取对应资源。

针对这个问题， HTTP 1.1 新增了 Cache-control 首部信息以便「更精准」地控制缓存。

常用的 Cache-control 信息有以下几种。

• no-cache: 使用 ETag 响应头来告知客户端（浏览器、代理服务器）这个资源首先需要被检查是否在服务端修改过，在这之前不能被复用。这个「意味着no-cache将会和服务器进行一次通讯」，确保返回的资源没有修改过，如果没有修改过，才没有必要下载这个资源。反之，则需要重新下载。
• no-store 在处理资源不能被缓存和复用的逻辑的时候与 no-cache类似。然而，他们之间有一个重要的「区别」。no-store要求资源每次都被请求并且下载下来。当在处理隐私信息（private information）的时候，这是一个重要的特性。
• public & private public表示此响应可以被浏览器以及中间缓存器「无限期缓存」，此信息并不常用，常规方案是使用 max-age 指定精确的缓存时间 private表示此响应可以被用户浏览器缓存，但是「不允许任何中间缓存器」对其进行缓存。例如，用户的浏览器可以缓存包含用户私人信息的 HTML 网页，但 CDN 却不能缓存。
• max-age=<seconds> 指定从「请求的时刻」开始计算，此响应的缓存副本有效的最长时间（单位：「秒」） 例如，max-age=360表示浏览器在接下来的 1 小时内使用此响应的本地缓存，不会发送实体请求到服务器
• s-maxage=<seconds> s-maxage 与 max-age类似，这里的「s」代表共享，这个指令一般仅用于 CDNs 或者其他「中间者」（intermediary caches）。这个指令会「覆盖」max-age和expires响应头。
• no-transform 中间代理有时会改变图片以及文件的格式，从而达到提高性能的效果。no-transform指令告诉中间代理不要改变资源的格式

❝max-age 指定的是缓存的「时间跨度」，而非缓存失效的时间点，不会受到客户端与服务器时间误差的影响。 ❞

与 Expires 相比， max-age 可以「更精确地控制缓存」，并且比 Expires 有「更高的优先级」

强制缓存策略下（ Cache-control 未指定 no-cache和no-store）的缓存判断流程

Etag 和 If-None-Match （协商缓存）

❝Etag 是「服务器」为资源分配的字符串形式「唯一性标识」，作为「响应首部」信息返回给浏览器 ❞

「浏览器」在 Cache-control 指定 no-cache 或者 max-age和 Expires 均过期之后，将Etag 值通过 If-None-Match 作为「请求首部」信息发送给服务器。

「服务器」接收到请求之后，对比所请求资源的 Etag 值是否改变，如果未改变将返回 304 Not Modified,并且根据既定的缓存策略分配新的 Cache-control 信息;如果资源发生了改变，则会 返回「最新」的资源以及重新分配的 Etag值。

如果强制浏览器使用协商缓存策略，需要将 Cache-control 首部信息设置为 no-cache ，这样便不会判断 max-age和 Expires 过期时间，从而「每次资源请求都会经过服务器对比」。

缓存场景应用

在上面我们从缓存实现机制，HTTP缓存分类等不同角度来讲缓存这件事。而缓存作为一个屡试不爽的性能优化点，在各种场合都屡见不鲜。

在vue开发中，有一个官方提供的优化手段<keep-alive>的内部组件。

❝KeepAlive的本质是「缓存管理」，再配合特殊的挂载/卸载逻辑 ❞

首先，KeepAlive组件的实现需要「渲染器」层面的支持。在KeepAlive卸载时候，不能真正的进行卸载处理，否则就不能维持组件的当前状态了。

正确的做法是，将KeepAlive所包裹的组件从「原容器」搬运到另外一个「隐藏」的容器中宏，实现「假卸载」(deactivated)。当被搬运到隐藏容器中的组件需要再次被「挂载」时，再从隐藏容器中搬运到原容器中。这叫(activated)

「失活」（deactivated）的本质就是将组件所渲染的内容移动到隐藏容器中，而「激活」(activated)的本质是将组件所渲染的内容从隐藏容器中搬运回原来的容器。

Vue.js采用LRU的缓存策略，对KeepAlive组件进行数据的更新。

<template>
  <keep-alive :max="2">
    <component :is="dynamicComp"/>
  </keep-alive>
</template>

在上面代码中，设置缓存容量为2。假设我们有三个组件Comp1/Comp2/Comp3，并且它们都会被缓存。

模拟组件切换过程中缓存变化：

• 初始渲染Comp1并缓存它。此时缓存队列为: [Comp1],并且最新一次访问(渲染)的组件是Comp1
• 切换到Comp2并缓存它。此时缓存队列为: [Comp1,Comp2],并且最新一次访问(渲染)的组件是Comp2
• 切换到Comp3,此时缓存容量已满，需要裁剪。根据LRU规则。Comp2是安全的，所以需要将最久的元素(队头元素)，也就是Comp1进行remove，然后将Comp3插入到队尾，以表示这是最新的数据

我们把上面的操作步骤套入第二部分(缓存的常见淘汰机制)中无论哪个代码中。都会发现思路如此明朗。这也是我为啥，用了很大的篇幅来手写了一个LRU。其实，就是为了讲这个做铺垫。