Spots

Semi-Linearizability: Cut Coordination, Keep Invariants

Geo-distributed systems often treat every operation as if it needed the same level of coordination. The result is a blunt trade-off: either pay global tail latency and bandwidth for linearizability, or accept broad inconsistency. Semi-linearizability offers a third path — exploit asymmetric (directional) dependencies between operations so that only the few ops that truly need global ordering use consensus, while the common-case ops proceed locally and fast.

In this article I'll explain the core idea

In this article I'll explain the core idea behind semi-linearizability, show how the DeMon prototype implements it, walk through a concrete auction example, and give a practical migration checklist you can use to start removing coordination from 50–70% of your writes. What is semi-linearizability?

Semi-linearizability is a consistency model that distinguishes operations

Semi-linearizability is a consistency model that distinguishes operations by the ordering relationships they require relative to other operations. Instead of forcing the entire system to provide a single uniform guarantee (e.g., linearizability), semi-linearizability defines three classes of relationships: Strong (linearizable) operations: require a global, strongly-ordered execution.

Weak operations: may execute locally and be asynchronously

Weak operations: may execute locally and be asynchronously propagated, provided their causal relationships to strong operations are preserved. Semi (or intermediate) operations: a hybrid that may require additional ordering constraints in one direction.

The key observation: many applications have asymmetric dependencies

The key observation: many applications have asymmetric dependencies. For example, in auctions a CloseAuction must observe all prior Bids that are relevant, but individual Bid operations don't need to be globally serialized against every other Bid. Semi-linearizability expresses those asymmetries and maps them to different coordination primitives. How DeMon realizes the model (high level) DeMon is a prototype that implements semi-linearizability with three primitives: Causal broadcast for weak operations (fast, local execution and asynchronous dissemination). Targeted consensus (e.g., OmniPaxos) for strong operations to establish a small, totally-ordered log.

Watermarks (vector-clock style summaries) to bridge weak and

Watermarks (vector-clock style summaries) to bridge weak and strong paths: when a strong op is proposed it attaches a watermark that tells consensus which weak ops must be considered ordered before the strong op.

A replica accepts a weak op, applies it

A replica accepts a weak op, applies it locally, and returns to the client immediately. The op is then causal-broadcast.

A strong op is proposed through consensus and

A strong op is proposed through consensus and carries a watermark summarizing the set of weak ops that must be ordered before it.

When a consensus entry is applied, replicas use

When a consensus entry is applied, replicas use the watermark to ensure any previously-applied weak ops are reconciled (possibly rolled back and replayed) so the strong ordering is respected.

This lets frequent weak ops be sub-millisecond (DeMon

This lets frequent weak ops be sub-millisecond (DeMon reports up to four orders of magnitude improvement for the common operation in RUBiS), while keeping the strong ops correct and linearizable. Auctions: a concrete example Auctions are a simple, practical example that exposes asymmetric dependencies.

News

Semi-Linearizability: Cut Coordination, Keep Invariants

Geo-distributed systems often treat every operation as if it needed the same level of coordination.

@spots #dev
Source: Dev.to
See more like this