vendor/github.com/hashicorp/golang-lru/arc.go

   1 package lru
   2
   3 import (
   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.
  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
  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
  31 func 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.
  63 func (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.
  85 func (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
 181 func (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
 197 func (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
 204 func (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
 213 func (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
 231 func (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.
 242 func (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.
 250 func (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 }