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

Question

“计算机科学中只有两个难题：缓存失效和命名。”

菲尔·卡尔顿

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

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

你可以打电话 getData() 每次 transformData() 被调用并将其与用于构建缓存的值进行比较，但这最终可能会非常昂贵。

Answer 1

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

如果你有一个幂等函数 a, b 到 c 哪里，如果 a 和 b 那么是一样的 c 是一样的，但是检查的费用 b 是高那么你要么：

1. 接受您有时会使用过时的信息进行操作，并且并不总是检查 b
2. 尽你所能进行检查 b 尽可能快

你不能鱼与熊掌兼得……

如果你可以基于 a 如果超过了，这就会对最初的问题产生一丁点影响。如果您选择 1，那么您拥有您赋予自己的任何自由，因此可以缓存更多内容，但必须记住考虑缓存值的有效性 b. 。如果您选择 2，您仍必须检查 b 每次但都可以依靠缓存 a 如果 b 退房。

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

如果你知道的话 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 (结束缓存[a] 过期或 不存在）

Answer 2

在缓存失效的问题是没有我们知道关于它的东西改变。因此，在某些情况下，一个解决方案是可能的，如果有，它了解它，可以通知我们一些其他的事情。在给出的示例中，函数的getData可以挂接到文件系统，它不知道所有文件的更改，无论使用什么过程改变了文件，并反过来这个组件可以通知转换数据的组件。

我不认为有任何变魔术一般修复，使问题消失。但是，在许多实际情况有很可能是来变换“轮询”为基础的做法的机会为“中断”为基础的一个，它可以使这个问题简单地去了。

Answer 3

如果你要的getData（）每次你的变换时间，那么你已经消除了缓存的全部好处。

有关你的榜样，它似乎是一个解决办法是，当你生成变换的数据，也存储从生成的数据文件的文件名和最后修改时间（你已经存储在这个在返回的任何数据结构通过的getData（），所以你只要复制记录到由transformData（）返回的数据结构），然后当你调用transformData（）再次，检查文件的最后修改时间。

Answer 4

IMHO，官能的反应性编程（FRP）在某种意义上是解决高速缓存无效的一般方法。

下面是为什么：在FRP术语陈旧数据称为毛刺。之一的FRP的目标是保证不存在毛刺。

FRP中更详细在此“本质FRP的”谈话解释和在此 SO回答。

在谈话中Cells代表一个缓存的对象/实体与Cell是如果更新它的一个依赖被刷新。

FRP隐藏与所述依赖图相关联的管道代码，并确保没有陈旧Cells。

---

的另一种方式（由FRP不同），我可以想到的是包装（类型b）所计算的值变成某种作家单子Writer (Set (uuid)) b的其中Set (uuid)（Haskell的符号）包含可变值的所有的标识符在其上计算值b取决于。所以，uuid是某种的唯一标识符的标识可变值/变量（比如在数据库中的行），其上所计算的b依赖

联合这个想法与对这类作家单子运行，并可能导致某种通用缓存失效的解决方案，如果你只使用这些组合子来计算新b组合程序。这种组合子（说filter的一个特殊版本）取作家单子和(uuid, a)-S作为输入，其中a是一个可变数据/变量，通过uuid识别。

所以每次你改变“原始”数据(uuid, a)（说从中b被计算数据库的归一化数据）那种类型的b的计算值取决于然后您可以作废包含b如果发生变异的任何缓存在其上计算a值取决于值b，因为基于作家的Set (uuid)单子就可以发生这种情况时说。

所以，任何时候你变异与给定uuid的东西，你的广播这种突变的所有缓存-S和它们无效值b依赖于与所述uuid确定的可变值，因为作家单子其中b包裹可以告诉如果b取决于所述uuid与否。

当然，这只是如果你读得多往往比你写的回报。

---

一个第三，实用，方法是使用在数据库中物化视图-S，并用它们作为高速缓存-ES。据我所知，他们还旨在解决了失效问题。当然，这限制了可变数据连接到所得到的数据的操作。

Answer 5

我现在正在研究一种基于 后锐利 和 记忆功能. 。我已经把它交给了我的导师，他也同意这是一种与内容无关的缓存的良好实现。

每个函数都可以用指定其有效期的属性来标记。以这种方式标记的每个函数都会被记忆，并将结果存储到缓存中，并以函数调用和参数的哈希值作为键。我在用着 速度 对于后端，它处理缓存数据的分配。

Answer 6

  

有没有通用的解决方案或方法来创建一个高速缓存，要知道当一个项目已过期，所以你保证总能获得最新的数据？

没有，因为所有的数据是不同的。一些数据可能是“陈旧的”一分钟后，一些一小时后，有的可能数天或数个月的被罚款。

关于你提到的具体的例子，最简单的办法是有一个“高速缓存器确认”的文件，你从两个getData和transformData通话功能。

Answer 7

没有通用的解决方案，但是：

• 您的缓存可以充当代理（拉）。假设您的缓存知道最后一次源更改的时间戳，当有人调用时 getData(), ，缓存向源询问其最后一次更改的时间戳，如果相同，则返回缓存，否则使用源更新其内容并返回其内容。（一种变体是客户端直接发送请求的时间戳，源仅在时间戳不同时才返回内容。）

• 您仍然可以使用通知过程（推送），缓存观察源，如果源发生变化，它会向缓存发送通知，然后将其标记为“脏”。如果有人打电话 getData() 缓存将首先更新到源，删除“脏”标志；然后返回其内容。

一般来说，选择取决于：

• 频率：许多电话 getData() 更喜欢推送，以避免源被 getTimestamp 函数淹没
• 您对来源的访问：您拥有源模型吗？如果没有，您很可能无法添加任何通知流程。

笔记：由于使用时间戳是 http 代理的传统工作方式，因此另一种方法是共享存储内容的哈希值。我知道两个实体一起更新的唯一方法是我打电话给你（拉）或者你打电话给我......（推）仅此而已。

Answer 8

因为你需要考虑的缓存是硬盘： 1）高速缓存是多个节点，需要对他们的共识 2）无效时间 3）竞争条件时multple获取/设置发生

这是良好的阅读： https://www.confluent.io /博客/转弯的-数据库内向外与 - Apache的samza /

Answer 9

也许缓存不经意算法将是最一般的（或者至少，硬件配置较少依赖），因为它们将首先使用最快的高速缓存，并从那里继续前进。这里就可以了麻省理工学院的演讲：缓存不经意算法