I once came across the fact that none of the Golang cache libraries are truly contention-free. All of them are just a standard map with mutex and some eviction policy. Unfortunately, these are not able to reach the speed of caches in other languages (such as Caffeine). For example, the fastest cache from Dgraph labs called Ristretto, which was faster than competitors by 30% at best (Otter is many times faster) and had a disgusting hit ratio even though README says otherwise. This can be a problem in different applications because no one wants to bump the performance of a cache library and its bad hit ratio π. As a result, I wanted to get the fastest, easiest-to-use cache with excellent hit ratio and support from the authors and Otter is designed to correct this unfortunate misunderstanding.
Please leave a β as motivation if you liked the idea π
Otter is based on the following papers:
- BP-Wrapper: A Framework Making Any Replacement Algorithms (Almost) Lock Contention Free
- FIFO queues are all you need for cache eviction
- Bucket-Based Expiration Algorithm: Improving Eviction Efficiency for In-Memory Key-Value Database
- A large scale analysis of hundreds of in-memory cache clusters at Twitter
This library has lots of features such as:
- Simple API: Just set the parameters you want in the builder and enjoy
- Autoconfiguration: Otter is automatically configured based on the parallelism of your application
- Generics: You can safely use any comparable types as keys and any types as values
- TTL: Expired values will be automatically deleted from the cache
- Cost-based eviction: Otter supports eviction based on the cost of each item
- Excellent performance: Otter is currently the fastest cache library with a huge lead over the competition
- Great hit ratio: New S3-FIFO algorithm is used, which shows excellent results
- Go 1.18+
go get -u github.com/maypok86/otter
Builder
Otter uses a builder pattern that allows you to conveniently create a cache object with different parameters
package main
import (
"github.com/maypok86/otter"
)
func main() {
// NewBuilder creates a builder and sets the future cache capacity to 1000 elements.
// Returns an error if capacity <= 0.
builder, err := otter.NewBuilder[string, string](1000)
if err != nil {
panic(err)
}
// StatsEnabled determines whether statistics should be calculated when the cache is running.
// By default, statistics calculating is disabled.
builder.StatsEnabled(true)
// Cost sets a function to dynamically calculate the weight of a key-value pair.
// By default this function always returns 1.
builder.Cost(func(key string, value string) uint32 {
return uint32(len(value))
})
// Build creates a new cache object or
// returns an error if invalid parameters were passed to the builder.
cache, err := builder.Build()
if err != nil {
panic(err)
}
cache.Close()
}
Cache
package main
import (
"fmt"
"time"
"github.com/maypok86/otter"
)
func main() {
// create a cache with capacity equal to 10000 elements
cache, err := otter.MustBuilder[string, string](10_000).Build()
if err != nil {
panic(err)
}
// set key-value pair with ttl (1 hour)
cache.SetWithTTL("key", "value", time.Hour)
// get value from cache
value, ok := cache.Get("key")
if !ok {
panic("not found key")
}
fmt.Println(value)
// delete key-value pair from cache
cache.Delete("key")
// delete data and stop goroutines
cache.Close()
}
The benchmark code can be found here
Otter is pretty unstoppable on all workloads except write-heavy, but that's completely unrepresentative of the cache workload.
This trace is described as "disk read accesses initiated by a large commercial search engine in response to various web search requests."
This trace is described as "a database server running at a commercial site running an ERP application on top of a commercial database."
The trace P3 was collected from workstations running Windows NT by using Vtrace which captures disk operations through the use of device filters
The trace P8 was collected from workstations running Windows NT by using Vtrace which captures disk operations through the use of device filters
This trace demonstrates a looping access pattern.
This trace is described as "references to a CODASYL database for a one hour period."
In summary, we have that S3-FIFO (otter) is inferior to W-TinyLFU (theine) on lfu friendly workloads (databases, search, analytics), but has a greater or equal hit ratio on web workloads.
Contributions are welcome as always, before submitting a new PR please make sure to open a new issue so community members can discuss it. For more information please see contribution guidelines.
Additionally, you might find existing open issues which can help with improvements.
This project follows a standard code of conduct so that you can understand what actions will and will not be tolerated.
This project is Apache 2.0 licensed, as found in the LICENSE.