- Atlas
- Computer Science
- Distributed Databases
Distributed Databases
A distributed database is a database whose data is stored on more than one computer, yet which is meant to be used as if it were a single database.
8 frameworks, from 1978 to today · Databases · Computer Science
- Distributed transaction 1978-Present
- Distributed Query Processing 1979-Present
- Parallel database 1979-Present
- Fragmentation and Replication Design 1980-Present
- Distributed Systems Correctness Theory 1985-Present
- Consensus-Based Replicated State 1989-Present
- Eventual Consistency and NoSQL Data Models 2006-Present
- NewSQL 2012-Present
Overview
A distributed database is a database whose data is stored on more than one computer, yet which is meant to be used as if it were a single database12. That simple-sounding goal is the source of the field's hardest problems. If a customer's account balance lives on a machine in Frankfurt and the transfer that debits it runs on a machine in Singapore, how does the system keep the two from disagreeing? If one site crashes mid-update, what happens to the half-finished work? And how does a query that needs data from five sites get answered without dragging every row across the network? Distributed databases are the branch of database systems that builds answers to these questions. Its history is a long negotiation between two demands that pull in opposite directions: correctness, which wants machines to coordinate closely, and availability and speed, which want them to act alone.
Sharing files and the first distributed systems
The idea of spreading data across machines is older than the database. In the 1970s, researchers at Xerox PARC built experimental systems for sharing files and computing across networked computers, and the ARPANET connected university machines into a working network. These projects established a basic vocabulary: a site (one machine in the network), a distributed system (several sites cooperating), and the problem of keeping copies of the same data consistent when the network can fail or partition. The database community inherited that vocabulary and added its own: transactions, schemas, and queries.
Distributed query processing
The first distinctly database problem was how to answer a query when the data is scattered. In a centralized database, the optimizer chooses among indexes and join orders. In a distributed one, it must also decide where to run each piece of the work and how much data to move. The classic formulation came from the System R project at IBM's San Jose research laboratory in the late 1970s and early 1980s, a distributed descendant of the influential System R. Its insight was that a query plan could be split into fragments executed at different sites, with the optimizer estimating the cost of shipping intermediate results over the network. A join between two large tables at different sites might be cheaper to run by sending one table to the other site than by sending both to a third. This was distributed query processing*: the same declarative query, planned against a model that includes network cost.
The approach made possible a genuinely useful property: a user could write one query against a logically single database and let the system decide how to gather the answer. It also exposed a new difficulty, because the optimizer's cost estimates now depended on network speeds and site loads that change from moment to moment.
Fragmentation and replication
For distributed query processing to have anything to optimize, the data itself had to be laid out deliberately. Two techniques became standard. Fragmentation splits a table into pieces stored at different sites—horizontally, by rows (all customers in one region at one site), or vertically, by columns3. Replication keeps copies of the same data at several sites, so that a query can be answered locally and so that a failed site does not take its data with it. The design question—how to fragment and where to place replicas to balance query cost, update cost, and failure tolerance—was worked out in the 1980s and remains the core of distributed database design. Replication is also where the field's central tension first bites: reading a local copy is fast, but every copy must eventually agree with the others.
Distributed transaction management
The harder problem was correctness. A transaction is a group of operations that must behave as one indivisible unit: either all of its effects happen or none do, and concurrent transactions must not interfere. In a single machine this is hard enough. Across sites it becomes a coordination problem, because a transaction may touch data at several sites and any of them may fail.
The canonical solution is two-phase commit, developed in the late 1970s and early 1980s. A coordinator asks every participating site whether it can commit; if all say yes, the coordinator tells them all to commit; if any says no or fails to answer, everyone aborts4. The protocol guarantees atomicity across sites, at the price of blocking: if the coordinator crashes after some sites have committed, the others may be stuck waiting. Researchers spent years refining variants and recovery procedures to reduce that window.
Running transactions concurrently across sites raised a second question: when is a schedule of interleaved operations serializable, meaning its outcome is equivalent to running the transactions one at a time? The theory of serializability, developed in the late 1970s, gave precise conditions, and distributed versions added rules for ordering operations across sites—typically through timestamps or a global lock manager. This body of work, sometimes called distributed systems correctness theory, supplied the field with its standards of proof: a protocol was acceptable only if it could be shown to preserve atomicity and serializability under stated failure assumptions.
Database machines and parallel architecture
A parallel strand ran alongside the distributed one. In the late 1970s and 1980s, database machines were special-purpose hardware designed to do database work directly—filtering and joining data as it streamed off disks—rather than routing everything through a general-purpose processor. Most of these machines did not survive commercially, but the research taught the field how to exploit parallelism. The lesson carried into parallel database architecture: shared-memory systems, where processors share one memory; shared-disk systems, where they share storage but not memory; and shared-nothing systems, where each processor has its own memory and disks and communicates only by messages1. The shared-nothing design, popularized by Teradata's systems and by research prototypes such as Gamma at the University of Wisconsin in the 1980s, became the template for scaling databases by adding machines. Its techniques—partitioning data across nodes and pushing work to where the data sits—are the direct ancestors of today's large analytical systems.
Consensus and replicated state
The 1980s and 1990s also produced the theoretical machinery for keeping replicas in agreement. The problem is consensus: how can a set of machines, some of which may crash or be slow, agree on a single sequence of decisions? The Paxos protocol, circulated by Leslie Lamport in the late 1980s and published in 1998, gave a famously subtle answer that tolerates a minority of failures. It was later joined by Raft, published in 2014 with an emphasis on understandability. Consensus-based replication uses such a protocol to order every write, so that all replicas apply the same operations in the same order and stay identical. The cost is coordination: a write must wait for a majority of replicas to acknowledge it. For decades this was considered too slow for ordinary databases, and consensus lived mostly in specialized systems and in theory.
NoSQL and eventual consistency
The 2000s changed the calculus. Web companies faced volumes of data and numbers of users that single large machines could not handle, and they were willing to trade strict consistency for availability. The CAP theorem, formulated by Eric Brewer in 2000 and proved by Seth Gilbert and Nancy Lynch in 2002, stated that a distributed system facing a network partition must choose between consistency and availability. The NoSQL movement of the late 2000s took the availability side. Systems such as Amazon's Dynamo (described in a 2007 paper) and Google's Bigtable (2006) stored data as key–value pairs or wide columns and embraced eventual consistency: replicas might temporarily disagree, but if updates stop, they converge. The trade was explicit—fast local reads and writes, no global coordination, and application code that must tolerate stale or conflicting data. This was a genuine break with the transaction-centric tradition, and it made distributed storage practical at internet scale.
NewSQL and globally consistent distributed SQL
The break did not last as a clean division. By the 2010s, many applications wanted both scale and the familiar guarantees of SQL and transactions. NewSQL systems answered by combining shared-nothing distribution with strong consistency, using consensus protocols to replicate data and a distributed transaction protocol to keep multi-row operations atomic. Google's Spanner, described in 2012, was the landmark: it used replicated, consensus-ordered data and a clock-synchronization service to assign globally meaningful timestamps, enabling externally consistent transactions across continents. CockroachDB and TiDB, both open-source and launched in the mid-2010s, followed similar designs. The result was a class of globally consistent distributed SQL databases: they scale horizontally like NoSQL stores but keep the serializable transactions and relational model that the older tradition had defended.
The present
Today the field's main approaches descend directly from these strands. Large analytical systems use shared-nothing partitioning and distributed query processing. Operational systems increasingly use consensus-based replication and distributed transactions, whether in cloud-managed relational databases or in NewSQL engines. Eventual consistency remains the right choice where availability matters more than immediate agreement, and many systems now offer a spectrum—tunable consistency levels, or strong guarantees for some data and weaker ones for the rest. The open questions are old ones in new clothes: how to reduce the latency cost of coordination without giving up correctness; how to make failure recovery predictable when a coordinator dies mid-commit; and how to keep query optimizers honest when the network and the machines beneath them are constantly changing. The tension between acting alone and agreeing together has not been resolved—it has been engineered into a range of workable compromises.
References
- Database (Classification terms), Wikipedia
- Distributed database, Wikipedia
- Shard (database architecture), Wikipedia
- Two-phase commit protocol, Wikipedia
The frameworks of Distributed Databases
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1978-Present
Distributed transaction
How can a transaction stay atomic across many machines?
- 1979-Present
- 1979-Present
- 1980-Present
Fragmentation and Replication Design
How should data be split and copied across sites?
- 1985-Present
Distributed Systems Correctness Theory
When is a concurrent execution correct?
- 1989-Present
Consensus-Based Replicated State
How can machines agree despite failures?
- 2006-Present
Eventual Consistency and NoSQL Data Models
Can we trade consistency for speed and availability?
- 2012-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Distributed Systems Correctness Theory grew out of Distributed transaction
Distributed correctness theory grew directly out of distributed transaction management: serializability theory and two-phase commit were formalized into general correctness conditions for distributed schedules and failure assumptions.
Carried by Philip A. Bernstein; Vassos Hadzilacos; Nathan Goodman.
NewSQL influenced by Consensus-Based Replicated State
NewSQL architectures use consensus protocols to replicate data and order writes, directly taking Paxos and Raft from consensus-based replicated state and embedding them in a distributed SQL database.
Carried by Spanner (2012); Raft (2014).
Distributed Query Processing influenced by Distributed transaction
System R* at IBM San Jose extended the System R transaction and query machinery to a distributed setting, so distributed query processing inherited the transaction model and the assumption that queries run inside atomic transactions across sites.
Carried by System R*; Patricia Selinger.
Fragmentation and Replication Design influenced by Distributed transaction
Replication design had to account for the cost of keeping copies consistent, a problem framed by distributed transaction management: update propagation and atomicity across replicas were treated as transaction problems in the design literature of the early 1980s.
Carried by Stefano Ceri; Giuseppe Pelagatti.
Eventual Consistency and NoSQL Data Models reacted against Distributed transaction
The NoSQL movement rejected the transaction-centric model of distributed databases, embracing eventual consistency and giving up cross-site atomicity and serializability in favor of availability and partition tolerance.
Carried by Dynamo (2007); Bigtable (2006).
Parallel database influenced by Distributed Query Processing
Parallel database systems reused the idea from distributed query processing that a query plan can be split into fragments executed at different nodes with network or interconnect cost in the optimizer, applying it to shared-nothing machines.
Carried by Gamma; David DeWitt.
Fragmentation and Replication Design influenced by Distributed Query Processing
Fragmentation and replication design was motivated by distributed query processing: the layout of data was chosen so that the optimizer could execute joins and selections locally, minimizing data shipment.
Carried by Stefano Ceri; Giuseppe Pelagatti.
NewSQL influenced by Parallel database
NewSQL systems adopted the shared-nothing architecture and data partitioning techniques developed in parallel database research, combining them with consensus replication and distributed transactions.
Carried by Spanner (2012); CockroachDB.
Consensus-Based Replicated State influenced by Distributed Systems Correctness Theory
Consensus-based replicated state drew on the correctness theory of distributed systems for its failure models and safety proofs; Paxos was formulated within the same tradition of reasoning about crash failures and message passing.
Carried by Leslie Lamport.
NewSQL influenced by Distributed Systems Correctness Theory
NewSQL systems relied on the formal correctness conditions for distributed transactions and replication that had been established in distributed systems correctness theory, using them to justify strong consistency guarantees.
Carried by Spanner (2012).
NewSQL reacted against Eventual Consistency and NoSQL Data Models
NewSQL defined itself against the eventual-consistency trade-off of NoSQL, arguing that applications could have both scale and strong transactional guarantees, and rejecting the abandonment of SQL and ACID.
Carried by Spanner (2012).
Beyond the field
Where Distributed Databases's ideas came from in other fields, and what they led to there: the strongest 12 of 58 links.
Distributed transaction influenced NewSQL in Nosql Systems
NewSQL systems build directly on decades of distributed transaction research, notably two-phase commit and later consensus-based commit protocols, to offer ACID guarantees across sharded clusters. The classical theory of distributed transactions supplies the mechanisms these systems implement.
Distributed transaction influenced NewSQL in Big Data Processing
NewSQL systems build on decades of distributed transaction research, adopting two-phase commit and consensus-based replication to give ACID guarantees across nodes.
Distributed transaction influenced NewSQL in Databases
NewSQL systems are built on distributed transaction protocols, extending two-phase commit and serializable concurrency control to geographically replicated, sharded clusters. The framework's central promise of scalable ACID semantics rests directly on this earlier work.
Distributed transaction grew out of Database transaction in Database Theory
Distributed transactions extended the single-node database transaction concept to multiple sites, keeping atomicity and serializability as the goal. The two-phase commit protocol and distributed concurrency control were built directly on the local transaction model.
Carried by Jim Gray.
Distributed transaction grew out of Transaction processing and ACID in Databases
Distributed transaction processing grew out of centralized transaction processing and ACID, generalizing its commit and recovery mechanisms to multiple sites. The same atomicity and durability guarantees were re-established across a network.
Carried by Jim Gray.
Distributed Query Processing led to Parallel Query Processing in Query Processing
Parallel query processing grew directly out of distributed query processing, generalizing its techniques for fragmenting, shipping, and scheduling query execution across nodes to tightly coupled parallel machines. The same operator and scheduling ideas were carried over.
Distributed Query Processing grew out of Cost-based query optimization in Query Processing
Distributed query processing adopted cost-based optimization and extended the cost model to include network transmission and site-local processing. The optimizer chose among distributed plans using the same cost-driven search.
Distributed Query Processing grew out of Query optimization in Database Theory
Distributed query optimization is the multi-site generalization of query optimization theory. The same cost and equivalence reasoning was extended to fragmentation and site assignment.
Distributed Query Processing grew out of Query optimization in Databases
Distributed query processing extended centralized query optimization to plans spanning multiple sites, adding communication costs and data shipping decisions. The optimization framework was carried over and generalized.
Consensus-Based Replicated State influenced NewSQL in Databases
NewSQL systems rely on consensus-based replicated state, typically Paxos or Raft, to keep multiple replicas consistent while providing transactional guarantees. The replicated-log machinery from distributed consensus is a foundation of these systems.
Consensus-Based Replicated State grew out of State machine replication in Distributed Algorithms
Consensus-based replicated state is the practical realization of state machine replication, using a consensus protocol to order client commands. The state machine replication model supplied the correctness argument for the approach.
Carried by Leslie Lamport.
Consensus-Based Replicated State influenced by Consensus in Distributed Algorithms
Consensus-based replicated state uses consensus algorithms such as Paxos to agree on the order of operations. Consensus theory provided the agreement primitive on which the replicated state is built.
Carried by Leslie Lamport.

Distributed Databases is a planet in Nousfarer
Its city has a tower for each of these 8 frameworks. Land, walk in, and climb one concept at a time.
Land on Distributed DatabasesRelated fields
Fields its ideas are linked to
- Distributed Algorithms 11 links
- Distributed Systems 10 links
- Databases 8 links
- Transaction Processing 6 links
- Big Data Processing 5 links
- Database Theory 4 links
- Nosql Systems 4 links
- Parallel Algorithms 2 links
- Data Science 2 links
- Query Processing 2 links
- Memory Hierarchy 1 link
- Parallel Computing 1 link
More in Databases
See where Distributed Databases sits on the Map of Human Knowledge