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