1package lru
2
3import (
4 "fmt"
5 "sync"
6
7 "github.com/hashicorp/golang-lru/simplelru"
8)
9
10const (
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.
29type 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.
41func 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.
47func 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.
88func (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.
110func (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
145func (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.
166func (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.
174func (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.
183func (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.
198func (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.
208func (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.
216func (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}