Distributed Databases

9.1 Architecture and Motivation

A distributed database stores data across multiple nodes connected by a network. Motivations Include:

• Performance: Data locality reduces latency; parallel query processing increases throughput.
• Availability: Replication allows the system to survive node failures.
• Scalability: Horizontal scaling by adding more nodes.

Shared-nothing architecture. Each node has its own CPU, memory, and disk. Nodes communicate Only via the network. This is the dominant architecture for distributed databases.

Data fragmentation:

• Horizontal fragmentation: Each fragment is a subset of rows (tuples) defined by a selection predicate. Example: partition Student by department.
• Vertical fragmentation: Each fragment is a subset of columns. Example: store frequently accessed columns on fast nodes.
• Hybrid fragmentation: A combination of horizontal and vertical.

9.2 Distributed Transactions

A distributed transaction involves operations on multiple nodes. The challenge is ensuring atomicity Across nodes.

Two-Phase Commit (2PC).

• Phase 1 (Voting): The coordinator sends a PREPARE message to all participants. Each participant writes its changes to a local log, votes YES (ready to commit) or NO (abort).
• Phase 2 (Decision): If all participants voted YESThe coordinator sends COMMIT; otherwise it sends ABORT. Participants apply the decision and acknowledge.

Theorem 9.1. 2PC guarantees atomicity of distributed transactions if no participant crashes Permanently and the log is on stable storage.

Proof. If the coordinator crashes after phase 1, participants that voted YES are blocked — they Cannot decide without knowing the coordinator”s decision. Upon recovery, the coordinator reads its Log to determine the decision and notifies participants. Since each participant wrote its vote to Stable storage before responding, no vote is lost. $\blacksquare$

Blocking problem. If the coordinator crashes after phase 1, participants that voted YES must Wait indefinitely (they are blocked). This is a fundamental limitation of 2PC.

Three-Phase Commit (3PC). Adds a PRE-COMMIT phase to eliminate blocking under the fail-stop Model:

1. CanCommit: Coordinator asks if participants can commit. Participants reply YES or NO.
2. PreCommit: If all YESCoordinator sends PRE-COMMIT. Participants acknowledge.
3. DoCommit: Coordinator sends COMMIT. Participants commit and acknowledge.

If the coordinator crashes after PRE-COMMITAny participant can contact others to determine the Outcome (since at least one participant must have received PRE-COMMIT and can coordinate).

Limitation of 3PC: Assumes reliable communication (no lost messages), which is unrealistic in Practice. 3PC is rarely used in production systems.

9.3 Replication

Synchronous replication. A write is not acknowledged until all replicas have applied it.

• Guarantees strong consistency (all replicas identical).
• High latency (wait for the slowest replica).
• Reduced availability during partitions (cannot acknowledge writes if a replica is unreachable).

Asynchronous replication. A write is acknowledged after the primary applies it; replicas are Updated in the background.

• Low latency (acknowledged immediately).
• Eventual consistency (replicas may lag behind).
• Higher availability during partitions.

Replication architectures:

Quorum-based consistency. For a system with $N$ replicas, define write quorum $W$ and read quorum $R$ such that $W + R \gt N$. This guarantees that any read sees at least one replica with the Latest write.

9.4 Consistency Models

Consistency models define the guarantees a distributed system provides about the order and visibility Of updates.

Strong consistency models:

• Linearisability: Every operation appears to execute atomically at a single point in real time. The strongest consistency model. Equivalent to “serialisable + real-time ordering.”
• Sequential consistency: All operations appear in some total order that is consistent with the program order of each individual process. Weaker than linearisability (no real-time requirement).

Weak consistency models:

• Causal consistency: Operations that are causally related are seen by all processes in the same order. Concurrent (non-causally-related) operations may be seen in different orders.
• Read-your-writes consistency: A process always sees its own writes.
• Eventual consistency: If no new updates are made, all replicas will eventually converge to the same state. The weakest model; provides no ordering guarantees.