02.终极缓存设计，面试官最喜欢的缓存系统！

TopGeeky2024年12月1日大约 18 分钟

这边先来看一个场景

都知道在高并发的海量请求下查询数据库是一件非常耗时的事情，所以这个时候采用的策略就是创建一个缓存，每次查询都从缓存中查询数据，如果缓存没有数据，那就从数据库中查询数据，并更新到缓存当中，如果是你你要怎么设计这个缓存呢？

如果面试官想要提及缓存相关的系统设计问题，那么他会怎么开头呢？

如果你的网站每秒有成千上万的请求，你会如何提高响应速度？
当数据库成为瓶颈时，你会采取什么措施来减轻压力？
在设计一个高效的缓存系统时，你考虑过哪些关键因素？
LRU缓存是如何工作的？你能用简单的例子解释一下吗？
如果缓存服务器宕机了，你会怎么处理以保证系统的稳定性？

听到这些题目是不是很熟悉，一种面试的压迫袭来？别紧张，看完这篇文章我保证你可以跟面试官对答如流！

什么是缓存？为什么这么重要

想象一下，如果每次你想吃零食时都要去超市买，那得多麻烦啊！于是，聪明的人类发明了冰箱——把常用的零食放在里面，下次想吃的时候直接打开冰箱就行了。这不仅节省了时间，还避免了不必要的奔波。缓存在计算机世界里扮演着类似的角色，它存储常用的数据，以便快速访问，从而提高应用程序的响应速度和效率。

面试提示：在谈论缓存的好处时，可以提及减少数据库负载、提高读取速度等实际应用场景。

缓存的优点：

提高响应速度：
- 缓存可以存储经常访问的数据，当用户请求这些数据时，可以直接从缓存中快速获取，而不需要每次都去访问数据库或远程服务器，从而显著减少响应时间。
减轻后端负载：
- 通过将频繁访问的数据存储在缓存中，可以减少对后端服务（如数据库）的请求次数，从而降低后端系统的负载，提高整体系统的处理能力。
减少网络延迟：
- 对于分布式系统，缓存可以部署在网络边缘，例如CDN（内容分发网络），这样可以减少数据传输的距离，降低网络延迟，加快数据的传递速度。
提高可扩展性：
- 缓存可以帮助系统更好地应对突发流量，因为缓存可以吸收一部分流量，避免后端服务过载。这使得系统更容易扩展，以适应不断增长的需求。
容错和高可用性：
- 通过在多个位置复制缓存数据，可以在某个缓存节点发生故障时，仍然能够从其他节点获取数据，从而提高系统的容错能力和可用性。

合理使用缓存的条件

使用缓存对提高系统性能有很多好处，但是并不是所有情况下都需要使用缓存，在存在下面条件的情况下才能适合使用缓存的条件：

高读写比：
- 数据的读取频率远高于写入频率。一般来说，如果数据的读写比至少为2:1（即每次写入后至少被读取两次），那么使用缓存是有意义的。在实际应用中，这个比例可能会更高。
存在热点数据：
- 应用系统访问数据时遵循二八定律，即80%的访问集中在20%的数据上。这种情况下，缓存可以显著提高这些热点数据的访问速度。
可容忍一定程度的数据不一致：
- 缓存中的数据与源数据可能存在短暂的不一致。对于那些对数据一致性要求不是特别高的场景，可以设置适当的缓存失效时间来平衡性能和一致性。
数据更新频率较低：
- 如果数据更新非常频繁，缓存可能很快就会失效，导致缓存命中率低。因此，适合缓存的是那些更新频率相对较低的数据。
数据大小适中：
- 缓存的数据不宜过大，否则会占用大量内存，增加成本。适合缓存的是那些大小适中的数据。
数据访问模式可预测：
- 如果数据访问模式较为固定，可以预先加载到缓存中，从而提高缓存命中率。

合理的使用缓存对提高系统性能有很多好处，但是不合理的使用缓存反而会成为系统的累赘甚至风险。滥用缓存的三种情况如下：

频繁修改的数据

数据的读写比至少应该是2:1以上，即写入一次缓存，在数据更新前至少读写两次，缓存才有意义。真正实践中这个比例可能会更高。

没有热点的访问

如果应用系统访问数据没有热点，不遵循二八定律，即大部分数据访问并没有集中在小部分数据中，那么缓存也没有意义，因为大部分数据还没有被再次访问就已经被挤出缓存了。

数据的不一致与脏读

写入缓存的数据最好能容忍一定时间的数据不一致，一般情况下最好对缓存的数据设置失效时间(固定值+一定范围的随机值)。如果不能容忍数据的不一致，必须在数据更新时，删除对应的缓存(思考：为什么不是更新缓存)，但是这种情况只针对读写比非常高的情况。

# 缓存设计需要考虑的问题？

如何避免缓存穿透？
如何避免缓存击穿？
如何避免缓存雪崩？
缓存和数据库的一致性保证？

如何解决缓存穿透的问题？

缓存穿透是指对于一个不存在于缓存中的数据，每次请求都会穿透缓存层，直接访问底层数据源。为了解决缓存穿透问题，可以采取以下措施：

使用布隆过滤器（Bloom Filter）等技术，在查询缓存前进行快速过滤，判断数据是否存在；
在底层数据源中存储一个空值标记，表示该数据不存在，避免对缓存的重复穿透；
设置短期的缓存过期时间，以避免大量请求同时穿透缓存。

如何解决缓存击穿的问题？

缓存击穿是指针对一个热点数据，缓存失效后，大量请求同时涌入底层数据源，导致数据源压力过大。为了解决缓存击穿问题，可以采取以下措施：

使用互斥锁或分布式锁，使得只有一个请求能够重新生成缓存，其他请求等待缓存生成完成；
使用热点数据预加载，提前生成热点数据的缓存，避免缓存失效时的高并发请求；
设置较短的缓存过期时间，并采用异步更新缓存的方式，减少缓存失效的影响。

如何解决缓存雪崩的问题？

缓存雪崩是指在某个时间点，缓存中的大量数据同时失效或过期，导致大量的请求直接访问后端系统，造成后端系统负载剧增，甚至引起系统崩溃。

解决缓存雪崩问题通常采用以下策略：

合理设置缓存过期时间：通过合理设置缓存数据的过期时间，避免大量缓存同时失效。可以采用随机的方式设置过期时间，分散缓存的失效时间点，减少雪崩的风险。
引入缓存数据的自动刷新机制：在缓存数据过期之前，提前异步刷新缓存数据。当缓存数据过期时，仍然可以提供旧数据，同时异步更新新数据到缓存中，确保缓存数据的及时有效性。
数据预热：在系统低峰期，提前加载缓存中的热点数据，避免在高峰期由于大量请求直接访问后端系统而引起的缓存雪崩。通过定时或手动方式，提前将热门数据加载到缓存中，确保缓存的有效性。

如何处理缓存数据的一致性问题？

处理缓存数据一致性问题的常见方法包括：

主动刷新（Cache Refresh）：定期或在数据发生变化时，立即刷新缓存中的数据，确保缓存数据与源数据保持一致。
延迟刷新（Lazy Refresh）：当缓存数据被请求时，检查源数据是否发生变化，如果发生变化，则刷新缓存数据。
失效标记（Invalidation）：在源数据发生变化时，通过标记缓存数据为无效状态，下一次请求时重新获取最新数据并更新缓存。
双写策略（Write-through）：每次写操作都更新缓存和源数据，确保数据的一致性。

如何设计一个缓存系统

合适数据结构

常见的缓存数据结构包括哈希表（Hash Table）和双向链表（Doubly Linked List），这两种数据结构通常会结合使用以达到最佳效果。

哈希表（Hash Table）：哈希表提供了平均时间复杂度为O(1)的查找和插入操作
双向链表（Doubly Linked List）：可以方便地维护数据的顺序，这对于实现LRU（最近最少使用）等缓存淘汰策略非常有用。在任意位置的插入和删除的复杂度是O(1)

结合使用哈希表和双向链表

下面就是利用Hash表和双向链表实现的结构类型

查找效率：哈希表提供快速查找，确保我们可以迅速找到缓存中的数据。
顺序管理：双向链表提供有序性，确保我们可以高效地管理数据的访问顺序，从而实现LRU等缓存淘汰策略。

具体实现：

哈希表：存储键值对，键是资源标识符，值是双向链表中的节点指针。
双向链表：维护数据的访问顺序，每个节点包含资源标识符、资源数据和前后节点的指针。

下面来看一下具体操作过程

查找：
- 通过哈希表快速查找资源标识符对应的节点。
- 如果找到，返回节点中的数据，并将该节点移动到链表尾部（表示最近被访问）。
插入：
- 如果缓存未满，直接在链表尾部插入新节点，并更新哈希表。
- 如果缓存已满，移除链表头部的节点（最久未使用的数据），然后在链表尾部插入新节点，并更新哈希表。
删除：
- 从哈希表中删除对应的键值对。
- 从双向链表中移除对应的节点。

缓存替换策略

LRU（最近最少使用）：
- 工作原理：淘汰最久未被访问的数据。
- 优点：简单易实现，适合大部分场景。
- 缺点：可能误删热点数据。
LFU（最不经常使用）：
- 工作原理：淘汰访问次数最少的数据。
- 优点：更适合访问频率差异大的场景。
- 缺点：需要额外空间来维护访问频率。
W-TinyLFU：
- 工作原理：结合时间窗口内的访问频率来决定淘汰策略。
- 优点：适应性强，能处理热点数据的变化。
- 缺点：实现复杂度较高。

数据一致性的Trade Off

可以这么说，只要在系统中使用了缓存就一定会有数据一致性的问题，但是利用缓存都就必须选择使用强一致性或者弱一致性

强一致性

CAP理论为数据的强一致性奠定了理论基础，但是CAP理论下的数据强一致性，很难做到既保证系统高性能的同时，又要保证数据的绝对一致。

例如，假设用户在抢购秒杀商品中，缓存中存在商品库存，通过了缓存中的校验逻辑。在真正下单时，还要校验数据库中的商品库存，如果此时数据库中已经没有商品剩余库存了，则终止下单逻辑，提示用户商品已售罄。

弱一致性

也就是说，在很小的一段时间内，允许缓存中的数据存在延迟，允许缓存中的数据与数据库中的数据在短时间内的不一致，只要在可接受的时间范围内最终达到一致即可。

充分发挥缓存的实际作用，即：缓存数据，提供系统的读写性能和抗系统流量。

如何做抉择呢？

可以从以下四点来分析：

业务需求：
- 数据敏感性：对于金融交易、支付系统等对数据一致性要求极高的场景，应选择强一致性。
- 用户体验：对于社交网络、新闻网站等对数据一致性要求相对较低的场景，可以选择弱一致性或最终一致性。
系统性能：
- 读写比：如果读操作远多于写操作，可以选择弱一致性或最终一致性，以提高性能。
- 延迟容忍度：如果系统能够容忍一定的延迟，可以选择最终一致性；如果不能容忍延迟，应选择强一致性。
技术实现：
- 复杂度：强一致性实现复杂，需要更多的同步机制和复杂的算法。弱一致性和最终一致性实现相对简单。
- 维护成本：强一致性系统维护成本高，需要更多的监控和故障处理机制。
数据更新频率：
- 低频更新：如果数据更新频率较低，可以选择强一致性，因为同步开销较小。
- 高频更新：如果数据更新频率较高，应选择弱一致性或最终一致性，以避免频繁的同步操作。

并发性能优化

在讨论缓存系统的并发性时，我们经常会遇到经典的“读写器问题”。想象一下，多个用户同时访问或更新同一个缓存条目，就像在派对上大家都想抢最后一块蛋糕一样。如果两个客户端同时尝试更新同一个缓存槽，最终只有一个客户端的更新会被保留，而另一个客户端的更新则会丢失。这种情况下，数据的一致性和准确性就会受到影响。

常见的解决方案包括：

使用锁（Locks）

优点：简单易实现，确保了数据的一致性。
缺点：性能瓶颈明显。当多个客户端同时请求同一资源时，其他客户端必须等待，这会导致响应时间变长，系统吞吐量下降。

分片加锁（Sharded Locks）

方法：将缓存分成多个分片，每个分片都有自己的锁。这样，不同分片之间的操作不会相互干扰。
优点：减少了锁的竞争，提高了并发性能。
缺点：热门数据可能会集中在某些分片上，导致这些分片的锁竞争仍然很激烈。此外，分片的设计和管理也增加了复杂性。

提交日志（Write-Ahead Logging, WAL）

方法：将所有更新操作先记录到一个日志中，而不是直接更新缓存。然后，后台进程异步地处理这些日志中的更新操作。
优点：减少了即时冲突，提高了系统的响应速度。即使某个更新操作失败，也可以通过日志进行恢复。
缺点：增加了额外的存储开销，并且需要处理日志的持久化和恢复机制。

定期备份：将缓存数据定期备份到持久化存储（如硬盘或远程存储）。
快速恢复：在缓存服务器启动时，从备份中加载数据。

风趣解释：想象一下，你有一台超级棒的冰箱，里面装满了各种美味的食物。但是，如果有一天冰箱突然坏了，所有的食物都变质了，你会怎么办？你需要一个“冰箱保险”计划！

定期备份：这就像是给你的冰箱拍照留念。每隔一段时间，你就把冰箱里的所有食物拍下来，这样即使冰箱坏了，你也可以根据照片重新购买同样的食物。
快速恢复：当冰箱修好后，你可以根据之前的照片迅速补货，让冰箱再次充满美食。这样，即使冰箱出了问题，你也不会饿肚子。

2. 冗余设计

方法：

多副本：在多个节点上复制缓存数据。
故障转移：当某个缓存节点宕机时，自动切换到备用节点。

风趣解释：再想象一下，你有两台冰箱，一台放在厨房，另一台放在地下室。这样，即使厨房的冰箱坏了，地下室的冰箱也能继续为你提供食物。

多副本：这就像是在不同的地方放置多台冰箱。即使某一台出了问题，还有备用的冰箱可以使用。这样一来，你永远不会因为一台冰箱坏了而挨饿。
故障转移：假设厨房的冰箱坏了，你立即切换到地下室的冰箱，而你根本不知道发生了什么变化。这种无缝切换让你的生活更加顺畅。

3. 一致性哈希

方法：

一致性哈希算法：通过一致性哈希算法将数据均匀分布到多个缓存节点上。

风趣解释：现在，假设你有很多朋友，每个人都想帮你管理一部分食物。为了公平分配任务，你可以使用一种特殊的方法来决定谁负责哪些食物。

一致性哈希：这就像是使用一种魔法算法，把食物均匀地分给每个朋友。这样，即使某个朋友不在，其他朋友也能轻松接管他的任务。这种方法不仅公平，还能确保每个人都能高效地工作。

4. 心跳检测与自动重启

方法：

心跳检测：定期发送心跳信号，检查缓存节点是否正常运行。
自动重启：当检测到缓存节点异常时，自动重启该节点。

风趣解释：最后，我们还需要一个智能的管家，定期检查冰箱的状态，确保它正常工作。

心跳检测：你可以设置一个智能管家，定期检查每台冰箱的状态。如果发现某台冰箱有问题，立即通知维修人员进行修复。这样，你可以及时发现并解决问题，避免更大的麻烦。
自动重启：如果冰箱只是暂时出了点小问题，智能管家可以直接重启它，让它恢复正常工作。这就像给冰箱按个重启键，让它重新开始工作，简单又有效。