1package cache 2 3import ( 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 22type unexportedShardedCache struct { 23 *shardedCache 24} 25 26type 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. 34func 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 65func (sc *shardedCache) bucket(k string) *cache { 66 return sc.cs[djb33(sc.seed, k)%sc.m] 67} 68 69func (sc *shardedCache) Set(k string, x interface{}, d time.Duration) { 70 sc.bucket(k).Set(k, x, d) 71} 72 73func (sc *shardedCache) Add(k string, x interface{}, d time.Duration) error { 74 return sc.bucket(k).Add(k, x, d) 75} 76 77func (sc *shardedCache) Replace(k string, x interface{}, d time.Duration) error { 78 return sc.bucket(k).Replace(k, x, d) 79} 80 81func (sc *shardedCache) Get(k string) (interface{}, bool) { 82 return sc.bucket(k).Get(k) 83} 84 85func (sc *shardedCache) Increment(k string, n int64) error { 86 return sc.bucket(k).Increment(k, n) 87} 88 89func (sc *shardedCache) IncrementFloat(k string, n float64) error { 90 return sc.bucket(k).IncrementFloat(k, n) 91} 92 93func (sc *shardedCache) Decrement(k string, n int64) error { 94 return sc.bucket(k).Decrement(k, n) 95} 96 97func (sc *shardedCache) Delete(k string) { 98 sc.bucket(k).Delete(k) 99} 100 101func (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. 112func (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 120func (sc *shardedCache) Flush() { 121 for _, v := range sc.cs { 122 v.Flush() 123 } 124} 125 126type shardedJanitor struct { 127 Interval time.Duration 128 stop chan bool 129} 130 131func (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 144func stopShardedJanitor(sc *unexportedShardedCache) { 145 sc.janitor.stop <- true 146} 147 148func runShardedJanitor(sc *shardedCache, ci time.Duration) { 149 j := &shardedJanitor{ 150 Interval: ci, 151 } 152 sc.janitor = j 153 go j.Run(sc) 154} 155 156func 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 181func 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