与我们以前的帖子类似，我们希望选择流行且实用的系统设计面试问题，这样您不仅可以获得关于如何分析面试问题的想法，而且还可以同时学习一些有趣的东西。
如果您对系统设计面试一无所知，建议您先阅读本教程。在本文中，我们正在解决问题-如何设计缓存系统。这篇文章涵盖的主题包括：
- LRU缓存
- 驱逐政策，
- 缓存并发
- 分布式缓存系统
问题
如何设计缓存系统？
缓存系统是当今几乎所有应用程序中广泛采用的技术。此外，它适用于技术堆栈的每个层。例如，在网络区域中，高速缓存用于DNS查找，而在Web服务器中，高速缓存用于频繁的请求。
简而言之，缓存系统存储常用资源（也许在内存中），当下次有人请求相同资源时，系统可以立即返回。它通过占用更多的存储空间来提高系统效率。
LRU
LRU（最近最少使用）是最常见的缓存系统之一。实际上，另一个常见的面试问题是讨论LRU缓存的数据结构和设计。让我们从这种方法开始。
LRU缓存的工作方式非常简单。客户端请求资源A时，情况如下：
- 如果缓存中存在A，我们将立即返回。
- 如果没有，并且缓存具有额外的存储插槽，我们将获取资源A并返回到客户端。另外，将A插入缓存。
- 如果缓存已满，我们将踢出最近最少使用的资源，并将其替换为资源A。
此处的策略是最大程度地增加请求资源在缓存中的机会。那么如何实现简单的LRU？
LRU设计
LRU缓存应支持以下操作：查找，插入和删除。显然，为了实现快速查找，我们需要使用哈希。同样，如果我们想快速插入/删除，您应该想到类似链表的内容。由于我们需要有效地找到最近最少使用的物品，因此我们需要一些东西，例如队列，堆栈或排序数组。
为了结合所有这些分析，我们可以使用由双链表实现的队列来存储所有资源。另外，需要一个哈希表，其中将资源标识符作为键，并将相应队列节点的地址作为值。
运作方式如下。当请求资源A时，我们检查哈希表以查看缓存中是否存在A。如果存在，我们可以立即找到相应的队列节点并返回资源。如果没有，我们将A添加到缓存中。如果有足够的空间，我们只需在队列末尾添加a并更新哈希表。否则，我们需要删除最近最少使用的条目。为此，我们可以轻松地从哈希表中删除队列的头部和相应的条目。
驱逐政策
当缓存已满时，我们需要删除现有项目以获取新资源。实际上，删除最近最少使用的项目只是最常见的方法之一。那么还有其他方法可以做到吗？
如上所述，该策略是最大程度地增加请求资源在缓存中的机会。我将在这里简要介绍几种方法：
- 随机替换（RR）–顾名思义，我们可以随机删除条目。
- 最少使用次数（LFU）–我们保留每项请求的频繁程度计数，并删除最不常用的一项。
- W-TinyLFU –我也想谈一谈这种现代驱逐政策。简而言之，LFU的问题是有时过去仅经常使用某个项目，但是LFU仍会保留该项目很长时间。W-TinyLFU通过计算时间窗口内的频率来解决此问题。它还具有各种存储优化。
并发
为了讨论并发性，我想谈谈为什么缓存存在并发性问题以及我们如何解决它。
它属于经典的读写器问题。当多个客户端尝试同时更新缓存时，可能会发生冲突。例如，两个客户端可能竞争同一个缓存插槽，而最后更新缓存的客户端则获胜。
当然，常见的解决方案是使用锁。缺点很明显–它对性能有很大影响。我们如何优化呢？
一种方法是将缓存拆分为多个分片，并对每个分片都有一个锁，这样，如果客户端从不同的分片更新缓存，客户端就不会彼此等待。但是，鉴于热门条目更可能被访问，某些分片将比其他分片更经常被锁定。
一种替代方法是使用提交日志。要更新缓存，我们可以将所有变异存储到日志中，而不是立即更新。然后一些后台进程将异步执行所有日志。数据库设计中通常采用此策略。
分布式缓存
当系统达到一定规模时，我们需要将缓存分配给多台计算机。
一般策略是保留一个将每个资源映射到相应计算机的哈希表。因此，从该哈希表中请求资源A时，我们知道机器M负责缓存A，并将请求定向到M。在机器M上，它的工作原理与上述本地缓存类似。如果机器M在内存中不存在，则可能需要获取并更新A的缓存。之后，它将缓存返回到原始服务器。
如果您对此主题感兴趣，可以查看有关Memcached的更多信息。
摘要
缓存可能是一个非常有趣且实用的主题，因为当今几乎所有系统都使用它。还有很多我不在此讨论的主题，例如过期策略。
