① lru演算法是什麼
lru演算法是一種頁面置換演算法，在對於內存中但是又不用的數據塊，叫做LRU，操作系統會根據那些數據屬於LRU而將其移出內存而騰出空間來載入另外的數據。
LRU演算法：最近最少使用，簡單來說就是將數據塊中，每次使用過的數據放在數據塊的最前端，然後將存在的時間最長的，也就是數據塊的末端的數據剔除掉這就是LRU演算法。
如果進程被調度，該進程需要使用的外存頁（數據）不存在於數據塊中，這個現象就叫做缺頁。如果這個數據此時不在，就會將這個數據從加入到數據塊首部。
數據塊插入與剔除：每次有新數據到來時，會將其放入數據塊首部，當數據每次被訪問時，將這個數據插入數據塊的首部如果數據塊滿了，每次新進的數據都會將數據塊尾部的數據擠出數據塊。
差距
為了盡量減少與理想演算法的差距，產生了各種精妙的演算法，最少使用頁面置換演算法便是其中一個。LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。
反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。
LRU在電子系統中的解釋：
Line Replaceable Unit—LRU，電子系統中常採用模塊化設計，這種可更換的模塊單元則被叫做LRU，中文名稱是「線性可更換單元」。
② lru演算法是什麼
是一種緩存淘汰策略。計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新內容騰位置。大家肯定希望刪掉哪些沒什麼用的緩存，而把有用的數據繼續留在緩存里，方便之後繼續使用。
LRU緩存淘汰演算法就是一種常用策略，也就是說認為最近使用過的數據應該是是「有用的」，很久都沒用過的數據應該是無用的，內存滿了就優先刪那些很久沒用過的數據。
LRU-K原理
LRU-K中的K代表最近使用的次數，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU演算法「緩存污染」的問題，其核心思想是將「最近使用過1次」的判斷標准擴展為「最近使用過K次」。
相比LRU，LRU-K需要多維護一個隊列，用於記錄所有緩存數據被訪問的歷史。只有當數據的訪問次數達到K次的時候，才將數據放入緩存。當需要淘汰數據時，LRU-K會淘汰第K次訪問時間距當前時間最大的數據。
③ LRU與LFU
LFU的push遇到重復元素不刪除key，只是get更新key之後對value進行覆蓋。
map<int,pair<int,list<pair<int,int>>::iterator>>KeyFreq 用iterator指向FreqList的List中的一個節點。
在數據訪問符合正態分布時，相比於LRU演算法，LFU演算法的緩存命中率會高一些。
(1)LFU的復雜度要比LRU更高一些。
(2)需要維護數據的訪問頻次，每次訪問都需要更新。
(3)早期的數據相比於後期的數據更容易被緩存下來，導致後期的數據很難被緩存。
(4)新加入緩存的數據很容易被剔除，像是緩存的末端發生「抖動」。
④ lru的演算法是什麼
lru的演算法是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。
對於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入內存，同時為了保持原有空間的大小，還要把一個內種調動越少，進程執行的效率也就越高。
硬體支持
LRU置換演算法雖然是一種比較好的演算法，但要求系統有較多的支持硬體。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬體之一的支持：寄存器或棧。
寄存器
為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為：
R = Rn-1 Rn-2 Rn-3…R2 R1 R0。
⑤ 分布式存儲最佳緩存比
作者：深入細節的 SmartX 一線技術團隊
近日，VMware 發布了 vSAN 8，對存儲架構進行了重大更新。其中最主要的變化，即引入了新的 Express Storage Architecture（ESA）架構：用「存儲池」替代了原存儲架構（OSA）中的「磁碟組」，並不再需要專用 SSD 承擔緩存加速功能，一定程度上避免了 8.0 之前版本中的專用緩存檔利用率低、易發生緩存擊穿等問題。
而值得一提的是，在 vSAN 大版本更新之前，SmartX 即通過統一緩存空間和智能冷熱數據管理優化了分布式存儲緩存機制，有效規避了上述問題。本文將通過重點解讀 vSAN（以 vSAN 7 為例）和 SmartX 分布式塊存儲組件 ZBS* 緩存機制的原理，並測試對比兩種緩存機制下虛擬機性能表現，讓讀者更好地了解兩種技術實現機制的區別對業務可能帶來的實際影響。
* ZBS 內置於 SmartX 超融合軟體 SMTX OS，可與 SmartX 原生虛擬化 ELF 搭配提供服務。
本文重點
vSAN 7 採用劃分讀寫緩存空間的機制，將緩存磁碟按照容量佔比劃分為寫緩沖區（30%）和讀緩存區（70%）。這種方式可能出現緩存利用率低、在訪問數據量過大時導致緩存擊穿，進而引起性能下降等問題。
ZBS 採用統一緩存空間的機制，並通過 2 級 LRU 演算法對冷熱數據進行管理，在充分利用緩存容量的同時避免了因訪問量激增導致虛擬機性能下降的情況。
本文基於相同的硬體配置和 I/O 讀寫場景，分別測試 VMware 超融合（vSphere 虛擬化 + vSAN 分布式存儲）寫入 300 GB 數據、SMTX OS（ELF + ZBS）寫入 500 GB 數據時虛擬機的性能表現。結果顯示，vSAN 7 難以充分利用緩存介質，發生緩存擊穿，導致存儲性能下降；而 SMTX OS 即便在寫入更多數據的情況下也未發生緩存擊穿，虛擬機性能保持穩定。
場景問題
混閃配置是超融合或分布式存儲現階段的主流落地模式。混閃配置是指機器中的磁碟使用 SSD + HDD 混合組成，其中 SSD 磁碟作為數據緩存層，而 HDD 磁碟作為數據容量層。以該模式構建的分布式存儲池通過軟體演算法進行冷熱數據自動判斷，在提供高性能的同時，還可獲得較大的存儲容量，進而提升資源利用率，獲得相對全快閃記憶體儲更高的性價比。
在將 SSD 磁碟用作數據緩存層時，部分超融合產品會將緩存容量（Cache）劃分為讀和寫各自獨立的兩部分。例如，vSAN 7 及更早版本會將每個磁碟組（Disk Group）中的緩存磁碟，按照容量佔比劃分為寫緩沖區（30%）和讀緩存區（70%），當讀取數據未命中緩存或者寫緩存已滿，將會直接從容量層進行讀寫。
⑥ LRU 緩存淘汰演算法
當要緩存某個數據的時候，先在鏈表中查找這個數據。如果沒有找到，則直接將數據放到鏈表的尾部；如果找到了，我們就把它移動到鏈表的尾部，然後淘汰頭部數據。
因為查找數據需要遍歷鏈表，所以單純用鏈表實現的 LRU 緩存淘汰演算法的時間復雜很高，是 O(n)。如果我們將散列表和雙向鏈表兩種數據結構組合使用，可以將這三個操作的時間復雜度都降低到 O(1)。
因為我們的散列表是通過鏈表法解決散列沖突的，所以每個結點會在兩條鏈中。一個鏈是剛剛我們提到的雙向鏈表，另一個鏈是散列表中的拉鏈。前驅和後繼指針是為了將結點串在雙向鏈表中，hnext 指針是為了將結點串在散列表的拉鏈中。
這整個過程涉及的查找操作都可以通過散列表來完成。其他的操作，比如刪除頭結點、鏈表尾部插入數據等，通過雙向鏈表都可以在 O(1) 的時間復雜度內完成。所以，這三個操作的時間復雜度都是 O(1)。
至此，我們就通過散列表和雙向鏈表的組合使用，實現了一個高效的、支持 LRU 緩存淘汰演算法的緩存系統原型。
散列表中數據是經過散列函數打亂之後無規律存儲的，但是 LinkedHashMap可以 做到按照數據的插入順序來存儲。
每次調用 put() 函數，往 LinkedHashMap 中添加數據的時候，都會將數據添加到鏈表的尾部，再次將鍵值為 3 的數據放入到 LinkedHashMap 的時候，會先查找這個鍵值是否已經有了，然後，再將已經存在的 (3,11) 刪除，並且將新的 (3,26) 放到鏈表的尾部，訪問到 key 為 5 的數據的時候，我們將被訪問到的數據移動到鏈表的尾部。
所以按照訪問時間排序的 LinkedHashMap 本身就是一個支持 LRU 緩存淘汰策略的緩存系統。
散列表這種數據結構雖然支持非常高效的數據插入、刪除、查找操作，但是散列表中的數據都是通過散列函數打亂之後無規律存儲的。也就說，它無法支持按照某種順序快速地遍歷數據。如果希望按照順序遍歷散列表中的數據，那我們需要將散列表中的數據拷貝到數組中，然後排序，再遍歷。
因為散列表是動態數據結構，不停地有數據的插入、刪除，所以每當我們希望按順序遍歷散列表中的數據的時候，都需要先排序，那效率勢必會很低。為了解決這個問題，我們將散列表和鏈表（或者跳錶）結合在一起使用。
⑦ 如何用LinkedHashMap實現LRU緩存演算法
緩存這個東西就是為了提高運行速度的，由於緩存是在寸土寸金的內存裡面，不是在硬碟
裡面，所以容量是很有限的。LRU這個演算法就是把最近一次使用時間離現在時間最遠的數據刪除掉。先說說List：每次訪問一個元素後把這個元素放在
List一端，這樣一來最遠使用的元素自然就被放到List的另一端。緩存滿了t的時候就把那最遠使用的元素remove掉。但更實用的是
HashMap。因為List太慢，要刪掉的數據總是位於List底層數組的第一個位置，刪掉之後，後面的數據要向前補位。。所以復雜度是O(n)，那就
用鏈表結構的LinkedHashMap唄~，LinkedHashMap默認的元素順序是put的順序，但是如果使用帶參數的構造函數，那麼
LinkedHashMap會根據訪問順序來調整內部 順序。
LinkedHashMap的get()方法除了返回元素之外還可以把被訪問的元素放到鏈表的底端，這樣一來每次頂端的元素就是remove的元素。
構造函數如下：
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；
initialCapacity 初始容量
loadFactor 載入因子，一般是 0.75f
accessOrder false 基於插入順序 true 基於訪問順序（get一個元素後，這個元素被加到最後，使用了LRU 最近最少被使用的調度演算法）
來個例子吧：
import java.util.*;
class Test
{
public static void main(String[] args) throws Exception{
Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
//現在遍歷的話順序肯定是9,7,5,3
//下面訪問了一下9,3這個鍵值對，輸出順序就變嘍~
map.get(9);
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
輸出
7
5
3
9
好玩吧~
下面開始實現LRU緩存嘍~
import java.util.*;
//擴展一下LinkedHashMap這個類，讓他實現LRU演算法
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{
//定義緩存的容量
private int capacity;
private static final long serialVersionUID = 1L;
//帶參數的構造器
LRULinkedHashMap(int capacity){
//調用LinkedHashMap的構造器，傳入以下參數
super(16,0.75f,true);
//傳入指定的緩存最大容量
this.capacity=capacity;
}
//實現LRU的關鍵方法，如果map裡面的元素個數大於了緩存最大容量，則刪除鏈表的頂端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
}
//測試類
class Test{
public static void main(String[] args) throws Exception{
//指定緩存最大容量為4
Map<Integer,Integer> map=new LRULinkedHashMap<>(4);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
map.put(6,6);
//總共put了5個元素，超過了指定的緩存最大容量
//遍歷結果
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
輸出結果如下
9=3
9=3
9=3
9=3
9=3
7
5
3
6
分析一下：使用帶參數構造器，且啟用LRU模式的LinkedHashMap會在每次有新元素加入的時候，判斷當前儲存元素是否超過了緩存上限，也就是執行
一次removeEldestEntry方法，看最後的遍歷結果，發現果然把9刪除了，LRU發揮作用了~
⑧ lru演算法是什麼
LRU是Least Recently Used的縮寫，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。
該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間t，當須淘汰一個頁面時，選擇現有頁面中其t值最大的，即最近最少使用的頁面予以淘汰。
特點：
LRU 演算法弊端是存在偶發性、周期性的批量操會降低緩存的命中率，對緩存造成污染，下面幾個就是改進演算法。
LRU-K會記錄每條數據的訪問歷史，當達到 k 時，才將數據存放到緩存，在緩存內存回收時，緩存中越接近 k 的數據被優先刪除。
Two queues（2Q）相當於 LRU-2，區別是訪問歷史（首次訪問）數據緩存於 FIFO 隊列，二次及以上的數據存放LRU緩存，FIFO 隊列數據遵循該緩存的內存回收機制，LRU緩存數據遵循該緩存的內存回收機制。
⑨ 頁面置換演算法之LRU演算法
三種常見的頁面置換演算法:FIFO、LFU、LRU
參考：
緩存演算法（頁面置換演算法）-FIFO、LFU、LRU
LRU（Least Recently Used，最近最少使用）演算法根據數據的歷史訪問記錄來進行淘汰數據，其核心思想是： 如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小 。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。
假設 序列為 4 3 4 2 3 1 4 2
物理塊有3個 則
首輪 4調入內存 4
次輪 3調入內存 3 4
之後 4調入內存 4 3
之後 2調入內存 2 4 3
之後 3調入內存 3 2 4
之後 1調入內存 1 3 2（因為最少使用的是4，所以丟棄4）
之後 4調入內存 4 1 3（原理同上）
最後 2調入內存 2 4 1
如果讓我們設計一個LRU Cache的數據結構，它應該支持兩個操作：
一種是採用數組來存儲每個數據項，再對每個key關聯一個時間戳，在cache中維護一個最大時間戳，其設計要點如下：
另一種是採用hashmap+雙向鏈表的數據結構，其設計要點如下：
對比上一節的兩種設計思路，不難發現，設計1需要為每個key維護一個時間戳，而且set和get操作的時間復雜度都是O(n)。顯而易見，隨著數據量的增大，set和get操作的速度越來越慢。而設計2通過採用hashmap+雙向鏈表，set和get操作的時間復雜度只需O(1)，下面給出設計2的具體實現。
運行結果為：
參考：
LRU Cache
LRU原理和Redis實現——一個今日頭條的面試題
⑩ 舉例說明用LRU替換策略cache命中率如何計算
近期最少使用法（LRU法）
近期最少使用（Least Recently Used，LRU）演算法。這種方法是將近期最少使用的Cache中的信息塊替換出去。該演算法較先進先出演算法要好一些。但此法也不能保證過去不常用將來也不常用。
LRU法是依據各塊使用的情況， 總是選擇那個最近最少使用的塊被替換。這種方法雖然比較好地反映了程序局部性規律，但是這種替換方法需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊。LRU演算法相對合理，但實現起來比較復雜，系統開銷較大。通常需要對每一塊設置一個稱為計數器的硬體或軟體模塊，用以記錄其被使用的情況。
實現LRU策略的方法有多種。 下面簡單介紹計數器法、寄存器棧法及硬體邏輯比較對法的設計思路。
計數器方法：緩存的每一塊都設置一個計數器，計數器的操作規則是：
(1) 被調入或者被替換的塊， 其計數器清「0」，而其它的計數器則加「1」。
(2) 當訪問命中時，所有塊的計數值與命中塊的計數值要進行比較，如果計數值小於命中塊的計數值，則該塊的計數值加「1」；如果塊的計數值大於命中塊的計數值，則數值不變。最後將命中塊的計數器清為0。
(3) 需要替換時，則選擇計數值最大的塊被替換。