Poison

ConcurrentLruCache

今天看到 Spring 中的 ConcurrentLruCache 实现,本文简要记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
* Simple LRU (Least Recently Used) cache, bounded by a specified cache limit.
*
* <p>This implementation is backed by a {@code ConcurrentHashMap} for storing
* the cached values and a {@code ConcurrentLinkedDeque} for ordering the keys
* and choosing the least recently used key when the cache is at full capacity.
*
* @author Brian Clozel
* @author Juergen Hoeller
* @since 5.3
* @param <K> the type of the key used for cache retrieval
* @param <V> the type of the cached values
* @see #get
*/
public class ConcurrentLruCache<K, V> {

private final int sizeLimit;

private final Function<K, V> generator;

private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();

// 当前实现为队列尾部为最近访问的节点
private final ConcurrentLinkedDeque<K> queue = new ConcurrentLinkedDeque<>();

private final ReadWriteLock lock = new ReentrantReadWriteLock();

// 对 size 的读取并不都被锁保护,所以使用了 volatile 修饰保证可见性
private volatile int size;


/**
* Create a new cache instance with the given limit and generator function.
* @param sizeLimit the maximum number of entries in the cache
* (0 indicates no caching, always generating a new value)
* @param generator a function to generate a new value for a given key
*/
public ConcurrentLruCache(int sizeLimit, Function<K, V> generator) {
Assert.isTrue(sizeLimit >= 0, "Cache size limit must not be negative");
Assert.notNull(generator, "Generator function must not be null");
this.sizeLimit = sizeLimit;
this.generator = generator;
}


/**
* Retrieve an entry from the cache, potentially triggering generation
* of the value.
* @param key the key to retrieve the entry for
* @return the cached or newly generated value
*/
public V get(K key) {
// 如果设置的 sizeLimit 为 0,说明不启用缓存,直接每次调用 generator 的 apply 函数生成值并返回
if (this.sizeLimit == 0) {
return this.generator.apply(key);
}

V cached = this.cache.get(key);
if (cached != null) { // 如果存在 key 对应的缓存
if (this.size < this.sizeLimit) { // 如果当前缓存区中缓存项个数不足 sizeLimit, 说明无需移动 queue 中的节点,直接返回即可
return cached;
}
this.lock.readLock().lock(); // 执行到此处说明缓存区中元素个数已经大于等于 sizeLimit, 那么此时需要移动 queue 中的节点
try {
if (this.queue.removeLastOccurrence(key)) { // 从队列尾部向前找当前访问的 key 并移除
this.queue.offer(key); // 将当前访问的 key 加入至队列尾部,注意此操作在读锁中实现,即存在并发调用,所以 queue 采用了线程安全的实现:ConcurrentLinkedDeque
}
return cached;
}
finally {
this.lock.readLock().unlock();
}
}

this.lock.writeLock().lock(); // 执行到此处说明缓存区中不存在 key 对应的缓存
try {
// 进入了写锁的临界区,此处进行双重检查,避免多个线程并发调用 get 然后串行进入该临界区导致重复创建了缓存
// Retrying in case of concurrent reads on the same key
cached = this.cache.get(key);
if (cached != null) {
if (this.queue.removeLastOccurrence(key)) {
this.queue.offer(key);
}
return cached;
}
// 执行到此处,即将调用 generator 的 apply 函数生成缓存
// Generate value first, to prevent size inconsistency
V value = this.generator.apply(key);
if (this.size == this.sizeLimit) { // 如果缓存区中的缓存项个数已经达到预设的个数限制,则移除队列头部元素
K leastUsed = this.queue.poll();
if (leastUsed != null) {
this.cache.remove(leastUsed);
}
}
this.queue.offer(key); // 添加至队列尾部,即最近的元素在队尾
this.cache.put(key, value);
this.size = this.cache.size();
return value;
}
finally {
this.lock.writeLock().unlock();
}
}

}

最为核心的方法即为 get 方法,其实现思路在上方增加了注释。关键点在于读锁那部分代码是允许多线程执行的,而我们又需要维护 queue 中节点的顺序,所以选用了线程安全的队列实现:ConcurrentLinkedDeque。唯一不理解的就是对 cache 的修改操作都被写锁保护,在当前实现中 cacheConcurrentHashMap 实现,是否可以更换为 HashMap 实现呢?

关于该实现,有用户提交 issue 反馈链表中的 O(n) 扫描效率低下,建议替换为 ConcurrentLinkedHashMap,详情可参考:Revisit ConcurrentLruCache implementation · Issue #26320

Reference

spring-framework/ConcurrentLruCache.java at v5.3.14 · spring-projects/spring-framework · GitHub
java - Why does ConcurrentLruCache in Spring still use thread-safe maps and queues instead of ordinary maps and queues even when read-write lock are used? - Stack Overflow