在做Lab3之前，先把之前的代码保存好，再拉取这个Lab3的分支代码：

git add .
git commit -m "Date"
git pull origin lru
git checkout lru

P.S. 之前作业若未完成，需切回对应分支重新完成

git add .
git commit -m "lru-cache"
git checkout date

实验描述

LRU替换算法原理解析

为什么需要有一个替换策略？

因为我们的Buffer Pool的容量是有限的，当它的容量满了，并且还需要读取一个新的内存页到我们的Buffer Pool的时候，我们就需要从当前的缓冲池中找一个牺牲者把它踢出去。踢出去的策略有很多，比如随机踢一个，先来先踢，后来先踢等等，这些策略实现都挺简单的，但是可能频繁出现一个页频繁被换入换出的情况。一种比较优秀的替换策略就是LRU，把最近最久未使用的page给置换出去。其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

如何理解LRU的替换策略的执行流程？

为了更好地理解 LRU，我们来看看 LRU 如何在示例引用序列上执行。下面表中展示了 结果。从表中，可以看到 LRU 如何利用历史记录，比无状态策略(如随机或 FIFO)做得更好。在这个例子中，当第一次需要替换页时，LRU 会踢出页 2，因为 0 和 1 的访问时间更近。然后它替换页 0，因为 1 和 3 最近被访问过。

Untitled

如何实现LRU？

一种比较简单且容易理解的实现就是时间戳算法：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。很显然，这样做时间复杂度是O(n)的。

如何优化LRU的时间复杂度？

另外一种很经典的算法就是双向链表（代码中的 _cache_items_list）+哈希表（代码中的 _cache_items_map）。使用双向链表不难理解。但是为什么要使用哈希表呢？思考一下当第二次访问页0的时候，我们是不是要把双向链表中间的页0移到队列头？那么我们首先要找到页0，如果是遍历链表，那么时间复杂度还是O(n)。所以我们引入了哈希表，它的键就是我们的双向链表中存储的值，它的值就是指向双向链表中对应节点的指针，这样我们就可以通过哈希表通过O(1)的时间复杂度定位到页0所在的节点的位置了！

miniob缓存管理器原理解析

BPM简介