离线缓存

缓存问题源于有限空间的限制。让我们假设我们的缓存 Ck 页面。现在我们要处理一系列 m 项请求,这些请求必须在处理之前放入缓存中。当然,如果 m<=k 然后我们只是将所有元素放在缓存中它会起作用,但通常是 m>>k

当项目已经在缓存中时,我们说请求是缓存命中,否则称为缓存未命中。在这种情况下,我们必须将请求的项目带入缓存并逐出另一个,假设缓存已满。目标是一种驱逐计划,可以最大限度地减少驱逐次数

这个问题有很多贪婪的策略,让我们来看看:

  1. 先进先出(FIFO) :最旧的页面被逐出
  2. 最后,先出(LIFO) :最新页面被逐出
  3. 最近出版(LRU) :最近访问最早的 Evict 页面
  4. 最不经常请求(LFU)最不常请求的 Evict 页面
  5. 最长前向距离(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];
}

基本想法很简单:对于每个请求,我有两个调用两个我的策略:

  1. apply :策略必须告诉调用者使用哪个页面
  2. 更新 :调用者使用该位置后,它会告诉策略是否是未命中。然后策略可以更新其内部数据。例如,策略 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 策略是最优的,但有一个很大的问题。它是最佳的离线解决方案。在实践中,缓存通常是一个在线问题,这意味着策略是无用的,因为我们现在不能在下次需要特定项目时使用。其他四种策略也是在线策略。对于在线问题,我们需要一种不同的方法。