---
title: 内存淘汰算法读写性能原理
date: 2019-10-30 08:42:28
update: 2019-10-30 08:42:28
categories: 缓存
tags: [缓存]
---
### 缓存淘汰算法LRU算法
**简介:精雕细刻缓存淘汰算法LRU算法**
------
- LRU算法是什么?
* Least recently used,最近最少使用get
- 为什么要用LRU算法
* 根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”
- LRU算法原理剖析

### 缓存淘汰算法LFU算法
**简介:缓存淘汰算法LRU算法实战**
------
- LFU算法是什么?
* Least Frequently Used
- 为什么要用LFU算法
* 算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”
- LFU算法原理剖析
* 新加入数据插入到队列尾部(因为引用计数为1)
* 队列中的数据被访问后,引用计数增加,队列重新排序;
* 当需要淘汰数据时,将已经排序的列表最后的数据块删除。

* LFU的缺点
* 复杂度
* 存储成本
* 尾部容易被淘汰
### 来自未来的缓存Caffine介绍
**简介:来自未来的缓存Caffine**
------
- Caffine是什么?
* Caffeine是一个基于Java 8的[高性能](https://github.com/ben-manes/caffeine/wiki/Benchmarks),[接近最佳的](https://github.com/ben-manes/caffeine/wiki/Efficiency)缓存库
- Caffine有什么特色?
- [自动将条目加载](https://github.com/ben-manes/caffeine/wiki/Population)到缓存中,可选择异步[加载](https://github.com/ben-manes/caffeine/wiki/Population)
- 基于[频率和新近度](https://github.com/ben-manes/caffeine/wiki/Efficiency)超过最大值时的[基于大小的驱逐](https://github.com/ben-manes/caffeine/wiki/Eviction#size-based)
- 自上次访问或上次写入以来测量的条目[的基于时间的到期](https://github.com/ben-manes/caffeine/wiki/Eviction#time-based)
- 当第一个条目的陈旧请求发生时,[异步刷新](https://github.com/ben-manes/caffeine/wiki/Refresh)
- 密钥自动包含在[弱引用中](https://github.com/ben-manes/caffeine/wiki/Eviction#reference-based)
- 值自动包含在[弱引用或软引用中](https://github.com/ben-manes/caffeine/wiki/Eviction#reference-based)
- 被驱逐(或以其他方式删除)条目的[通知](https://github.com/ben-manes/caffeine/wiki/Removal)
- [写入传播](https://github.com/ben-manes/caffeine/wiki/Writer)到外部资源
- 累积缓存访问[统计信息](https://github.com/ben-manes/caffeine/wiki/Statistics)
- W-Tiny-LFU实现原理分析
- Count-Min Sketch。基于滑动窗口的时间衰减设计机制,借助于一种简易的reset操作:每次添加一条记录到Sketch的时候,都会给一个计数器上加1,当计数器达到一个尺寸W的时候,把所有记录的Sketch数值都除以2,该reset操作可以起到衰减的作用

### Caffine缓存的使用
```xml
com.github.ben-manes.caffeine
caffeine
2.6.2
```
```java
com.github.benmanes.caffeine.cache.LoadingCache> couponCaffeine = Caffeine.newBuilder()
.expireAfterWrite(10, TimeUnit.MINUTES).refreshAfterWrite(5, TimeUnit.MINUTES)
.build(new com.github.benmanes.caffeine.cache.CacheLoader>() {
@Override
public List load(Integer o) throws Exception {
return loadCoupon(o);
}
});
/***
* 获取有效时间的可用优惠券列表
* // 1、是否存在远程调用 HTTP、RPC Metrics
* // 2、大量内存处理 list.contain() ==>set.contain
* @return
*/
public List getCouponListCaffeine() {
List tCoupons = Lists.newArrayList();
try {
tCoupons = couponCaffeine.get(1);
} catch (Exception e) {
e.printStackTrace();
}
return tCoupons;
}
```
### 内存缓存对比
**简介:内存缓存产品对比**
------
- 内存缓存分类
- 从淘汰算法和并发性分析内存缓存的利弊

性能对比
```
Benchmark Mode Cnt Score Error Units
JMHSpringbootTest.test thrpt 2 92908.760 ops/s
JMHSpringbootTest.testCaffeine thrpt 2 94115.021 ops/s
JMHSpringbootTest.testDB thrpt 2 5527.610 ops/s
JMHSpringbootTest.testMap thrpt 2 95026.750 ops/s
```
### 模拟LRU淘汰算法
```java
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache extends LinkedHashMap {
private int cacheSize;
public LRUCache(int cacheSize) {
super(16, 0.75f, true);
this.cacheSize = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
boolean r = size() > cacheSize;
if (r) {
System.out.println("清除缓存key:" + eldest.getKey());
}
return r;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache<>(5);
cache.put("A", "A");
cache.put("B", "B");
cache.put("C", "C");
cache.put("D", "D");
cache.put("E", "E");
System.out.println("初始化:" + cache.keySet());
System.out.println("访问值:" + cache.get("C"));
System.out.println("访问C后:" + cache.keySet());
System.out.println("访问值:" + cache.put("F", "F"));
System.out.println("put F后:" + cache.keySet());
}
}
```
```
初始化:[A, B, C, D, E]
访问值:C
访问C后:[A, B, D, E, C]
清除缓存key:A
访问值:null
put F后:[B, D, E, C, F]
```
内存淘汰算法读写性能原理