4 ms·

Show HN: Whirlwind – Async concurrent hashmap for Rust

140 points by willothy 2y ago

Hey HN, this is Will and David from Fortress (https://news.ycombinator.com/item?id=41426998 https://news.ycombinator.com/item?id=41426998). We use a lot of async Rust internally, and created this library out of a need for an async-aware concurrent hashmap since there weren’t many available in the Rust ecosystem. Whirlwind is a sharded HashMap with a fully asynchronous API. Just as dashmap is a replacement for std::sync::RwLock<HashMap>, whirlwind aims to be a replacement for tokio::sync::RwLock<HashMap>. It has a similar design and performance characteristics to dashmap, but seems to perform better in read-heavy workloads with tokio's green threading. Benchmarks are in the readme! We used an asyncified version of dashmap's benchmark suite. The project is in a pretty early stage and I'm sure there are flaws, but I'm pretty happy with the performance. There is some unsafe involved, but we run Miri in ci to (hopefully) catch undefined behavior well before it's in an actual release. We'd appreciate any feedback! Thanks in advance :)

Sytten 2y ago
Looks interesting! We used quick-cache [1] for that purpose right now, might be interesting to add comparison with those types of Key-Value caching crates. [1] https://github.com/arthurprs/quick-cache https://github.com/arthurprs/quick-cache
- willothy 2y ago
  Good point, thanks! I'll look into adding that crate to the benchmarks.
olix0r 2y ago
> Just as dashmap is a replacement for std::sync::RwLock<HashMap>, whirlwind aims to be a replacement for tokio::sync::RwLock<HashMap>. I'm curious about the practical benefits of handling a HashMap with an async interface. My long-standing understanding is that `tokio::sync::RwLock<HashMap>` is only useful when you'd want to hold the lock guard across another `await` operation; but when the lock guard is not held across an await, it is always preferable to use the synchronous version. This would lead me to assume that same applies for dashmap--it should be sufficient for async use cases and doesn't need an async API unless we expect to be blocked, but the benchmarks indicate that whirlwind outperforms dashmap in various situations. Do you have a sense of where this blocking occurs in dashmap?
- willothy 2y ago
  The blocking mainly occurs due to contention - imo most of the performance gain comes from being able to poll the lock instead of blocking until it's available when acquiring locks on shards. In all honesty I was quite surprised by the benchmarks as well though, I wouldn't expect that much performance gain, but in high-contention scenarios it definitely makes sense.
  - conradludgate 2y ago
    Benchmarks will always look good when using a spin-lock like you seem to be using here https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba14870f64828b7bb3a1059b78bb171/src/shard/futures.rs#L27 https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba...
    - dwattttt 2y ago
      I believe that doesn't indicate it's spinlocking; the `poll` API is specified to not block.
      - conradludgate 2y ago
        > In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available Immediately waking itself, the task is scheduled and will be polled again shortly. This creates the loop in which is checks if the lock is available. This has no effective difference compared to using hint::spin_loop() but in async. A more traditional lock will use a queue in which the task will not be polled until it's likely available, rather than blindly trying on repeat.
        dwattttt 2y ago
        The code linked does the following: - attempt to acquire an RWLock without blocking - if it does, wake the task waiting for the lock - if it doesn't, return "not ready yet" The RWLock is straight from the standard lib; there's no loop and no spinning involved. Every single Future you look at will look like this, by specification they cannot block, only return "ready" (and wake the task), or return "not ready".
phlip9 2y ago
Benches look promising! My main concern is validating correctness; implementing good concurrency primitives is always challenging. Have you looked into testing against a purpose-built concurrency model checker like tokio-rs/loom [1] or awslabs/shuttle [2]? IMO that would go a long way towards building trust in this impl. [1] https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom [2] https://github.com/awslabs/shuttle https://github.com/awslabs/shuttle
- willothy 2y ago
  Yep, someone suggested loom on our Reddit r/rust post as well - I'm actively working on that. Somehow I'd just never heard of loom before this.
judofyr 2y ago
One thing which wasn’t obvious to me from the benchmark: What’s the key distribution? A sharded map will probably have great performance on uniform keys, but in my experience it’s far more common to have power law distribution in real life scenarios. It would be good to see a benchmark where it only touches a _single_ key. If Whirlwind is still fast than the others I would be far more convinced to use it unconditionally. EDIT: I also see that you're benchmarking on a M3 Max. Note that this has 6 performance cores and 6 efficiency cores. This means that if you're running at <6 cores it will most likely start out running it at the efficiency core. From my experience it's quite important to do warmup phases in order to get stable results at low thread count. And even then I find it hard to reason about the results since you're running in mixed set of cores…
- willothy 2y ago
  Definitely a good point. I used dashmap's benchmark suite because it was already setup to bench many popular libraries, but I definitely want to get this tested in more varied scenarios. I'll try to add a benchmark for a single key only this week. Regarding your edit: damn I hadn't thought of that. I'll rerun the benchmarks on my Linux desktop with a Ryzen chip and update the readme.
  - judofyr 2y ago
    Very fascinating results though! The sharding approach is quite a simple way of doing more fine-grained locking, making sure that writes don't block all the reads. Pretty cool to see that it actually pays off even with the overhead of Tokie scheduling everything! There might be some fairness concerns here? Since we're polling the lock (instead of adding ourselves to a queue) it could be the case that some requests are constantly "too late" to acquire it? Could be interesting to see the min/max/median/P99 of the requests themselves. It seems that Bustle only reports the average latency[1] which honestly doesn't tell us much more than the throughputs. [1]: https://docs.rs/bustle/latest/bustle/struct.Measurement.html https://docs.rs/bustle/latest/bustle/struct.Measurement.html
    - willothy 2y ago
shepardrtc 2y ago
How do you determine the number of shards to use?
- willothy 2y ago
  I use a multiple of `std::thread::available_paralellism()`. Tbh I borrowed the strategy from dashmap, but I tested others and this seemed to work quite well. Considering making that configurable in the future so that it can be specialized for different use-cases or used in single-threaded but cooperatively scheduled contexts.
- cogman10 2y ago
  (std::thread::available_parallelism().map_or(1, usize::from) * 4).next_power_of_two()
gsliepen 2y ago
I'm sure this library does the thing it claims to do very nicely. However, as a programmer I am saddened that so many things that should have been in the standard library by now need to come from external repositories and have a weird and unintuitive names.
- willothy 2y ago
  Hey, I think the name is cool! Fair point though, there would definitely be some benefit to having some of these things in the stdlib.
- bryanlarsen 2y ago
  tokio itself is not mature/stable enough to be in the standard library, IMO, let alone anything based on tokio.
  - rsanders 2y ago
    I'm pretty new to Rust so forgive me if I'm mistaken, but it seems to me that this crate doesn't require the use of tokio.
    - lesuorac 2y ago
      When all the examples are marked with `#[tokio::main]`, it probably requires tokio. Although I guess they do implement Future on their own so it shouldn't need a specific runtime then. https://github.com/fortress-build/whirlwind/blob/main/src/shard/futures.rs https://github.com/fortress-build/whirlwind/blob/main/src/sh...
      - blurbleblurble 2y ago
        They're just using tokio as a dev dependency. You could use this with any async runtime https://github.com/fortress-build/whirlwind/blob/main/Cargo.toml#L14 https://github.com/fortress-build/whirlwind/blob/main/Cargo....
      - willothy 2y ago
James_K 2y ago
> This crate is in development, and breaking changes may be made up until a 1.0 release. When will this happen? I imagine a lot of people who want use it might just forget about it if you say "do not use this until some unspecified point in the future".
- willothy 2y ago
  I think there's a pretty big difference between committing to semantic versioning and saying "do not use this until some unspecified point in the future." Maybe I'm just not clear enough in the note - I just mean that the API could change. But as long as a consumer doesn't use `version = "*"` in their Cargo.toml, breaking changes will always be opt-in and builds won't start failing if I release something with a big API change.
  - James_K 2y ago
    Maybe I'm a bit weird, but I would never commit to using something if the person making it wasn't providing a consistent interface. It could well be different in your case, but as a general rule, a sub 1.0 version is software that isn't yet ready to be used. The vast vast majority of projects that say "you can use this, but we won't provide a consistent interface yet" end up either dying before they get to v1 or causing so much pain they weren't worth using. I can see this issue being especially bad in Rust, where small API changes can create big issues with lifetimes and such.
KolmogorovComp 2y ago
Great crate! Why use a hashmap instead of a Btreemap which is usually advised in rust?
- aw1621107 2y ago
  > Why use a hashmap instead of a Btreemap which is usually advised in rust? Is this actually the case? I can't say I've seen the same.
- willothy 2y ago
  There are a few reasons - For one, I'm not sure BTreeMap is always faster in Rust... it may be sometimes but lookups are still O(log(n)) due to the searching where with a HashMap it's (mostly) O(1). They both have their uses - I usually go for BTreeMap when I explicitly need the collection to be ordered. A second reason is sharding - sharding based on a hash is quite simple to do, but sharding an ordered collection would be quite difficult since some reads would need to search across multiple shards and thus take multiple locks. If you mean internally (like for each shard), we're using hashbrown's raw HashTable API because it allows us to manage hashing entirely ourselves, and avoid recomputing the hash when determining the shard and looking up a key within a shard.
- CyberDildonics 2y ago
  Why would you use a b tree if you don't need sorting? It will not only be slower but require a lot more to make lock free (is this hash map lock free?).
conradludgate 2y ago
I don't think I'd recommend using this in production. The benchmarks look good, but by immediately waking the waker[0], you've effectively created a spin-lock. They may work in some very specific circumstances, but they will most likely in practice be more costly to your scheduler (which likely uses locks btw) than just using locks [0]: https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba14870f64828b7bb3a1059b78bb171/src/shard/futures.rs#L27 https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba...
- willothy 2y ago
  I don't believe that waking the waker in `poll` synchronously waits / runs poll again immediately. I think it is more likely just adding the future back to the global queue to be polled. I could be wrong though, I'll look into this more. Thanks for the info!
  - conradludgate 2y ago
    It does immediately put itself into the queue to be polled again. But that's no different in effect to a spin-lock. If you have other tasks in your runtime, this will be putting excess pressure on your scheduler
    - conradludgate 2y ago
      Expanding on this. If you have a lot of concurrent tasks, you will overflow[0] the task local queue and be bottlenecked by the global queue mutex[1] [0]: https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f896319eeb8777cf255fc/tokio/src/runtime/scheduler/multi_thread/queue.rs#L63 https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f8... [1]: https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f896319eeb8777cf255fc/tokio/src/runtime/scheduler/inject/rt_multi_thread.rs#L77 https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f8...
      - willothy 2y ago
        Oh this is really good to know, thank you!
Hippieblog 2y ago
[dead]
warambo1010 2y ago
[dead]
PixelPulse97 2y ago
I don't see the use case of this

140 points by willothy 2y ago

Sytten 2y ago

Looks interesting! We used quick-cache [1] for that purpose right now, might be interesting to add comparison with those types of Key-Value caching crates. [1] https://github.com/arthurprs/quick-cache https://github.com/arthurprs/quick-cache

willothy 2y ago
Good point, thanks! I'll look into adding that crate to the benchmarks.

olix0r 2y ago

> Just as dashmap is a replacement for std::sync::RwLock<HashMap>, whirlwind aims to be a replacement for tokio::sync::RwLock<HashMap>. I'm curious about the practical benefits of handling a HashMap with an async interface. My long-standing understanding is that `tokio::sync::RwLock<HashMap>` is only useful when you'd want to hold the lock guard across another `await` operation; but when the lock guard is not held across an await, it is always preferable to use the synchronous version. This would lead me to assume that same applies for dashmap--it should be sufficient for async use cases and doesn't need an async API unless we expect to be blocked, but the benchmarks indicate that whirlwind outperforms dashmap in various situations. Do you have a sense of where this blocking occurs in dashmap?

willothy 2y ago
The blocking mainly occurs due to contention - imo most of the performance gain comes from being able to poll the lock instead of blocking until it's available when acquiring locks on shards. In all honesty I was quite surprised by the benchmarks as well though, I wouldn't expect that much performance gain, but in high-contention scenarios it definitely makes sense.
- conradludgate 2y ago
  Benchmarks will always look good when using a spin-lock like you seem to be using here https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba14870f64828b7bb3a1059b78bb171/src/shard/futures.rs#L27 https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba...
  - dwattttt 2y ago
    I believe that doesn't indicate it's spinlocking; the `poll` API is specified to not block.
    - conradludgate 2y ago
      > In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available Immediately waking itself, the task is scheduled and will be polled again shortly. This creates the loop in which is checks if the lock is available. This has no effective difference compared to using hint::spin_loop() but in async. A more traditional lock will use a queue in which the task will not be polled until it's likely available, rather than blindly trying on repeat.
      - dwattttt 2y ago
        The code linked does the following: - attempt to acquire an RWLock without blocking - if it does, wake the task waiting for the lock - if it doesn't, return "not ready yet" The RWLock is straight from the standard lib; there's no loop and no spinning involved. Every single Future you look at will look like this, by specification they cannot block, only return "ready" (and wake the task), or return "not ready".

phlip9 2y ago

Benches look promising! My main concern is validating correctness; implementing good concurrency primitives is always challenging. Have you looked into testing against a purpose-built concurrency model checker like tokio-rs/loom [1] or awslabs/shuttle [2]? IMO that would go a long way towards building trust in this impl. [1] https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom [2] https://github.com/awslabs/shuttle https://github.com/awslabs/shuttle

willothy 2y ago
Yep, someone suggested loom on our Reddit r/rust post as well - I'm actively working on that. Somehow I'd just never heard of loom before this.

judofyr 2y ago

One thing which wasn’t obvious to me from the benchmark: What’s the key distribution? A sharded map will probably have great performance on uniform keys, but in my experience it’s far more common to have power law distribution in real life scenarios. It would be good to see a benchmark where it only touches a _single_ key. If Whirlwind is still fast than the others I would be far more convinced to use it unconditionally. EDIT: I also see that you're benchmarking on a M3 Max. Note that this has 6 performance cores and 6 efficiency cores. This means that if you're running at <6 cores it will most likely start out running it at the efficiency core. From my experience it's quite important to do warmup phases in order to get stable results at low thread count. And even then I find it hard to reason about the results since you're running in mixed set of cores…

willothy 2y ago
Definitely a good point. I used dashmap's benchmark suite because it was already setup to bench many popular libraries, but I definitely want to get this tested in more varied scenarios. I'll try to add a benchmark for a single key only this week. Regarding your edit: damn I hadn't thought of that. I'll rerun the benchmarks on my Linux desktop with a Ryzen chip and update the readme.
- judofyr 2y ago
  Very fascinating results though! The sharding approach is quite a simple way of doing more fine-grained locking, making sure that writes don't block all the reads. Pretty cool to see that it actually pays off even with the overhead of Tokie scheduling everything! There might be some fairness concerns here? Since we're polling the lock (instead of adding ourselves to a queue) it could be the case that some requests are constantly "too late" to acquire it? Could be interesting to see the min/max/median/P99 of the requests themselves. It seems that Bustle only reports the average latency[1] which honestly doesn't tell us much more than the throughputs. [1]: https://docs.rs/bustle/latest/bustle/struct.Measurement.html https://docs.rs/bustle/latest/bustle/struct.Measurement.html
  - willothy 2y ago

shepardrtc 2y ago

How do you determine the number of shards to use?

willothy 2y ago
I use a multiple of `std::thread::available_paralellism()`. Tbh I borrowed the strategy from dashmap, but I tested others and this seemed to work quite well. Considering making that configurable in the future so that it can be specialized for different use-cases or used in single-threaded but cooperatively scheduled contexts.
cogman10 2y ago
(std::thread::available_parallelism().map_or(1, usize::from) * 4).next_power_of_two()

gsliepen 2y ago

I'm sure this library does the thing it claims to do very nicely. However, as a programmer I am saddened that so many things that should have been in the standard library by now need to come from external repositories and have a weird and unintuitive names.

willothy 2y ago
Hey, I think the name is cool! Fair point though, there would definitely be some benefit to having some of these things in the stdlib.
bryanlarsen 2y ago
tokio itself is not mature/stable enough to be in the standard library, IMO, let alone anything based on tokio.
- rsanders 2y ago
  I'm pretty new to Rust so forgive me if I'm mistaken, but it seems to me that this crate doesn't require the use of tokio.
  - lesuorac 2y ago
    When all the examples are marked with `#[tokio::main]`, it probably requires tokio. Although I guess they do implement Future on their own so it shouldn't need a specific runtime then. https://github.com/fortress-build/whirlwind/blob/main/src/shard/futures.rs https://github.com/fortress-build/whirlwind/blob/main/src/sh...
    - blurbleblurble 2y ago
      They're just using tokio as a dev dependency. You could use this with any async runtime https://github.com/fortress-build/whirlwind/blob/main/Cargo.toml#L14 https://github.com/fortress-build/whirlwind/blob/main/Cargo....
    - willothy 2y ago

James_K 2y ago

> This crate is in development, and breaking changes may be made up until a 1.0 release. When will this happen? I imagine a lot of people who want use it might just forget about it if you say "do not use this until some unspecified point in the future".

willothy 2y ago
I think there's a pretty big difference between committing to semantic versioning and saying "do not use this until some unspecified point in the future." Maybe I'm just not clear enough in the note - I just mean that the API could change. But as long as a consumer doesn't use `version = "*"` in their Cargo.toml, breaking changes will always be opt-in and builds won't start failing if I release something with a big API change.
- James_K 2y ago
  Maybe I'm a bit weird, but I would never commit to using something if the person making it wasn't providing a consistent interface. It could well be different in your case, but as a general rule, a sub 1.0 version is software that isn't yet ready to be used. The vast vast majority of projects that say "you can use this, but we won't provide a consistent interface yet" end up either dying before they get to v1 or causing so much pain they weren't worth using. I can see this issue being especially bad in Rust, where small API changes can create big issues with lifetimes and such.

KolmogorovComp 2y ago

Great crate! Why use a hashmap instead of a Btreemap which is usually advised in rust?

aw1621107 2y ago
> Why use a hashmap instead of a Btreemap which is usually advised in rust? Is this actually the case? I can't say I've seen the same.
willothy 2y ago
There are a few reasons - For one, I'm not sure BTreeMap is always faster in Rust... it may be sometimes but lookups are still O(log(n)) due to the searching where with a HashMap it's (mostly) O(1). They both have their uses - I usually go for BTreeMap when I explicitly need the collection to be ordered. A second reason is sharding - sharding based on a hash is quite simple to do, but sharding an ordered collection would be quite difficult since some reads would need to search across multiple shards and thus take multiple locks. If you mean internally (like for each shard), we're using hashbrown's raw HashTable API because it allows us to manage hashing entirely ourselves, and avoid recomputing the hash when determining the shard and looking up a key within a shard.
CyberDildonics 2y ago
Why would you use a b tree if you don't need sorting? It will not only be slower but require a lot more to make lock free (is this hash map lock free?).

conradludgate 2y ago

I don't think I'd recommend using this in production. The benchmarks look good, but by immediately waking the waker[0], you've effectively created a spin-lock. They may work in some very specific circumstances, but they will most likely in practice be more costly to your scheduler (which likely uses locks btw) than just using locks [0]: https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba14870f64828b7bb3a1059b78bb171/src/shard/futures.rs#L27 https://github.com/fortress-build/whirlwind/blob/0e4ae5a2aba...

willothy 2y ago
I don't believe that waking the waker in `poll` synchronously waits / runs poll again immediately. I think it is more likely just adding the future back to the global queue to be polled. I could be wrong though, I'll look into this more. Thanks for the info!
- conradludgate 2y ago
  It does immediately put itself into the queue to be polled again. But that's no different in effect to a spin-lock. If you have other tasks in your runtime, this will be putting excess pressure on your scheduler
  - conradludgate 2y ago
    Expanding on this. If you have a lot of concurrent tasks, you will overflow[0] the task local queue and be bottlenecked by the global queue mutex[1] [0]: https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f896319eeb8777cf255fc/tokio/src/runtime/scheduler/multi_thread/queue.rs#L63 https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f8... [1]: https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f896319eeb8777cf255fc/tokio/src/runtime/scheduler/inject/rt_multi_thread.rs#L77 https://github.com/tokio-rs/tokio/blob/8897885425bf3d89053f8...
    - willothy 2y ago
      Oh this is really good to know, thank you!

Hippieblog 2y ago

[dead]

warambo1010 2y ago

[dead]

PixelPulse97 2y ago

I don't see the use case of this