fastcache

README

fastcache - fast thread-safe inmemory cache for big number of entries in Go

Features

• Fast. Performance scales on multi-core CPUs. See benchmark results below.
• Thread-safe. Concurrent goroutines may read and write into a single cache instance.
• The fastcache is designed for storing big number of entries without GC overhead.
• Fastcache automatically evicts old entries when reaching the maximum cache size set on its creation.
• Simple API.
• Simple source code.
• Cache may be loaded from file and saved to file.
• Works on Google AppEngine.

Benchmarks

Fastcache performance is compared with BigCache, standard Go map and sync.Map.

GOMAXPROCS=4 go test github.com/VictoriaMetrics/fastcache -bench=. -benchtime=10s
goos: linux
goarch: amd64
pkg: github.com/VictoriaMetrics/fastcache

BenchmarkBigCacheSet-4      	    2000	  10937855 ns/op	   5.99 MB/s	 4660369 B/op	       6 allocs/op
BenchmarkBigCacheGet-4      	    2000	   6985426 ns/op	   9.38 MB/s	  684169 B/op	  131076 allocs/op
BenchmarkBigCacheSetGet-4   	    1000	  17301294 ns/op	   7.58 MB/s	 5046746 B/op	  131083 allocs/op
BenchmarkCacheSet-4         	    5000	   3975946 ns/op	  16.48 MB/s	    1142 B/op	       2 allocs/op
BenchmarkCacheGet-4         	    5000	   3572679 ns/op	  18.34 MB/s	    1141 B/op	       2 allocs/op
BenchmarkCacheSetGet-4      	    2000	   9337256 ns/op	  14.04 MB/s	    2856 B/op	       5 allocs/op
BenchmarkStdMapSet-4        	    2000	  14684273 ns/op	   4.46 MB/s	  268423 B/op	   65537 allocs/op
BenchmarkStdMapGet-4        	    5000	   2833647 ns/op	  23.13 MB/s	    2561 B/op	      13 allocs/op
BenchmarkStdMapSetGet-4     	     100	 137417861 ns/op	   0.95 MB/s	  387356 B/op	   65558 allocs/op
BenchmarkSyncMapSet-4       	    1000	  23300189 ns/op	   2.81 MB/s	 3417183 B/op	  262277 allocs/op
BenchmarkSyncMapGet-4       	    5000	   2316508 ns/op	  28.29 MB/s	    2543 B/op	      79 allocs/op
BenchmarkSyncMapSetGet-4    	    2000	  10444529 ns/op	  12.55 MB/s	 3412527 B/op	  262210 allocs/op
BenchmarkSaveToFile-4       	      50	 259800249 ns/op	 129.15 MB/s	55739129 B/op	    3091 allocs/op
BenchmarkLoadFromFile-4     	     100	 121189395 ns/op	 276.88 MB/s	98089036 B/op	    8748 allocs/op

MB/s column here actually means millions of operations per second. As you can see, fastcache is faster than the BigCache in all the cases. fastcache is faster than the standard Go map and sync.Map on workloads with inserts.

Limitations

• Keys and values must be byte slices. Other types must be marshaled before storing them in the cache.
• Summary size of a (key, value) entry cannot exceed 64KB. Bigger values must be split into smaller values before storing in the cache.
• There is no cache expiration. Entries are evicted from the cache only on cache size overflow. Entry deadline may be stored inside the value in order to implement cache expiration.

Architecture details

The cache uses ideas from BigCache:

• The cache consists of many buckets, each with its own lock. This helps scaling the performance on multi-core CPUs, since multiple CPUs may concurrently access distinct buckets.
• Each bucket consists of a hash(key) -> (key, value) position map and 64KB-sized byte slices (chunks) holding encoded (key, value) entries. Each bucket contains only O(chunksCount) pointers. For instance, 64GB cache would contain ~1M pointers, while similarly-sized map[string][]byte would contain ~1B pointers for short keys and values. This would lead to huge GC overhead.

64KB-sized chunks reduce memory fragmentation and the total memory usage comparing to a single big chunk per bucket. Chunks are allocated off-heap if possible. This reduces total memory usage because GC collects unused memory more frequently without the need in GOGC tweaking.

Users

• Fastcache has been extracted from VictoriaMetrics sources. See this article for more info about VictoriaMetrics.

FAQ

What is the difference between fastcache and other similar caches like BigCache or FreeCache?

• Fastcache is faster. See benchmark results above.
• Fastcache uses less memory due to lower heap fragmentation. This allows saving many GBs of memory on multi-GB caches.
• Fastcache API is simpler. The API is designed to be used in zero-allocation mode.

Why fastcache doesn't support cache expiration?

Because we don't need cache expiration in VictoriaMetrics. Cached entries inside VictoriaMetrics never expire. They are automatically evicted on cache size overflow.

It is easy to implement cache expiration on top of fastcache by caching values with marshaled deadlines and verifying deadlines after reading these values from the cache.

Why fastcache doesn't support advanced features such as thundering herd protection or callbacks on entries' eviction?

Because these features would complicate the code and would make it slower. Fastcache source code is simple - just copy-paste it and implement the feature you want on top of it.

Documentation

Index

• type Cache
  • func LoadFromFile(filePath string) (*Cache, error)
  • func LoadFromFileOrNew(filePath string, maxBytes int) *Cache
  • func New(maxBytes int) *Cache
  • func (c *Cache) Del(k []byte)
  • func (c *Cache) Get(dst, k []byte) []byte
  • func (c *Cache) Reset()
  • func (c *Cache) SaveToFile(filePath string) error
  • func (c *Cache) Set(k, v []byte)
  • func (c *Cache) UpdateStats(s *Stats)
• type Stats

Types

type Cache

type Cache struct {
	// contains filtered or unexported fields
}

Cache is a fast thread-safe inmemory cache optimized for big number of entries.

It has much lower impact on GC comparing to a simple `map[string][]byte`.

Use New or LoadFromFile* for creating new cache instance. Concurrent goroutines may call any Cache methods on the same cache instance.

Call Reset when the cache is no longer needed. This reclaims the allocated memory.

func LoadFromFile

func LoadFromFile(filePath string) (*Cache, error)

LoadFromFile loads cache data from the given filePath.

func LoadFromFileOrNew

func LoadFromFileOrNew(filePath string, maxBytes int) *Cache

LoadFromFileOrNew tries loading cache data from the given filePath.

The function falls back to creating new cache with the given maxBytes capacity if error occurs during loading the cache from file.

func New

func New(maxBytes int) *Cache

New returns new cache with the given maxBytes capacity in bytes.

maxBytes must be smaller than the available RAM size for the app, since the cache holds data in memory.

If maxBytes is less than 16MB, then the minimum cache capacity is 16MB.

func (*Cache) Del

func (c *Cache) Del(k []byte)

Del deletes value for the given k from the cache.

k contents may be modified after returning from Del.

func (*Cache) Get

func (c *Cache) Get(dst, k []byte) []byte

Get appends value by the key k to dst and returns the result.

Get allocates new byte slice for the returned value if dst is nil.

k contents may be modified after returning from Get.

func (*Cache) Reset

func (c *Cache) Reset()

Reset removes all the items from the cache.

func (*Cache) SaveToFile

func (c *Cache) SaveToFile(filePath string) error

SaveToFile atomically saves cache data to the given filePath.

SaveToFile may be called concurrently with other operations on the cache.

func (*Cache) Set

func (c *Cache) Set(k, v []byte)

Set stores (k, v) in the cache.

The stored entry may be evicted at any time either due to cache overflow or due to unlikely hash collision. Pass higher maxBytes value to New if the added items disappear frequently.

(k, v) entries with summary size exceeding 64KB aren't stored in the cache.

k and v contents may be modified after returning from Set.

func (*Cache) UpdateStats

func (c *Cache) UpdateStats(s *Stats)

UpdateStats adds cache stats to s.

type Stats

type Stats struct {
	// GetCalls is the number of Get calls.
	GetCalls uint64

	// SetCalls is the number of Set calls.
	SetCalls uint64

	// Misses is the number of cache misses.
	Misses uint64

	// Collisions is the number of cache collisions.
	Collisions uint64

	// EntriesCount is the current number of entries in the cache.
	EntriesCount uint64

	// BytesSize is the current size of the cache in bytes.
	BytesSize uint64
}

Stats represents cache stats.

Use Cache.UpdateStats for obtaining fresh stats from the cache.