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}
177
178// replace is used to adaptively evict from either T1 or T2
179// based on the current learned value of P
180func (c *ARCCache) replace(b2ContainsKey bool) {
181	t1Len := c.t1.Len()
182	if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) {
183		k, _, ok := c.t1.RemoveOldest()
184		if ok {
185			c.b1.Add(k, nil)
186		}
187	} else {
188		k, _, ok := c.t2.RemoveOldest()
189		if ok {
190			c.b2.Add(k, nil)
191		}
192	}
193}
194
195// Len returns the number of cached entries
196func (c *ARCCache) Len() int {
197	c.lock.RLock()
198	defer c.lock.RUnlock()
199	return c.t1.Len() + c.t2.Len()
200}
201
202// Keys returns all the cached keys
203func (c *ARCCache) Keys() []interface{} {
204	c.lock.RLock()
205	defer c.lock.RUnlock()
206	k1 := c.t1.Keys()
207	k2 := c.t2.Keys()
208	return append(k1, k2...)
209}
210
211// Remove is used to purge a key from the cache
212func (c *ARCCache) Remove(key interface{}) {
213	c.lock.Lock()
214	defer c.lock.Unlock()
215	if c.t1.Remove(key) {
216		return
217	}
218	if c.t2.Remove(key) {
219		return
220	}
221	if c.b1.Remove(key) {
222		return
223	}
224	if c.b2.Remove(key) {
225		return
226	}
227}
228
229// Purge is used to clear the cache
230func (c *ARCCache) Purge() {
231	c.lock.Lock()
232	defer c.lock.Unlock()
233	c.t1.Purge()
234	c.t2.Purge()
235	c.b1.Purge()
236	c.b2.Purge()
237}
238
239// Contains is used to check if the cache contains a key
240// without updating recency or frequency.
241func (c *ARCCache) Contains(key interface{}) bool {
242	c.lock.RLock()
243	defer c.lock.RUnlock()
244	return c.t1.Contains(key) || c.t2.Contains(key)
245}
246
247// Peek is used to inspect the cache value of a key
248// without updating recency or frequency.
249func (c *ARCCache) Peek(key interface{}) (value interface{}, ok bool) {
250	c.lock.RLock()
251	defer c.lock.RUnlock()
252	if val, ok := c.t1.Peek(key); ok {
253		return val, ok
254	}
255	return c.t2.Peek(key)
256}
257