你面試的時候遇見過LRU嗎？

LRU 算法，全稱是Least Recently Used。

翻譯過來就是最近最少使用算法。

這個算法的思想就是： 如果一個數(shù)據(jù)在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。所以，當指定的空間已存滿數(shù)據(jù)時，應當把最久沒有被訪問到的數(shù)據(jù)淘汰。

聽描述你也知道了，它是一種淘汰算法。

這個算法也是面試的一個高頻考點。

有的面試官甚至要求手擼一個 LRU 算法出來。

其實我覺得吧，遇到這種情況也不要慌，你就按照自己的思路寫一個出來就行。

賭一把，面試官也許自己短時間內(nèi)都手擼不出來一個無 bug 的 LRU。他也只是檢查幾個關(guān)鍵點、看看你的代碼風格、觀察一下你的解題思路而已。

但其實大多數(shù)情況下面試場景都是這樣的：

面試官：你知道 LRU 算法嗎？

我：知道，翻譯過來就是最近最少使用算法。其思想是（前面說過，就不復述了）......

面試官：那你能給我談談你有哪些方法來實現(xiàn) LRU 算法呢？

這個時候問的是什么？

問的是：我們都知道這個算法的思路了，請你按照這個思路給出一個可以落地的解決方案。

不用徒手擼一個。

方案一：數(shù)組

如果之前完全沒有接觸過 LRU 算法，僅僅知道其思路。

第一次聽就要求你給一個實現(xiàn)方案，那么數(shù)組的方案應該是最容易想到的。

假設(shè)我們有一個定長數(shù)組。數(shù)組中的元素都有一個標記。這個標記可以是時間戳，也可以是一個自增的數(shù)字。

我這里用自增的數(shù)字。

每放入一個元素，就把數(shù)組中已經(jīng)存在的數(shù)據(jù)的標記更新一下，進行自增。當數(shù)組滿了后，就將數(shù)字最大的元素刪除掉。

每訪問一個元素，就將被訪問的元素的數(shù)字置為 0 。

這不就是 LRU 算法的一個實現(xiàn)方案嗎？

按照這個思路，擼一份七七八八的代碼出來，問題應該不大吧？

但是這一種方案的弊端也是很明顯：需要不停地維護數(shù)組中元素的標記。

那么你覺得它的時間復雜度是多少？

是的，每次操作都伴隨著一次遍歷數(shù)組修改標記的操作，所以時間復雜度是 O(n)。

但是這個方案，面試官肯定是不會滿意的。因為，這不是他心中的標準答案。

也許他都沒想過：你還能給出這種方案呢？

但是它不會說出來，只會輕輕的說一句：還有其他的方案嗎？

方案二：鏈表

于是你扣著腦殼想了想。最近最少使用，感覺是需要一個有序的結(jié)構(gòu)。

我每插入一個元素的時候，就追加在數(shù)組的末尾。

等等。

我每訪問一個元素，也要把被訪問的元素移動到數(shù)組的末尾。

這樣最近被用的一定是在最后面的，頭部的就是最近最少使用的。

當指定長度被用完了之后，就把頭部元素移除掉就行了。

這是個什么結(jié)構(gòu)？

這不就是個鏈表嗎？

維護一個有序單鏈表，越靠近鏈表頭部的結(jié)點是越早之前訪問的。

當有一個新的數(shù)據(jù)被訪問時，我們從鏈表頭部開始順序遍歷鏈表。

如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個數(shù)據(jù)的對應結(jié)點，并將其從原來的位置刪除，并插入到鏈表尾部。

如果此數(shù)據(jù)沒在緩存鏈表中，怎么辦？

分兩種情況：

• 如果此時緩存未滿，可直接在鏈表尾部插入新節(jié)點存儲此數(shù)據(jù)；

• 如果此時緩存已滿，則刪除鏈表頭部節(jié)點，再在鏈表尾部插入新節(jié)點。

你看，這不又是 LRU 算法的一個實現(xiàn)方案嗎？

按照這個思路，擼一份八九不離十的代碼出來，問題應該不大吧？

這個方案比數(shù)組的方案好在哪里呢？

我覺得就是莫名其妙的高級感，就是看起來就比數(shù)組高級了一點。

從時間復雜度的角度看，因為鏈表插入、查詢的時候都要遍歷鏈表，查看數(shù)據(jù)是否存在，所以它還是O(n)。

總之，這也不是面試官想要的答案。

當你回答出這個方案之后，面試官也許會說： 你能不能給我一個查詢和插入的時間復雜度都是O(1)的解決方案？

到這里，如果第一次遇到這題，就得看天分了。

有一說一，如果我之前完全沒有接觸過 LRU 算法，我可以非常自信的說：

方案三：雙向鏈表+哈希表

如果我們想要查詢和插入的時間復雜度都是 O(1)，那么我們需要一個滿足下面三個條件的數(shù)據(jù)結(jié)構(gòu)：

• 1.首先這個數(shù)據(jù)結(jié)構(gòu)必須是有時序的，以區(qū)分最近使用的和很久沒有使用的數(shù)據(jù)，當容量滿了之后，要刪除最久未使用的那個元素。

• 2.要在這個數(shù)據(jù)結(jié)構(gòu)中快速找到某個 key 是否存在，并返回其對應的 value。

• 3.每次訪問這個數(shù)據(jù)結(jié)構(gòu)中的某個 key，需要將這個元素變?yōu)樽罱褂玫?。也就是說，這個數(shù)據(jù)結(jié)構(gòu)要支持在任意位置快速插入和刪除元素。

那么，你說什么樣的數(shù)據(jù)結(jié)構(gòu)同時符合上面的條件呢？

查找快，我們能想到哈希表。但是哈希表的數(shù)據(jù)是亂序的。

有序，我們能想到鏈表，插入、刪除都很快，但是查詢慢。

所以，我們得讓哈希表和鏈表結(jié)合一下，成長一下，形成一個新的數(shù)據(jù)結(jié)構(gòu)，那就是：哈希鏈表，LinkedHashMap。

這個結(jié)構(gòu)大概長這樣：

借助這個結(jié)構(gòu)，我們再來分析一下上面的三個條件：

• 1.如果每次默認從鏈表尾部添加元素，那么顯然越靠近尾部的元素就越是最近使用的。越靠近頭部的元素就是越久未使用的。

• 2.對于某一個 key ，可以通過哈希表快速定位到鏈表中的節(jié)點，從而取得對應的 value。

• 3.鏈表顯示是支持在任意位置快速插入和刪除的，修改指針就行。但是單鏈表無非按照索引快速訪問某一個位置的元素，都是需要遍歷鏈表的，所以這里借助哈希表，可以通過 key，快速的映射到任意一個鏈表節(jié)點，然后進行插入和刪除。

這才是面試官想要關(guān)于 LRU 的正確答案。

但是你以為回答到這里就結(jié)束了嗎？

面試官為了確認你的掌握程度，還會追問一下。

那么請問： 為什么這里要用雙鏈表呢，單鏈表為什么不行？

你心里一慌：我靠，這題我也背過。一時想不起來了。

所以，別只顧著背答案，得理解。

你想啊，我們是不是涉及到刪除元素的操作？

那么鏈表刪除元素除了自己本身的指針信息，還需要什么東西？

是不是還需要前驅(qū)節(jié)點的指針？

那么我們這里要求時間復雜度是O(1)，所以怎么才能直接獲取到前驅(qū)節(jié)點的指針？

這玩意是不是就得上雙鏈表？

咦，你看在一波靈魂追問中，就得到了答案。

面試官的第二個問題又隨之而來了： 哈希表里面已經(jīng)保存了 key ，那么鏈表中為什么還要存儲 key 和 value 呢，只存入 value 不就行了？

不會，也不要慌，你先分析一波。

剛剛我們說刪除鏈表中的節(jié)點，需要借助雙鏈表來實現(xiàn) O(1)。

刪除了鏈表中的節(jié)點，然后呢？

是不是還忘記了什么東西？

是不是還有一個哈希表忘記操作了？

哈希表是不是也得進行對應的刪除操作？

刪除哈希表需要什么東西？

是不是需要 key，才能刪除對應的 value？

這個 key 從哪里來？

是不是只能從鏈表中的結(jié)點里面來？

如果鏈表中的結(jié)點，只有 value 沒有 key，那么我們就無法刪除哈希表的 key。那不就完犢子了嗎？

又是一波靈魂追問。

所以，你現(xiàn)在知道答案了嗎？

另外在多說一句，有的小伙伴可能會直接回答借助 LinkedHashMap 來實現(xiàn)。

我覺得吧，你要是實在不知道，也可以這樣說。

但是，這個回答可能是面試官最不想聽到的回答了。

他會覺得你投機取巧。

但是呢，實際開發(fā)中，真正要用的時候，我們還是用的 LinkedHashMap。

而且更多的實際情況是，你開發(fā)，寫業(yè)務代碼的時候，根本就不會用到 LRU 算法。

你說這個事情，難受不難受。

好了，你以為到這里面試就結(jié)束了？

天真。

LRU 在 MySQL 中的應用

面試官：小伙子剛剛 LRU 回答的不錯哈。要不你給我講講，LRU 在 MySQL 中的應用？

LRU 在 MySQL 的應用就是 Buffer Pool，也就是緩沖池。

它的目的是為了減少磁盤 IO。

緩沖池具體是干啥的，我這里就不展開說了。

你就知道它是一塊連續(xù)的內(nèi)存，默認大小 128M，可以進行修改。

這一塊連續(xù)的內(nèi)存，被劃分為若干默認大小為 16KB 的頁。

既然它是一個 pool，那么必然有滿了的時候，怎么辦？

就得移除某些頁了，對吧？

那么問題就來了：移除哪些頁呢？

剛剛說了，它是為了減少磁盤 IO。所以應該淘汰掉很久沒有被訪問過的頁。

很久沒有使用，這不就是 LRU 的主場嗎？

但是在 MySQL 里面并不是簡單的使用了 LRU 算法。

因為 MySQL 里面有一個預讀功能。預讀的出發(fā)點是好的，但是有可能預讀到并不需要被使用的頁。

這些頁也被放到了鏈表的頭部，容量不夠，導致尾部元素被淘汰。

哦豁，降低命中率了，涼涼。

還有一個場景是全表掃描的 sql，有可能直接把整個緩沖池里面的緩沖頁都換了一遍，影響其他查詢語句在緩沖池的命中率。

那么怎么處理這種場景呢？

把 LRU 鏈表分為兩截，一截里面放的是熱數(shù)據(jù)，一截里面放的是冷數(shù)據(jù)。

打住，不能再說了。

再說就是另外一篇文章了，點到為止。

你就了解在 MySQL 里面，LRU 是有一個變種的。

如果你不清楚，建議去學習一下哦。

只要你學的夠快，你就會被卷的越慢。

LRU 在 Redis 中的應用

既然是內(nèi)存淘汰算法，那么我們常用的 Redis 里面必然也有對應的實現(xiàn)。

Redis 的內(nèi)存淘汰策略有如下幾種：

• noenviction：默認策略。不繼續(xù)執(zhí)行寫請求（DEL 請求可以處理），讀請求可以繼續(xù)進行。

• volatile-lru：從已設(shè)置過期時間的數(shù)據(jù)集中挑選最近最少使用的數(shù)據(jù)淘汰。沒有設(shè)置過期時間的 key 不會被淘汰。

• volatile-random：從已設(shè)置過期時間的數(shù)據(jù)集中隨機選擇數(shù)據(jù)淘汰。

• volatile-ttl：從已設(shè)置過期時間的數(shù)據(jù)集中挑選將要過期的數(shù)據(jù)淘汰。

• allkeys-lru：和 volatile-lru 不同的是，這個策略要淘汰的 key 對象是全體的 key 集合。

• allkeys-random：從所有數(shù)據(jù)集中隨機選擇數(shù)據(jù)淘汰。

關(guān)于 Redis 中的 LRU 算法，官網(wǎng)上是這樣說的：

https://github.com/redis/redis-doc/blob/master/topics/lru-cache.md

在 Redis 中的 LRU 算法不是嚴格的 LRU 算法。

Redis 會嘗試執(zhí)行一個近似的LRU算法，通過采樣一小部分鍵，然后在采樣鍵中回收最適合的那個，也就是最久沒有被訪問的那個（with the oldest access time）。

然而，從 Redis 3.0 開始，改善了算法的性能，使得更接近于真實的 LRU 算法。做法就是維護了一個回收候選鍵池。

Redis 的 LRU 算法有一個非常重要的點就是你可以通過修改下面這個參數(shù)的配置，自己調(diào)整算法的精度。

maxmemory-samples 5

而上面截圖中，我認為最重要的一句話也已經(jīng)標志出來了：

The reason why Redis does not use a true LRU implementation is because it costs more memory.

Redis 沒有使用真實的 LRU 算法的原因是因為這會消耗更多的內(nèi)存。

然后官網(wǎng)上給了一個隨機 LRU 算法和嚴格 LRU 算法的對比圖：

對于這個圖官網(wǎng)是這樣說的：

你可以從圖中看到三種不同的小圓點形成的三個不同的帶：

• 淺灰色帶是被回收（被 LRU 算法淘汰）的對象

• 灰色帶是沒有被回收的對象

• 綠色帶是新添加的對象

由于 Redis 3.0 對 LRU 算法進行了改進，增加了淘汰池。

所以你可以看到，同樣使用 5 個采樣點，Redis 3.0 表現(xiàn)得比 Redis 2.8 要好。

同時可以看出，在 Redis 3.0 中使用 10 為采樣大小，近似值已經(jīng)非常接近理論性能。

寫到這里我突然想起了另外一個面試題。

數(shù)據(jù)庫中有 3000w 的數(shù)據(jù)，而 Redis 中只有 100w 數(shù)據(jù)，如何保證 Redis 中存放的都是熱點數(shù)據(jù)？

這個題你說它的考點是什么？

考的就是淘汰策略呀，同志們，只是方式比較隱晦而已。

我們先指定淘汰策略為 allkeys-lru 或者 volatile-lru，然后再計算一下 100w 數(shù)據(jù)大概占用多少內(nèi)存，根據(jù)算出來的內(nèi)存，限定 Redis 占用的內(nèi)存。

接下來的，就交給 Redis 的淘汰策略了。

搞定。