[[326308]]

概述

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

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

LRU鏈：

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

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

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

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

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

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

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

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

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

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

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

塊S會(huì)被從冷端移到熱端，并且它的訪問(wèn)次數(shù)會(huì)被清零。此時(shí)，塊R就是犧牲者了，因?yàn)樗脑L問(wèn)次數(shù)不到兩次。

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

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

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

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

臟塊與臟LRU鏈：

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

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

臟塊在被寫回磁盤前，也就是在它還是臟塊時(shí)，它是不能被覆蓋的，因?yàn)椋K塊含有用戶修改過(guò)的數(shù)據(jù)，而這些數(shù)據(jù)還沒(méi)被寫到磁盤，如果此時(shí)覆蓋了臟塊，用戶的修改結(jié)果將會(huì)丟失。

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

總結(jié)

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

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

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

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