-
Notifications
You must be signed in to change notification settings - Fork 387
/
cache.go
234 lines (195 loc) · 5.36 KB
/
cache.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
// Copyright (C) 2021 Storj Labs, Inc.
// See LICENSE for copying information.
package lrucache
import (
"container/list"
"context"
"sync"
"time"
"github.com/spacemonkeygo/monkit/v3"
"storj.io/common/time2"
)
var mon = monkit.Package()
// Options controls the details of the expiration policy.
type Options struct {
// Expiration is how long an entry will be valid. It is not
// affected by LRU or anything: after this duration, the object
// is invalidated. A non-positive value means no expiration.
Expiration time.Duration
// Capacity is how many objects to keep in memory.
Capacity int
// Name is used to differentiate cache in monkit stat.
Name string
}
// cacheState contains all of the state for a cached entry.
type cacheState[T any] struct {
once sync.Once
when time.Time
order *list.Element
value T
loaded bool
}
// ExpiringLRU is a backwards compatible implementation of ExpiringLRU.
type ExpiringLRU = ExpiringLRUOf[any]
// ExpiringLRUOf caches values for string keys with a time based expiration and
// an LRU based eviciton policy.
type ExpiringLRUOf[T any] struct {
mu sync.Mutex
opts Options
data map[string]*cacheState[T]
order *list.List
}
// New constructs an ExpiringLRU with the given options.
func New(opts Options) *ExpiringLRU {
return NewOf[any](opts)
}
// NewOf constructs an ExpiringLRU with the given options.
func NewOf[T any](opts Options) *ExpiringLRUOf[T] {
return &ExpiringLRUOf[T]{
opts: opts,
data: make(map[string]*cacheState[T], opts.Capacity),
order: list.New(),
}
}
// Get returns the value for some key if it exists and is valid. If not
// it will call the provided function. Concurrent calls will dedupe as
// best as they are able. If the function returns an error, it is not
// cached and further calls will try again.
func (e *ExpiringLRUOf[T]) Get(ctx context.Context, key string, fn func() (T, error)) (value T, err error) {
if e.opts.Capacity <= 0 {
e.monitorCache(false)
return fn()
}
for {
e.mu.Lock()
state, ok := e.data[key]
switch {
case !ok:
for len(e.data) >= e.opts.Capacity {
back := e.order.Back()
delete(e.data, back.Value.(string))
e.order.Remove(back)
}
state = &cacheState[T]{
when: time2.Now(ctx),
order: e.order.PushFront(key),
}
e.data[key] = state
case e.opts.Expiration > 0 && time2.Since(ctx, state.when) > e.opts.Expiration:
delete(e.data, key)
e.order.Remove(state.order)
e.mu.Unlock()
continue
default:
e.order.MoveToFront(state.order)
}
e.mu.Unlock()
called := false
state.once.Do(func() {
called = true
value, err = fn()
if err == nil {
// careful because we don't want a `(*T)(nil) != nil` situation
// that's why we only assign to state.value if err == nil.
state.value = value
state.loaded = true
} else {
// the once has been used. delete it so that any other waiters
// will retry.
e.mu.Lock()
if e.data[key] == state {
delete(e.data, key)
e.order.Remove(state.order)
}
e.mu.Unlock()
}
})
if called || state.loaded {
e.monitorCache(!called)
return state.value, err
}
}
}
func (e *ExpiringLRUOf[T]) monitorCache(valueFromCache bool) {
if e.opts.Name == "" {
return
}
nameTag := monkit.NewSeriesTag("name", e.opts.Name)
if valueFromCache {
mon.Event("cache_hit", nameTag)
} else {
mon.Event("cache_miss", nameTag)
}
}
// Delete explicitly removes a key from the cache if it exists.
func (e *ExpiringLRUOf[T]) Delete(ctx context.Context, key string) {
e.mu.Lock()
defer e.mu.Unlock()
state, ok := e.data[key]
if !ok {
return
}
delete(e.data, key)
e.order.Remove(state.order)
}
// Add adds a value to the cache.
//
// replaced is true if the key already existed in the cache and was valid, hence
// the value is replaced.
func (e *ExpiringLRUOf[T]) Add(ctx context.Context, key string, value T) (replaced bool) {
e.mu.Lock()
defer e.mu.Unlock()
state, evicted := e.peek(ctx, key)
if state == nil {
if !evicted && e.order.Len() >= e.opts.Capacity {
item := e.order.Back()
delete(e.data, item.Value.(string))
}
e.data[key] = &cacheState[T]{
when: time2.Now(ctx),
order: e.order.PushFront(key),
value: value,
}
return false
}
e.order.Remove(state.order)
e.data[key] = &cacheState[T]{
when: time2.Now(ctx),
order: e.order.PushFront(key),
value: value,
}
return true
}
// GetCached returns the value associated with key and true if it exists and
// hasn't expired, otherwise nil and false.
func (e *ExpiringLRUOf[T]) GetCached(ctx context.Context, key string) (value T, cached bool) {
e.mu.Lock()
defer e.mu.Unlock()
state, _ := e.peek(ctx, key)
if state == nil {
var zero T
return zero, false
}
e.order.MoveToFront(state.order)
return state.value, true
}
// peek returns the state associated to the key if exists and it's valid,
// otherwise nil. evicted is true when the key existed but the state has
// expired.
//
// peek doesn't update the key as being recently used.
//
// NOTE the caller must always lock and unlock the mutex before calling this
// method.
func (e *ExpiringLRUOf[T]) peek(ctx context.Context, key string) (state *cacheState[T], evicted bool) {
state, ok := e.data[key]
if !ok {
return nil, false
}
if e.opts.Expiration > 0 && time2.Since(ctx, state.when) > e.opts.Expiration {
e.order.Remove(state.order)
delete(e.data, key)
return nil, true
}
return state, false
}