netramesh

1
package cache
2

3
import (
4
	"crypto/rand"
5
	"math"
6
	"math/big"
7
	insecurerand "math/rand"
8
	"os"
9
	"runtime"
10
	"time"
11
)
12

13
// This is an experimental and unexported (for now) attempt at making a cache
14
// with better algorithmic complexity than the standard one, namely by
15
// preventing write locks of the entire cache when an item is added. As of the
16
// time of writing, the overhead of selecting buckets results in cache
17
// operations being about twice as slow as for the standard cache with small
18
// total cache sizes, and faster for larger ones.
19
//
20
// See cache_test.go for a few benchmarks.
21

22
type unexportedShardedCache struct {
23
	*shardedCache
24
}
25

26
type shardedCache struct {
27
	seed    uint32
28
	m       uint32
29
	cs      []*cache
30
	janitor *shardedJanitor
31
}
32

33
// djb2 with better shuffling. 5x faster than FNV with the hash.Hash overhead.
34
func djb33(seed uint32, k string) uint32 {
35
	var (
36
		l = uint32(len(k))
37
		d = 5381 + seed + l
38
		i = uint32(0)
39
	)
40
	// Why is all this 5x faster than a for loop?
41
	if l >= 4 {
42
		for i < l-4 {
43
			d = (d * 33) ^ uint32(k[i])
44
			d = (d * 33) ^ uint32(k[i+1])
45
			d = (d * 33) ^ uint32(k[i+2])
46
			d = (d * 33) ^ uint32(k[i+3])
47
			i += 4
48
		}
49
	}
50
	switch l - i {
51
	case 1:
52
	case 2:
53
		d = (d * 33) ^ uint32(k[i])
54
	case 3:
55
		d = (d * 33) ^ uint32(k[i])
56
		d = (d * 33) ^ uint32(k[i+1])
57
	case 4:
58
		d = (d * 33) ^ uint32(k[i])
59
		d = (d * 33) ^ uint32(k[i+1])
60
		d = (d * 33) ^ uint32(k[i+2])
61
	}
62
	return d ^ (d >> 16)
63
}
64

65
func (sc *shardedCache) bucket(k string) *cache {
66
	return sc.cs[djb33(sc.seed, k)%sc.m]
67
}
68

69
func (sc *shardedCache) Set(k string, x interface{}, d time.Duration) {
70
	sc.bucket(k).Set(k, x, d)
71
}
72

73
func (sc *shardedCache) Add(k string, x interface{}, d time.Duration) error {
74
	return sc.bucket(k).Add(k, x, d)
75
}
76

77
func (sc *shardedCache) Replace(k string, x interface{}, d time.Duration) error {
78
	return sc.bucket(k).Replace(k, x, d)
79
}
80

81
func (sc *shardedCache) Get(k string) (interface{}, bool) {
82
	return sc.bucket(k).Get(k)
83
}
84

85
func (sc *shardedCache) Increment(k string, n int64) error {
86
	return sc.bucket(k).Increment(k, n)
87
}
88

89
func (sc *shardedCache) IncrementFloat(k string, n float64) error {
90
	return sc.bucket(k).IncrementFloat(k, n)
91
}
92

93
func (sc *shardedCache) Decrement(k string, n int64) error {
94
	return sc.bucket(k).Decrement(k, n)
95
}
96

97
func (sc *shardedCache) Delete(k string) {
98
	sc.bucket(k).Delete(k)
99
}
100

101
func (sc *shardedCache) DeleteExpired() {
102
	for _, v := range sc.cs {
103
		v.DeleteExpired()
104
	}
105
}
106

107
// Returns the items in the cache. This may include items that have expired,
108
// but have not yet been cleaned up. If this is significant, the Expiration
109
// fields of the items should be checked. Note that explicit synchronization
110
// is needed to use a cache and its corresponding Items() return values at
111
// the same time, as the maps are shared.
112
func (sc *shardedCache) Items() []map[string]Item {
113
	res := make([]map[string]Item, len(sc.cs))
114
	for i, v := range sc.cs {
115
		res[i] = v.Items()
116
	}
117
	return res
118
}
119

120
func (sc *shardedCache) Flush() {
121
	for _, v := range sc.cs {
122
		v.Flush()
123
	}
124
}
125

126
type shardedJanitor struct {
127
	Interval time.Duration
128
	stop     chan bool
129
}
130

131
func (j *shardedJanitor) Run(sc *shardedCache) {
132
	j.stop = make(chan bool)
133
	tick := time.Tick(j.Interval)
134
	for {
135
		select {
136
		case <-tick:
137
			sc.DeleteExpired()
138
		case <-j.stop:
139
			return
140
		}
141
	}
142
}
143

144
func stopShardedJanitor(sc *unexportedShardedCache) {
145
	sc.janitor.stop <- true
146
}
147

148
func runShardedJanitor(sc *shardedCache, ci time.Duration) {
149
	j := &shardedJanitor{
150
		Interval: ci,
151
	}
152
	sc.janitor = j
153
	go j.Run(sc)
154
}
155

156
func newShardedCache(n int, de time.Duration) *shardedCache {
157
	max := big.NewInt(0).SetUint64(uint64(math.MaxUint32))
158
	rnd, err := rand.Int(rand.Reader, max)
159
	var seed uint32
160
	if err != nil {
161
		os.Stderr.Write([]byte("WARNING: go-cache's newShardedCache failed to read from the system CSPRNG (/dev/urandom or equivalent.) Your system's security may be compromised. Continuing with an insecure seed.\n"))
162
		seed = insecurerand.Uint32()
163
	} else {
164
		seed = uint32(rnd.Uint64())
165
	}
166
	sc := &shardedCache{
167
		seed: seed,
168
		m:    uint32(n),
169
		cs:   make([]*cache, n),
170
	}
171
	for i := 0; i < n; i++ {
172
		c := &cache{
173
			defaultExpiration: de,
174
			items:             map[string]Item{},
175
		}
176
		sc.cs[i] = c
177
	}
178
	return sc
179
}
180

181
func unexportedNewSharded(defaultExpiration, cleanupInterval time.Duration, shards int) *unexportedShardedCache {
182
	if defaultExpiration == 0 {
183
		defaultExpiration = -1
184
	}
185
	sc := newShardedCache(shards, defaultExpiration)
186
	SC := &unexportedShardedCache{sc}
187
	if cleanupInterval > 0 {
188
		runShardedJanitor(sc, cleanupInterval)
189
		runtime.SetFinalizer(SC, stopShardedJanitor)
190
	}
191
	return SC
192
}
193