Paper Summary: On The Purpose Of Clocks To Enforce Consistency Inward The Cloud

This newspaper is past times Manuel Bravo, Nuno Diegues, Jingna Zeng, Paolo Romano, Luis Rodrigues, in addition to appeared inwards IEEE Data Engineering Bulletin 2015.

The purpose of this newspaper is to revisit how the logical in addition to physical clock concepts are applied inwards the context of developing distributed information shop systems for the cloud in addition to review the selection of clocks inwards relation to consistency/performance tradeoffs.

The occupation of clocks inwards weak consistency information stores 

Dynamo employs sloppy quorums in addition to hinted hand-off in addition to uses version vector (a special representative of vector clocks) to rails causal dependencies inside the replication grouping of each key. A version vector contains 1 entry for each replica (thus the size of clocks grows linearly alongside the give away of replicas). The purpose of this metadata is to notice conflicting updates in addition to to last used inwards the conflict reconciliation function.
Here is a link to my Dynamo review.

COPS is a geo-replicated datastore in addition to it assigns a scalar clock to each object. Clients hold the terminal clock value of all objects read inwards the causal past. Updates piggyback their dependencies when beingness propagated to other information centers. When a information catch receives an update propagated past times around other information center, it solely makes it visible when its dependencies are satisfied. COPS provides a partial assort of transactions called causally consistent read-only transactions which render versions of the read objects that belong to a causally consistent snapshot. A two-round protocol implements these transactions. In the worst representative the listing of dependencies tin grow in addition to tedious downwardly the system.
Here is a link to my COPS review.

The GentleRain protocol aims to cut back the metadata piggybacked on updates propagation in addition to to eliminate dependency checking procedures. The thought is to solely allow a information catch to brand a remote update visible in 1 trial all partitions (within the information center) bring seen all updates upwards to the remote update fourth dimension stamp. Thus, a customer that reads a version is automatically ensured to read causally consistent versions inwards subsequent reads without the remove of explicitly checking dependencies or beingness forced to expect until a causally consistent version is ready. In other words, GentleRain shoehorns causality inwards to physical clocks past times delaying updates.

ORBE uses vector clocks, organized equally a matrix, to stand upwards for dependencies. The vector clock has an entry per segmentation in addition to information center. Physical clocks are used for generating read snapshot times, in addition to ORBE tin consummate read-only transactions inwards 1 circular past times relying on physical clocks.

The occupation of clocks inwards potent consistency information stores

Clock-SI assumes loosely synchronized clocks that solely movement forward, in addition to provides Snapshot Isolation consistency, where read-only transactions read from a consistent (possibly multi-versioned) snapshot, in addition to other transactions commit if no object written past times them was too written concurrently. To ensure security against clocks skews, Clock-SI introduces delays to read operations.  Here is a link to my Clock-SI review.

Google Spanner employs TrueTime (which employs GPS in addition to atomic clocks), in addition to provides a potent consistency property: external consistency, which is too known equally strict serializability. To ensure security against clock skews, Spanner too introduces delays to read operations, in addition to too delays commits inwards update operations to supply strict serializability. Here is a link to my Spanner review.

FinallyHere is a link to our Hybrid Logical Clocks (HLC) work.

I am quoting from the "On the occupation of Clocks to Enforce Consistency inwards the Cloud" newspaper nigh HLC: "Unlike Spanner, CockroachDB does non assume the availability of specialized hardware to ensure narrow bounds on clock synchronization, but relies on conventional NTP-based clock synchronization that oft imposes clock skews of several tens of milliseconds. HLC is thus especially beneficial inwards this case, at it allows for ensuring external consistency across causally related transactions piece sparing from the costs of commit waits."

Discussion 

The newspaper has an intriguing give-and-take section. It makes the observation that nosotros practice non fully empathise the trade-offs betwixt logical in addition to physical clocks yet, in addition to mentions that HLC is an interesting in addition to promising approach to investigate these tradeoffs. It gives around comparisons of the inwards a higher house protocols to present that fourth dimension (in price of its precision in addition to comprehensiveness) is a resources that tin last a component inwards the performance in addition to consistency tradeoffs inwards distributed information stores. The newspaper too talks nigh the costs of totally-ordered versus concurrent operations inwards distributed datastores. I constitute that this give-and-take brand similar points alongside my "distributed is non necessarily to a greater extent than scalable than centralized" post.

Use of clocks inwards distributed datastores for consistency/performance tradeoffs is sure an interesting in addition to fruitful question expanse nowadays.

So how does your favorite information shop occupation clocks/version-stamps? How would changing to a dissimilar clock scheme behave on performance versus consistency tradeoffs inwards that information store?

Earlier I had discussed nigh the occupation of clocks inwards Granola, in addition to how upgrading to HLC tin amend performance in addition to throughput.

Share this post