GO TO A SECTION

↑ ↓ to navigate · Enter to openExplore all sections →
FDEInterviews logo
PVLDB 2025

K2: On Optimizing Distributed Transactions in a Multi-region Data Store with TrueTime Clocks (Extended Version)

K2 combines bounded clocks, multiversion transactions and replica epochs. Learn what each mechanism guarantees, where the throughput gains come from, and why newer data can still be unsafe to read.

Breakdown by FDE Interviews · 13 min read · Updated

About the original · 2025
AUTHORS
Song, Wang, Chen, Feng, Feng, Fang, Cui, Kong
FROM
University of Hong Kong, Shanghai Jiao Tong University, Huawei Cloud, Shanghai AI Laboratory
PUBLISHED
Apr 2025 · PVLDB 2025
IN THIS BREAKDOWN · 10 SECTIONS

You can read 13% of this breakdown.

01

The paper in one minute

A database can know which transaction came first and still be unable to serve a safe read from a remote replica. The replica may have received a later write while an earlier transaction's effects remain in flight. K2 studies both problems: ordering transactions across regions and deciding when their effects can become visible elsewhere.

The design uses clocks with a bounded uncertainty interval, called TrueTime clocks in the paper. It builds three mechanisms around that assumption. K2-TB gives coordinators short-lived batches of timestamps so that every transaction does not need an oracle round trip. K2-MVTO orders transactions by their start timestamps and keeps multiple versions, including unresolved writes. K2-VCR assigns epochs that help replicas construct consistent read views.

The benchmark reports substantial throughput gains, but the baseline matters. The large TPC-C comparison is against the authors' implementation of a distributed two-phase-locking protocol with bounded clocks. It is not a benchmark of the managed Google Cloud Spanner service. The experiments also use asynchronous cross-region replication, which affects what the commit latency includes.

This is a distributed database paper from April 2025. It is unrelated to the Kimi K2 language model.

THE IDEA, VISUALLY
K2: THREE DIFFERENT COORDINATION COSTS A timestamp cannot tell you what arrived. Allocate time K2-TB Bounded timestamp batches Fewer oracle round trips Order transactions K2-MVTO Start timestamp + versions Resolve conflicting writes Serve replica reads K2-VCR Epoch cuts + replay progress Resolve undecided writes THE REPLICA MUST ESTABLISH A READ VIEW Serialization order: which transaction comes first? Visibility: which complete transaction effects can this replica expose? Mechanism overview from sections 4–6. No throughput claim or implementation benchmark.
K2 separates timestamp allocation, transaction ordering and replica visibility. The arrows show the relationship between mechanisms, not every network message. A clock bound does not establish that a replica has received all writes needed for a read.
Research notes: the problem, approach and results
2.32×

peak TPC-C throughput relative to MVTO-HLC (section 7.3.1)

9.82×

peak TPC-C throughput relative to the authors' d2PL-TTC baseline (section 7.3.1)

5 regions

experimental deployment, with asynchronous cross-region replication (section 7.1)

THE PROBLEM

Multi-region transactions pay for timestamp allocation, conflict handling and the coordination needed to expose consistent replica reads.

THE IDEA

Batch bounded timestamps, order multiversion transactions by start time, and assign coordinated epochs to control visibility on replicas.

THE RESULT

The authors report higher throughput in their experimental store. The gains depend on the workload, baseline protocol and replication configuration.

02

Why it matters to an FDE

An agent reserves inventory, then reads the order from another region. A correct application workflow still depends on the database's transaction and replica-read contracts. If the read can return a partial transaction or miss a completed reservation, a prompt change will not repair it.

K2 gives you useful questions for that deployment. Is the delay in acquiring a timestamp, resolving conflicting transactions, persisting a decision, or waiting for a replica to catch up? Which operations require current data, and which can accept an explicitly older snapshot? Those questions lead to different configuration choices and different measurements.

Use this paper to understand a storage engine's claims and to design evaluations. Building a replacement transaction engine inside an application is a poor default. Start with the consistency guarantees of the database you already operate, then reproduce the customer's failure under controlled replication delay. The consistency and CAP concept explains the vocabulary needed to describe that failure precisely.

THE FULL BREAKDOWN

Understand the mechanism. Try it on a real problem.

Unlock this breakdown and 294 more papers.

Premium opens every paper in full, plus every answer, concept, course and guide on the site. One payment for six months of access.

6 months · One payment · No auto-renewal

Get Premium · ₹2,000 / $25
  • ◇1 architecture diagram
  • </>2 runnable code blocks
  • ▦3 results tables
  1. 03Key takeaways

    Six distinctions for interpreting bounded-clock transactions and replica reads

    Free account
  2. 04How it works

    Follow a transaction through timestamp batches, write streams and replica epochs

    Premium
  3. 05The numbers that matter

    Read the TPC-C comparisons with their baseline and replication conditions

    Premium
  4. 06Try it yourself

    Reproduce a replica that has newer writes but cannot expose a complete snapshot

    Premium
  5. 07Where it breaks

    Clock-bound violations, replica delays and recovery rules define the operating limits

    Premium
  6. 08Using it on a deployment

    Build a consistency experiment before making a clock or database migration decision

    Premium
  7. 09Interview angles

    Explain the mechanisms behind ordering, atomic visibility and benchmark comparisons

    Premium
Back to the paper library →