PaperlayerView exact revision on arXiv

Source-linked AI summary

MDCC: Multi-Data Center Consistency

Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden

arXiv:1203.6049v1cs.DBcs.DC

TL;DR

Strongly consistent replication across geographically separated data centers is difficult because communication is expensive and highly variable, while existing approaches trade off consistency, availability, or latency. MDCC addresses this with a masterless optimistic commit protocol and a programming model for unpredictable delays, achieving strong consistency at similar cost to eventually consistent protocols and sustaining data-center failures without compromising availability or consistency.

  • Problem

    Inter-data-center replication has expensive, highly variable delays, making strongly consistent synchronous replication difficult while existing approaches compromise consistency, availability, or failure safety.

  • Method

    MDCC combines a masterless optimistic commit protocol with a programming model that exposes transaction progress and handles unpredictable wide-area delays.

  • Results

    MDCC provides strong consistency at a cost similar to eventually consistent protocols, commits in one round trip in the common case, and sustains data-center failures without compromising availability or consistency.

  • Takeaways & Limitations

    MDCC demonstrates that wide-area transactional consistency can combine low normal-case latency with resilience to data-center failures.

  • Takeaways & Limitations

    The programming model remains to be extended to additional languages, and atomic visibility is unsupported because committed transaction updates may become visible only partially.

Abstract

from arXiv · show

Replicating data across multiple data centers not only allows moving the data closer to the user and, thus, reduces latency for applications, but also increases the availability in the event of a data center failure. Therefore, it is not surprising that companies like Google, Yahoo, and Netflix already replicate user data across geographically different regions. However, replication across data centers is expensive. Inter-data center network delays are in the hundreds of milliseconds and vary significantly. Synchronous wide-area replication is therefore considered to be unfeasible with strong consistency and current solutions either settle for asynchronous replication which implies the risk of losing data in the event of failures, restrict consistency to small partitions, or give up consistency entirely. With MDCC (Multi-Data Center Consistency), we describe the first optimistic commit protocol, that does not require a master or partitioning, and is strongly consistent at a cost similar to eventually consistent protocols. MDCC can commit transactions in a single round-trip across data centers in the normal operational case. We further propose a new programming model which empowers the application developer to handle longer and unpredictable latencies caused by inter-data center communication. Our evaluation using the TPC-W benchmark with MDCC deployed across 5 geographically diverse data centers shows that MDCC is able to achieve throughput and latency similar to eventually consistent quorum protocols and that MDCC is able to sustain a data center outage without a significant impact on response times while guaranteeing strong consistency.

1. INTRODUCTION

MDCC addresses the cost and latency challenges of strongly consistent replication across data centers with a masterless optimistic commit protocol and a latency-aware programming model. The paper reports strong consistency at costs similar to eventually consistent protocols, including single-round-trip commits in the common case.

  • Motivation: Replication across data centers improves availability but incurs expensive, highly variable inter-data-center delays.These delays complicate synchronous replication and motivate alternatives to traditional wide-area commit protocols.
  • Motivation: Traditional protocols such as 2PC add message delays, hold locks, and depend on a coordinator that can fail.Existing approaches can block transactions during coordinator recovery, while asynchronous replication may lose committed transactions, become unavailable, or violate consistency.
  • MDCC Contributions: MDCC is a masterless optimistic commit protocol that provides strong consistency at a cost similar to eventually consistent protocols.It commits transactions with one wide-area message round trip in the common case and supports reads or updates from any node in any data center.
  • Evaluation: 50% lower per-transaction latency, to 234 ms, and twice the transaction throughput were reported against 2PC on TPC-W across five Amazon data centers.The evaluation also reports strong consistency with costs similar to eventually consistent protocols and examines normal-operation optimizations and data-center failure.
  • MDCC Contributions: MDCC’s programming model exposes transaction stages through callbacks so applications can respond differently when operations are committed or still pending.The model is service-level-objective aware and targets highly delayed messages caused by wide-area latency variance.

2. ARCHITECTURE OVERVIEW

MDCC uses a library-centric architecture that separates stateful storage from stateless database functionality. The database library supplies transaction programming and coordinates replication and consistency through the commit protocol.

  • Architecture Overview: MDCC separates the database’s stateful record manager from higher-level functionality in a stateless database library.Storage nodes are simplified and can scale through standard techniques such as hash partitioning.
  • Architecture Overview: The database library provides the transaction programming model and coordinates data replication and consistency by implementing MDCC’s commit protocol.It may communicate directly with storage servers or select a storage node to coordinate a transaction.
  • Architecture Overview: The architecture supports flexible coordination in which storage nodes or application servers can act as the master for a record.This flexibility depends on the situation rather than requiring one fixed coordinating component.
  • Scope: The paper focuses on the transaction programming model and commit protocol, leaving load balancing and storage-node design beyond its scope.Those system components are deferred to other work.

3. THE MDCC PROGRAMMING MODEL

MDCC’s programming model makes response-time objectives explicit and exposes transaction stages so applications can respond appropriately to uncertain wide-area execution times. It supports multiple data models and consistency guarantees while providing callbacks for pending, accepted, committed, or failed transactions.

  • SLO and transaction stages: The programming model replaces fire-and-hope behavior with callbacks that distinguish transaction failure, acceptance, commitment, and final remote completion.Callbacks include onFailure, onAccept, onCommit, finally, and finallyRemote.
  • Data model and guarantees: The model can be used with different data models, query languages, and consistency guarantees, including key/value operations and PIQL queries.The implementation provides an object-relational data model with tables, primary keys, complex attributes, and secondary indexes.
  • Data model and guarantees: MDCC supports interleaved application logic with transactional table operations, while non-database application-variable changes remain nonpersistent and are not rolled back.Durability and transactional guarantees apply to table put and get operations.
  • Data model and guarantees: MDCC’s default consistency level is read committed without lost updates, allowing reads of only committed values and preventing write-write conflicts.Writes are postponed until transaction end, while a record cache exposes transaction-local writes during execution.
  • SLO and transaction stages: MDCC lets developers specify a response-time SLO and executes the latest reached transaction stage when that timeout expires.The SLO is a timeout that guarantees execution returns to the application within the specified time.

3.3 Usage Scenarios

MDCC’s usage scenarios show how developers tailor transaction callbacks to the importance of an operation and the acceptable delay before user feedback. Web-store purchases distinguish pending, success, failure, and later status updates, while tweets use simpler acceptance and failure handling.

  • Web shop: Web-store checkout uses a 300ms threshold to provide immediate success or abort feedback when the transaction finishes within that time.The transaction creates an order, adds an order line, and reduces product stock.
  • Web shop: If checkout remains unresolved after 300ms, the application can show a pending status while later callbacks communicate the final outcome.The example uses onAccept, onCommit, finally, and finallyRemote stages.
  • Twitter: Twitter transactions use only onFailure and onAccept because tweets are less critical and need not become immediately globally visible.This usage does not require the developer to wait for or handle the commit result directly.

4. THE MDCC PROTOCOL

MDCC introduces an optimistic, master-free commit protocol for wide-area transactions. It avoids a prepare phase in the common case, exploits rare conflicts or commuting updates, and provides read-committed consistency with complete write-write conflict detection.

  • Protocol design: MDCC commits updates in a single wide-area message round-trip when no conflicts are detected, unlike pessimistic protocols that require a prepare phase.The protocol trades CPU cycles for reduced communication overhead in wide-area deployments.
  • Protocol design: The protocol exploits workloads where conflicts are rare or updates commute within constraints such as nonnegative stock.A conflict-resolution path remains available through the pessimistic baseline.
  • Protocol design: MDCC extends Multi-Paxos with multi-row transaction support, then uses Generalized Paxos ideas to become optimistic and master free.The protocol combines Generalized Paxos with escrow transactions and demarcation techniques.
  • Consistency: MDCC guarantees read-committed consistency and detects all write-write conflicts, while permitting alternative read strategies.The commit protocol can be combined with different read guarantees.

4.1 Background: Paxos

This section explains Classic Paxos as a quorum protocol that uses a master to coordinate updates for replicated records. Its two phases establish mastership and accept values, while optimizations batch mastership metadata across versions.

  • Paxos background: Paxos reaches consensus on one value among replicas and tolerates lost, duplicated, or reordered messages and node fail-recovery.The paper maps clients, proposers, acceptors, and learners to app-servers, masters, storage nodes, and learners.
  • Classic Paxos: In Classic Paxos, app-servers send record updates to a master, which persuades a majority of storage nodes to accept them.Storage nodes accept updates only from the latest known master and proposal state.
  • Classic Paxos: Phase 1 establishes mastership with a unique ballot number, while Phase 2 proposes a value and preserves any higher-numbered previously accepted value.Proposal numbers combine a number with the server IP address to ensure uniqueness.
  • Classic Paxos: Classic Paxos uses separate rounds for record versions and requires the previous version to have been chosen successfully.This addresses the algorithm’s limitation of learning only one value per round.
  • Classic Paxos: MDCC can preselect mastership for several versions by storing start round, end round, ballot, and server-IP metadata with the record.Storage nodes answer for multiple rounds in a single message, while different versions may use different masters.

4.2 Transaction Support

MDCC extends its record-level Paxos protocol to multi-record transactions, providing atomic durability and write-write conflict detection while supporting deterministic outcomes and single-round-trip commits in favorable cases.

  • Multi-record transactions: Each record update is proposed as an option through a separate Paxos round, enabling atomic durability and detection of all write-write conflicts.A transaction commits only when every record option is learned as accepted; any rejected option aborts it.
  • Multi-record transactions: Write-write conflicts are detected by comparing each option’s vread version with the record’s current version before accepting the proposed update.A mismatch means the record changed between the transaction’s read and write.
  • Transaction outcomes: Transaction status is deterministic: commit requires all options accepted, abort follows any rejection, and otherwise the transaction remains undecided.Clients cannot manually abort a proposed transaction, so failures do not change the outcome independently of learned options.
  • Commit latency: A single round-trip can determine commit or abort when all record masters are local, because record options are processed in parallel and the outcome is irrevocably learned from quorum responses.The later Learned notification is sent after the application moves on and supports fresh reads.
  • Deadlock handling: Deadlocks from transactions waiting on options are avoided by learning competing options together, accepting one and rejecting the other.This relaxed progression allows one transaction to commit while the conflicting transaction aborts.
  • Failure recovery: Multi-Paxos masks storage-node failures with quorums, while app-server failures require transaction identifiers, write-set keys, and logs of learned options to reconstruct state.The programming model maps protocol progress to transaction stages such as onAccept, onFailure, and finally.

4.3 Transactions without a Master

MDCC removes the master from common-case option acceptance by using Fast Paxos-style fast rounds and quorums, while switching to classic rounds when conflicts or master acquisition require extra coordination.

  • Round-trip requirements: Transactions require two wide-area round-trips when a record master is remote or must first be acquired, unlike the local-master case.The additional coordination limits when MDCC can achieve its fastest path.
  • Fast rounds: Fast rounds let app-servers propose directly to storage nodes, using fast quorums that preserve safety without contacting the master.With replication factor 5, a typical configuration uses classic quorum size 3 and fast quorum size 4.
  • Conflict recovery: If a fast quorum is not achieved or proposals collide, MDCC starts a classic round to recover safely and resolve the conflict.The recovery phase examines classic-quorum responses and computes intersections with possible fast quorums.
  • Multi-round optimization: MDCC pre-sets consecutive fast rounds and orders classic ballots above fast ballots, allowing multiple masterless rounds before conflict resolution.After a conflict, the protocol changes the round to classic, resolves it, and then proceeds to the next round.
  • Adaptive policy: Fast rounds can require two extra message round-trips after a conflict, whereas classic rounds consistently require two round-trips.MDCC therefore uses fast rounds when conflicts are rare and adjusts the round type automatically.
  • Adaptive policy: The self-adjusting policy favors fast mode when conflicts are rare and classic mode when conflicts are common, periodically retesting fast mode.The policy uses the observed history of successful fast rounds and conflict resolution.

4.4 Commutative Updates

MDCC uses Generalized Paxos to process commuting updates without enforcing unnecessary order, then adds quorum-aware demarcation to preserve global value constraints.

  • Commutative updates: Generalized Paxos lets MDCC accept commuting updates in the same round even when storage nodes do not agree on one exact ordering.This extends Fast Paxos from consensus on one value to consensus on compatible sequences of values.
  • Commutative-round protocol: Fast commutative rounds begin from a master-established base value, after which clients propose delta updates directly to storage nodes.An update commits when a fast quorum accepts it, allowing the protocol to bypass the master during the round.
  • Global constraints: Generalized Paxos alone does not enforce integrity constraints such as requiring stock to remain nonnegative.Independent local decisions can accept updates whose combined committed effect violates the domain constraint.
  • Global constraints: MDCC’s demarcation strategy treats replicated base values as resources and derives a lower acceptance limit from the replication factor and fast-quorum size.The limit prevents storage nodes from accepting decrements that could drive the value below the guaranteed safe boundary.
  • Global constraints: The limit is recalculated for each new base value but is not updated merely because an option has committed.Options rejected by this limit are handled as conflicts, causing an automatic switch to classic rounds.

5. CONSISTENCY GUARANTEES

MDCC guarantees atomicity and a default read-committed level without lost updates, while offering stronger snapshot options and exposing trade-offs in freshness and visibility.

  • Core guarantees: MDCC guarantees atomic durability and prevents two concurrent write-conflicting update transactions from both committing.Different read strategies can be combined with the commit protocol to provide varying consistency levels.
  • Read committed: The default consistency level is read committed without lost updates, preventing transactions from reading uncommitted changes.This level is presented as sufficient for a wide range of applications deployed across data centers.
  • Read freshness: Single-node local reads return only committed records but may be stale; obtaining the latest value requires a majority read.Majority reads make freshness more expensive than local reads.
  • Read strategies: Local up-to-date or monotonic reads can be enabled by ensuring the local master participates in Phase 1 and Phase 2 quorums and tracking failures.This strategy assumes clients are normally colocated with the local storage master.
  • Atomic visibility: MDCC provides atomic durability but not atomic visibility, so different updates from one committed transaction may become visible at different times.Achieving atomic visibility by storing complete write-sets with every update is expensive.
  • Snapshot isolation: NMSI provides wait-free transactions, consistent snapshots, and exclusion of dual commits for write conflicts, but its snapshots are not totally ordered.MDCC achieves NMSI with a local counter per data center and saves one cross-data-center message for commits.

6. EVALUATION

MDCC was evaluated against two-phase commit and quorum writes using TPC-W and a micro-benchmark across five geographically diverse data centers. It achieved performance close to quorum protocols, improved with fast and commutative-update optimizations, and continued committing during a simulated outage.

  • Experimental setup: The evaluation deployed MDCC across five geographically diverse Amazon regions and compared it with two-phase commit and quorum writes.TPC-W and a custom micro-benchmark were used to measure latency, throughput, optimization effects, and outage behavior.
  • TPC-W write response times: MDCC write response times were closer to quorum writes than to two-phase commit because fast rounds commit in one inter-data-center message round trip.The comparison reports write transaction response times; reads were local and contributed little latency.
  • TPC-W transaction throughput: For 100 concurrent clients, MDCC transaction throughput was within 10% of quorum-write throughput, while two-phase commit throughput was significantly lower.The two-phase commit result is attributed to additional waiting and message overhead from its second round.
  • Overall evaluation: MDCC provided strong consistency for cross-data-center transactions at a cost similar to eventually consistent protocols.This summarizes the TPC-W latency and throughput findings.
  • Micro-benchmark response times: MDCC classic rounds performed similarly to two-phase commit, whereas fast configurations had similar response times and physical updates were slightly worse than commutative updates.Classic rounds required two inter-data-center round trips in the tested deployment; non-commutative conflicts could trigger two extra message delays.
  • Micro-benchmark throughput: Throughput increased from classic to fast rounds and from non-commutative to commutative updates.The optimizations reduced conflict likelihood and the messages required for conflict resolution.
  • Data-center fault tolerance: 173.5 ms before the outage increased to 211.7 ms afterward, while MDCC continued committing transactions across the data-center failure.The increase resulted from waiting for responses from a farther data center and from greater variance with fewer responding servers.

7. RELATED WORK

Related systems provide varied consistency, replication, partitioning, and transaction guarantees. MDCC distinguishes itself through strong, multi-record transactional consistency with synchronous replication, no required static partitioning or normal-case master, and single-round-trip commits.

  • Partitioned systems: Megastore synchronously replicates across data centers but statically partitions data into entity groups and uses a master to serialize transactions within each group.Across partitions, Megastore uses two-phase commit, while MDCC does not require static partitions or a normal-case master.
  • Consistency and replication: PNUTS uses asynchronous replication and timeline consistency per record, whereas MDCC provides full transactions across records with synchronous replication.The synchronous replication is described as preventing data loss from a data-center failure.
  • Consistency and replication: Dynamo uses quorum replication for eventual consistency, while MDCC provides stronger consistency and atomic multi-key transactions.Both systems use quorum reads and writes to tolerate partial failures, but their consistency and transaction guarantees differ.
  • Commit protocols: Walter uses asynchronous replication or two-phase commit, implying either possible data loss after a data-center failure or two message rounds.The passage states that combining Walter with MDCC could provide one-message-round commits without update-loss risk.
  • Transaction guarantees: COPS provides causal consistency but does not support transactions or atomicity, whereas MDCC makes all updates in a transaction succeed or fail together.MDCC assumes write-write conflicts may prevent a transaction’s set of updates from succeeding.
  • Paxos-based systems: Scalaris uses Paxos across several keys, while MDCC uses generalized Paxos and can bypass the master through fast Paxos.This distinguishes MDCC’s normal-case commit path from master-mediated Paxos execution.
  • Deployment scope: Spinnaker focuses on strongly consistent single-record transactions within one data center, while MDCC targets multi-data-center replication and multi-record transactions.The systems therefore differ in deployment scope and transaction granularity.
  • MDCC contribution: MDCC is presented as the first optimistic commit protocol providing read-committed consistency in a single round trip across all involved nodes.Its design leverages demarcation and escrow ideas and uses Generalized Paxos as the commit protocol.

8. CONCLUSION

MDCC combines a programming model for variable wide-area latencies with an optimistic commit protocol for strongly consistent synchronous replication. It sustains data center failures without compromising availability or consistency at a cost similar to eventually consistent protocols, while future work targets broader language support and further protocol optimizations.

  • 8. CONCLUSION: MDCC combines a transaction programming model for wildly varying wide-area latencies with a new optimistic commit protocol for synchronous replication.The programming model targets user-facing transactions, while the protocol exploits rare conflicts or commuting updates.
  • 8. CONCLUSION: Future work includes extending the programming model to C++, Java, Ruby, and .Net, plus runtime and batching optimizations and integration with additional read strategies.The authors specifically identify client-locality strategy selection, batching, and PSI as future avenues.
  • 8. CONCLUSION: One message round-trip across data centers in the normal operational case enables strong consistency at a cost similar to eventually consistent protocols.The paper describes this as the first transaction model and commit protocol for the wide-area network with that combination.
Loading 1203.6049v1…