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

still a working view ended · each leads to its entry below

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

  1. Database (Classification terms), Wikipedia
  2. Distributed database, Wikipedia
  3. Shard (database architecture), Wikipedia
  4. 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.

  1. 1978-Present

    Distributed transaction

    How can a transaction stay atomic across many machines?

    Fly to its tower in Nousfarer

  2. 1979-Present
  3. 1979-Present

    Parallel database

    How can many machines work together on one query?

    Fly to its tower in Nousfarer

  4. 1980-Present

    Fragmentation and Replication Design

    How should data be split and copied across sites?

    Fly to its tower in Nousfarer

  5. 1985-Present
  6. 1989-Present
  7. 2006-Present

    Eventual Consistency and NoSQL Data Models

    Can we trade consistency for speed and availability?

    Fly to its tower in Nousfarer

  8. 2012-Present

    NewSQL

    Can we have both scale and strong guarantees?

    Fly to its tower in Nousfarer

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 transactionDistributed Query ProcessingParallel databaseFragmentation and Replication DesignDistributed Systems Correctness TheoryConsensus-Based Replicated StateEventual Consistency and NoSQL Data M…NewSQL

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Databases

Related fields

Fields its ideas are linked to

More in Databases

See where Distributed Databases sits on the Map of Human Knowledge