关于redis:有趣的Redis缓存被我写满了该怎么办

Redis 是一个内存数据库，当 Redis 应用的内存超过物理内存的限度后，内存数据会和磁盘产生频繁的替换，替换会导致 Redis 性能急剧下降。所以在生产环境中咱们通过配置参数 maxmemoey 来限度应用的内存大小。

当理论应用的内存超过 maxmemoey 后，Redis 提供了如下几种可选策略。

noeviction：写申请返回谬误

volatile-lru：应用 lru 算法删除设置了过期工夫的键值对
volatile-lfu：应用 lfu 算法删除设置了过期工夫的键值对
volatile-random：在设置了过期工夫的键值对中随机进行删除
volatile-ttl：依据过期工夫的先后进行删除，越早过期的越先被删除

allkeys-lru：在所有键值对中，应用 lru 算法进行删除
allkeys-lfu：在所有键值对中，应用 lfu 算法进行删除
allkeys-random：所有键值对中随机删除

咱们来具体理解一下 lru 和 lfu 算法，这是 2 个常见的缓存淘汰算法。因为计算机缓存的容量是无限的，所以咱们要删除那些没用的数据，而这两种算法的区别就是断定没用的纬度不一样。

LRU算法

lru（Least recently used，最近起码应用）算法，即最近拜访的数据，后续很大概率还会被拜访到，即是有用的。而长时间未被拜访的数据，应该被淘汰

lru 算法中数据会被放到一个链表中，链表的头节点为最近被拜访的数据，链表的尾节点为长时间没有被拜访的数据

lru算法的外围实现就是哈希表加双向链表 。链表能够用来保护拜访元素的程序，而 hash 表能够帮咱们在 O(1) 工夫复杂度下拜访到元素。

至于为什么是双向链表呢？次要是要删除元素，所以要获取前继节点。数据结构图示如下

应用双向链表 +HashMap

双向链表节点定义如下

public class ListNode<K, V> {

K key;

V value;

ListNode pre;

ListNode next;

public ListNode() {}

public ListNode(K key, V value) {

this.key = key;

this.value = value;

}

封装双向链表的罕用操作

public class DoubleList {

private ListNode head;

private ListNode tail;

public DoubleList() {

head = new ListNode();

tail = new ListNode();

head.next = tail;

tail.pre = head;

}

public void remove(ListNode node) {

node.pre.next = node.next;

node.next.pre = node.pre;

}

public void addLast(ListNode node) {

node.pre = tail.pre;

tail.pre = node;

node.pre.next = node;

node.next = tail;

}

public ListNode removeFirst() {

if (head.next == tail) {

return null;

}

ListNode first = head.next;

remove(first);

return first;

}

封装一个缓存类，提供最根本的 get 和 put 办法。须要留神，这两种根本的办法都波及到对两种数据结构的批改。

public class MyLruCache<K, V> {

private int capacity;

private DoubleList doubleList;

private Map<K, ListNode> map;

public MyLruCache(int capacity) {

this.capacity = capacity;

map = new HashMap<>();

doubleList = new DoubleList();

}

public V get(Object key) {

ListNode<K, V> node = map.get(key);

if (node == null) {

return null;

}

// 先删除该节点，再接到尾部

doubleList.remove(node);

doubleList.addLast(node);

return node.value;

}

public void put(K key, V value) {

// 间接调用这边的 get 办法，如果存在，它会在 get 外部被挪动到尾巴，不必再挪动一遍, 间接批改值即可

if ((get(key)) != null) {

map.get(key).value = value;

return;

}

// 如果超出容量，把头去掉

if (map.size() == capacity) {

ListNode listNode = doubleList.removeFirst();

map.remove(listNode.key);

}

// 若不存在，new 一个进去

ListNode node = new ListNode(key, value);

map.put(key, node);

doubleList.addLast(node);

}

这里咱们的实现为最近拜访的放在链表的尾节点，不常常拜访的放在链表的头节点

测试一波，输入为链表的正序输入（代码为了简洁没有贴 toString 办法）

MyLruCache<String, String> myLruCache = new MyLruCache<>(3);

// {5 : 5}

myLruCache.put(“5”, “5”);

// {5 : 5}{3 : 3}

myLruCache.put(“3”, “3”);

// {5 : 5}{3 : 3}{4 : 4}

myLruCache.put(“4”, “4”);

// {3 : 3}{4 : 4}{2 : 2}

myLruCache.put(“2”, “2”);

// {4 : 4}{2 : 2}{3 : 3}

myLruCache.get(“3”);

因为 LinkedHashMap 的底层实现就是哈希表加双向链表，所以你能够用 LinkedHashMap 替换 HashMap 和 DoubleList 来改写一下下面的类。

我来演示一下更骚的操作，只须要重写一个流量交易构造函数和 removeEldestEntry 办法即可。

应用 LinkedHashMap 实现 LRU

public class LruCache<K, V> extends LinkedHashMap<K, V> {

private int cacheSize;

public LruCache(int cacheSize) {

/**

initialCapacity: 初始容量大小
loadFactor: 负载因子
accessOrder: false 基于插入排序（默认），true 基于拜访排序

super(cacheSize, 0.75f, true);

this.cacheSize = cacheSize;

}

/**

当调用 put 或者 putAll 办法时会调用如下办法，是否删除最老的数据，默认为 false

@Override

protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {

return size() > cacheSize;

}

留神这个缓存并不是线程平安的，能够调用 Collections.synchronizedMap 办法返回线程平安的 map

LruCache<String, String> lruCache = new LruCache(3);

Map<String, String> safeMap = Collections.synchronizedMap(lruCache);

Collections.synchronizedMap 实现线程平安的形式很简略，只是返回一个代理类。代理类对 Map 接口的所有办法加锁

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {

return new SynchronizedMap<>(m);

}

LFU算法

LRU 算法有一个问题，当一个长时间不被拜访的 key，偶然被拜访一下后，可能会造成一个比这个 key 拜访更频繁的 key 被淘汰。

即 LRU 算法对 key 的冷热水平的判断可能不精确。而 LFU 算法（Least Frequently Used，最不常常应用）则是依照拜访频率来判断 key 的冷热水平的，每次删除的是一段时间内拜访频率较低的数据，比 LRU 算法更精确。

应用 3 个 hash 表实现 lfu 算法

那么咱们应该如何组织数据呢？

为了实现键值的对快速访问，用一个 map 来保留键值对

private HashMap<K, Integer> keyToVal;

还须要用一个 map 来保留键的拜访频率

private HashMap<K, Integer> keyToFreq;

当然你也能够把值和拜访频率封装到一个类中，用一个 map 来代替上述的 2 个map

接下来就是最外围的局部，删除拜访频率最低的数据。

为了能在 O(1)工夫复杂度内找到拜访频率最低的数据，咱们须要一个变量 minFreq 记录拜访最低的频率
每个拜访频率有可能对应多个键。当空间不够用时，咱们要删除最早被拜访的数据，所以须要如下数据结构，Map< 频率, 有序汇合 >。每次内存不够用时，删除有序汇合的第一个元素即可。并且这个有序汇合要能疾速删除某个 key，因为某个 key 被拜访后，须要从这个汇合中删除，退出 freq+ 1 对应的汇合中
有序汇合很多，然而能满足疾速删除某个 key 的只有 set，然而 set 插入数据是无序的。幸好 Java 有LinkedHashSet这个类，链表和汇合的结合体，链表不能疾速删除元素，然而能保障插入程序。汇合外部元素无序，然而能疾速删除元素，完满

上面就是具体的实现。

public class LfuCache<K, V> {

private HashMap<K, V> keyToVal;

private HashMap<K, Integer> keyToFreq;

private HashMap<Integer, LinkedHashSet<K>> freqTokeys;

private int minFreq;

private int capacity;

public LfuCache(int capacity) {

keyToVal = new HashMap<>();

keyToFreq = new HashMap<>();

freqTokeys = new HashMap<>();

this.capacity = capacity;

this.minFreq = 0;

}

public V get(K key) {

V v = keyToVal.get(key);

if (v == null) {

return null;

}

increaseFrey(key);

return v;

}

public void put(K key, V value) {

// get 办法外面会减少频次

if (get(key) != null) {

// 从新设置值

keyToVal.put(key, value);

return;

}

// 超出容量，删除频率最低的 key

if (keyToVal.size() >= capacity) {

removeMinFreqKey();

}

keyToVal.put(key, value);

keyToFreq.put(key, 1);

// key 对应的 value 存在，返回存在的 key

// key 对应的 value 不存在，增加 key 和 value

freqTokeys.putIfAbsent(1, new LinkedHashSet<>());

freqTokeys.get(1).add(key);

this.minFreq = 1;

}

// 删除呈现频率最低的 key

private void removeMinFreqKey() {

LinkedHashSet<K> keyList = freqTokeys.get(minFreq);

K deleteKey = keyList.iterator().next();

keyList.remove(deleteKey);

if (keyList.isEmpty()) {

// 这里删除元素后不须要从新设置 minFreq

// 因为 put 办法执行完会将 minFreq 设置为 1

freqTokeys.remove(keyList);

}

keyToVal.remove(deleteKey);

keyToFreq.remove(deleteKey);

}

// 减少频率

private void increaseFrey(K key) {

int freq = keyToFreq.get(key);

keyToFreq.put(key, freq + 1);

freqTokeys.get(freq).remove(key);

freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());

freqTokeys.get(freq + 1).add(key);

if (freqTokeys.get(freq).isEmpty()) {

freqTokeys.remove(freq);

// 最小频率的 set 为空，key 被挪动到 minFreq+ 1 对应的 set 了

// 所以 minFreq 也要加 1

if (freq == this.minFreq) {

this.minFreq++;

}

测试一下

LfuCache<String, String> lfuCache = new LfuCache(2);

lfuCache.put(“1”, “1”);

lfuCache.put(“2”, “2”);

// 1

System.out.println(lfuCache.get(“1”));

lfuCache.put(“3”, “3”);

// 1 的频率为 2，2 和 3 的频率为 1，但 2 更早之前被拜访，所以被革除

// 后果为 null

System.out.println(lfuCache.get(“2”));

关于redis:有趣的Redis缓存被我写满了该怎么办

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）