A lock-free, partially wait-free, eventually consistent, concurrent hashmap.

Overview

A lock-free, partially wait-free, eventually consistent, concurrent hashmap.

This map implementation allows reads to always be wait-free on certain platforms, and almost as cheap as reading from an Arc<HashMap<K, V>>. Moreover, writes (when executed from a single thread only) will effectively be wait-free if performed sufficiently infrequently, and readers do not hold onto guards for extended periods of time.

The trade-offs for extremely cheap reads are that a write can only be executed from one thread at a time, and eventual consistency. In other words, when a write is performed, all reading threads will only observe the write once they complete their last read and begin a new one.

How is flashmap different?

The underlying algorithm used here is, in principle, the same as that used by evmap. However the implementation of that algorithm has been modified to significantly improve reader performance, at the cost of some necessary API changes and a different performance profile for the writer. More information on the implementation details of the algorithm can be found in the algorithm module, whose contents can also be found here on github.

When to use flashmap

flashmap is optimized for read-heavy to almost-read-only workloads where a single writer is acceptable. Good use-cases include:

  • High frequency reads with occational insertion/removal
  • High frequency modification of existing entries with low contention via interior mutability with occasional insertion/removal
  • High frequency reads with another thread executing a moderate write workload

Situations when not to use flashmap include:

  • Frequent, small writes which cannot be batched
  • Concurrent write access from multiple threads

Examples

use flashmap;

// Create a new map; this function returns a write handle and a read handle
// For more advanced options, see the `Builder` type
let (mut write, read) = flashmap::new::<String, String>();

// Create a write guard to modify the map
let mut write_guard = write.guard();

write_guard.insert("foo".to_owned(), "bar".to_owned());
write_guard.insert("fizz".to_owned(), "buzz".to_owned());
write_guard.insert("baz".to_owned(), "qux".to_owned());

// Publish all previous changes, making them visible to new readers. This has
// the same effect as dropping the guard.
write_guard.publish();

// You must also create a guard from a read handle to read the map, but this
// operation is cheap
assert_eq!(read.guard().get("fizz").unwrap(), "buzz");

// You can clone read handles to get multiple handles to the same map...
let read2 = read.clone();

use std::thread;

// ...and do concurrent reads from different threads
let t1 = thread::spawn(move || {
    assert_eq!(read.guard().get("foo").unwrap(), "bar");
    read
});

let t2 = thread::spawn(move || {
    assert_eq!(read2.guard().get("baz").unwrap(), "qux");
    read2
});

let read = t1.join().unwrap();
let _ = t2.join().unwrap();

// Read guards see a "snapshot" of the underlying map. You need to make a new
// guard to see the latest changes from the writer.

// Make a read guard
let read_guard = read.guard();

// Do some modifications while the read guard is still live
let mut write_guard = write.guard();

write_guard.remove("fizz".to_owned());
write_guard.replace("baz".to_owned(), |old| {
    let mut clone = old.clone();
    clone.push('!');
    clone
});

// Make changes visible to new readers
write_guard.publish();

// Since the read guard was created before the write was published, it will
// see the old version of the map
assert!(read_guard.get("fizz").is_some());
assert_eq!(read_guard.get("baz").unwrap(), "qux");

// Drop and re-make the read guard
drop(read_guard);
let read_guard = read.guard();

// Now we see the new version of the map
assert!(read_guard.get("fizz").is_none());
assert_eq!(read_guard.get("baz").unwrap(), "qux!");

// We can continue to read the map even when the writer is dropped
drop(write);
assert_eq!(read_guard.len(), 2);

// The resources associated with the map are deallocated once all read and
// write handles are dropped

// We need to drop this first since it borrows from `read`
drop(read_guard);
// Deallocates the map
drop(read);

Performance

Four performance charts are shown below. First is an almost read-only workload (2500 reads per 1 write), and the second is a read-heavy workload (50 reads per 1 write).

These benchmarks were performed on an AMD 9 Ryzen 5900X 12-core CPU (12 physical cores, 24 logical cores), which uses the x86-64 architecture. The read-heavy workload was measured using conc-map-bench, and the almost read-only workload was measured by using that crate with a modified version of bustle in order to skew the read percentage above 99%.

In the first case, we can see that throughput scales almost linearly up to the physical core count, and less so up to the logical core count. There seems to be a possibility of extreme latency spikes past the logical core count, but the cause of this has yet to be determined.

In the second use-case, both flashmap and evmap suffer as concurrency increases. This is because they are single-writer maps, so in order for multiple threads to write concurrently the writer needs to be wrapped in a mutex. The limiting factor in the read-heavy case is actually the mutex, since writes are much more expensive when compared to reads. If you need to write to the map from multiple threads, you should benchmark your code to determine whether or not you fall into the first case or second case.

Click the text that says "See ... Charts" to see the charts. You can click the text again to collapse the charts as well.

See Almost Read-Only Charts

almost-read-only-throughput almost-read-only-latency

See Read-Heavy Charts

read-heavy-throughput read-heavy-latency

You might also like...
wait-for-pid -- Wait for processes to exit

wait-for-pid -- Wait for processes to exit wait-for-pid PID is similar to the bash built-in command wait, except it works even when the processes star

🍋: A General Lock following paper
🍋: A General Lock following paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method"

Optimistic Lock Coupling from paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method" In actual projects, th

wait-free spsc linked-list queue with individually reusable nodes

A wait-free single-producer single-consumer linked-list queue with individually reusable nodes.

Garbage Collector(Hyaline- Safe Memory Reclaimation) for lock free data structures

Hyaline-SMR This crate provides garbage collection using hyaline algorithm for building concurrent data structures. When a thread removes an object fr

A lock-free thread-owned queue whereby tasks are taken by stealers in entirety via buffer swapping

Swap Queue A lock-free thread-owned queue whereby tasks are taken by stealers in entirety via buffer swapping. This is meant to be used [thread_local]

A lock-free multi-producer multi-consumer unbounded queue.

lf-queue A lock-free multi-producer multi-consumer unbounded queue. Examples [dependencies] lf-queue = "0.1" Single Producer - Single Consumer: use lf

Quinine is a Rust library that implements atomic, lock-free, but write-once versions of containers like `Box` or `Arc`

Quinine is a Rust library that implements atomic, lock-free, but write-once versions of containers like `Box` or `Arc`

A lock-free, append-only atomic pool.

A lock-free, append-only atomic pool. This library implements an atomic, append-only collection of items, where individual items can be acquired and r

A syntax exploration of eventually stable Rust Iterator items

Rust Iterator Items: a syntax exploration This crate is a thin wrapper around the unstable generator feature, allowing users to create new items that

Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention

Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention. Codemod was developed at Facebook and released as open source.

A collection (eventually) of examples that use some non-beginner things.

nannou examples A collection (eventually) of examples that use some non-beginner things. Right now the only example combines nannou's standard draw AP

parse command-line arguments into a hashmap and vec of positional args

parse command-line arguments into a hashmap and vec of positional args This library doesn't populate custom structs, format help messages, or convert types.

A hashmap implementation, which uses hashset, and keys are contained within values.

A hashmap implementation, which uses hashset, and keys are contained within values.

A HashMap/Vector hybrid: efficient, ordered key-value data storage in Rust.

hashvec A HashVec is a hash map / dictionary whose key-value pairs are stored (and can be iterated over) in a fixed order, by default the order in whi

ASURA implementation in Rust. A better alternative of consistent-hashing.
ASURA implementation in Rust. A better alternative of consistent-hashing.

ASURA implementation in Rust. A better alternative of consistent-hashing.

Wait, another virtual machine ?

WAVM WAVM, Wait, another virtual machine ?, is a register based 64 bits virtual machine written in Rust. It relies on 32 registers and 31 opcodes that

Wait for async tasks

taskwait Runtime agnostic way of waiting for async tasks. Features Done: Support for golang's WaitGroup.Add & WaitGroup.Done Done: Support for RAII ba

Tells you how many years you need to wait until your subatomic xeon crystal synchronizer has doubled in plasma inversion efficiency on the Goldberg-Moleman scale or whatever.

about Tells you how many years you need to wait until your subatomic xeon crystal synchronizer has doubled in plasma inversion efficiency on the Goldb

Tiny crate that allows to wait for a stop signal across multiple threads

Tiny crate that allows to wait for a stop signal across multiple threads. Helpful mostly in server applications that run indefinitely and need a signal for graceful shutdowns.

Comments
  • Add async support

    Add async support

    The only blocking operation in this entire crate is the synchronize method on Core. This should be able to to be readily converted into a future.

    This different API could then be exposed through an AsyncWriteHandle type. This type could offload most of its work by forwarding methods on the sync WriteHandle.

    One issue to consider is that the WriteHandle currently calls this method on drop. This is not acceptable in an async context and could cause a deadlock. This could likely be solved by offloading the work done there on drop to be done when the Core is dropped. An easy hack for this would be to add a Box<dyn FnOnce(&Self)> to Core called on drop when the async feature is enabled.

    opened by Cassy343 1
A collection (eventually) of examples that use some non-beginner things.

nannou examples A collection (eventually) of examples that use some non-beginner things. Right now the only example combines nannou's standard draw AP

Alexis Andre 19 Sep 14, 2022
A HashMap/Vector hybrid: efficient, ordered key-value data storage in Rust.

hashvec A HashVec is a hash map / dictionary whose key-value pairs are stored (and can be iterated over) in a fixed order, by default the order in whi

Skye Terran 2 May 16, 2022
Wait, another virtual machine ?

WAVM WAVM, Wait, another virtual machine ?, is a register based 64 bits virtual machine written in Rust. It relies on 32 registers and 31 opcodes that

Wafelack 61 May 2, 2022
Shuttle is a library for testing concurrent Rust code

Shuttle Shuttle is a library for testing concurrent Rust code. It is an implementation of a number of randomized concurrency testing techniques, inclu

Amazon Web Services - Labs 346 Sep 22, 2022
Cogo is a high-performance library for programming stackful coroutines with which you can easily develop and maintain massive concurrent programs.

Cogo is a high-performance library for programming stackful coroutines with which you can easily develop and maintain massive concurrent programs.

co-rs 45 Sep 16, 2022
High Assurance Rust - A free book about developing secure and robust systems software.

High Assurance Rust - A free book about developing secure and robust systems software.

Tiemoko Ballo 1k Sep 23, 2022
Free Rust 🦀 course in English 🇬🇧

Learn Rust ?? Free Rust ?? course in English ???? This course was inspired by Dcode Before starting to learn a programming language, you need to under

Skwal 10 Jul 5, 2022
Eventually consistent values for Rust

Eventuals give you the most up-to-date snapshots of some value. They are like Futures that update over time, continually resolving to an eventually co

Edge & Node 108 Aug 12, 2022
wait-free 4-level 64-bit pagetable for contiguous low-contention concurrent metadata

pagetable Wait-free 4-level page table that maps from a u64 key to an &AtomicU64 value. Page fan-out is 2^16. If a key doesn't exist, intermediate pag

Komora 17 Aug 23, 2022
Wait Service is a pure rust program to test and wait on the availability of a service.

Wait Service Wait Service is a pure rust program to test and wait on the availability of a service.

Magic Len (Ron Li) 3 Jan 18, 2022