Concurrent Ledger

A concurrency study rather than a database. The ledger supports transfer(from, to, amount) and getBalance(id), and must guarantee no lost updates, no partial transfers, no deadlocks, and linearizable transfers. The sum of all balances must never change.

Four implementations

1. Global lock. A single ReentrantLock. Trivially correct and fully serialized, so it serves as the baseline.
2. Per-account locks with deterministic ordering. Lock the smaller ID, then the larger one. Strict global ordering makes it deadlock-free. This is the main correct implementation.
3. Striped locks. A fixed pool of locks. Fewer lock objects, but it adds contention between accounts that share a stripe.
4. CAS. AtomicLong per account with rollback and retry. Kept for comparison only, since debit and credit are not atomic across accounts.

Verification and benchmarks

A stress harness runs 16+ threads through tens of millions of transfers, under both uniform and 90%-hotspot workloads, and checks the invariant by locking all accounts in order. JMH measures throughput from 1 to 32 threads.

What it showed

• Fine-grained locking localizes contention. It does not eliminate it.
• CAS is not a substitute for multi-entity atomicity.
• Under skew, optimistic concurrency degrades more sharply than blocking locks.
• Deterministic lock ordering removes deadlocks without any global coordination.