今天是2013-09-09，時(shí)別n久的一篇經(jīng)典文章，有被我在google發(fā)現(xiàn)了，再次轉(zhuǎn)載一下。學(xué)習(xí)一下。

一、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è)犧牲者。這一點(diǎn)我們?cè)诠蚕沓刂性峒斑^(guò)，這個(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。注意，這就是LRU的宗旨，“將最后訪問(wèn)時(shí)間距現(xiàn)在最遠(yuǎn)的塊作為犧牲者”。

???? 為了實(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)入熱端。

The database does not physically move blocks in memory. The movement is the change in location of a pointer on a list.

When a buffer is pinned, the database determines when its touch count was last incremented. If the count was incremented over three seconds ago, then the count is incremented; otherwise, the count stays the same. The three-second rule prevents a burst of pins on a buffer counting as many touches. For example, a session may insert several rows in a data block, but the database considers these inserts as one touch.

If a buffer is on the cold end of the LRU, but its touch count is high, then the buffer moves to the hot end. If the touch count is low, then the buffer ages out of the cache.

?

???? 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)樵娇拷涠耍瑝K的訪問(wèn)次數(shù)有可能越少、最后的訪問(wèn)時(shí)間離現(xiàn)在最遠(yuǎn)。好了， LRU 鏈還沒(méi)有講完，下面，我們?cè)儆懻撘幌屡K塊與臟 LRU 鏈的問(wèn)題。

二、臟塊與臟LRU鏈：

???? Oracle中修改塊的規(guī)則是只對(duì)Buffer cache中的塊進(jìn)行修改，并不直接修改磁盤(pá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ì)定期的將臟塊寫(xiě)到磁盤(pán)中。有一個(gè)專(zhuān)門(mén)的后臺(tái)進(jìn)程就是專(zhuān)門(mén)負(fù)責(zé)寫(xiě)臟塊到磁盤(pán)的，它就是DBWn。我們也把DBWn寫(xiě)臟塊到磁盤(pán)這個(gè)過(guò)程叫做刷新臟塊，刷新過(guò)后，臟塊就不臟了，又變成了干凈塊。其實(shí)，有一個(gè)塊A，如果Buffer cache中此塊的數(shù)據(jù)和磁盤(pán)上塊中數(shù)據(jù)不一致，那么，這個(gè)塊就是臟塊。否則，就是干凈塊。當(dāng)修改完成后，因?yàn)镺racle只修改Buffer cache，因此，塊中數(shù)據(jù)和磁盤(pán)肯定不一致，這時(shí)塊就是臟塊。當(dāng)塊被刷新后，塊被寫(xiě)到磁盤(pán)，那么，磁盤(pán)中塊數(shù)據(jù)和Buffer cache中塊的數(shù)據(jù)又是一致的，此時(shí)，塊就又變成了干凈塊。

???? 臟塊在被寫(xiě)回磁盤(pán)前，也就是在它還是臟塊時(shí)，它是不能被覆蓋的，因?yàn)椋K塊含有用戶修改過(guò)的數(shù)據(jù)，而這些數(shù)據(jù)還沒(méi)被寫(xiě)到磁盤(pán)，如果此時(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 ，然后將 N 插入到 Y 之前。然后呢，下一次有塊進(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 鏈，專(zhuān)門(mén)保存臟塊。當(dāng)塊變臟時(shí)，塊不會(huì)馬上被移到臟 LRU 中，只有當(dāng) Oracle 從冷端頭開(kāi)始，尋找犧牲者時(shí)，才會(huì)將發(fā)現(xiàn)的臟塊移動(dòng)到臟 LRU 鏈中。這樣做的目的我們剛才已經(jīng)快要講到了，就是下次再尋找犧牲者時(shí)，可以不用再檢查這些臟塊。好，讓我們繼續(xù)看圖，接著上圖，有新塊 Z 要進(jìn)入 Buffer cache ：

???? 如上圖， O 、 P 、 Q 將被移到臟 LRU 鏈中。

???? 冷端頭變成了N，N的訪問(wèn)次數(shù)小于2，它就是本次的犧牲者了。這樣當(dāng)下一次再需要從冷端頭開(kāi)始尋找犧牲者時(shí)，就不用再檢查O、P、Q這三個(gè)臟塊了。當(dāng)臟LRU鏈的長(zhǎng)度，也就是臟LRU鏈中的臟塊達(dá)到一定數(shù)目時(shí)，DBWn會(huì)開(kāi)始刷新臟塊。

???? 通過(guò)上面所講述的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算法。Oracle這樣做的目的，是為了讓我們平時(shí)的查詢、修改所需完成的操作盡量的少。對(duì)于用戶的查詢、修改操作，LRU算法幾乎沒(méi)有任何的影響，額外所做的工作只是改變了幾個(gè)標(biāo)志位而已，查詢時(shí)增加訪問(wèn)次數(shù)標(biāo)志位，修改塊時(shí)設(shè)置臟塊標(biāo)志位。LRU算法大部分的工作，都是在尋找犧牲者時(shí)完成的。因此，有時(shí)尋找犧牲者這個(gè)過(guò)程有可能會(huì)出現(xiàn)等待，等待事件是free buffer waits。

? ? 訪問(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事件中。另外，在資料視圖中有一個(gè)資料free buffer inspected，它記錄了Oracle在所有次的尋找犧牲者的過(guò)程中，共計(jì)碰到了多少個(gè)不可覆蓋的塊。

? ? 在尋找犧牲者過(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寫(xiě)刷新速度慢造成的。我們應(yīng)該將DBWn更頻繁的被喚醒去刷新臟塊，好讓它們變干凈、可以被選為犧牲者。我們不應(yīng)該讓臟塊從臟LRU鏈中被刷新，因?yàn)檫@時(shí)通常會(huì)出現(xiàn)free buffer inspected。臟LRU鏈并不是為了將臟塊集中到一起，讓DBWn去刷新的，我們上面的圖例中已經(jīng)講過(guò)，將臟塊移動(dòng)到臟LRU鏈中，是為了減少下一次尋找犧牲者時(shí)，所需搜尋的塊。Oracle中另有一個(gè)鏈表，準(zhǔn)門(mén)用來(lái)記錄臟塊，好讓DBWn定期刷新，這個(gè)鏈表是檢查點(diǎn)隊(duì)列。

ORALCE 之LRU鏈與臟LRU鏈