python - 使用 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以Key-Value形式存储在RAM中
• Hashmap将被备份(每隔一段时间序列化到一个文件)

我正在尝试为 URL 缩短器制作此缓存，但想将其扩展为一个完整的缓存服务器。我面临的问题是:

• 我将如何确定要存储的键值对的数量？
• 如果数据库中的值发生变化，我是否必须删除处理它的 Query(Key)？

我该如何解决？

Answer 1

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

How will I determine the number of Key-Value Pairs to be stored?

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

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

If the value in DB is changed, will I have to remove the Query(Key) that deals with it?

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