Crate crossbeam_skiplist[−][src]

Concurrent maps and sets based on skip lists.

This crate provides the types SkipMap and SkipSet. These data structures provide an interface similar to BTreeMap and BTreeSet, respectively, except they support safe concurrent access across multiple threads.

Concurrent access

SkipMap and SkipSet implement Send and Sync, so they can be shared across threads with ease.

Methods which mutate the map, such as insert, take &self rather than &mut self. This allows them to be invoked concurrently.

use crossbeam_skiplist::SkipMap;
use crossbeam_utils::thread::scope;

let person_ages = SkipMap::new();

scope(|s| {
    // Insert entries into the map from multiple threads.
    s.spawn(|_| {
        person_ages.insert("Spike Garrett", 22);
        person_ages.insert("Stan Hancock", 47);
        person_ages.insert("Rea Bryan", 234);

        assert_eq!(person_ages.get("Spike Garrett").unwrap().value(), &22);
    });
    s.spawn(|_| {
        person_ages.insert("Bryon Conroy", 65);
        person_ages.insert("Lauren Reilly", 2);
    });
}).unwrap();

assert!(person_ages.contains_key("Spike Garrett"));
person_ages.remove("Rea Bryan");
assert!(!person_ages.contains_key("Rea Bryan"));

Concurrent access to skip lists is lock-free and sound. Threads won’t get blocked waiting for other threads to finish operating on the map.

Be warned that, because of this lock-freedom, it’s easy to introduce race conditions into your code. For example:

use crossbeam_skiplist::SkipSet;
use crossbeam_utils::thread::scope;

let numbers = SkipSet::new();
scope(|s| {
    // Spawn a thread which will remove 5 from the set.
    s.spawn(|_| {
        numbers.remove(&5);
    });

    // While the thread above is running, insert a value into the set.
    numbers.insert(5);

    // This check can fail!
    // The other thread may remove the value
    // before we perform this check.
    assert!(numbers.contains(&5));
}).unwrap();

In effect, a single operation on the map, such as insert, operates atomically: race conditions are impossible. However, concurrent calls to functions can become interleaved across threads, introducing non-determinism.

To avoid this sort of race condition, never assume that a collection’s state will remain the same across multiple lines of code. For instance, in the example above, the problem arises from the assumption that the map won’t be mutated between the calls to insert and contains. In sequential code, this would be correct. But when multiple threads are introduced, more care is needed.

Note that race conditions do not violate Rust’s memory safety rules. A race between multiple threads can never cause memory errors or segfaults. A race condition is a logic error in its entirety.

Mutable access to elements

SkipMap and SkipSet provide no way to retrieve a mutable reference to a value. Since access methods can be called concurrently, providing e.g. a get_mut function could cause data races.

A solution to the above is to have the implementation wrap each value in a lock. However, this has some repercussions:

Instead, the approach taken by this crate gives more control to the user. If mutable access is needed, then you can use interior mutability, such as RwLock: SkipMap<Key, RwLock<Value>>.

Garbage collection

A problem faced by many concurrent data structures is choosing when to free unused memory. Care must be taken to prevent use-after-frees and double-frees, both of which cause undefined behavior.

Consider the following sequence of events operating on a SkipMap:

What happens here? If the map implementation frees the memory belonging to a value when it is removed, then a user-after-free occurs, resulting in memory corruption.

To solve the above, this crate uses the epoch-based memory reclamation mechanism implemented in crossbeam-epoch. Simplified, a value removed from the map is not freed until after all references to it have been dropped. This mechanism is similar to the garbage collection found in some languages, such as Java, except it operates solely on the values inside the map.

This garbage collection scheme functions automatically; users don’t have to worry about it. However, keep in mind that holding Entry handles to entries in the map will prevent that memory from being freed until at least after the handles are dropped.

Performance versus B-trees

In general, when you need concurrent writes to an ordered collection, skip lists are a reasonable choice. However, they can be substantially slower than B-trees in some scenarios.

The main benefit of a skip list over a RwLock<BTreeMap> is that it allows concurrent writes to progress without mutual exclusion. However, when the frequency of writes is low, this benefit isn’t as useful. In these cases, a shared BTreeMap may be a faster option.

These guidelines should be taken with a grain of salt—performance in practice varies depending on your use case. In the end, the best way to choose between BTreeMap and SkipMap is to benchmark them in your own application.

Alternatives

This crate implements ordered maps and sets, akin to BTreeMap and BTreeSet. In many situations, however, a defined order on elements is not required. For these purposes, unordered maps will suffice. In addition, unordered maps often have better performance characteristics than their ordered alternatives.

Crossbeam does not currently provide a concurrent unordered map. That said, here are some other crates which may suit you:

Examples

SkipMap basic usage:

use crossbeam_skiplist::SkipMap;

// Note that the variable doesn't have to be mutable:
// SkipMap methods take &self to support concurrent access.
let movie_reviews = SkipMap::new();

// Insert some key-value pairs.
movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
movie_reviews.insert("The Godfather",      "Very enjoyable.");
movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");

// Get the value associated with a key.
// get() returns an Entry, which gives
// references to the key and value.
let pulp_fiction = movie_reviews.get("Pulp Fiction").unwrap();
assert_eq!(*pulp_fiction.key(), "Pulp Fiction");
assert_eq!(*pulp_fiction.value(), "Masterpiece.");

// Remove a key-value pair.
movie_reviews.remove("The Blues Brothers");
assert!(movie_reviews.get("The Blues Brothers").is_none());

// Iterate over the reviews. Since SkipMap
// is an ordered map, the iterator will yield
// keys in lexicographical order.
for entry in &movie_reviews {
    let movie = entry.key();
    let review = entry.value();
    println!("{}: \"{}\"", movie, review);
}

SkipSet basic usage:

use crossbeam_skiplist::SkipSet;

let books = SkipSet::new();

// Add some books to the set.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

// Check for a specific one.
if !books.contains("The Winds of Winter") {
   println!("We have {} books, but The Winds of Winter ain't one.",
            books.len());
}

// Remove a book from the set.
books.remove("To Kill a Mockingbird");
assert!(!books.contains("To Kill a Mockingbird"));

// Iterate over the books in the set.
// Values are returned in lexicographical order.
for entry in &books {
    let book = entry.value();
    println!("{}", book);
}

Modules

base

A lock-free skip list. See SkipList.

map

An ordered map based on a lock-free skip list. See SkipMap.

set

A set based on a lock-free skip list. See SkipSet.

Structs

SkipList

A lock-free skip list.

SkipMap

An ordered map based on a lock-free skip list.

SkipSet

A set based on a lock-free skip list.