https://github.com/maypok86/otter Skip to content Toggle navigation Sign in * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Resources + Learning Pathways + White papers, Ebooks, Webinars + Customer Stories + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} maypok86 / otter Public * Notifications * Fork 4 * Star 311 Fastest golang in-memory cache library based on S3-FIFO algorithm. many times faster than Ristretto and friends License Apache-2.0 license 311 stars 4 forks Activity Star Notifications * Code * Issues 1 * Pull requests 0 * Actions * Projects 0 * Security * Insights Additional navigation options * Code * Issues * Pull requests * Actions * Projects * Security * Insights maypok86/otter This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. main Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 3 branches 0 tags Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/m] Use Git or checkout with SVN using the web URL. [gh repo clone maypok] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @maypok86 maypok86 [Chore] Update throughput benchmark results ... a9479c8 Dec 22, 2023 [Chore] Update throughput benchmark results a9479c8 Git stats * 55 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .github Bump github/codeql-action from 2 to 3 December 14, 2023 11:06 assets [Chore] Update throughput benchmark results December 22, 2023 17:30 internal [Chore] Use TTAS spinlock instead of TAS December 22, 2023 16:46 scripts [Chore]: Add project template September 13, 2023 23:24 .gitignore [Chore] Rewrite project October 22, 2023 20:42 .golangci.yml [#23] Use spinlock instead of mutex to synchronize nodes December 15, 2023 23:53 CODE_OF_CONDUCT.md [Chore]: Add project template September 13, 2023 23:24 CONTRIBUTING.md [Chore]: Add project template September 13, 2023 23:24 LICENSE [Chore]: Add project template September 13, 2023 23:24 Makefile [Chore] Add policy cost synchronization December 16, 2023 20:39 README.md [Chore] Update throughput benchmark results December 22, 2023 17:30 builder.go [Chore] Use only one shard December 8, 2023 01:20 builder_test.go [Chore] Use only one shard December 8, 2023 01:20 cache.go [Chore] Add lock to retrieve value from node December 17, 2023 22:04 cache_test.go [Chore] Add tests for expiration policy December 17, 2023 00:54 go.mod [#19] Implement queues based on double-linked lists December 15, 2023 22:42 go.sum [#19] Implement queues based on double-linked lists December 15, 2023 22:42 View code [ ] High performance in-memory cache Contents Motivation Related works Features Usage Requirements [?] Installation [?] Examples Benchmarks Performance Read (100%) Read (75%) / Write (25%) Write (100%) Hit ratio Zipf S3 DS1 P3 P8 LOOP OLTP Contribute License README.md [logo] High performance in-memory cache [badge] [6874747073] [6874747073] [6874747073] Contents * Motivation * Related works * Features * Usage + Requirements + Installation + Examples * Benchmarks + Performance + Hit ratio * Contribute * License Motivation 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 Related works 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 Features 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 Usage Requirements * Go 1.18+ [?] Installation go get -u github.com/maypok86/otter [?] Examples 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() } Benchmarks The benchmark code can be found here Performance Read (100%) reads=100%,writes=0% Read (75%) / Write (25%) reads=75%,writes=25% Write (100%) reads=0%,writes=100% Hit ratio Zipf zipf S3 This trace is described as "disk read accesses initiated by a large commercial search engine in response to various web search requests." s3 DS1 This trace is described as "a database server running at a commercial site running an ERP application on top of a commercial database." ds1 P3 The trace P3 was collected from workstations running Windows NT by using Vtrace which captures disk operations through the use of device filters p3 P8 The trace P8 was collected from workstations running Windows NT by using Vtrace which captures disk operations through the use of device filters p8 LOOP This trace demonstrates a looping access pattern. loop OLTP This trace is described as "references to a CODASYL database for a one hour period." oltp In summary, we have that S3-FIFO (otter) is inferior to W-TinyLFU (theine) on lfu friendly traces (databases, search, analytics), but has a greater or equal hit ratio on web traces. Contribute 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. License This project is Apache 2.0 licensed, as found in the LICENSE. About Fastest golang in-memory cache library based on S3-FIFO algorithm. many times faster than Ristretto and friends Topics go cache perfomance s3-fifo Resources Readme License Apache-2.0 license Code of conduct Code of conduct Activity Stars 311 stars Watchers 4 watching Forks 4 forks Report repository Releases No releases published Packages 0 No packages published Contributors 2 * @maypok86 maypok86 Alexey Mayshev * @dependabot[bot] dependabot[bot] Languages * Go 97.6% * Makefile 1.7% * Shell 0.7% Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact * Manage cookies * Do not share my personal information You can't perform that action at this time.