Badger: Introduce LRU cache in Badger

[manishrjain]

Could work at 2 levels:

• Cache SSTables in memory, based on frequent access. Though, that might just be the same effect as doing mmap over the tables.
• Cache values which lie in value log. This could be useful in that it can avoid disk seeks. We don't need to cache values which lie in the LSM tree, considering SSTables are already either in RAM or at least MMapped in most cases.

The question is which LRU cache to use. https://github.com/coocood/freecache , or https://github.com/allegro/bigcache seem promising. Or, maybe we write our own, similar to this one: http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html

[zhiqiangxu]

I think "Cache values which lie in value log" is the way to go:)

IMHO the most difficult point is to maintain data consistency when introducing cache.

[manishrjain]

From coocood/freecache:

$ go test -v --bench=. -run=XXX
goos: linux
goarch: amd64
pkg: github.com/coocood/freecache
BenchmarkCacheSet-32                     5000000           461 ns/op
BenchmarkMapSet-32                       2000000           644 ns/op
BenchmarkCacheGet-32                     5000000           484 ns/op
BenchmarkCacheGetWithExpiration-32       5000000           481 ns/op
BenchmarkMapGet-32                      10000000           197 ns/op
BenchmarkHashFunc-32                    200000000            6.87 ns/op
PASS
ok      github.com/coocood/freecache    27.415s

$ go test -v --bench=. -run=XXX
goos: linux
goarch: amd64
pkg: github.com/coocood/freecache
BenchmarkCacheSet-32                     5000000           427 ns/op
BenchmarkMapSet-32                       2000000           609 ns/op
BenchmarkCacheGet-32                     5000000           468 ns/op
BenchmarkCacheGetWithExpiration-32       5000000           471 ns/op
BenchmarkMapGet-32                      10000000           196 ns/op
BenchmarkHashFunc-32                    200000000            7.05 ns/op
PASS
ok      github.com/coocood/freecache    26.515s

But, only single thread benchmarking. Needs multi-thread benchmarking. See: https://github.com/coocood/freecache/issues/54

[alxarch]

Check out https://github.com/VictoriaMetrics/fastcache also

[mangalaman93]

We have considered Fastcache, it doesn't do well on hit ratios. Here are the raw results for benchmarks https://docs.google.com/spreadsheets/d/1c5AbsHPh-z6KyxkiBJ4ipNR7U7QVuSmR38fym8NeC50/edit?usp=sharing

[campoy]

Hi @mangalaman93,

Could you update this is issue? What's the current status?

[mangalaman93]

https://github.com/dgraph-io/ristretto work is in progress. Once it is complete, we should be able to add it to badger.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[anacrolix]

Any plans for this now that Ristretto is released?

[jarifibrahim]

@anacrolix We're working on adding ristretto to badger.

[danielmai]

Ristretto has been added to Badger with #1066 and released in Badger v2.0.0.