8 ms·

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

121 points by daniele_dll 4y ago

I am the author of the platform, happy to reply to any question you might have! It scales up really nicely thanks to a year of research and development of the hashtable implemented in cachegrand, on the hardware used for benchmarking, an AMD EPYC 7502P, it was able to reach up to 5mln GET QPS and 4.5mln SET QPS, with batching up to 60mln GET QPS and up to 26MLN SET QPS. cachegrand is fast, it's fully Open Source, it's under a BSD 3-clause license - it can be used easily as standalone platform or incorporated in other ones without any licensing issue - and we are working to expand the Redis functionalities supported and to impelement a tiered storage to cache more data than the available memory. Longer term our goal is to expand the support to different platforms (e.g. memcache, kafka, etc.), add support to webassembly to have user defined functions and server side events, and of course a network bypass (combining XDP and a lockless FreeBSD tcp/ip stack) and a storage bypass. Although it can easily used via docker, here a direct link to the latest release https://github.com/danielealbano/cachegrand/releases/tag/v0.1.4 https://github.com/danielealbano/cachegrand/releases/tag/v0.... Currently we are focused on supporting Redis, here the list of commands currently implemented https://github.com/danielealbano/cachegrand/blob/main/docs/architecture/modules/redis.md https://github.com/danielealbano/cachegrand/blob/main/docs/a...

gpderetta 4y ago
The uncommon name and edit-distance of 1 from cachegrind tripped me up for a few moments.
- junon 4y ago
  Same, I thought Cachegrind added some new feature or something. Was thoroughly confused until I read the comments.
- daniele_dll 4y ago
  ahahahahha, that's definitely true, quite similar to Valgrind tooling :D
- cozzyd 4y ago
  Yes, though a cachegrind profile would be nice to show...
nerpderp82 4y ago
The benchmarks should be against Aerospike or something similar not Redis, as it cooks the results vs what is the current highest performant OSS KV store.
- otabdeveloper4 4y ago
  Aerospike will happily ignore your requests if it feels like. Use it only if you don't care about correctness or losing data.
  - nvartolomei 4y ago
    “In hundreds of tests of SC mode through network partitions, 3.99.1.5 and higher versions have not shown any sign of nonlinearizable histories, lost increments to counters, or lost updates to sets.” – Kyle Kingsbury, Aerospike 3.99.0.3, 12-27-2017 - https://aerospike.com/blog/aerospike-4-strong-consistency-and-jepsen/ https://aerospike.com/blog/aerospike-4-strong-consistency-an... - https://jepsen.io/analyses/aerospike-3-99-0-3 https://jepsen.io/analyses/aerospike-3-99-0-3
    - otabdeveloper4 4y ago
      Good for them. We got rid of Aerospike because using it in the "right" way to get data in and out correctly is a pain in the ass and makes everything slow.
- nvartolomei 4y ago
  Or against https://github.com/dragonflydb/dragonfly https://github.com/dragonflydb/dragonfly.
  - justinholmes 4y ago
    We posted benchmarks https://www.linkedin.com/posts/danielesalvatorealbano_cachegrand-redis-debunk-activity-6972894707924267010-HzbU https://www.linkedin.com/posts/danielesalvatorealbano_cacheg...
eatonphil 4y ago
It's a key-value store that's also a time series database? I'd like to understand better (both why and how) but the linked time-series documentation is mostly TODOs.
- Octoth0rpe 4y ago
  to be fair, it's very clearly marked as `work in progress` in their readme.
  - eatonphil 4y ago
    Sure, I'm not criticizing it. I'd just like to learn more. :)
    - daniele_dll 4y ago
      I would love to sit and write more documentation but I am doing this work during the night and/or over the weekends so sorry for not having it but I promise I will slowly slowly start to put together something more than a "TODO", even if it's a general intro. The timeseriesdb is "half" a consequence of having a Write-Ahead-Log that is split in chunks and it's chained. I am saying "half" because the other one is the future addition of secondary index to make it possible and easier to query the internal db properly. I know that we are talking mainly about Redis right now, but that's just the tip of the iceberg and my long term vision is to build a much more complete and flexible platform which can easily handle streams (e.g. via a Kafka interface) and/or allow you to run more evolved data processing via WASM (e.g. I want yo make possible to calculate rolling window averages in a time-sensible fashion :)).
      - jonhohle 4y ago
        So the TSDB is being recorded, it’s just not queryable, or it’s not binary compatible with whatever the future in disk format will look like? Is the time series replicated and merged between nodes or does each have its own log for the keys it manages?
deleted 4y ago
[deleted]
danudey 4y ago
These are extremely impressive numbers, and while what is accomplished here is extremely impressive, I just find it funny how rarely Redis or memcached is the bottleneck for an application's scalability. (Obviously it does happen, but statistically speaking it's almost never)
- daniele_dll 4y ago
  (I am the main author of cachegrand) I definitely agree, that's why cachegrand puts the focus on functionalities like an on-disk db, which will also be a timeseries db, active-active replication and support for webassembly. In terms of "just performance", 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, if we leave 15% of marging for peak traffic / issues / surprises / etc, it would still take an application handling 17.5k RPS which is an HUGE amount if we think that this would require easily between 50 and 100 machines beefy machines! I think the biggest limitation nowadays is instead the cost of using "only" memory for the cache and having to use a bunch of different systems to process your data. Try to imagine what you would be able to do if cachegrand would ingest your stream as kafka-compatible server, run your webassembly compiled script and/or run your ML/AI models (leveraging webassembly) and then let push data to other databases / systems and/or let you access your processed data via the Redis / Memcache / GraphQL interface! And on top of this, imagine that all these modules (Kafka, Redis, Memcache, GraphQL, etc.) can leverage a network bypass and a nvme bypass to perform super fast I/O. It's a lot of stuff, but that's my long term goal / vision. Of course to achieve all of this, you need a blazing fast and very flexible base! We are currently focusing on the Redis support because needs many different bits and pieces and would allows us to have people starting to use cachegrand which is a key to understand if the grand plan makes sense :)
  - morelisp 4y ago
    I roughly agree that get throughput is not generally a bottleneck, but > 17.5k RPS which is an HUGE amount if we think that this would require easily between 50 and 100 machines beefy machines! Maybe we have different definitions of beefy, but in terms of HTTP, we serve 2-4x this on less than half that.
NiekvdMaas 4y ago
The redis compatibility layer seems to be very early stage, see https://github.com/danielealbano/cachegrand/blob/main/docs/architecture/modules/redis.md https://github.com/danielealbano/cachegrand/blob/main/docs/a... Compare with e.g. dragonflydb: https://github.com/dragonflydb/dragonfly/blob/main/docs/api_status.md https://github.com/dragonflydb/dragonfly/blob/main/docs/api_... Interesting to see how this will develop over time.
- justinholmes 4y ago
  Dragonfly break Redis license also is slower https://www.linkedin.com/posts/danielesalvatorealbano_cachegrand-redis-debunk-activity-6972894707924267010-HzbU https://www.linkedin.com/posts/danielesalvatorealbano_cacheg...
- daniele_dll 4y ago
  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.
- yewenjie 4y ago
  DragonflyDB is not open source, unfortunately.
  - freeqaz 4y ago
    It will be in 2027 and, unless you plan to run a SaaS that sells Dragonfly (like AWS), then it's Open Source for you today. (The license is Business Source License[0]) 0: https://github.com/dragonflydb/dragonfly/blob/main/LICENSE.md https://github.com/dragonflydb/dragonfly/blob/main/LICENSE.m...
    - daniele_dll 4y ago
      Please don't confuse free source with open source, there is quite a massive difference. There is a reason for which the BSL is not a recognized open source license.
mnutt 4y ago
Are there any plans to implement key eviction to use it as a LRU cache?
- daniele_dll 4y ago
  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.
Andys 4y ago
Any plans to make it distributed? Generally need reliability and fail-over more than straight line speed of using all the cores of a machine.
- daniele_dll 4y ago
  Absolutely, I was planning to introduce the Active-Active replication in a few releases but I changed the plan to do it for the v0.2, together with a memory control and an LRU to evict keys if it's necessary to free up memory, with RDB load support and the ability to work as slave in a Redis cluster, so it will be possible to join it to a cluster and having running to be used for other purposes if wanted (e.g. analytics or similar). In general is pretty stable, I let it run for hours under memtier_benchmark hammering it, although I relocated in March and all my stuff is still packed in a warehouse (it's impossible to find an apartment in Zurich, Switzerland) but I am getting a new 2 x AMD EPYC 7551 with 512GB of ram to have plenty of room for testing and benchmarking with local hardware instead of asking favours :)
mdcds 4y ago
Where does superior performance come from? SSDs optimizations, multi-threading, and O(1) mem allocator?
- daniele_dll 4y ago
  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.
- daniele_dll 4y ago
coderhs 4y ago
Is there a document on how cachegrand achieves this speed over redis?
- daniele_dll 4y ago
  I replied in a few posts in the thread with some details, if you want more there is also this presentation I did at the London performance summit https://www.youtube.com/watch?v=ZSpxuWQK7sM https://www.youtube.com/watch?v=ZSpxuWQK7sM Most of the performance exploits for the hashtable (which is the driving engine here) are explained after minute 8.30 (although I would suggest you to watch the entire presentstion). I will present my work at the p99conf as well.
PeterCorless 4y ago
Awesome stuff, Daniele! For folks wanting to learn more, we'll have Daniele's session for cachegrand at P99 CONF next month (free, virtual event): https://www.p99conf.io/ https://www.p99conf.io/ [edit: just realized we'll also have Roman Gershman of DragonflyDB. So you can hear two different ways to tackle the issue.]
- daniele_dll 4y ago
  Thanks! I also promise to document more the actual inner workings of the various components, I have some scattered documentation here and there which will help me in the task!
deleted 4y ago
[deleted]
kaiser81 4y ago
I'm following your project Daniele! Can't wait to have a stable release
- daniele_dll 4y ago
  Thanks! My goal is to make it usable enough from the 0.3.0 where I want to have enough Redis commands supported (hashsets, sets, lists, multiple dbs, hyperloglog, etc.), have more memory control and have an MVP of the on-disk database. Implementing the data replication, which will come right after, will be fairly easy, thanks to all the logics already built in for the on-disk database, so that should be implemented fairly quickly. Also I have recently bought 2 x AMD EPYC 7551 so I will setup a better performance regression tracking and a proper benchmark suite to track everything (a contributor is working on leveraging the tests and use them as base for the two things mentioned above)

121 points by daniele_dll 4y ago

gpderetta 4y ago

The uncommon name and edit-distance of 1 from cachegrind tripped me up for a few moments.

junon 4y ago
Same, I thought Cachegrind added some new feature or something. Was thoroughly confused until I read the comments.
daniele_dll 4y ago
ahahahahha, that's definitely true, quite similar to Valgrind tooling :D
cozzyd 4y ago
Yes, though a cachegrind profile would be nice to show...

nerpderp82 4y ago

The benchmarks should be against Aerospike or something similar not Redis, as it cooks the results vs what is the current highest performant OSS KV store.

otabdeveloper4 4y ago
Aerospike will happily ignore your requests if it feels like. Use it only if you don't care about correctness or losing data.
- nvartolomei 4y ago
  “In hundreds of tests of SC mode through network partitions, 3.99.1.5 and higher versions have not shown any sign of nonlinearizable histories, lost increments to counters, or lost updates to sets.” – Kyle Kingsbury, Aerospike 3.99.0.3, 12-27-2017 - https://aerospike.com/blog/aerospike-4-strong-consistency-and-jepsen/ https://aerospike.com/blog/aerospike-4-strong-consistency-an... - https://jepsen.io/analyses/aerospike-3-99-0-3 https://jepsen.io/analyses/aerospike-3-99-0-3
  - otabdeveloper4 4y ago
    Good for them. We got rid of Aerospike because using it in the "right" way to get data in and out correctly is a pain in the ass and makes everything slow.
nvartolomei 4y ago
Or against https://github.com/dragonflydb/dragonfly https://github.com/dragonflydb/dragonfly.
- justinholmes 4y ago
  We posted benchmarks https://www.linkedin.com/posts/danielesalvatorealbano_cachegrand-redis-debunk-activity-6972894707924267010-HzbU https://www.linkedin.com/posts/danielesalvatorealbano_cacheg...

eatonphil 4y ago

It's a key-value store that's also a time series database? I'd like to understand better (both why and how) but the linked time-series documentation is mostly TODOs.

Octoth0rpe 4y ago
to be fair, it's very clearly marked as `work in progress` in their readme.
- eatonphil 4y ago
  Sure, I'm not criticizing it. I'd just like to learn more. :)
  - daniele_dll 4y ago
    I would love to sit and write more documentation but I am doing this work during the night and/or over the weekends so sorry for not having it but I promise I will slowly slowly start to put together something more than a "TODO", even if it's a general intro. The timeseriesdb is "half" a consequence of having a Write-Ahead-Log that is split in chunks and it's chained. I am saying "half" because the other one is the future addition of secondary index to make it possible and easier to query the internal db properly. I know that we are talking mainly about Redis right now, but that's just the tip of the iceberg and my long term vision is to build a much more complete and flexible platform which can easily handle streams (e.g. via a Kafka interface) and/or allow you to run more evolved data processing via WASM (e.g. I want yo make possible to calculate rolling window averages in a time-sensible fashion :)).
    - jonhohle 4y ago
      So the TSDB is being recorded, it’s just not queryable, or it’s not binary compatible with whatever the future in disk format will look like? Is the time series replicated and merged between nodes or does each have its own log for the keys it manages?

deleted 4y ago

[deleted]

danudey 4y ago

These are extremely impressive numbers, and while what is accomplished here is extremely impressive, I just find it funny how rarely Redis or memcached is the bottleneck for an application's scalability. (Obviously it does happen, but statistically speaking it's almost never)

daniele_dll 4y ago
(I am the main author of cachegrand) I definitely agree, that's why cachegrand puts the focus on functionalities like an on-disk db, which will also be a timeseries db, active-active replication and support for webassembly. In terms of "just performance", 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, if we leave 15% of marging for peak traffic / issues / surprises / etc, it would still take an application handling 17.5k RPS which is an HUGE amount if we think that this would require easily between 50 and 100 machines beefy machines! I think the biggest limitation nowadays is instead the cost of using "only" memory for the cache and having to use a bunch of different systems to process your data. Try to imagine what you would be able to do if cachegrand would ingest your stream as kafka-compatible server, run your webassembly compiled script and/or run your ML/AI models (leveraging webassembly) and then let push data to other databases / systems and/or let you access your processed data via the Redis / Memcache / GraphQL interface! And on top of this, imagine that all these modules (Kafka, Redis, Memcache, GraphQL, etc.) can leverage a network bypass and a nvme bypass to perform super fast I/O. It's a lot of stuff, but that's my long term goal / vision. Of course to achieve all of this, you need a blazing fast and very flexible base! We are currently focusing on the Redis support because needs many different bits and pieces and would allows us to have people starting to use cachegrand which is a key to understand if the grand plan makes sense :)
- morelisp 4y ago
  I roughly agree that get throughput is not generally a bottleneck, but > 17.5k RPS which is an HUGE amount if we think that this would require easily between 50 and 100 machines beefy machines! Maybe we have different definitions of beefy, but in terms of HTTP, we serve 2-4x this on less than half that.

NiekvdMaas 4y ago

The redis compatibility layer seems to be very early stage, see https://github.com/danielealbano/cachegrand/blob/main/docs/architecture/modules/redis.md https://github.com/danielealbano/cachegrand/blob/main/docs/a... Compare with e.g. dragonflydb: https://github.com/dragonflydb/dragonfly/blob/main/docs/api_status.md https://github.com/dragonflydb/dragonfly/blob/main/docs/api_... Interesting to see how this will develop over time.

justinholmes 4y ago
Dragonfly break Redis license also is slower https://www.linkedin.com/posts/danielesalvatorealbano_cachegrand-redis-debunk-activity-6972894707924267010-HzbU https://www.linkedin.com/posts/danielesalvatorealbano_cacheg...
daniele_dll 4y ago
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.
yewenjie 4y ago
DragonflyDB is not open source, unfortunately.
- freeqaz 4y ago
  It will be in 2027 and, unless you plan to run a SaaS that sells Dragonfly (like AWS), then it's Open Source for you today. (The license is Business Source License[0]) 0: https://github.com/dragonflydb/dragonfly/blob/main/LICENSE.md https://github.com/dragonflydb/dragonfly/blob/main/LICENSE.m...
  - daniele_dll 4y ago
    Please don't confuse free source with open source, there is quite a massive difference. There is a reason for which the BSL is not a recognized open source license.

mnutt 4y ago

Are there any plans to implement key eviction to use it as a LRU cache?

daniele_dll 4y ago
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.

Andys 4y ago

Any plans to make it distributed? Generally need reliability and fail-over more than straight line speed of using all the cores of a machine.

daniele_dll 4y ago
Absolutely, I was planning to introduce the Active-Active replication in a few releases but I changed the plan to do it for the v0.2, together with a memory control and an LRU to evict keys if it's necessary to free up memory, with RDB load support and the ability to work as slave in a Redis cluster, so it will be possible to join it to a cluster and having running to be used for other purposes if wanted (e.g. analytics or similar). In general is pretty stable, I let it run for hours under memtier_benchmark hammering it, although I relocated in March and all my stuff is still packed in a warehouse (it's impossible to find an apartment in Zurich, Switzerland) but I am getting a new 2 x AMD EPYC 7551 with 512GB of ram to have plenty of room for testing and benchmarking with local hardware instead of asking favours :)

mdcds 4y ago

Where does superior performance come from? SSDs optimizations, multi-threading, and O(1) mem allocator?

daniele_dll 4y ago
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.
daniele_dll 4y ago

coderhs 4y ago

Is there a document on how cachegrand achieves this speed over redis?

daniele_dll 4y ago
I replied in a few posts in the thread with some details, if you want more there is also this presentation I did at the London performance summit https://www.youtube.com/watch?v=ZSpxuWQK7sM https://www.youtube.com/watch?v=ZSpxuWQK7sM Most of the performance exploits for the hashtable (which is the driving engine here) are explained after minute 8.30 (although I would suggest you to watch the entire presentstion). I will present my work at the p99conf as well.

PeterCorless 4y ago

Awesome stuff, Daniele! For folks wanting to learn more, we'll have Daniele's session for cachegrand at P99 CONF next month (free, virtual event): https://www.p99conf.io/ https://www.p99conf.io/ [edit: just realized we'll also have Roman Gershman of DragonflyDB. So you can hear two different ways to tackle the issue.]

daniele_dll 4y ago
Thanks! I also promise to document more the actual inner workings of the various components, I have some scattered documentation here and there which will help me in the task!

deleted 4y ago

[deleted]

kaiser81 4y ago

I'm following your project Daniele! Can't wait to have a stable release

daniele_dll 4y ago
Thanks! My goal is to make it usable enough from the 0.3.0 where I want to have enough Redis commands supported (hashsets, sets, lists, multiple dbs, hyperloglog, etc.), have more memory control and have an MVP of the on-disk database. Implementing the data replication, which will come right after, will be fairly easy, thanks to all the logics already built in for the on-disk database, so that should be implemented fairly quickly. Also I have recently bought 2 x AMD EPYC 7551 so I will setup a better performance regression tracking and a proper benchmark suite to track everything (a contributor is working on leveraging the tests and use them as base for the two things mentioned above)