Source: Dissertation Abstracts International, Volume: 75-05(E), Section: B.

Adviser: Daniel J. Abadi.

The concurrency control mechanisms traditionally used in database systems to support ACID transactions are highly nondeterministic. They allow (and often cause) in-progress transactions to abort for reasons unrelated to transaction logic, such as deadlock, hardware failures, and other unpredictable events.

We propose an alternative approach to concurrency control that emulates a deterministic serial execution of an (explicitly logged) input sequence of transaction requests. In a database system using a deterministic concurrency control protocol, all system replicas that use the same transaction input log remain strongly consistent with no further synchronization. Distributed transactions that span multiple shards within a replica may also eschew the distributed commit protocols required by traditional nondeterministic database systems, reducing lock contention and thereby ameliorating one of the main hurdles to building horizontally scalable transactional database systems.

To explore the possibilities opened by deterministic transaction processing, we implemented Calvin, a distributed transaction scheduling and replication management system that connects a deterministic concurrency control engine to a pluggable storage backend. Calvin scales near-linearly on clusters of commodity machines and supports strongly consistent Paxos-based replication---including across geographically distant datacenters---at no cost to transactional throughput. We demonstrate these performance characteristics first in the context of standard OLTP database benchmarks, and then by using Calvin to build a scalable metadata management subsystem for a highly available filesystem.

We also observe that system components in Calvin operate more independently from one another than those in standard, monolithic database systems, encouraging more modular database system designs.