LRU链表

郑全

LRU链表结构概述

在前面，我们已经知道了Oracle是如何在hash chain中搜索要找的数据块所对应的buffer header的过程，我们也知道如果在hash chain上没有找到所要的buffer header时，Oracle会发出I/O调用，到磁盘上的数据文件中获取数据块，并将该数据块的内容复制一份到buffer cache中的内存数据块里。这个时候，假如buffer cache是空的，比较好办，直接拿一个空的内存数据块来用即可。但是如果buffer cache中的内存数据块全都被用掉了，没有空的内存数据块了，怎么办？应该重新使用哪一个内存数据块？当然我们可以逐个比较内存数据块与其对应在数据文件中的数据块的内容是否一致，如果一致则可以将该数据块拿来，将其内容清空，然后将当前数据块的内容复制进入；如果不一致，则说明数据块在内存里被修改了，但是还没有写入数据文件，因此该数据块不能被其他内容覆盖，则跳过，再找下一个。毫无疑问，这种方式效率低下。为了高效地管理buffer cache中的内存数据块，Oracle引入了LRU链表等结构。

在buffer cache中，最耳熟能详的链表可能就是LRU链表了。在前面描述buffer cache结构的图上，也可以看到LRU链表。在介绍LRU前，先说明几个概念。

? 脏数据块（dirty buffer）：buffer cache中的内存数据块的内容被修改，从而导致与数据文件中的数据块的内容不一致。
? 空闲数据块（free buffer）：buffer cache中的内存数据块为空。
? 干净数据块（clean buffer）：buffer的内容与数据文件中的一致。
? 钉住的数据块（pin buffer）：当前正在更新的内存数据块。
? 数据库写进程（DBWR）：这是一个很底层的数据库后台进程。既然是后台进程，就表示该进程是不能被用户调用的。由Oracle内置的一些事件根据需要启动该进程，该进程用来将脏数据块写入磁盘上的数据文件。

对于空闲数据块和干净数据块，我们一般都统称为可用数据块，因为其中的内容可以被新的数据内容覆盖。其他状态的数据块，比如脏数据块，则不能被新的内容覆盖。

LRU表示Least Recently Used，也就是指最近最少使用的buffer header链表。LRU链表串联起来的buffer header都指向可用数据块。buffer按照被使用的先后顺序挂在LRU链表上，先被使用的buffer挂在LRU链表的后面，后被使用的buffer则被挂在LRU链表的前面。如果buffer被DML语句修改了，则该buffer会从LRU链表上摘下来。换句话说，LRU链表上的buffer header所指向的buffer都是可用数据块。

当服务器进程无法找到空的buffer来存放新的数据请求时，则需要把已经存放了数据的buffer拿来使用，也就是用新的数据块的内容覆盖曾经使用过的buffer。在查找应该覆盖哪个buffer时，Oracle会在LRU链表上的尾部开始扫描，如果扫描到的buffer正在被使用，则跳过该buffer，继续往下找，直到找到为止。如果扫描了一定数量的buffer以后还没找到可用的buffer，则说明脏块太多了，于是触发DBWn进程，将脏块刷新到数据文件里，刷新完毕以后，buffer的内容与数据文件里的一致，于是这些脏块就变成干净的buffer了，也就可以拿来覆盖其中的内容了。这些干净的buffer就会挂在LRU链表的尾部，供进程所使用。

当进程在LRU链表上扫描可用数据块时，会受到cache buffers lru chain latch的保护