Body Of Body Of Water Vista: Gossip-Based Visibility Command For Speedy Geo-Distributed Transactions

the SLOG paper: 

SLOG uses a deterministic architecture to displace most of this communication exterior of conflict boundaries, enabling these transactions to last processed at high throughput. More specifically, SLOG relies on deterministic processing to avoid 2 stage commit. Once all parties concur to the plan, processing occurs (mostly) independently on each node, amongst the arrangement relying on the plan's determinism inwards fellowship to avoid replica divergence.

All multi-home transactions, no affair where they originate, must last ordered amongst honour to each other. For this SLOG employs a global log for ordering the multihome transactions amongst honour to other multi-home transactions as well as sends them to the regions where they are ordered amongst honour to single-home transactions.

Ocean Vista also orders transactions amongst honour to each other showtime as well as executes them solely afterward this ordering is stable. Ocean Vista explains this watch inwards damage of watermarks, but it is a real similar idea. Both papers appeared inwards VLDB'19. I gauge this is around other illustration of a concurrent regain of an watch whose fourth dimension has come.  

Gossip-based visibility control 

The presentation slides hither are nice, thus I volition borrow around figures from them to explicate the Ocean Vista algorithm. 

Ocean Vista (OV), uses multi-versioning to combine transaction control, concurrency control, as well as replication functions into a unmarried protocol, that gossips watermarks. 

The park synchronous transaction processing proceeds as: (1) Read all keys, (2) Compute, (3) Write all keys. In contrast OV reverses this: (1) write/replicate transaction amongst functors equally information version placeholders, (2) Read & Compute transaction 1 time watermark is cleared, (3) Perform asynchronous write to supervene upon the functors amongst the in conclusion values.

Here is the algorithm.

Transactions are totally ordered past times global versions generated based on synchronized clocks. The visibility watermark Vwatermark is a version number below which all transactions must convey completed their write-only operations (S-phase). All transactions amongst versions below Vwatermark tin last made visible safely, as well as the transaction fellowship is fixed because no transaction amongst a lower version may last created. 

The replica watermark Rwatermark is a version number, below which all versions of transactions must convey been fully replicated on all corresponding replicas. OV tin render consistent reads using RO (i.e., read from whatever replica) inwards the mutual illustration for transaction below the Rwatermark. The read-only functioning Read(key, ts) (ts < Vwatermark) retrieves the latest version no greater than ts for key. When ts < Rwatermark, the Read tin telephone yell upwards Get(key, ts) straight on whatever replica. Reading versions that convey been made visible but are non fully replicated (i.e., Rwatermark<ts<Vwatermark) is the solely illustration that requires reading from a quorum.

As far equally the write quorums go, writes/replications inwards the S-phase tin succeed inwards 1 circular trip inwards the fast path regardless of conflicts, as well as require 2 circular trips inwards the ho-hum path when besides many failed nodes are present. This has been a request of give-and-take inwards our Zoom Reading Group. Aleksey made this observation, as well as I intend he is right. It may last possible to avoid using fast Paxos for implementing OV replication inwards S-phase.

Why does OV protocol utilization the FastPaxos-like algorithm for replication? FastPaxos requires the utilization of larger "super quorums", however, OV replication is non client-driven, as well as a server specifically picks a unique timestamp for the replication. In FastPaxos, multiple commands may last tried on the same illustration (i.e. timestamp), requiring a larger quorum for recovery inwards phase-1 of Paxos amongst a smaller bulk quorum. However, inwards OV nosotros exercise non encounter such conflicts: the timestamps for transactions are *unique* as well as are assigned past times 1 node that coordinates replication. The solely possible conflict that nosotros saw happening is when a transaction showtime tries to replicate the command as well as thus issues an abort on the same timestamp. This arguably creates a write-write conflict on the same illustration (timestamp), but nosotros intend it tin last resolved past times establishing fixed precedence to brand aborts ever win over the regular writes. With precedence fellowship established, writing abort to a bulk of nodes should last sufficient to brand abort persistent as well as recoverable. We convey non reached a definite decision on why OV uses larger fast quorums, thus nosotros may silent last missing something inwards our agreement of the protocol.

Discussion

Comparing SLOG as well as Ocean Vista for differences is instructive. SLOG seems to be  to a greater extent than centralized, having both a dedicated primary per partitioning as well as a dedicated ordering layer for multi-partition transactions. OV employs aggregation based per portion gossipers to assistance hold traffic manageable, but that is non centralization per se. On the other hand, OV may convey around vulnerability areas due to NTP clock timestamping. (The newspaper dedicates a subsection explaining this is non a security employment but could displace around performance issues.) SLOG avoids that employment past times beingness to a greater extent than centralized.

SLOG, Ocean vista, as well as also TAPIR impose around restrictions to the transactions they allow. As SLOG puts it: "Unfortunately, inwards fellowship to exercise a deterministic innovation of execution, to a greater extent than noesis well-nigh the transaction is needed prior to processing it relative to traditional nondeterministic systems. Most importantly, the entire transaction (information regarding which information volition last accessed past times the transaction) must last acquaint during this planning process." Ocean Vista calls this functors implemented equally stored procedures.

Here is a video of the Ocean Vista presentation from our Zoom Reading group.

Share this post