2q.go

Documentation: github.com/hashicorp/golang-lru

     1  package lru
     2  
     3  import (
     4  	"fmt"
     5  	"sync"
     6  
     7  	"github.com/hashicorp/golang-lru/simplelru"
     8  )
     9  
    10  const (
    11  	// Default2QRecentRatio is the ratio of the 2Q cache dedicated
    12  	// to recently added entries that have only been accessed once.
    13  	Default2QRecentRatio = 0.25
    14  
    15  	// Default2QGhostEntries is the default ratio of ghost
    16  	// entries kept to track entries recently evicted
    17  	Default2QGhostEntries = 0.50
    18  )
    19  
    20  // TwoQueueCache is a thread-safe fixed size 2Q cache.
    21  // 2Q is an enhancement over the standard LRU cache
    22  // in that it tracks both frequently and recently used
    23  // entries separately. This avoids a burst in access to new
    24  // entries from evicting frequently used entries. It adds some
    25  // additional tracking overhead to the standard LRU cache, and is
    26  // computationally about 2x the cost, and adds some metadata over
    27  // head. The ARCCache is similar, but does not require setting any
    28  // parameters.
    29  type TwoQueueCache struct {
    30  	size       int
    31  	recentSize int
    32  
    33  	recent      simplelru.LRUCache
    34  	frequent    simplelru.LRUCache
    35  	recentEvict simplelru.LRUCache
    36  	lock        sync.RWMutex
    37  }
    38  
    39  // New2Q creates a new TwoQueueCache using the default
    40  // values for the parameters.
    41  func New2Q(size int) (*TwoQueueCache, error) {
    42  	return New2QParams(size, Default2QRecentRatio, Default2QGhostEntries)
    43  }
    44  
    45  // New2QParams creates a new TwoQueueCache using the provided
    46  // parameter values.
    47  func New2QParams(size int, recentRatio, ghostRatio float64) (*TwoQueueCache, error) {
    48  	if size <= 0 {
    49  		return nil, fmt.Errorf("invalid size")
    50  	}
    51  	if recentRatio < 0.0 || recentRatio > 1.0 {
    52  		return nil, fmt.Errorf("invalid recent ratio")
    53  	}
    54  	if ghostRatio < 0.0 || ghostRatio > 1.0 {
    55  		return nil, fmt.Errorf("invalid ghost ratio")
    56  	}
    57  
    58  	// Determine the sub-sizes
    59  	recentSize := int(float64(size) * recentRatio)
    60  	evictSize := int(float64(size) * ghostRatio)
    61  
    62  	// Allocate the LRUs
    63  	recent, err := simplelru.NewLRU(size, nil)
    64  	if err != nil {
    65  		return nil, err
    66  	}
    67  	frequent, err := simplelru.NewLRU(size, nil)
    68  	if err != nil {
    69  		return nil, err
    70  	}
    71  	recentEvict, err := simplelru.NewLRU(evictSize, nil)
    72  	if err != nil {
    73  		return nil, err
    74  	}
    75  
    76  	// Initialize the cache
    77  	c := &TwoQueueCache{
    78  		size:        size,
    79  		recentSize:  recentSize,
    80  		recent:      recent,
    81  		frequent:    frequent,
    82  		recentEvict: recentEvict,
    83  	}
    84  	return c, nil
    85  }
    86  
    87  // Get looks up a key's value from the cache.
    88  func (c *TwoQueueCache) Get(key interface{}) (value interface{}, ok bool) {
    89  	c.lock.Lock()
    90  	defer c.lock.Unlock()
    91  
    92  	// Check if this is a frequent value
    93  	if val, ok := c.frequent.Get(key); ok {
    94  		return val, ok
    95  	}
    96  
    97  	// If the value is contained in recent, then we
    98  	// promote it to frequent
    99  	if val, ok := c.recent.Peek(key); ok {
   100  		c.recent.Remove(key)
   101  		c.frequent.Add(key, val)
   102  		return val, ok
   103  	}
   104  
   105  	// No hit
   106  	return nil, false
   107  }
   108  
   109  // Add adds a value to the cache.
   110  func (c *TwoQueueCache) Add(key, value interface{}) {
   111  	c.lock.Lock()
   112  	defer c.lock.Unlock()
   113  
   114  	// Check if the value is frequently used already,
   115  	// and just update the value
   116  	if c.frequent.Contains(key) {
   117  		c.frequent.Add(key, value)
   118  		return
   119  	}
   120  
   121  	// Check if the value is recently used, and promote
   122  	// the value into the frequent list
   123  	if c.recent.Contains(key) {
   124  		c.recent.Remove(key)
   125  		c.frequent.Add(key, value)
   126  		return
   127  	}
   128  
   129  	// If the value was recently evicted, add it to the
   130  	// frequently used list
   131  	if c.recentEvict.Contains(key) {
   132  		c.ensureSpace(true)
   133  		c.recentEvict.Remove(key)
   134  		c.frequent.Add(key, value)
   135  		return
   136  	}
   137  
   138  	// Add to the recently seen list
   139  	c.ensureSpace(false)
   140  	c.recent.Add(key, value)
   141  }
   142  
   143  // ensureSpace is used to ensure we have space in the cache
   144  func (c *TwoQueueCache) ensureSpace(recentEvict bool) {
   145  	// If we have space, nothing to do
   146  	recentLen := c.recent.Len()
   147  	freqLen := c.frequent.Len()
   148  	if recentLen+freqLen < c.size {
   149  		return
   150  	}
   151  
   152  	// If the recent buffer is larger than
   153  	// the target, evict from there
   154  	if recentLen > 0 && (recentLen > c.recentSize || (recentLen == c.recentSize && !recentEvict)) {
   155  		k, _, _ := c.recent.RemoveOldest()
   156  		c.recentEvict.Add(k, nil)
   157  		return
   158  	}
   159  
   160  	// Remove from the frequent list otherwise
   161  	c.frequent.RemoveOldest()
   162  }
   163  
   164  // Len returns the number of items in the cache.
   165  func (c *TwoQueueCache) Len() int {
   166  	c.lock.RLock()
   167  	defer c.lock.RUnlock()
   168  	return c.recent.Len() + c.frequent.Len()
   169  }
   170  
   171  // Keys returns a slice of the keys in the cache.
   172  // The frequently used keys are first in the returned slice.
   173  func (c *TwoQueueCache) Keys() []interface{} {
   174  	c.lock.RLock()
   175  	defer c.lock.RUnlock()
   176  	k1 := c.frequent.Keys()
   177  	k2 := c.recent.Keys()
   178  	return append(k1, k2...)
   179  }
   180  
   181  // Remove removes the provided key from the cache.
   182  func (c *TwoQueueCache) Remove(key interface{}) {
   183  	c.lock.Lock()
   184  	defer c.lock.Unlock()
   185  	if c.frequent.Remove(key) {
   186  		return
   187  	}
   188  	if c.recent.Remove(key) {
   189  		return
   190  	}
   191  	if c.recentEvict.Remove(key) {
   192  		return
   193  	}
   194  }
   195  
   196  // Purge is used to completely clear the cache.
   197  func (c *TwoQueueCache) Purge() {
   198  	c.lock.Lock()
   199  	defer c.lock.Unlock()
   200  	c.recent.Purge()
   201  	c.frequent.Purge()
   202  	c.recentEvict.Purge()
   203  }
   204  
   205  // Contains is used to check if the cache contains a key
   206  // without updating recency or frequency.
   207  func (c *TwoQueueCache) Contains(key interface{}) bool {
   208  	c.lock.RLock()
   209  	defer c.lock.RUnlock()
   210  	return c.frequent.Contains(key) || c.recent.Contains(key)
   211  }
   212  
   213  // Peek is used to inspect the cache value of a key
   214  // without updating recency or frequency.
   215  func (c *TwoQueueCache) Peek(key interface{}) (value interface{}, ok bool) {
   216  	c.lock.RLock()
   217  	defer c.lock.RUnlock()
   218  	if val, ok := c.frequent.Peek(key); ok {
   219  		return val, ok
   220  	}
   221  	return c.recent.Peek(key)
   222  }
   223
View as plain text