离线缓存
缓存问题源于有限空间的限制。让我们假设我们的缓存 C 有 k 页面。现在我们要处理一系列 m 项请求，这些请求必须在处理之前放入缓存中。当然，如果 m<=k 然后我们只是将所有元素放在缓存中它会起作用，但通常是 m>>k。
当项目已经在缓存中时，我们说请求是缓存命中，否则称为缓存未命中。在这种情况下，我们必须将请求的项目带入缓存并逐出另一个，假设缓存已满。目标是一种驱逐计划，可以最大限度地减少驱逐次数。
这个问题有很多贪婪的策略，让我们来看看：
- 先进先出（FIFO） ：最旧的页面被逐出
- 最后，先出（LIFO） ：最新页面被逐出
- 最近出版（LRU） ：最近访问最早的 Evict 页面
- 最不经常请求（LFU） ： 最不常请求的 Evict 页面
- 最长前向距离（LFD） ：缓存中的 Evict 页面，直到将来最远才会请求。
注意： 对于以下示例，如果可以驱逐多个页面，我们将逐出具有最小索引的页面。
示例（FIFO）
让缓存大小为 k=3 初始缓存 a,b,c 和请求 a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c：
| 请求 | 一个 | 一个 | d | Ë | b | b | 一个 | C | F | d | Ë | 一个 | F | b | Ë | C |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
cache 1 |
一个 | 一个 | d | d | d | d | 一个 | 一个 | 一个 | d | d | d | F | F | F | C |
cache 2 |
b | b | b | Ë | Ë | Ë | Ë | C | C | C | Ë | Ë | Ë | b | b | b |
cache 3 |
C | C | C | C | b | b | b | b | F | F | F | 一个 | 一个 | 一个 | Ë | Ë |
| 缓存未命中 | X | X | X | X | X | X | X | X | X | X | X | X | X |
十六个请求中的十三个缓存未命中听起来不是最理想的，让我们尝试使用另一个策略的相同示例：
示例（LFD）
让缓存大小为 k=3 初始缓存 a,b,c 和请求 a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c：
| 请求 | 一个 | 一个 | d | Ë | b | b | 一个 | C | F | d | Ë | 一个 | F | b | Ë | C |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
cache 1 |
一个 | 一个 | d | Ë | Ë | Ë | Ë | Ë | Ë | Ë | Ë | Ë | Ë | Ë | Ë | C |
cache 2 |
b | b | b | b | b | b | 一个 | 一个 | 一个 | 一个 | 一个 | 一个 | F | F | F | F |
cache 3 |
C | C | C | C | C | C | C | C | F | d | d | d | d | b | b | b |
| 缓存未命中 | X | X | X | X | X | X | X | X |
八次缓存未命中要好得多。
Selftest ：做 LIFO，LFU，RFU 的例子，看看发生了什么。
以下示例程序（用 C++编写）由两部分组成：
骨架是一个应用程序，它解决了依赖于所选择的贪婪策略的问题：
#include <iostream>
#include <memory>
using namespace std;
const int cacheSize = 3;
const int requestLength = 16;
const char request[] = {'a','a','d','e','b','b','a','c','f','d','e','a','f','b','e','c'};
char cache[] = {'a','b','c'};
// for reset
char originalCache[] = {'a','b','c'};
class Strategy {
public:
Strategy(std::string name) : strategyName(name) {}
virtual ~Strategy() = default;
// calculate which cache place should be used
virtual int apply(int requestIndex) = 0;
// updates information the strategy needs
virtual void update(int cachePlace, int requestIndex, bool cacheMiss) = 0;
const std::string strategyName;
};
bool updateCache(int requestIndex, Strategy* strategy)
{
// calculate where to put request
int cachePlace = strategy->apply(requestIndex);
// proof whether its a cache hit or a cache miss
bool isMiss = request[requestIndex] != cache[cachePlace];
// update strategy (for example recount distances)
strategy->update(cachePlace, requestIndex, isMiss);
// write to cache
cache[cachePlace] = request[requestIndex];
return isMiss;
}
int main()
{
Strategy* selectedStrategy[] = { new FIFO, new LIFO, new LRU, new LFU, new LFD };
for (int strat=0; strat < 5; ++strat)
{
// reset cache
for (int i=0; i < cacheSize; ++i) cache[i] = originalCache[i];
cout <<"\nStrategy: " << selectedStrategy[strat]->strategyName << endl;
cout << "\nCache initial: (";
for (int i=0; i < cacheSize-1; ++i) cout << cache[i] << ",";
cout << cache[cacheSize-1] << ")\n\n";
cout << "Request\t";
for (int i=0; i < cacheSize; ++i) cout << "cache " << i << "\t";
cout << "cache miss" << endl;
int cntMisses = 0;
for(int i=0; i<requestLength; ++i)
{
bool isMiss = updateCache(i, selectedStrategy[strat]);
if (isMiss) ++cntMisses;
cout << " " << request[i] << "\t";
for (int l=0; l < cacheSize; ++l) cout << " " << cache[l] << "\t";
cout << (isMiss ? "x" : "") << endl;
}
cout<< "\nTotal cache misses: " << cntMisses << endl;
}
for(int i=0; i<5; ++i) delete selectedStrategy[i];
}
基本想法很简单：对于每个请求，我有两个调用两个我的策略：
- apply ：策略必须告诉调用者使用哪个页面
- 更新 ：调用者使用该位置后，它会告诉策略是否是未命中。然后策略可以更新其内部数据。例如，策略 LFU 必须更新缓存页面的命中频率，而 LFD 策略必须重新计算缓存页面的距离。
现在让我们看看我们的五个策略的示例实现：
FIFO
class FIFO : public Strategy {
public:
FIFO() : Strategy("FIFO")
{
for (int i=0; i<cacheSize; ++i) age[i] = 0;
}
int apply(int requestIndex) override
{
int oldest = 0;
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
else if(age[i] > age[oldest])
oldest = i;
}
return oldest;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
// nothing changed we dont need to update the ages
if(!cacheMiss)
return;
// all old pages get older, the new one get 0
for(int i=0; i<cacheSize; ++i)
{
if(i != cachePos)
age[i]++;
else
age[i] = 0;
}
}
private:
int age[cacheSize];
};
FIFO 只需要信息页面在缓存中的长度（当然仅相对于其他页面）。因此，唯一要做的就是等待错过，然后制作页面，这些页面在没有被驱逐的情况下更老。对于上面的示例，程序解决方案是：
Strategy: FIFO
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d d b c x
e d e c x
b d e b x
b d e b
a a e b x
c a c b x
f a c f x
d d c f x
e d e f x
a d e a x
f f e a x
b f b a x
e f b e x
c c b e x
Total cache misses: 13
这确切地说是上面的解决方案。
LIFO
class LIFO : public Strategy {
public:
LIFO() : Strategy("LIFO")
{
for (int i=0; i<cacheSize; ++i) age[i] = 0;
}
int apply(int requestIndex) override
{
int newest = 0;
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
else if(age[i] < age[newest])
newest = i;
}
return newest;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
// nothing changed we dont need to update the ages
if(!cacheMiss)
return;
// all old pages get older, the new one get 0
for(int i=0; i<cacheSize; ++i)
{
if(i != cachePos)
age[i]++;
else
age[i] = 0;
}
}
private:
int age[cacheSize];
};
实施 LIFO 是或多或少相同的 FIFO ，但我们退出的最年轻不是最古老的页面。该计划的结果是：
Strategy: LIFO
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d d b c x
e e b c x
b e b c
b e b c
a a b c x
c a b c
f f b c x
d d b c x
e e b c x
a a b c x
f f b c x
b f b c
e e b c x
c e b c
Total cache misses: 9
LRU
class LRU : public Strategy {
public:
LRU() : Strategy("LRU")
{
for (int i=0; i<cacheSize; ++i) age[i] = 0;
}
// here oldest mean not used the longest
int apply(int requestIndex) override
{
int oldest = 0;
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
else if(age[i] > age[oldest])
oldest = i;
}
return oldest;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
// all old pages get older, the used one get 0
for(int i=0; i<cacheSize; ++i)
{
if(i != cachePos)
age[i]++;
else
age[i] = 0;
}
}
private:
int age[cacheSize];
};
在 LRU 的情况下，策略独立于缓存页面，其唯一的兴趣是最后一次使用。该计划的结果是：
Strategy: LRU
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d a d c x
e a d e x
b b d e x
b b d e
a b a e x
c b a c x
f f a c x
d f d c x
e f d e x
a a d e x
f a f e x
b a f b x
e e f b x
c e c b x
Total cache misses: 13
LFU
class LFU : public Strategy {
public:
LFU() : Strategy("LFU")
{
for (int i=0; i<cacheSize; ++i) requestFrequency[i] = 0;
}
int apply(int requestIndex) override
{
int least = 0;
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
else if(requestFrequency[i] < requestFrequency[least])
least = i;
}
return least;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
if(cacheMiss)
requestFrequency[cachePos] = 1;
else
++requestFrequency[cachePos];
}
private:
// how frequently was the page used
int requestFrequency[cacheSize];
};
LFU 驱逐页面使用最少。所以更新策略只是计算每次访问。当然，在计数失败后，计数重置。该计划的结果是：
Strategy: LFU
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d a d c x
e a d e x
b a b e x
b a b e
a a b e
c a b c x
f a b f x
d a b d x
e a b e x
a a b e
f a b f x
b a b f
e a b e x
c a b c x
Total cache misses: 10
LFD
class LFD : public Strategy {
public:
LFD() : Strategy("LFD")
{
// precalc next usage before starting to fullfill requests
for (int i=0; i<cacheSize; ++i) nextUse[i] = calcNextUse(-1, cache[i]);
}
int apply(int requestIndex) override
{
int latest = 0;
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
else if(nextUse[i] > nextUse[latest])
latest = i;
}
return latest;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
nextUse[cachePos] = calcNextUse(requestIndex, cache[cachePos]);
}
private:
int calcNextUse(int requestPosition, char pageItem)
{
for(int i = requestPosition+1; i < requestLength; ++i)
{
if (request[i] == pageItem)
return i;
}
return requestLength + 1;
}
// next usage of page
int nextUse[cacheSize];
};
该 LFD 策略是大家以前不同。它是唯一使用未来要求驱逐的人的策略。该实现使用函数 calcNextUse 来获取下一次使用最远的页面。程序解决方案等同于上面的解决方案：
Strategy: LFD
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d a b d x
e a b e x
b a b e
b a b e
a a b e
c a c e x
f a f e x
d a d e x
e a d e
a a d e
f f d e x
b b d e x
e b d e
c c d e x
Total cache misses: 8
贪婪策略 LFD 确实是所提出的五种策略中唯一的最佳策略。证据相当长，可以在这里或 Jon Kleinberg 和 Eva Tardos 的书中找到 （参见下面的评论中的来源）。
算法与现实
该 LFD 策略是最优的，但有一个很大的问题。它是最佳的离线解决方案。在实践中，缓存通常是一个在线问题，这意味着策略是无用的，因为我们现在不能在下次需要特定项目时使用。其他四种策略也是在线策略。对于在线问题，我们需要一种不同的方法。