algorithm - 缓存失效——有通用的解决方案吗？

Question

"There are only two hard problems in Computer Science: cache invalidation and naming things."

菲尔·卡尔顿

是否有使缓存失效的通用解决方案或方法？了解条目何时过时，以便保证始终获得最新数据？

例如，考虑一个从文件中获取数据的函数 getData()。它根据文件的最后修改时间缓存它，每次调用时都会检查它。
然后添加第二个函数 transformData() 来转换数据，并在下次调用该函数时缓存其结果。它不知道该文件 - 如何添加依赖项，如果文件发生更改，此缓存将失效？

您可以在每次调用 transformData() 时调用 getData() 并将其与用于构建缓存的值进行比较，但这最终可能是非常昂贵。

Answer 1

你说的是生命周期依赖链，一件事依赖于另一件事，而另一件事可以在它的控制之外进行修改。

如果你有来自 a 的幂等函数, b至 c其中，如果 a和 b那么c是一样的是一样的但是检查的成本b是高那么你要么:

1. 承认您有时会使用过时的信息进行操作并且并不总是检查 b
2. 尽力检查b尽快

你不能吃你的蛋糕......

如果您可以根据 a 分层附加缓存最重要的是，这不会影响最初的问题。如果您选择 1，那么您将拥有给自己的任何自由，因此可以缓存更多内容，但必须记住要考虑 b 的缓存值的有效性。 .如果您选择 2，您仍然必须检查 b每次都可以回退到缓存 a如果b checkout 。

如果您对缓存进行分层，您必须考虑是否由于组合行为而违反了系统的“规则”。

如果你知道a如果 b 始终有效那么你可以像这样安排你的缓存(伪代码):

private map<b,map<a,c>> cache // 
private func realFunction    // (a,b) -> c

get(a, b) 
{
    c result;
    map<a,c> endCache;
    if (cache[b] expired or not present)
    {
        remove all b -> * entries in cache;   
        endCache = new map<a,c>();      
        add to cache b -> endCache;
    }
    else
    {
        endCache = cache[b];     
    }
    if (endCache[a] not present)     // important line
    {
        result = realFunction(a,b); 
        endCache[a] = result;
    }
    else   
    {
        result = endCache[a];
    }
    return result;
}

显然，连续分层(比如 x)是微不足道的，只要在每个阶段新添加的输入的有效性与 a 相匹配即可。 : b x 的关系: b和 x : a .

然而，您很有可能获得三个输入，其有效性完全独立(或循环)，因此不可能分层。这意味着标记为//important 的行必须更改为

if (endCache[a] expired or not present)