This post continues to elaborate on Virtual Consensus and the new Loglet abstractions of the AtomicLog and LogDrive. My last post focused on composability, this post looks at log sealing.
A common aspect of segmented logs is that when extending the log with a new segment, the current active segment needs to be sealed to prevent further appends. This post discusses segment sealing in the AtomicLog and LogDrive abstractions.
I’m going to treat Virtual Consensus here less as a fixed API and more as a collection of architectural patterns and correctness requirements. The Delos paper defines a specific Loglet API, and the AtomicLog in the LogDrive paper implements that API verbatim. But the implementer has some flexibility regarding where the responsibilities related to seal enforcement live (which is discussed in this post).
The single value register
The LogDrive is an unusually weak abstraction. It is an abstraction over single-value linearizable registers (an address is only required to behave linearly if the caller(s) ensures that only one distinct value is ever written to it). Should callers attempt to write two different values to the same register, we get undefined behavior. This means we can write value V1 to register R1 once, twice, as many times as we want, but never V1 and V2. It’s kind of like write-once semantics, where the caller guarantees the write-once property not the register (so significantly weaker than a WOR).
So who guarantees that a given address (a given register) will only ever have one value proposed to it? The sequencer in the AtomicLog.
Fig 1. The sequencer ensures the single-value register property.
Delegating this responsibility to the AtomicLog rather than the storage service weakens the storage primitive we need. It also makes quorum composition cheaper. A general multi-writer ABD-style atomic register requires two rounds for a write: one to discover the latest version and another to install a newer value. With a single-value register there can be no competing value to discover, so a QuorumLogDrive can simply write the value to a write quorum in one round trip.
Multi-Paxos also achieves one quorum round-trip per append in the steady state, but for a different reason. Its leader has already completed Phase 1 for its ballot, amortizing that round across subsequent log entries. Crucially, Paxos cannot assume that only one value will ever be proposed for a slot: after a leader change, different leaders operating in different ballots may have proposed different values to the same slot. The acceptors therefore need ballot-aware semantics to reconcile these proposals. AtomicLog avoids this problem entirely as its sequencer is never replaced within an AtomicLog. If it fails, the AtomicLog is sealed and the VirtualLog moves to a new one.
From a system builder's perspective this is quite nice as we can use more types of backing storage service. Simply put, a Primitive LogDrive is not constrained to use a storage service that provides conditional writes or one with awareness of ballots or fencing mechanisms. Conditional writes are becoming more and more commonly supported across cloud services such as object storage and databases, but it's not everywhere.
So to recap, the LogDrive needs only single-value register semantics, not write-once registers (WOR) or conditional registers (CR).
This brings us to sealing
The Virtual Consensus in Delos paper provides some flexibility regarding seal semantics. At the architectural level, what Virtual Consensus really needs from sealing is an acknowledgement fence. Once the seal has taken effect, an append must not be allowed to return successfully. Importantly, that does not mean the append must be prevented from reaching storage. Delos explicitly allows a failed append to nevertheless become durable.
Within this space we have two broad types of seal that we can call strong and weak seals.
Strong seal: the seal is enforced inline by the append path
Weak seal: the data write operation is oblivious to sealing. The write can complete normally, but its success is conditional on a subsequent check of an independent seal register.
The seal in the LogDrive paper is the weak seal.
Strong seal on “active” storage
The NativeLoglet in the Delos paper uses a strong seal. The seal operation contacts the Log Servers of the Loglet, to set their seal bit. The seal bit is essentially, unset or set, idempotent and monotonic. Once set, it is forever set.
Fig 2. Example strong seal, where Log Servers cooperate in the sealing protocol and reject writes once the seal bit is set.
After sealing a NativeLoglet, a quorum-write by the sequencer will fail as the Loglet has been quorum-fenced. This approach is basically the same as what Apache BookKeeper does. Active, inline fencing is possible because the Log Servers are active participants in the protocol: they durably store the seal state and consult it when processing writes.
Weak seal on passive storage
I defined active storage as storage processors that can apply custom logic as part of the write. Likewise, I define passive storage as simply a (third party) storage service that has more limited semantics (such as S3, DynamoDB, etc, etc). Passive storage services generally lack the ability to fence an entity’s address space. Many support conditional writes which are fundamentally limited to specific individual addresses (or keys). Other services may not support conditional writes at all.
This is where the weak seal becomes useful. The weak seal is based on a seal register (another single-value register—you can only set it to True). The AtomicLog can represent the seal register as a LogDrive with a single address (0), configured the same way or differently to the Loglet address space (i.e. based on the same or different composition, with same or different backing storage service).
Fig 3. Checking the seal becomes the last step of an append. The data and seal registers can exist in the same backing storage or separate storage services.
With a weak seal, the seal register is checked post-write. To strictly comply with the Loglet API, the AtomicLog append must perform the seal check before returning. The downside of this approach is that it involves one more round-trip to check the seal register.
However, we could also split seal validation into its own Loglet API operation. This allows the VirtualLog to amortize the cost of the seal check by group-commit behavior (basically checking the seal status after a group of appends has completed).
The strong seal over passive storage
Implementing a strong seal over passive storage, within the AtomicLog/LogDrive context, starts getting a bit more involved.
For example, the sealer can potentially install barrier values ahead of the tail, such that once the seal is complete, we guarantee no further writes can succeed.
Fig 4. Barrier values written to the loglet tail to fence further writes
This requires a backing storage service with conditional writes. Correctness depends on placing that barrier safely relative to the in-flight write window. But it's more than that, for one, we have lost the guarantee that each address will only ever have one value written to it. Now, for any given address, we can have a normal value competing with a barrier value. Suddenly we’re entering the consensus arena.
For singleton Primitive Log Drives, this can be solved by Write-Once-Register semantics (we delegate consensus to the backing service). Whoever writes first wins. The barrier writer just needs to ensure that the normal value tail cannot advance. At least one barrier entry must be written ahead of the normal value tail, and no additional addresses below the barrier can remain writable. After that, we guarantee normal writers cannot progress.
For QuorumLogDrives it gets more complicated, as we’ll need conditional register semantics in the backing storage service coupled with a Paxos style of protocol. Importantly: regular writes can use ballot 0 as a fast path, skipping Phase 1 because the AtomicLog guarantees that no competing normal value will be proposed. But barrier entries will require the full two-phase protocol with ballot 1+, where the barrier writer will end up either completing a partial normal value write or completing its own barrier write.
There’s a bit to it and I don’t want to get bogged down here further, just know it starts getting deep into distributed systems consensus stuff.
Final thoughts
The LogDrive paper doesn’t discuss strong seals (or even define the terms strong and weak seal). It explores the LogDrive as the weakest, most reduced set of behaviors possible. But the implementer can take these ideas and apply strong seals all the same. There are a few interesting insights to remark on.
First, the extremely weak semantics of the LogDrive are possible because AtomicLog ensures that normal values never compete for an address. This is also why the AtomicLog sequencer is not recovered: if it fails, the VirtualLog seals that AtomicLog and moves to another one. If instead a new sequencer with a new epoch were to take over the same Loglet address space, we’d have competing values for the same address.
Weak sealing preserves this single-value invariant. The seal lives out-of-band, so the data addresses remain simple single-value registers. The cost is that acknowledgement must be gated by a post-write seal check, either per append or amortized over a group of appends.
Strong sealing avoids this post-write check cost. With active storage, fencing can be performed directly by the storage processes. This is where a strong seal is close to a no-brainer. With passive storage, an in-band barrier introduces a second possible value for an address and therefore breaks the single-value assumption, making things non-trivial for the QuorumLogDrive implementer.
So choose your trade-off. A weak seal keeps the storage abstraction as weak and portable as possible, at the cost of extra work pre-acknowledgement. A strong seal can avoid that cost, but may require more active participating storage or potentially adding more complexity to the storage protocol for more passive storage.