Distributed Database Fundamentals

A distributed database (DDB) is a set of interconnected databases, stored at different sites of a computer network, that logically function as a single database from the viewpoint of a user or application. This is distinct from merely running a database on a distributed system — the defining property is that data itself is partitioned or replicated across multiple sites (also called nodes), each with its own local storage, local processing power, and often its own local database management system. Three concepts anchor the design of any distributed database. Transparency means users interact with the system through a single logical interface, without needing to know how many sites exist, where data resides, or how many copies of it are kept. Site autonomy means each participating site can manage its local data and continue serving local requests independently, without requiring permission from a central controller for every operation. Failure independence means the failure of one site should not cause other sites to fail or become unusable — the system degrades gracefully rather than catastrophically. These three properties are frequently in tension: strong transparency often requires more cross-site coordination, which can undermine autonomy and make failures propagate rather than stay contained. It helps to contrast a distributed database with two related but different architectures. A centralized database keeps all data and processing on one machine — simple to reason about, but a single point of failure and a scalability ceiling. A parallel database typically runs on a tightly coupled cluster within one data center, primarily for performance (parallelizing large queries), and generally assumes fast, reliable interconnects. A true distributed database, by contrast, often spans geographically separate sites connected by a wide-area network with variable latency and the real possibility of communication failures — this is precisely what makes transparency and autonomy hard to achieve simultaneously, and it foreshadows why concepts like the CAP Theorem become unavoidable once a database is truly distributed. Because the Relational Model and Transactions were originally designed with a single-site machine in mind, distributed databases must re-engineer both the storage layer and the transaction manager to work across a network.

Architectural building blocks

A distributed database system is built from a small number of recurring components, no matter which specific architecture (client-server, peer-to-peer, or shared-nothing cluster) is chosen:

• Sites (nodes): Independent machines, each running a local DBMS instance and holding some fragment or replica of the overall data.
• Global schema: The logical description of all data in the system, as if it were one database — this is what application developers see.
• Fragmentation schema: Describes how the global relations are split into fragments (horizontal, vertical, or mixed) and which site stores which fragment.
• Allocation schema: Describes which physical sites hold which fragments, and how many replicas of each fragment exist.
• Distributed transaction manager: Coordinates operations that touch data at more than one site, ensuring atomicity and consistency across the network.
• Communication network: The medium (and its failure modes — delays, message loss, partitions) that connects all sites.

The four transparency layers

Transparency is not a single property but a stack of illusions, each hiding one aspect of the distribution from the layer above it: 1. Fragmentation transparency — the user queries a relation as a whole; they need not know it has been split into fragments across sites. 2. Replication transparency — the user need not know how many copies of a fragment exist or which copy answered the query. 3. Location transparency — the user need not know the physical site at which any fragment or replica resides; a name-server-like mechanism resolves logical names to physical locations. 4. Transaction (or naming) transparency — a transaction that reads/writes data at several sites still appears to the application as a single atomic unit, exactly like a local transaction. A query issued by an application passes down through these layers before ever touching disk: ``` PSEUDOCODE: Query resolution through the transparency stack function EXECUTE_GLOBAL_QUERY(query, global_schema):

# Step 1: Fragmentation transparency

# Translate a query on a global relation into a set of

# sub-queries on its fragments. fragment_queries = TRANSLATE_TO_FRAGMENTS(query, global_schema.fragmentation_schema)

# Step 2: Replication transparency

# For each fragment needed, choose one available replica

# (e.g., nearest, least loaded, or most up to date). site_assignments = {} for fq in fragment_queries: replicas = LOOKUP_REPLICAS(fq.fragment_id, global_schema.allocation_schema) chosen = SELECT_REPLICA(replicas, policy = "nearest_available") if chosen is None: raise SiteUnavailableError(fq.fragment_id) site_assignments[fq] = chosen

# Step 3: Location transparency

# Resolve chosen replicas to physical network addresses. physical_plan = [] for fq, site in site_assignments.items(): address = RESOLVE_SITE_ADDRESS(site) physical_plan.append((fq, address))

# Step 4: Distributed query optimization

# Decide execution order, joins across sites, and where

# intermediate results should be shipped (data shipping

# vs. query shipping) to minimize network cost. ordered_plan = OPTIMIZE_DISTRIBUTED_PLAN(physical_plan)

# Step 5: Execute sub-queries at remote sites in parallel partial_results = [] for step in ordered_plan: result = SEND_AND_EXECUTE(step.address, step.fragment_query) partial_results.append(result)

# Step 6: Combine results into the single answer the

# user expects (transaction/global transparency) final_result = MERGE_RESULTS(partial_results, query) return final_result ```

Coordinating distributed transactions

When a transaction spans multiple sites — say, debiting an account fragment stored in one country and crediting one stored in another — the system must still guarantee the Transactions property of atomicity: either all sites commit, or all sites abort. The classical mechanism for this is the two-phase commit (2PC) protocol, run by a coordinator over a set of participant sites. ``` PSEUDOCODE: Two-Phase Commit (2PC)

# --- Coordinator side --- function COORDINATOR_COMMIT(transaction, participants):

# Phase 1: Voting / Prepare for site in participants: SEND(site, PREPARE, transaction.id) votes = [] for site in participants: vote = RECEIVE_WITH_TIMEOUT(site, timeout = T) if vote is TIMEOUT or vote == NO: votes.append(NO) else: votes.append(YES)

# Phase 2: Decision if all(v == YES for v in votes): decision = COMMIT else: decision = ABORT LOG(decision, transaction.id) # write decision to stable log first for site in participants: SEND(site, decision, transaction.id)

# Wait for acknowledgments; retry sending to any site

# that does not acknowledge, until all have confirmed. pending = set(participants) while pending: for site in list(pending): ack = RECEIVE_WITH_TIMEOUT(site, timeout = T) if ack == ACK: pending.remove(site)

# else: resend decision, keep retrying return decision

# --- Participant site side --- function PARTICIPANT_HANDLE(transaction_id): msg = RECEIVE(coordinator) if msg == PREPARE: if CAN_COMMIT_LOCALLY(transaction_id): LOG("PREPARED", transaction_id) # stable log, survives crash SEND(coordinator, YES) else: SEND(coordinator, NO) decision = RECEIVE_WITH_RETRY(coordinator) # blocks until decision arrives if decision == COMMIT: APPLY_COMMIT(transaction_id) LOG("COMMITTED", transaction_id) else: APPLY_ABORT(transaction_id) LOG("ABORTED", transaction_id) SEND(coordinator, ACK) ``` The protocol's name comes directly from its structure: a prepare/vote phase, in which every site declares whether it can commit, followed by a decision phase, in which the coordinator broadcasts a single, universally binding outcome. Crucially, once a participant votes YES, it must be able to commit later regardless of any local event — this is why it writes a durable "PREPARED" log record before voting, so it can recover its promise even after a crash.

Cost of a distributed query. In a centralized database, the dominant cost is disk I/O. In a distributed database, we must also account for communication cost, since sites may be separated by a wide-area network with latency orders of magnitude larger than a disk seek. If a query requires shipping $n$ tuples between two sites at cost $c$ per unit of data, the total cost is modeled as

Distributed query optimizers therefore choose between data shipping (move raw tuples to the site running the query) and query shipping (move the query to the site holding the data, returning only the small result), preferring whichever minimizes the dominant network term — this is a direct generalization of the join-ordering problem from centralized query optimization, now with a communication-cost dimension added.

Correctness of Two-Phase Commit. The key correctness property required of a distributed transaction is atomicity: no execution may end with some sites having committed and others having aborted the same transaction. 2PC achieves this through an invariant maintained across both phases: > Invariant: once any participant has sent a YES vote, it holds a durable, recoverable promise ("PREPARED" record) that it can either commit or abort as instructed later; the coordinator's committed decision (in its log) is the single source of truth all participants must eventually match. Proof sketch. The coordinator only decides COMMIT if every participant voted YES (so every site is provably able to commit). It only decides ABORT if at least one participant voted NO or timed out (so no site is forced to commit something it could not support). Because the decision is written to a durable log before being broadcast, even a coordinator crash after deciding cannot lose or reverse the decision — on recovery, it simply re-reads the log and re-sends the same decision. Because a prepared participant has durably logged its ability to comply, even a participant crash between voting YES and receiving the decision cannot cause it to unilaterally abort; on recovery it must ask the coordinator (or other participants) for the outcome and apply it. Hence, by induction over the protocol steps, all live sites converge on the same COMMIT/ABORT decision — atomicity holds.

Complexity. Two-Phase Commit requires two round trips of messages ($O(n)$ messages per phase for $n$ participants) and each participant performs at least two forced log writes (the PREPARE vote and the final decision), giving $O(n)$ messages, $O(1)$ communication rounds per phase, and $O(1)$ synchronous disk writes per participant — cheap in message count, but each round trip pays real wide-area latency, and the protocol is famously blocking: if the coordinator crashes after some participants voted YES but before the decision is sent, those participants must hold their locks and wait, unable to unilaterally commit or abort, until the coordinator recovers. This blocking property is the central weakness that motivates more advanced consensus protocols in modern distributed systems, and it is one concrete reason why replication and failure-handling strategies (covered under Replication Strategies) matter so much once a database is truly distributed.

Honest tradeoffs. Full location, fragmentation, and replication transparency are attractive for programmers but are not free: maintaining them requires metadata lookups, replica-selection logic, and cross-site coordination on every write, all of which cost latency. Systems that prioritize maximal availability and low latency (favoring site autonomy) often relax strict transparency or strict consistency — a tension that becomes precise and unavoidable once we study the CAP Theorem.

Consider a simplified banking relation `ACCOUNTS(acct_id, city, balance)`, horizontally fragmented by city and distributed across three sites: Tokyo (Site A), London (Site B), and São Paulo (Site C), with each site keeping a replicated backup of a neighboring site's fragment (as shown in the figure above).

Scenario: A customer initiates a wire transfer of $500 from account `T-102` (a Tokyo-fragment account) to account `L-207` (a London-fragment account). This is a single logical transaction that must touch two different sites.

Now introduce a failure. Suppose at step 8, Site A crashes immediately after logging `PREPARED` but before receiving the coordinator's decision (which was actually COMMIT, already durably logged by the coordinator at step 7). Because Site A logged `PREPARED` durably before crashing, on recovery it does not simply guess — it contacts the coordinator, learns the decision was COMMIT, applies the debit, logs `COMMITTED`, and sends its ACK late. The transaction still ends atomically committed at both sites, exactly as the invariant guarantees, even though one participant was temporarily unreachable. If instead Site A had crashed before logging `PREPARED` (i.e., before voting), the coordinator's timeout on Site A's vote would trigger a global ABORT, and Site B — which may have already voted YES but not yet received a decision — simply rolls back when it receives the ABORT message. In neither case does the system end up half-committed.

Distributed database theory emerged from the practical need to connect separately administered mainframe systems in the 1970s and 1980s, as organizations began networking computers across buildings, cities, and eventually continents. The foundational challenge — making many machines look like one, without giving up their independence — was recognized early as a problem distinct from ordinary networking, requiring new theory around atomic commitment, replicated data consistency, and query decomposition.

Distributed database fundamentals underlie the infrastructure of nearly every large-scale software system in production today. Global banking and payment networks rely on distributed transaction coordination to keep balances consistent across data centers on different continents. Cloud data warehouses and NewSQL systems (such as Google Spanner, CockroachDB, and Amazon Aurora) build directly on the transparency and autonomy principles introduced here, layering more sophisticated consensus and replication protocols on top of the same core goals. Airline reservation systems, telecommunication billing platforms, and multinational retail inventory systems all depend on fragmenting and distributing their Relational Model-based data while preserving something close to single-system semantics for application developers. Understanding these fundamentals is also the necessary springboard to the next layer of distributed systems design: how exactly data gets split across sites (see Data Partitioning and Sharding), how many copies of it should exist and how they stay synchronized (see Replication Strategies), and the fundamental limit on what any distributed system can simultaneously guarantee under network failure (see The CAP Theorem).

Ask the tutor: How does two-phase commit's blocking problem get resolved in systems like Google Spanner or CockroachDB?