armdb 0.5.4

sharded bitcask key-value storage optimized for NVMe
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

//! Cross-collection transaction contract (`atomic2`/`atomic3`/`atomic4`).
//!
//! Each collection family implements [`MultiTx`]. `Db::atomicN` acquires every
//! involved shard mutex in a global canonical `(collection_id, shard_id)` order,
//! runs the closure under all locks, then tears down in three phases ACROSS
//! collections: release-all-locks → sync → replay-hooks. See
//! `docs/superpowers/specs/26-06-13-armdb-cross-collection-transactions.md`.

use crate::DbResult;
use crate::Key;

/// Shards of one collection whose `should_sync()` was true at release time and
/// must be re-locked and `sync()`'d in teardown phase 2. Empty for families with
/// no per-write sync seam (Typed/Var) and for the Bitcask backend.
#[derive(Default)]
pub struct SyncNeeds(pub Vec<usize>);

impl SyncNeeds {
    pub fn none() -> Self {
        SyncNeeds(Vec::new())
    }
    pub fn push(&mut self, shard_id: usize) {
        self.0.push(shard_id);
    }
    pub fn shards(&self) -> &[usize] {
        &self.0
    }
}

/// A collection that can participate in a cross-collection transaction.
///
/// `collection_id` defaults to the collection-object address — a stable, unique
/// total order (collections live behind an `Arc`, so the address does not move).
pub trait MultiTx {
    type Key: Key;
    /// The typed handle handed to the closure. Owns this collection's locked-shard
    /// guards plus one collection-wide event log. Each family is a distinct type
    /// holding its own guard combination (durability+seize / durability+index /
    /// engine+seize / engine+index / type-erased var ptr).
    type Tx<'a>
    where
        Self: 'a;

    fn collection_id(&self) -> usize {
        self as *const Self as *const () as usize
    }

    /// Route a key to its shard (`xxh3(key) % shard_count`, honoring
    /// `shard_prefix_bits`).
    fn shard_for_key(&self, key: &Self::Key) -> usize;

    /// Create an empty transaction handle: no shards locked yet, empty event log,
    /// epoch guard entered (for families that need one).
    fn begin_tx(&self) -> Self::Tx<'_>;

    /// Lock one shard and append its guard(s) into `tx`. Called by the scheduler
    /// in global canonical order.
    fn lock_shard_into<'a>(&'a self, shard_id: usize, tx: &mut Self::Tx<'a>);

    /// Phase 1: collect shards needing sync (read `should_sync` before dropping),
    /// then release all of this collection's shard locks. The event log stays.
    fn release_locks(&self, tx: &mut Self::Tx<'_>) -> SyncNeeds;

    /// Phase 2: re-lock and `sync()` the reported shards. No-op when empty.
    fn run_sync(&self, needs: SyncNeeds) -> DbResult<()>;

    /// Phase 3: replay the collection-wide event log via the write hook, in
    /// closure order. Called only after EVERY collection has done phase 1.
    fn replay_hooks(&self, tx: Self::Tx<'_>);
}

/// Unique, ascending shard ids reached by `keys` under `shard_for`.
pub(crate) fn unique_sorted_shards<K>(keys: &[K], shard_for: impl Fn(&K) -> usize) -> Vec<usize> {
    let mut v: Vec<usize> = keys.iter().map(&shard_for).collect();
    v.sort_unstable();
    v.dedup();
    v
}