Distributed Database Systems

Introduction and Context

A distributed database system stores and manages logically related data across multiple networked computers. To users and applications, the collection should appear as one coherent database, even though data may be partitioned, replicated, geographically dispersed, and managed by different database servers. Distribution is used to improve scalability, availability, fault tolerance, locality, and operational resilience. It also introduces costs: network latency, partial failure, coordination overhead, consistency challenges, complex recovery, and difficult observability.

Traditional centralized database design assumes that computation, storage, and transaction control occur within one administrative and failure domain. Distributed database design must instead reason about independent failures, unreliable communication, clock differences, data placement, and conflicting updates. A successful design is therefore not simply a centralized database replicated across machines; it is an explicit set of trade-offs among consistency, availability, latency, durability, and operational complexity.

This chapter examines fragmentation, replication, sharding, distributed queries and transactions, CAP and PACELC, consensus, quorum systems, consistency models, design practices, and a practical distributed-commerce scenario.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Distinguish distribution, fragmentation, replication, and sharding.

2. Evaluate placement strategies using locality, load, failure-domain, and consistency considerations.

3. Explain distributed query processing and distributed transaction protocols.

4. Apply CAP, PACELC, quorum, and consistency models to architectural decisions.

5. Analyze consensus and leader-based coordination.

6. Select appropriate designs while recognizing performance, governance, and operational limitations.

1. Architectural Foundations

A distributed database may be homogeneous, with the same database technology at each site, or heterogeneous, with different database systems connected through middleware or data-integration services. It may also be shared-nothing, where each node owns its local resources, or use shared storage. Modern cloud-native systems predominantly use shared-nothing architectures because they scale horizontally and isolate many failures.

Important terms include:

• Node or site: A computer or database instance participating in the system.
• Replica: A copy of a data object or partition.
• Partition: A subset of a relation or key space stored as a unit.
• Shard: A horizontally partitioned unit, usually distributed across nodes.
• Coordinator: A component that plans or controls a distributed operation.
• Failure domain: A set of components likely to fail together, such as a rack, availability zone, or region.
• Distributed transaction: A transaction whose read or write set spans multiple nodes.

Distribution transparency is a classical goal. Location transparency hides the physical site of data; fragmentation transparency hides how a relation is divided; replication transparency hides the number and location of copies. Full transparency is useful for application simplicity, but it can conceal costs. A query that appears local may cross regions, and a transaction that appears atomic may require a distributed commit protocol.

A distributed database must also distinguish logical data independence from operational transparency. Logical data independence allows conceptual schemas to evolve without changing applications. Operational transparency concerns whether applications need to know about placement, failover, consistency, or transaction boundaries. In practice, systems often expose some operational behavior because hiding latency and availability trade-offs completely is impossible.

2. Fragmentation and Sharding

Fragmentation determines how a relation is divided. The objective is to place data near its users and distribute load while preserving correctness.

2.1 Horizontal fragmentation

Horizontal fragmentation divides rows according to predicates. For a Customer relation, fragments might be defined as:

• Customer_Europe: region = 'EU'
• Customer_Asia: region = 'ASIA'
• Customer_Americas: region = 'AMER'

A complete horizontal fragmentation should satisfy:

1. Completeness: Every required row appears in at least one fragment.

2. Reconstruction: The original relation can be reconstructed, commonly by union.

3. Disjointness, where intended: A row belongs to only one fragment, although overlapping fragments can be valid.

For disjoint fragments, reconstruction is:

Customer = Customer_Europe UNION Customer_Asia UNION Customer_Americas.

A predicate-based scheme may become unbalanced when one region grows much faster than another. Hash partitioning, such as hashing a customer identifier modulo the number of partitions, produces more even distribution but provides weaker locality. Range partitioning supports efficient range queries but can create hotspots when new keys concentrate at one end.

2.2 Vertical fragmentation

Vertical fragmentation divides columns. Each fragment must include a common key so that the original relation can be reconstructed by a join. For Employee(emp_id, name, department, salary), one fragment may contain (emp_id, name, department), and another (emp_id, salary). The key is repeated intentionally; without it, tuple reconstruction would be ambiguous.

Vertical fragmentation is useful when different applications require different attributes or when sensitive columns should be isolated. It can, however, increase join cost and complicate authorization.

2.3 Hybrid fragmentation

Hybrid fragmentation applies horizontal and vertical fragmentation in sequence. For example, customer data may first be divided by region and then separated into operational and sensitive columns. Hybrid strategies can align data with organizational boundaries, but they increase metadata and placement complexity.

2.4 Sharding strategies

Sharding is the operational distribution of partitions across database nodes. Common strategies include:

• Range sharding: Keys in an interval are stored together. It supports range scans but risks hotspots.
• Hash sharding: A hash function spreads keys. It balances point operations but makes range queries expensive.
• Directory-based sharding: A lookup service maps keys to shards. It permits flexible movement but creates metadata dependencies.
• Consistent hashing: Key placement changes relatively gradually when nodes are added or removed, especially when virtual nodes are used. It is useful for elastic systems, although rebalancing and skew still require control.
• Composite sharding: A system may first select a region and then hash within that region.

A shard key should have high cardinality, distribute traffic, support important access paths, and respect data-residency requirements. A poor key, such as a monotonically increasing timestamp under range partitioning, can direct most writes to one shard. Resharding is expensive because it moves data, changes routing metadata, and may require dual-write or change-capture procedures.

3. Replication and Placement

Replication stores multiple copies of data. Replicas improve read locality and availability but consume storage and create update-coordination costs.

3.1 Replication models

• Synchronous replication: A write is acknowledged only after specified replicas confirm it. It provides stronger durability and consistency but increases write latency and may reduce availability during communication failures.
• Asynchronous replication: The primary acknowledges before replicas are confirmed. It reduces write latency but permits replica lag and potential loss of recently acknowledged data if the primary fails before propagation.
• Single-leader replication: One leader orders writes; followers replicate the ordered log. It simplifies conflict handling but can make leader failure and cross-region writes costly.
• Multi-leader replication: Several sites accept writes. It supports local writes but requires conflict detection and resolution.
• Leaderless replication: Clients or coordinators communicate with multiple replicas using quorum rules. It can tolerate some node failures but requires careful read-repair, hinted handoff, and conflict management.

3.2 Placement principles

Replica placement should consider failure independence. Three replicas in one rack do not provide the same resilience as three replicas in separate availability zones. Geographic placement improves disaster tolerance but increases latency and regulatory complexity.

Replication factor alone does not determine safety. A replication factor of three is weak if all copies share a power domain, if acknowledgements are accepted from only one copy, or if a failover mechanism can promote stale data. Designers should specify the failure model, acknowledgement policy, recovery-point objective, recovery-time objective, and acceptable staleness.

4. Consistency Models and Quorums

Consistency describes what values operations may observe. It is not identical to durability or availability.

• Linearizability: Each operation appears to take effect atomically at one point between invocation and response, respecting real-time order. It is strong but often expensive across regions.
• Sequential consistency: Operations appear in one order that respects each client’s program order, but not necessarily real-time order across clients.
• Causal consistency: Causally related operations are observed in causal order; concurrent operations may be seen in different orders.
• Eventual consistency: If updates stop and communication continues, replicas eventually converge. It does not by itself specify how stale reads may be or how conflicts are resolved.
• Read-your-writes: A client observes its own completed writes.
• Monotonic reads: Once a client has observed a value, later reads do not move backward to an older version.

For a replicated object with N replicas, a quorum design uses a write quorum W and read quorum R. Under the simplified assumptions of identical replicas, successful operations contacting the specified number of replicas, and no exceptional reconciliation behavior, R + W > N ensures that a read set and a write set overlap. W > N/2 ensures that two successful writes overlap. These conditions support detection of the latest version when version ordering and repair are correctly implemented; they do not automatically provide linearizability.

For N = 3, W = 2 and R = 2, both intersections are guaranteed. A write requiring only W = 1 is faster but can be acknowledged without any durable second copy. Quorum policies must also account for node diversity: two acknowledgements from the same failure domain may not provide two independent failures of protection.

Version vectors, logical timestamps, conflict-free replicated data types, and application-level merge functions may be used to reconcile concurrent updates. Last-write-wins is simple but can discard valid updates when clocks are inaccurate or timestamps lack sufficient semantic meaning.

5. CAP and PACELC

The CAP theorem concerns a distributed system that experiences a network partition. It states that a system cannot simultaneously guarantee linearizable consistency and availability for all requests during such a partition. Partition tolerance is generally not optional in a networked system: communication failures can occur. Therefore, a design must choose whether affected operations reject or wait for consistency, or continue with potentially weaker consistency.

CAP is frequently misinterpreted. It does not say a system can choose only two properties under normal operation, nor does it mean consistency and availability are permanently mutually exclusive. It focuses on behavior during partitions and on precise definitions of consistency and availability.

PACELC extends the discussion: if there is a Partition, one chooses Availability or Consistency; Else, under normal conditions, one chooses Latency or Consistency. A cross-region synchronous commit may provide stronger consistency but incur high latency. A locally acknowledged asynchronous write may minimize latency but expose stale reads or recovery loss.

The appropriate choice depends on semantics. A banking ledger, inventory reservation, or authorization decision may require strong coordination. Product recommendations, activity feeds, and telemetry often tolerate bounded staleness or eventual convergence.

6. Distributed Query Processing

A distributed query is decomposed into operations executed at different sites. Its major costs include network transfer, remote startup, serialization, synchronization, and local computation. The query optimizer should therefore minimize data movement rather than merely local CPU work.

A common technique is selection pushdown: apply restrictive predicates at the data source before transmitting rows. Projection pushdown transmits only needed columns. In a distributed join, a small relation or filtered subset may be broadcast to nodes holding the larger relation. Alternatively, both relations may be repartitioned on the join key, often by hashing, so matching rows meet at the same node.

For relations R and S joined on key K, a repartitioned hash join may:

1. Hash-partition R and S on K.

2. Send each tuple to the node responsible for its hash bucket.

3. Perform local joins at each node.

4. Union the local results.

This approach assumes sufficient network capacity, reasonably balanced keys, and manageable skew. A highly frequent key can create a straggler node. Query plans should therefore monitor skew, use adaptive repartitioning where available, and avoid unnecessary global barriers.

Distributed aggregation can use partial aggregation. Each node computes local counts or sums, sends compact partial results, and a coordinator combines them. This is correct for decomposable aggregates such as SUM and COUNT, but more care is needed for MEDIAN or exact percentile calculations.

7. Distributed Transactions and Consensus

A transaction spanning nodes must address atomicity, isolation, failure recovery, and sometimes global serializability. The classic two-phase commit protocol (2PC) has:

1. Prepare phase: The coordinator asks participants whether they can commit. Each participant records sufficient state and votes yes or no.

2. Commit phase: If all vote yes, the coordinator instructs commit; otherwise it instructs abort.

2PC preserves atomicity under many failures but is a blocking protocol: if the coordinator fails after participants prepare, participants may be unable to decide independently until recovery or coordinator-state discovery. It also adds network round trips and durable logging. Three-phase commit reduces some blocking conditions under stronger timing assumptions, but it does not eliminate the fundamental difficulties of asynchronous distributed failure and is less common than other approaches.

Modern systems often avoid broad distributed transactions by co-locating data that must change atomically, using transactional outboxes, sagas, idempotent operations, or application-level compensation. A saga decomposes a business process into local transactions and defines compensating actions. Compensation is not the same as rollback: an external shipment or email cannot always be perfectly undone.

Consensus protocols such as Raft and Paxos allow a group of nodes to agree on an ordered log despite certain crash failures. In a commonly simplified majority model, a cluster of N = 2f + 1 nodes can tolerate up to f crash failures while retaining a majority, assuming network and timing conditions eventually permit progress. This statement concerns crash tolerance and quorum intersection; it does not cover arbitrary Byzantine behavior. Consensus provides an ordering mechanism, not automatically a complete distributed transaction solution.

Leader election, replicated logs, membership changes, and fencing are critical. A former leader must be prevented from continuing to accept writes after losing authority; otherwise split-brain behavior may produce divergent state.

8. Worked Design Example

An online retailer stores Orders, OrderItems, Inventory, and ProductCatalog. Customers are distributed globally. Product browsing is read-heavy, while inventory reservations must prevent overselling.

A suitable design is:

• Shard Orders by customer region and a stable customer identifier.
• Keep OrderItems colocated with Orders when order retrieval is the dominant access pattern.
• Replicate ProductCatalog asynchronously to regional read sites because modest staleness is acceptable.
• Store authoritative inventory in a strongly coordinated partition, with reservations serialized per product or stock bucket.
• Use a transactional boundary for reservation and order state where feasible.
• Use an outbox event after a committed order state change to publish notifications reliably.

Suppose inventory has three replicas and requires acknowledgements from two independent availability zones. A write quorum of two provides redundancy against one zone failure, provided the replicas are correctly placed and the protocol prevents stale promotion. A regional outage may force the system either to reject reservations, preserving inventory correctness, or to accept provisional reservations with a carefully designed reconciliation process. The latter improves availability but risks temporary over-allocation and requires explicit business rules.

For a query requesting European orders for a customer, routing directly to the regional shard avoids a global scatter-gather query. For a global sales report, local aggregation followed by coordinator aggregation reduces data transfer. The report may use a consistent analytical snapshot or tolerate slight lag, depending on financial and operational requirements.

9. Illustrative Case: Global Health-Records Platform

Background

Consider a fictional health-records provider operating clinics in three jurisdictions. It must offer local availability, preserve auditability, and comply with data-residency law. Clinicians require recent patient information, while billing and clinical updates have different consistency needs.

Problem

A single global primary creates unacceptable latency for local writes and becomes a regional failure bottleneck. Fully independent regional writes improve availability but create conflicts in medication and allergy records, where silent loss could harm patients.

Analysis

The platform classifies data by safety and business impact. Immutable audit events require durable ordering and retention. Patient profile attributes may support causal or session consistency. Clinical facts require stronger conflict prevention, especially for medication changes. Search indexes and dashboards can tolerate asynchronous lag.

Approach

The provider uses jurisdiction-aware partitioning, independent failure domains, and encrypted replicas. Clinical updates are routed through an authority for the relevant patient record, using a consensus-backed log. Read-your-writes and causal metadata are provided to clinicians. Search projections are asynchronously built from committed events. During a partition, safety-critical writes fail closed or route to an explicitly designated authority rather than accepting uncontrolled concurrent edits. Every access is logged, and administrative actions require least privilege and separation of duties.

Outcome

Local reads remain responsive, while sensitive writes receive stronger coordination. The system sacrifices some availability during partitions for clinical correctness. Delayed projections are clearly marked with freshness metadata, and reconciliation procedures are tested using simulated regional failures.

Learning Points

The case demonstrates that consistency should be selected by data type and operation, not imposed uniformly. Data residency influences placement; safety requirements influence coordination; and asynchronous projections can separate user-facing query performance from authoritative state management.

10. Challenges, Governance, and Best Practices

Distributed systems are difficult to test because failures are partial and timing-dependent. Network partitions, delayed packets, duplicate messages, clock skew, replica lag, reordering, and stale caches should be included in fault-injection and property-based testing. Observability should expose request trace identifiers, shard routing, replica lag, commit positions, quorum outcomes, conflict rates, and data freshness.

Security must cover data in transit, data at rest, node identity, key rotation, tenant isolation, and administrative access. Replication can unintentionally copy regulated data into prohibited jurisdictions. Retention and deletion policies must account for replicas, backups, logs, caches, and derived indexes. Audit trails should be tamper-evident and access-controlled.

Operational best practices include:

1. Define consistency and failure semantics per operation.

2. Choose shard keys using measured access patterns and growth projections.

3. Place replicas across independent failure domains.

4. Automate rebalancing but rate-limit data movement.

5. Make retries safe through idempotency keys and deduplication.

6. Use bounded timeouts and explicit retry budgets; uncontrolled retries can amplify outages.

7. Monitor skew, hot partitions, replica lag, and quorum failures.

8. Test restore procedures, not merely backup creation.

9. Document transaction boundaries and compensation behavior.

10. Record freshness and provenance for replicated or derived data.

AI-based workload forecasting can help predict hotspots and recommend partition movement, but automated placement must respect privacy, residency, explainability, and safety constraints. An optimization model should not silently move protected data or change consistency guarantees. Human approval and policy enforcement remain necessary for high-impact systems.

Contemporary Developments

Cloud databases increasingly provide serverless scaling, globally distributed SQL, multi-region consensus, and automated online rebalancing. Newer systems combine relational transactions with distributed storage, while analytical platforms use lakehouse architectures and independent compute-storage scaling. Edge computing increases the value of local autonomy but intensifies synchronization and security challenges.

Research continues on adaptive consistency, programmable replication, deterministic transaction scheduling, Byzantine-resilient storage, confidential computing, and geo-distributed transaction processing. The central research problem remains unchanged: how to provide useful semantics under realistic failures without imposing unacceptable latency or cost.

Chapter Summary

Distributed database systems divide and replicate data across networked nodes to achieve scale, locality, availability, and resilience. Fragmentation may be horizontal, vertical, or hybrid; sharding operationalizes partition placement using range, hash, directory, or composite strategies. Replication improves availability and read performance but introduces lag, conflict, and recovery concerns.

Consistency models range from eventual consistency to linearizability. Quorum conditions such as R + W > N describe replica-set intersection under stated assumptions, but they do not alone guarantee linearizability. CAP explains the consistency–availability choice during partitions, while PACELC adds the normal-operation latency–consistency trade-off.

Distributed query processing seeks to reduce data movement through predicate pushdown, projection pushdown, local aggregation, and appropriate join strategies. Distributed transactions may use two-phase commit, sagas, outbox patterns, or carefully designed co-location. Consensus protocols order decisions and tolerate specified crash failures, but they do not eliminate application-level design responsibilities.

Professional practice requires explicit semantics, failure-domain-aware placement, idempotent retries, observability, security, regulatory compliance, and rigorous failure testing. The best architecture assigns stronger coordination only where business or safety semantics require it.

Key Terms

Fragmentation: Division of a logical relation into smaller components.

Horizontal fragmentation: Partitioning rows according to predicates.

Vertical fragmentation: Partitioning columns while retaining a reconstruction key.

Sharding: Distribution of partitions across database nodes.

Replication: Maintaining multiple copies of data.

Failure domain: Components likely to fail together.

Linearizability: Atomic real-time-consistent operation ordering.

Eventual consistency: Convergence when updates cease and communication continues.

Causal consistency: Preservation of causal ordering across observations.

Quorum: Required subset of replicas participating in an operation.

CAP theorem: Constraint involving consistency, availability, and partition behavior.

PACELC: Framework adding latency-versus-consistency trade-offs outside partitions.

Distributed query: Query whose execution involves multiple nodes.

Two-phase commit: Prepare-and-commit protocol for atomic distributed transactions.

Saga: Sequence of local transactions with compensating actions.

Consensus: Agreement on a value or ordered log despite specified failures.

Replica lag: Delay between authoritative updates and a replica’s state.

Split brain: Multiple nodes incorrectly acting as authoritative leaders.

Data locality: Placement of data near its users or computation.

Idempotency: Property allowing repeated execution without additional semantic effect.

Review Questions

Short Answer Questions

1. What are the completeness and reconstruction requirements of horizontal fragmentation?

2. Why is a key repeated in vertical fragments?

3. State the simplified quorum intersection condition for a read quorum and write quorum.

4. What trade-off does PACELC add to CAP?

5. Why can two-phase commit block?

Long Answer Questions

1. Compare range, hash, directory-based, and composite sharding, including suitable workloads and limitations.

2. Explain synchronous, asynchronous, single-leader, multi-leader, and leaderless replication.

3. Describe distributed query optimization techniques and discuss the effect of data skew.

4. Compare linearizability, causal consistency, and eventual consistency using application examples.

5. Explain how consensus differs from distributed transaction commitment and why both may be needed.

Analytical / Application Questions

1. Design a sharding and replication strategy for a global e-commerce system. Justify choices for orders, catalog data, and inventory.

2. A three-replica system uses W = 2 and R = 2. Explain what quorum intersection guarantees and what it does not guarantee.

3. During a regional network partition, should a clinical-record system accept concurrent medication updates? Evaluate the decision using CAP, safety, availability, and reconciliation considerations.

Multiple Choice Questions with Answers

Question 1

Which fragmentation method divides a relation into subsets of rows based on predicates?

A. Horizontal fragmentation

B. Vertical fragmentation

C. Replica placement

D. Projection pushdown

Correct Answer: A. Horizontal fragmentation

Question 2

For a replicated object with N replicas, which simplified condition ensures that a read quorum and write quorum overlap?

A. R + W = N

B. R + W > N

C. R = W = 1

D. W < N/2

Correct Answer: B. R + W > N

Question 3

What is a principal limitation of two-phase commit?

A. It cannot coordinate more than one participant

B. It never records durable state

C. It may block if the coordinator fails at a critical point

D. It guarantees availability during every partition

Correct Answer: C. It may block if the coordinator fails at a critical point

Question 4

Under CAP, what fundamental choice arises during a network partition?

A. Choose between indexing and normalization

B. Choose between availability and linearizable consistency

C. Choose between hashing and range partitioning

D. Choose between encryption and compression

Correct Answer: B. Choose between availability and linearizable consistency

Question 5

Which sharding strategy generally supports range scans most naturally but may create hotspots at range boundaries?

A. Range sharding

B. Hash sharding

C. Random replica selection

D. Vertical fragmentation

Correct Answer: A. Range sharding

Question 6

What is the main purpose of predicate pushdown in distributed query processing?

A. Increase the number of transferred rows

B. Apply filters near the data source to reduce network transfer

C. Disable local computation

D. Convert every join into a transaction

Correct Answer: B. Apply filters near the data source to reduce network transfer

Question 7

A consensus cluster has N = 5 nodes and assumes only crash failures. Under the simplified majority model, how many crash failures can it tolerate while retaining a majority?

A. 1

B. 2

C. 3

D. 4

Correct Answer: B. 2

Question 8

Which consistency model guarantees that a client does not observe its own completed write being replaced by an older value?

A. Read-your-writes consistency

B. Eventual consistency only

C. Random consistency

D. Partition consistency

Correct Answer: A. Read-your-writes consistency

Question 9

Why should replicas be placed in separate availability zones?

A. To make all writes synchronous automatically

B. To increase the likelihood that a single zone failure does not remove all copies

C. To eliminate network latency

D. To avoid storing metadata

Correct Answer: B. To increase the likelihood that a single zone failure does not remove all copies

Question 10

Which pattern decomposes a business process into local transactions and compensating actions?

A. Saga

B. Vertical join

C. Broadcast index

D. Read repair only

Correct Answer: A. Saga