horon_engine/
concurrency.rs

1//! concurrency.rs - Striped locking for parallel writes to independent subtrees
2//!
3//! Provides a fixed-size array of Mutex stripes keyed by hash of parent_id.
4//! Writers to the same parent serialize (golden-angle counter consistency);
5//! writers to different parents proceed in parallel when they hit different stripes.
6
7use std::hash::{Hash, Hasher};
8use std::collections::hash_map::DefaultHasher;
9use std::sync::{Mutex, MutexGuard};
10
11/// A fixed-size array of Mutex stripes for fine-grained write serialization.
12///
13/// Hash a key to select a stripe. Two keys that hash to the same stripe
14/// serialize against each other (correctness preserved, slight throughput
15/// reduction). 64 stripes is sufficient for typical workloads.
16pub struct StripedLock<const N: usize> {
17    locks: [Mutex<()>; N],
18}
19
20impl<const N: usize> StripedLock<N> {
21    /// Create a new striped lock with N stripes.
22    pub fn new() -> Self {
23        Self {
24            locks: std::array::from_fn(|_| Mutex::new(())),
25        }
26    }
27
28    /// Acquire the stripe for the given key.
29    pub fn lock(&self, key: &str) -> MutexGuard<'_, ()> {
30        let index = Self::stripe_index(key);
31        self.locks[index].lock().unwrap_or_else(|e| e.into_inner())
32    }
33
34    /// Acquire the stripes for two keys at once, deadlock-free.
35    ///
36    /// Stripes are always taken in ascending index order, so two threads that
37    /// each need the same pair of stripes can never form a hold-and-wait
38    /// cycle. When both keys map to the **same** stripe, a single guard is
39    /// returned and the second is `None` — re-locking the same mutex would
40    /// deadlock (it is not reentrant), and one guard already serializes both
41    /// keys. The returned guards are in stripe-index order, not argument
42    /// order; callers should treat them as an opaque "hold both" token.
43    pub fn lock_two(&self, a: &str, b: &str) -> (MutexGuard<'_, ()>, Option<MutexGuard<'_, ()>>) {
44        let ia = Self::stripe_index(a);
45        let ib = Self::stripe_index(b);
46        if ia == ib {
47            return (self.locks[ia].lock().unwrap_or_else(|e| e.into_inner()), None);
48        }
49        let (lo, hi) = if ia < ib { (ia, ib) } else { (ib, ia) };
50        let g_lo = self.locks[lo].lock().unwrap_or_else(|e| e.into_inner());
51        let g_hi = self.locks[hi].lock().unwrap_or_else(|e| e.into_inner());
52        (g_lo, Some(g_hi))
53    }
54
55    /// Compute the stripe index for a key.
56    fn stripe_index(key: &str) -> usize {
57        let mut hasher = DefaultHasher::new();
58        key.hash(&mut hasher);
59        (hasher.finish() as usize) % N
60    }
61}
62
63impl<const N: usize> Default for StripedLock<N> {
64    fn default() -> Self {
65        Self::new()
66    }
67}
68
69// StripedLock is Send+Sync because Mutex<()> is Send+Sync
70unsafe impl<const N: usize> Sync for StripedLock<N> {}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_striped_lock_different_keys() {
78        let lock = StripedLock::<64>::new();
79        // Different keys should (usually) hit different stripes
80        let _g1 = lock.lock("parent_a");
81        // This shouldn't deadlock if keys hit different stripes
82        // (If they collide, this test would deadlock — extremely unlikely with 64 stripes)
83    }
84
85    #[test]
86    fn test_striped_lock_same_key_serializes() {
87        let lock = StripedLock::<64>::new();
88        {
89            let _g = lock.lock("same_parent");
90            // Lock acquired
91        }
92        // Lock released, acquire again
93        let _g2 = lock.lock("same_parent");
94    }
95}
horon_engine/concurrency.rs

horon_engine/
concurrency.rs
