+++++buffer cache 深度解析( 六 ) _链表

图三
到了8i以后，引入了一种更加复杂的机制来管理LRU上的数据块。8i以后，LRU和LRUW链表都具有两个子链表，分别叫做辅助链表和主链表。同时还对增加了一个属性：touch数量，也就是每个曾经被访问过的次数，来对LRU链表进行管理。每访问一次，就会将该上的touch数量增加1，因此，touch数量“近似”的体现了某个内存数据块总共被访问的次数。注意，这只是近似，并不精确。因为touch的增加并没有使用latch来管理并发性。这只是一个大概值，表示趋势的，不用百分百的精确。
还是用上面的这个例子来说明。还是假设 cache只能容纳4个数据块，同时只有一个hash chain和一个LRU（确切的说应该是一对LRU主链表和辅助链表）。读入第一个数据块时，该数据块对应的会挂到LRU辅助链表（注意，这里是辅助链表，而不是主链表）的最末端，同时touch数量为1 。读取第二个不同的数据块时，该数据块对应的会挂到前一个的后面，从而位于LRU辅助链表的最末端，同样touch为1 。假设4个数据块全都用完以后的LRU链表可以用下图四描述。每个的touch数量都为1 。
从上图中我们可以看到辅助LRU链表都挂满了，而主LRU链表还是空的。这个时候，前台发出第五句SQL语句，要求返回指定的数据块。这时，发现 cache里已经没有空的内存数据块了，于是从辅助LRU链表的尾部开始扫描，也就是从BH1开始扫描，以查找可以被替代的数据块。扫描的过程中按照下面的逻辑来选择被牺牲的（也就是可以被替代的）数据块：
1）如果被扫描到的的touch数量小于隐藏参数ia（该参数缺省为2）的值，则选中该作为牺牲者，并立即返回该所含有的数据块的地址。
2）如果当前的touch数量大于ia的值，则不会使用该。但是如果当前的的值小于ia的值，则会将当前该的touch值赋值给；否则将当前的touch数量减掉一半。
按照上述的逻辑，这时将选出BH1作为牺牲者（因为BH1的touch数量为1，小于ia
的值），并将其对应的内存数据块的内容清空，同时将当前第五个数据块的内容拷贝进去。但是这里要注意，这个时候该BH1在LRU链表上的位置并不会发生任何的变化（这里是插入了新的数据块的内容，所以touc的数量没有变化，下面是返回已经有的数据块，所以touch的数量加1了，这样就保证了touch为1的数据块即不常用的数据块一直在辅助链表，而不会跑到主lru链表上）。而不会像8i之前的那样，BH1变成LRU链表的首端。
接下来，前台发来了第六句和第七句SQL，分别要返回与第五句和第四句SQL一样的数据块，也就是要返回当前的BH1和BH4 。这个时候，会增加BH1和BH4的touch数量，同时将该BH1和BH4从辅助LRU链表上摘下，转移到主LRU链表的中间位置。可以用下图五描述。
图五
这个时候，如果发来了第八句SQL，要求返回与第三句SQL相同的数据块，也就是当前的BH3，则这时该BH3会插入主LRU链表上的BH1和BH4中间，注意每次向主LRU列表插入时都是向中间位置插入。如果发来了第九句SQL要求返回BH2，则我们可以知道，BH2会转移到主LRU链表的中间。这个时候，辅助LRU链表就空了，没有了。
这时，如果又发来第十句SQL，要求返回一个新的、 cache中不存在所需内容的数据块时。会先扫描辅助LRU链表，发现上面没有任何的时，则必须扫描主LRU链表。从尾部开始扫描，采用前面说到的与扫描辅助LRU链表相同的规则挑选牺牲者。挑出的可以被替代的将从主LRU链表上摘下，放入辅助LRU链表。
从上面所描述的在辅助LRU链表和主LRU链表之间交替的过程中，我们可以看出，改进LRU链表的管理方式的目的，就是想千方百计的能够将多次被访问的数据块保留在内存里，同时又要平衡有限的内存资源。这种方式相比较8i之前而言，无疑是进步很多的。在8i之前中，某个数据块可能只会被访问一次，但是就这么一次的访问就将该数据块放到了LRU的首端，从而可能就挤掉了一个LRU上不是那么经常被访问，但是也会多次访问的数据块。而8i以后，将访问一次的数据块和访问一次以上的数据块彻底分开，而且查找可用数据块时，始终都是从辅助LRU链表开始扫描。实际上也就使得越倾向于只访问一次的数据块越快的从内存中清理出去。