BLOG

缓存语言模型是一种统计语言模型。这些发生在计算机科学的自然语言处理子领域，并通过概率分布将概率分配给给定的单词序列。统计语言模型是语音识别系统和许多机器翻译系统的关键组成部分：它们告诉这些系统哪些可能的输出单词序列是可能的，哪些是不可能的。缓存语言模型的特殊特征是它包含一个缓存组件，并为给定文本中其他地方出现的单词或单词序列分配相对较高的概率。缓存语言模型的主要（但绝不是唯一）使用是在语音识别系统中。

为了理解为什么统计语言模型包含缓存组件是一个好主意，可以考虑有人向语音识别系统口述关于大象的字母。标准（非缓存）N-gram语言模型将为单词“elephant”分配非常低的概率，因为它在英语中是一个非常罕见的单词。如果语音识别系统不包含缓存组件，则口述字母的人可能会感到恼火：每次说出“大象”一词时，可以根据N-gram语言模型识别出另一个概率更高的单词序列（例如，“告诉一个计划”）。每次说出“大象”时，必须手动删除这些错误的序列，并在文本中替换为“大象”。如果系统具有缓存语言模型，则“大象”在第一次说出时仍可能被错误识别，并且必须手动输入到文本中;然而，从这一点开始，系统意识到“大象”可能会再次出现——“大象”出现的估计概率增加了，这使得如果说出来，它更有可能被正确识别。一旦“大象”出现多次，系统很可能每次说出来时都能正确识别它，直到字母完全口述。分配给“大象”出现的概率的增加是机器学习结果的一个例子，更具体地说是模式识别的结果。

缓存语言模型存在变体，其中不仅单个单词，而且先前出现的多单词序列都被分配了更高的概率（例如，如果“旧金山”发生在文本开头附近，则后续实例将被分配更高的概率）。

缓存语言模型最初是在1990年发表的一篇论文中提出的，之后IBM语音识别小组对这个概念进行了实验。该小组发现，一旦文档的前几百个单词被口述，实现一种形式的缓存语言模型就会使单词错误率下降24%。对语言建模技术的详细调查得出结论，缓存语言模型是为数不多的对标准 N-gram 方法产生改进的新语言建模技术之一：“我们的缓存结果表明，缓存是迄今为止在中小型训练数据大小下减少困惑的最有用的技术”。

缓存语言模型的开发引起了那些关心计算语言学，特别是统计自然语言处理的人的极大兴趣：最近，人们对在统计机器翻译领域应用缓存语言模型产生了兴趣。

缓存语言模型在改进单词预测方面的成功取决于人类以“突发”方式使用单词的倾向：当一个人在某个上下文中讨论某个主题时，一个人使用某些单词的频率将与在其他上下文中讨论其他主题时的频率大不相同。传统的N-gram语言模型完全依赖于来自要分配概率的单词前面的极少数（四个，三个或两个）单词的信息，不能充分模拟这种“爆发性”。

最近，缓存语言模型概念 - 最初为N-gram统计语言模型范式构思 - 已被调整用于神经范式。例如，最近在递归神经网络（RNN）设置中对连续缓存语言模型的工作已将缓存概念应用于比以前大得多的上下文，从而显着降低了困惑度。最近的另一项研究涉及在前馈神经语言模型（FN-LM）中加入缓存组件以实现快速域适应。

在计算机体系结构中，缓存一致性是最终存储在多个本地缓存中的共享资源数据的一致性。当系统中的客户端维护公共内存资源的缓存时，可能会出现数据不一致的问题，多处理系统 中的CPU尤其如此。

显示某些内存的多个缓存（充当共享资源）的插图

不连贯的缓存：缓存具有单个地址位置的不同值。

在右图中，假设两个客户端都具有上一次读取的特定内存块的缓存副本。假设底部的客户端更新/更改了该内存块，则顶部的客户端可能会留下无效的内存缓存，而不会发出任何更改通知。缓存一致性旨在通过维护多个缓存中数据值的一致视图来管理此类冲突。

相干缓存：所有缓存副本中的值都相同。

一致性定义了读取和写入单个地址位置的行为。[2]

在不同的高速缓存内存中同时出现的一种数据称为高速缓存一致性，或者在某些系统中称为全局内存。

在多处理器系统中，考虑多个处理器缓存了内存位置 X 的副本。以下条件是实现缓存一致性所必需的：[4]

1. 在处理器 P 对位置 X 进行的读取之后，同一处理器 P 对 X 进行写入，并且在 P 进行的写入和读取指令之间没有发生另一个处理器对 X 的写入，X 必须始终返回值P写的
2. 在处理器 P1 对位置 X 的读取之后另一个处理器 P2 对 X 的写入之后，在两次访问之间没有发生任何处理器对 X 的其他写入，并且读取和写入被充分分离，X 必须始终返回 P2 写入的值。这种情况定义了连贯记忆观的概念。将写入传播到共享内存位置可确保所有缓存都具有一致的内存视图。如果处理器 P1 读取 X 的旧值，即使在 P2 写入之后，我们也可以说内存是不连贯的。

上述条件满足高速缓存一致性所需的写入传播标准。但是，它们还不够，因为它们不满足事务序列化条件。为了更好地说明这一点，请考虑以下示例：

多处理器系统由四个处理器组成 - P1、P2、P3 和 P4，所有处理器都包含共享变量S的缓存副本，其初始值为 0。处理器 P1 将S的值（在其缓存副本中）更改为 10，随后处理器 P2 将其缓存副本中S的值更改为 20。如果我们确保只进行写入传播，那么 P3 和 P4 肯定会看到P1 和 P2对S所做的更改。但是，P3 可能会在看到 P2 所做的更改后看到 P1 所做的更改，因此在读取S时返回 10 。另一方面，P4 可能会看到 P1 和 P2 按更改顺序进行的更改，因此在读取S时返回 20. 处理器 P3 和 P4 现在对内存的看法不一致。

因此，为了满足事务序列化，从而实现缓存一致性，必须满足以下条件以及本节中提到的前两个条件：

• 必须对同一位置的写入进行排序。换句话说，如果位置 X 从任意两个处理器按此顺序接收到两个不同的值 A 和 B，则处理器永远不会将位置 X 读取为 B，然后将其读取为 A。位置 X 必须被视为具有值 A 和B 依此顺序。[5]

一致性系统的另一种定义是通过顺序一致性内存模型的定义：“缓存一致性系统必须以尊重每个线程程序顺序的总顺序执行所有线程的加载和存储到单个内存位置” . [3]因此，缓存一致性系统和顺序一致系统之间的唯一区别在于定义所讨论的地址位置的数量（缓存一致性系统的单个内存位置，以及顺序一致系统的所有内存位置）。

另一个定义是：“如果对同一内存位置的所有写入都以某种顺序执行，则多处理器是缓存一致的”。[6]

很少，但特别是在算法中，连贯性可以指代参考的局部性。相同数据的多个副本可以同时存在于不同的缓存中，如果允许处理器自由更新自己的副本，则会导致内存视图不一致。

确保一致性的两种最常见的机制是侦听和基于目录，每种机制都有自己的优点和缺点。如果带宽足够，基于侦听的协议往往会更快可用，因为所有事务都是所有处理器看到的请求/响应。缺点是窥探不可扩展。每个请求都必须广播到系统中的所有节点，这意味着随着系统变大，（逻辑或物理）总线的大小及其提供的带宽也必须增加。另一方面，目录往往有更长的延迟（3 跳请求/转发/响应）但使用更少的带宽，因为消息是点对点的而不是广播的。出于这个原因，许多较大的系统（>64 个处理器）使用这种类型的缓存一致性。

Snooping

侦听于 1983 年首次引入，是一个过程，其中各个缓存监视地址线以访问它们缓存的内存位置。[4]写无效协议和写更新协议利用了这种机制。

对于侦听机制，侦听过滤器通过维护多个条目来减少侦听流量，每个条目代表可能由一个或多个节点拥有的高速缓存行。当需要替换条目之一时，探听过滤器选择替换表示由最少节点拥有的一个或多个高速缓存行的条目，如从每个条目中的存在向量所确定的那样。如果最少的节点拥有多个缓存行，则使用时间算法或其他类型的算法来细化选择。[8]

Directory-based

在基于目录的系统中，被共享的数据被放置在一个公共目录中，该目录保持缓存之间的一致性。该目录充当过滤器，处理器必须通过该过滤器请求许可才能将条目从主内存加载到其缓存中。更改条目时，目录会更新或使包含该条目的其他缓存无效。

分布式共享内存系统模仿这些机制，试图在松耦合系统中保持内存块之间的一致性。[9]

一致性协议在多处理器系统中应用高速缓存一致性。目的是两个客户端绝不能看到相同共享数据的不同值。

该协议必须实现一致性的基本要求。它可以为目标系统或应用程序量身定制。

协议也可以分为 snoopy 或基于目录的。通常，早期系统使用基于目录的协议，其中目录将跟踪共享的数据和共享者。在史努比协议中，事务请求（读取、写入或升级）被发送到所有处理器。所有处理器都会侦听请求并做出适当的响应。

snoopy 协议中的写传播可以通过以下两种方法之一实现：

写无效 Write-invalidate

当观察到对缓存具有副本的位置的写操作时，缓存控制器会使它自己的窥探内存位置的副本无效，这会强制在其下一次访问时从主内存读取新值。[4]

写更新 Write-update

当观察到对缓存具有副本的位置的写操作时，缓存控制器使用新数据更新其自己的窥探内存位置的副本。

如果协议设计声明每当共享数据的任何副本发生更改时，所有其他副本都必须“更新”以反映更改，那么它就是一个写更新协议。如果设计表明任何处理器对缓存副本的写入需要其他处理器丢弃或使它们的缓存副本无效，那么它就是一个写无效协议。

然而，可扩展性是广播协议的一个缺点。

已经设计了各种模型和协议来保持一致性，例如MSI、MESI（又名伊利诺伊州）、MOSI、MOESI、MERSI、MESIF、一次写入、Synapse、Berkeley、Firefly和Dragon 协议。[1] 2011 年，ARM Ltd提出了 AMBA 4 ACE [10]用于处理SoC中的一致性。ARM Ltd的AMBA CHI（相干集线器接口）规范[11]，属于 AMBA5 规范组，定义了用于连接完全一致处理器的接口。

在共享内存多处理器系统中，每个处理器都有一个单独的高速缓存，可以有多个共享数据的副本：一个副本在主内存中，一个在请求它的处理器的本地缓存中。当其中一个数据副本发生更改时，其他副本必须反映该更改。缓存一致性是确保共享操作数（数据）值的变化及时在整个系统中传播的规则。

以下是缓存一致性的要求：

Write Propagation 写入传播

对任何缓存中数据的更改必须传播到对等缓存中的其他副本（该缓存行）。

Transaction Serialization事务序列化

所有处理器必须以相同的顺序查看对单个内存位置的读/写。

从理论上讲，一致性可以在加载/存储粒度上执行。但是，在实践中，它通常是在缓存块的粒度上执行的。

一致性定义了对单个地址位置的读取和写入行为。

在不同高速缓存中同时发生的一种类型的数据称为高速缓存一致性，或在某些系统中称为全局存储器。

在多处理器系统中，假设多个处理器缓存了内存位置 X 的副本。要实现缓存一致性，必须满足以下条件：

1. 在处理器 P 对位置 X 进行的读取中，该位置 X 遵循同一处理器 P 对 X 的写入，在 P 的写入和读取指令之间没有另一个处理器对 X 进行写入，X 必须始终返回 P 写入的值。
2. 在处理器 P1 对位置 X 的读取中，在另一个处理器 P2 写入 X 之后，在两次访问之间没有任何处理器对 X 进行其他写入，并且读取和写入充分分离，X 必须始终返回 P2 写入的值。此条件定义了内存的连贯视图的概念。将写入传播到共享内存位置可确保所有高速缓存都具有一致的内存视图。如果处理器 P1 读取 X 的旧值，即使在 P2 写入之后，我们也可以说内存是不连贯的。

上述条件满足缓存一致性所需的写入传播条件。但是，它们是不够的，因为它们不满足事务序列化条件。为了更好地说明这一点，请考虑以下示例：

多处理器系统由四个处理器组成 - P1、P2、P3 和 P4，它们都包含初始值为 0 的共享变量 S 的缓存副本。处理器 P1 将 S（在其缓存副本中）的值更改为 10，然后处理器 P2 将自己的缓存副本中的 S 值更改为 20。如果我们只确保写入传播，那么 P3 和 P4 肯定会看到 P1 和 P2 对 S 所做的更改。但是，P3 可能会在看到 P2 所做的更改后看到 P1 所做的更改，因此在读取到 S 时返回 10。另一方面，P4 可能会看到 P1 和 P2 按其更改的顺序进行更改，因此在读取 S 时返回 20。处理器 P3 和 P4 现在对内存的视图不连贯。

因此，为了满足事务序列化，从而实现缓存一致性，必须满足以下条件以及本节中提到的前两个条件：

• 对同一位置的写入必须按顺序进行排序。换句话说，如果位置 X 按此顺序从任意两个处理器接收两个不同的值 A 和 B，则处理器永远无法将位置 X 读取为 B，然后将其读取为 A。必须按该顺序查看位置 X 的值 A 和 B。

相干系统的替代定义是通过顺序一致性内存模型的定义：“缓存相干系统必须以遵循每个线程的程序顺序的总顺序执行所有线程的加载并存储到单个内存位置”。因此，高速缓存一致性系统和顺序一致性系统之间的唯一区别在于定义中讨论的地址位置数（缓存一致性系统的单个内存位置，以及顺序一致性系统的所有内存位置）。

另一个定义是：“如果对同一内存位置的所有写入都按某种顺序执行，则多处理器是高速缓存一致的”。

很少，尤其是在算法中，一致性可以指参考的位置。相同数据的多个副本可以同时存在于不同的缓存中，如果允许处理器自由更新自己的副本，则可能导致内存视图不一致。

确保一致性的两种最常见的机制是窥探和基于目录的机制，每种机制都有自己的优点和缺点。如果有足够的带宽可用，则基于侦听的协议往往更快，因为所有事务都是所有处理器看到的请求/响应。缺点是窥探不可扩展。每个请求都必须广播到系统中的所有节点，这意味着随着系统变大，（逻辑或物理）总线的大小及其提供的带宽必须增长。另一方面，目录往往具有更长的延迟（具有 3 跳请求/转发/响应），但由于消息是点对点而不是广播，因此使用的带宽要少得多。因此，许多较大的系统（>64 处理器）都使用这种类型的缓存一致性。

侦听于 1983 年首次引入，是各个缓存监视地址行以访问它们缓存的内存位置的过程。写入无效协议和写入更新协议使用此机制。

对于侦听机制，侦听过滤器通过维护多个条目来减少侦听流量，每个条目表示可能由一个或多个节点拥有的缓存行。当需要替换其中一个条目时，侦听筛选器会选择替换表示最少节点拥有的缓存行的条目，该条目由每个条目中的存在向量确定。如果最少节点拥有多个缓存行，则使用临时算法或其他类型的算法来优化选择。

在基于目录的系统中，共享的数据放置在维护缓存之间一致性的公共目录中。该目录充当过滤器，处理器必须通过该过滤器请求将条目从主内存加载到其缓存的权限。更改条目时，目录会更新该条目的其他缓存或使其失效。

分布式共享内存系统模仿这些机制，试图在松散耦合的系统中保持内存块之间的一致性。

一致性协议在多处理器系统中应用缓存一致性。目的是两个客户端绝不能看到同一共享数据的不同值。

议定书必须落实一致性的基本要求。它可以为目标系统或应用量身定制。

协议也可以分类为史努比或基于目录。通常，早期系统使用基于目录的协议，其中目录将跟踪正在共享的数据和共享者。在 snoopy 协议中，事务请求（读取、写入或升级）被发送到所有处理器。所有处理器都会窥探请求并做出适当的响应。

史努比协议中的写入传播可以通过以下任一方法实现：

Write-invalidate 写作无效

当观察到对缓存具有副本的位置执行写入操作时，缓存控制器会使其自己的侦听内存位置副本失效，这会强制在下次访问时从主内存读取新值。

Write-update 写入更新

当观察到对缓存具有副本的位置执行写入操作时，缓存控制器会使用新数据更新其自己的侦听内存位置副本。

如果协议设计规定，每当共享数据的任何副本发生更改时，必须“更新”所有其他副本以反映更改，那么它就是写入更新协议。如果设计声明任何处理器对缓存副本的写入要求其他处理器丢弃其缓存副本或使其无效，则它是写入无效协议。

但是，可伸缩性是广播协议的一个缺点。

已经设计了各种模型和协议来保持一致性，例如MSI，MESI（又名伊利诺伊州），MOSI，MOESI，MERSI，MESIF，写一次，Synapse，Berkeley，Firefly和Dragon协议。2011 年，ARM Ltd 提出了 AMBA 4 ACE 来处理 SoC 中的一致性。来自 ARM Ltd 的 AMBA CHI（相干集线器接口）规范属于 AMBA5 规范组，定义了用于连接完全相干处理器的接口。

在计算中，分布式缓存是在单个区域设置中使用的传统缓存概念的扩展。分布式缓存可以跨越多个服务器，以便它可以增加大小和事务容量。它主要用于存储驻留在数据库和Web会话数据中的应用程序数据。分布式缓存的想法现在已经变得可行，因为主内存变得非常便宜，网卡变得非常快，1Gbit现在到处都是标准，10Gbit越来越受欢迎。 [when?] 此外，分布式缓存在通常用于 Web 服务器的低成本机器上运行良好，而不是需要昂贵硬件的数据库服务器。一种新兴的互联网架构被称为以信息为中心的网络（ICN），是分布式缓存网络的最佳示例之一。ICN是网络级解决方案，因此现有的分布式网络缓存管理方案不太适合ICN。在超级计算机环境中，分布式缓存通常以突发缓冲区的形式实现。

• Aerospike 气钉
• Apache Ignite 阿帕奇点燃
• Couchbase 沙发底座
• Ehcache 埃赫缓存
• GigaSpaces 千兆空间
• Hazelcast 榛子
• Infinispan 英菲尼斯潘
• Memcached 内存缓存
• Oracle Coherence 甲骨文一致性
• Riak 里亚克
• Redis 雷迪斯
• SafePeak 安全峰
• Tarantool 塔兰图
• Velocity/AppFabric

  Velocity/AppFabric

在计算中，缓存替换策略（也称为缓存替换算法或缓存算法）正在优化指令或算法，计算机程序或硬件维护的结构可以利用这些指令或算法来管理存储在计算机上的信息缓存。缓存通过将最近或经常使用的数据项保存在内存位置来提高性能，这些位置的访问速度比普通内存存储更快或计算成本更低。当缓存已满时，算法必须选择要丢弃的项目，以便为新项目腾出空间。

平均内存参考时间为

m = miss ratio = 1 - (hit ratio)

Tm = 在未命中时进行主内存访问的时间（或者，对于多级缓存，下一个较低缓存的平均内存参考时间

Th = 延迟：引用缓存的时间（命中和未命中应相同）

E = 各种次要效应，例如多处理器系统中的排队效应

缓存有两个主要品质因数：延迟和命中率。还有许多影响缓存性能的次要因素。

缓存的“命中率”描述了在缓存中实际找到搜索项的频率。更高效的替换策略会跟踪更多使用情况信息，以提高命中率（对于给定的缓存大小）。

缓存的“延迟”描述了在请求所需项目后多久缓存可以返回该项目（当有命中时）。更快的替换策略通常会跟踪较少的使用情况信息（或者在直接映射缓存的情况下，不跟踪任何信息），以减少更新该信息所需的时间。

每个替换策略都是命中率和延迟之间的折衷。

命中率测量通常在基准测试应用程序上执行。实际命中率因应用程序而异。特别是，视频和音频流应用程序的命中率通常接近于零，因为流中的每个数据位都是第一次读取一次（强制未命中），使用，然后永远不会再次读取或写入。更糟糕的是，许多缓存算法（特别是LRU）允许这些流数据填充缓存，从而推出即将再次使用的缓存信息（缓存污染）。

其他需要考虑的事项：

• 具有不同成本的物品：保留昂贵的物品，例如那些需要很长时间才能获得的物品。
• 占用更多缓存的项目：如果项目具有不同的大小，则缓存可能希望丢弃一个大项目来存储几个较小的项目。
• 随时间过期的项目：某些缓存会保留过期的信息（例如新闻缓存、DNS 缓存或 Web 浏览器缓存）。计算机可能会丢弃项目，因为它们已过期。根据缓存的大小，可能不需要进一步的缓存算法来丢弃项目。

还存在各种算法来维护缓存一致性。这仅适用于对同一数据使用多个独立高速缓存的情况（例如，多个数据库服务器更新单个共享数据文件）。

最有效的缓存算法是始终丢弃将来最长时间不需要的信息。这种最优结果被称为贝拉迪最优算法/简单最优替换策略或千里眼算法。由于通常无法预测未来需要多大程度的信息，因此在实践中通常无法实施。实际最小值只能在实验后计算，并且可以比较实际选择的缓存算法的有效性。

最佳工作

在发生页面错误的那一刻，内存中存在一组页面。在该示例中，“5”、“0”、“1”的序列分别由帧 1、帧 2、帧 3 访问。然后，当访问“2”时，它会替换位于第 1 帧中的值“5”，因为它预测值“5”在不久的将来不会被访问。由于现实生活中的通用操作系统实际上无法预测何时访问“5”，因此无法在这样的系统上实现贝拉迪算法。

随机选择一个候选项目，并在必要时将其丢弃以腾出空间。此算法不需要保留有关访问历史记录的任何信息。由于其简单性，它已被用于ARM处理器。它允许有效的随机模拟。

基于队列的简单策略

使用此算法，缓存的行为方式与 FIFO 队列相同。缓存按块添加顺序逐出块，而不考虑以前访问它们的频率或次数。

使用此算法，缓存的行为方式与堆栈相同，与 FIFO 队列相反。缓存首先逐出最近添加的块，而不考虑之前访问该块的频率或次数。

基于新近度的简单策略

首先丢弃最近最少使用的项目。此算法需要跟踪何时使用的内容，如果想要确保算法始终丢弃最近最少使用的项目，则成本很高。此技术的一般实现需要为缓存行保留“年龄位”，并根据年龄位跟踪“最近最少使用”的缓存行。在这样的实现中，每次使用缓存行时，所有其他缓存行的期限都会更改。LRU实际上是一个缓存算法家族，其成员包括Theodore Johnson和Dennis Shasha的2Q，以及Pat O'Neil，Betty O'Neil和Gerhard Weikum的LRU / K。

以下示例的访问顺序为 A B C D E D F。

LRU工作

在示例中，一旦 A B C D 安装在具有序列号的块中（每个新访问的增量为 1），当访问 E 时，它是一个未命中，需要将其安装在其中一个块中。根据LRU算法，由于A的秩（A（0））最低，E将取代A。

在倒数第二步中，访问 D，因此更新序列号。

最后，访问 F 代替目前排名最低的 B（B（1））。

感知最近最少使用 （TLRU） 是 LRU 的一种变体，专为缓存中存储的内容具有有效生存期的情况而设计。该算法适用于网络缓存应用，如以信息为中心的网络（ICN）、内容分发网络（CDN）和一般的分布式网络。TLRU引入了一个新术语：TTU（使用时间）。TTU 是内容/页面的时间戳，它根据内容的位置和内容发布者公告规定内容的可用性时间。由于基于此位置的时间戳，TTU 为本地管理员提供了更多的控制，以规范网络存储。在 TLRU 算法中，当一段内容到达时，缓存节点会根据内容发布者分配的 TTU 值计算本地 TTU 值。本地 TTU 值是使用本地定义的函数计算的。计算本地 TTU 值后，将对存储在缓存节点中的总内容的子集执行内容替换。TLRU确保不太受欢迎和较小的生活内容应替换为传入的内容。

与最近最少使用的 （LRU） 相反，MRU 首先丢弃最近使用的项目。在第11届VLDB会议上发表的研究结果中，Chou和DeWitt指出，“当以[循环顺序]参考模式重复扫描文件时，MRU是最好的替换算法。随后，在第 22 届 VLDB 会议上发言的其他研究人员指出，对于随机访问模式和对大型数据集的重复扫描（有时称为循环访问模式），MRU 缓存算法比 LRU 具有更多的命中率，因为它们倾向于保留旧数据。MRU 算法在项目越旧、访问的可能性就越大的情况下最有用。

以下示例的访问顺序为 A B C D E C D B。

MRU 工作

在这里，A B C D 被放置在缓存中，因为仍有可用空间。在第 5 次访问 E 时，我们看到持有 D 的块现在被替换为 E，因为该块是最近使用的。对 C 的另一个访问和对 D 的下一次访问时，C 被替换，因为它是在 D 之前访问的块，依此类推。

缓存分为两个段，一个试用段和一个受保护段。每个段中的行按最近访问次数从最多到最少的顺序排列。未命中数据将添加到试用期最近访问端的缓存中。命中将从其当前所在的任何位置删除，并添加到受保护段的最近访问端。因此，受保护网段中的线路至少被访问了两次。受保护段是有限的，因此将线路从试用段迁移到受保护段可能会强制受保护段中的 LRU 线路迁移到试用段的最近使用 （MRU） 端，从而在替换之前再次有机会访问此线路。受保护分段上的大小限制是一个 SLRU 参数，该参数因 I/O 工作负载模式而异。每当必须从缓存中丢弃数据时，都会从试用段的 LRU 端获取行。

在具有较高关联性的缓存中，LRU 可能非常昂贵。实用硬件通常采用近似值，以更低的硬件成本实现类似的性能。

对于具有较大关联性的 CPU 缓存（通常>4 种方式），LRU 的实现成本变得令人望而却步。在许多 CPU 缓存中，几乎总是丢弃最近最少使用的项目之一的方案就足够了，因此许多 CPU 设计人员选择的 PLRU 算法只需要每个缓存项目一位即可工作。与 LRU 相比，PLRU 的失误率通常稍差，延迟稍好，功耗略低于 LRU，开销也更低。

下面的示例演示 Bits 如何用作指向最近使用的子树的 1 位指针的二叉树。沿着指向叶节点的指针链标识替换候选项。访问时，链中从访问方式的叶节点到根节点的所有指针都设置为指向不包含所访问方式的子树。

访问顺序为 A B C D E。

伪 LRU 工作

如果我们只看箭头指针，这里的原理很容易理解。当可以访问一个值时，比如“A”，并且我们在缓存中找不到它，然后我们从内存中加载它并将其放置在箭头当前指向的块上，从上到下。放置该块后，我们翻转相同的箭头，使它们指向相反的方向。在上面的例子中，我们看到“A”是如何放置的，后跟“B”、“C 和”D”。然后，当缓存已满时，“E”替换了“A”，因为那是当时箭头指向的位置，并且导致“A”的箭头被翻转为指向相反的方向。然后箭头指向“B”，这将是下一次缓存未命中时替换的块。

LRU算法由于其高开销，无法直接在计算机系统（如操作系统）的关键路径中实现。LRU的近似值，称为CLOCK，通常用于实现。同样，CLOCK-Pro是LIRS的近似值，用于在系统中实现低成本。CLOCK-Pro在基本的CLOCK框架下，但有三个主要的不同优点。首先，CLOCK-Pro有三个“时钟指针”，而CLOCK的简单结构只使用一个“手”。通过三只指针，CLOCK-Pro能够以近似的方式测量数据访问的重用距离。其次，保留了LIRS的所有优点，例如快速驱逐一次性访问和/或低位置数据项。第三，CLOCK-Pro的复杂性与CLOCK相同，因此易于以低成本实现。当前版本的Linux中的缓冲区缓存替换实现是LRU和CLOCK-Pro的组合。

基于频率的简单策略

计算需要项目的频率。那些最不常使用的被丢弃。这与 LRU 非常相似，不同之处在于我们不存储最近访问块的值，而是存储访问该块的次数的值。因此，当然，在运行访问序列时，我们将从缓存中替换使用次数最少的块。例如，如果 A 被使用（访问）5 次，B 被使用 3 次，其他 C 和 D 分别被使用 10 次，我们将替换 B。

最近使用频率最低 （LFRU） 缓存替换方案结合了 LFU 和 LRU 方案的优点。LFRU 适用于“网络内”缓存应用，例如以信息为中心的网络 （ICN）、内容交付网络 （CDN） 和一般的分布式网络。在 LFRU 中，缓存分为两个分区，称为特权分区和非特权分区。特权分区可以定义为受保护分区。如果内容非常受欢迎，则会将其推送到特权分区中。特权分区的替换如下：LFRU 从非特权分区中逐出内容，将内容从特权分区推送到非特权分区，最后将新内容插入特权分区。在上述过程中，LRU 用于特权分区，近似 LFU （ALFU） 方案用于非特权分区，因此缩写为 LFRU。

基本思想是使用 ALFU 方案过滤掉本地流行的内容，并将流行的内容推送到特权分区之一。

一种称为具有动态老化功能的 LFU （LFUDA） 的变体，它使用动态老化来适应流行对象集中的变化。当将新对象添加到缓存或重新引用现有对象时，它会将缓存老化因子添加到引用计数中。LFUDA 在逐出块时通过将其设置为逐出对象的键值来递增缓存老化。因此，缓存老化始终小于或等于缓存中的最小键值。假设过去经常访问一个对象，现在它变得不受欢迎，它将在缓存中保留很长时间，从而防止新近或不太受欢迎的对象替换它。因此，引入这种动态老化是为了减少此类对象的数量，从而使它们有资格进行替换。LFUDA 的优点是当缓存大小非常小时，它可以减少 LFU 造成的缓存污染。当缓存大小很大时，很少有替换决策就足够了，缓存污染不会成为问题。

RRIP风格的策略构成了许多其他缓存替换策略的基础，包括赢得CRC2冠军的鹰眼，被认为是当时最先进的缓存替换策略。

RRIP 是英特尔提出的一种非常灵活的策略，它试图提供良好的抗扫描性，同时还允许逐出未重复使用的旧缓存行。所有缓存行都有一个称为 RRPV（重新引用预测值）的预测值，该值应与预期重用该行的时间相关联。在插入时，此 RRPV 通常很高，因此如果该行没有很快重用，它将被逐出，这样做是为了防止扫描（仅使用一次的大量数据）填满缓存。重用高速缓存行时，此 RRPV 设置为零，表示此行已重用一次，并且很可能再次重用。

在缓存未命中时，RRPV 等于最大可能 RRPV 的行将被逐出（例如，对于 3 位值，RRPV 为 2 3 - 1 = 7 的行被逐出），如果没有行具有此值，则集合中的所有 RRPV 都将递增 1，直到达到它。需要一个决胜局，通常是左边的第一行。需要此增量来确保旧行正确老化，如果不重复使用，则会被逐出。

SRRIP 插入 RRPV 值为 maxRRIP 的行。这意味着刚刚插入的行最有可能在缓存未命中时被逐出。

SRRIP 在正常情况下表现良好，但当工作集远大于缓存大小并导致缓存抖动时会受到影响，这可以通过大多数时间插入 RRPV 值为 maxRRPV 的行和以低概率随机插入 RRPV 值为 maxRRPV - 1 的行来补救。这会导致某些行“粘”在缓存中并有助于防止抖动。

但是，BRRIP 会降低非抖动访问的性能。

当工作集小于缓存大小时，SRRIP 性能最佳，而当工作集大于缓存大小时，BRRIP 性能最佳。

DRRIP的目标是两全其美。它使用集合决斗来选择是使用 SRRIP 还是 BRRIP。它将几个集（通常为 32 个）专用于仅使用 SRRIP，另外几个集仅用于使用 BRRIP，并使用策略计数器来监视这些集中的哪个集性能更好，以确定缓存的其余部分将使用哪个策略。

Bélády 算法是最佳的缓存替换策略，但它需要了解未来才能逐出将来最远重用的行。已经提出了多个替换策略，试图预测与过去访问模式的未来重用距离，从而允许它们近似最佳替换策略。一些性能最好的缓存替换策略是那些试图模仿 Bélády 算法的策略。

Hawkeye 试图模拟 Bélády 的算法，通过使用 PC 过去的访问来预测它产生的访问是生成缓存友好访问（稍后使用的访问）还是缓存厌恶访问（以后不使用）。

它通过对许多缓存集（未对齐）进行采样来实现这一点，它使用长度 8×the cache size 历史记录并在这些访问上模拟 Bélády 的算法。这允许策略确定哪些行应该缓存，哪些行不应该缓存。

此数据允许它预测指令是缓存友好还是缓存厌恶。然后将此数据馈送到 RRIP，这意味着来自缓存友好指令的访问具有较低的 RRPV 值（可能稍后被逐出），而来自缓存厌恶指令的访问具有较高的 RRPV 值（可能更早被逐出）。

RRIP 后端是执行实际逐出决策的部分。采样缓存和OPT生成器仅用于设置插入的缓存行的初始RRPV值。

鹰眼在 2017 年赢得了 CRC2 缓存冠军，击败了当时所有其他缓存替换策略。

Harmony 是 Hawkeye 的扩展，可提高预取性能。

Block diagram of the Mockingjay cache replacement policy.

Mockingjay 缓存替换策略的框图。

Mockingjay试图以多种方式改进鹰眼。首先，它删除二进制预测，允许它就要逐出哪些缓存行做出更精细的决策。其次，在更多信息可用后，它决定稍后要逐出哪个缓存行。

它通过保留唯一访问的采样缓存、产生它们的 PC 及其时间戳来实现这一点。当再次访问采样缓存中的一行时，时间差将发送到重用距离预测器，该预测器使用时间差分学习，其中新的 RDP 值将增加或减少少量以补偿异常值。该数字的计算公式为 �=���(1,timestamp difference16) 。除非该值尚未初始化，在这种情况下，将直接插入观察到的重用距离。如果采样缓存已满，并且我们需要丢弃一行，则我们训练上次访问它的 PC 生成流式访问的 RDP。

在访问或插入时，此行的估计重用时间 （ETR） 将更新以反映预测的重用距离。每隔几次访问集，递减集合的所有 ETR 计数器（如果不访问超过其估计的重用时间，则可能会变为负数）。

在缓存未命中时，具有最高绝对 ETR 值的线路将被逐出（估计在将来重用最远的线路，或者估计在过去重用最远且未重用的线路）。

Mockingjay 获得的结果非常接近最优的 Bélády 算法，通常只有百分之几的性能差异。

多个缓存替换策略尝试使用感知器、马尔可夫链或其他类型的机器学习来预测要逐出哪条线。还有针对缓存替换问题的学习增强算法。

其他缓存替换策略

LIRS 是一种页面替换算法，与 LRU 和许多其他较新的替换算法相比，性能有所提高。这是通过使用重用距离作为动态排名访问页面以做出替换决策的指标来实现的。LIRS 通过使用新近度来评估参考间新近度 （IRR） 以做出替换决策，从而有效地解决了 LRU 的限制。

LIRS算法工作

在上图中，“x”表示在时间t访问块。假设如果在时间 1 访问块 A1，则新近度将变为 0，因为这是第一个访问的块，IRR 将为 1，因为它预测 A1 将在时间 3 再次被访问。在访问 A4 后的时间 2 中，A4 的新近度将变为 0，A1 的新近度将变为 1，因为 A4 是最近访问的对象，IRR 将变为 4 并且将继续。在时间 10 时，LIRS 算法将有两个集合 LIR set = {A1， A2} 和 HIR 集合 = {A3， A4， A5}。现在在时间 10 如果可以访问 A4，则会发生未命中。LIRS 算法现在将逐出 A5 而不是 A2，因为它的新近度最大。

不断在LRU和LFU之间平衡，以改善组合结果。ARC 通过使用有关最近逐出的缓存项的信息来动态调整受保护段和试用段的大小，以充分利用可用缓存空间，从而改进了 SLRU。通过示例解释了自适应替换算法。

使用最近的命中/未命中来调整跳跃，在攀爬中任何命中将位置切换一个插槽到顶部，而在 LRU 命中将命中位置切换到顶部。因此，当程序处于固定范围内时，受益于爬升的最佳性，以及像LRU一样快速适应新范围。还支持内核之间的缓存共享，当引用到缓存的顶部时，通过释放额外的内容。

Further information: Clock with adaptive replacement更多信息：带自适应替换功能的时钟

Combines the advantages of Adaptive Replacement Cache (ARC) and CLOCK. CAR has performance comparable to ARC, and substantially outperforms both LRU and CLOCK. Like ARC, CAR is self-tuning and requires no user-specified magic parameters. It uses 4 doubly linked lists: two clocks T1 and T2 and two simple LRU lists B1 and B2. T1 clock stores pages based on "recency" or "short term utility" whereas T2 stores pages with "frequency" or "long term utility". T1 and T2 contain those pages that are in the cache, while B1 and B2 contain pages that have recently been evicted from T1 and T2 respectively. The algorithm tries to maintain the size of these lists B1≈T2 and B2≈T1. New pages are inserted in T1 or T2. If there is a hit in B1 size of T1 is increased and similarly if there is a hit in B2 size of T1 is decreased. The adaptation rule used has the same principle as that in ARC, invest more in lists that will give more hits when more pages are added to it.

结合了自适应替换缓存 （ARC） 和时钟的优点。CAR的性能可与ARC相媲美，并且大大优于LRU和CLOCK。与 ARC 一样，CAR 是自整定的，不需要用户指定的魔术参数。它使用 4 个双向链表：两个时钟 T1 和 T2 以及两个简单的 LRU 列表 B1 和 B2。T1时钟根据“新近度”或“短期效用”存储页面，而T2存储具有“频率”或“长期效用”的页面。T1 和 T2 包含缓存中的那些页面，而 B1 和 B2 分别包含最近从 T1 和 T2 中逐出的页面。该算法尝试维护这些列表 B1≈T2 和 B2≈T1 的大小。新页面插入到 T1 或 T2 中。如果在 B1 中受到打击，则 T1 的大小会增加，同样，如果在 B2 中出现命中，则 T1 的大小会减小。使用的适应规则与 ARC 中的原则相同，在列表中投入更多，当添加更多页面时，这些列表将提供更多点击。

The multi queue algorithm or MQ was developed to improve the performance of second level buffer cache for e.g. a server buffer cache. It is introduced in a paper by Zhou, Philbin, and Li. The MQ cache contains an m number of LRU queues: Q0, Q1, ..., Qm-1. Here, the value of m represents a hierarchy based on the lifetime of all blocks in that particular queue. For example, if j>i, blocks in Qj will have a longer lifetime than those in Qi. In addition to these there is another history buffer Qout, a queue which maintains a list of all the Block Identifiers along with their access frequencies. When Qout is full the oldest identifier is evicted. Blocks stay in the LRU queues for a given lifetime, which is defined dynamically by the MQ algorithm to be the maximum temporal distance between two accesses to the same file or the number of cache blocks, whichever is larger. If a block has not been referenced within its lifetime, it is demoted from Qi to Qi−1 or evicted from the cache if it is in Q0. Each queue also has a maximum access count; if a block in queue Qi is accessed more than 2i times, this block is promoted to Qi+1 until it is accessed more than 2i+1 times or its lifetime expires. Within a given queue, blocks are ranked by the recency of access, according to LRU.

开发多队列算法或MQ是为了提高二级缓冲区缓存的性能，例如服务器缓冲区缓存。这是在周、菲尔宾和李的一篇论文中介绍的。MQ 高速缓存包含 m 个 LRU 队列：Q ， Q ， ...， Q 0 1 m-1 。在这里，m 的值表示基于该特定队列中所有块的生存期的层次结构。例如，如果为 j>i，则 Q 中的块将比 Q 中的块具有更长的生存期。除此之外，还有另一个历史缓冲区Q out ，一个维护所有块标识符及其访问频率列表的队列。当 Q out 已满时，将逐出最旧的标识符。块在给定的生存期内保留在 LRU 队列中，该生存期由 MQ 算法动态定义为对同一文件的两次访问之间的最大时间距离或缓存块数，以较大者为准。如果某个块在其生存期内未被引用，则会将其从 Q 降级到 Q， i−1 或者如果它在 Q 中，则会从缓存中逐出 0 。每个队列还具有最大访问计数;如果队列 Q 中的块被访问超过 2 次，则该块将提升为 Q， i+1 直到访问超过 2 i+1 次或其生存期到期。根据 LRU 的说法，在给定的队列中，块按访问的新近度进行排名。

Multi Queue Replacement 多队列替换

We can see from Fig. how the m LRU queues are placed in the cache. Also see from Fig. how the Qout stores the block identifiers and their corresponding access frequencies. a was placed in Q0 as it was accessed only once recently and we can check in Qout how b and c were placed in Q1 and Q2 respectively as their access frequencies are 2 and 4. The queue in which a block is placed is dependent on access frequency(f) as log2(f). When the cache is full, the first block to be evicted will be the head of Q0 in this case a. If a is accessed one more time it will move to Q1 below b.

我们可以从图中看到。m LRU 队列在缓存中的放置方式。另见图。Q 如何 out 存储块标识符及其相应的访问频率。a 被放置在 Q 中， 0 因为它最近只被访问过一次，我们可以在 Q 中检查 b 和 c out 是如何 2 分别放置在 Q 和 Q 中的，因为它们的访问频率是 2 1 和 4。放置块的队列依赖于访问频率（f）作为日志 2 （f）。当缓存已满时，在本例 0 中，第一个要逐出的块将是 Q 的头部 a。如果再访问一次 a，它将移动到 b 1 下方的 Q。

S3FIFO is an enhanced FIFO-based eviction algorithm utilizing three static queues: the Small FIFO queue (S), the Main FIFO queue (M), and the Ghost FIFO queue (G). The Small FIFO (S) holds 10% of the cache space, while the Main FIFO (M) manages the remaining 90%. The Ghost FIFO (G) keeps ghost entries with the same number of entries in the Main FIFO queue.

S3FIFO 是一种基于 FIFO 的增强型逐出算法，利用三个静态队列：小型 FIFO 队列 （S）、主 FIFO 队列 （M） 和幽灵 FIFO 队列 （G）。小型 FIFO （S） 拥有 10% 的缓存空间，而主 FIFO （M） 管理剩余的 90%。幽灵 FIFO （G） 在主 FIFO 队列中保留具有相同数量条目的幻影条目。

Upon object introduction:

在对象介绍时：

• New objects are admitted to S unless they're found in G, in which case they're placed in M.

  除非在 G 中找到新对象，否则它们会被允许进入 S，在这种情况下，它们被放置在 M 中。

• As Small FIFO fills, objects at its end move to either M (if accessed more than twice) or G, with their access bits cleared.

  当小型FIFO填充时，其末端的对象将移动到M（如果访问两次以上）或G，并清除其访问位。

Ghost FIFO evicts objects in FIFO fashion upon filling.

幽灵FIFO在填充时以FIFO方式驱逐对象。

• Main FIFO operates akin to FIFO-Reinsertion, using two bits to track access frequency. Objects accessed at least once are reinserted, with frequency decremented by one.

  主FIFO的操作类似于FIFO重新插入，使用两个位来跟踪访问频率。至少访问一次的对象将重新插入，频率降低 1。

In essence, S3FIFO merges the simplicity of FIFO with added nuances.

从本质上讲，S3FIFO融合了FIFO的简单性和额外的细微差别。

Pannier is a container-based flash caching mechanism that identifies divergent (heterogeneous) containers where blocks held therein have highly varying access patterns. Pannier uses a priority-queue based survival queue structure to rank the containers based on their survival time, which is proportional to the live data in the container. Pannier is built based on Segmented LRU (S2LRU), which segregates hot and cold data. Pannier also uses a multi-step feedback controller to throttle flash writes to ensure flash lifespan.

Pannier 是一种基于容器的闪存缓存机制，可识别不同（异构）容器，其中保存的块具有高度不同的访问模式。Pannier 使用基于优先级队列的生存队列结构根据容器的生存时间对容器进行排名，该时间与容器中的实时数据成正比。Pannier 基于分段 LRU （S2LRU） 构建，它隔离了冷热数据。Pannier 还使用多步反馈控制器来限制闪存写入，以确保闪存使用寿命。

One may want to establish, through static analysis, which accesses are cache hits or misses, for instance to rigorously bound the worst-case execution time of a program. The output of static analysis is thus, for every access in the program, an indication if it always a cache hit, always a miss, or in indeterminate status. Many refinements are possible: for instance one may establish that an access is a hit if the procedure where it is located is used in certain calling contexts, that an access in a loop a cache miss in the first iteration of that loop but a hit in the other iterations, etc.

人们可能希望通过静态分析来确定哪些访问是缓存命中或未命中，例如严格绑定程序的最坏情况执行时间。因此，对于程序中的每次访问，静态分析的输出都指示它是否始终是缓存命中、始终未命中或处于不确定状态。许多改进是可能的：例如，如果在某些调用上下文中使用访问所在的过程，则可以确定访问是命中，循环中的访问在该循环的第一次迭代中缓存未命中，但在其他迭代中命中，等等。

A classical approach to analyzing properties of LRU caches is to associate to each block in the cache an "age" (0 for the most recently used, and so on up to cache associativity) and compute intervals for possible ages. This analysis can be refined to distinguish automatically cases where the same program point is accessible by paths that result, for some, in misses, and for some, in hits. One may even obtain an exact analysis (with respect to an execution model that considers only the syntactic control flow of the program, without semantics for conditions) that is at the same time efficient by abstracting sets of cache states by antichains, which are themselves represented by compact binary decision diagrams.

分析 LRU 缓存属性的经典方法是将“年龄”（0 表示最近使用，依此类推直至缓存关联性）与缓存中的每个块相关联，并计算可能的年龄间隔。可以优化此分析，以自动区分同一程序点可通过路径访问的情况，这些路径对某些路径造成未命中，对某些人来说，导致命中。人们甚至可以获得精确的分析（关于只考虑程序的语法控制流，没有条件语义的执行模型），同时通过反链抽象缓存状态集来提高效率，反链本身由紧凑的二进制决策图表示。

This good property of LRU from the point of view of static analysis does not generalize to pseudo-LRU policies. It indeed can be shown that, from the point of view of computational complexity theory, static analysis problems posed by pseudo-LRU and FIFO belong to higher complexity classes than those for LRU · .

从静态分析的角度来看，LRU 的这种良好特性不能推广到伪 LRU 策略。从计算复杂度理论的角度看，伪LRU和FIFO提出的静态分析问题比LRU·的静态分析问题属于更高的复杂度类。

In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus, a cache-oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache.

在计算中，忽略缓存算法（或缓存超越算法）是一种旨在利用处理器缓存的算法，而无需将缓存的大小（或缓存行的长度等）作为显式参数。最佳缓存忽略算法是一种缓存忽略算法，它以最佳方式使用缓存（在渐近意义上，忽略常量因子）。因此，忽略缓存算法被设计为在具有不同缓存大小的多台计算机上或具有不同大小的不同缓存级别的内存层次结构上执行良好，无需修改。忽略缓存的算法与显式循环切片形成对比，显式循环切片将问题显式分解为针对给定缓存优化大小的块。

Optimal cache-oblivious algorithms are known for matrix multiplication, matrix transposition, sorting, and several other problems. Some more general algorithms, such as Cooley–Tukey FFT, are optimally cache-oblivious under certain choices of parameters. As these algorithms are only optimal in an asymptotic sense (ignoring constant factors), further machine-specific tuning may be required to obtain nearly optimal performance in an absolute sense. The goal of cache-oblivious algorithms is to reduce the amount of such tuning that is required.

最优缓存遗忘算法已知矩阵乘法、矩阵转置、排序和其他几个问题。一些更通用的算法，如Cooley-Tukey FFT，在某些参数选择下是最优的缓存忽略。由于这些算法仅在渐近意义上是最优的（忽略常数因子），因此可能需要进一步的特定于机器的调整才能在绝对意义上获得接近最佳的性能。忽略缓存的算法的目标是减少所需的此类调优量。

Typically, a cache-oblivious algorithm works by a recursive divide-and-conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into the cache, regardless of the cache size. For example, an optimal cache-oblivious matrix multiplication is obtained by recursively dividing each matrix into four sub-matrices to be multiplied, multiplying the submatrices in a depth-first fashion.[citation needed] In tuning for a specific machine, one may use a hybrid algorithm which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache-oblivious algorithm.

通常，忽略缓存的算法通过递归分而治之算法工作，其中问题被划分为越来越小的子问题。最终，无论缓存大小如何，都会达到适合缓存的子问题大小。例如，通过将每个矩阵递归划分为四个要乘法的子矩阵，以深度优先的方式乘以子矩阵，获得最优缓存忽略矩阵乘法。 [citation needed] 在针对特定计算机进行调优时，可以使用混合算法，该算法使用针对底层特定缓存大小进行调优的循环平铺，否则使用忽略缓存的算法。

The idea (and name) for cache-oblivious algorithms was conceived by Charles E. Leiserson as early as 1996 and first published by Harald Prokop in his master's thesis at the Massachusetts Institute of Technology in 1999. There were many predecessors, typically analyzing specific problems; these are discussed in detail in Frigo et al. 1999. Early examples cited include Singleton 1969 for a recursive Fast Fourier Transform, similar ideas in Aggarwal et al. 1987, Frigo 1996 for matrix multiplication and LU decomposition, and Todd Veldhuizen 1996 for matrix algorithms in the Blitz++ library.

忽略缓存算法的想法（和名称）早在1996年就由Charles E. Leiserson提出，并由Harald Prokop于1999年在麻省理工学院的硕士论文中首次发表。有许多前辈，通常分析具体问题;Frigo等人于1999年详细讨论了这些问题。引用的早期例子包括Singleton 1969的递归快速傅立叶变换，Aggarwal等人1987年的类似想法，Frigo 1996的矩阵乘法和LU分解，以及Todd Veldhuizen 1996的Blitz++库中的矩阵算法。

In general, a program can be made more cache-conscious:

通常，可以使程序更具缓存意识：

• Temporal locality, where the algorithm fetches the same pieces of memory multiple times;

  时间局部性，其中算法多次获取相同的内存片段;

• Spatial locality, where the subsequent memory accesses are adjacent or nearby memory addresses.

  空间局部性，其中后续内存访问是相邻或附近的内存地址。

Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the cache-oblivious model. This model is much easier to analyze than a real cache's characteristics (which have complicated associativity, replacement policies, etc.), but in many cases is provably within a constant factor of a more realistic cache's performance. It is different than the external memory model because cache-oblivious algorithms do not know the block size or the cache size.

忽略缓存算法通常使用缓存的理想化模型（有时称为忽略缓存模型）进行分析。此模型比实际缓存的特征（具有复杂的关联性、替换策略等）更容易分析，但在许多情况下，可以证明在更真实的缓存性能的恒定因子内。它与外部内存模型不同，因为忽略缓存的算法不知道块大小或缓存大小。

In particular, the cache-oblivious model is an abstract machine (i.e., a theoretical(i.e., a theoretical model of computation ). It is similar to the RAM machine model which replaces the Turing machine

's infinite tape with an infinite array. Each location within the array can be accessed in time, similar to the random-access memory on a real computer. Unlike the RAM machine model, it also introduces a cache: the second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:

特别是，忽略缓存模型是一台抽象机器（即计算的理论模型）。它类似于RAM机器模型，它用无限数组替换了图灵机的无限磁带。数组中的每个位置都可以及时访问，类似于真实计算机上的随机存取存储器。与 RAM 机器模型不同，它还引入了缓存：RAM 和 CPU 之间的第二级存储。下面列出了两种型号之间的其他区别。在忽略缓存的模型中：

为了衡量在忽略缓存的模型中执行的算法的复杂性，我们测量算法经历的缓存未命中次数。由于该模型捕获了访问缓存中的元素比访问主内存中的事物快得多的事实，因此算法的运行时间仅由缓存和主内存之间的内存传输数定义。这类似于外部存储器模型，其具有上述所有功能，但忽略缓存的算法独立于缓存参数（ � 和 � ）。这种算法的好处是，在忽略缓存的机器上有效的算法很可能在许多真实机器上是有效的，而无需对特定的真实机器参数进行微调。对于许多问题，对于具有两个以上内存层次结构级别的计算机，最佳缓存忽略算法也是最佳算法。

An empirical comparison of 2 RAM-based, 1 cache-aware, and 2 cache-oblivious algorithms implementing priority queues found that:

对实现优先级队列的 2 种基于 RAM、1 种缓存感知算法和 2 种缓存忽略算法的经验比较发现：

• Cache-oblivious algorithms performed worse than RAM-based and cache-aware algorithms when data fits into main memory.

  当数据适合主内存时，忽略缓存的算法的性能比基于 RAM 和缓存感知的算法差。

• The cache-aware algorithm did not seem significantly more complex to implement than the cache-oblivious algorithms, and offered the best performance in all cases tested in the study.

  缓存感知算法的实现似乎并不比忽略缓存的算法复杂得多，并且在研究中测试的所有情况下都提供了最佳性能。

• Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory.

  当数据大小超过主内存大小时，缓存遗忘算法的性能优于基于 RAM 的算法。

Another study compared hash tables (as RAM-based or cache-unaware), B-trees (as cache-aware), and a cache-oblivious data structure referred to as a "Bender set". For both execution time and memory usage, the hash table was best, followed by the B-tree, with the Bender set the worst in all cases. The memory usage for all tests did not exceed main memory. The hash tables were described as easy to implement, while the Bender set "required a greater amount of effort to implement correctly".

另一项研究比较了哈希表（基于RAM或缓存感知），B树（缓存感知）和称为“弯曲集”的缓存遗忘数据结构。对于执行时间和内存使用情况，哈希表是最好的，其次是 B 树，在所有情况下，Bender 设置的最差。所有测试的内存使用量均未超过主内存。哈希表被描述为易于实现，而 Bender 集“需要更大的努力才能正确实现”。

A cache stampede is a type of cascading failure that can occur when massively parallel computing systems with caching mechanisms come under a very high load. This behaviour is sometimes also called dog-piling.

缓存踩踏是一种级联故障，当具有缓存机制的大规模并行计算系统承受非常高的负载时，可能会发生这种故障。这种行为有时也称为狗堆。

To understand how cache stampedes occur, consider a web server that uses memcached to cache rendered pages for some period of time, to ease system load. Under particularly high load to a single URL, the system remains responsive as long as the resource remains cached, with requests being handled by accessing the cached copy. This minimizes the expensive rendering operation.

要了解缓存踩踏是如何发生的，请考虑使用 memcached 将呈现的页面缓存一段时间的 Web 服务器，以减轻系统负载。在单个 URL 的负载特别高的情况下，只要资源保持缓存状态，系统就会保持响应，并通过访问缓存的副本来处理请求。这最大限度地减少了昂贵的渲染操作。

Under low load, cache misses result in a single recalculation of the rendering operation. The system will continue as before, with the average load being kept very low because of the high cache hit rate.

在低负载下，缓存未命中会导致渲染操作的单次重新计算。系统将像以前一样继续，由于缓存命中率高，平均负载保持在非常低的水平。

However, under very heavy load, when the cached version of that page expires, there may be sufficient concurrency in the server farm that multiple threads of execution will all attempt to render the content of that page simultaneously. Systematically, none of the concurrent servers know that the others are doing the same rendering at the same time. If sufficiently high load is present, this may by itself be enough to bring about congestion collapse of the system via exhausting shared resources. Congestion collapse results in preventing the page from ever being completely re-rendered and re-cached, as every attempt to do so times out. Thus, cache stampede reduces the cache hit rate to zero and keeps the system continuously in congestion collapse as it attempts to regenerate the resource for as long as the load remains very heavy.

但是，在非常重的负载下，当该页面的缓存版本过期时，服务器场中可能有足够的并发性，多个执行线程将尝试同时呈现该页面的内容。从系统上讲，没有一个并发服务器知道其他服务器同时在执行相同的渲染。如果存在足够高的负载，这本身可能足以通过耗尽共享资源来导致系统的拥塞崩溃。拥塞折叠会导致阻止页面完全重新呈现和重新缓存，因为每次尝试这样做都会超时。因此，缓存踩踏将缓存命中率降低到零，并使系统持续处于拥塞崩溃状态，因为它试图重新生成资源，只要负载仍然非常重。

To give a concrete example, assume the page in consideration takes 3 seconds to render and we have a traffic of 10 requests per second. Then, when the cached page expires, we have 30 processes simultaneously recomputing the rendering of the page and updating the cache with the rendered page.

举一个具体的例子，假设所考虑的页面需要 3 秒才能呈现，并且我们的流量为每秒 10 个请求。然后，当缓存的页面过期时，我们有 30 个进程同时重新计算页面的呈现并使用呈现的页面更新缓存。

Below is a typical cache usage pattern for an item that needs to be updated every ttl units of time:

以下是需要每 ttl 时间单位更新的项目的典型缓存使用模式：

function fetch(key,ttl) {
value ← cache_read(key)
if (!value) {
value ← recompute_value()
        cache_write(key,value,ttl)
    }
returnvalue
}

If the function recompute_value() takes a long time and the key is accessed frequently, many processes will simultaneously call recompute_value() upon expiration of the cache value.

如果函数 recompute_value（） 需要很长时间并且频繁访问密钥，则许多进程将在缓存值到期时同时调用 recompute_value（）。

In typical web applications, the function recompute_value() may query a database, access other services, or perform some complicated operation (which is why this particular computation is being cached in the first place). When the request rate is high, the database (or any other shared resource) will suffer from an overload of requests/queries, which may in turn cause a system collapse.

在典型的 Web 应用程序中，函数 recompute_value（） 可以查询数据库、访问其他服务或执行一些复杂的操作（这就是首先缓存此特定计算的原因）。当请求速率较高时，数据库（或任何其他共享资源）将遭受请求/查询过载，这反过来可能导致系统崩溃。

Several approaches have been proposed to mitigate cache stampedes (also known as dogpile prevention). They can be roughly grouped in 3 main categories.

已经提出了几种方法来减轻缓存踩踏（也称为狗堆预防）。它们可以大致分为 3 个主要类别。

To prevent multiple simultaneous recomputations of the same value, upon a cache miss a process will attempt to acquire the lock for that cache key and recompute it only if it acquires it.

为了防止同时重新计算同一值，在缓存未命中时，进程将尝试获取该缓存键的锁，并仅在获取该锁时才重新计算它。

There are different implementation options for the case when the lock is not acquired:

对于未获取锁的情况，有不同的实现选项：

• Wait until the value is recomputed

  等到重新计算值

• Return a "not-found" and have the client handle the absence of the value properly

  返回“未找到”，并让客户端正确处理缺少值的情况

• Keep a stale item in the cache to be used while the new value is recomputed

  在缓存中保留一个过时的项目，以便在重新计算新值时使用

If implemented properly, locking can prevent stampedes altogether, but requires an extra write for the locking mechanism. Apart from doubling the number of writes, the main drawback is a correct implementation of the locking mechanism which also takes care of edge cases including failure of the process acquiring the lock, tuning of a time-to-live for the lock, race-conditions, and so on.

如果实施得当，锁定可以完全防止踩踏，但需要对锁定机制进行额外的写入。除了使写入次数加倍之外，主要缺点是锁定机制的正确实现，该机制还可以处理边缘情况，包括获取锁的过程失败、调整锁的生存时间、竞争条件等。

This solution moves the recomputation of the cache value from the processes needing it to an external process. The recomputation of the external process can be triggered in different ways:

此解决方案将缓存值的重新计算从需要它的进程移动到外部进程。外部进程的重新计算可以通过不同的方式触发：

• When the cache value approaches its expiration

  当缓存值接近到期时

• Periodically

  周期性地

• When a process needing the value encounters a cache miss

  当需要该值的进程遇到缓存未命中时

This approach requires one more moving part - the external process - that needs to be maintained and monitored. In addition, this solution requires unnatural code separation/duplication and is mostly suited for static cache keys (i.e., not dynamically generated, as in the case of keys indexed by an id).

这种方法需要另一个活动部分 - 外部过程 - 需要维护和监控。此外，此解决方案需要非自然的代码分离/复制，并且主要适用于静态缓存键（即，不是动态生成的，如按 id 索引的键）。

With this approach, each process may recompute the cache value before its expiration by making an independent probabilistic decision, where the probability of performing the early recomputation increases as we get closer to the expiration of the value. Since the probabilistic decision is made independently by each process, the effect of the stampede is mitigated as fewer processes will expire at the same time.

使用这种方法，每个进程都可以通过做出独立的概率决策来在缓存值到期之前重新计算缓存值，其中执行早期重新计算的概率随着我们接近值到期而增加。由于概率决策是由每个进程独立做出的，因此可以减轻踩踏的影响，因为同时过期的进程将减少。

The following implementation based on an exponential distribution has been shown to be optimal in terms of its effectiveness in preventing stampedes and how early recomputations can happen.

以下基于指数分布的实现已被证明在防止踩踏事件的有效性以及如何进行早期重新计算方面是最佳的

function x-fetch(key,ttl,beta=1) {
value,delta,expiry ← cache_read(key)
if (!value || (time() -delta *beta * log(rand(0,1))) ≥expiry) {
start ← time()
value ← recompute_value()
delta ← time() – start
        cache_write(key, (value,delta),ttl)
    }
returnvalue
}

The parameter beta can be set to a value greater than 1 to favor earlier recomputations and further reduce stampedes but the authors show that setting beta=1 works well in practice. The variable delta represents the time to recompute the value and is used to scale the probability distribution appropriately.

参数 beta 可以设置为大于 1 的值，以支持早期的重新计算并进一步减少踩踏事件，但作者表明，设置 beta=1 在实践中效果很好。变量 delta 表示重新计算值的时间，用于适当地缩放概率分布。

This approach is simple to implement and effectively reduces cache stampedes by automatically favoring early recomputations when the traffic rate increases. One drawback is that it takes more memory in cache as we need to bundle the value delta with the cache item - when the caching system does not support retrieval of the key expiration time, we also need to store the expiry (that is, time() + ttl) in the bundle.

此方法易于实现，通过在流量速率增加时自动支持早期重新计算来有效减少缓存踩踏。一个缺点是缓存中需要更多的内存，因为我们需要将值增量与缓存项捆绑在一起 - 当缓存系统不支持检索密钥过期时间时，我们还需要将过期（即 time（） + ttl）存储在捆绑包中

Database caching is a process included in the design of computer applications which generate web pages on-demand (dynamically) by accessing backend databases.

数据库缓存是计算机应用程序设计中包含的过程，它通过访问后端数据库按需（动态）生成网页。

When these applications are deployed on multi-tier environments that involve browser-based clients, web application servers and backend databases, middle-tier database caching is used to achieve high scalability and performance.

当这些应用程序部署在涉及基于浏览器的客户端、Web 应用程序服务器和后端数据库的多层环境中时，使用中间层数据库缓存来实现高可扩展性和性能。

In a three tier architecture, the application software tier and data storage tier can be in different hosts. Throughput of an application can be limited by the network speed. This limitation can be minimized by having the database at the application tier. Because commercial database software makes extensive use of system resources, it is not always practical to have the application and the database at the same host. In this case, a more light-weight database application can be used to cache data from the commercial database management system.

在三层体系结构中，应用软件层和数据存储层可以位于不同的主机中。应用程序的吞吐量可能受到网络速度的限制。通过将数据库置于应用程序层，可以最大程度地减少此限制。由于商业数据库软件广泛使用系统资源，因此将应用程序和数据库放在同一个主机上并不总是可行的。在这种情况下，可以使用更轻量级的数据库应用程序来缓存来自商业数据库管理系统的数据。

Database caching improves scalability by distributing query workload from backend to multiple cheap front-end systems. It allows flexibility in the processing of data; for example, the data of Platinum customers can be cached while that of ordinary customers are not. Caching can improve availability of data, by providing continued service for applications that depend only on cached tables even if the backend server is unavailable. Another benefit is improved data access speeds brought about by locality of data and smoothing out load peaks by avoiding round-trips between middle-tier and data-tier.

数据库缓存通过将查询工作负载从后端分配到多个廉价的前端系统来提高可伸缩性。它允许灵活处理数据;例如，白金客户的数据可以缓存，而普通客户的数据则不然。缓存可以为仅依赖于缓存表的应用程序提供持续服务，即使后端服务器不可用，缓存也可以提高数据的可用性。另一个好处是提高了数据局部性带来的数据访问速度，并通过避免中间层和数据层之间的往返来平滑负载峰值。

• Updateable cache tables: Many cache systems are read-only which limits their usage to small segment of the applications, non-real time applications.

  可更新的缓存表：许多缓存系统是只读的，这限制了它们的使用，即一小部分应用程序，即非实时应用程序。

• Bi-Directional updates: For updateable caches, updates, which happen in cache, should be propagated to the target database and any updates that happen directly on the target database should come to cache automatically.

  双向更新：对于可更新的缓存，缓存中发生的更新应传播到目标数据库，并且直接在目标数据库上发生的任何更新都应自动进入缓存。

• Synchronous and asynchronous update propagation: The updates on cache table shall be propagated to target database in two modes. Synchronous mode makes sure that after the database operation completes the updates are applied at the target database as well. In case of Asynchronous mode the updates are delayed to the target database. Synchronous mode gives high cache consistency and is suited for real time applications. Asynchronous mode gives high throughput and is suited for near real time applications.

  同步和异步更新传播：缓存表上的更新应以两种模式传播到目标数据库。同步模式确保在数据库操作完成后，更新也会应用于目标数据库。在异步模式下，更新将延迟到目标数据库。同步模式提供高缓存一致性，适用于实时应用程序。异步模式提供高吞吐量，适用于近实时应用。

• Multiple cache granularity - Database level, Table level and Result-set caching: Major portions of corporate databases are historical and infrequently accessed. But, there is some information that should be instantly accessible like premium customer's data, etc.

  多缓存粒度 - 数据库级别、表级别和结果集缓存：公司数据库的主要部分是历史的，很少访问。但是，有些信息应该可以立即访问，例如高级客户的数据等。

• Recovery for cached tables: In case of system or power failure, during the restart of caching platform all the committed transactions on the cached tables should be recovered.

  缓存表的恢复：如果发生系统或电源故障，在缓存平台重新启动期间，应恢复缓存表上所有已提交的事务。

• Tools to validate the coherence of cache: In case of asynchronous mode of update propagation, cache at different cache nodes and target database may diverge. This needs to be resolved manually, with mismatches identified and corrective measures taken if required.

  验证缓存一致性的工具：在更新传播的异步模式下，不同缓存节点和目标数据库上的缓存可能会有所不同。这需要手动解决，识别不匹配并在需要时采取纠正措施。

• Horizontally scalable: Cluster computing may increase availability and achieve load balancing. Caching in a clustered environment spans multiple nodes, keeping the cached data coherent across nodes.

  水平可扩展：集群计算可以提高可用性并实现负载均衡。群集环境中的缓存跨越多个节点，使缓存的数据在节点之间保持一致。

• Transparent access to non-cached tables reside in target database: Database cache should keep track of queries and should be able to intelligently route to the database cache or to the origin database based on the data locality without any application code modification.

  对驻留在目标数据库中的非缓存表的透明访问：数据库缓存应跟踪查询，并且应该能够根据数据局部性智能地路由到数据库缓存或源数据库，而无需修改任何应用程序代码。

• Transparent Fail over: There should not be any service outages in case of caching platform failure. Client connections should be routed to the target database.

  透明故障转移：在缓存平台发生故障时，不应有任何服务中断。客户端连接应路由到目标数据库。

• No or very few changes to application: Support for standard interfaces JDBC, ODBC etc. that will make the application to work seamlessly without any application code changes. It should route all stored procedure calls to target database so that they don't need to be migrated.

  对应用程序没有或很少的更改：支持标准接口JDBC，ODBC等，这将使应用程序无缝工作，而无需任何应用程序代码更改。它应将所有存储过程调用路由到目标数据库，以便不需要迁移它们。

• Cache walking on deletes or invalidation events: Cache designs that leverage external cache engines such as Redis or Hazelcast will often trigger invalidation by issuing deletions against the invalidated objects. This could result in a single write operation triggering thousands of deletes, impacting performance.

  缓存遍历删除或失效事件：利用外部缓存引擎（如 Redis 或 Hazelcast）的缓存设计通常会通过对失效对象发出删除来触发失效。这可能会导致单个写入操作触发数千次删除，从而影响性能。

• Lack of key tracking: Again, if using an external cache engine, any request will often trigger a key lookup at the cache layer. If this is a miss, it can trigger an extra RTT, adding to the overall latency of requests. Engines such as Redis and Hazelcast provide for key change notification support however, allowing local cache layers to be updated when keys are changed in a remote cache layer. By tracking these keys locally, remote lookups on a cache miss can be avoided, preventing a cache hit penalty.

  缺少密钥跟踪：同样，如果使用外部缓存引擎，任何请求通常会触发缓存层的密钥查找。如果这是未命中，它可能会触发额外的 RTT，从而增加请求的整体延迟。但是，Redis 和 Hazelcast 等引擎提供密钥更改通知支持，允许在远程缓存层中更改密钥时更新本地缓存层。通过在本地跟踪这些键，可以避免对缓存未命中进行远程查找，从而防止缓存命中损失。

• Invalidation as an instant event, not a time range: When a table is to be changed as part of a transaction, the SQL mode can impact if a query on another connection should see the changes or not. As such, while a transaction hasn't yet been committed or rolled back, any change against a table during the transaction should trigger the table to be considered volatile until the transaction is completed. Often, cache engines will only invalidate a result before or after the query is executed.

  作为即时事件而非时间范围的失效：当表作为事务的一部分进行更改时，SQL 模式可能会影响另一个连接上的查询是否应看到更改。因此，虽然事务尚未提交或回滚，但在事务完成之前，事务期间对表的任何更改都应触发表被视为易失性。通常，缓存引擎只会在执行查询之前或之后使结果失效。

• Distributed caches w/ lack of communication: If a cache design is using an underlying storage layer, when used as a distributed cache, invalidations are done locally, based on what tables are written to at a given time. Unfortunately, other nodes may have written cache objects for the same table, and these objects won't be invalidated. When used for local session data with upstream client persistence, this may be acceptable, but for shared data that needs to maintain consistency across sessions, this can cause data consistency problems.

  缺乏通信的分布式缓存：如果缓存设计使用底层存储层，则在用作分布式缓存时，将根据给定时间写入的表在本地完成失效。遗憾的是，其他节点可能为同一表写入了缓存对象，并且这些对象不会失效。当用于具有上游客户端持久性的本地会话数据时，这可能是可以接受的，但对于需要在会话之间保持一致性的共享数据，这可能会导致数据一致性问题