lru算法和redis的lru
lru算法和redis的lru
lru算法和redis的lru
LRU
使用linkedHashMap实现LRU
package com.earthchen.lru.linkedhashmap;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* lru缓存算法
* <p>
* LinkedHashMap
*
* @author earthchen
* @date 2018/9/20
**/
public class LRUCache<K, V> {
private static final float HASH_LOAD_FACTORY = 0.75f;
private LinkedHashMap<K, V> map;
private int cacheSize;
public LRUCache(int cacheSize) {
this.cacheSize = cacheSize;
int capacity = (int) Math.ceil(cacheSize / HASH_LOAD_FACTORY) + 1;
map = new LinkedHashMap<K, V>(capacity, HASH_LOAD_FACTORY, true) {
/**
* 重写删除最老的元素
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > LRUCache.this.cacheSize;
}
};
}
/**
* 根据key获取value
*
* @param key
* @return
*/
public synchronized V get(K key) {
return map.get(key);
}
/**
* 添加
*
* @param key
* @param value
*/
public synchronized void put(K key, V value) {
map.put(key, value);
}
/**
* 清除
*/
public synchronized void clear() {
map.clear();
}
/**
* 已经使用的大小
*
* @return
*/
public synchronized int usedSize() {
return map.size();
}
/**
* 打印
*/
public void print() {
for (Map.Entry<K, V> entry : map.entrySet()) {
System.out.print(entry.getValue() + "--");
}
System.out.println();
}
}LRU-K
原理
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
实现
相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
其他算法在此省略。。最常用的是LRU-2
Redis的lru实现
回收策略
- volatile-lru -> 根据LRU算法删除设置了超时属性（expire）的键，直到腾出足够空间为止。如果没有可删除的键对象，回退到noeviction策略。
- allkeys-lru -> 根据LRU算法删除键，不管数据有没有设置超时属性，直到腾出足够空间为止。
- volatile-lfu -> 根据LFU算法删除设置了超时属性（expire）的键，直到腾出足够空间为止。如果没有可删除的键对象，回退到noeviction策略。
- allkeys-lfu -> 根据LFU算法删除键，不管数据有没有设置超时属性，直到腾出足够空间为止。
- volatile-random -> 随机删除过期键，直到腾出足够空间为止。 allkeys-random -> 随机删除所有键，直到腾出足够空间为止。 volatile-ttl -> 根据键值对象的ttl属性，删除最近将要过期数据。如果没有，回退到noeviction策略。 *noeviction -> 不会删除任何数据，拒绝所有写入操作并返 回客户端错误信息，此 时Redis只响应读操作。
lfu是redis 4.0之后才有的
回收过程
- 一个客户端运行一个新命令，添加了新数据。 Redis 检查内存使用情况，如果大于 maxmemory 限制，根据策略来回收键。
- 一个新的命令被执行，如此等等。
- 通过检查，然后回收键以返回到限制以下，来连续不断的穿越内存限制的边界。
如果一个命令导致大量的内存被占用
(像一个很大的集合交集保存到一个新的键)，一会功夫内存限制就会被这个明显的内存量所超越。
近似的 LRU 算法
Redis 的 LRU 算法不是一个精确的实现。这意味着 Redis 不能选择最佳候选键来回收，也就是最久钱被访问的那些键。相反，会尝试运营一个近似的 LRU 算法，通过采样一小部分键，然后在采样键中回收最适合(拥有最久访问时间)的那个。
Redis 的 LRU 算法有一点很重要，你可以调整算法的精度，通过改变每次回收时检查的采样数量。这个参数可以通过如下配置指令
maxmemory-samples 5Redis 没有使用真实的 LRU 实现的原因，是因为这会消耗更多的内存。然而，近似值对使用 Redis 的应用来说基本上也是等价的。为 Redis 使用的 LRU 近似值和真实 LRU 之间的比较。
Redis 服务被填充了指定数量的键。键被从头访问到尾，所以第一个键是 LRU 算法的最佳候选回收键。然后，再新添加 50% 的键，强制一般的旧键被回收。
在理论的 LRU 实现中，我们期待看到的是，在旧键中第一半会过期。而 Redis 的 LRU 算法则只是概率性的过期这些旧键。
你可以看到，同样采用 5 个采样，Redis 3.0 表现得比 Redis 2.8 要好，Redis 2.8 中最近被访问的对象之间的对象仍然被保留。在 Redis 3.0 中使用 10 为采样大小，近似值已经非常接近理论性能。
注意，LRU 只是一个预言指定键在未来如何被访问的模式。另外，如果你的数据访问模式非常接近幂律，大多数的访问都将集中在一个集合中，LRU 近似算法将能处理得很好。
在模拟实验的过程中，我们发现使用幂律访问模式，真实的 LRU 算法和 Redis 的近似算法之间的差异非常小，或者根本就没有。
然而，你可以提高采样大小到 10，这会消耗额外的 CPU，来更加近似于真实的 LRU 算法，看看这会不会使你的缓存错失率有差异。
使用 CONFIG SET maxmemory-samples 命令在生产环境上试验各种不同的采样大小值是很简单的。