CEP-15 proposes leaderless transactions across Cassandra partitions

Cassandra applications can face a difficult choice when related state spans partitions. Coordinating changes in application code adds a distributed protocol above the database. Packing all related state into one partition places a limit on how the model can grow. CEP-15 proposes general-purpose transactions to address that tension within Cassandra while preserving a leaderless approach.

The proposal record identifies Benedict Elliott Smith as its creator on September 5. Because a proposal can change, the technical account here uses revision 7 from that same day. That revision describes Accord and an incomplete prototype. Its claims are proposed protocol properties and reported prototype results, not guarantees delivered by a Cassandra production release.

I find this proposal interesting because Cassandra's active-active orientation is part of its appeal. Adding transactions is useful only if the design accounts for the distributed behavior that makes the database worth choosing. CEP-15 makes that requirement explicit through its latency and failure-tolerance goals, then describes mechanisms intended to support them.

The intended transaction can span arbitrary keys

The motivation is broader than making a conditional change to one partition. The proposed facility can operate atomically over any set of keys, with changes conditional on existing contents elsewhere in that set. Its goals include strict-serializable isolation, scalability without a new bottleneck and operation on commodity hardware. Those goals define the design problem before specifying its integration into Cassandra.

The proposal targets one wide-area round trip under normal conditions. It also seeks to keep latency and performance unaffected by any minority of failed replicas. Those statements describe intended properties of the protocol. They are not a measured latency guarantee for an arbitrary application, whose execution can involve dependencies and data reads as well as consensus.

Keeping that distinction avoids compressing a transaction into one message exchange. The proposal separately describes agreement on a timestamp and the execution needed to obtain data and apply an update. A claim about fast-path consensus should retain which phase it concerns. The execution description remains necessary even when the timestamp agrees on its first attempt.

The initial revision also proposes incubating Accord as a standalone library within the project. Cassandra integration is work to accompany that library. The prototype is reported to have undergone checks with Jepsen's Maelstrom tool and an in-tree facility, but the document explicitly calls it incomplete and unsuitable for production. That status establishes the significance of the event as a design proposal.

Timestamp agreement and dependencies serve different purposes

Accord's proposed ordering uses globally unique hybrid logical clocks. Each replica appends its own identifier to its logical clock value. The unique timestamp identifies an ordering position, while dependencies identify conflicting transactions whose execution may affect the transaction's result. Timestamp selection alone does not eliminate the need to account for those dependencies.

On the fast path, a coordinator proposes an initial timestamp to replicas. A replica accepts it if the timestamp is greater than the timestamps it has witnessed for prior conflicting transactions. It also returns information about transactions that may execute at a lower timestamp. When enough fast-path participants accept the original timestamp, the transaction agrees to execute at that timestamp.

The proposal contrasts this with requiring every participant to return an identical dependency history. Accord permits dependency sets to differ between coordinators. The sets must still include the dependencies required by the ordering conditions described in the protocol. Relaxing exact agreement about the set is intended to avoid costs associated with insisting on one precise dependency set.

This is a technical design claim, not permission to ignore conflicts. The subsequent execution phase still waits on relevant dependencies. The flexibility concerns which sufficient dependency sets replicas retain, while timestamps supply a consistent basis for deciding which dependencies must precede execution. Both parts appear in the proposed mechanism.

The slow path records a recoverable timestamp

If a replica cannot accept the initial timestamp, it returns a higher one. When the coordinator fails to obtain fast-path agreement, it chooses the highest timestamp it received and proposes it to a simple majority. The document explains that this round durably records which timestamp was selected. Different sets of received responses might otherwise have led coordinators to different choices.

That durability matters if the coordinator fails. A recovery coordinator needs to continue the same transaction using the decision already made. The additional round therefore serves a recovery purpose as well as supplying an ordering value after the original proposal failed. The proposal describes a newer recovery ballot as a condition that can prevent accepting the earlier coordinator's proposal.

The slow path also obtains a new dependency set. The coordinator discards the dependencies collected for execution on the fast path and uses the new information. This follows the changed timestamp choice. Carrying forward an old dependency interpretation without considering the new ordering position would miss a distinction the protocol description makes explicitly.

For the application designer, the relevant implication is that a failed fast path is part of the protocol's intended operation. It is not evidence by itself that the transaction must abort. The coordinator has a specified route to obtain an agreed timestamp and continue, subject to the recovery and dependency rules.

A reorder buffer trades waiting for timestamp order

The proposed reorder buffer addresses arrival-order differences between coordinators. The cluster determines clock-skew and point-to-point-latency information. Replicas buffer timestamp proposals long enough to allow potentially conflicting messages to arrive, then process them in timestamp order. The document describes the delay in terms of maximum skew and network latency, adjusted for the coordinator-to-replica path.

This means the fast-path objective includes deliberate waiting. A one-round agreement mechanism is not the same thing as processing every received message immediately. The buffer aims to avoid rejecting an older proposal merely because a newer conflicting proposal reached a replica first. Its timing assumptions are part of the mechanism that supports the fast-path claim.

The proposal also names unhealthy or stalled coordinators as a qualification to its arrival reasoning. That keeps the buffering argument tied to its operating assumptions. It discusses a possible refinement for heterogeneous networks in which a replica might wait only for messages from coordinators that need its participation to reach a fast quorum. That refinement is presented as a possible modification.

I appreciate that the latency goal comes with a concrete explanation of where waiting moves. Wide-area coordination still has to account for clocks and network paths. The reorder buffer proposes an explicit place to do so, allowing the design to be discussed in terms of its assumptions and state transitions.

Fast-path voters can be a subset of replicas

The proposal calls the replicas eligible to vote an electorate. It permits the fast-path electorate to exclude some replicas, reducing the votes required for a fast-path decision. The reasoning relies on intersections between possible fast-path quorums and the quorums used for recovery. It does not simply reduce the required votes without preserving an intersection argument.

The document illustrates the extreme case with only one reachable simple quorum. An electorate restricted to those reachable replicas has one possible fast-path quorum, and that quorum overlaps the simple quorums relevant to recovery. This is the proposed basis for retaining fast-path operation under the maximum failures the system tolerates.

The distinction between electorate and full replica set is central. A replica can belong to the data's replica set without being eligible for a particular fast-path vote. That separation is the design's answer to failure-related fast-path degradation. Its correctness depends on the quorum rules described in the proposal, rather than on treating a convenient set of reachable nodes as interchangeable voters.

Execution still waits for earlier conflicting work

After consensus, the coordinator sends reads to replicas of the participating shards, preferably in the same datacenter. Each receiving replica waits for dependencies to commit, then determines which have earlier execution timestamps. Those earlier dependencies must execute and apply locally before the read evaluates. The coordinator combines the responses to calculate an update and client result.

It then disseminates the update to replicas. Applying replicas also wait for the necessary earlier dependencies. These steps explain how agreeing on an ordering value relates to the actual values used in the transaction. The initial proposal leaves a substantial integration task, but it already specifies that the read and apply phases must respect the dependency order established by the protocol.