Calvin

Implementation of the Calvin deterministic transaction protocol from Thomson et al., SIGMOD 2012.

Calvin: Fast Distributed Transactions for Partitioned Database Systems

---

What it is

Calvin separates transaction ordering from execution. A sequencer layer assigns a globally deterministic order to all transactions before any locks are acquired. Every node independently executes the same log in the same order and arrives at the same final state. No two-phase commit, no distributed deadlocks.

This implementation covers the full paper architecture:

• Sequencer with 10ms epoch batching
• Deterministic lock manager
• 5-phase execution pipeline
• Key-value storage over PostgreSQL
• Multi-partition routing with consistent hashing
• Async replication with Paxos-lite batch agreement
• OLLP for dependent transactions
• Disk prefetching simulation
• Zig-Zag checkpointing and log-based recovery
• Metrics collection (throughput, contention, lock wait times)
• TPC-C New Order and contention microbenchmarks

---

Stack

Component	Version
Python	3.11
FastAPI	0.115
SQLAlchemy	2.0
PostgreSQL	16
Docker Compose	3.8

---

Running

docker compose up --build

Server starts at http://localhost:8000. A second replica runs at http://localhost:8001.

# health check
curl http://localhost:8000/health

# submit a transaction
curl -X POST http://localhost:8000/sequencer/submit \
  -H "Content-Type: application/json" \
  -d '{"read_set": ["key:a"], "write_set": {"key:a": "1"}}'

# metrics
curl http://localhost:8000/metrics

---

Tests

docker compose exec app pytest

274 tests covering correctness, determinism, replication convergence, OLLP restart logic, checkpointing, and recovery.

---

Benchmarks

# full suite (writes RESULTS.md)
docker compose exec app python -m benchmarks.run_all

# quick mode
docker compose exec app python -m benchmarks.run_all --quick

# TPC-C New Order only
docker compose exec app python -m benchmarks.tpcc_new_order --warehouses 2 --duration 10

# contention sweep
docker compose exec app python -m benchmarks.contention_bench --sweep

See RESULTS.md for the latest run.

---

Benchmark Environment

Results in RESULTS.md were produced on:

Machine	Apple M1 (8-core, 16 GB RAM)
OS	macOS 15.7.3
Deployment	Single-node Docker Compose (app + PostgreSQL in separate containers)
Storage	In-container PostgreSQL, no persistence volume
Concurrency	2 submitter threads, 4 executor worker threads

The paper's figures come from 100-node Amazon EC2 High-CPU Extra-Large deployments with in-memory storage. Absolute TPS numbers are not comparable. Scaling behavior and qualitative claims hold.

---

Paper Claims

Claim	Status
No 2PC: zero coordination messages on multi-partition commits	Validated (commit 16)
2PC incurs ~200x slowdown at contention index 0.01	Validated, model produces 201x
Calvin throughput degrades gradually; 2PC collapses	Validated, sweep shows 12-77 TPS vs 2PC collapsing to 0
Near-linear scaling with node count	Not testable on single machine
~500K TPC-C TPS on 100 nodes	Not testable on single machine

---

Structure

app/
  sequencer/       epoch batching, global transaction log
  scheduler/       deterministic lock manager, scheduler loop
  executor/        5-phase pipeline, worker pool
  storage/         PostgreSQL CRUD, partition schemas
  partition/       consistent hash routing, partition registry
  replication/     async replicator, Paxos sequencer, consistency checker
  ollp/            reconnaissance queries, staleness detection
  prefetch/        access tracking, cold-read simulation
  checkpoint/      Zig-Zag checkpointer, recovery
  metrics/         throughput, contention, lock wait times
benchmarks/
  tpcc_new_order.py    TPC-C New Order microbenchmark
  contention_bench.py  contention sweep, 2PC comparison model
  run_all.py           full suite, writes RESULTS.md
  report.py            RESULTS.md formatter
tests/
RESULTS.md