LRU算法介绍
LRU过期策略---最近最少使用
概述：LRU 是 Least Recently Used 的缩写，即最近最少使用，是内存管理的一种页面置换算法。算法的核心是：如果一个数据在最近一段时间内没有被访问到，那么它在将来被访问的可能性也很小。换言之，当内存达到极限时，应该把内存中最久没有被访问的数据淘汰掉。
那么，如何表示这个最久呢？Redis 在实现上引入了一个 LRU 时钟来代替 unix 时间戳，每个对象的每次被访问都会记录下当前服务器的 LRU 时钟，然后用服务器的 LRU 时钟减去对象本身的时钟，得到的就是这个对象没有被访问的时间间隔（也称空闲时间），空闲时间最大的就是需要淘汰的对象。
LRU算法实现
LRU算法在java中的实现和应用
https://blog.csdn.net/weixin_34417635/article/details/91477695
LRU算法具体实现(参考leetcode代码)
https://leetcode.cn/problems/lru-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-g-1uo3/
LRU算法在Apache Zeppelin中的应用
zeppelin 在保存note 的时候会采用LRU 算法，对于经常使用Note进行采用LRU算法，具体代码：
private class LRUCache extends LinkedHashMap<String, Note> { private static final long serialVersionUID = 1L; public LRUCache() { super(NoteCache.this.threshold, 0.5f, true /* lru by access mode */); } @Override protected boolean removeEldestEntry(java.util.Map.Entry<String, Note> eldest) { if (size() <= NoteCache.this.threshold) { return false; } final Note eldestNote = eldest.getValue(); final Lock lock = eldestNote.getLock().writeLock(); if (lock.tryLock()) { // avoid eviction in case the note is in use try { return true; } finally { lock.unlock(); } } else { LOGGER.info("Can not evict note {}, because the write lock can not be acquired. {} notes currently loaded.", eldestNote.getId(), size()); cleanupCache(); return false; } } private void cleanupCache() { Iterator<Map.Entry<String, Note>> iterator = this.entrySet().iterator(); int count = 0; // if size >= shrinked_size and have next() try remove while ((this.size() - 1) >= NoteCache.this.threshold && iterator.hasNext()) { Map.Entry<String, Note> noteEntry = iterator.next(); final Note note = noteEntry.getValue(); final Lock lock = note.getLock().writeLock(); if (lock.tryLock()) { // avoid eviction in case the note is in use try { iterator.remove(); // remove LRU element from LinkedHashMap LOGGER.debug("Remove note {} from LRU Cache", note.getId()); ++count; } finally { lock.unlock(); } } } LOGGER.info("The cache cleanup removes {} entries", count); } } }
可以看到其实就是采用java LinkedHashMap来实现的LRU算法
