Debian Codegraph @

arc/arc.go

raw
1 // Copyright (c) HashiCorp, Inc.
2 // SPDX-License-Identifier: MPL-2.0
3
4 package arc
5
6 import (
7 "sync"
8
9 "github.com/hashicorp/golang-lru/v2/simplelru"
10 )
11
12 // ARCCache is a thread-safe fixed size Adaptive Replacement Cache (ARC).
13 // ARC is an enhancement over the standard LRU cache in that tracks both
14 // frequency and recency of use. This avoids a burst in access to new
15 // entries from evicting the frequently used older entries. It adds some
16 // additional tracking overhead to a standard LRU cache, computationally
17 // it is roughly 2x the cost, and the extra memory overhead is linear
18 // with the size of the cache. ARC has been patented by IBM, but is
19 // similar to the TwoQueueCache (2Q) which requires setting parameters.
20 type ARCCache[K comparable, V any] struct {
21 size int // Size is the total capacity of the cache
22 p int // P is the dynamic preference towards T1 or T2
23
24 t1 simplelru.LRUCache[K, V] // T1 is the LRU for recently accessed items
25 b1 simplelru.LRUCache[K, struct{}] // B1 is the LRU for evictions from t1
26
27 t2 simplelru.LRUCache[K, V] // T2 is the LRU for frequently accessed items
28 b2 simplelru.LRUCache[K, struct{}] // B2 is the LRU for evictions from t2
29
30 lock sync.RWMutex
31 }
32
33 // NewARC creates an ARC of the given size
34 func NewARC[K comparable, V any](size int) (*ARCCache[K, V], error) {
35 // Create the sub LRUs
36 b1, err := simplelru.NewLRU[K, struct{}](size, nil)
37 if err != nil {
38 return nil, err
39 }
40 b2, err := simplelru.NewLRU[K, struct{}](size, nil)
41 if err != nil {
42 return nil, err
43 }
44 t1, err := simplelru.NewLRU[K, V](size, nil)
45 if err != nil {
46 return nil, err
47 }
48 t2, err := simplelru.NewLRU[K, V](size, nil)
49 if err != nil {
50 return nil, err
51 }
52
53 // Initialize the ARC
54 c := &ARCCache[K, V]{
55 size: size,
56 p: 0,
57 t1: t1,
58 b1: b1,
59 t2: t2,
60 b2: b2,
61 }
62 return c, nil
63 }
64
65 // Get looks up a key's value from the cache.
66 func (c *ARCCache[K, V]) Get(key K) (value V, ok bool) {
67 c.lock.Lock()
68 defer c.lock.Unlock()
69
70 // If the value is contained in T1 (recent), then
71 // promote it to T2 (frequent)
72 if val, ok := c.t1.Peek(key); ok {
73 c.t1.Remove(key)
74 c.t2.Add(key, val)
75 return val, ok
76 }
77
78 // Check if the value is contained in T2 (frequent)
79 if val, ok := c.t2.Get(key); ok {
80 return val, ok
81 }
82
83 // No hit
84 return
85 }
86
87 // Add adds a value to the cache.
88 func (c *ARCCache[K, V]) Add(key K, value V) {
89 c.lock.Lock()
90 defer c.lock.Unlock()
91
92 // Check if the value is contained in T1 (recent), and potentially
93 // promote it to frequent T2
94 if c.t1.Contains(key) {
95 c.t1.Remove(key)
96 c.t2.Add(key, value)
97 return
98 }
99
100 // Check if the value is already in T2 (frequent) and update it
101 if c.t2.Contains(key) {
102 c.t2.Add(key, value)
103 return
104 }
105
106 // Check if this value was recently evicted as part of the
107 // recently used list
108 if c.b1.Contains(key) {
109 // T1 set is too small, increase P appropriately
110 delta := 1
111 b1Len := c.b1.Len()
112 b2Len := c.b2.Len()
113 if b2Len > b1Len {
114 delta = b2Len / b1Len
115 }
116 if c.p+delta >= c.size {
117 c.p = c.size
118 } else {
119 c.p += delta
120 }
121
122 // Potentially need to make room in the cache
123 if c.t1.Len()+c.t2.Len() >= c.size {
124 c.replace(false)
125 }
126
127 // Remove from B1
128 c.b1.Remove(key)
129
130 // Add the key to the frequently used list
131 c.t2.Add(key, value)
132 return
133 }
134
135 // Check if this value was recently evicted as part of the
136 // frequently used list
137 if c.b2.Contains(key) {
138 // T2 set is too small, decrease P appropriately
139 delta := 1
140 b1Len := c.b1.Len()
141 b2Len := c.b2.Len()
142 if b1Len > b2Len {
143 delta = b1Len / b2Len
144 }
145 if delta >= c.p {
146 c.p = 0
147 } else {
148 c.p -= delta
149 }
150
151 // Potentially need to make room in the cache
152 if c.t1.Len()+c.t2.Len() >= c.size {
153 c.replace(true)
154 }
155
156 // Remove from B2
157 c.b2.Remove(key)
158
159 // Add the key to the frequently used list
160 c.t2.Add(key, value)
161 return
162 }
163
164 // Potentially need to make room in the cache
165 if c.t1.Len()+c.t2.Len() >= c.size {
166 c.replace(false)
167 }
168
169 // Keep the size of the ghost buffers trim
170 if c.b1.Len() > c.size-c.p {
171 c.b1.RemoveOldest()
172 }
173 if c.b2.Len() > c.p {
174 c.b2.RemoveOldest()
175 }
176
177 // Add to the recently seen list
178 c.t1.Add(key, value)
179 }
180
181 // replace is used to adaptively evict from either T1 or T2
182 // based on the current learned value of P
183 func (c *ARCCache[K, V]) replace(b2ContainsKey bool) {
184 t1Len := c.t1.Len()
185 if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) {
186 k, _, ok := c.t1.RemoveOldest()
187 if ok {
188 c.b1.Add(k, struct{}{})
189 }
190 } else {
191 k, _, ok := c.t2.RemoveOldest()
192 if ok {
193 c.b2.Add(k, struct{}{})
194 }
195 }
196 }
197
198 // Len returns the number of cached entries
199 func (c *ARCCache[K, V]) Len() int {
200 c.lock.RLock()
201 defer c.lock.RUnlock()
202 return c.t1.Len() + c.t2.Len()
203 }
204
205 // Keys returns all the cached keys
206 func (c *ARCCache[K, V]) Keys() []K {
207 c.lock.RLock()
208 defer c.lock.RUnlock()
209 k1 := c.t1.Keys()
210 k2 := c.t2.Keys()
211 return append(k1, k2...)
212 }
213
214 // Values returns all the cached values
215 func (c *ARCCache[K, V]) Values() []V {
216 c.lock.RLock()
217 defer c.lock.RUnlock()
218 v1 := c.t1.Values()
219 v2 := c.t2.Values()
220 return append(v1, v2...)
221 }
222
223 // Remove is used to purge a key from the cache
224 func (c *ARCCache[K, V]) Remove(key K) {
225 c.lock.Lock()
226 defer c.lock.Unlock()
227 if c.t1.Remove(key) {
228 return
229 }
230 if c.t2.Remove(key) {
231 return
232 }
233 if c.b1.Remove(key) {
234 return
235 }
236 if c.b2.Remove(key) {
237 return
238 }
239 }
240
241 // Purge is used to clear the cache
242 func (c *ARCCache[K, V]) Purge() {
243 c.lock.Lock()
244 defer c.lock.Unlock()
245 c.t1.Purge()
246 c.t2.Purge()
247 c.b1.Purge()
248 c.b2.Purge()
249 }
250
251 // Contains is used to check if the cache contains a key
252 // without updating recency or frequency.
253 func (c *ARCCache[K, V]) Contains(key K) bool {
254 c.lock.RLock()
255 defer c.lock.RUnlock()
256 return c.t1.Contains(key) || c.t2.Contains(key)
257 }
258
259 // Peek is used to inspect the cache value of a key
260 // without updating recency or frequency.
261 func (c *ARCCache[K, V]) Peek(key K) (value V, ok bool) {
262 c.lock.RLock()
263 defer c.lock.RUnlock()
264 if val, ok := c.t1.Peek(key); ok {
265 return val, ok
266 }
267 return c.t2.Peek(key)
268 }