使用LFU设计缓存服务器以减少数据库负载

Question

我正在尝试设计一个缓存服务器，它将存储数据库查询的查询和结果键，从而减少负载。 它可能是这样的：

if Cache.isSet(query):
       return Cache.get(query)
else:
       result = db.run(query)
       Cache.set(query, result)
       return result

我计划设计的Cache的属性：

• 将是一个使用REST API的缓存服务器
• 将使用Hashmap以密钥值形式存储在RAM中
• 将备份Hashmap（每隔一段时间序列化到一个文件）

我正在尝试为URL Shortener创建此缓存，但希望将其扩展为完整的缓存服务器。我面临的问题是：

• 如何确定要存储的键值对的数量？
• 如果更改了DB中的值，我是否必须删除处理它的查询（密钥）？

我该如何解决这个问题？

Answer 1

Redis的开发人员在Random notes on improving the Redis LRU algorithm上有一篇很好的文章，也涵盖了LFU的实现。 LRU算法的主要思想是在访问时用时间戳标记对象。如果内存不足，请选择五个随机密钥并逐出具有最旧时间戳的密钥。这是一种eventual concistency方法，在这种方法中，您将无法找到驱逐的最佳关键，但您将在宏观层面上使数据集更好，更好。主要好处是每个对象都有自己的状态，您不需要维护复杂的优先级列表来跟踪要驱逐的内容。该文档后来建立在LRU的基础上，但也展示了如何在没有太多工作的情况下将其转换为LFU算法。

如何确定要存储的键值对的数量？

尽可能多地使用内存。无限RAM的最佳情况是缓存整个数据集。使用受限制的RAM，您必须查看您的访问模式。是否有大部分时间要求的“热”对象的小核心？然后确保尽可能多的缓存。

我怀疑你可能会遇到一个URL缩短程序的问题是你会有很长的URL。也就是说，旧的URL很少访问每个URL，但这些URL的数量太大，以至于它们共同构成了数据库负载的很大一部分。如果是这种情况，您可能需要考虑适合整个数据集的缓存或某种加速数据库查询的方法。长尾与热对象的不同之处在于长尾对象的访问频率很低，以至于它们在每次访问之间被从缓存中逐出。没有适合长尾的缓存驱逐算法;您可以缓存整个长尾，也可以专注于加速原始未缓存访问。

如果更改了DB中的值，我是否必须删除处理它的查询（密钥）？

是的，或者更新缓存。如果您的系统逻辑可以接受一些延迟，您可以使用密钥上的生存时间。然后你驱逐超过x秒的密钥。回顾Redis，他们通过查看您尝试读取密钥时的时间戳来处理这个问题。如果生存时间已过期，则删除密钥并返回缓存未命中。