golang-fifo

This is a modern cache implementation, inspired by the following papers, provides high efficiency.

• SIEVE | SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches (NSDI'24)
• S3-FIFO | FIFO queues are all you need for cache eviction (SOSP'23)

This offers state-of-the-art efficiency and scalability compared to other LRU-based cache algorithms.

Basic Usage

import "github.com/scalalang2/golang-fifo/sieve"

size := 1e5
ttl := 0 // 0 means no expiration
cache := sieve.New[string, string](size, ttl)

// set value under hello
cache.Set("hello", "world")

// get value under hello
val, ok := cache.Get("hello")
if ok {
    fmt.Printf("value: %s", val) // => "world"
}

// set more keys
for i := 0; i < 10; i++ {
    cache.Set(fmt.Sprintf("key%d", i), fmt.Sprintf("value%d", i))
}

// get number of cache entries
fmt.Printf("len: %d", cache.Len()) // => 11

// remove value under hello
removed := cache.Remove("hello")
if removed {
    fmt.Println("hello was removed")
}

Expiry

import "github.com/scalalang2/golang-fifo/sieve"

size := 1e5
ttl := time.Second * 3600 // 1 hour
cache := sieve.New[string, string](size, ttl)

// this callback will be called when the element is expired
cahe.SetOnEvict(func(key string, value string) {
    fmt.Printf("key: %s, value: %s was evicted", key, value)
})

// set value under hello
cache.Set("hello", "world")

// remove all cache entries and stop the eviction goroutine.
cache.Close()

Benchmark Result

The benchmark result were obtained using go-cache-benchmark

itemSize=500000, workloads=7500000, cacheSize=0.10%, zipf's alpha=0.99, concurrency=16

      CACHE      | HITRATE |   QPS   |  HITS   | MISSES
-----------------+---------+---------+---------+----------
  sieve          | 47.66%  | 2508361 | 3574212 | 3925788
  tinylfu        | 47.37%  | 2269542 | 3552921 | 3947079
  s3-fifo        | 47.17%  | 1651619 | 3538121 | 3961879
  slru           | 46.49%  | 2201350 | 3486476 | 4013524
  s4lru          | 46.09%  | 2484266 | 3456682 | 4043318
  two-queue      | 45.49%  | 1713502 | 3411800 | 4088200
  clock          | 37.34%  | 2370417 | 2800750 | 4699250
  lru-groupcache | 36.59%  | 2206841 | 2743894 | 4756106
  lru-hashicorp  | 36.57%  | 2055358 | 2743000 | 4757000

SIEVE delivers both high hit rates and the highest QPS(queries per seconds) compared to other LRU-based caches. Additionally, It approximately improves 30% for efficiency than a simple LRU cache.

Increasing efficiency means not only reducing cache misses, but also reducing the demand for heavy operations such as backend database access, which lowers the mean latency.

While LRU promotes accessed objects to the head of the queue, requiring a potentially slow lock acquisition, SIEVE only needs to update a single bit upon a cache hit. This update can be done with a significantly faster reader lock, leading to increased performance.

The real-world traces are also evaluated at here

Appendix

Contribution

How to run unit test

$ go test -v ./...

How to run benchmark test

$ ./bench.sh