Expand description

A library for high concurrency reads.

This library is named after the 2 (identical) tables that are held internally:

  • Active - this is the table that all Readers view. This table will never be write locked, so readers never face contention.
  • Standby - this is the table that writers mutate. A writer should face minimal contention retrieving this table since Readers move to the Active table whenever calling .read().

There are 2 ways to use this crate:

  1. Direct interaction with AsLock/AsLockHandle. This is more flexible since users can pass in any struct they want and mutate it however they choose. All updates though, will need to be done by passing a function instead of via mutable methods (UpdateTables trait).
  2. Using collections which are built out of the primitives but which provide an API similar to RwLock<T>; writers can directly call to methods without having to provide a mutator function.

There are 2 flavors/modules:

  1. Lockless - this variant trades off increased performance against changing the API to be less like a RwLock. This centers around the AsLockHandle, which is conceptually similar to Arc<RwLock> (requires a separate AsLockHandle per thread/task).
  2. Sync - this centers around using an AsLock, which is meant to feel like a RwLock. The main difference is that you still cannot gain direct write access to the underlying table due to the need to keep them identical.

The cost of minimizing contention is:

  1. Memory - Internally there are 2 copies of the underlying type the user created. This is needed to allow there to always be a table that Readers can access out without contention.
  2. CPU - The writer must apply all updates twice, once to each table. Lock contention for the writer should be less than with a plain RwLock due to Readers using the active_table, so it’s possible that write times themselves will drop.

Example

Example of the 3 usage patterns: build your own wrapper, use prebuilt collections, and use the primitives. Each of these can be done with both sync and lockless.

use std::thread::sleep;
use std::time::Duration;
use std::sync::Arc;

// Create wrapper class so that users can interact with the active_standby
// struct via a RwLock-like interface. See the implementation of the
// collections for more examples.
mod wrapper {
    use active_standby::UpdateTables;

    active_standby::generate_lockless_aslockhandle!(i32);

    struct AddOne {}

    impl<'a> UpdateTables<'a, i32, ()> for AddOne {
        fn apply_first(&mut self, table: &'a mut i32) {
            *table = *table + 1;
        }
        fn apply_second(mut self, table: &mut i32) {
            self.apply_first(table);
        }
    }

    // Client's must implement the mutable interface that they want to
    // offer users. Non mutable functions are automatic via Deref.
    impl<'w> AsLockWriteGuard<'w> {
        pub fn add_one(&mut self) {
            self.guard.update_tables(AddOne {})
        }
    }
}

pub fn run_wrapper() {
    let table = wrapper::AsLockHandle::new(0);
    let table2 = table.clone();

    let handle = std::thread::spawn(move || {
        while *table2.read() != 1 {
            sleep(Duration::from_micros(100));
        }
    });

    table.write().add_one();
    handle.join();
}

// Use a premade collection which wraps `AsLock<Vec<T>>`, to provide an
// interface akin to `RwLock<Vec<T>>`.
pub fn run_collection() {
    use active_standby::sync::collections::AsVec;
 
    let table = Arc::new(AsVec::default());
    let table2 = Arc::clone(&table);

    let handle = std::thread::spawn(move || {
        while *table2.read() != vec![1] {
            sleep(Duration::from_micros(100));
        }
    });

    table.write().push(1);
    handle.join();
}

// Use the raw AsLock interface to update the underlying data.
pub fn run_primitive() {
    use active_standby::sync::AsLock;

    // If the entries in your table are large, you may want to hold only
    // 1 copy shared by both tables. This is safe so long as you never
    // mutate the shared data; only remove and replace it in the table.
    let table = Arc::new(AsLock::new(vec![Arc::new(1)]));
    let table2 = Arc::clone(&table);

    let handle = std::thread::spawn(move || {
        while *table2.read() != vec![Arc::new(2)] {
            sleep(Duration::from_micros(100));
        }
    });

    table.write().update_tables_closure(|table| {
        // Update the entry in the table, not the shared value behind the
        // Arc.
        table[0] = Arc::new(2);
    });
    handle.join();
}

fn main() {
    run_wrapper();
    run_collection();
    run_primitive();
}

Testing

There are a number of tests that come with active_standby (see tests/tests_script.sh for examples):

unittests

benchmarks

loom

LLVM Sanitizers

Miri

Rudra

Modules

Macros

Check that both tables equal the expected value.

These macros automatically generates an easy to use interface for interacting with an ActiveStandby data structure. Note that this is done for each underlying table, as opposed to an RwLock which is generic over all underlying types.

These macros automatically generates an easy to use interface for interacting with an ActiveStandby data structure. Note that this is done for each underlying table, as opposed to an RwLock which is generic over all underlying types.

Traits

Operations that update underlying data. Users mutate the tables by implementing this trait for each function to be performed on the tables. For examples check the README (or implementation of collections).