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