在 Ceph 中 Client 和 MDS 部分的 lru 實(shí)現(xiàn)和淘汰策略稍有不同，但作用都是用來管理 dentry 等結(jié)構(gòu)，方便及時(shí)將不使用的文件和目錄清出內(nèi)存，這里主要關(guān)注 lru 的實(shí)現(xiàn)而不關(guān)注 dentry 的淘汰時(shí)機(jī)。

首先看下 LRU 的結(jié)構(gòu)：

這里和大部分 LRU 的實(shí)現(xiàn)類似， ceph 也使用一個(gè)雙向鏈表作為 lru 的基礎(chǔ)結(jié)構(gòu)（也就是這里的 xlist，基本可以當(dāng)作一個(gè)雙向鏈表看待）。只不過 ceph 同時(shí)使用了三個(gè)鏈表 top、bottom 和 pintail 來細(xì)化 lru 的不同位置。

其中 top 和 bottom 比較好理解就是一般 lru 實(shí)現(xiàn)中的首尾兩端，越靠近 top.front() 則說明最近越多使用，越靠近 bottom.back() 則說明最近越少使用，可以被淘汰。

pintail 稍微特殊一點(diǎn)，在此鏈中的 dentry 表示正在有人使用（可能是外部應(yīng)用持有文件的 filehandle，因此隨時(shí)有可能訪問），因此不會(huì)被 從 lru 鏈中淘汰，即使最近沒有人使用，這里不是我們關(guān)注的重點(diǎn)。

這里就對(duì)應(yīng)將一個(gè) lru object 插入 lru 鏈的三個(gè)位置（從外部看 lru 是一個(gè)鏈，內(nèi)部才分為 top 或者 bottom），實(shí)際對(duì)應(yīng)就是

另外之前已經(jīng)說了 xlist 的實(shí)現(xiàn)屬于是一個(gè)雙向鏈表的變種，這里也簡(jiǎn)單看一下，以 top.push_front 為例：

首先就是如果這個(gè) item（也就是一個(gè) lru object） 已經(jīng)在某一個(gè)鏈上了，那么先通過 remove 把這個(gè) item 從先前的鏈上摘下來，這個(gè)實(shí)現(xiàn)可以避免一個(gè) item 掛在多個(gè)鏈上

接著將自己的 _list 指向 this，表示 item 的所屬鏈表（也就是 top）

這里就是首先把 item 掛到鏈表上，因?yàn)槭?push_front 所以 _prev 為空， _front 是整個(gè)鏈表的頭部。

同時(shí)要更新一下鏈表的頭尾指針，以及整個(gè)鏈表的長(zhǎng)度。

接著，必要時(shí) client 通過 lru_get_next_expire 獲取最近最少使用的 object 進(jìn)行 trim，這個(gè)過程實(shí)際上就是從 lru 中拿出 bottom.back()

這里 adjust 就是把整個(gè) lru 鏈中 object 數(shù)量的 60%（實(shí)際要減去 pinned object）放入 top，剩余部分放入 bottom

接著直接從 bottom 拿出末端 object，如果這個(gè) object 沒有 pinned 則直接將其返回，表示此 object 可以被 trim

pin 和 unpin 則是一個(gè)特殊的過程， pin 一個(gè)指定的 dentry 時(shí)我們只需要將對(duì)應(yīng)的 object 從 top 或者 bottom 上移出到 pintail 鏈上（無關(guān)乎首尾，因?yàn)?pintail 上的 dentry 都不能 trim），而 unpin 則只需要將其 pintail 中移出到 bottom 的尾部即可

整個(gè) lru 設(shè)計(jì)相對(duì)來說比較容易理解，也非常易于使用。

對(duì)于一個(gè)特定的 dentry，我們會(huì)在初次獲取到其 object 時(shí)可以將其放至 lru mid，初次使用時(shí)將其放至 lru top，接著如果沒有使用會(huì)隨著 lru 的 adjust 逐漸移動(dòng)到 bottom 然后被 client 取出作為 expired object 淘汰掉，而如果這時(shí)通過 pin 加入 pintail 的話就會(huì)一直等到 unpin 之后再放到 bottom.back 等待 trim