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

小开

也许缓存无关算法将是最通用的(或者至少，不太依赖硬件配置) ，因为它们将首先使用最快的缓存，然后继续前进。这是麻省理工学院的课程: 缓存遗忘算法

小开

我正在研究一种基于 PostSharp和记忆功能的方法。我和我的导师讨论过了，他也认为这是一个很好的内容不可知的缓存实现。

每个函数都可以标记一个指定其有效期的属性。以这种方式标记的每个函数都被制表，并将结果存储到缓存中，其中使用函数调用的散列和参数作为键。我在后端使用速度，它处理缓存数据的分布。

小开

是否有创建缓存的通用解决方案或方法，以了解条目何时过时，从而确保始终获得新数据？

不，因为所有的数据都是不同的。一些数据可能在一分钟之后“过时”，一些在一小时之后“过时”，一些可能在几天或几个月内都没有问题。

关于您的特定示例，最简单的解决方案是为文件提供一个“缓存检查”函数，您可以从 getData和 transformData调用该函数。

小开

如果每次执行转换时都要使用 getData () ，那么就消除了缓存的全部好处。

对于您的例子来说，一个解决方案似乎是当您生成转换后的数据时，同时存储文件名和生成数据的文件的最后修改时间(您已经将其存储在 getData ()返回的任何数据结构中，所以您只需将该记录复制到 formData ()返回的数据结构中) ，然后当您再次调用 formData ()时，检查文件的最后修改时间。

小开

最佳答案

您所谈论的是生存期依赖链，即一件事物依赖于另一件事物，而另一件事物可以在其控制范围之外进行修改。

如果你有一个从 a，b到 c的幂等函数，如果 a和 b是相同的，那么 c是相同的，但是检查 b的成本很高，那么你可以:

接受你有时操作与过时的信息，并不总是检查 b
尽你最大的努力使检查 b尽快

你不能一边吃蛋糕一边..。

如果您可以在顶部基于 a分层一个额外的缓存，那么这将不会影响最初的问题。如果您选择了1，那么您就拥有了您给自己的任何自由，因此可以缓存更多内容，但是必须记住考虑 b缓存值的有效性。如果您选择了2，那么您必须每次都检查 b，但是如果 b检查完毕，则可以回到缓存中检查 a。

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

如果你知道 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: b和 x: a的 a: b关系，那么连续的分层(比如说 x)就是微不足道的。

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

如果(endCache [ a ] 过期或不存在)

小开

缓存失效的问题在于，在我们不知道的情况下，事情发生了变化。所以，在某些情况下，如果有其他的东西确实知道并且能够通知我们，那么解决方案是可能的。在给定的示例中，getData 函数可以挂接到文件系统，该文件系统确实知道对文件的所有更改，无论什么进程更改文件，而且该组件反过来可以通知转换数据的组件。

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

小开

目前没有普遍的解决办法，但:

缓存可以充当代理(拉)。假设您的缓存知道上次更改的时间戳，当有人调用 getData()时，缓存会询问上次更改的时间戳的原点，如果相同，它返回缓存，否则它会用源更新其内容并返回其内容。(变体是客户端直接发送请求的时间戳，源只有在时间戳不同的情况下才返回内容。)
您仍然可以使用通知过程(推) ，缓存观察源，如果源发生变化，它发送一个通知到缓存，然后标记为“脏”。如果有人调用 getData()，缓存将首先更新到源，删除“脏”标志; 然后返回其内容。

一般来说，选择取决于:

频率: 对 getData()的许多调用都希望使用推送，以避免源代码被 getTimestamp 函数淹没
您对源代码的访问: 您是否拥有源代码模型？如果没有，则可能无法添加任何通知进程。

注意: 由于使用时间戳是 http 代理工作的传统方式，另一种方法是共享存储的内容的散列。我所知道的两个实体一起更新的唯一方法是，要么我叫你(拉) ，要么你叫我... (推)就这样。

小开

从某种意义上说，函数式反应型编程是解决缓存失效问题的一种通用方法。

原因如下: 在 FRP 术语中，陈旧的数据称为故障。玻璃钢的目标之一是保证没有故障。

FRP 在本 “玻璃钢的精髓”谈话和本回答我中有更详细的解释。

在谈谈中，Cell表示一个缓存的 Object/Entity，如果一个 Cell的依赖项被刷新，它就会被刷新。

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

我能想到的另一种方法(不同于 FRP)是将计算值(类型为 b)封装到某种类型的编写器 Monad Writer (Set (uuid)) b中，其中 Set (uuid)(Haskell 表示法)包含计算值 b所依赖的可变值的所有标识符。因此，uuid是某种唯一标识符，它标识计算出的 b所依赖的可变值/变量(比如数据库中的一行)。

将这种思想与在这种类型的编写器 Monad 上运行的组合器结合起来，如果只使用这些组合器计算新的 b，可能会导致某种通用的缓存失效解决方案。这样的组合子(比如 filter的一个特殊版本)以 Writer 单子和 (uuid, a)-s 作为输入，其中 a是由 uuid标识的可变数据/变量。

因此，每次你更改 b类型的计算值所依赖的“原始”数据 (uuid, a)(比如说计算 b的数据库中的标准化数据)时，如果你更改任何 a值所依赖的 b值，那么你可以使包含 b的缓存失效，因为基于 Writer Monad 中的 Set (uuid)，你可以知道这种情况何时发生。

所以任何时候你用一个给定的 uuid变异一些东西，你广播这个变异到所有的缓存-s 和他们失效的值 b取决于可变的值确定与所述 uuid，因为编写单子，其中的 b包装可以告诉如果 b依赖于所述 uuid或不。

当然，只有当你阅读的次数比写作的次数多得多时，这才会有回报。

第三种实用的方法是在数据库中使用物化视图，并将它们用作缓存。AFAIK 也致力于解决失效问题。这当然限制了将可变数据连接到派生数据的操作。

小开

缓存是困难的，因为你需要考虑: 1)缓存是多个节点，需要对它们进行一致性处理 2)失效时间 3)多个 get/set 发生时的竞态条件