當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

cache 的设计与实现--转载

發布時間：2025/4/5 编程问答 33 豆豆

生活随笔收集整理的這篇文章主要介紹了 cache 的设计与实现--转载小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

本文整理自一下兩篇博客：http://my.oschina.net/ScottYang/blog/298727http://my.oschina.net/u/866190/blog/188712

Cache簡介：

??? Cache(高速緩存)，一個在計算機中幾乎隨時接觸的概念。CPU中Cache能極大提高存取數據和指令的時間，讓整個存儲器(Cache+內存)既有Cache的高速度，又能有內存的大容量；操作系統中的內存page中使用的Cache能使得頻繁讀取的內存磁盤文件較少的被置換出內存，從而提高訪問速度。Cache的算法設計常見的有FIFO(first in first out，先進先出)、LRU(least recently used，最近最少使用)和LFU（Least Frequently userd，最不經常使用)。

LRU(Least Recently Used ，最近最少使用) —— 刪除最久沒有被使用過的數據

??? 算法根據數據的最近訪問記錄來淘汰數據，其原理是如果數據最近被訪問過，將來被訪問的幾概率相對比較高，最常見的實現是使用一個鏈表保存緩存數據，詳細具體算法如下：

1. 新數據插入到鏈表頭部；

2. 每當緩存數據命中，則將數據移到鏈表頭部；

3. 當鏈表滿的時候，將鏈表尾部的數據丟棄；

LFU(Least Frequently Used，最不經常使用) —— 刪除使用次數最少的的數據

??? 算法根據數據的歷史訪問頻率來淘汰數據，其原理是如果數據過去被訪問次數越多，將來被訪問的幾概率相對比較高。LFU的每個數據塊都有一個引用計數，所有數據塊按照引用計數排序，具有相同引用計數的數據塊則按照時間排序。具體算法如下：

1. 新加入數據插入到隊列尾部（因為引用計數為1）；?
2. 隊列中的數據被訪問后，引用計數增加，隊列重新排序；?
3. 當需要淘汰數據時，將已經排序的列表最后的數據塊刪除；

FIFO(First In First Out ，先進先出)

??? 算法是根據先進先出原理來淘汰數據的，實現上是最簡單的一種,具體算法如下：

1. 新訪問的數據插入FIFO隊列尾部，數據在FIFO隊列中順序移動；?
2. 淘汰FIFO隊列頭部的數據；

??????? 評價一個緩存算法好壞的標準主要有兩個，一是命中率要高，二是算法要容易實現。當存在熱點數據時，LRU的效率很好，但偶發性的、周期性的批量操作會導致LRU命中率急劇下降，緩存污染情況比較嚴重。LFU效率要優于LRU，且能夠避免周期性或者偶發性的操作導致緩存命中率下降的問題。但LFU需要記錄數據的歷史訪問記錄，一旦數據訪問模式改變，LFU需要更長時間來適用新的訪問模式，即：LFU存在歷史數據影響將來數據的“緩存污染”效用。FIFO雖然實現很簡單，但是命中率很低，實際上也很少使用這種算法。

面試題：Google和百度的面試題都出現了設計一個Cache的題目，什么是Cache，如何設計簡單的Cache

解題思路：

??? Cache中的存儲空間往往是有限的，當Cache中的存儲塊被用完，而需要把新的數據Load進Cache的時候，我們就需要設計一種良好的算法來完成數據塊的替換。LRU的思想是基于“最近用到的數據被重用的概率比較早用到的大的多”這個設計規則來實現的。

??? 為了能夠快速刪除最久沒有訪問的數據項和插入最新的數據項，我們雙向鏈表連接Cache中的數據項，并且保證鏈表維持數據項從最近訪問到最舊訪問的順序。每次數據項被查詢到時，都將此數據項移動到鏈表頭部（O(1)的時間復雜度）。這樣，在進行過多次查找操作后，最近被使用過的內容就向鏈表的頭移動，而沒有被使用的內容就向鏈表的后面移動。當需要替換時，鏈表最后的位置就是最近最少被使用的數據項，我們只需要將最新的數據項放在鏈表頭部，當Cache滿時，淘汰鏈表最后的位置就是了。?
注：對于雙向鏈表的使用，基于兩個考慮。首先是Cache中塊的命中可能是隨機的，和Load進來的順序無關。其次，雙向鏈表插入、刪除很快，可以靈活的調整相互間的次序，時間復雜度為O(1)。?
??? 查找一個鏈表中元素的時間復雜度是O(n)，每次命中的時候，我們就需要花費O(n)的時間來進行查找，如果不添加其他的數據結構，這個就是我們能實現的最高效率了。目前看來，整個算法的瓶頸就是在查找這里了，怎么樣才能提高查找的效率呢？Hash表，對，就是它，數據結構中之所以有它，就是因為它的查找時間復雜度是O(1)。

??? 梳理一下思路：對于Cache的每個數據塊，我們設計一個數據結構來儲存Cache塊的內容，并實現一個雙向鏈表，其中屬性next和prev時雙向鏈表的兩個指針，key用于存儲對象的鍵值，value用戶存儲要cache塊對象本身。

Cache的接口：

查詢：

根據鍵值查詢hashmap，若命中，則返回節點，否則返回null。
從雙向鏈表中刪除命中的節點，將其重新插入到表頭。
所有操作的復雜度均為O(1)。

??? 插入：

將新的節點關聯到Hashmap
如果Cache滿了，刪除雙向鏈表的尾節點，同時刪除Hashmap對應的記錄
將新的節點插入到雙向鏈表中頭部

??? 更新：

- 和查詢相似

??? 刪除：

- 從雙向鏈表和Hashmap中同時刪除對應的記錄。

實現方式

??? 參考實現：Apache jcs

??? 1）首先我們需要一個雙向鏈表，自然地，我們需要定義雙向鏈表的節點：DoubleLinkListNode，DoubleLinkList

// 雙向鏈表節點 public class DoubleLinkListNode implements Serializable{private Object value;public DoubleLinkListNode next;public DoubleLinkListNode prev;DoubleLinkListNode(Object value){this.value = value;}public Object getValue() {return value;} }

??????? 對于?DoubleLinkList ,我們需要同步對節點的各種讀寫操作：

public class DoubleLinkList {private int size = 0;private DoubleLinkListNode first;private DoubleLinkListNode last;public DoubleLinkList(){super();}// 在鏈表的尾部的插入一個節點public synchronized void addLast(DoubleLinkListNode me){if (first == null) {first = me;}else{last.next = me;me.prev = last;}last = me;size++;}// 在鏈表的頭部插入一個節點public synchronized void addFirtst(DoubleLinkListNode me){if (last == null) {last = me;}else{first.next = me;me.prev = first;}first = me;size++;}// 獲取尾節點public synchronized DoubleLinkListNode getLast(){return last;}// 獲取頭結點public synchronized DoubleLinkListNode getFirst(){return first;}// 刪除鏈表指定節點（這個節點一定在鏈表中）public synchronized boolean remove(DoubleLinkListNode me){if(me.next == null){//刪除尾節點if (me.prev == null) {// Make sure it really is the only node before setting head and// tail to null. It is possible that we will be passed a node// which has already been removed from the list, in which case// we should ignore itif ( me == first && me == last ){first = last = null;}} else {last = me.prev;last.next = null;me.prev = null;// gc 回收需要}}else if(me.prev == null){// 頭結點first = me.next;first.prev = null;me.next = null;}else{// 中間節點me.prev.next = me.next;me.next.prev = me.prev;me.prev = me.next = null;}size--;return true;}// 刪除鏈表所有元素// 注意不能只執行 first = last = null,這樣會引起 OutOfMemorypublic synchronized boolean removeAll(){for(DoubleLinkListNode me=first;me!=null;){if (me.prev != null) {me.prev = null;}DoubleLinkListNode next = me.next;me = next;}first = last = null;size = 0;return true;}// 刪除鏈表的尾節點public synchronized DoubleLinkListNode removeLast(){DoubleLinkListNode temp = last;if (last != null) {remove(last);}return temp;}// 將節點 node 移到頭部public synchronized void makeFirst(DoubleLinkListNode node){if (node.prev == null) {// already the first node , or not a nodereturn;}node.prev.next = node.next;if (node.next == null) {// last but the firstlast = node.prev;last.next = null;}else {//neither the last or the firstnode.next.prev = node.prev;}first.prev = node;node.next = first;node.prev = null;first = node;}public synchronized int size(){return size;} }

??? 2）雙向鏈表實現了，接著我們需要實現一個自定義的 LRUMap，根據 key 來存儲 DoubleLinkListNode。這樣我們就可以借助map 的hash 表來查詢相對應的值。

·在給出實現之前，我們也許回想到，map 的鍵值對中，key 自己創建，而 value 就是 DoubleLinkListNode，來實現這個map，在 put 的時候，根據需要調整 cache 的容量即可（LRU 算法）。

??? 如果是這樣想得，那我們再反過來想，其實 map 本事就是一個容器，可直接用作 cache，直接使用 Map(Object key,Object value) 比使用 Map(Object key,doubleLinkListNode node)更好，可這樣做的時候，就會出現一個問題，當我們需要刪除一個對象，準確地說，是刪除一個最近最久沒有被使用過得對象，這樣的操作原始的 map 結果是實現不了的；或許更進一步，你會想到，我們可以 map 里的每一個對象添加一個時間標記，這樣在刪除的時候，需要遍歷每一個對象，找出時間標記為最早的那一個，直接就刪除它（這樣做，效率會很不好，需要O(n) 的時間）。說道這里，其實就是想說，借助雙鏈表就是為了快速刪除最近最久未被使用的對象，所以我們需要搭建一個描述符，來關聯 hashMap 和雙聯表之間的關系。

先實現一個 map 鍵值對描述符，如下：

public class LRUElementDescriptor extends DoubleLinkListNode {private Object key;public LRUElementDescriptor(Object key,Object value){super(value);this.key = key;}public Object getKey() {return key;}public void setKey(Object key) {this.key = key;} }

???? 接著實現一下LRUMap 基本的操作，如下：

import java.util.Collection; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Set;@SuppressWarnings("unchecked") public class LRUMap implements Map {// 在 LRUMap 里，需要使用到 map，DoubleLinkListprivate DoubleLinkList list = null;private Map map = null;private int maxSize = -1; //cache 容量，< 0 時，表示容量不限private int chunkSize = 1; //當cache 溢出時，需要刪除對象的個數,最好驗證 chunkSize < maxSizepublic LRUMap(){list = new DoubleLinkList();map = new HashMap();}public LRUMap(int size){this();this.maxSize = size;}public void clear() {map.clear();list.removeAll();}public boolean containsKey(Object key) {return map.containsKey(key);}public boolean containsValue(Object value) {return map.containsValue(value);}//返回 key-value 值，注意不是 key-DoubleLinkListNodepublic Set entrySet() {Set entries = map.entrySet();Set unWraped = new HashSet();Iterator it = entries.iterator();while (it.hasNext()) {Entry pre = (Entry) it.next();Entry post = new LRUMapEntry(pre.getKey(),((LRUElementDescriptor)pre.getValue()).getValue());;unWraped.add(post);}return unWraped;}public Object get(Object key) {Object value = null;LRUElementDescriptor elem = (LRUElementDescriptor)map.get(key);if (elem !=null) {value = elem.getValue();list.makeFirst(elem);}return value;}public boolean isEmpty() {return map.size() == 0;}public Set keySet() {return map.keySet();}public Object put(Object key, Object value) {LRUElementDescriptor old = null;synchronized (this) {addFirst(key, value);old = (LRUElementDescriptor) map.put(((LRUElementDescriptor)list.getFirst()).getKey(),list.getFirst());// 若已經存在于緩存里，則刪除舊的if (old != null && ((LRUElementDescriptor)list.getFirst()).getKey().equals(old.getKey())) {list.remove(old);}}// 判斷是否溢出，若溢出，則刪除最后 chunkSize 個元素int size = map.size();if (this.maxSize >=0 && this.maxSize < size) {for(int i = 0;i<chunkSize;i++){LRUElementDescriptor last = (LRUElementDescriptor) list.getLast();if (last != null) {map.remove(last.getKey());}else{System.err.println("update: remove failed for key:"+last.getKey());}list.removeLast();}}// Map.put 操作的返回值if(old != null){return old.getValue();}return null;}public synchronized void addFirst (Object key,Object value){LRUElementDescriptor elem = new LRUElementDescriptor(key,value);list.addFirtst(elem);}public void putAll(Map source) {if (source != null) {Set entries = source.entrySet();Iterator it = entries.iterator();while (it.hasNext()) {Entry elem = (Entry) it.next();// 這里不是使用 map.put，因為這樣 DoubleLinkList 就會失去作用this.put(elem.getKey(), elem.getValue());}}}public Object remove(Object key) {LRUElementDescriptor elem =(LRUElementDescriptor) map.remove(key);if (elem != null) {list.remove(elem);return elem.getValue();}return null;}public int size() {return map.size();}// DoubleLinkListNode 的集合public Collection values() {return map.values();}}

?原文：http://peiquan.blog.51cto.com/7518552/1558294

轉載于:https://www.cnblogs.com/davidwang456/p/4001342.html

總結

以上是生活随笔為你收集整理的cache 的设计与实现--转载的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

cache

上一篇： SHELL网络爬虫实例剖析--转载
下一篇：基于注解的Spring AOP的配置和使