Morty: How Re-Execution Shatters Concurrency Limits in Distributed Databases

Distributed databases have long grappled with a brutal trade-off: enforce strict serializable isolation to guarantee correctness, and watch performance crumble under contention. Systems like Google's Spanner or TAPIR often idle below 17% CPU utilization during high-conflict scenarios, throttled by exponential backoff and rampant aborts. Enter Morty, a radical approach unveiled at EuroSys 2023 that replaces wholesale transaction restarts with surgical re-execution of only outdated logic—delivering staggering throughput gains while preserving serializability for dynamic, interactive transactions.

The Serialization Bottleneck

Serializability (SER) demands that transactions appear to execute sequentially, avoiding anomalies like dirty reads or lost updates. Traditional systems enforce this by aborting transactions when conflicts arise—especially painful in geo-distributed environments where WAN latency extends conflict windows. As Murat Demirbas notes in his analysis, "High WAN latency stretches transaction durations, increasing the window for conflicts." Morty confronts this by rethinking the root constraint: serialization windows. These temporal spans—defined per object from a read's commit to a write's commit—must not overlap for SER compliance. Figures 1 and 2 in the paper illustrate how overlapping windows force aborts in conventional systems, while Morty's re-execution realigns them with minimal waste.

Morty's re-execution avoids overlapping serialization windows that doom traditional approaches (Source: EuroSys '23 paper)

How Morty Rewrites the Rules

Morty's architecture hinges on two innovations:

1. Read Unrolling via Continuations: Instead of aborting a transaction encountering a stale read, Morty rewinds execution to the point where the outdated data was accessed—thanks to transactions structured in Continuation-Passing Style (CPS). This asynchronous pattern (familiar in Node.js or Go) exposes control flow explicitly. Morty's API—Get(ctx, key, cont), Put(ctx, key, val), Commit(ctx, cont)—allows resuming from cont after replacing invalid reads. As Demirbas explains, "Re-execution reuses the context, shifts the stale read forward, and resumes execution."

2. A Priori Ordering with Adaptive Execution: Morty assigns each transaction a speculative timestamp at inception, establishing an immutable order. If execution deviates (e.g., a read misses a newer write), it doesn't revise the order—it re-executes to align with it. Crucially, Morty ignores read validity during execution, allowing speculative reads from uncommitted writes. Validation occurs only at commit-time via quorum-based checks:

# Simplified Morty commit validation pseudocode
def validate(transaction):
    if reads_missed_writes(transaction) or writes_missed_by_others(transaction):
        return Abandon  # Trigger re-execution
    elif dirty_reads(transaction) or reads_from_garbage(transaction):
        return Abort
    else:
        return Commit

This minimizes "validity windows"—the period between a dependency committing and the transaction committing—which directly impacts throughput.

Performance That Demands Attention

Morty's evaluation dispels any doubt about its impact. On TPC-C benchmarks, it achieved 7.4x the throughput of Spanner-style systems and 4.4x over vanilla TAPIR. For the high-contention Retwis workload, results were jaw-dropping: 96x higher throughput than TAPIR. CPU utilization soared to 35.3k txn/s on 20 cores, while Spanner and TAPIR plateaued early due to abort storms.

Throughput scaling under Retwis workload: Morty (blue) vs. TAPIR (red) and Spanner-style (green) (Source: EuroSys '23 paper)

Why This Matters Beyond Academia

Morty isn't just incremental—it challenges decades of concurrency orthodoxy. Unlike CockroachDB's read-refresh (which restarts entire transactions on conflicts), Morty's granular re-execution salvages partial progress. Its CPS-based API also offers practical hooks for modern async frameworks. While the approach demands developer familiarity with continuation patterns, the performance payoff for contended workloads—like financial systems or real-time inventory—could redefine scalability ceilings. As Demirbas observes, "Morty is one of the most technically rich papers on serializability in recent years." For engineers battling the latency-throughput tradeoff, Morty’s blend of speculative daring and surgical precision might just be the escape hatch from concurrency purgatory.

Source: Murat Demirbas' blog, based on the EuroSys '23 paper "Morty: Scaling Concurrency Control with Re-Execution"