ocp知识点讲解 之 lru链与脏lru链-凯发app官方网站

一、lru链：

     任何缓存的大小都是有限制的，并且总不如被缓存的数据多。就像buffer cache用来缓存数据文件，数据文件的大小远远超过buffer cache。因此，缓存总有被占满的时候。当缓存中已经没有空闲内存块时，如果新的数据要求进入缓存，就只有从缓存中原来的数据中选出一个牺牲者，用新进入缓存的数据覆盖这个牺牲者。这一点我们在共享池中曾提及过，这个牺牲者的选择，是很重要的。缓存是为了数据可以重用，因此，通常应该挑选缓存中最没有可能被重用的块当作牺牲者。牺牲者的选择，从cpu的l1、l2缓存，到共享池、buffer cache池，绝大多数的缓存池都是采用著名的lru算法，不过在oracle中，oracle采用了经过改进的lru算法。具体的算法它没有公布，不过lru算法总的宗旨就是――“最近最少”，其意义是将最后被访问的时间距现在最远的内存块作为牺牲者。比如说，现在有三个内存块，分别是a、b、c，a被访问过10次，最后一次访问是在10:20，b被访问过15次，最后一次访问是10:18，c也被访问10次，最后一次被访问是在10:22。当需要选择牺牲者时，b访问次数最多，牺牲者肯定不是它。a、c访问次数一样，但a在10:20被访问，而c在10:22被访问，a最后被访问的更早些，牺牲者就是a。注意，这就是lru的宗旨，“将最后访问时间距现在最远的块作为牺牲者”。

     为了实现lru的功能，oracle在buffer cache中创建了一个lru链表，oracle将buffer cache中所有内存块，按照访问次数、访问时间排序串在链表中。链表的两头我们分别叫做热端与冷端， 如下图

     当你第一次访问某个块时，如果这个块不在buffer cache中，oracle要选将它读进buffer cache。在buffer cache中选择牺牲者时，oracle将从冷端头开始选择，在上图的例子中，内存块u将是牺牲者。

 如上图，新块将会被读入u，覆盖u原来的内容。这里，我们假设新块是v。但是块v不会被放在冷端头，因为冷端头的块，会很快被当作牺牲者权覆盖的。这不符合“将最后访问时间距现在最远的块作为牺牲者”的宗旨。块v是最后时间距当前时刻最近的，它不应该作为下一个牺牲者。oracle是如何实验lru的，我们继续看。

 oracle将lru链从中间分为两半，一半记录热端块、一半记录冷端块。如上图，而刚刚被访问的块v，如下图：

     如过再有新的块进入buffer cache，比如块x被读入buffer cache，它将覆盖t，并且会被移至块v的前面，如下图：

     大家可以想像一下，如果按照这面的方式继续下去，最右边冷端头处的块，一定是最后一次访问时间距现在最远的块。那么，访问次数多的块是不会被选做牺牲者的，这一点oracle是如何实现的？这很简单，oracle一般以2次为准，块被访问2次以上了，它就有机会进入热端。

     oracle为内存中的每个块都添加了一个记录访问次数的标志位，假设图中每个块的访问次数如下：

     如果现在又有新块要被读入buffer cache，oracle开始从冷端头寻找牺牲者，冷端头第一个块s，它的访问次数是2，那么，它不能被覆盖，只要访问次数大于等于2的块，oracle会认为它可能会被经常访问到，oracle要把它移到热端，它会选择r做为本次的牺牲者：

     块s会被从冷端移到热端，并且它的访问次数会被清零。此时，块r就是牺牲者了，因为它的访问次数不到两次。

     新块y覆盖了块r，并被移到了冷端块开始处，它的访问次数是1。如果块y再被访问了一次，它的访问次数变为了2：

     虽然y的访问次数达到了两次，但它不会马上被移到热端，它仍然留在原来的位置，随着不断有新块加入，被插入到它的前面，它会不断的被向后推移。

     如上图，又加入了很多的新块，y又被推到了冷端头，当再有新块进入buffer cache时，y不会是牺牲者，它会被移到热端头s的前面，y后面的z，它的访问次数没有达到2，它将会是牺牲者。

     好了，这就是oracle中buffer cache管理lru的原理。按照这种方式运作，oracle可以把常用的块尽量长的保持在buffer cache中。而且，每有新块进入buffer cache，oracle都会从冷端头处，从右向左搜索牺牲块。因为越靠近冷端，块的访问次数有可能越少、最后的访问时间离现在最远。好了，lru链还没有讲完，下面，我们再讨论一下脏块与脏lru链的问题。

二、脏块与脏lru链：

     oracle中修改块的规则是只对buffer cache中的块进行修改，并不直接修改磁盘中的块。如果要修改的块不在buffer cache中，oracle会先将它读入buffer cache，再在buffer cache中进行修改。当buffer cache中的块被修改后，oracle会把它标记为“脏”块。脏块含有脏数据，脏数据就是用户修改过的数据。oracle会定期的将脏块写到磁盘中。有一个专门的后台进程就是专门负责写脏块到磁盘的，它就是dbwn。我们也把dbwn写脏块到磁盘这个过程叫做刷新脏块，刷新过后，脏块就不脏了，又变成了干净块。其实，有一个块a，如果buffer cache中此块的数据和磁盘上块中数据不一致，那么，这个块就是脏块。否则，就是干净块。当修改完成后，因为oracle只修改buffer cache，因此，块中数据和磁盘肯定不一致，这时块就是脏块。当块被刷新后，块被写到磁盘，那么，磁盘中块数据和buffer cache中块的数据又是一致的，此时，块就又变成了干净块。

     脏块在被写回磁盘前，也就是在它还是脏块时，它是不能被覆盖的，因为，脏块含有用户修改过的数据，而这些数据还没被写到磁盘，如果此时覆盖了脏块，用户的修改结果将会丢失。

     设当前lru链如上图所示，其中v、l、o、p、q是脏块。当新的块要进入buffer cache时，oracle从冷端头开始选择牺牲块，q、p和o都不能做作牺牲块，因为它们是脏块，n是这一次的牺牲者，新进入的块将会覆盖n，然后将n插入到y之前。然后呢，下一次有块进入buffer cache时，oracle从冷端头开始搜索，它还要检查一边q、p和o，发现它们都不能覆盖，再将m定为牺牲者。等等，每一次都要检查一边o、p、q，这太浪费时间了，oracle不会这么傻，oracle有准备了一个脏lru链，专门保存脏块。当块变脏时，块不会马上被移到脏lru中，只有当oracle从冷端头开始，寻找牺牲者时，才会将发现的脏块移动到脏lru链中。这样做的目的我们刚才已经快要讲到了，就是下次再寻找牺牲者时，可以不用再检查这些脏块。好，让我们继续看图，接着上图，有新块z要进入buffer cache：

     如上图，o、p、q将被移到脏lru链中。

     冷端头变成了n，n的访问次数小于2，它就是本次的牺牲者了。这样当下一次再需要从冷端头开始寻找牺牲者时，就不用再检查o、p、q这三个脏块了。当脏lru链的长度，也就是脏lru链中的脏块达到一定数目时，dbwn会开始刷新脏块。

     通过上面所讲述的lru链与脏lru链的原理，我们可以发现oracle把很多工作，都留到了在lru的冷端搜索牺牲者时。当块的访问次数增加的超过2时，块在lur链的位置不变；当块变脏时，块的lru链位置也不变。只有当从lru的冷端搜索牺牲者时，才会将发现的脏块移到脏lru链，将访问次数超过2的，插入到热端，这就是oracle改进了的lru算法。oracle这样做的目的，是为了让我们平时的查询、修改所需完成的操作尽量的少。对于用户的查询、修改操作，lru算法几乎没有任何的影响，额外所做的工作只是改变了几个标志位而已，查询时增加访问次数标志位，修改块时设置脏块标志位。lru算法大部分的工作，都是在寻找牺牲者时完成的。因此，有时寻找牺牲者这个过程有可能会出现等待，等待事件是free buffer waits。

  ÿ 访问次数大于2的块太多，或才脏块太多，反正这些块都是不能覆盖的，oracle不得不移动它们到它们该去的位置。当碰到的这样的块超过lru中总块数的40%时，也就是说搜索了一小半lru链，还是没有发现可以覆盖的牺牲者，oracle就不在找了，它会唤醒dbwn刷新脏块。在dbwn刷新期间的等待，就会被记入到free buffer waits事件中。另外，在资料视图中有一个资料free buffer inspected，它记录了oracle在所有次的寻找牺牲者的过程中，共计碰到了多少个不可覆盖的块。

  ÿ 在寻找牺牲者过程中发现脏块，oracle将其移动到脏lru链，但是脏lru链中脏块数目达到限制，dbwn被唤醒开始刷新脏块，oracle必须等待刷新脏块完毕，才能再继续寻找牺牲者，这其间的等待事件，也会被记入free buffer inspected。

总之，free buffer waits事件发生的主要原因就是在lru中寻找牺牲者的时间过长。如果     这个等待事件频繁出现，说明buffer cache中脏块太多了，这通常是dbwn写刷新速度慢造成的。我们应该将dbwn更频繁的被唤醒去刷新脏块，好让它们变干净、可以被选为牺牲者。我们不应该让脏块从脏lru链中被刷新，因为这时通常会出现free buffer inspected。脏lru链并不是为了将脏块集中到一起，让dbwn去刷新的，我们上面的图例中已经讲过，将脏块移动到脏lru链中，是为了减少下一次寻找牺牲者时，所需搜寻的块。oracle中另有一个链表，准门用来记录脏块，好让dbwn定期刷新，这个链表是检查点队列。

（下一篇讲解检查点队列，敬请期待！）