6 "github.com/hashicorp/golang-lru/simplelru"
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.
17 type 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
21 t1 simplelru.LRUCache // T1 is the LRU for recently accessed items
22 b1 simplelru.LRUCache // B1 is the LRU for evictions from t1
24 t2 simplelru.LRUCache // T2 is the LRU for frequently accessed items
25 b2 simplelru.LRUCache // B2 is the LRU for evictions from t2
30 // NewARC creates an ARC of the given size
31 func NewARC(size int) (*ARCCache, error) {
32 // Create the sub LRUs
33 b1, err := simplelru.NewLRU(size, nil)
37 b2, err := simplelru.NewLRU(size, nil)
41 t1, err := simplelru.NewLRU(size, nil)
45 t2, err := simplelru.NewLRU(size, nil)
62 // Get looks up a key's value from the cache.
63 func (c *ARCCache) Get(key interface{}) (value interface{}, ok bool) {
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 {
75 // Check if the value is contained in T2 (frequent)
76 if val, ok := c.t2.Get(key); ok {
84 // Add adds a value to the cache.
85 func (c *ARCCache) Add(key, value interface{}) {
89 // Check if the value is contained in T1 (recent), and potentially
90 // promote it to frequent T2
91 if c.t1.Contains(key) {
97 // Check if the value is already in T2 (frequent) and update it
98 if c.t2.Contains(key) {
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
111 delta = b2Len / b1Len
113 if c.p+delta >= c.size {
119 // Potentially need to make room in the cache
120 if c.t1.Len()+c.t2.Len() >= c.size {
127 // Add the key to the frequently used list
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
140 delta = b1Len / b2Len
148 // Potentially need to make room in the cache
149 if c.t1.Len()+c.t2.Len() >= c.size {
156 // Add the key to the frequently used list
161 // Potentially need to make room in the cache
162 if c.t1.Len()+c.t2.Len() >= c.size {
166 // Keep the size of the ghost buffers trim
167 if c.b1.Len() > c.size-c.p {
170 if c.b2.Len() > c.p {
174 // Add to the recently seen list
179 // replace is used to adaptively evict from either T1 or T2
180 // based on the current learned value of P
181 func (c *ARCCache) replace(b2ContainsKey bool) {
183 if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) {
184 k, _, ok := c.t1.RemoveOldest()
189 k, _, ok := c.t2.RemoveOldest()
196 // Len returns the number of cached entries
197 func (c *ARCCache) Len() int {
199 defer c.lock.RUnlock()
200 return c.t1.Len() + c.t2.Len()
203 // Keys returns all the cached keys
204 func (c *ARCCache) Keys() []interface{} {
206 defer c.lock.RUnlock()
209 return append(k1, k2...)
212 // Remove is used to purge a key from the cache
213 func (c *ARCCache) Remove(key interface{}) {
215 defer c.lock.Unlock()
216 if c.t1.Remove(key) {
219 if c.t2.Remove(key) {
222 if c.b1.Remove(key) {
225 if c.b2.Remove(key) {
230 // Purge is used to clear the cache
231 func (c *ARCCache) Purge() {
233 defer c.lock.Unlock()
240 // Contains is used to check if the cache contains a key
241 // without updating recency or frequency.
242 func (c *ARCCache) Contains(key interface{}) bool {
244 defer c.lock.RUnlock()
245 return c.t1.Contains(key) || c.t2.Contains(key)
248 // Peek is used to inspect the cache value of a key
249 // without updating recency or frequency.
250 func (c *ARCCache) Peek(key interface{}) (value interface{}, ok bool) {
252 defer c.lock.RUnlock()
253 if val, ok := c.t1.Peek(key); ok {
256 return c.t2.Peek(key)