[[326308]]

概述

所謂的LRU(Least recently used)算法的基本概念是當(dāng)內(nèi)存的剩余的可用空間不夠時,緩沖區(qū)盡可能的先保留使用者最常使用的數(shù)據(jù),換句話說就是優(yōu)先清除”較不常使用的數(shù)據(jù)”,并釋放其空間.之所以”較不常使用的數(shù)據(jù)”要用引號是因為這里判斷所謂的較不常使用的標(biāo)準(zhǔn)是人為的、不嚴(yán)格的.所謂的MRU(Most recently used)算法的意義正好和LRU算法相反。

Oracle在高速緩沖區(qū)工作機制中就用到了這個算法，下面一起看看吧~

LRU鏈：

任何緩存的大小都是有限制的，并且總不如被緩存的數(shù)據(jù)多。就像Buffer cache用來緩存數(shù)據(jù)文件，數(shù)據(jù)文件的大小遠(yuǎn)遠(yuǎn)超過Buffer cache。

因此，緩存總有被占滿的時候。當(dāng)緩存中已經(jīng)沒有空閑內(nèi)存塊時，如果新的數(shù)據(jù)要求進(jìn)入緩存，就只有從緩存中原來的數(shù)據(jù)中選出一個犧牲者，用新進(jìn)入緩存的數(shù)據(jù)覆蓋這個犧牲者。這個犧牲者的選擇，是很重要的。緩存是為了數(shù)據(jù)可以重用，因此，通常應(yīng)該挑選緩存中最沒有可能被重用的塊當(dāng)作犧牲者。犧牲者的選擇，從CPU的L1、L2緩存，到共享池、Buffer cache池，絕大多數(shù)的緩存池都是采用著名的LRU算法，不過在Oracle中，Oracle采用了經(jīng)過改進(jìn)的LRU算法。具體的算法它沒有公布，不過LRU算法總的宗旨就是“最近最少”，其意義是將最后被訪問的時間距現(xiàn)在最遠(yuǎn)的內(nèi)存塊作為犧牲者。

比如說，現(xiàn)在有三個內(nèi)存塊，分別是A、B、C，A被訪問過10次，最后一次訪問是在10:20，B被訪問過15次，最后一次訪問是10:18，C也被訪問10次，最后一次被訪問是在10:22。當(dāng)需要選擇犧牲者時，B訪問次數(shù)最多，犧牲者肯定不是它。A、C訪問次數(shù)一樣，但A在10:20被訪問，而C在10:22被訪問，A最后被訪問的更早些，犧牲者就是A。

為了實現(xiàn)LRU的功能，Oracle在Buffer cache中創(chuàng)建了一個LRU鏈表，Oracle將Buffer cache中所有內(nèi)存塊，按照訪問次數(shù)、訪問時間排序串在鏈表中。鏈表的兩頭我們分別叫做熱端與冷端， 如下圖

當(dāng)你第一次訪問某個塊時，如果這個塊不在Buffer cache中，Oracle要選將它讀進(jìn)Buffer cache。在Buffer cache中選擇犧牲者時，Oracle將從冷端頭開始選擇，在上圖的例子中，內(nèi)存塊U將是犧牲者。

如上圖，新塊將會被讀入U，覆蓋U原來的內(nèi)容。這里，我們假設(shè)新塊是V。但是塊V不會被放在冷端頭，因為冷端頭的塊，會很快被當(dāng)作犧牲者權(quán)覆蓋的。這不符合“將最后訪問時間距現(xiàn)在最遠(yuǎn)的塊作為犧牲者”的宗旨。塊V是最后時間距當(dāng)前時刻最近的，它不應(yīng)該作為下一個犧牲者。Oracle是如何實驗LRU的，我們繼續(xù)看。

Oracle將LRU鏈從中間分為兩半，一半記錄熱端塊、一半記錄冷端塊。如上圖，而剛剛被訪問的塊V，如下圖：

如過再有新的塊進(jìn)入Buffer cache，比如塊X被讀入Buffer cache，它將覆蓋T，并且會被移至塊V的前面，如下圖：

如果按照這面的方式繼續(xù)下去，最右邊冷端頭處的塊，一定是最后一次訪問時間距現(xiàn)在最遠(yuǎn)的塊。那么，訪問次數(shù)多的塊是不會被選做犧牲者的，這一點Oracle是如何實現(xiàn)的?這很簡單，Oracle一般以2次為準(zhǔn)，塊被訪問2次以上了，它就有機會進(jìn)入熱端。

Oracle為內(nèi)存中的每個塊都添加了一個記錄訪問次數(shù)的標(biāo)志位，假設(shè)圖中每個塊的訪問次數(shù)如下：

如果現(xiàn)在又有新塊要被讀入Buffer cache，Oracle開始從冷端頭尋找犧牲者，冷端頭第一個塊S，它的訪問次數(shù)是2，那么，它不能被覆蓋，只要訪問次數(shù)大于等于2的塊，Oracle會認(rèn)為它可能會被經(jīng)常訪問到，Oracle要把它移到熱端，它會選擇R做為本次的犧牲者：

塊S會被從冷端移到熱端，并且它的訪問次數(shù)會被清零。此時，塊R就是犧牲者了，因為它的訪問次數(shù)不到兩次。

新塊Y覆蓋了塊R，并被移到了冷端塊開始處，它的訪問次數(shù)是1。如果塊Y再被訪問了一次，它的訪問次數(shù)變?yōu)榱?：

雖然Y的訪問次數(shù)達(dá)到了兩次，但它不會馬上被移到熱端，它仍然留在原來的位置，隨著不斷有新塊加入，被插入到它的前面，它會不斷的被向后推移。

如上圖，又加入了很多的新塊，Y又被推到了冷端頭，當(dāng)再有新塊進(jìn)入Buffer cache時，Y不會是犧牲者，它會被移到熱端頭S的前面，Y后面的Z，它的訪問次數(shù)沒有達(dá)到2，它將會是犧牲者。

上面就是Oracle中Buffer cache管理LRU的原理。按照這種方式運作，Oracle可以把常用的塊盡量長的保持在Buffer cache中。而且，每有新塊進(jìn)入Buffer cache，Oracle都會從冷端頭處，從右向左搜索犧牲塊。因為越靠近冷端，塊的訪問次數(shù)有可能越少、最后的訪問時間離現(xiàn)在最遠(yuǎn)。

臟塊與臟LRU鏈：

Oracle中修改塊的規(guī)則是只對Buffer cache中的塊進(jìn)行修改，并不直接修改磁盤中的塊。如果要修改的塊不在Buffer cache中，Oracle會先將它讀入Buffer cache，再在Buffer cache中進(jìn)行修改。

當(dāng)Buffer cache中的塊被修改后，Oracle會把它標(biāo)記為“臟”塊。臟塊含有臟數(shù)據(jù)，臟數(shù)據(jù)就是用戶修改過的數(shù)據(jù)。Oracle會定期的將臟塊寫到磁盤中。有一個專門的后臺進(jìn)程就是專門負(fù)責(zé)寫臟塊到磁盤的，它就是DBWn。我們也把DBWn寫臟塊到磁盤這個過程叫做刷新臟塊，刷新過后，臟塊就不臟了，又變成了干凈塊。其實，有一個塊A，如果Buffer cache中此塊的數(shù)據(jù)和磁盤上塊中數(shù)據(jù)不一致，那么，這個塊就是臟塊。否則，就是干凈塊。當(dāng)修改完成后，因為Oracle只修改Buffer cache，因此，塊中數(shù)據(jù)和磁盤肯定不一致，這時塊就是臟塊。當(dāng)塊被刷新后，塊被寫到磁盤，那么，磁盤中塊數(shù)據(jù)和Buffer cache中塊的數(shù)據(jù)又是一致的，此時，塊就又變成了干凈塊。

臟塊在被寫回磁盤前，也就是在它還是臟塊時，它是不能被覆蓋的，因為，臟塊含有用戶修改過的數(shù)據(jù)，而這些數(shù)據(jù)還沒被寫到磁盤，如果此時覆蓋了臟塊，用戶的修改結(jié)果將會丟失。

設(shè)當(dāng)前LRU鏈如上圖所示，其中V、L、O、P、Q是臟塊。當(dāng)新的塊要進(jìn)入Buffer cache時，Oracle從冷端頭開始選擇犧牲塊，Q、P和O都不能做作犧牲塊，因為它們是臟塊，N是這一次的犧牲者，新進(jìn)入的塊將會覆蓋N，然后將新的塊插入到Y(jié)之前。然后呢，下一次有塊進(jìn)入Buffer cache時，Oracle從冷端頭開始搜索，它還要檢查一邊Q、P和O，發(fā)現(xiàn)它們都不能覆蓋，再將M定為犧牲者。等等，每一次都要檢查一邊O、P、Q，這太浪費時間了，Oracle不會這么傻，Oracle有準(zhǔn)備了一個臟LRU鏈，專門保存臟塊。當(dāng)塊變臟時，塊不會馬上被移到臟LRU中，只有當(dāng)Oracle從冷端頭開始，尋找犧牲者時，才會將發(fā)現(xiàn)的臟塊移動到臟LRU鏈中。這樣做的目的就是下次再尋找犧牲者時，可以不用再檢查這些臟塊。

總結(jié)

從LRU鏈與臟LRU鏈的原理，我們可以發(fā)現(xiàn)Oracle把很多工作，都留到了在LRU的冷端搜索犧牲者時。當(dāng)塊的訪問次數(shù)增加的超過2時，塊在LUR鏈的位置不變;當(dāng)塊變臟時，塊的LRU鏈位置也不變。只有當(dāng)從LRU的冷端搜索犧牲者時，才會將發(fā)現(xiàn)的臟塊移到臟LRU鏈，將訪問次數(shù)超過2的，插入到熱端，這就是Oracle改進(jìn)了的LRU算法。

當(dāng)訪問次數(shù)大于2的塊太多，或才臟塊太多，反正這些塊都是不能覆蓋的，Oracle不得不移動它們到它們該去的位置。當(dāng)碰到的這樣的塊超過LRU中總塊數(shù)的40%時，也就是說搜索了一小半LRU鏈，還是沒有發(fā)現(xiàn)可以覆蓋的犧牲者，Oracle就不在找了，它會喚醒DBWn刷新臟塊。在DBWn刷新期間的等待，就會被記入到free buffer waits事件中。

在尋找犧牲者過程中發(fā)現(xiàn)臟塊，Oracle將其移動到臟LRU鏈，但是臟LRU鏈中臟塊數(shù)目達(dá)到限制，DBWn被喚醒開始刷新臟塊，Oracle必須等待刷新臟塊完畢，才能再繼續(xù)尋找犧牲者，這其間的等待事件，也會被記入free buffer inspected。

總之，free buffer waits事件發(fā)生的主要原因就是在LRU中尋找犧牲者的時間過長。如果 這個等待事件頻繁出現(xiàn)，說明Buffer cache中臟塊太多了，這通常是DBWn寫刷新速度慢造成的。