數(shù)據(jù)庫(kù)存取緩沖區(qū)的lru與mru算法
1.cache hit and cache miss
當(dāng)使用者第一次向數(shù)據(jù)庫(kù)發(fā)出查詢數(shù)據(jù)的請(qǐng)求的時(shí)候，數(shù)據(jù)庫(kù)會(huì)先在緩沖區(qū)中查找該數(shù)據(jù),如果要訪問(wèn)的數(shù)據(jù)恰好已經(jīng)在緩沖區(qū)中(我們稱之為cache hit)那么就直接用緩沖區(qū)中讀取該數(shù)據(jù).
反之如果緩沖區(qū)中沒有使用者要查詢的數(shù)據(jù)那么這種情況稱之為cache miss,在這種情況下數(shù)據(jù)庫(kù)就會(huì)先從磁盤上讀取使用者要的數(shù)據(jù)放入緩沖區(qū),使用者再?gòu)木彌_區(qū)讀取該數(shù)據(jù).
很顯然從感覺上來(lái)說(shuō)cache hit會(huì)比cache miss時(shí)存取速度快.
2. lru(最近最少使用算法) and mru(最近最常使用算法)
所謂的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算法相反.
下面我們通過(guò)oracle 9i cache中對(duì)lru和mru的使用來(lái)看一下兩者在緩沖區(qū)工作機(jī)制中的作用和區(qū)別:
在oracle 9i中有l(wèi)ru list的概念: 我們可以把lru list想象成是一連串的緩沖區(qū)集合,兩端分別是lru端和mru端, 當(dāng)數(shù)據(jù)庫(kù)從磁盤上讀取數(shù)據(jù)放入緩沖區(qū)時(shí),系統(tǒng)必須先確定緩沖區(qū)中有free buffers,這個(gè)時(shí)候oracle 9i會(huì)掃描lru list,掃描的基本原則是:
1. 從lru端到mru端;
2. 當(dāng)掃描到free buffer或已掃描的緩沖區(qū)數(shù)目超過(guò)臨界值時(shí),就會(huì)停止掃描動(dòng)作;
如果在掃描過(guò)程順利的在lru list中找到了free buffer,那么oracle 9i就把從磁盤讀出的數(shù)據(jù)寫到free buffer中然后把free buffer加到lru list的mru端.
那如果掃描過(guò)程沒有在lru list中找到free buffer怎么辦?當(dāng)然是從lru list的lru端開始清除緩沖區(qū),如此一來(lái)就可以騰出新的空間了.
下圖就是一個(gè)例子:
使用者查詢數(shù)據(jù)a,初始的時(shí)候lru list中沒有數(shù)據(jù)a,于是oracle 9i到磁盤讀取a,然后放到lru list的mru端,使用者再?gòu)膌ru list中讀取數(shù)據(jù)a,同理對(duì)于b,c…當(dāng)lru list滿了以后,如果使用者查詢n,此時(shí)n不在lru list中而且lru list中已經(jīng)沒有free buffer了,此時(shí)oracle 9i就開始從lru端淘汰a以騰出空間存放n.
圖 1
我們?cè)賮?lái)看另外一種情況:
在state 3之后,恰好使用者持續(xù)的查詢a—這將會(huì)導(dǎo)致a一直被放置在靠近mru端的緩沖區(qū),結(jié)果將如圖state m’所示,你會(huì)發(fā)現(xiàn)圖2的state m’與圖1的state m緩沖區(qū)存放的數(shù)據(jù)完全一樣但是存放位置不一樣.此時(shí)lru list滿了,如果再放n的時(shí)候lru list`淘汰的是b,因?yàn)閍的查詢率高于b,所以lru list讓a在緩沖區(qū)中呆上較長(zhǎng)的時(shí)間而先淘汰掉”較不常用的”的b.
圖 2
