Module txn_lock::semaphore

A futures-aware semaphore used to maintain the ACID compliance of a mutable data store.

This differs from tokio::sync::Semaphore by tracking read and write reservations rather than a single atomic integer. This is because of the additional logical constraints of a transactional resource– a write permit blocks future read permits and a read permit conflicts with past write permits.

More information: https://en.wikipedia.org/wiki/ACID

Example:

use std::ops::Range;

use collate::Collator;

use txn_lock::semaphore::*;
use txn_lock::Error;

let collator = Collator::default();
let semaphore = Semaphore::<u64, Collator<usize>, Range<usize>>::new(collator);

// Multiple overlapping read permits within a transaction are fine
let permit0_1 = semaphore.try_read(0, 0..1).expect("read 0..1");
let permit0_2 = semaphore.try_read(0, 0..1).expect("read 0..1");
// And non-overlapping write permits are fine
let permit0_3 = semaphore.try_write(0, 2..3).expect("write 2..3");
// But an overlapping write permit in the same transaction will block
assert_eq!(semaphore.try_write(0, 0..2).unwrap_err(), Error::WouldBlock);
std::mem::drop(permit0_1);
assert_eq!(semaphore.try_write(0, 0..2).unwrap_err(), Error::WouldBlock);
std::mem::drop(permit0_2);
// Until all overlapping permits are dropped
let permit0_3 = semaphore.try_write(0, 0..2).expect("write 0..2");

// Finalizing a transaction will un-block permits for later transactions
// It's the caller's responsibility to make sure that data can't be mutated after finalizing
semaphore.finalize(&0, false);

// Now permits for later transactions are un-blocked
let permit1 = semaphore.try_read(1, 1..2).expect("permit");
// Acquiring a write permit is fine even if there's a read permit in the past
let permit2 = semaphore.try_write(2, 1..3).expect("permit");
// But it will block all permits for later transactions
assert_eq!(semaphore.try_read(3, 1..4).unwrap_err(), Error::WouldBlock);

// To prevent a memory leak, finalize all transactions earlier than the given ID
semaphore.finalize(&2, true);

// Now later permits are un-blocked
let permit3 = semaphore.try_write(3, 1..4).expect("permit");
// And trying to write-lock the past will result in a conflict error
assert_eq!(semaphore.try_write(2, 2..3).unwrap_err(), Error::Conflict);

// It's still allowed to acquire a write permit for later transactions
// if the range doesn't overlap with any other reservations
let permit4 = semaphore.try_write(4, 4..5).expect("permit");

Structs

• PermitRead
  A permit to read a specific section of a transactional resource
• PermitWrite
  A permit to write to a specific section of a transactional resource
• Semaphore
  A semaphore used to maintain the ACID compliance of transactional resource