arc.go

Documentation: github.com/hashicorp/golang-lru

     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  }
   177  
   178  // replace is used to adaptively evict from either T1 or T2
   179  // based on the current learned value of P
   180  func (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
   196  func (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
   203  func (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
   212  func (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
   230  func (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.
   241  func (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.
   249  func (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
View as plain text