130

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

菲尔·卡尔顿

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

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

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

4

9 回答 9

57

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

如果你有一个幂等函数 from a, bto cwhere, if aand bare the same thenc是相同的，但检查的成本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关系匹配。xbxa

但是，您很可能会得到三个有效性完全独立（或循环）的输入，因此不可能进行分层。这意味着标记为 // 重要的行必须更改为

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

于 2009-07-27T15:07:06.333 回答
16

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

我认为没有任何通用的魔法解决方法可以让问题消失。但是在许多实际情况下，很可能有机会将基于“轮询”的方法转变为基于“中断”的方法，这可以使问题简单地消失。

于 2011-02-28T16:50:40.800 回答
4

恕我直言，功能响应式编程（FRP）在某种意义上是解决缓存失效的一般方法。

原因如下：FRP 术语中的陈旧数据称为故障。FRP 的目标之一是保证没有故障。

FRP 在此“FRP 本质”演讲和此SO 答案中进行了更详细的解释。

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

FRP 隐藏了与依赖图关联的管道代码，并确保没有过时Cell的代码。

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

将这个想法与在这种写入器 Monad 上运行的组合器结合起来，如果你只使用这些组合器来计算一个新的b. 此类组合器（例如 的特殊版本filter）将 Writer monad 和(uuid, a)-s 作为输入，其中a是可变数据/变量，由uuid.

因此，每次您更改类型的计算值所依赖的“原始”数据（例如计算出(uuid, a)的数据库中的规范化数据）时，如果您改变计算值所依赖的任何值，则可以使包含的缓存无效，因为根据Writer Monad 中的 ，您可以判断何时发生这种情况。bbbabSet (uuid)

因此，无论何时你用给定的东西改变某些东西uuid，你都会将此突变广播到所有缓存，它们会使b依赖于用 said 标识的可变值的值无效，uuid因为包装在其中的 Writer monadb可以判断这b是否取决于 saiduuid或不是。

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

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

于 2016-08-11T07:29:23.397 回答
3

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

对于您的示例，似乎一个解决方案是在您生成转换后的数据时，还存储生成数据的文件的文件名和上次修改时间（您已经将其存储在 getData( )，因此您只需将该记录复制到 transformData()) 返回的数据结构中，然后当您再次调用 transformData() 时，检查文件的最后修改时间。

于 2009-07-27T15:00:56.810 回答
2

我现在正在研究一种基于PostSharp和记忆功能的方法。我已经通过我的导师运行它，他同意这是一种以与内容无关的方式实现缓存的好方法。

每个函数都可以用一个属性来标记，该属性指定它的有效期。以这种方式标记的每个函数都被记忆并将结果存储到缓存中，函数调用的哈希和用作键的参数。我在后端使用Velocity，它处理缓存数据的分发。

于 2009-07-27T14:54:29.957 回答
1

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

不，因为所有数据都不同。有些数据可能在一分钟后“陈旧”，有些在一小时后可能会“陈旧”，而有些数据可能会在几天或几个月内完好无损。

关于您的具体示例，最简单的解决方案是为文件提供“缓存检查”功能，您可以从getData和transformData.

于 2009-07-27T14:59:13.007 回答
1

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

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

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

一般来说，选择取决于：

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

注意：由于使用时间戳是 http 代理的传统工作方式，另一种方法是共享存储内容的哈希值。我知道 2 个实体一起更新的唯一方法是我叫你（拉）或你叫我……（推）就是这样。

于 2015-06-22T13:15:24.420 回答
0

缓存很难，因为您需要考虑：1）缓存是多个节点，需要对它们达成共识 2）失效时间 3）发生多次获取/设置时的竞争条件

this is good reading: https://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/

于 2018-05-14T03:58:47.120 回答
-2

也许缓存遗忘算法将是最通用的（或者至少，较少依赖硬件配置），因为它们将首先使用最快的缓存并从那里继续。这是关于它的 MIT 讲座：Cache Oblivious Algorithms

于 2009-07-27T14:50:19.043 回答