Frames

BigCache #148

0
1
2
3
4
5
6
7
8
9
1package bigcache
2
3import (
4 "fmt"
5 "time"
6)
7
8const (
9 minimumEntriesInShard = 10 // Minimum number of entries in single shard
10)
11
12// BigCache is fast, concurrent, evicting cache created to keep big number of entries without impact on performance.
13// It keeps entries on heap but omits GC for them. To achieve that, operations take place on byte arrays,
14// therefore entries (de)serialization in front of the cache will be needed in most use cases.
15type BigCache struct {
16 shards []*cacheShard
17 lifeWindow uint64
18 clock clock
19 hash Hasher
20 config Config
21 shardMask uint64
22 maxShardSize uint32
23 close chan struct{}
24}
25
26// Response will contain metadata about the entry for which GetWithInfo(key) was called
27type Response struct {
28 EntryStatus RemoveReason
29}
30
31// RemoveReason is a value used to signal to the user why a particular key was removed in the OnRemove callback.
32type RemoveReason uint32
33
34const (
35 // Expired means the key is past its LifeWindow.
36 // @TODO: Go defaults to 0 so in case we want to return EntryStatus back to the caller Expired cannot be differentiated
37 Expired RemoveReason = iota
38 // NoSpace means the key is the oldest and the cache size was at its maximum when Set was called, or the
39 // entry exceeded the maximum shard size.
40 NoSpace
41 // Deleted means Delete was called and this key was removed as a result.
42 Deleted
43)
44
45// NewBigCache initialize new instance of BigCache
46func NewBigCache(config Config) (*BigCache, error) {
47 return newBigCache(config, &systemClock{})
48}
49
50func newBigCache(config Config, clock clock) (*BigCache, error) {
51
52 if !isPowerOfTwo(config.Shards) {
53 return nil, fmt.Errorf("Shards number must be power of two")
54 }
55
56 if config.Hasher == nil {
57 config.Hasher = newDefaultHasher()
58 }
59
60 cache := &BigCache{
61 shards: make([]*cacheShard, config.Shards),
62 lifeWindow: uint64(config.LifeWindow.Seconds()),
63 clock: clock,
64 hash: config.Hasher,
65 config: config,
66 shardMask: uint64(config.Shards - 1),
67 maxShardSize: uint32(config.maximumShardSize()),
68 close: make(chan struct{}),
69 }
70
71 var onRemove func(wrappedEntry []byte, reason RemoveReason)
72 if config.OnRemoveWithMetadata != nil {
73 onRemove = cache.providedOnRemoveWithMetadata
74 } else if config.OnRemove != nil {
75 onRemove = cache.providedOnRemove
76 } else if config.OnRemoveWithReason != nil {
77 onRemove = cache.providedOnRemoveWithReason
78 } else {
79 onRemove = cache.notProvidedOnRemove
80 }
81
82 for i := 0; i < config.Shards; i++ {
83 cache.shards[i] = initNewShard(config, onRemove, clock)
84 }
85
86 if config.CleanWindow > 0 {
87 go func() {
88 ticker := time.NewTicker(config.CleanWindow)
89 defer ticker.Stop()
90 for {
91 select {
92 case t := <-ticker.C:
93 cache.cleanUp(uint64(t.Unix()))
94 case <-cache.close:
95 return
96 }
97 }
98 }()
99 }
100
101 return cache, nil
102}
103
104// Close is used to signal a shutdown of the cache when you are done with it.
105// This allows the cleaning goroutines to exit and ensures references are not
106// kept to the cache preventing GC of the entire cache.
107func (c *BigCache) Close() error {
108 close(c.close)
109 return nil
110}
111
112// Get reads entry for the key.
113// It returns an ErrEntryNotFound when
114// no entry exists for the given key.
115func (c *BigCache) Get(key string) ([]byte, error) {
116 hashedKey := c.hash.Sum64(key)
117 shard := c.getShard(hashedKey)
118 return shard.get(key, hashedKey)
119}
120
121// GetWithInfo reads entry for the key with Response info.
122// It returns an ErrEntryNotFound when
123// no entry exists for the given key.
124func (c *BigCache) GetWithInfo(key string) ([]byte, Response, error) {
125 hashedKey := c.hash.Sum64(key)
126 shard := c.getShard(hashedKey)
127 return shard.getWithInfo(key, hashedKey)
128}
129
130// Set saves entry under the key
131func (c *BigCache) Set(key string, entry []byte) error {
132 hashedKey := c.hash.Sum64(key)
133 shard := c.getShard(hashedKey)
134 return shard.set(key, hashedKey, entry)
135}
136
137// Delete removes the key
138func (c *BigCache) Delete(key string) error {
139 hashedKey := c.hash.Sum64(key)
140 shard := c.getShard(hashedKey)
141 return shard.del(hashedKey)
142}
143
144// Reset empties all cache shards
145func (c *BigCache) Reset() error {
146 for _, shard := range c.shards {
147 shard.reset(c.config)
148 }
149 return nil
150}
151
152// Len computes number of entries in cache
153func (c *BigCache) Len() int {
154 var len int
155 for _, shard := range c.shards {
156 len += shard.len()
157 }
158 return len
159}
160
161// Capacity returns amount of bytes store in the cache.
162func (c *BigCache) Capacity() int {
163 var len int
164 for _, shard := range c.shards {
165 len += shard.capacity()
166 }
167 return len
168}
169
170// Stats returns cache's statistics
171func (c *BigCache) Stats() Stats {
172 var s Stats
173 for _, shard := range c.shards {
174 tmp := shard.getStats()
175 s.Hits += tmp.Hits
176 s.Misses += tmp.Misses
177 s.DelHits += tmp.DelHits
178 s.DelMisses += tmp.DelMisses
179 s.Collisions += tmp.Collisions
180 }
181 return s
182}
183
184// KeyMetadata returns number of times a cached resource was requested.
185func (c *BigCache) KeyMetadata(key string) Metadata {
186 hashedKey := c.hash.Sum64(key)
187 shard := c.getShard(hashedKey)
188 return shard.getKeyMetadata(hashedKey)
189}
190
191// Iterator returns iterator function to iterate over EntryInfo's from whole cache.
192func (c *BigCache) Iterator() *EntryInfoIterator {
193 return newIterator(c)
194}
195
196func (c *BigCache) onEvict(oldestEntry []byte, currentTimestamp uint64, evict func(reason RemoveReason) error) bool {
197 oldestTimestamp := readTimestampFromEntry(oldestEntry)
198 if currentTimestamp-oldestTimestamp > c.lifeWindow {
199 evict(Expired)
200 return true
201 }
202 return false
203}
204
205func (c *BigCache) cleanUp(currentTimestamp uint64) {
206 for _, shard := range c.shards {
207 shard.cleanUp(currentTimestamp)
208 }
209}
210
211func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
212 return c.shards[hashedKey&c.shardMask]
213}
214
215func (c *BigCache) providedOnRemove(wrappedEntry []byte, reason RemoveReason) {
216 c.config.OnRemove(readKeyFromEntry(wrappedEntry), readEntry(wrappedEntry))
217}
218
219func (c *BigCache) providedOnRemoveWithReason(wrappedEntry []byte, reason RemoveReason) {
220 if c.config.onRemoveFilter == 0 || (1<<uint(reason))&c.config.onRemoveFilter > 0 {
221 c.config.OnRemoveWithReason(readKeyFromEntry(wrappedEntry), readEntry(wrappedEntry), reason)
222 }
223}
224
225func (c *BigCache) notProvidedOnRemove(wrappedEntry []byte, reason RemoveReason) {
226}
227
228func (c *BigCache) providedOnRemoveWithMetadata(wrappedEntry []byte, reason RemoveReason) {
229 hashedKey := c.hash.Sum64(readKeyFromEntry(wrappedEntry))
230 shard := c.getShard(hashedKey)
231 c.config.OnRemoveWithMetadata(readKeyFromEntry(wrappedEntry), readEntry(wrappedEntry), shard.getKeyMetadata(hashedKey))
232}
233