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.
Fig 1. Leaderless broker fleet writes Kafka batches to S3, with Conflux shards as sequencers and metadata databases for S3-stored Kafka data.
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:
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.
Fig 2. VirtualLog abstracts the log as a whole, with a virtual address space. Each Loglet abstracts a log segment, with one active segment.
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.
Fig 3. When a Loglet must be replaced, it is sealed, a new active Loglet added and the log metadata committed.
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.
Fig 4. Reconfiguration moves the system from one steady state configuration to another in response to failures, policy triggers or other factors such as load balancing.
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).
Fig 5. StripedLoglet
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).
Fig 6. The NativeLoglet, a quorum-replicated Loglet.
Loglet composition via append is the problem. This now brings us to the new abstractions: AtomicLog and LogDrive.
Fig 7. The Loglet is decomposed into the AtomicLog and LogDrive abstractions.
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.
Fig 8. Depicts the AtomicLog and LogDrive abstractions in two Conflux instances
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:
Acquire the next free slot from the sequencer (the slot is the address)
Write the append value to the acquired address via the LogDrive
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).
Fig 9. A snapshot of sequencer state compared to LogDrive state
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.
In this post we’re going to ignore how seal comes into play, we’ll look at that in a subsequent post.
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.
Fig 10. Fast and slow path checkTail
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 following can be computed from a weakTail result:
T ==
min(H) or N if H is emptyAddr written ==
addr < N and addr \notin HAddr unwritten ==
addr >= N or addr \in H
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.
It’s worth noting that the sequencer’s view and the backing storage’s view of the contiguous tail regularly diverge. From the example earlier, once address 3 is written, if you call weakTail on the LogDrive, it will return N=7,H={5} thus T=5. However, until completeSlot(3) is called, the sequencer sees T=3. This has correctness implications. For this reason, the slow-path is only used once the AtomicLog is sealed (via a linearizable register). Thus once the slow-path has been invoked once, the fast-path will never be invoked again (avoiding diverging results between callers of fast and slow path).
Why N + H and not simply T?
Why does the LogDrive weakTail return {N, H} instead of simply T? And why is it called a weak tail? We cover the former in this post (it's needed for LogDrive composition) and the latter in the next post (it’s about weak semantics).
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.
Fig 11. Singleton primitive LogDrive, StripedLogDrive over primitives, QuorumLogDrive over primitives.
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.
Fig 12. The root LogDrive is a QuorumLogDrive over three regions, where each region is striped across two DynamoDB tables.
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.
For example, with a StripedLogDrive of 3 child PrimitiveLogDrives, any given read/write call is mapped to a read/write call of the correct child LogDrive, with address translation between the parent address space and the child address space, both of which are always contiguous.
Fig 13. Depicts the routing of writes and the mapping of the root LogDrive address space to its children.
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.
Fig 14. Swiss cheese individually, but globally contiguous quorum-written
A scalar child tail is insufficient because it loses information about writes above the child’s first hole. For example:
Fig 15. Left and write return the same child T values, but correspond to different global T value.
Each child may have a different pattern of holes within its write window, and the QuorumLogDrive must determine the global status of each address based on the richer N, H result of its children. The specific algorithm that the QuorumLogDrive uses to merge the weakTail results of its children into its own combined weakTail is detailed in the paper and also in my TLA+ specification.
Motivations Behind the Log Drive
One motivation behind this work was to make it easier and faster to adapt to changing cloud services and, just as importantly, changing cloud service pricing.
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.
This lowers the cost of adopting a new storage service. If a cloud provider introduces a cheaper, faster, or otherwise more suitable storage primitive, supporting it does not require reimplementing sequencing, replication, striping, or the rest of the shared-log stack.
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.
The same composition machinery can therefore be reused over different primitives and nested arbitrarily: quorums over stripes, stripes over quorums, and even compositions involving heterogeneous backing stores. As long as a Primitive LogDrive satisfies the LogDrive API, it can participate in these higher-level compositions without those layers needing to know anything about the underlying storage service.
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.
The combination is powerful: LogDrive provides a way to construct different durability configurations from reusable building blocks, while Virtual Consensus provides a way to transition between those configurations over time. This makes the storage layer adaptable to changes in cloud services, performance characteristics, failure requirements, and pricing without having to rewrite the shared-log stack.
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.
Murat Demirbas just wrote a great piece on Modularity abstraction versus Modeling abstraction where he compares and contrasts abstraction in terms of modularity and abstraction in terms of reducing something to its very core behavior. A key heading in that post was titled: Modularity abstraction hides. Modeling abstraction reduces.
Dominik Tournow recently tweeted something along similar lines about modeling abstraction: “Systems design is the process of reduction: reduce a problem and its solution to their very essence. When you've found the right abstraction, there are no transformations, no translations, no mappings, no workarounds.“
I think this is a useful lense through which to view the LogDrive paper.
Having worked on Apache Pulsar and Apache BookKeeper, I can tell you that BookKeeper has both striping and quorums built in. But what it doesn’t have is a set of formalized abstractions that allow for arbitrary composition based on composable building blocks over a diverse set of backing storage that the AtomicLog and LogDrive give you. BookKeeper is akin to the NativeLoglet.
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.