Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optional feature flag to use a DashMap as opposed to a HashMap #92

Closed
Milo123459 opened this issue Feb 20, 2022 · 32 comments · Fixed by #99
Closed

Optional feature flag to use a DashMap as opposed to a HashMap #92

Milo123459 opened this issue Feb 20, 2022 · 32 comments · Fixed by #99
Assignees
Labels
enhancement New feature or request
Milestone

Comments

@Milo123459
Copy link
Contributor

I'd be happy to implement this.

@tatsuya6502
Copy link
Member

Hi. Thank you for the offer.

Moka's concurrent cache implementations sync::Cache, sync::SegmentedCache and future::Cache do not use std::collections::HashMap. They use moka::cht::segment::HashMap, which is a lock-free concurrent hash table.

/// A lock-free hash map implemented with segmented bucket pointer arrays, open
/// addressing, and linear probing.

Are you saying that you want an optional Cargo feature to use DashMap from dashmap instead of moka::cht::SegmentedHashMap? DashMap is a concurrent hash table but is not lock-free. (it uses RwLocks internally)

If so, could you please tell me the reasons you want the feature?

moka::cht::segmented::HashMap has different API to std::collections::HashMap and dashmap::DashMap, so it would not be straightforward to add such feature.

@Milo123459
Copy link
Contributor Author

I was going to implement this into https://github.com/serenity-rs/serenity which uses a DashMap for caching and we were interested in implementing a TTL, so we found this crate. However, due to #34 it sadly looks like we aren't going to be able to use this crate.

@tatsuya6502
Copy link
Member

Thanks. I understood the reason.

Let me add the feature.

There will be some limitations. When the feature is enabled, cache will not support the following methods because DashMap does not provide necessary functions:

  • get_or_insert_with (doc)
  • get_or_try_insert_with (doc)

I think you will be okay with the limitation above because you are currently using DashMap and it does not provide methods like them.

Also I think you are using iter method of DashMap:
https://github.com/serenity-rs/serenity/blob/next/src/cache/mod.rs#L39

but our caches do not provide iterators. Is this okay?

@tatsuya6502 tatsuya6502 self-assigned this Feb 20, 2022
@tatsuya6502 tatsuya6502 added the enhancement New feature or request label Feb 20, 2022
@tatsuya6502 tatsuya6502 added this to the v0.7.3 milestone Feb 20, 2022
@Milo123459
Copy link
Contributor Author

Yes, this is all fine! Thank you very much for the swift response.

However, the still major roadblock for us using this library is #34. If that can be resolved (no rush) then serenity will happily move over to using Moka.

@Milo123459
Copy link
Contributor Author

Ah, we do need Iter. I just checked with some of the people who work on Serenity.

@tatsuya6502
Copy link
Member

tatsuya6502 commented Feb 20, 2022

However, the still major roadblock for us using this library is #34. If that can be resolved (no rush) then serenity will happily move over to using Moka.

The issue #34 (segfault) will not occur when this feature is enabled because:

  • Segfaults have been occurring only when using get_or_insert_with and get_or_try_insert_with methods.
    • And these methods will not be available when this feature is enabled.
  • Segfaults seem to be occurring in somewhere in external dependencies of moka::cht::segment::HashMap.
    • So if Moka uses DashMap instead of moka::cht::segment::HashMap, they will not occur.

Once I finish implementing this feature, I will run the same load tests that have triggered the segfaults.

@tatsuya6502
Copy link
Member

Ah, we do need Iter. I just checked with some of the people who work on Serenity.

Okay. I created #93 "Iterating all entries in a cache". I hope it will not difficult to implement if DashMap is used (because DashMap already provides iterators. moka::cht::segment::HashMap does not)

@Milo123459
Copy link
Contributor Author

Hey,

We have discussed some design changes, and we are only going to use Moka as a temporary cache for things that don't update from events. Provided that the segfaults only happen on those functions, DashMap support isn't needed for serenity.

@Dessix
Copy link

Dessix commented Feb 28, 2022

@tatsuya6502 Regarding your previous post: DashMap does actually provide an equivalent for get_or_try_insert_with; it's .entry(k).or_try_insert_with(...).


As for the overall issue being discussed- a feature flag is not likely the correct way to do this. Feature flags can arise from those set in your dependencies, and would alter the perceived function for your library. Unless the feature-flag enables a strict superset of functionality with no degradation or drawbacks, crate flags should not alter the behaviour of existing, compiling code.

I'd suggest a generic parameter with a default to HashMap instead, and an alias that directly refers to the DashMap implementation's type. Additionally, by doing it this way, you gain the ability to plug-in other storage mechanisms as long as they fulfill a trait description used by the library.

An example of a library that does this correctly is opentelemetry which has flags that enable compilation of various runtime adapters, but requires the caller to explicitly specify which to initialize when starting up the telemetry system.

@Milo123459
Copy link
Contributor Author

Ah, I see. That function is the only one with the vulnerability though?

@Dessix
Copy link

Dessix commented Feb 28, 2022

I have no idea what you mean by vulnerability. It was mentioned that a functionality was missing- but this was not the case; DashMap is indeed capable of upsert semantics.

@Milo123459
Copy link
Contributor Author

Not vulnerability, sorry. I meant does the issue mentioned in #34 only happen on those functions.

@Dessix
Copy link

Dessix commented Feb 28, 2022

That issue shouldn't happen at all, and I suggested that MIRI and Loom may be capable of isolating the root cause, but the segfaults appear to be specific to the HashMap being used by Moka, not the presence nor usage of an upsert function.

@Milo123459
Copy link
Contributor Author

Ah, thanks for the information.

@Milo123459
Copy link
Contributor Author

Hey 👋 any updates on this? No rush, just curious.

@tatsuya6502
Copy link
Member

Hi @Milo123459. Sorry, I am not making progress on this yet. I had been busy on some urgent stuff for three weeks and had no time to work on Moka. (These urgent stuff were mainly for my job, but some others for Japanese Rust community)

Now those urgent stuff are basically done and I am going to resume my works on Moka. Let me finish up another work in Moka (#91), which I was working on a month ago, and then I will work on this.

@Milo123459
Copy link
Contributor Author

Thanks for the update!

@tatsuya6502
Copy link
Member

tatsuya6502 commented Mar 19, 2022

Hi @Milo123459 — I started to work on this. I added an optional moka::dash::Cache to Moka under Cargo feature dash. All unit tests are passing now. You can try it to see if it has everything you need.

To try it, add the following to the [dependencies] section of your Cargo.toml:

[dependencies]
moka = { git = "https://github.com/moka-rs/moka", branch = "master", features = ["dash"] }

Then generate the Rust doc using the following command:

$ cargo doc

Open ./target/doc/moka/index.html with a web browser, and navigate to moka::dash::Cache. You may want to start with the example on the page.

Please let me know if you are happy with it or you need me to add/change something. I wonder if you still need the iterator #93.

I will start to run some load tests to ensure no segfaults occurs.

Thanks!

@Milo123459
Copy link
Contributor Author

Thank you so much!

Yeah, we still do need the iteration system. Thanks for also running some load tests!

@tatsuya6502
Copy link
Member

tatsuya6502 commented Mar 20, 2022

I will start to run some load tests to ensure no segfault occurs.

I ran the load tests and no segfault occurred. Merging pull request #99.

@Milo123459
Copy link
Contributor Author

Hey, I'm getting this issue: https://paste.rs/AHX

It's a bit weird. I think this is related to moka and not serenity.

@tatsuya6502 tatsuya6502 reopened this Mar 20, 2022
@tatsuya6502
Copy link
Member

Hi @Milo123459 — Can you please run cargo update and see what happens?

@Milo123459
Copy link
Contributor Author

Will do. It's updated loads of things, so I have some other issues to fix.

@Milo123459
Copy link
Contributor Author

Ah, it worked.

@Milo123459
Copy link
Contributor Author

Hi, sorry again. Is there a chance that moka::dash::Cache could implement Debug?

@tatsuya6502
Copy link
Member

Yes, it could implement Debug. Let me work on it later today.

@Milo123459
Copy link
Contributor Author

Thank you so much!

@tatsuya6502
Copy link
Member

Hi @Milo123459 — I added Debug to moka::dash::Cache via #102. Please run cargo update again to pull the update from the master branch.

@Milo123459
Copy link
Contributor Author

Thank you once more!

@Dessix
Copy link

Dessix commented Mar 22, 2022

Will this be included in a release in the near future?

@tatsuya6502
Copy link
Member

Hi @Dessix — Yes. This will be included in next release v0.8.0 as an experimental feature. I am trying to release it by this weekend.

@tatsuya6502
Copy link
Member

Hi @Milo123459 and @Dessix — I have published Moka v0.8.0 with dash::Cache to crates.io. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants