The Case for Determinism in Database Systems
📜 Abstract
Replication is a widely used method for achieving high availability in database systems. Due to the nondeterminism inherent in traditional concurrency control schemes, however, special care must be taken to ensure that replicas don’t diverge. Log shipping, eager commit protocols, and lazy synchronization protocols are well-understood methods for safely replicating databases, but each comes with its own cost in availability, performance, or consistency. In this paper, we propose a distributed database system which combines a simple deadlock avoidance technique with concurrency control schemes that guarantee equivalence to a predetermined serial ordering of transactions. This effectively removes all nondeterminism from typical OLTP workloads, allowing active replication with no synchronization overhead whatsoever. Further, our system eliminates the requirement for two-phase commit for any kind of distributed transaction, even across multiple nodes within the same replica. By eschewing deadlock detection and two-phase commit, our system under many workloads outperforms traditional systems that allow nondeterministic transaction reordering.
✨ Summary
Summary
The paper argues that database systems should reconsider nondeterministic transaction ordering for modern, short, predominantly in-memory OLTP workloads. It proposes executing transactions in a manner equivalent to a predetermined serial order, using ordered locking and an execution-to-completion rule. This design enables replicas receiving the same ordered transaction stream to reach the same state without synchronization during execution, while also avoiding deadlock detection. For distributed transactions, deterministic execution can reduce or eliminate the need for two-phase commit because failures are handled through replicated execution and recovery rather than nondeterministic transaction aborts.
The prototype experiments show that deterministic execution performs similarly to traditional two-phase locking when transactions are short and predictable, but can suffer severe queueing or “clogging” when an early transaction stalls. For partitioned TPC-C workloads with increasing numbers of multipartition transactions, however, the deterministic prototype degrades more gracefully than traditional locking because it avoids holding locks throughout two-phase commit. Transactions whose complete read/write sets are not initially known are handled through deterministic decomposition and retry; the measured cost is small when dependency records have low volatility.
Influence
The paper’s ideas were developed further in Calvin: Fast Distributed Transactions for Partitioned Database Systems (SIGMOD 2012), which explicitly uses deterministic ordering, deterministic locking, replication of transaction inputs, and elimination of distributed commit protocols to support scalable distributed ACID transactions. (15799.courses.cs.cmu.edu) The authors’ subsequent 2014 experimental study evaluated the advantages and disadvantages of deterministic database systems, confirming deadlock avoidance as a major performance benefit while documenting costs involving execution flexibility, overload handling, preprocessing, and transactions whose accessed data is not known in advance. (cs.umd.edu)
Subsequent deterministic database research, including work on workload-aware partitioning and blockchain-oriented transaction systems, continues to cite the paper as an early formulation of deterministic transaction processing for replication and distributed execution. (cs.nthu.edu.tw) The available evidence supports clear influence on later research prototypes and system designs, especially Calvin; it does not by itself establish broad commercial adoption of the specific prototype described in this paper.