Redis的常用淘汰策略以及算法實現(xiàn)
點擊上方藍色字體，選擇“標星公眾號”
優(yōu)質(zhì)文章，第一時間送達
作者 | MXC肖某某
來源 | urlify.cn/UFZjyu
一、Redis的內(nèi)存配置
1，Redis配置內(nèi)存為多少合適？
默認：如果不設置最大內(nèi)存大小或者設置最大內(nèi)存大小為0，在64為操作系統(tǒng)下不限制內(nèi)存大小，在32位操作系統(tǒng)下最多使用3GB內(nèi)存。
極限情況：留出一倍內(nèi)存。比如你的redis數(shù)據(jù)占用了8G內(nèi)存，那么你還需要再預留8G空閑內(nèi)存。也就是內(nèi)存需求是16G。內(nèi)存占用率低于50%是最安全的。
普通情況：正常情況下，在序列化周期內(nèi)，不會更改所有數(shù)據(jù)，只會有部分數(shù)據(jù)更改，那么，預留出可能產(chǎn)生的更改部分的空間，就行。如果實在要說一個數(shù)據(jù)的話，一般推薦Redis設置內(nèi)存為最大物理內(nèi)存的75%都是安全的。
2，如何修改內(nèi)存
a）配置文件修改
redis.conf中
#設置為100M，單位是byte
maxmemory 104857600b）命令行修改
config set maxmemory 104857600
3，查看最大內(nèi)存
config get maxmemory
#或者使用
info memory
4，如果Redis的內(nèi)存你打滿了會怎么樣?
二、Redis的內(nèi)存淘汰策略
1，Redis 過期策略是：定期刪除+惰性刪除。
所謂定期刪除，指的是 Redis 默認是每隔 100ms 就隨機抽取一些設置了過期時間的 key，檢查其是否過期，如果過期就刪除。
假設 Redis 里放了 10w 個 key，都設置了過期時間，你每隔幾百毫秒，就檢查 10w 個 key，那 Redis 基本上就死了，cpu 負載會很高的，消耗在你的檢查過期 key 上了。注意，這里可不是每隔 100ms 就遍歷所有的設置過期時間的 key，那樣就是一場性能上的災難。實際上 Redis 是每隔 100ms 隨機抽取一些 key 來檢查和刪除的。
惰性刪除：數(shù)據(jù)到達過期時間，不做處理。等下次訪問該數(shù)據(jù)時，如果未過期，返回數(shù)據(jù)；發(fā)現(xiàn)已過期，刪除，返回不存在。
但是實際上這還是有問題的，如果定期刪除漏掉了很多過期 key，然后你也沒及時去查，也就沒走惰性刪除，此時會怎么樣？如果大量過期 key 堆積在內(nèi)存里，導致 Redis 內(nèi)存塊耗盡了，咋整？實際上會走：內(nèi)存淘汰機制。
2，內(nèi)存淘汰機制
Redis內(nèi)存淘汰機制有以下幾個：
noeviction: 當內(nèi)存不足以容納新寫入數(shù)據(jù)時，新寫入操作會報錯，這個一般沒人用吧，實在是太惡心了。
allkeys-lru：當內(nèi)存不足以容納新寫入數(shù)據(jù)時，在鍵空間中，移除最近最少使用的 key（這個是最常用的）。
allkeys-random：當內(nèi)存不足以容納新寫入數(shù)據(jù)時，在鍵空間中，隨機移除某個 key，這個一般沒人用吧，為啥要隨機，肯定是把最近最少使用的 key 給干掉啊。
volatile-lru：當內(nèi)存不足以容納新寫入數(shù)據(jù)時，在設置了過期時間的鍵空間中，移除最近最少使用的 key（這個一般不太合適）。
volatile-random：當內(nèi)存不足以容納新寫入數(shù)據(jù)時，在設置了過期時間的鍵空間中，隨機移除某個 key。
volatile-ttl：當內(nèi)存不足以容納新寫入數(shù)據(jù)時，在設置了過期時間的鍵空間中，有更早過期時間的 key 優(yōu)先移除。
allkeys-lfu: 對所有key使用LFU算法進行刪除。LFU:最不經(jīng)常使用，如果一個數(shù)據(jù)在最近一段時間內(nèi)使用次數(shù)很少，那么在將來一段時間內(nèi)被使用的可能性也很小。
volatile-lfu: 對所有設置了過期時間的key使用LFU算法進行刪除。
三、手寫LRU算法
1，采用LinkedHashMap實現(xiàn)
public class Demo015_LRUCacheLinkedHashMap {
private int capacity;
private LinkedHashMap<Integer, Integer> linkedHashMap;
public Demo015_LRUCacheLinkedHashMap(int capacity) {
this.capacity = capacity;
/**
* 三個參數(shù):capacity為容量，0.75位擴容因子，true為按照訪問排序false為按照插入排序
* 重寫刪除尾結(jié)點的方法，一旦發(fā)現(xiàn)當前l(fā)inkhashmap的長度大于總?cè)萘烤托枰獎h除*/
linkedHashMap = new LinkedHashMap<Integer, Integer>(capacity,0.75F,true){
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return super.size() > capacity;
}
};
}
public void put(int key, int value) {
linkedHashMap.put(key, value);
}
public int get(int key) {
Integer value = linkedHashMap.getOrDefault(key,-1);
return value;
}
}
2，自定義雙向鏈表
定義Node節(jié)點：key,val,next和prev
定義DoubleLinkedNode管理Node結(jié)點組成頭尾結(jié)點的雙向鏈表
定義hashmap存儲每個結(jié)點
插入時判斷當前值是否已經(jīng)存在hashmap中
如果存在就更改當前值，刪除雙向鏈表中原來的這個值，添加新值到鏈表頭結(jié)點并修改hashmap中當前值
如果不存在當前值，判斷當前容器是否滿了，如果滿了就刪除鏈表尾部刪除hashmap中數(shù)據(jù)。并添加新結(jié)點到鏈表頭部和hashmap中
獲取時，直接從hashmap中獲取。如果不存在直接返回-1，如果存在就刪除鏈表尾部數(shù)據(jù)，更新鏈表頭部數(shù)據(jù)為當前node
public class Demo015_LRUCache {
class Node<K, V> {
K key;
V val;
Node next;
Node prev;
public Node(){
next = prev = null;
}
public Node(K key, V val) {
this.key = key;
this.val = val;
next = prev = null;
}
}
class DoubleLinkedNode<K,V>{
Node head;
Node tail;
public DoubleLinkedNode() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public void addHead(Node<K,V> node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public void remove(Node<K,V> node) {
if (node.prev == null || node.next==null) {
return;
}
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}
public Node<K,V> getLast() {
if (tail.prev == head) {
return null;
}
return tail.prev;
}
}
private int capacity;
private HashMap<Integer, Node<Integer,Integer>> hashMap;
private DoubleLinkedNode<Integer, Integer> doubleLinkedNode;
public Demo015_LRUCache(int capacity) {
this.capacity = capacity;
hashMap = new HashMap<>();
doubleLinkedNode = new DoubleLinkedNode<>();
}
public int get(int key) {
Node<Integer,Integer> node = hashMap.get(key);
if (node == null) {
return -1;
}
doubleLinkedNode.remove(node);
doubleLinkedNode.addHead(node);
return node.val;
}
public void put(int key, int value) {
Node<Integer, Integer> node = hashMap.get(key);
if (node == null) { //沒有添加過
if (hashMap.size() == capacity) { //達到最大值狀態(tài)
//刪除最后結(jié)點
Node<Integer, Integer> last = doubleLinkedNode.getLast();
doubleLinkedNode.remove(last);
hashMap.remove(last.key);
}
//添加頭結(jié)點
node = new Node<>(key, value);
hashMap.put(key,node);
doubleLinkedNode.addHead(node);
}else {
//如果添加過,刪除雙向鏈表的該節(jié)點,將其修改值之后添加到頭節(jié)點
doubleLinkedNode.remove(node);
node.val = value;
doubleLinkedNode.addHead(node);
hashMap.put(key, node);
}
}
}
粉絲福利：Java從入門到入土學習路線圖
??????
??長按上方微信二維碼 2 秒
感謝點贊支持下哈 