Chris Kim's Digital Garden

14-SNOW Theorem

Properties3
description—
tagsarea/distributed-systems, topic/snow-theorem
aliases—

4 min read

SNOW Theorem

The SNOW theorem says:

  • A distributed RO (read-only) transaction cannot simultaneously provide all four SNOW properties:
    • Strict serializability
    • Non-blocking reads
    • One response per read
    • Conflicting Write transactions.

SNOW is about understanding this fundamental tradeoff.

Spanner’s Read-only Transactions Analyzed with SNOW

There are two RO transactions Spanner provides

  • Externally consistent read-only transaction
  • Serializable snapshot read

Both are one-round, lock-free, and always succeed. However, there is a crucial distinction between them under SNOW thoerem.

For example:

  • Externally consistent RO transaction is:
    • Strictly serializable
    • Possibly blocking
  • Snapshot read is:
    • Serializable
    • Non-blocking

SNOW clarifies this tradeoff as follows:

  • Externally consistent RO transaction has:
S + O + W
  • but snapshot read has:
N + O + W

SNOW Properties

S: Strict Serializability

Strict Serializability

N: Non-blocking operations

It cannot wait for

  • a lock to be released
  • another server to send a message
  • a concurrent write transaction to reach a safe state

The server respond immediately using its current local state.

O: One response per read

  • One round-trip per server
    • No message redirection
      • Centralized component such as coordinator
    • No retries
  • One version per response
    • Each server returns exactly one version of the requested object.

W: Write Transactions Compability

The system must allow atomic write transactions that spends data on multiple servers while read-only transactions may concurrently inspect that data.

This is more powerful than allowing only independent single-key writes. Multi-object write transactions make applications easier to program because the application can preserve invariants spanning several records.

The difficult case is precisely when (R) and (W) conflict and overlap.

Takeaway

SNOW theorem states that it is impossible for RO transaction algorithms to have all SNOW properties.

Why All Four Properties Are Impossible

Suppose:

Where:

  • (C_R): client executing read-only transaction (R)
  • (C_W): client executing write transaction (W)
  • (S_A): server holding A
  • (S_B): server holding B.

Each server receiving write operation has a transition point (T), usually indicated by timestamp, before which reads return old values and after which reads return new values.

However, the transitions need not occur simultaneously. Consequently, there can be an interval during which:

  • S_A has made W visible
  • S_B has not yet made W visible

Furthermore, because network messages can be delayed independently, the following execution is possible:

Time moves downward

S_A                              S_B
 │                                │
 t_A: W becomes visible           │
 │                                │
 read A arrives → returns new     │
 │                                │
 │              read B arrives → returns old
 │                                │
 │                          t_B: W becomes visible

Then, the RO transaction receives:

R = (A_new, B_old)

Why system can’t repair the result

  • Because of (N), neither server may wait to coordinate with the other server.
  • Because of (O), the client cannot validate, retry, or request another version.
  • Because of (W), the conflicting write is allowed to execute concurrently.
  • The mixed result violates (S), because it cannot be placed before or after atomic transaction (W).

Therefore, S is not achievable with rest of the properties.

A Deeper Look at SNOW

SNOW Is Tight

Any combination of 3 properties is possible:

CombinationSacrificed propertyExampleMeaning
(S+N+O)WCOPS-DWStrong immediate one-round reads, but no general conflicting write transactions
(S+N+W)ORIFLStrong non-blocking reads with writes, but multiple responses/rounds
(S+O+W)NSpanner-ROStrong one-round reads with writes, but reads may wait
(N+O+W)SSpanner-SnapImmediate one-round reads with writes, but weaker/stale consistency

This means the set {S,N,O,W} is minimal: removing any one property makes the remaining three achievable.

Optimality

  • SNOW-optimal: have any 3 properties
  • Latency-optimal: have property N and O

Usage of SNOW

Study existing systems

SNOW and latency-optimal systems:

  • Spanner-Snap
  • Yesquel
  • MySQL Cluster

Systems with room for improvement:

  • COPS
    • Causal consistency
    • Non-blocking reads
    • At most two rounds
    • No conflicting multi-object write transactions

Improve existing systems

COPS-SNOW

  • Adds one-response property while retaining now-blocking reads
  • Is therefore latency-optimal
  • The algorithm improves latency within COPS’s existing weak consistency and write model.

SNOW Insight

The design principle is:

To optimize reads, shift coordination overhead to writes.

Possible transformations include:

  • block writes instead of reads;
  • add metadata to writes;
  • make writes communicate with more servers;
  • establish visibility information during commit;
  • make the write path ensure that future reads can answer with little coordination.

This is attractive for read-heavy workloads.
However, the cost doesn’t disappear. The system is choosing where to pay it.

SNOW Helps Performance Improvement

Significantly Lower Latency

N and O ensure the latency-optimal properties of systems.

Higher Throughput

Although SNOW is not focused on improving throughout, it can improve throughput performance as well. Regarding optimizing performance, look into 15-Performance-Optimal Read-Only Transaction

Backlinks