In July, several Confluent colleagues and I published The LogDrive: Composable Durability for Cloud-Based Shared Logs. The paper evolves the concepts of Virtual Consensus in Delos by decomposing the Loglet abstraction into AtomicLog and LogDrive, moving composition below sequencing to a new durability abstraction. This post describes these new abstractions in the context of Virtual Consensus, focusing on how they support RAID-like composability for shared logs.

The ideas of the paper came out of a research project led by Mahesh Balakrishnan, Gardner Vickers, and Lucas Bradstreet. The project itself was to build a Kafka-on-S3 service to run in Confluent Cloud and the project ultimately became K2 or Kora 2, the next evolution of the Kora engine (which powers Confluent Cloud’s Kafka service). The first product built on K2 was Freight Clusters (Kafka on S3). The research that led to the LogDrive paper originated in Conflux, the scalable metadata service in K2 which acts as sequencer and metadata database for the fleet of leaderless brokers, akin to WarpStream’s agents.

Conflux is a multi-master state-machine replication service built over a shared log based on Virtual Consensus which uses cloud services such as S3 and DynamoDB as the backing storage service.

But this post isn’t about K2, nor even Conflux, its about extending the shared log protocol Virtual Consensus for better composability, specifically, being able to use RAID-like semantics to build logs with striping and quorums over diverse backing storage without having to rewrite the stack.

A brief recap of Virtual Consensus

I recommend reading my previous posts on Virtual Consensus to better understand this post:

• An Introduction to Virtual Consensus in Delos

• Steady on! Separating Failure-Free Ordering from Fault-Tolerant Consensus

But in any case, I will do a quick recap to set the scene for describing the new abstractions introduced by the LogDrive paper.

Traditional replicated-log protocols tend to combine sequencing, durable storage, failure handling, and membership changes. Virtual Consensus separates these responsibilities between a VirtualLog and a sequence of Loglets.

The VirtualLog exposes one logical address space over a chain of independent Loglets. One Loglet is active, while its predecessors are sealed. The active Loglet provides the steady-state data path: it accepts appends and establishes a durable order within a fixed configuration—failure-free ordering. Basically the happy steady state where everything is running fine.

The VirtualLog provides the control plane. When the active Loglet experiences a failure and must be replaced, the VirtualLog seals it, records its final tail, and extends the chain with a new Loglet.

Virtual Consensus separates the protocol into failure-free ordering (Loglet) and fault-tolerant consensus (VirtualLog). A Loglet does not need to implement recovery from partial failure, such as leader elections or membership changes. In that sense, it can be much simpler to implement than Raft. It only needs to order entries with a fixed configuration and provide fault-tolerant seal and checkTail operations so that the VirtualLog can terminate the segment safely.

The Problem With Append and Loglet Composition

There is a limitation to the Loglet abstraction when it comes to Loglet composition. By composition I mean building Loglets that are composed of other Loglets. For example, building a generic QuorumLoglet over a set of child Loglets, or a StripingLoglet that stripes writes across a set of child Loglets.

The fundamental write operation of the Loglet is append(value) -> address.

An append both assigns a position and stores the value.

Striping works despite this coupling of sequencing with storage. A StripedLoglet routes each append to one child Loglet append and translates the returned child address into its own address space. This works provided that each child allocates contiguous addresses (for address translation between child and parent address space).

But while append can work for striping, it does not compose cleanly for a QuorumLoglet. A parent can forward an append to several child Loglets, but each child independently assigns the address. Partial failures and retries may place corresponding values at different addresses across the child Loglets, creating divergence.

An external sequencer could assign positions first, but the Loglet API has no operation for storing a value at a caller-selected address (it only has append). The parent would have to ignore the children’s ordering and somehow add its own sequencing and reordering machinery. Doesn’t sound like much fun.

In Delos, quorum replication was therefore implemented inside the NativeLoglet. The NativeLoglet consists of a sequencer and a set of Log Servers. The sequencer assigns an address to each append and then writes the value at that address to a quorum of Log Servers. Crucially, the Log Servers expose write(address, value), not append(value).

Loglet composition via append is the problem. This now brings us to the new abstractions: AtomicLog and LogDrive.

Making Loglets More Composable

The AtomicLog together with the LogDrive is an implementation of the Loglet API. From the VirtualLog’s perspective, AtomicLog is simply another Loglet: it supports append, readNext, checkTail, prefixTrim and seal, and it can be replaced through the normal Virtual Consensus reconfiguration mechanism.

The further decomposition of the Loglet is as follows:

• The AtomicLog is responsible for sequencing and general log semantics but delegates durability. Sequencing/addressing is achieved via a soft-state sequencer (which we can consider is part of the AtomicLog).

• The LogDrive (sitting below the AtomicLog) is concerned with durability rather than sequencing. It exposes a flat numbered address space of durable single-value registers together with weakTail, an operation that lets AtomicLog reconstruct the tail from backing storage after the sequencer has disappeared. 

Composition into stripes and quorums exists at the LogDrive level, below sequencing. That is, composition is via the LogDrive API, not the AtomicLog (Loglet) API.

The LogDrive API does not include append, as composition requires writes to use caller-defined addresses:

interface LogDrive {
  void write(long address, ByteBuf payload);
  ByteBuf read(long address);
  TailDesc weakTail(int K);
  struct TailDesc {
    long nonContiguousTail;
    Set<Long> holes;
  }
}

Appends

An AtomicLog append consists of a three step process:

1. Acquire the next free slot from the sequencer (the slot is the address)

2. Write the append value to the acquired address via the LogDrive

3. Complete the slot

The sequencer is essentially a map of: address -> {FREE, ACQUIRED, COMPLETED}, though the sequencer uses the term slot instead of address. 

Multiple addresses can be written concurrently using a windowed write discipline: the sequencer permits up to (K) appends to be in flight ahead of the contiguous log tail T. The contiguous tail is the first unwritten address and the non-contiguous tail is the lowest unwritten address after which all addresses are unwritten (or alternatively the last written address + 1).

On a completeSlot(slot) call, the sequencer blocks until all prior slots are also completed. In the figure above, we see that the window of four addresses which is being written to concurrently has holes in addresses 3 and 5. The LogDrive writes for 4 and 6 can finish out of order but their sequencer completeSlot calls cannot complete until all preceding slots have completed. Only once address 3 has been written to and completeSlot(3) is called, can address 4 complete and the contiguous tail advance to slot 5. So while writes to the LogDrive can complete out-of-order, the appends at the AtomicLog are strictly completed in address order.

checkTail

When a Loglet is unsealed, checkTail simply asks the sequencer what the tail is. This is the fast-path as the sequencer keeps all its state in memory. Should the sequencer become unavailable, then the AtomicLog can only discover the tail by inspecting log storage (slow-path). The LogDrive offers the weakTail command for this purpose.

While the AtomicLog checkTail returns a scalar contiguous tail (T) address, the LogDrive weakTail returns:

• N: the non-contiguous tail (first unwritten address after which all addresses are unwritten, or alternatively, the highest written address + 1)

• H: The holeset, the unwritten addresses within the write window.

As seen in Fig 9, the write window can create a Swiss cheese of holes at the tail of the log. The weakTail result implicitly describes the state of the write window. The write discipline maintains N − T ≤ K. Therefore, every hole lies in the address range [max(0, N − K), N), while all addresses below that range are guaranteed to be written.

The window provides concurrency while bounding the number of holes that incomplete or slow writes can create. Limiting the window size allows the tail to be recovered or checked efficiently by examining at most the last K addresses rather than scanning an unbounded address space. 

LogDrive composition

There are three main types of LogDrive:

• Primitive LogDrive: A thin interface over remote storage, such as a cloud database, KV store or object storage. For example, one might implement a DynamoDBLogDrive, or an S3LogDrive, which are thin shims.

• StripedLogDrive: A log drive with a set of child log drives where each child is a stripe. Maps addresses to stripes and performs address translation between its own address space and that of its children.

• QuorumLogDrive: Also has a set of child log drives. Each read, write, weakTail is a quorum operation over its child logdrives.

Striped and Quorum LogDrives call the LogDrive API of their children—the LogDrive API is the compositional interface. So we can compose LogDrives arbitrarily: quorums over stripes over primitives, or stripes over quorums over primitives and even over heterogenous primitives. The base of the tree must ultimately consist of primitive implementations.

read/write composition

A call to write(a, v) in the root LogDrive will flow down as calls to write(a,v) in child LogDrives, according to the type LogDrive.

A QuorumLogDrive forwards write(a, v) to its child LogDrives and waits for a write quorum (Qw). Flexible quorums apply here, where the read-quorum (Qr) is computed as N-Qw+1. So if N=3, Qw=2, then the Qr=2. If N=5, Qw=4, then Qr=2. Because the parent supplies a, every child receives the same value for the same address. Partial success can leave an address unwritten on some children, but it cannot cause their logical address assignments to diverge as independent child append calls can.

weakTail composition

The Loglet API checkTail command returns T, the contiguous tail (plus a boolean whether the Loglet is sealed). However, this is not enough for quorum composition. A single scalar value per child tail does not provide enough information for a QuorumLogDrive to compute its tail value.

The write window of each child LogDrive may individually resemble Swiss cheese of holes but when unioned together form a contiguous slice of quorum-written addresses.

Motivations Behind the Log Drive

Cheap adaptation to new storage services

A Primitive LogDrive is intended to be a thin adapter over some backing storage service such as DynamoDB, S3, or a KV store. Because it only needs to implement the small LogDrive API, a new primitive can be relatively simple, on the order of a few hundred lines of code rather than a new shared-log implementation.

Reusable composition

Striping and quorum replication live in generic StripedLogDrive and QuorumLogDrive implementations. These operate over the LogDrive API and therefore do not care whether their children are backed by DynamoDB, S3, S3 Express One Zone, or something else.

Evolving durability configurations over time

Virtual Consensus adds another useful property: different Loglets in the same VirtualLog can use different LogDrive configurations.

A log might initially use an AtomicLog backed by a singleton DynamoDBLogDrive. A later reconfiguration could extend the VirtualLog with a new AtomicLog backed by a QuorumLogDrive over several S3 Express One Zone LogDrives, perhaps spread across availability zones or regions. The old configuration remains responsible for its existing segment while new appends move to the new one, and the old segment can eventually age out as the log prefix is trimmed.

Final thoughts on Abstractions

You might be thinking that you’ve seen all these patterns before and there’s nothing groundbreaking here, and in some ways you’d be right. But what the paper contributes are the formalized abstractions.

The contribution of LogDrive is instead the abstraction: reducing durability to a numbered collection of single-value registers plus weakTail, while moving sequencing above it into AtomicLog. The interesting part is that the weaker abstraction is the more composable one. By reducing durability to its essential behavior, LogDrive provides a better building block for constructing shared logs.