scalalang2/golang-fifo

Modern efficient cache design with simple FIFO queue only in Golang

$ whoami?

• 💻 A software engineer.
• 🛠️ Loves to find problems, and solves it.
• 🎮 Plays Honkai: Star Rail, Genshin Impacts and The Finals.

Projects

• golang-fifo : An implementation of SIEVE and S3-FIFO cache eviction algorithm in golang.
• protoc-gen-unreal-engine : A protobuf compiler used to generate UE5 compatible C++ and Blueprint codes.
• cosmscan-rs : An indexer engine for cosmos based blockchain (rust).
• cosmfaucet : Multi-chain faucet for cosmos based blockchains.

Hobbies

• pyflink-playgound : The playground for PyFlink written with Helm chart.
• C# by examples : A collection of examples that help developers to start writing their own program in one day.

Profiles

• baekjoon | scalalang
• atcoder | scalalang
• hoyolab | scalalang2

Publishment

• Medium

golang-fifo's Issues

[FEATURE] Lock-free implementation

Motivation

As mentioned in paper, It can be possible to be implemented with lock-free queue.

S3-FIFO is also more scalable because FIFO queues enable lock-free implementations. We implemented a prototype in Cachelib and show that S3-FIFO achieves more than 6× higher throughput than the highly-optimized LRU implementation on 16 cores. Compared to advanced eviction algorithms such as 2Q and TinyLFU, the throughput gap is further enlarged.

I think that implementing lock-free algorithms is quite complex requiring long-term commitment.

Add concurrent test & make coverage to be greater than 90 percent

Motivation

Add concurrent unit test codes to avoid race conditions

Ref.

#21

Bump up Go version to `1.22`

Go 1.22 is released !

Add a test code for SIEVE.

Add CI pipeline

Motivation

• Run build and unit tests when a pull request submitted and the code updated on main branch

Feedback on a statement

This is awesome work!

One suggestion on the result. It mentions that "SIEVE is about 10% more efficient than a simple LRU cache", which I think is not very accurate.
When comparing the miss ratio, we usually state relative numbers. For example, reducing the mass ratio from 2% to 1% is a (2-1)/2=50% improvement because the backend load is reduced by 50%. Moreover, the mean latency is about proportional to the mass ratio and has a similar reduction. :)

BTW, do you have results for S3-FIFO as well?

Update the benchmark result.

Motivation

There has been a lot changes to golang-fifo library.
I expect that the QPS might have been decreased.

[FEATURE] Implement expirable SIEVE & S3-FIFO.

Motivation

hashicorp/golang-lru has implemented expirable LRU which discards entries exceeding specific durations.

I think that golang-fifo also need to implement expirable version of SIEVE and S3-FIFO

Replace built-in hash map to `Swiss Table`

Motivation

This suggests evaluating the performance of the Swiss Table data structure against built-in hash table.

• You can find the idea behind the swiss table here
• The go version of it is implemented by cockroachdb team

Implementation of the `ShardedCache`

Motivation

refer : elastic/go-freelru

They provides ShardedLRU which provides sharded, concurrency-safe implementation but it uses an approximate LRU algorithm.

[FEATURE] Non-generic optimized cache algorithm

Motivation

Large map with a pointer-typed value occurs non-trivial GC overhead. see here
We can make a cache algorithm optimized for GC by referring to bigcache

To achieve that, I think, it should be non-generic and handle only []byte type.

Action

• Create a new package optimized
  • I'm not good at naming, if you have any suggestions on it, please leave a comment
• Put a GC-optimized SIEVE and S3-FIFO codes under optimized

Proper implementation of bucket table.

Motivation

At that time of writing S3-FIFO algorithm, I didn't deep dive into the bucket table implementation.
Therefore Its implementation may look different from actual bucket table and may not work properly.

Improve worst-case time complexity.

Motivation

the S3-FIFO and SIEVE both have O(N) of worst-case time-complexity.
There are many discussion around here to improve this.

refer. https://discuss.systems/@tobinbaker/111660148137611847

Data race?

My test suite caught this:

Write at 0x00c02f86dee0 by goroutine 3037:
  github.com/scalalang2/golang-fifo/sieve.(*Sieve[go.shape.struct { BucketURL string; FileName string; Offset int; Length int },go.shape.interface { GoAsync(func() (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error)); GoSync(func() (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error)); IsDone() bool; Reject(error); Resolve(github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue]); ResolveOrReject(github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error); Wait() (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error); WaitCtx(context.Context) (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error) }]).Get()
      /home/runner/go/pkg/mod/github.com/scalalang2/[email protected]/sieve/sieve.go:54 +0x1de
...


Previous write at 0x00c02f86dee0 by goroutine 3007:
  github.com/scalalang2/golang-fifo/sieve.(*Sieve[go.shape.struct { BucketURL string; FileName string; Offset int; Length int },go.shape.interface { GoAsync(func() (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error)); GoSync(func() (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error)); IsDone() bool; Reject(error); Resolve(github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue]); ResolveOrReject(github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error); Wait() (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error); WaitCtx(context.Context) (github.com/warpstreamlabs/warpstream/pkg/cache.TWrapper[github.com/warpstreamlabs/warpstream/pkg/filecache.FooterCacheValue], error) }]).Get()
      /home/runner/go/pkg/mod/github.com/scalalang2/[email protected]/sieve/sieve.go:54 +0x1de

func (s *Sieve[K, V]) Get(key K) (value V, ok bool) {
	s.lock.RLock()
	defer s.lock.RUnlock()
	if e, ok := s.items[key]; ok {
		e.Value.(*entry[K, V]).visited = true
		return e.Value.(*entry[K, V]).value, true
	}

	return
}

Looks like concurrent writes while holding an RLock?

[ENHANCEMENT] Enhance performance

Motivation

Let's explore a way to enhance the performance of this implementation 🤔

not an issue, just a thanks

Hi! Just wanted to drop a "thank you" here for putting this repo up :) It was helpful to understand S3-FIFO and SIEVE. I'm not using Go for any projects, but Go is easy to understand the algorithms and easy to translate into other languages. Thank you!!