sharded.go

Documentation: github.com/patrickmn/go-cache

     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
View as plain text