?utm_source=tuicool&utm_medium=referral
http://www.cnblogs.com/tujia/p/5413028.html
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝PART 1===============
1）memcached不會自動清空緩存的值如果add了一個值，但不去get它，那么這個值過期了，它也不會被清空。解釋：memcached不自動檢測和清空值，它只當你需要get這個值的時候，才檢測這個值是否過期，過期則清空此值，并返回空。
PS：可使用stats命令查詢 memcached的curr_items和total_items狀態
2）memcached不會自動刪除緩存的值即使一個值過期了，memcached也不會刪除它，只了清空了它的值，狀態改為已過期。真正刪除值：只有當memcached內存滿了，有新值需要占用空間，才會的把過期的值刪除，存入新的值。
3）刪除規則剛剛說不自動刪除值，只有當存入新的值，才會刪除過期的值，那么刪除哪一個過期值呢？？
FIFO刪除機制這是其他應用刪除機制，隊列的刪除機制，first in first out，先進先出，刪除最先來的那個值
memcached的LRU刪除機制memcached的刪除機制是LRU刪除機制，它并不是刪除最新存的那個值，而是刪除最少使用的那個值。
PS1：當get key的時候，此key的新鮮度更新為最新鮮，并不是新鮮度+1PS2：這種LRU刪除機制并不是只刪除過期的值，如果memcached內存滿了，即使最近的那個值還沒過期，也會被踢除（永久數據被踢除現象）
=============PART 2==================
memcached是一個高性能的分布式內存緩存服務器，memcached在linux上可以通過yum命令安裝，這樣方便很多，在生產環境下建議用Linux系統，memcached使用libevent這個庫在Linux系統上才能發揮它的高性能。它的分布式其實在服務端是不具有分布式的特征的，是依靠客戶端的分布式算法進行了分布式，memcached是一個純內存型的數據庫，這樣在讀寫速度上相對來說比較快。
memcached的內存分配是預先分配內存，常規的程序使用內存無非是兩種，一種是預先分配，一種是動態分配。動態分配從效率的角度來講相對來說要慢點，因為它需要實時的去分配內存使用，但是這種方式的好處就是可以節約內存使用空間；memcached采用的是預先分配的原則，這種方式是拿空間換時間的方式來提高它的速度，這種方式會造成不能很高效的利用內存空間，但是memcached采用了Slab Allocation機制來解決內存碎片的問題，Slab Allocation的基本原理就是按照預先規定的大小，將分配的內存分割成特定長度的塊，并把尺寸相同的塊分成組（chunk的集合），借用一下網上的圖：
memcached會針對客戶端發送的數據選擇slab并緩存到chunk中，這樣就有一個弊端那就是比如要緩存的數據大小是50個字節，如果被分配到如上圖88字節的chunk中的時候就造成了33個字節的浪費，雖然在內存中不會存在碎片，但是也造成了內存的浪費，這也是我上面說的拿空間換時間的原因，不過memcached對于分配到的內存不會釋放，而是重復利用。默認情況下如下圖chunk是1.25倍的增加的，當然也可以自己通過-f設置，這種內部的分割算法可以參看源碼下的slabs.c文件。
memcached本身內部不會監視記錄是否過期，而是當get時依靠記錄的過期時間檢查是否過期，這也是memcached的一種惰性過期機制。默認情況下memcached內部也維護著一套LRU置換算法，當設定的內存滿的時候，會進行最近很少使用的數據置換出去從而分配空間，所以對于提升memcached命中率的問題主要還是一是根據業務存放的value值來調整好chunk的大小以達到最大效率的利用內存；二是擴大內存保證所有緩存的數據不被置換出去。
對于memcached的分布式完全就是依靠客戶端的一致哈希算法來達到分布式的存儲，因為本身各個memcached的服務器之間沒辦法通信，并不存在副本集或者主從的概念，它的分布式算法主要是先求出每一個memcached的服務器節點的哈希值，并將它們分配到2的32次方的圓上，然后根據存儲的key的哈希值來映射到這個圓上，屬于哪個區間順時針找到的節點就存到這個服務器節點上，大致借用圖表示如下圖：
然而當添加新的memcached節點的時候必然會打亂現有這個圓的結構，這時候是沒辦法完全保證你以前的key依然會存在之前的節點上，但是這種結構卻是能保證在添加緩存服務器的時候把損失降到最小，受結構調整后key不能命中的只有在這個圓上新增的服務器節點逆時針的第一臺服務器上，其他的是不受影響的，借用圖如下：
memcached和redis一樣內部的存儲都是key/Value的形式，正是這種哈希表數據結構保證了在內存中查找的時間的復雜度為O(1)，整體上memcached的高性能這兩個哈希結構起了很大的作用，當然還有memcached的多路復用I/O模型也在高并發下起到了很大的作用。另外memcached的內部操作還具有CAS原子操作，這種利用CPU指令集的操作來保證在單個節點下數據的一致性，效率相對來說比加鎖要高很多。
===========PART 3==============
LRU：是Least Recently Used 近期最少使用算法。 Memcached的LRU幾種策略 1. 惰性刪除。memcached一般不會主動去清除已經過期或者失效的緩存，當get請求一個item的時候，才會去檢查item是否失效。 2. flush命令。flush命令會將所有的item設置為失效。 3. 創建的時候檢查。Memcached會在創建ITEM的時候去LRU的鏈表尾部開始檢查，是否有失效的ITEM，如果沒有的話就重新創建。 4. LRU爬蟲。memcached默認是關閉LRU爬蟲的。LRU爬蟲是一個單獨的線程，會去清理失效的ITEM。
==============PART 4==================
LRU緩存實現(java)
LRU Cache的LinkedHashMap實現LRU Cache的鏈表+HashMap實現LinkedHashMap的FIFO實現調用示例LRU是Least Recently Used 的縮寫，翻譯過來就是“最近最少使用”，LRU緩存就是使用這種原理實現，簡單的說就是緩存一定量的數據，當超過設定的閾值時就把一些過期的數據刪除掉，比如我們緩存10000條數據，當數據小于10000時可以隨意添加，當超過10000時就需要把新的數據添加進來，同時要把過期數據刪除，以確保我們最大緩存10000條，那怎么確定刪除哪條過期數據呢，采用LRU算法實現的話就是將最老的數據刪掉，廢話不多說，下面來說下Java版的LRU緩存實現
Java里面實現LRU緩存通常有兩種選擇，一種是使用LinkedHashMap，一種是自己設計數據結構，使用鏈表+HashMap
LRU Cache的LinkedHashMap實現
LinkedHashMap自身已經實現了順序存儲，默認情況下是按照元素的添加順序存儲，也可以啟用按照訪問順序存儲，即最近讀取的數據放在最前面，最早讀取的數據放在最后面，然后它還有一個判斷是否刪除最老數據的方法，默認是返回false，即不刪除數據，我們使用LinkedHashMap實現LRU緩存的方法就是對LinkedHashMap實現簡單的擴展，擴展方式有兩種，一種是inheritance，一種是delegation，具體使用什么方式看個人喜好
//LinkedHashMap的一個構造函數，當參數accessOrder為true時，即會按照訪問順序排序，最近訪問的放在最前，最早訪問的放在后面
public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認返回false，即不刪除老數據
//我們要做的就是重寫這個方法，當滿足一定條件時刪除老數據
PRotected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
returnfalse;
}
LRU緩存LinkedHashMap(inheritance)實現
采用inheritance方式實現比較簡單，而且實現了Map接口，在多線程環境使用時可以使用 Collections.synchronizedMap()方法實現線程安全操作
package cn.lzrabbit.structure.lru;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by liuzhao on 14-5-15.
*/
public class LRUCache2<K, V>extends LinkedHashMap<K, V> {
privatefinal int MAX_CACHE_SIZE;
public LRUCache2(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f,true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protectedboolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<K, V> entry : entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}
這樣算是比較標準的實現吧，實際使用中這樣寫還是有些繁瑣，更實用的方法時像下面這樣寫，省去了單獨見一個類的麻煩
final int cacheSize = 100;
Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f,true) {
@Override
protectedboolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > cacheSize;
}
};
LRU緩存LinkedHashMap(delegation)實現
delegation方式實現更加優雅一些，但是由于沒有實現Map接口，所以線程同步就需要自己搞定了
package cn.lzrabbit.structure.lru;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
/**
* Created by liuzhao on 14-5-13.
*/
public class LRUCache3<K, V> {
privatefinal int MAX_CACHE_SIZE;
privatefinal float DEFAULT_LOAD_FACTOR = 0.75f;
LinkedHashMap<K, V> map;
public LRUCache3(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
//根據cacheSize和加載因子計算hashmap的capactiy，+1確保當達到cacheSize上限時不會觸發hashmap的擴容，
int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR,true) {
@Override
protectedboolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
};
}
publicsynchronized void put(K key, V value) {
map.put(key, value);
}
publicsynchronized V get(K key) {
return map.get(key);
}
publicsynchronized void remove(K key) {
map.remove(key);
}
publicsynchronized Set<Map.Entry<K, V>> getAll() {
return map.entrySet();
}
publicsynchronized int size() {
return map.size();
}
publicsynchronized void clear() {
map.clear();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry entry : map.entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}
LRU Cache的鏈表+HashMap實現
注：此實現為非線程安全，若在多線程環境下使用需要在相關方法上添加synchronized以實現線程安全操作
package cn.lzrabbit.structure.lru;
import java.util.HashMap;
/**
* Created by liuzhao on 14-5-12.
*/
public class LRUCache1<K, V> {
privatefinal int MAX_CACHE_SIZE;
private Entry first;
private Entry last;
private HashMap<K, Entry<K, V>> hashMap;
public LRUCache1(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
hashMap = new HashMap<K, Entry<K, V>>();
}
publicvoid put(K key, V value) {
Entry entry = getEntry(key);
if (entry ==null) {
if (hashMap.size() >= MAX_CACHE_SIZE) {
hashMap.remove(last.key);
removeLast();
}
entry = new Entry();
entry.key = key;
}
entry.value = value;
moveToFirst(entry);
hashMap.put(key, entry);
}
public V get(K key) {
Entry<K, V> entry = getEntry(key);
if (entry ==null) returnnull;
moveToFirst(entry);
return entry.value;
}
publicvoid remove(K key) {
Entry entry = getEntry(key);
if (entry !=null) {
if (entry.pre !=null) entry.pre.next = entry.next;
if (entry.next !=null) entry.next.pre = entry.pre;
if (entry == first) first = entry.next;
if (entry == last) last = entry.pre;
}
hashMap.remove(key);
}
privatevoid moveToFirst(Entry entry) {
if (entry == first)return;
if (entry.pre !=null) entry.pre.next = entry.next;
if (entry.next !=null) entry.next.pre = entry.pre;
if (entry == last) last = last.pre;
if (first ==null || last == null) {
first = last = entry;
return;
}
entry.next = first;
first.pre = entry;
first = entry;
entry.pre = null;
}
privatevoid removeLast() {
if (last !=null) {
last = last.pre;
if (last ==null) first = null;
else last.next =null;
}
}
private Entry<K, V> getEntry(K key) {
return hashMap.get(key);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Entry entry = first;
while (entry !=null) {
sb.append(String.format("%s:%s ", entry.key, entry.value));
entry = entry.next;
}
return sb.toString();
}
class Entry<K, V> {
public Entry pre;
public Entry next;
public K key;
public V value;
}
}
LinkedHashMap的FIFO實現
FIFO是First Input First Output的縮寫，也就是常說的先入先出，默認情況下LinkedHashMap就是按照添加順序保存，我們只需重寫下removeEldestEntry方法即可輕松實現一個FIFO緩存，簡化版的實現代碼如下
final int cacheSize = 5;
LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {
@Override
protectedboolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
return size() > cacheSize;
}
};
調用示例
測試代碼
package cn.lzrabbit.structure.lru;
import cn.lzrabbit.ITest;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by liuzhao on 14-5-15.
*/
public class LRUCacheTest {
publicstatic void main(String[] args)throws Exception {
System.out.println("start...");
lruCache1();
lruCache2();
lruCache3();
lruCache4();
System.out.println("over...");
}
static void lruCache1() {
System.out.println();
System.out.println("===========================LRU 鏈表實現===========================");
LRUCache1<Integer, String> lru = new LRUCache1(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
static <T> void lruCache2() {
System.out.println();
System.out.println("===========================LRU LinkedHashMap(inheritance)實現===========================");
LRUCache2<Integer, String> lru = new LRUCache2(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
static void lruCache3() {
System.out.println();
System.out.println("===========================LRU LinkedHashMap(delegation)實現===========================");
LRUCache3<Integer, String> lru = new LRUCache3(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
static void lruCache4() {
System.out.println();
System.out.println("===========================FIFO LinkedHashMap默認實現===========================");
finalint cacheSize = 5;
LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {
@Override
protectedboolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
return size() > cacheSize;
}
};
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
System.out.println(lru.toString());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
System.out.println(lru.toString());
System.out.println();
}
}
運行結果
"C:/Program Files (x86)/Java/jdk1.6.0_10/bin/java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:/Program Files (x86)/JetBrains/IntelliJ IDEA 13.0.2/bin" -Dfile.encoding=UTF-8 -classpath "C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/charsets.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/deploy.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/javaws.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/jce.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/jsse.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/management-agent.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/plugin.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/resources.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/rt.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/ext/dnsns.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/ext/localedata.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/ext/sunjce_provider.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar;D:/SVN/projects/Java/Java.Algorithm/target/test-classes;D:/SVN/projects/Java/Java.Algorithm/target/classes;C:/Program Files (x86)/JetBrains/IntelliJ IDEA 13.0.2/lib/idea_rt.jar" com.intellij.rt.execution.application.AppMain Main
start...
===========================LRU 鏈表實現===========================
5:11 4:11 3:11 2:11 1:11
4:11 7:77 2:11 6:66 5:11
===========================LRU LinkedHashMap(inheritance)實現===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
===========================LRU LinkedHashMap(delegation)實現===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
===========================FIFO LinkedHashMap默認實現===========================
{1=11, 2=11, 3=11, 4=11, 5=11}
{3=11, 4=11, 5=11, 6=66, 7=77}
over...
Process finished with exit code 0
新聞熱點
疑難解答
