移动端相关

到这里，相信大家已经能够熟练运用缓存来加速甚至避免网络请求，然而浏览器为每个应用所分配的存储空间是有限的，因此我们往往需要删除部分缓存来释放存储空间，至于需要删除哪些缓存，这正是本章需要讲解的内容。

由于 CacheStorage 是针对请求/响应类型对象的存储方案，它适用于网址可寻址（比如脚本、样式、图片、HTML 等）资源，基于此我们将使用 IndexedDB 来存储并处理缓存的过期信息，下文中所使用的类 DB 为 IndexedDB API 的简单封装，具体代码可在示例中获得，为节省篇幅，此处不再列出。

# 常见算法

# FIFO

该算法的核心思想是：如果一个数据最先加入缓存中，那么在存储空间不足时应该删除加入时间较久远的数据。

代码实现如下：

class CacheExpirationDB extends DB {
  constructor(cacheName, maxAgeSeconds) {
    super('CacheExpiration', 1, event => {
      const db = event.target.result;
      const objStore = db.createObjectStore('CacheExpiration', { keyPath: 'id' });
      objStore.createIndex('timestamp', 'timestamp', { unique: false });
    });
    this._cacheName = cacheName;
    this._maxAgeSeconds = maxAgeSeconds;
  }

  /**
   * 去除 `url` 中的 `hash`（比如将：`/detail/12#hash` 转换为 `/detail/12`）
   */
  _normalizeURL(baseUrl) {
    const url = new URL(baseUrl, location);
    url.hash = '';
    return url.pathname;
  }

  /**
   * 根据 url 生成记录 id
   */
  _getId(url) {
    return `${this._cacheName}|${this._normalizeURL(url)}`;
  }

  async set(url, timestamp) {
    const expireEntries = await this.expireEntries(timestamp);
    await this.write('put', 'CacheExpiration', {
      id: this._getId(url),
      cacheName: this._cacheName,
      url: this._normalizeURL(url),
      timestamp
    });
    return expireEntries;
  }

  async expireEntries(timestamp) {
    const minTimestamp = timestamp - this._maxAgeSeconds;
    const entriesToDelete = await this._transaction(
      'CacheExpiration', 'readonly', (transaction, done) => {
        const entriesToDelete = [];
        const store = transaction.objectStore('CacheExpiration');
        const result = store.index('timestamp').openCursor(null, 'prev');
        result.onsuccess = ({ target }) => {
          const cursor = target.result;
          if (cursor) {
            const record = cursor.value;
            if (record.cacheName === this._cacheName && record.timestamp < minTimestamp) {
              entriesToDelete.push(record);
            }
            cursor.continue();
          } else {
            done(entriesToDelete);
          }
        };
      }
    );

    const urlsDeleted = [];
    for (const entry of entriesToDelete) {
      await this.write('delete', 'CacheExpiration', entry.id);
      urlsDeleted.push(entry.url);
    }
    return urlsDeleted;
  }
}

方法 set 中：
- 首先尝试移除时间戳（timestamp）小于指定值的记录，而后将该 url 相关的缓存信息添加到记录中。
- 返回需要移除的记录信息，以便 Cache API 删除具体的缓存。
方法 set仅需要在设置缓存时调用。
方法 expireEntries 中，我们需要通过 timestamp 索引并以降序的形式来获得记录列表，这样才能保证得到的待删除记录是最老的记录。

该算法存在的主要问题是：最先被加入的缓存很可能是被经常访问的，如果将其移除，便会降低缓存命中率，从而造成缓存污染现象。针对此类问题，我们可以使用下面的 LRU 或 LFU 来解决。

# LRU

该算法的核心思想是：如果一个数据在最近一段时间内没有被访问，那么在未来它被访问的可能性也很小，故此在存储空间不足时优先删除最久没有被访问到的数据。

代码实现如下：

class CacheExpirationDB extends DB {
  //constructor、_normalizeURL、 _getId 及 expireEntries 的实现与 FIFO 一致，故此省略

  async set(url, timestamp) {
    const id = this._getId(url);
    const entry = await this.read('get', 'CacheExpiration', id);
    if (entry) {
      await this.write('put', 'CacheExpiration', {
        ...entry,
        timestamp
      });
      return [];
    }
    const expireEntries = await this.expireEntries(timestamp);
    await this.write('put', 'CacheExpiration', {
      cacheName: this._cacheName,
      url: this._normalizeURL(url),
      id,
      timestamp
    });
    return expireEntries;
  }
}

方法 set 中：
- 如果存在指定 url 的缓存记录，直接更新该记录的时间戳（timestamp），
- 如果不存在指定 url 的缓存记录，首先尝试移除时间戳（timestamp）小于指定值的记录，而后将该 url 相关的缓存信息添加到记录中，
- 返回需要移除的记录信息，以便 Cache API 删除具体的缓存。
方法 set 需要在命中缓存以及设置缓存时调用。
方法 expireEntries 中，我们需要通过 timestamp 索引并以降序的形式来获得记录列表，这样才能保证得到的待删除记录是最老的记录。

该算法存在的主要问题是：当处理热点数据时，该算法的效率很好，但如果处理偶发或周期性批量操作时依然会因为命中率的降低而造成缓存污染现象，针对此类问题，我们可以使用下面的 LFU 来解决。

# LFU

该算法的核心思想是：如果一个数据在最近一段时间内访问次数很少，那么在未来它被访问的可能性也很小，故此在存储空间不足时优先删除访问次数较少的数据。

代码实现如下：

class CacheExpirationDB extends DB {
  //_normalizeURL 与 _getId 的实现与 FIFO 一致，故此省略

  constructor(cacheName, maxEntries) {
    super('CacheExpiration', 1, event => {
      const db = event.target.result;
      const objStore = db.createObjectStore('CacheExpiration', { keyPath: 'id' });
      objStore.createIndex('usedCount', 'usedCount', { unique: false });
    });
    this._cacheName = cacheName;
    this._maxEntries = maxEntries;
  }

  async set(url) {
    const id = this._getId(url);
    const entry = await this.read('get', 'CacheExpiration', id);
    if (entry) {
      await this.write('put', 'CacheExpiration', {
        ...entry,
        usedCount: entry.usedCount + 1
      });
      return [];
    }

    const expireEntries = await this.expireEntries();
    await this.write('put', 'CacheExpiration', {
      cacheName: this._cacheName,
      url: this._normalizeURL(url),
      usedCount: 1,
      id
    });
    return expireEntries;
  }

  async expireEntries() {
    const entriesToDelete = await this._transaction(
      'CacheExpiration', 'readonly', (transaction, done) => {
        const entriesToDelete = [];
        let entriesNotDeletedCount = 0;
        const store = transaction.objectStore('CacheExpiration');
        const result = store.index('usedCount').openCursor(null, 'prev');
        result.onsuccess = ({ target }) => {
          const cursor = target.result;
          if (cursor) {
            const record = cursor.value;
            if (record.cacheName === this._cacheName) {
              if (entriesNotDeletedCount >= this._maxEntries) {
                entriesToDelete.push(record);
              } else {
                entriesNotDeletedCount++;
              }
            }
            cursor.continue();
          } else {
            done(entriesToDelete);
          }
        };
      }
    );
    const urlsDeleted = [];
    for (const entry of entriesToDelete) {
      await this.write('delete', 'CacheExpiration', entry.id);
      urlsDeleted.push(entry.url);
    }
    return urlsDeleted;
  }
}

方法 set 中：
- 如果存在指定 url 的缓存记录，直接更新该记录的访问次数（usedCount），
- 如果不存在指定 url 的缓存记录，首先尝试移除访问次数较小的记录，而后将该 url 相关的缓存信息添加到记录中，
- 返回需要移除的记录信息，以便 Cache API 删除具体的缓存。
方法 set 需要在命中缓存以及设置缓存时调用。
方法 expireEntries中，我们需要通过 usedCount索引并以降序的形式来获得记录列表，这样才能保证得到的待删除记录是使用次数较小的记录。
一般情况下，该算法的效率高于 LRU，且能够避免偶发或周期性批量操作时因缓存命中率下降而导致的缓存污染现象，但由于该算法需要记录数据的历史访问记录，一旦数据访问模式发生改变，则需要很长的时间来适应新的访问模式，在这段时间中很可能造成缓存污染。

# 运用

上一节中，我们介绍了常见的缓存置换算法，本节我们选用 FIFO 算法来对其使用进行说明，主要代码（仅对关键逻辑进行阐述说明，完整代码参见[示例](https://github.com/nanjingboy/pwa-demos/blob/master/part-2/client/sw.js）如下：

async function updateCacheExpirations(cacheName, cacheKey = null) {
  const db = new CacheExpirationDB(cacheName, maxAgeSeconds[cacheName]);
  let deletedKeys;
  if (cacheKey) {
    deletedKeys = await db.set(cacheKey, Date.now());
  } else {
    deletedKeys = await db.expireEntries(Date.now());
  }
  const cache = await caches.open(cacheName);
  for (const deletedKey of deletedKeys) {
    await cache.delete(deletedKey);
  }
}

async function setCache(cacheName, cacheKey, value) {
  const cache = await caches.open(cacheName);
  try {
    await cache.put(cacheKey, value);
    await updateCacheExpirations(cacheName, cacheKey);
  } catch (error) {
    if (error.name === 'QuotaExceededError') {
      await updateCacheExpirations(precacheName);
      await updateCacheExpirations(runtimeCacheName);
    }
    throw error;
  }
}

self.addEventListener('install', event => {
  event.waitUntil((async () => {
    //... 添加预缓存信息
    const precacheExpirationDB = new CacheExpirationDB(
      precacheName,
      maxAgeSeconds[precacheName]
    );
    for (const precacheItem of precacheList) {
      await precacheExpirationDB.set(precacheItem, Date.now());
    }
  })());
});

self.addEventListener('activate', event => {
  event.waitUntil((async () => {
    //... 其他逻辑
    const cacheNames = await caches.keys();
    for (const cacheName of cacheNames) {
      if (cacheName !== precacheName && /^precache\-\d+$/.test(cacheName)) {
        await caches.delete(cacheName);
        await (new CacheExpirationDB(cacheName, maxAgeSeconds[precacheName])).expireEntries(Infinity);
      }
    }
  })());
});

在 install 事件中初始化预缓存的有效期信息，并在 activate 事件中将之前版本的预缓存立刻失效以便释放存储空间。
由于 FIFO 只有在数据更新时才会设置相关缓存的时间戳，因此动态缓存有效期设置主要集中在 setCache 方法中：
- 尝试设置缓存并调用 updateCacheExpirations 方法删除已过期的缓存项。
- 如果在缓存设置中出现异常，且异常类型为 QuotaExceededError（该异常表示已使用的存储空间已经超过了浏览器的限制）时，我们将删除预缓存及运行时缓存中已过期的缓存项，以此来释放存储空间。
在 updateCacheExpirations 中，我们首先获得符合条件的已过期缓存对象，然后调用 Cache API 删除相关缓存。

# 总结

本章中，我们首先对常见的缓存置换算法进行了讨论：

FIFO：先进先出算法，当缓存空间不足时，优先删除最先加入缓存的数据项，该算法主要适用于实时性较强的数据。
LRU：最近最少使用算法，当缓存空间不足时，优先删除最久没有被访问到的数据，该算法主要适用于热点数据。
LFU：最不常使用算法，当缓存空间不足时，优先删除访问次数较少的数据，该算法主要适用于数据访问模式不会频繁发生变化的数据。

然后我们通过实例对 FIFO 算法的应用进行了阐述。由于不存在适用于所有场景的算法，因此我们在实际工作中，需要结合缓存类型、访问模式等因素来选择一个或综合多个算法来灵活地处理所遇到的问题。

阅读全文

← 实战篇 5 请求策略实战篇 7 Service Worker 更新 →