/
lrucache.go
401 lines (365 loc) · 11.3 KB
/
lrucache.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
// Copyright © Hraban Luyat <hraban@0brg.net>
//
// License for use of this code is detailed in the LICENSE file
// Light-weight in-memory LRU (object) cache library for Go.
//
// To use this library, first create a cache:
//
// c := lrucache.New(1234)
//
// Then, optionally, define a type that implements some of the interfaces:
//
// type cacheableInt int
//
// func (i cacheableInt) OnPurge(why lrucache.PurgeReason) {
// fmt.Printf("Purging %d\n", i)
// }
//
// Finally:
//
// for i := 0; i < 2000; i++ {
// c.Set(strconv.Itoa(i), cacheableInt(i))
// }
//
// This will generate the following output:
//
// Purging 0
// Purging 1
// ...
// Purging 764
// Purging 765
//
// Note:
//
// * The unit of item sizes is not defined; whatever it is, once the sum
// exceeds the maximum cache size, elements start getting purged until it
// drops below the threshold again.
//
// * These integers are passed by value. Caching pointers is, of course, Okay,
// but be careful when caching a memory location that holds two different
// values at different points in time; updating the value of a pointer after
// caching it will change the cached value.
//
package lrucache
import (
"errors"
"sync"
)
// A function that generates a fresh entry on "cache miss". See the Cache.OnMiss
// method.
type OnMissHandler func(string) (Cacheable, error)
// Cache is a single object containing the full state of a cache.
//
// All access to this object through its public methods is gated through a
// single mutex. It is, therefore, safe for concurrent use, although it will not
// actually offer any parallel performance benefits.
type Cache struct {
// Everything on this struct is accessed through the lock. I'm sure there is a
// more efficient way of doing this, but it's a good start.
lock sync.RWMutex
// We could technically make this concurrently accessible through atomic
// operations, but it seems hardly worth it.
size int64
maxSize int64
entries map[string]*cacheEntry
// most recently used entry
mostRU *cacheEntry
// least recently used entry
leastRU *cacheEntry
// If not nil, invoked for every cache miss.
onMiss OnMissHandler
}
// Anything can be cached!
type Cacheable interface{}
// Optional interface for cached objects. If this interface is not implemented,
// an element is assumed to have size 1.
type SizeAware interface {
// See Cache.MaxSize() for an explanation of the semantics. Please report a
// constant size; the cache does not expect objects to change size while
// they are cached. Items are trusted to report their own size accurately.
Size() int64
}
func getSize(x Cacheable) int64 {
if s, ok := x.(SizeAware); ok {
return s.Size()
}
return 1
}
// Reasons for a cached element to be deleted from the cache
type PurgeReason int
const (
// Cache is growing too large and this is the least used item
CACHEFULL PurgeReason = iota
// This item was explicitly deleted using Cache.Delete(id)
EXPLICITDELETE
// A new element with the same key is stored (usually indicates an update)
KEYCOLLISION
)
// Optional interface for cached objects
type NotifyPurge interface {
// Called once when the element is purged from cache. The argument
// indicates why.
//
// Example use-case: a session cache where sessions are not stored in a
// database until they are purged from the memory cache. As long as the
// memory cache is large enough to hold all of them, they expire before the
// cache grows too large and no database connection is ever needed. This
// OnPurge implementation would store items to a database iff reason ==
// CACHEFULL.
//
// Called from within a private goroutine, but never called concurrently
// with other elements' OnPurge(). The entire cache is blocked until this
// function returns. By all means, feel free to launch a fresh goroutine
// and return immediately.
OnPurge(why PurgeReason)
}
type cacheEntry struct {
payload Cacheable
id string
// youngest older entry (age being usage) (DLL pointer)
older *cacheEntry
// oldest younger entry (age being usage) (DLL pointer)
younger *cacheEntry
}
// Only call c.OnPurge() if c implements NotifyPurge.
func safeOnPurge(c Cacheable, why PurgeReason) {
if t, ok := c.(NotifyPurge); ok {
t.OnPurge(why)
}
return
}
func removeEntry(c *Cache, e *cacheEntry) {
delete(c.entries, e.id)
if e.older == nil {
c.leastRU = e.younger
} else {
e.older.younger = e.younger
}
if e.younger == nil {
c.mostRU = e.older
} else {
e.younger.older = e.older
}
c.size -= getSize(e.payload)
return
}
// purgeLRU removes the least recently used from the cache
func purgeLRU(c *Cache) {
safeOnPurge(c.leastRU.payload, CACHEFULL)
removeEntry(c, c.leastRU)
return
}
// trimCache removes elements from the cache until its size <= max size
func trimCache(c *Cache) {
if c.maxSize <= 0 {
return
}
for c.size > c.maxSize {
purgeLRU(c)
}
return
}
// directSet sets an entry in the cache without managing locks
func directSet(c *Cache, id string, payload Cacheable) {
// Overwrite old entry
if old, ok := c.entries[id]; ok {
safeOnPurge(old.payload, KEYCOLLISION)
removeEntry(c, old)
}
e := cacheEntry{payload: payload, id: id}
c.entries[id] = &e
size := getSize(payload)
if size == 0 {
return
}
if c.leastRU == nil { // aka "if this is the first entry..."
// init DLL
c.leastRU = &e
c.mostRU = &e
e.younger = nil
e.older = nil
} else {
// e is younger than the old "most recently used"
c.mostRU.younger = &e
e.older = c.mostRU
c.mostRU = &e
}
c.size += size
trimCache(c)
return
}
// handleCacheMiss calls the onMiss handler (if any) and stores the result
func handleCacheMiss(c *Cache, id string) (Cacheable, error) {
var val Cacheable
var err error = ErrNotFound
c.lock.RLock()
onmiss := c.onMiss
c.lock.RUnlock()
if onmiss != nil {
val, err = onmiss(id)
if err == nil {
if val != nil {
c.lock.Lock()
defer c.lock.Unlock()
directSet(c, id, val)
} else {
err = ErrNotFound
}
}
}
return val, err
}
func (c *Cache) Init(maxsize int64) {
c.maxSize = maxsize
c.entries = map[string]*cacheEntry{}
return
}
// Set stores an item in cache. Panics if the cacheable is nil. It can, however, be
// an interface pointer to nil.
// TODO: write a test for the above.
func (c *Cache) Set(id string, p Cacheable) {
if p == nil {
panic("Cacheable value must not be nil")
}
c.lock.Lock()
defer c.lock.Unlock()
directSet(c, id, p)
}
var ErrNotFound = errors.New("Key not found in cache")
// Get fetches an element from the cache.
//
// Updates the cache to mark this element as least recently used. If no element
// is found for this id, a registered onmiss handler will be called.
func (c *Cache) Get(id string) (Cacheable, error) {
// A Get still modifies the cache in an LRU, so we need a write lock
c.lock.Lock()
// WARNING!! No deferred Unlock! Do not panic!
e, ok := c.entries[id]
if !ok {
// We don't want to lock the entire cache while handling the cache miss
c.lock.Unlock()
return handleCacheMiss(c, id)
}
defer c.lock.Unlock()
if e.younger == nil {
// I'm already the fresh kid on the block
return e.payload, nil
}
// Put element at the start of the LRU list
if e.older != nil {
e.older.younger = e.younger
} else {
// If nobody was older than me, my younger sibling is now the oldest.
c.leastRU = e.younger
}
e.younger.older = e.older
e.older = c.mostRU // my elder is whoever used to be youngest
c.mostRU = e // I'm the newest one now
e.younger = nil // nobody's younger than me
e.older.younger = e //
return e.payload, nil
}
func (c *Cache) Delete(id string) {
c.lock.Lock()
defer c.lock.Unlock()
e, ok := c.entries[id]
if ok {
safeOnPurge(e.payload, EXPLICITDELETE)
if getSize(e.payload) != 0 {
removeEntry(c, e)
}
}
return
}
// OnMiss stores a callback for handling Gets to unknown keys.
//
// Say you're looking for entry "bob", but there is no such entry in your
// cache. Do you always handle that in the same way? Get "bob" from disk or S3?
// Then you could register an OnMiss handler which does this for you. Make this
// your "persistent storage lookup" function, hook it up to your cache right
// here and it will be called automatically next ime you're looking for bob. The
// advantage is that you can expect Get() calls to resolve.
//
// The Get() call invoking this OnMiss will always return whatever value is
// returned from the OnMiss handler, error or not.
//
// If the function returns a non-nil error, that error is directly returned
// from the Get() call that caused it to be invoked. Otherwise, if the function
// return value is not nil, it is stored in cache.
//
// To remove a previously set OnMiss handler, call OnMiss(nil).
//
// Return (nil, nil) to indicate the specific key could not be found. It will
// be treated as a Get() to an unknown key without an OnMiss handler set.
//
// The synchronization lock which controls access to the entire cache is
// released before calling this function. The benefit is that a long running
// OnMiss handler call won't block the cache. The downside is that calling Get
// concurrently with the same key, before the first OnMiss call returns, will
// invoke another OnMiss call; the last one to return will have its value stored
// in the cache. To avoid this, wrap the OnMiss handler in a NoConcurrentDupes.
func (c *Cache) OnMiss(f OnMissHandler) {
c.lock.Lock()
defer c.lock.Unlock()
c.onMiss = f
}
// MaxSize updates the maximum size of all cached elements.
//
// The size of the cache is the sum of calling .Size() on every individual
// element. If an element has no such method, the default is 1. Notably, the
// size has nothing to do with bytes in memory (unless the individual cached
// entries have a .Size method which returns their size, in bytes). If (roughly)
// all cached items are going to be (roughly) the same size it makes sense to
// set maxSize to the maximum number of elements you want to allow in cache. To
// remove the limit altogether set a maximum size of 0. No elements will be
// purged with reason CACHEFULL until the next call to MaxSize.
//
// Can be changed at any point during the cache's lifetime.
func (c *Cache) MaxSize(i int64) {
c.lock.Lock()
defer c.lock.Unlock()
c.maxSize = i
trimCache(c)
}
func (c *Cache) Size() int64 {
c.lock.RLock()
defer c.lock.RUnlock()
return c.size
}
// Close is an obsolete explicit closer method.
//
// Kept around for backwards compatibility, but not necessary anymore.
func (c *Cache) Close() error {
return nil
}
// Create and initialize a new cache, ready for use.
func New(maxsize int64) *Cache {
var mem Cache
c := &mem
c.Init(maxsize)
// Go's SetFinalizer cannot be unit tested, so basically it's a joke.
//runtime.SetFinalizer(c, finalizeCache)
return c
}
// Shared cache for configuration-less use
var sharedCache = New(0)
// Get an element from the shared cache.
func Get(id string) (Cacheable, error) {
return sharedCache.Get(id)
}
// Put an object in the shared cache (requires no configuration).
func Set(id string, c Cacheable) {
sharedCache.Set(id, c)
return
}
// Delete an item from the shared cache.
func Delete(id string) {
sharedCache.Delete(id)
return
}
// A shared cache is available immediately for all users of this library. By
// default, there is no size limit. Use this function to change that.
func MaxSize(size int64) {
sharedCache.MaxSize(size)
return
}