lock-db
_{^{LOCK MANAGER & DEADLOCK DETECTION}}

lock-db is the lock manager for a transactional database: the component that lets many transactions touch shared data at once without corrupting it, and that notices when they have deadlocked and breaks the tie.

It provides row and range locks across multiple granularities (database, table, page, row) with the standard lock modes and a compatibility matrix, and it builds a wait-for graph to detect deadlock cycles and select a victim to abort.

---

MSRV is 1.85+ (Rust 2024 edition). Row/range locks. Hierarchical granularity. Wait-for deadlock detection.

Status: stable. v1.1.0. The public API is stable until 2.0; 1.x releases only add to it. The feature set is complete (the five MGL modes, hierarchical and range locks, wait queues, and wait-for deadlock detection), verified by property, loom, and adversarial-contention / deadlock-storm stress suites, and green across Linux, macOS, and Windows.

---

What it does

• Lock modes — the five standard multi-granularity modes — intention-shared (IS), intention-exclusive (IX), shared (S), shared-intention-exclusive (SIX), and exclusive (X) — with a const compatibility matrix at the core of every grant decision
• Hierarchical granularities — lock a database / table / page / row hierarchy correctly with intention locks; the manager enforces the matrix at every level
• Range locks — lock a contiguous span of keys (KeyRange) for predicate / phantom protection, with overlap-based conflict detection
• Deadlock detection: a wait-for graph with cycle detection and victim selection; the deadlock-aware request queues waits first in, first out, checks only the part of the graph the new wait can reach, and fences the chosen victim until it has rolled back; WaitForGraph is reusable on its own
• Sharded lock table — the resource space is partitioned across independent shards so acquisitions on unrelated resources never contend on the same mutex
• Acquire / release — non-blocking try_acquire, single and bulk release, re-entrant acquisition, and lattice upgrades (e.g. S + IX → SIX)

---

Installation

[dependencies]
lock-db = "1"

Quick Start

use lock_db::prelude::*;

// One manager, shared across all worker threads behind an `Arc`.
let lm = LockManager::new();
let row = ResourceId::new(1);
let (writer, reader) = (TxnId::new(1), TxnId::new(2));

// The writer takes the row exclusively.
lm.try_acquire(writer, row, LockMode::Exclusive).unwrap();

// A concurrent reader is refused while the write lock is held.
assert_eq!(lm.try_acquire(reader, row, LockMode::Shared), Err(LockError::Conflict));

// Once the writer commits and releases, the reader gets in.
lm.release(writer, row).unwrap();
lm.try_acquire(reader, row, LockMode::Shared).unwrap();

Range-lock a span of keys to keep another transaction from inserting into it (phantom protection):

use lock_db::prelude::*;

let lm = LockManager::new();
let index = ResourceId::new(10); // the key space being protected

// Txn 1 read-locks keys [100, 200].
lm.try_acquire_range(TxnId::new(1), index, KeyRange::new(100, 200).unwrap(), LockMode::Shared).unwrap();

// Txn 2 cannot write key 150 inside that range, but a disjoint range is free.
assert!(lm.try_acquire_range(TxnId::new(2), index, KeyRange::point(150), LockMode::Exclusive).is_err());
lm.try_acquire_range(TxnId::new(2), index, KeyRange::new(201, 300).unwrap(), LockMode::Exclusive).unwrap();

A transaction drops its whole lock set — point and range — in one call at commit or abort:

use lock_db::prelude::*;

let lm = LockManager::new();
let txn = TxnId::new(1);
for id in 0..3 {
    lm.try_acquire(txn, ResourceId::new(id), LockMode::Exclusive).unwrap();
}
assert_eq!(lm.release_all(txn), 3);

The deadlock-aware request records waits and reports cycles, naming a victim to abort:

use lock_db::prelude::*;

let lm = LockManager::new();
let (a, b) = (ResourceId::new(1), ResourceId::new(2));
let (t1, t2) = (TxnId::new(1), TxnId::new(2));

lm.request(t1, a, LockMode::Exclusive); // T1 holds A
lm.request(t2, b, LockMode::Exclusive); // T2 holds B
lm.request(t1, b, LockMode::Exclusive); // T1 waits for T2

// T2 waiting for A closes the cycle; abort the victim to break it.
if let Acquisition::Deadlock(d) = lm.request(t2, a, LockMode::Exclusive) {
    lm.release_all(d.victim);
}

When the victim is another transaction, its own thread is told on its next call: request returns Acquisition::Deadlock naming it, and try_acquire returns LockError::Aborted, until it rolls back and calls release_all on itself. is_aborted lets it ask directly.

API Overview

For the complete reference with method tables and examples, see docs/API.md.

• LockMode — the five MGL modes and the compatibility matrix
• LockManager — the sharded lock table (point locks, range locks, deadlock-aware request)
• WaitForGraph — wait-for graph, cycle detection, and victim selection
• KeyRange — an inclusive key interval for range locks
• TxnId and ResourceId — opaque identifiers
• LockError — failure modes

Examples

Runnable examples live in examples/. Run any of them with cargo run --example <name>:

Example	Shows
quick_start	Acquire, conflict, release on a single row.
two_phase_locking	Growing-phase acquires, then release_all at commit.
shared_upgrade	Read under a shared lock, then upgrade to exclusive.
hierarchy	Intention locks over a database/table/page/row hierarchy.
range_locks	Range locking for phantom protection.
deadlock	Wait-for deadlock detection and victim abort.
concurrent	Many threads contending on one row, with a mutual-exclusion check.

---

Where It Fits

lock-db is a pessimistic concurrency-control layer for a transaction or storage engine to build on. No published crate in this collection depends on it yet: txn-db uses optimistic multi-version concurrency control instead, and page-db and index-db do not take locks from it. Typical uses are row and table locks for two-phase locking, page locks over a paged store, and range locks over B+tree key ranges for phantom protection.

It has no first-party dependencies, so it builds and tests standalone.

Cross-Platform Support

Linux (x86_64, aarch64), macOS (x86_64, Apple Silicon), and Windows (x86_64) are first-class and verified by the CI matrix.

Contributing

See CONTRIBUTING.md and dev/DIRECTIVES.md. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.

License

Licensed under either of

• Apache License, Version 2.0 — LICENSE-APACHE
• MIT License — LICENSE-MIT

at your option.

^{COPYRIGHT © 2026 JAMES GOBER.}