缓存算法

缓存算法是一种用于管理缓存或一组数据的算法。当缓存满了的时候，它决定应该从缓存中删除哪个项目。命中率这个词描述了一个请求可以从缓存中被服务的频率。术语延迟描述了多长时间可以获得一个缓存项目。缓存算法是命中率和延迟之间的权衡。

• 最有效的缓存算法将是始终丢弃未来最长时间内不需要的信息。这种最优结果被称为Belady最优算法或千里眼算法。由于一般无法预测未来多长时间内需要的信息，所以在实际中一般无法实现。只有经过实验才能计算出实际的最小值，人们可以将实际选择的缓存算法与最优最小值的效果进行比较。
• 最近最少使用（LRU）：先删除最近最少使用的项目。这个算法需要跟踪什么时候用过的东西。如果想确保算法总是丢弃最近使用最少的项目，这是很昂贵的。这种技术的一般实现需要为缓存线保留"年龄位"，并根据年龄位跟踪"最近使用的最少的"缓存线。在这样的实现中，每当一个缓存线被使用，其他所有缓存线的年龄就会发生变化。LRU实际上是一个缓存算法家族，成员包括：。Theodore Johnson和Dennis Shasha的2Q和Pat O'Neil、Betty O'Neil和Gerhard Weikum的LRU/K。
• 最近使用的项目（MRU）。这种算法首先删除最近使用的项目。这种缓存机制通常用于数据库内存缓存。
• 伪LRU（PLRU）。在某些情况下，LRU很难实现。在这种情况下，可能只要知道在大多数情况下，最近使用最少的一个项目被删除就够了。PLRU算法可以用在那里，因为它只需要每个缓存项有一个位就可以工作。

• 2路集关联：适用于高速CPU缓存，连PLRU都嫌慢的地方。新项目的地址被用来计算缓存中两个可能的位置中的一个，它被允许去。两个中的LRU被丢弃。这需要每对缓存行一个位，来表示两个中哪个是最近使用的最少的。
• 直接映射式缓存：适用于速度最高的CPU缓存，在这种情况下，即使是2路集关联缓存也太慢了。新项目的地址被用来计算缓存中允许它去的一个位置。不管之前的东西都会被丢弃。
• 最不常使用（LFU）。LFU是指计算一件物品的使用频率。最不常使用的物品首先被丢弃。
• 自适应替换缓存(ARC)：在LRU和LFU之间不断平衡，以提高综合效果。
• 多队列（MQ）缓存算法。(作者：Y. Zhou J.F. Philbin和Kai Li)。

其他需要考虑的事情。

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

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

问题和答案

按字母搜索