hadoop.yarn 带时间的LRU 延迟删除
org.apache.hadoop.yarn.util.LRUCache
这是一个在 Hadoop YARN 中被使用的、实现了最近最少使用(LRU)策略的缓存。它主要用于存储那些可以被重新计算或获取,但访问代价较高的数据,通过缓存来提升系统性能。
整体设计与核心组件
LRUCache 的实现非常经典,它通过组合两个辅助类来完成其功能:
LRUCacheHashMap<K, CacheNode<V>>
这是缓存的底层存储结构。它是一个继承自java.util.LinkedHashMap
的类。LinkedHashMap
的构造函数中,accessOrder
参数被设置为true
时,每次访问(get
)一个元素,该元素都会被移动到链表的末尾。当插入新元素导致容量超出限制时,链表头部的元素(也就是最久未被访问的元素)就会被移除。这正是 LRU 策略的核心。
public class LRUCacheHashMap<K, V> extends LinkedHashMap<K, V> {private static final long serialVersionUID = 1L;// Maximum size of the cacheprivate int maxSize;/*** Constructor.** @param maxSize max size of the cache* @param accessOrder true for access-order, false for insertion-order*/public LRUCacheHashMap(int maxSize, boolean accessOrder) {super(maxSize, 0.75f, accessOrder);this.maxSize = maxSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > maxSize;}
}
CacheNode<V>
这是一个简单的包装类,定义在CacheNode.java
中。它的作用是封装缓存的实际值V
,并记录下该值被存入缓存时的时间戳cacheTime
。这个时间戳是实现缓存过期的关键。// ... existing code ... public class CacheNode<V> {private V value;private long cacheTime;public CacheNode(V value) {this.value = value;cacheTime = Time.now();}// ... existing code ... }
LRUCache 提供了两个构造函数:
// ... existing code ...
public LRUCache(int capacity) {this(capacity, -1);
}public LRUCache(int capacity, long expireTimeMs) {cache = new LRUCacheHashMap<>(capacity, true);this.expireTimeMs = expireTimeMs;
}
// ... existing code ...
LRUCache(int capacity)
创建一个有固定容量限制但永不过期的缓存。
LRUCache(int capacity, long expireTimeMs)
创建一个既有容量限制,又有过期时间的缓存。expireTimeMs
是过期时间(毫秒),如果传入一个小于等于0
的值,效果等同于永不过期。
get(K key)
方法
延迟删除,get不影响TTL
// ... existing code ...
public synchronized V get(K key) {CacheNode<V> cacheNode = cache.get(key);if (cacheNode != null) {if (expireTimeMs > 0 && Time.now() > cacheNode.getCacheTime() + expireTimeMs) {cache.remove(key);return null;}}return cacheNode == null ? null : cacheNode.get();
}
// ... existing code ...
线程安全
该方法使用了synchronized
关键字,确保了在多线程环境下对缓存的读操作是原子性的,避免了竞态条件。过期检查
在返回缓存值之前,它会检查是否设置了过期时间 (expireTimeMs > 0
)。如果设置了,它会用当前时间Time.now()
与条目的缓存时间cacheNode.getCacheTime()
加上过期时长进行比较。如果发现条目已过期,它会从缓存中移除该条目并返回null
。LRU 更新
调用cache.get(key)
会触发底层LRUCacheHashMap
的机制,将被访问的这个条目标记为“最近使用过”。
put(K key, V value)
方法
// ... existing code ...
public synchronized V put(K key, V value) {cache.put(key, new CacheNode<>(value));return value;
}
// ... existing code ...public CacheNode(V value){this.value = value;cacheTime = Time.now();}
线程安全
同样使用synchronized
保证了写操作的线程安全。包装与存储
它首先将要存入的value
包装成一个CacheNode
对象,这个过程会记录下当前的时间戳。然后将这个CacheNode
存入底层的LRUCacheHashMap
。LRU 驱逐
如果put
操作导致缓存的大小超过了其容量(capacity
),底层的LRUCacheHashMap
会自动移除最久未被访问的条目。
从 TestLRUCache.java
中我们可以看到 LRUCache 的预期行为:
容量测试
测试代码创建了一个容量为3
的LRUCache
,并依次放入了"1"
,"2"
,"3"
,"4"
四个元素。断言缓存大小为3
,并且键为"1"
的条目已经被驱逐(assertNull(lruCache.get("1"))
)。过期测试
测试代码放入一个元素后,线程休眠超过了过期时间,然后尝试获取该元素,断言缓存中已经没有该元素了(size()
变为0
)。
总结
LRUCache 是一个设计简洁、功能明确且线程安全的 LRU 缓存。它巧妙地利用了 LinkedHashMap
的 accessOrder
特性来实现 LRU 驱逐策略,并通过一个包装类 CacheNode
来额外支持了过期功能。这种实现方式在很多 Java 项目中都很常见,是学习和理解缓存设计的一个优秀范例。