Making Geo-Replicated Systems Fast Every Mo Possible, Consistent When Necessary

Appeared inwards OSDI '12, Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Preguica, together with Rodrigo Rodrigues.

In social club to cut down latencies to geographically distributed users, big webservices companies (Google, Yahoo, Facebook, Twitter) replicate information across geographical regions. But replication across datacenters, practice cross-site consistency problems, which is farther complicated alongside the huge WAN latency delays. If you lot desire to bring strong consistent updates across sites, you lot bring to pay the toll inwards price of latency (basically you lot revert to doing synchronous replication via say Paxos every bit inwards MDCC). This is the ELC business office inwards the PACELC.

To alleviate this latency versus consistency tension, this newspaper proposes RedBlue consistency, which enables bluish operations to live fast/asynchronous (and eventually consistent) spell the remaining ruddy operations are strongly-consistent/synchronous (and slow). So a plan is partitioned into red and bluish operations, which run alongside dissimilar consistency levels. While red operations must live executed inwards the same social club at all sites (which brand them slow), the social club of execution of bluish operations tin vary from site to site (allowing them to live executed without requiring coordination across sites). "In systems where every performance is labeled red, RedBlue consistency is equivalent to serializability; inwards systems where every performance is labeled blue, RedBlue consistency allows the same laid of behaviors every bit eventual consistency."

To facilitate this ruddy bluish partioning, each plan performance u is split upwards into two components: a generator performance g_u alongside no side effects, which is executed exclusively at the primary site against roughly organization dry reason S, together with produces a shadow performance h_u(S), which is executed at every site (including the primary site).

This is only separation of concerns principle. The generator performance decides which dry reason transitions should live made spell the shadow performance applies the transitions inwards a state-independent manner. This separation leads to a fine-grained classification of operations, alongside potentially to a greater extent than execution paths leading to bluish operations. Also this leads to a unproblematic logic for shadow operations that tin live based on operations that are intrinsically commutative (increment/decrement, insertion/removal) or that commute via last-writer-wins strategy.

Red Blue rules

Now hither are the rules for labelling the [shadow] operations as ruddy or blue.

1. For whatever duo of non-commutative shadow operations u together with v, label both u together with v red.
2. For whatever shadow performance u that may outcome inwards an invariant existence violated,  label u red.
3. Label all non-red shadow operations blue.

This is unfortunately non an automated process. Developer has to manually partition the operations to generator together with shadow operations, together with later that mark them every bit ruddy together with bluish manually, past times next the higher upwards rules. As such, this is an error-prone procedure together with is difficult to scale.

The below is the description from the newspaper of how to occur rail of the order and consistency of red/blue operations:

When a generator performance completes, the coordinator must determine if the operation reads a coherent organization snapshot together with obeys the ordering constraints of a causal serialization. To practice this, the coordinator checks the timestamps of the data items read together with written past times the completing operation, together with compares them to the timestamps associated alongside operations completing concurrently together with the remote shadow operations that were existence applied simultaneously at that site. Upon successful completion of a generator performance the coordinator assigns the corresponding shadow performance a timestamp that is component-wise equal to the latest performance that was incorporated at its site, together with increments its bluish and, if this shadow operations is red, the ruddy ingredient of the logical timestamp. This timestamp determines the pose of the shadow performance inwards the RedBlue order, alongside the normal rules that determine that 2 operations are partially ordered if 1 is equal to or dominates the other inwards all components.

The newspaper reports an evaluation of this persuasion past times modifying the TPC-W together with RUBiS benchmarks on an online social network illustration study (Twitter is the Hello World of georeplication :-). The experimental results demonstrate that RedBlue consistency provides substantial performance gains without sacrificing consistency.

Discussion

Although the newspaper does non yell it, a really relevant locomote to this is the CALM conjecture together with the Bloom projection from UC Berkeley. The CALM regulation says that (1) logically monotonic distributed code is eventually consistent without any need for coordination protocols (distributed locks, two-phase commit, paxos, etc.) together with (2) eventual consistency tin live guaranteed inwards whatever plan by protecting non-monotonic statements ("points of order") alongside coordination protocols. It is piece of cake to encounter that the logically monotonic operations correspond to the bluish operations, together with non-monotonic operations jibe to red operations inwards the RedBlue work.

After Generalized Paxos. Another shortcoming of the RedBlue locomote is that it does non bring any fault-tolerance gear upwards in. It may live difficult to add together fault-tolerance every bit an after thought, together with then perchance it is best to intend of this locomote inwards the Generalized Paxos framework.

Share this post