--- 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] ```