** 数据库存取缓冲区的 ** ** LRU ** ** 与 ** ** MRU ** ** 算法 ** ** **
** 1.Cache Hit and Cache Miss **
当使用者第一次向数据库发出查询数据的请求的时候，数据库会先在缓冲区中查找该数据 , 如果要访问的数据恰好已经在缓冲区中 ( 我们称之为 Cache Hit) 那么就直接用缓冲区中读取该数据 .
反之如果缓冲区中没有使用者要查询的数据那么这种情况称之为 Cache Miss, 在这种情况下数据库就会先从磁盘上读取使用者要的数据放入缓冲区 , 使用者再从缓冲区读取该数据 .
很显然从感觉上来说 Cache Hit 会比 Cache Miss 时存取速度快 .
** 2. ** ** LRU( ** ** 最近最少使用算法 ** ** ) and MRU( ** ** 最近最常使用算法 ** ** ) **
所谓的 LRU(Least recently used) 算法的基本概念是 : 当内存的剩余的可用空间不够时 , 缓冲区尽可能的先保留使用者最常使用的数据 , 换句话说就是优先清除 ” 较不常使用的数据 ”, 并释放其空间 . 之所以 ” 较不常使用的数据 ” 要用引号是因为这里判断所谓的较不常使用的标准是人为的、不严格的 . 所谓的 MRU(Most recently used) 算法的意义正好和 LRU 算法相反 .
下面我们通过 Oracle 9i Cache 中对 LRU 和 MRU 的使用来看一下两者在缓冲区工作机制中的作用和区别 :
在 Oracle 9i 中有 LRU List 的概念 : 我们可以把 LRU List 想象成是一连串的缓冲区集合 , 两端分别是 ** LRU ** ** 端 ** 和 ** MRU ** ** 端 ** , 当数据库从磁盘上读取数据放入缓冲区时 , 系统必须先确定缓冲区中有 free buffers, 这个时候 Oracle 9i 会扫描 LRU List, 扫描的基本原则是 :
1. 从 ** LRU ** ** 端 ** 到 ** MRU ** ** 端 ** ;
2. 当扫描到 free buffer 或已扫描的缓冲区数目超过临界值时 , 就会停止扫描动作 ;
如果在扫描过程顺利的在 LRU List 中找到了 free buffer, 那么 Oracle 9i 就把从磁盘读出的数据写到 free buffer 中然后把 free buffer 加到 LRU List 的 ** MRU ** ** 端 ** .
那如果扫描过程没有在 LRU List 中找到 free buffer 怎么办 ? 当然是从 LRU List 的 ** LRU ** ** 端 ** 开始清除缓冲区 , 如此一来就可以腾出新的空间了 .
下图就是一个例子 :
使用者查询数据 A, 初始的时候 LRU List 中没有数据 A, 于是 Oracle 9i 到磁盘读取 A, 然后放到 LRU List 的 ** MRU ** ** 端 ** , 使用者再从 LRU List 中读取数据 A, 同理对于 B,C… 当 LRU List 满了以后 , 如果使用者查询 N, 此时 N 不在 LRU List 中而且 LRU List 中已经没有 free buffer 了 , 此时 Oracle 9i 就开始从 ** LRU ** ** 端 ** 淘汰 A 以腾出空间存放 N.
图 1
我们再来看另外一种情况 :
在 State 3 之后 , 恰好使用者持续的查询 A— 这将会导致 A 一直被放置在靠近 ** MRU ** ** 端 ** 的缓冲区 , 结果将如图 State m’ 所示 , 你会发现图 2 的 State m’ 与图 1 的 State m 缓冲区存放的数据完全一样但是存放位置不一样 . 此时 LRU List 满了 , 如果再放 N 的时候 LRU List` 淘汰的是 B, 因为 A 的查询率高于 B, 所以 LRU List 让 A 在缓冲区中呆上较长的时间而先淘汰掉 ” 较不常用的 ” 的 B.
图 2