-
Notifications
You must be signed in to change notification settings - Fork 0
/
cache.go
188 lines (169 loc) · 4.4 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
package cache
import (
"errors"
"sync"
"sync/atomic"
"time"
)
var (
// KeyError is returned by Get if a key is not found in the cache.
KeyError = errors.New("Key not found.")
ExpiredError = errors.New("Key expired.")
// MaxSizeError is returned by Set on implementations of Interface that have max size limits.
MaxSizeError = errors.New("Cache full.")
)
// Interface is the common cache interface for all implementations.
type Interface interface {
// Interface implements Upstream and returns KeyError if a key is not found in cache.
Upstream
// Set assigns a value to a key and sets the expiration time
Set(key, value interface{}, exp *time.Time) error
// Evict drops the provided keys from cache (if they exist) and returns the new size of the cache.
// Calling Evict without arguments returns the current cache size.
Evict(keys ...interface{}) (size int)
Metrics() Metrics
}
// Never is a helper that returns a nil expiration time.
func Never() *time.Time {
return nil
}
func Exp(ttl time.Duration) *time.Time {
exp := time.Now().Add(ttl)
return &exp
}
// Cache implements Interface.
// Removal of expired items is the responsibility of the caller.
type Cache struct {
values map[interface{}]interface{}
exp map[interface{}]*time.Time
maxsize int
mu sync.RWMutex
metrics Metrics
}
// New returns a new Cache.
// size determines the maximum number of items the cache can hold.
// If set to zero or less the cache will not have a size limit.
func New(size int) *Cache {
return &Cache{
values: make(map[interface{}]interface{}),
exp: make(map[interface{}]*time.Time),
maxsize: size,
}
}
func (c *Cache) init() {
if c.values == nil {
c.values = make(map[interface{}]interface{})
}
if c.exp == nil {
c.exp = make(map[interface{}]*time.Time)
}
}
// Set assigns a value to a key and sets the expiration time
// If the size limit is reached it returns MaxSizeError.
func (c *Cache) Set(k, v interface{}, exp *time.Time) error {
c.mu.Lock()
defer c.mu.Unlock()
if _, ok := c.values[k]; !ok && c.maxsize > 0 && len(c.values) >= c.maxsize {
return MaxSizeError
}
c.values[k] = v
if exp != nil {
c.exp[k] = exp
}
return nil
}
// Get returns a value assigned to a key and it's expiration time.
// If a key does not exist in cache KeyError is returned.
// If a key is expired ExpiredError is returned
func (c *Cache) Get(k interface{}) (v interface{}, exp *time.Time, err error) {
c.mu.RLock()
defer c.mu.RUnlock()
var ok bool
if v, ok = c.values[k]; ok {
if exp = c.exp[k]; exp == nil || exp.After(time.Now()) {
atomic.AddInt64(&c.metrics.Hit, 1)
return
}
go func() {
c.mu.Lock()
defer c.mu.Unlock()
delete(c.values, k)
delete(c.exp, k)
}()
return nil, nil, ExpiredError
}
atomic.AddInt64(&c.metrics.Miss, 1)
return nil, nil, KeyError
}
// Size returns size of all keys in cache both expired and fresh
func (c *Cache) Size() int {
c.mu.RLock()
defer c.mu.RUnlock()
return len(c.values)
}
// Trim removes all expired keys and returns a slice of removed keys
func (c *Cache) Trim(now time.Time) []interface{} {
c.mu.Lock()
defer c.mu.Unlock()
expired := make([]interface{}, 0, len(c.exp))
for k, exp := range c.exp {
if exp != nil && exp.Before(now) {
expired = append(expired, k)
}
}
for _, k := range expired {
delete(c.exp, k)
delete(c.values, k)
}
c.metrics.Expired += int64(len(expired))
return expired
}
func (c *Cache) evict(keys []interface{}) (n int) {
for _, k := range keys {
if _, ok := c.values[k]; ok {
delete(c.values, k)
delete(c.exp, k)
n++
}
}
return
}
// Evict removes items from the cache. It returns the new cache size.
func (c *Cache) Evict(keys ...interface{}) (size int) {
c.mu.Lock()
defer c.mu.Unlock()
c.metrics.Evict += int64(c.evict(keys))
return len(c.values)
}
type Metrics struct {
Hit, Miss, Evict, Expired, Items int64
}
func (c *Cache) Metrics() (m Metrics) {
c.mu.RLock()
defer c.mu.RUnlock()
m.Hit = atomic.LoadInt64(&c.metrics.Hit)
m.Miss = atomic.LoadInt64(&c.metrics.Miss)
m.Evict = c.metrics.Evict
m.Expired = c.metrics.Expired
m.Items = int64(len(c.values))
return
}
type EvictionPolicy int
const (
PolicyNone EvictionPolicy = iota
PolicyFIFO
PolicyLRU
PolicyLFU
)
func NewCache(size int, policy EvictionPolicy) Interface {
switch policy {
case PolicyFIFO:
return NewFIFO(size)
case PolicyLRU:
return NewLRU(size)
case PolicyLFU:
return NewLFU(size)
default:
return New(size)
}
}