Gre*_*reg 117 algorithm caching cache-invalidation generalization
"计算机科学只有两个难题:缓存失效和命名事物."
菲尔卡尔顿
是否存在使缓存无效的通用解决方案或方法; 要知道某个条目何时过时,所以您可以保证始终获得最新数据？
例如,考虑一个getData()从文件中获取数据的函数.它根据文件的最后修改时间对其进行缓存,每次调用时都会检查该文件.
然后添加第二个函数transformData()来转换数据,并在下次调用函数时缓存其结果.它不知道该文件 - 如何添加依赖关系,如果文件被更改,此缓存将变为无效？
您可以在getData()每次调用时transformData()调用它并将其与用于构建缓存的值进行比较,但这可能最终成本非常高.
Shu*_*oUk 55
你所谈论的是终身依赖链,有一件事依赖于另一件可以在其控制范围之外修改的东西.
如果你有一个幂函数,从a,b到c那里,如果a和b相同,则c是相同的,但检查的成本b是高的,那么你可以:
bb尽可能快地进行检查你不能吃蛋糕吃它...
如果您可以基于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(endCache [a] 过期或不存在)
The*_*Dag 15
缓存失效的问题是,在我们不知道的情况下,东西会发生变化.因此,在某些情况下,如果有其他事情可以了解并可以通知我们,则可以采用解决方案.在给定的示例中,getData函数可以挂接到文件系统,该文件系统确实知道对文件的所有更改,而不管文件的进程是什么,并且该组件反过来可以通知转换数据的组件.
我不认为有任何一般的魔法修复可以解决问题.但在许多实际情况中,很可能有机会将基于"轮询"的方法转换为基于"中断"的方法,这可能会使问题彻底消失.
恕我直言，函数反应式编程（FRP）在某种意义上是解决缓存失效的通用方法。
原因如下：FRP 术语中的陈旧数据称为故障。FRP 的目标之一是保证不出现故障。
FRP 在“FRP 的本质”演讲和SO 答案中进行了更详细的解释。
在演讲中， sCell表示缓存的对象/实体，并且Cell如果刷新其中一个依赖项，则刷新 a 。
FRP 隐藏与依赖图关联的管道代码，并确保不存在过时的Cell代码。
我能想到的另一种方法（与 FRP 不同）是将计算值（类型b）包装到某种编写器 Monad 中Writer (Set (uuid)) b，其中Set (uuid)（Haskell 表示法）包含计算值所依赖的可变值的所有标识符b。因此，uuid它是某种唯一标识符，用于标识计算所b依赖的可变值/变量（例如数据库中的一行）。
将这个想法与在这种编写器 Monad 上运行的组合器结合起来，如果您只使用这些组合器来计算新的b. 此类组合器（例如 的特殊版本filter）将 Writer monad 和(uuid, a)-s 作为输入，其中a是可变数据/变量，由 标识uuid。
因此，每次更改类型的计算值所依赖的“原始”数据(uuid, a)（例如数据库中b计算的标准化数据）时，如果您改变计算值所依赖的任何值，b则可以使包含的缓存无效，因为根据Writer Monad 中的 ，您可以知道何时发生这种情况。babSet (uuid)
因此，每当您使用给定的 进行变异时uuid，您都会将此变异广播到所有缓存，并且它们会使b依赖于 said 标识的可变值的值无效uuid，因为包装 的 Writer monadb可以判断它是否b依赖于 saiduuid或不是。
当然，只有当你阅读的次数多于写作的次数时，这才会有回报。
第三种实用方法是在数据库中使用物化视图并将它们用作缓存。据我所知，他们还旨在解决无效问题。这当然限制了将可变数据连接到派生数据的操作。