logo标签列表

缓存失效 - 是否存在通用解决方案？

algorithmcachinggeneralizationcache-invalidation
133
“在计算机科学中，只有两个难题:缓存失效和命名事物。”
Phil Karlton
是否有一种通用的解决方案或方法来使缓存失效；以便知道何时条目过期，从而保证始终获得新鲜数据？
例如，考虑一个函数`getData()`，它从文件获取数据并基于文件的上次修改时间将其缓存，每次调用该函数时都会检查这个时间。然后您添加第二个函数`transformData()`，它转换数据，并缓存其结果以供下次调用该函数使用。它不知道文件-如何添加此依赖关系，如果文件发生更改，则此缓存变为无效？
您可以每次调用`transformData()`时调用`getData()`并将其与用于构建缓存的值进行比较，但这可能非常昂贵。
6
我相信他与编写 X Window 有关。 - Greg
1
我认为标题改为“缓存失效 - 是否存在通用解决方案？”会更好，因为它涉及到一类特定的缓存问题。 - RBarryYoung
73
不，他并不懂很多计算机科学。我确信他参与创建OpenGL、X11和SSLv3使得他太忙了，没有真正花时间去学习它。 :-) - Tim Lesher
83
计算机科学中只有两个难点：缓存失效、命名规则和差一错误。 - The Dag
9
我曾听过这样的说法："计算机科学中最困难的两件事是缓存失效、命名事物和 off-by-one 错误。" - Jonathon Reinhart
是的，我们添加了一个新的:D https://twitter.com/julia_asterisk/status/829045121933000708 这发生在2014年之后的某个时候。 - jcolebrand
9个回答
59
你所说的是生命周期依赖链，一个东西依赖于另一个东西，而后者可能会在它的控制范围之外被修改。
如果你有一个幂等函数，从 a, b 映射到 c，其中，如果 a 和 b 相同，则 c 相同，但检查 b 的成本很高，那么你可以选择：
1. 接受你有时候使用过时信息并且不总是检查 b。 2. 尽力使检查 b 尽可能快。
你无法两全其美...
如果你可以在顶部添加一个基于 a 的额外缓存，那么这对最初的问题没有任何影响。如果你选择了 1，那么你就拥有了你给自己的自由，并且可以缓存更多内容，但必须记得考虑 b 的缓存值的有效性。如果你选择了 2，则仍然必须每次检查 b，但如果 b 没问题，就可以退而求其次，使用 a 的缓存。
如果你层叠缓存，你必须考虑是否因为组合行为而违反了系统的“规则”。
如果你知道如果 b 有效，a 总是有效的，那么你可以像这样排列缓存（伪代码）：
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）是微不足道的，只要在每个阶段新添加的输入的有效性匹配 x:b 和 x:a 的 a:b 关系。然而，很可能会出现三个输入其有效性完全独立（或循环），因此不能进行分层。这意味着标记为 // important 的行必须更改为：如果 (endCache[a] 过期或不存在)。
3
如果检查 b 的成本很高，你可以使用发布-订阅模式，使得当 b 发生变化时通知 c。观察者模式很常见。 - user1031420
16

缓存失效的问题在于我们不知道内容发生了改变。因此，在某些情况下，如果有其他东西知道内容发生了改变并能够通知我们，则可能有解决方案。在给定的示例中，getData函数可以连接到文件系统，文件系统知道文件的所有更改，无论哪个进程更改了文件，该组件转而可以通知转换数据的组件。

我不认为有任何通用的魔法方法可以解决这个问题。但在许多实际情况下，很可能可以将“轮询”方法转换为“中断”方法，从而可以简单地解决问题。

6

在我看来，函数响应式编程（FRP）从某种意义上说是解决缓存失效的一般方法。

原因如下：在FRP术语中，过期的数据称为glitch。 FRP的目标之一是保证没有glitches。

FRP在这个'Essence of FRP' talk和这个SO answer中有更详细的解释。

在talk中，Cell代表一个缓存对象/实体，并且如果它的任何一个依赖项被刷新，Cell就会刷新。

FRP隐藏了与依赖图相关的管道代码，并确保没有陈旧的Cell。

另一种我能想到的方法（与FRP不同）是将计算值（类型为b）包装到某种写入器单子Writer(Set(uuid)) b中。其中Set(uuid)（Haskell符号）包含所有可变值的标识符，这些可变值是计算值b所依赖的。因此，uuid是一种唯一标识符，用于标识计算b所依赖的可变值/变量（比如数据库中的一行）。
将此思想与操作该类写入器单子的组合器相结合，如果您仅使用这些组合器计算新的b，那么可能会导致某种通用缓存失效解决方案。这样的组合器（比如filter的特殊版本）接受写入器单子和(uuid, a)作为输入，其中a是由uuid标识的可变数据/变量。
每当更改“原始”数据（uuid，a）（例如从中计算出b的数据库中的归一化数据）时，取决于类型b的计算值，则可以使包含b的缓存无效，如果您改变了计算b值所依赖的任何值a，因为基于Writer Monad中的Set（uuid），您可以知道何时发生这种情况。
因此，每当您更改具有给定uuid的某些内容时，都会将此突变广播到所有缓存，并且它们会使依赖于使用该uuid标识的可变值的值b无效，因为Writer monad包装了b，可以告诉该b是否依赖于该uuid。
当然，只有在读取远远超过写入时才能实现这一点。
第三种实用方法是在数据库中使用物化视图，并将其用作缓存。据我所知，它们也旨在解决失效问题。当然，这限制了将可变数据连接到派生数据的操作。
2

我目前正在研究一种基于PostSharp和函数备忘录技术的方法。我向我的导师请教过，他同意这是一种在内容无关的情况下实现缓存的好方法。

每个函数都可以用一个属性标记其到期时间。以这种方式标记的每个函数都会被备忘录化，并将结果存储到缓存中，使用函数调用和参数的哈希作为键。我在后端使用Velocity来处理缓存数据的分布。

2
如果每次进行转换时都要调用getData()，那么你就消除了缓存的全部好处。
对于你的例子，一个解决方案似乎是在生成转换数据时，同时存储生成数据所使用的文件名和最后修改时间（你已经在getData()返回的数据结构中存储了这些信息，因此只需将该记录复制到transformData()返回的数据结构中），然后再次调用transformData()时，检查文件的最后修改时间。
1

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

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

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

一般而言，选择取决于：

  • 频率：对于许多对 getData() 的调用，推送可能更好，以避免源被 getTimestamp 函数淹没。
  • 您对源的访问：您是否拥有源模型？如果没有，您很可能无法添加任何通知过程。
注意：由于时间戳是http代理工作的传统方式，另一种方法是共享存储内容的哈希值。我知道两个实体同时更新的唯一方法是我打电话给你（拉）或者你打电话给我（推），就这样。
1
有没有一般的解决方案或方法来创建缓存，以知道何时条目已过期，从而保证始终获取新鲜数据？
不，因为所有数据都是不同的。有些数据可能在一分钟后就会“过期”，有些则需要一个小时，还有一些可能可以保持数天或数月。
关于您的具体示例，最简单的解决方案是为文件设置一个“缓存检查”函数，您可以从getData和transformData中调用它。
0
-2

也许缓存无感知算法是最通用的（或者至少不太依赖硬件配置），因为它们会首先使用最快的缓存，然后继续执行。这里有一篇麻省理工学院关于此的讲座：缓存无感知算法

3
我认为他所说的并不是硬件缓存，而是他的getData()代码具有一个将从文件中获取的数据“缓存在内存中”的功能。 - Alex319
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接