Ristretto - A high performance memory-bound Go cache

Related tags

Caching golang cache
Overview

Ristretto

Go Doc Go Report Card Coverage Tests

Ristretto is a fast, concurrent cache library built with a focus on performance and correctness.

The motivation to build Ristretto comes from the need for a contention-free cache.

Use outcaste-io/issues repository to file issues for Ristretto.

Features

  • High Hit Ratios - with our unique admission/eviction policy pairing, Ristretto's performance is best in class.
    • Eviction: SampledLFU - on par with exact LRU and better performance on Search and Database traces.
    • Admission: TinyLFU - extra performance with little memory overhead (12 bits per counter).
  • Fast Throughput - we use a variety of techniques for managing contention and the result is excellent throughput.
  • Cost-Based Eviction - any large new item deemed valuable can evict multiple smaller items (cost could be anything).
  • Fully Concurrent - you can use as many goroutines as you want with little throughput degradation.
  • Metrics - optional performance metrics for throughput, hit ratios, and other stats.
  • Simple API - just figure out your ideal Config values and you're off and running.

Status

Ristretto is production-ready. See Projects using Ristretto.

Table of Contents

Usage

Example

func main() {
	cache, err := ristretto.NewCache(&ristretto.Config{
		NumCounters: 1e7,     // number of keys to track frequency of (10M).
		MaxCost:     1 << 30, // maximum cost of cache (1GB).
		BufferItems: 64,      // number of keys per Get buffer.
	})
	if err != nil {
		panic(err)
	}

	// set a value with a cost of 1
	cache.Set("key", "value", 1)

	// wait for value to pass through buffers
	cache.Wait()

	value, found := cache.Get("key")
	if !found {
		panic("missing value")
	}
	fmt.Println(value)
	cache.Del("key")
}

Config

The Config struct is passed to NewCache when creating Ristretto instances (see the example above).

NumCounters int64

NumCounters is the number of 4-bit access counters to keep for admission and eviction. We've seen good performance in setting this to 10x the number of items you expect to keep in the cache when full.

For example, if you expect each item to have a cost of 1 and MaxCost is 100, set NumCounters to 1,000. Or, if you use variable cost values but expect the cache to hold around 10,000 items when full, set NumCounters to 100,000. The important thing is the number of unique items in the full cache, not necessarily the MaxCost value.

MaxCost int64

MaxCost is how eviction decisions are made. For example, if MaxCost is 100 and a new item with a cost of 1 increases total cache cost to 101, 1 item will be evicted.

MaxCost can also be used to denote the max size in bytes. For example, if MaxCost is 1,000,000 (1MB) and the cache is full with 1,000 1KB items, a new item (that's accepted) would cause 5 1KB items to be evicted.

MaxCost could be anything as long as it matches how you're using the cost values when calling Set.

BufferItems int64

BufferItems is the size of the Get buffers. The best value we've found for this is 64.

If for some reason you see Get performance decreasing with lots of contention (you shouldn't), try increasing this value in increments of 64. This is a fine-tuning mechanism and you probably won't have to touch this.

Metrics bool

Metrics is true when you want real-time logging of a variety of stats. The reason this is a Config flag is because there's a 10% throughput performance overhead.

OnEvict func(hashes [2]uint64, value interface{}, cost int64)

OnEvict is called for every eviction.

KeyToHash func(key interface{}) [2]uint64

KeyToHash is the hashing algorithm used for every key. If this is nil, Ristretto has a variety of defaults depending on the underlying interface type.

Note that if you want 128bit hashes you should use the full [2]uint64, otherwise just fill the uint64 at the 0 position and it will behave like any 64bit hash.

Cost func(value interface{}) int64

Cost is an optional function you can pass to the Config in order to evaluate item cost at runtime, and only for the Set calls that aren't dropped (this is useful if calculating item cost is particularly expensive and you don't want to waste time on items that will be dropped anyways).

To signal to Ristretto that you'd like to use this Cost function:

  1. Set the Cost field to a non-nil function.
  2. When calling Set for new items or item updates, use a cost of 0.

Benchmarks

The benchmarks can be found in https://github.com/dgraph-io/benchmarks/tree/master/cachebench/ristretto.

Hit Ratios

Search

This trace is described as "disk read accesses initiated by a large commercial search engine in response to various web search requests."

Database

This trace is described as "a database server running at a commercial site running an ERP application on top of a commercial database."

Looping

This trace demonstrates a looping access pattern.

CODASYL

This trace is described as "references to a CODASYL database for a one hour period."

Throughput

All throughput benchmarks were ran on an Intel Core i7-8700K (3.7GHz) with 16gb of RAM.

Mixed

Read

Write

Projects Using Ristretto

Below is a list of known projects that use Ristretto:

  • Badger - Embeddable key-value DB in Go
  • Dgraph - Horizontally scalable and distributed GraphQL database with a graph backend
  • Vitess - Database clustering system for horizontal scaling of MySQL
  • SpiceDB - Horizontally scalable permissions database

FAQ

How are you achieving this performance? What shortcuts are you taking?

We go into detail in the Ristretto blog post, but in short: our throughput performance can be attributed to a mix of batching and eventual consistency. Our hit ratio performance is mostly due to an excellent admission policy and SampledLFU eviction policy.

As for "shortcuts," the only thing Ristretto does that could be construed as one is dropping some Set calls. That means a Set call for a new item (updates are guaranteed) isn't guaranteed to make it into the cache. The new item could be dropped at two points: when passing through the Set buffer or when passing through the admission policy. However, this doesn't affect hit ratios much at all as we expect the most popular items to be Set multiple times and eventually make it in the cache.

Is Ristretto distributed?

No, it's just like any other Go library that you can import into your project and use in a single process.

You might also like...
Cachy is a simple and lightweight in-memory cache api.
Cachy is a simple and lightweight in-memory cache api.

cachy Table of Contents cachy Table of Contents Description Features Structure Configurability settings.json default values for backup_file_path Run o

A REST-API service that works as an in memory key-value store with go-minimal-cache library.

A REST-API service that works as an in memory key-value store with go-minimal-cache library.

An in-memory key:value store/cache library written in Go 1.18 generics

go-generics-cache go-generics-cache is an in-memory key:value store/cache that is suitable for applications running on a single machine. This in-memor

Gocodecache - An in-memory cache library for code value master in Golang

gocodecache An in-memory cache library for code master in Golang. Installation g

A zero-dependency cache library for storing data in memory with generics.

Memory Cache A zero-dependency cache library for storing data in memory with generics. Requirements Golang 1.18+ Installation go get -u github.com/rod

LevelDB style LRU cache for Go, support non GC object.

Go语言QQ群: 102319854, 1055927514 凹语言(凹读音“Wa”)(The Wa Programming Language): https://github.com/wa-lang/wa LRU Cache Install go get github.com/chai2010/c

groupcache is a caching and cache-filling library, intended as a replacement for memcached in many cases.

groupcache Summary groupcache is a distributed caching and cache-filling library, intended as a replacement for a pool of memcached nodes in many case

☔️ A complete Go cache library that brings you multiple ways of managing your caches
☔️ A complete Go cache library that brings you multiple ways of managing your caches

Gocache Guess what is Gocache? a Go cache library. This is an extendable cache library that brings you a lot of features for caching data. Overview He

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

Fast thread-safe inmemory cache for big number of entries in Go. Minimizes GC overhead

Comments
  • Release a new version

    Release a new version

    Hi, could you release a new version? I want to use a new version that includes https://github.com/dgraph-io/ristretto/pull/281 which already includes in your repo.

    opened by atlas-comstock 12
  • fix: use atomic in the cache

    fix: use atomic in the cache

    Signed-off-by: Weizhen Wang [email protected]

    we find the data race in the cache of ristretto when to test our cases.

    ==================
    WARNING: DATA RACE
    Write at 0x00c002c1a0d8 by goroutine 99:
      github.com/dgraph-io/ristretto.(*Cache).Close()
          /home/prow/go/pkg/mod/github.com/dgraph-io/[email protected]/cache.go:363 +0xe4
      github.com/pingcap/tidb/store/copr.(*Store).Close()
          /go/tidb/store/copr/store.go:97 +0x91
      github.com/pingcap/tidb/store/mockstore/mockstorage.(*mockStorage).Close()
          /go/tidb/store/mockstore/mockstorage/storage.go:116 +0x27
      github.com/pingcap/tidb/testkit.bootstrap.func1()
          /go/tidb/testkit/mockstore.go:57 +0x68
      runtime.deferreturn()
          /usr/local/go/src/runtime/panic.go:436 +0x32
      github.com/pingcap/failpoint.parseTerm()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/terms.go:149 +0x377
      github.com/pingcap/failpoint.parse()
          /home/prow/go/pkg/mod/github.com/pingcap/failpoint[email protected]/terms.go:126 +0xa8
      github.com/pingcap/failpoint.newTerms()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/terms.go:98 +0x50
      github.com/pingcap/failpoint.(*Failpoint).Enable()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/failpoint.go:54 +0x44
      github.com/pingcap/failpoint.(*Failpoints).Enable()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/failpoints.go:105 +0x276
      github.com/pingcap/failpoint.Enable()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/failpoints.go:225 +0x14f
      github.com/pingcap/tidb/executor/seqtest_test.TestParallelHashAggClose()
          /go/tidb/executor/seqtest/seq_executor_test.go:711 +0x150
      testing.tRunner()
          /usr/local/go/src/testing/testing.go:1439 +0x213
      testing.(*T).Run.func1()
          /usr/local/go/src/testing/testing.go:1486 +0x47
    Previous read at 0x00c002c1a0d8 by goroutine 7:
      github.com/dgraph-io/ristretto.(*Cache).Get()
          /home/prow/go/pkg/mod/github.com/dgraph-io/[email protected]/cache.go:225 +0x4a
      github.com/pingcap/tidb/store/copr.(*coprCache).Get()
          /go/tidb/store/copr/coprocessor_cache.go:152 +0x84
      github.com/pingcap/tidb/store/copr.(*copIteratorWorker).handleTaskOnce()
          /go/tidb/store/copr/coprocessor.go:724 +0x744
      github.com/pingcap/tidb/store/copr.(*copIteratorWorker).handleTask()
          /go/tidb/store/copr/coprocessor.go:676 +0x1e5
      github.com/pingcap/tidb/store/copr.(*copIteratorWorker).run()
          /go/tidb/store/copr/coprocessor.go:418 +0x173
      github.com/pingcap/tidb/store/copr.(*copIterator).open.func1()
          /go/tidb/store/copr/coprocessor.go:450 +0x58
    Goroutine 99 (running) created at:
      testing.(*T).Run()
          /usr/local/go/src/testing/testing.go:1486 +0x724
      testing.runTests.func1()
          /usr/local/go/src/testing/testing.go:1839 +0x99
      testing.tRunner()
          /usr/local/go/src/testing/testing.go:1439 +0x213
      testing.runTests()
          /usr/local/go/src/testing/testing.go:1837 +0x7e4
      testing.(*M).Run()
          /usr/local/go/src/testing/testing.go:1719 +0xa71
      go.uber.org/goleak.VerifyTestMain()
          /home/prow/go/pkg/mod/go.uber.org/[email protected]/testmain.go:53 +0x59
      github.com/pingcap/tidb/executor/seqtest.TestMain()
          /go/tidb/executor/seqtest/main_test.go:37 +0x430
      main.main()
          _testmain.go:125 +0x317
    Goroutine 7 (finished) created at:
      github.com/pingcap/tidb/store/copr.(*copIterator).open()
          /go/tidb/store/copr/coprocessor.go:450 +0xc4
      github.com/pingcap/tidb/store/copr.(*CopClient).Send()
          /go/tidb/store/copr/coprocessor.go:143 +0x10c9
      github.com/pingcap/tidb/distsql.Select()
          /go/tidb/distsql/distsql.go:101 +0x8c3
      github.com/pingcap/tidb/distsql.SelectWithRuntimeStats()
          /go/tidb/distsql/distsql.go:150 +0xbb
      github.com/pingcap/tidb/executor.selectResultHook.SelectResult()
          /go/tidb/executor/table_reader.go:53 +0x1c5
      github.com/pingcap/tidb/executor.(*TableReaderExecutor).buildResp()
          /go/tidb/executor/table_reader.go:310 +0x69d
      github.com/pingcap/tidb/executor.(*TableReaderExecutor).Open()
          /go/tidb/executor/table_reader.go:210 +0x13f5
      github.com/pingcap/tidb/executor.(*baseExecutor).Open()
          /go/tidb/executor/executor.go:185 +0x6a9
      github.com/pingcap/tidb/executor.(*HashAggExec).Open()
          /go/tidb/executor/aggregate.go:309 +0xe6
      github.com/pingcap/tidb/executor.(*ExecStmt).Exec()
          /go/tidb/executor/adapter.go:407 +0x7f8
      github.com/pingcap/tidb/session.runStmt()
          /go/tidb/session/session.go:2017 +0x6cb
      github.com/pingcap/tidb/session.(*session).ExecuteStmt()
          /go/tidb/session/session.go:1894 +0xd3a
      github.com/pingcap/tidb/session.(*session).Execute()
          /go/tidb/session/session.go:1534 +0x478
      github.com/pingcap/tidb/executor/seqtest_test.TestParallelHashAggClose()
          /go/tidb/executor/seqtest/seq_executor_test.go:716 +0x21b
      github.com/pingcap/failpoint.parseTerm()
          /home/prow/go/pkg/mod/github.com/pingcap/fa[email protected]/terms.go:149 +0x377
      github.com/pingcap/failpoint.parse()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/terms.go:126 +0xa8
      github.com/pingcap/failpoint.newTerms()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/terms.go:98 +0x50
      github.com/pingcap/failpoint.(*Failpoint).Enable()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/failpoint.go:54 +0x44
      github.com/pingcap/failpoint.(*Failpoints).Enable()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/failpoints.go:105 +0x276
      github.com/pingcap/failpoint.Enable()
          /home/prow/go/pkg/mod/github.com/pingcap/[email protected]/failpoints.go:225 +0x14f
      github.com/pingcap/tidb/executor/seqtest_test.TestParallelHashAggClose()
          /go/tidb/executor/seqtest/seq_executor_test.go:711 +0x150
      testing.tRunner()
          /usr/local/go/src/testing/testing.go:1439 +0x213
      testing.(*T).Run.func1()
          /usr/local/go/src/testing/testing.go:1486 +0x47
    ================== 
    
    

    ref https://github.com/pingcap/tidb/issues/33649


    This change is Reviewable

    bug 
    opened by hawkingrei 3
  • Add a test to ensure that calling Set after Close does not panic

    Add a test to ensure that calling Set after Close does not panic

    On a previous version of ristretto, we experienced a panic occasionally due to calling Set after Close resulting in a write to the closed setBuf channel. We originally wrote this test as part of a fix on a forked version of Ristretto. Thankfully, on HEAD, this test is no longer failing, so we are submitting it to act as a guard against any regressions in the future.

    NOTE: The update to golang.org/x/sys also fixes a build issue with Golang 1.18 on Darwin


    This change is Reviewable

    opened by josephschorr 2
  • z,contrib: remove github.com/golang/glog

    z,contrib: remove github.com/golang/glog

    Currently ristretto depends on glog. The problem with glog is that it defines global flags, which is not a nice behavior for libraries.

    The code called glog.Fatal, which can be replaced with a regular panic.


    This change is Reviewable

    opened by egonelbre 1
Owner
Outcaste, Inc.
Outcaste, Inc.
Ristretto - A fast, concurrent cache library built with a focus on performance and correctness

Ristretto Ristretto is a fast, concurrent cache library built with a focus on pe

Koichi Shiraishi 2 Aug 21, 2022
cyhone 144 Nov 25, 2022
🦉owlcache is a lightweight, high-performance, non-centralized, distributed Key/Value memory-cached data sharing application written by Go

??owlcache is a lightweight, high-performance, non-centralized, distributed Key/Value memory-cached data sharing application written by Go . keyword : golang cache、go cache、golang nosql

d4rkdu0 859 Nov 5, 2022
Cache library for golang. It supports expirable Cache, LFU, LRU and ARC.

GCache Cache library for golang. It supports expirable Cache, LFU, LRU and ARC. Features Supports expirable Cache, LFU, LRU and ARC. Goroutine safe. S

Jun Kimura 2.2k Nov 18, 2022
Package cache is a middleware that provides the cache management for Flamego.

cache Package cache is a middleware that provides the cache management for Flamego. Installation The minimum requirement of Go is 1.16. go get github.

Flamego 11 Nov 9, 2022
A mem cache base on other populator cache, add following feacture

memcache a mem cache base on other populator cache, add following feacture add lazy load(using expired data, and load it asynchronous) add singlefligh

zhq 1 Oct 28, 2021
Cache - A simple cache implementation

Cache A simple cache implementation LRU Cache An in memory cache implementation

Stanislav Petrashov 1 Jan 25, 2022
Gin-cache - Gin cache middleware with golang

Gin-cache - Gin cache middleware with golang

Anson 38 Mar 16, 2022
An in-memory cache library for golang. It supports multiple eviction policies: LRU, LFU, ARC

GCache Cache library for golang. It supports expirable Cache, LFU, LRU and ARC. Features Supports expirable Cache, LFU, LRU and ARC. Goroutine safe. S

Jun Kimura 318 May 31, 2021
An in-memory key:value store/cache (similar to Memcached) library for Go, suitable for single-machine applications.

go-cache go-cache is an in-memory key:value store/cache similar to memcached that is suitable for applications running on a single machine. Its major

Patrick Mylund Nielsen 6.7k Nov 28, 2022