03 Cache问题

Cache问题

考虑下面这个高速缓存(Cache)的问题：有一个大小为$k$的cache（也即cache内能存$k$个页），现在用户依次请求访问$n$个页：$x_1,\cdots,x_n$。每当用户请求一个页的时候，如果这个页在cache当中，就称为cache hit，否则称为cache miss。如果cache miss发生，我们需要把当前页加入到cache当中，如果cache已满，就需要决策踢走一个cache中的页，替换为当前页。这是一个在线算法问题：应当如何制定页的踢出的策略，来使得在$n$个request以后总的cache miss次数最少？

这个问题的$\text{OPT}$应当如何设计呢？也即如果提前知道所有页请求的数据， 该如何决策踢出哪个页呢？容易发现这样的事实：对于当前cache中的$k$个页，如果某个页之后再也不会被访问了，那么直接踢出即可。类似的道理，如果某个页将会是最晚被访问的，那么踢出它一定不会比踢出别的页产生更多的cache miss（真的吗？仔细思考）。

对于在线的情况下，我们无法预测未来的页访问顺序，因此无法踢出将被最迟访问的那个页。对于这个问题，人们提出了很多算法：先进先出算法(First In First Out, FIFO)认为应当踢出当前cache中最早存进来的那个页；后进先出算法(Last In First Out, LIFO)认为应当踢出当前cache中最晚存进来的那个页；最近最早访问算法(Least Recently Used, LRU)认为应当踢出当前cache中上一次访问时间最远的那个页；最近最少访问算法(Least Frequently Used, LFU)认为应当踢出当前cache中从存进来以后开始计算被cache hit击中次数最早的那个页；……

LIFO

对于后进先出算法(LIFO)，我们可以构造这样一个输入：cache大小$k=2$，页访问顺序为1 2 3 2 3 2 3……。对于$\text{OPT}$，初始为空，访问1和$2$时miss，访问$3$时miss，同时踢出再也不会被访问的$1$，从此再也没有cache miss，可见$\text{OPT}$的miss数量为$3$。然而对于LIFO，在存下1 2以后，进入3会踢出2，进入2又会踢出3，可见每一次都会miss，总数为$n$。由此可得竞争比为$\dfrac{n}{3}$，当$n\to\infty$时趋向无穷。可见这是一个不可接受的算法。

LFU

最近最少访问算法(LFU)也是不好的！构造这样一个长度为$2m+2$的输入：1 2 1 1 1 …… 1 1 （$m$个）3 2 3 2 …… 3 2（$m$个）。对于$\text{OPT}$，初始时产生2个miss，在第一个3进入时miss，踢出1存入3，然后就再也不会miss，依然共miss 3次。而对于LFU，初始时miss两次，当第一个3进入时，发现1已经cache hit了$m+1$次，所以1是不容踢出的，踢出2；下一个2进入时，再踢出3……共产生$m+2$个miss。可见竞争比为$\dfrac{m+2}{3}$，依然会趋向无穷。

LRU & FIFO

相对于LIFO和LFU，LRU和FIFO在最坏情况下表现优秀得多。我们证明这两个算法的竞争比不超过$k$，也就是cache大小。

考虑任意的一个页请求序列，从第一个请求到第一次出现第$k+1$个不同的页之前，$\text{OPT}$和$\text{ALG}$都最多miss $k$次。我们称以上部分为phase 0。接下来重新计数，在下一次出现第$k+1$个不同的页之前称为phase 1；再重新计数，在下一次出现第$k+1$个不同的页之前称为phase 2；……我们注意到，对于任何一个phase $i$，$i>0$，在phase $i+1$的第一个请求发生以后，$\text{OPT}$一定会增加1个miss（不然存不下）；而在phase $i$之内，LRU算法或是FIFO算法如果需要踢走某个页，那这个页一定是上一个phase残留下来的页，因此总共不超过$k$个。综上，对于每个phase，$\text{ALG}$的miss数量都不超过$\text{OPT}$的$k$倍，因此竞争比不超过$k$。

竞争比$k$对于LRU和FIFO算法来说是tight的。考虑以下请求顺序：1 2 3 4 $\cdots k \ k+1$ 1 2 3 4 $\cdots k \ k+1\cdots$，请求刚好以1 2 3 4 $\cdots k$为一个phase。对于phase 1，$\text{OPT}$会把$k$踢走放进$k+1$，接下来都不会miss；对于phase 2，会把$k-1$踢走放进$k$，接下来都不会miss；也即$\text{OPT}$每个phase只会miss 1次。然而LRU在phase 1 $k+1$进来时会踢走1，1进来时踢走2……每个都发生miss。可见竞争比恰好为$k$（由于第一个phase大家的miss相同，因此这是在序列趋向无穷的意义下说的）。

Marking算法

能否通过引入随机性，在期望意义下达到比$k$更优的竞争比呢？我们考虑这样一个算法：算法能够主动按照上一节的分析中的phase划分把输入数据划分成各个phase，在每个phase开始时把标记清空，当需要把一个页换入cache时，在所有未标记的页里随机踢出一个，然后换入当前页，并打上标记。这就是marking算法。显然我们可以沿用上一节的所有分析，证明这个算法也一定有一个worst-case不超过$k$的竞争比。我们能不能进一步分析期望意义下的竞争比呢？

设$m_i$表示phase $i$与phase $i-1$相比出现了多少个全新的页，那么$\text{OPT}$在phase $i$与phase $i-1$这两个阶段的过程中至少产生了$m_i$个miss。我们把$m_i$累加起来，说明$\text{OPT}$产生的总的miss的“两倍”不超过$\sum m_i$（因为每个phase会被累加两次）。因此$\text{OPT} \geq \dfrac{1}{2}\sum m_i$。

每当一个phase结束时，cache中的页就是这个phase中所有不同的页。因此当每个phase的页请求中新页全都排在旧页之前时，miss的概率相比之下更高，因为新页会把一些旧页踢走。所以在分析时，我们总可以假设新页是排在旧页之前的，因为这样只是在为更坏的情况考虑。对于phase $i$，$\text{ALG}$首先会在每个新页上miss，共$m_i$个。接下来的第一个旧页，它面对的cache中已经有随机的$m_i$个被换成了新页了，也即已经有$m_i$个旧页被踢出了，这个旧页发生miss的概率也即从$k$个物品里随机丢掉$m_i$个恰好丢掉其中特定某一个的概率，计算得$\dfrac{\binom{k-1}{m_i-1}}{\binom{k}{m_i}}=\dfrac{m_i}{k}$。再考虑第二个旧页，如果上一个旧页没有miss则cache不变，如果上一个旧页miss了则它会踢出一个旧页换上自己这个旧页，从效果上来看就好像没变一样，因此第二个旧页miss的概率依旧是从$k$个物品里随机丢掉$m_i$个恰好丢掉其中特定某一个的概率，只不过此时我们知道“第一个旧页”这个物品一定不是被丢掉的那个。如果第二个旧页就是第一个旧页，那么一定不miss，所以我们不妨假设第二个旧页和第一个不同，这样会把概率放大，由此可得概率不超过$\dfrac{\binom{k-2}{m_i-1}}{\binom{k-1}{m_i}}=\dfrac{m_i}{k-1}$。以此类推，第$j$个旧页miss的概率不超过$\dfrac{m_i}{k-j+1}$。由此可得期望意义下$\text{ALG}$在一个phase里的miss不超过$\dfrac{m_i}{k}+\dfrac{m_i}{k-1}+\cdots+\dfrac{m_i}{1}\leq m_i\log k$。综上，对于整个算法，$\dfrac{\text{ALG}}{\text{OPT}}=\dfrac{k+\log k\sum{m_i}}{k+\frac{1}{2}\sum m_i}=O(\log k)$。我们得到了一个期望意义下竞争比为$O(\log k)$的随机算法！

由Yao's Minimax可以证明不存在竞争比比$O(\log k)$更小的随机算法。（？）