设计缓存系统

原文:Design a Cache System

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

与我们以前的文章相似,我们希望选择一些流行和实用的系统设计面试问题,这样你不仅可以理解如何在面试中分析问题,同时还可以学习一些有趣的内容。

如果你不了解系统设计面试,我建议你先阅读本教程。在这篇文章中,我们正在解决这个问题 - 如何设计一个缓存系统。这篇文章涵盖的主题包括:

  • 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 的信息。

总结

缓存可能是非常有趣和实用的话题,因为现在几乎所有的系统都使用它。 还有很多话题,像过期策略,我没有在这里设计。

如果你想了解更多类似的文章,请查看我们的系统设计面试问题集。