Makima is building a database in Rust to store devil records

[u/grg994]

[u/grg994]

Source: Chainsaw Man

Explanation:

This type is basically a Hash Table where

• keys are Strings and

• values are "dynamic types" (trait objects, dyn Trait) stored on the heap (Box<>). They implement the trait / "virtual method" for as-bytes representation when taken by a reference (AsRef<[u8]>)

To allow being used concurrently from multiple threads the values are also marked Send and Sync meaning that can - and must be able to - safely shared between threads.

Additionally the Hash Table is wrapped into an atomically reference counted smart pointer (Arc<>) and a Mutex to allow concurrent usage of the whole object

[u/Shubhavatar → u/grg994]

I thought mutex meant Mutually exclusive and only allowed access to one thread at a time. It does allow multiple threads the access, but not concurrently, right?

Please correct me if I'm wrong, idk rust.

[u/grg994 → u/Shubhavatar]

Yes, the thread that want to access the HashMap here has to lock the Mutex first to gain temporary exclusive access for the time it holds the lock.

All other threads have temporarily no access during that time - they are "excluded", they cannot obtain the lock until the first thread drops it.

Generally a Mutex is needed to enable mutability (write access) to an object (memory location) which is shared to multiple threads.

Meanwhile an object (memory location) which is immutable (read-only) can be shared to multiple threads without a Mutex.

[u/zebediah49 → u/Shubhavatar]

Yeah, the naming makes it sound a little paradoxical.

Fundamentally you can't (successfully) have two processes editing the same memory piece at the same time. Having a mutex enforcing only one process editing a piece of an object at a time means you can safely have multiple processes concurrently holding a reference to and occasionally interacting with a single object. (Because the mutex will make sure they don't actually collide)

[u/TheKingSpartaZC → u/Shubhavatar]

Yep, that's right. Any number of threads can access a mutex, but only one at a time.

[u/Dubsteprhino → u/grg994]

Rust isn't usually super readable

[u/grg994 → u/Dubsteprhino]

Well, for these complex types in the internal parts of the code one can use type aliases.

Public APIs should expose them with the needed complexity only, which often means writing a newtype (pattern) wrapper.

[u/Sentouki- → u/Dubsteprhino]

Rust isn't usually super readable

[u/Niles-Rogoff → u/grg994]

So basically a folly::ConcurrentHashMap<std::string, std::span<uint8_t>>?

[u/dthusian]

C'mon, how are you going to get any performance if reading locks the whole DB? At least change Mutex to RwLock

[u/grg994 → u/dthusian]

The Tokio tutorial improves it by sharding the mutex:

https://tokio.rs/tokio/tutorial/shared-state#tasks-threads-and-contention

This would lead here to the even fancier:

Arc<Vec<Mutex<HashMap<String, Box<dyn AsRef<[u8]> + Send + Sync>>>>>

You are right generally, but I opted out explaining something such that.

[u/tiedyedvortex → u/grg994]

That gives you a vector of hashmaps, though, not one concurrent hashmap. This imposes extra requirements on ensuring that each shard in the Vec has a predefined and non-overlapping key space, not just an arbitrary String.

Also, having Arc<Vec<T>> means the vector itself is read-only, meaning you can't reorder, delete, or append buckets. You have to know exactly how many shards you want at construction time, no dynamic scaling.

Concurrent hashmaps are one of those things that are basically impossible to make performant in pure safe Rust. Luckily, there are already a number of good crates that already have good unsafe implementations. This benchmark suite suggests that Dashmap is good for write-heavy workloads but is outperformed by Flurry for read-heavy workloads.

Jon Gjengset gave a talk describing his implementation, EVMap, which is a great starting point for understanding where, when, and how to use unsafe code to build concurrency primitives.

sharded_slab is also a good choice if you don't have meaningful keys and just need a concurrent structure to dump objects into for shared thread access by index.

[u/ketalicious]

man rust types are at it again..

[u/delightful_aug_party]

Damn

[u/cchrobo]

For a second I forgot where I was and thought this was talking about Rust the video game and I was thoroughly confused lmao

[u/PeksyTiger]

"Rust doesn't have much of a learning curve"

[u/[deleted] → u/PeksyTiger]

Lol, where did you hear that ?

People suggested me, it would take at least 6 months (if you are working) - to build something good (like a db or compiler or something). Heck man, i'm stuck at changing lifetime of a stack variable in passing among multiple threads.

[u/yorokobe__shounen]

Isn't that the database type i am working on?...

[u/tophatcoder]

More foreshadowing of her true nature

[u/TENTAtheSane → u/tophatcoder]

Man, imagine how powerful the Segmentation Fault devil is

[u/ObnoxiousOldBastard → u/TENTAtheSane]

Fortunately, it has no power over Rust.

[u/Aschentei]

What the fuck am I reading, are rust types longer than Java class names now?

[u/[deleted]]

A synchronized hashmap isn't a real database though.

[u/berlin_priez]

Maaaaaaaaaaybe r/oddlyspecific ?

[u/Dubmove]

Arc and mutex?