与我们以前的帖子类似，我们精选了一些流行且实用的系统设计面试问题。希望通过本文，您不仅能获得分析面试问题的思路，还能同时学习一些有趣的技术知识。

如果您对系统设计面试一无所知，建议您先阅读本教程。本文将聚焦于一个经典问题：如何设计缓存系统。文章涵盖的主题包括：

  • LRU 缓存
  • 淘汰策略 (Eviction Policy)
  • 缓存并发控制
  • 分布式缓存系统

问题描述

如何设计缓存系统？

缓存系统)是当今几乎所有应用程序中广泛采用的技术，适用于技术堆栈的每一层。例如，在网络层，缓存用于 DNS 查找；在 Web 服务器层，缓存用于处理频繁的请求。

简而言之，缓存系统存储常用资源（通常在内存中），当后续请求相同资源时，系统可以立即返回。它通过占用更多的存储空间来换取系统效率的提升。

LRU 缓存

LRU（最近最少使用） 是最常见的缓存算法之一。实际上，讨论 LRU 缓存的数据结构和设计也是常见的面试问题。让我们从这种方法开始。

LRU 缓存的工作方式非常简单。当客户端请求资源 A 时，情况如下：

  • 缓存命中：如果缓存中存在 A，我们将立即返回。
  • 缓存未命中（有空位）：如果缓存中没有 A，且具有额外的存储插槽，我们将获取资源 A 返回给客户端，并将 A 插入缓存。
  • 缓存未命中（已满）：如果缓存已满，我们将淘汰最近最少使用的资源，并将其替换为资源 A。

此处的策略是最大程度地增加请求资源在缓存中的命中率。那么如何实现一个简单的 LRU 缓存呢？

LRU 设计与实现

LRU 缓存应支持以下操作：查找、插入和删除。

  • 为了实现快速查找，我们需要使用哈希表 (Hash Map)。
  • 为了实现快速插入/删除，您应该想到类似链表的内容。
  • 由于我们需要有效地找到最近最少使用的物品，我们需要某种有序结构，例如队列、堆栈或排序数组。

结合上述分析，我们可以使用由双向链表实现的队列来存储所有资源。另外，需要一个哈希表，其中将资源标识符作为键，并将相应队列节点的地址作为值。

运作方式如下：

  1. 当请求资源 A 时，我们检查哈希表以查看缓存中是否存在 A。
  2. 如果存在，我们可以立即找到相应的队列节点并返回资源（通常需将该节点移至链表尾部，表示最近使用）。

  3. 如果不存在，我们将 A 添加到缓存中。

    • 如果有足够的空间，我们只需在队列末尾添加 A 并更新哈希表。
    • 否则，我们需要删除最近最少使用的条目。为此，我们可以轻松地从哈希表中删除队列的头部节点及相应的条目。

淘汰策略

当缓存已满时，我们需要删除现有项目以获取新资源。实际上，删除最近最少使用的项目只是最常见的方法之一。那么还有其他方法可以做到吗？

如上所述，该策略的核心是最大程度地增加请求资源在缓存中的机会。以下简要介绍几种方法：

  • 随机替换 (RR, Random Replacement)：顾名思义，我们可以随机删除条目。
  • 最少使用次数 (LFU, Least Frequently Used)：我们保留每项资源被请求的频率计数，并删除最不常用的一项。
  • W-TinyLFU：这是一种现代淘汰策略。简而言之，LFU 的问题是有时某个项目仅在过去经常使用，但 LFU 仍会保留该项目很长时间。W-TinyLFU 通过计算时间窗口内的频率来解决此问题，并具有各种存储优化。

并发控制

为了讨论并发性，我们需要探讨为什么缓存存在并发问题以及我们如何解决它。

这属于经典的读写器问题 (Reader-Writer Problem)。当多个客户端尝试同时更新缓存时，可能会发生冲突。例如，两个客户端可能竞争同一个缓存插槽，而最后更新缓存的客户端则获胜（可能导致数据不一致）。

当然，常见的解决方案是使用锁 (Lock)。缺点很明显——它对性能有很大影响。我们如何优化呢？

  • 分片 (Sharding)：一种方法是将缓存拆分为多个分片，并对每个分片加锁。这样，如果客户端从不同的分片更新缓存，客户端就不会彼此等待。但是，鉴于热点条目更可能被访问，某些分片将比其他分片更经常被锁定。
  • 提交日志 (Commit Log)：一种替代方法是使用提交日志。要更新缓存，我们可以将所有变更操作存储到日志中，而不是立即更新。然后由一些后台进程异步执行所有日志。数据库设计中通常采用此策略。

分布式缓存

当系统达到一定规模时，我们需要将缓存分配给多台计算机。

一般策略是保留一个将每个资源映射到相应计算机的哈希表。因此，从该哈希表中请求资源 A 时，我们知道机器 M 负责缓存 A，并将请求定向到 M。在机器 M 上，其工作原理与上述本地缓存类似。如果机器 M 在内存中不存在该资源，则可能需要获取并更新 A 的缓存。之后，它将缓存返回到原始服务器。

如果您对此主题感兴趣，可以查看有关 Memcached 的更多信息。

总结

缓存可能是一个非常有趣且实用的主题，因为当今几乎所有系统都使用它。还有很多我不在此讨论的主题，例如过期策略 (Expiration Policy)。

说明：本文主要介绍缓存系统设计的核心概念与通用策略，具体实现细节可能因业务场景和技术栈的不同而有所差异。