"Fossies" - the Fresh Open Source Software Archive

Member "mattermost-server-6.0.1/vendor/github.com/hashicorp/golang-lru/2q.go" (18 Oct 2021, 5585 Bytes) of package /linux/www/mattermost-server-6.0.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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 float64, 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     return
  142 }
  143 
  144 // ensureSpace is used to ensure we have space in the cache
  145 func (c *TwoQueueCache) ensureSpace(recentEvict bool) {
  146     // If we have space, nothing to do
  147     recentLen := c.recent.Len()
  148     freqLen := c.frequent.Len()
  149     if recentLen+freqLen < c.size {
  150         return
  151     }
  152 
  153     // If the recent buffer is larger than
  154     // the target, evict from there
  155     if recentLen > 0 && (recentLen > c.recentSize || (recentLen == c.recentSize && !recentEvict)) {
  156         k, _, _ := c.recent.RemoveOldest()
  157         c.recentEvict.Add(k, nil)
  158         return
  159     }
  160 
  161     // Remove from the frequent list otherwise
  162     c.frequent.RemoveOldest()
  163 }
  164 
  165 // Len returns the number of items in the cache.
  166 func (c *TwoQueueCache) Len() int {
  167     c.lock.RLock()
  168     defer c.lock.RUnlock()
  169     return c.recent.Len() + c.frequent.Len()
  170 }
  171 
  172 // Keys returns a slice of the keys in the cache.
  173 // The frequently used keys are first in the returned slice.
  174 func (c *TwoQueueCache) Keys() []interface{} {
  175     c.lock.RLock()
  176     defer c.lock.RUnlock()
  177     k1 := c.frequent.Keys()
  178     k2 := c.recent.Keys()
  179     return append(k1, k2...)
  180 }
  181 
  182 // Remove removes the provided key from the cache.
  183 func (c *TwoQueueCache) Remove(key interface{}) {
  184     c.lock.Lock()
  185     defer c.lock.Unlock()
  186     if c.frequent.Remove(key) {
  187         return
  188     }
  189     if c.recent.Remove(key) {
  190         return
  191     }
  192     if c.recentEvict.Remove(key) {
  193         return
  194     }
  195 }
  196 
  197 // Purge is used to completely clear the cache.
  198 func (c *TwoQueueCache) Purge() {
  199     c.lock.Lock()
  200     defer c.lock.Unlock()
  201     c.recent.Purge()
  202     c.frequent.Purge()
  203     c.recentEvict.Purge()
  204 }
  205 
  206 // Contains is used to check if the cache contains a key
  207 // without updating recency or frequency.
  208 func (c *TwoQueueCache) Contains(key interface{}) bool {
  209     c.lock.RLock()
  210     defer c.lock.RUnlock()
  211     return c.frequent.Contains(key) || c.recent.Contains(key)
  212 }
  213 
  214 // Peek is used to inspect the cache value of a key
  215 // without updating recency or frequency.
  216 func (c *TwoQueueCache) Peek(key interface{}) (value interface{}, ok bool) {
  217     c.lock.RLock()
  218     defer c.lock.RUnlock()
  219     if val, ok := c.frequent.Peek(key); ok {
  220         return val, ok
  221     }
  222     return c.recent.Peek(key)
  223 }