Show HN: Cachegrand – a fast OSS Key-Value store built for modern hardware

A bit from everything: the hashtable leverages the CPU caches and the cachelines, it also uses SIMD instructions to search very quickly the hash, once a bucket in the hashtable is identified, only the relevant bits in the hash are compared, on top of this there is the custom memory allocator, fibers and io_uring is of great help network side, etc.

The multithreading helps to scale the access to the hashtable vertically almost linearly.

The use of the fibers make everything easier because cachegrand doesn't have multiple threads running on the same core fighting for the same resources.

On top of this (and thanks to not having multiple threads fighting for the same resources on the same core), the hashtable uses user-space spinlocks (that are "fake" spinlocks as they can't prevent the kernel to preemept, although there are ways to do it) and the "contention" is spread all across the hashtable. The spinlocks though are only used to change the hashtable (with UPSERT, DEL and Read-Modify-Write operations), they are not required to read from it.

Let's say that thread A, B and C, want to access key1, key2 and key3.

If you an hashtable of 10000 buckets, cachegrand will basically split it in chunks of 14 elements and each chunk will have its own localized lock, so there will be about 714 different possible locks. In general, unless you are writing always to the same key, the writes will be distribuited across all the hashtable hitting different locks so it will not be necessary to wait.

Of course I considered different approches a few years ago when I was researching the hashtable including sharding it across multiple threads and let a thread own a slice of it but decided not to go down this way because instead of having 714 locks, like the case above, you will need to use queues to pass messages between the threads (a bit like Scala does) and "focus" the contention on limited number of memory areas (e.g. if you have 4 threads you will have 4 queues and focus the contention on these 4 queues which is bad). Of course you can use atomic operations to push and pop elements from these queues but it will not be able to scale up as the contention will make this system tremble under heavy load.

cachegrand, thanks to the localized spinlocks, can hit 60 million GET and 27 million SET per second on hardware used for benchmarking.

Yes, I was planning to bring it in after a few releases and focus on more commands right now but I was asked to make it more production ready so the next release I will bring in: - Active-Active replication - memory control (with key eviction using an LRU) - RDB load & save (or at least RDB load) - the ability to run cachegrand as slave of a simple redis cluster (e.g. sharded but active-passive replication), so will be possible to introduce cachegrand slowly and test it out without impacting a whole deployment.

I don't understand this comment in relation to your previous one at all, then.

You said:

Redis can easily chew 200k GET RPS on an average low-core count VM, even if an application does 10 Redis queries per request in average it would still take 20k requests to saturate it... which is an HUGE amount if we think that this would require easily between 50 and 100 machines beefy machines!

Which says you estimate 50-100 machines to saturate one "low-core count VM" Redis. But now you say you meant 50-100 machines for Redis servers?

We run about 20 machines, perhaps the equivalent of 10 "beefy machines", to handle a ~50k/sec request load (with substantially higher peaks). We have less than 100 servers total, most of which are doing asynchronous data processing and not directly in the request pipeline. Our data storage architecture is not really comparable to redis in terms of request load as it's insert/upsert-dominated but the total size is 5-10TB.

It is early stage in the sense it only support commands that operate on the strings and some on the key space.

Other commands are planned to be added soon but the ones already implemented cover already a lot of different use cases.

DragonflyDB is not open source, unfortunately.