← Back to branch summary

~nskaggs/+junk/xenial-test

« back to all changes in this revision

Viewing changes to src/github.com/juju/utils/cache/cache.go

  • Committer: Nicholas Skaggs
  • Date: 2016-10-24 20:56:05 UTC
  • Revision ID: nicholas.skaggs@canonical.com-20161024205605-z8lta0uvuhtxwzwl
Initi with beta15

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/github.com/juju/utils/cache/cache.go
 
1
// Copyright 2015 Canonical Ltd.
 
2
// Licensed under the LGPLv3, see LICENCE file for details.
 
3
 
 
4
// Package cache provides a simple caching mechanism
 
5
// that limits the age of cache entries and tries to avoid large
 
6
// repopulation events by staggering refresh times.
 
7
package cache
 
8
 
 
9
import (
 
10
        "math/rand"
 
11
        "sync"
 
12
        "time"
 
13
 
 
14
        "gopkg.in/errgo.v1"
 
15
)
 
16
 
 
17
// entry holds a cache entry. The expire field
 
18
// holds the time after which the entry will be
 
19
// considered invalid.
 
20
type entry struct {
 
21
        value  interface{}
 
22
        expire time.Time
 
23
}
 
24
 
 
25
// Key represents a cache key. It must be a comparable type.
 
26
type Key interface{}
 
27
 
 
28
// Cache holds a time-limited set of values for arbitrary keys.
 
29
type Cache struct {
 
30
        maxAge time.Duration
 
31
 
 
32
        // mu guards the fields below it.
 
33
        mu sync.Mutex
 
34
 
 
35
        // expire holds when the cache is due to expire.
 
36
        expire time.Time
 
37
 
 
38
        // We hold two maps so that can avoid scanning through all the
 
39
        // items in the cache when the cache needs to be refreshed.
 
40
        // Instead, we move items from old to new when they're accessed
 
41
        // and throw away the old map at refresh time.
 
42
        old, new map[Key]entry
 
43
}
 
44
 
 
45
// New returns a new Cache that will cache items for
 
46
// at most maxAge. If maxAge is zero, items will
 
47
// never be cached.
 
48
func New(maxAge time.Duration) *Cache {
 
49
        // The returned cache will have a zero-valued expire
 
50
        // time, so will expire immediately, causing the new
 
51
        // map to be created.
 
52
        return &Cache{
 
53
                maxAge: maxAge,
 
54
        }
 
55
}
 
56
 
 
57
// Len returns the total number of cached entries.
 
58
func (c *Cache) Len() int {
 
59
        c.mu.Lock()
 
60
        defer c.mu.Unlock()
 
61
        return len(c.old) + len(c.new)
 
62
}
 
63
 
 
64
// Evict removes the entry with the given key from the cache if present.
 
65
func (c *Cache) Evict(key Key) {
 
66
        c.mu.Lock()
 
67
        defer c.mu.Unlock()
 
68
        delete(c.new, key)
 
69
        delete(c.old, key)
 
70
}
 
71
 
 
72
// EvictAll removes all entries from the cache.
 
73
func (c *Cache) EvictAll() {
 
74
        c.mu.Lock()
 
75
        defer c.mu.Unlock()
 
76
        c.new = make(map[Key]entry)
 
77
        c.old = nil
 
78
}
 
79
 
 
80
// Get returns the value for the given key, using fetch to fetch
 
81
// the value if it is not found in the cache.
 
82
// If fetch returns an error, the returned error from Get will have
 
83
// the same cause.
 
84
func (c *Cache) Get(key Key, fetch func() (interface{}, error)) (interface{}, error) {
 
85
        return c.getAtTime(key, fetch, time.Now())
 
86
}
 
87
 
 
88
// getAtTime is the internal version of Get, useful for testing; now represents the current
 
89
// time.
 
90
func (c *Cache) getAtTime(key Key, fetch func() (interface{}, error), now time.Time) (interface{}, error) {
 
91
        if val, ok := c.cachedValue(key, now); ok {
 
92
                return val, nil
 
93
        }
 
94
        // Fetch the data without the mutex held
 
95
        // so that one slow fetch doesn't hold up
 
96
        // all the other cache accesses.
 
97
        val, err := fetch()
 
98
        if err != nil {
 
99
                // TODO consider caching cache misses.
 
100
                return nil, errgo.Mask(err, errgo.Any)
 
101
        }
 
102
        if c.maxAge < 2*time.Nanosecond {
 
103
                // If maxAge is < 2ns then the expiry code will panic because the
 
104
                // actual expiry time will be maxAge - a random value in the
 
105
                // interval [0, maxAge/2). If maxAge is < 2ns then this requires
 
106
                // a random interval in [0, 0) which causes a panic.
 
107
                //
 
108
                // This value is so small that there's no need to cache anyway,
 
109
                // which makes tests more obviously deterministic when using
 
110
                // a zero expiry time.
 
111
                return val, nil
 
112
        }
 
113
        c.mu.Lock()
 
114
        defer c.mu.Unlock()
 
115
        // Add the new cache entry. Because it's quite likely that a
 
116
        // large number of cache entries will be initially fetched at
 
117
        // the same time, we want to avoid a thundering herd of fetches
 
118
        // when they all expire at the same time, so we set the expiry
 
119
        // time to a random interval between [now + t.maxAge/2, now +
 
120
        // t.maxAge] and so they'll be spread over time without
 
121
        // compromising the maxAge value.
 
122
        c.new[key] = entry{
 
123
                value:  val,
 
124
                expire: now.Add(c.maxAge - time.Duration(rand.Int63n(int64(c.maxAge/2)))),
 
125
        }
 
126
        return val, nil
 
127
}
 
128
 
 
129
// cachedValue returns any cached value for the given key
 
130
// and whether it was found.
 
131
func (c *Cache) cachedValue(key Key, now time.Time) (interface{}, bool) {
 
132
        c.mu.Lock()
 
133
        defer c.mu.Unlock()
 
134
        if now.After(c.expire) {
 
135
                c.old = c.new
 
136
                c.new = make(map[Key]entry)
 
137
                c.expire = now.Add(c.maxAge)
 
138
        }
 
139
        if e, ok := c.entry(c.new, key, now); ok {
 
140
                return e.value, true
 
141
        }
 
142
        if e, ok := c.entry(c.old, key, now); ok {
 
143
                // An old entry has been accessed; move it to the new
 
144
                // map so that we only use a single map access for
 
145
                // subsequent lookups. Note that because we use the same
 
146
                // duration for cache refresh (c.expire) as for max
 
147
                // entry age, this is strictly speaking unnecessary
 
148
                // because any entries in old will have expired by the
 
149
                // time it is dropped.
 
150
                c.new[key] = e
 
151
                delete(c.old, key)
 
152
                return e.value, true
 
153
        }
 
154
        return nil, false
 
155
}
 
156
 
 
157
// entry returns an entry from the map and whether it
 
158
// was found. If the entry has expired, it is deleted from the map.
 
159
func (c *Cache) entry(m map[Key]entry, key Key, now time.Time) (entry, bool) {
 
160
        e, ok := m[key]
 
161
        if !ok {
 
162
                return entry{}, false
 
163
        }
 
164
        if now.After(e.expire) {
 
165
                // Delete expired entries.
 
166
                delete(m, key)
 
167
                return entry{}, false
 
168
        }
 
169
        return e, true
 
170
}