面试题：缓存设计之边缘计算场景缓存部署基础

Question

在边缘计算场景中，假设你要设计一个简单的缓存系统来存储用户请求频繁的静态文件，简要描述你会如何选择缓存的数据结构以及原因，并且说明怎样处理缓存的过期策略。

Answer 1

缓存数据结构选择及原因

1. 哈希表（如 Python 中的字典）
   • 原因：哈希表具有非常高的查找效率，时间复杂度接近 O(1)。在边缘计算场景下，对于频繁请求的静态文件，快速查找缓存中的文件至关重要。通过将文件的唯一标识（如文件路径或 URL）作为键，文件内容或文件的相关元数据作为值存储在哈希表中，可以快速判断文件是否已在缓存中，并获取相应的数据。
2. 双向链表
   • 原因：结合哈希表使用双向链表可以实现 LRU（最近最少使用）缓存策略。双向链表可以有效地管理缓存的顺序，新访问的节点移到链表头部，当缓存满时，从链表尾部移除节点。这样可以保证经常被访问的文件始终留在缓存中，而长时间未被访问的文件被淘汰。

缓存过期策略处理

1. 时间戳过期策略
   • 实现方式：在缓存数据结构中，为每个缓存项添加一个时间戳字段。当缓存项被插入时，记录当前时间。每次访问缓存项时，检查当前时间与时间戳的差值是否超过设定的过期时间。如果超过，则认为该缓存项过期，从缓存中移除。
   • 优点：实现简单，易于理解和维护。
   • 缺点：需要每次访问都进行时间检查，增加了一定的开销。
2. 惰性删除和定期删除结合
   • 惰性删除：在每次获取缓存项时检查其是否过期，如果过期则删除。这样可以避免在缓存项未被访问时不必要的删除操作。
   • 定期删除：每隔一段时间（如每隔几分钟）遍历缓存，删除所有过期的缓存项。这可以防止长时间未被访问但已过期的缓存项占用过多内存。通过这种结合方式，可以在性能和内存管理之间找到较好的平衡。