设计缓存系统
译者：飞龙
自豪地采用谷歌翻译
与我们以前的文章相似，我们希望选择一些流行和实用的系统设计面试问题，这样你不仅可以理解如何在面试中分析问题，同时还可以学习一些有趣的内容。
如果你不了解系统设计面试，我建议你先阅读本教程。在这篇文章中，我们正在解决这个问题 - 如何设计一个缓存系统。这篇文章涵盖的主题包括：
- LRU 缓存
- 换页策略
- 缓存并发
- 分布式缓存系统
问题
如何设计缓存系统？
缓存系统是目前几乎所有应用中广泛采用的技术。另外，它适用于技术栈的每一层。例如，在网络领域中，缓存用于 DNS 查找，Web 服务器缓存用于频繁的请求。
简而言之，缓存系统（可能在内存中）存储常用资源，当下次有人请求相同的资源时，系统可以立即返回。它通过消耗更多的存储空间来提高系统效率。
LRU
最常用的缓存系统之一是 LRU（最久未使用）。 事实上，另一个常见的面试问题是讨论 LRU 缓存的数据结构和设计。 我们从这个方法开始。
LRU 缓存的工作方式非常简单。 当客户端请求资源 A 时，发生如下情况：
- 如果缓存中存在 A，我们只需立即返回。
- 如果没有，并且缓存具有额外的存储空间，则我们获取资源 A 并返回给客户端。 另外，将 A 插入缓存。
- 如果缓存已满，我们将最久没使用的资源剔除，并将其替换为资源 A
这里的策略是最大限度地提高请求资源存在于缓存中的机会。 那么我们怎样才能实现一个简单的 LRU？
LRU 设计
LRU 缓存应该支持这些操作：查找，插入和删除。显然，为了实现快速查找，我们需要使用散列。同样的道理，如果我们想要快速插入/删除，链接列表就会出现在你的脑海里。由于我们需要有效地查找最久未使用的项目，所以我们需要按顺序排列队列，栈或有序数组。
为了结合所有这些分析，我们可以使用由双向链表实现的队列来存储所有的资源。此外，还需要一个哈希表，其中资源标识符为键，相应队列节点的地址为值。
工作原理是这样。当请求资源 A 时，我们检查哈希表来查看缓存中是否存在 A。如果存在，我们可以立即找到相应的队列节点并返回资源（译者注：并移动到队列尾部）。如果不是的话，我们将 A 添加到缓存中。如果有足够的空间，我们只要在队列的末尾添加 A 就可以了。否则，我们需要删除最久未使用的条目。为了这样做，我们可以很容易地删除队列的头部和哈希表中相应的条目。
（译者注：队列中也需要储存资源 ID，这样从队列中删除资源之后，可以从哈希表中也删除。）
换页策略
当缓存已满时，我们需要删除现有项目来存放新资源。 实际上，删除最久未使用的项目只是最常用的方法之一。 那么还有其他方法可以做到吗？
如上所述，策略是尽可能地将请求资源存在于缓存中。 我将在这里简要提一下几种方法：
- 随机替换（RR） - 如术语所示，我们可以随机删除一个条目。
- 最不经常使用（LFU） - 我们维护每个项目的请求频率，并删除最不经常使用的项目。
- W-TinyLFU - 我也想谈谈这个现代的换页策略。 总而言之，LFU 的问题在于，有时候一个条目只是过去经常使用，而 LFU 仍然会保留这个项目很长一段时间。 W-TinyLFU 通过计算时间窗内的频率来解决这个问题。 它也有各种存储优化。
并发
为了讨论并发性，我想谈谈为什么缓存存在并发问题，我们如何解决这个问题。
它可以归为经典的读写器问题。当多个客户端同时尝试更新缓存时，可能会有冲突。例如，两个客户端可能竞争相同的缓存槽，而最后一个更新缓存的客户端将获胜。
当然，常见的解决方案是使用锁。缺点是显而易见的 - 它会严重影响性能。我们如何优化呢？
一种方法是将缓存分成多个分片，并为每个分片分配一个锁，这样如果客户端在不同的分片中更新缓存，就不会相互等待。但是，由于热门的条目更有可能被访问，某些分片将比其他碎片锁定得更频繁。
另一种方法是使用提交日志。为了更新缓存，我们可以将所有改动存储到日志中，而不是立即更新。然后一些后台进程将异步执行所有的日志。数据库设计中通常采用这种策略。
分布式缓存
当系统达到一定规模时，我们需要将缓存分配给多台机器。
一般的策略是保留一个哈希表，将每个资源映射为相应的机器。 因此，当请求资源 A 时，从这个哈希表中我们知道机器 M 负责缓存 A 并将请求指向 M。在机器 M 中，其工作方式类似于上面讨论的本地缓存。 如果 A 不存在于内存中，则机器 M 可能需要获取并更新 A 的缓存。 之后，它将缓存返回到原始服务器。
如果你对此主题感兴趣，可以查看更多 Memcached 的信息。
总结
缓存可能是非常有趣和实用的话题，因为现在几乎所有的系统都使用它。 还有很多话题，像过期策略，我没有在这里设计。
如果你想了解更多类似的文章，请查看我们的系统设计面试问题集。