Redesigning ZooKeeper's Session Model for Delos
ZooKeeper’s session semantics are the hardest part to reconcile with Delos. In ZooKeeper, every client operation happens within a session that provides failure detection and ordering guarantees. Delos, by contrast, offers linearizable operations on a shared log but permits proposals to be reordered before they are appended. This creates a fundamental mismatch: ZooKeeper requires strong total ordering within a session, while Delos only guarantees a single linearizable order across all operations.
ZooKeeper also provides infallible operation sequences within a session — for example, if operation A precedes B, B cannot progress unless A succeeds. Delos, however, allows operations to abort for reasons such as network failures or system reconfiguration. Additionally, Delos has no real-time primitives, which ZooKeeper relies on for session lifetime management, leader election, and failure detection.
To build Zelos, we had to resolve three main areas of impedance mismatch:
- Sessions and strong ordering within a session
- Session-based leases and real-time contracts
- Transparent migration of existing ZooKeeper applications
Reconciling Sessions with Linearizability
Delos’s linearizability model guarantees a consistent order for all operations, which is sufficient for most distributed applications. But ZooKeeper’s per-session ordering is stronger than linearizability: operations issued by the same client in a single session are totally ordered, regardless of when they are received by the ensemble.
Zelos handles this by layering session state on top of Delos’s shared log. Each session is represented as a state machine within the Delos framework, with session-specific metadata stored in the replicated state. The key insight is that while Delos allows proposals to be reordered, Zelos can enforce session ordering by batching operations from the same session and ensuring they are committed in sequence.
This approach requires careful handling of the guarantees ZooKeeper provides. Within a session, clients can issue operations that depend on earlier ones having succeeded. Zelos tracks session state in the Delos state machine, allowing it to reject operations that arrive out of order or that depend on failed predecessors. Cross-session operations, which ZooKeeper treats with weaker semantics, can be safely delegated to Delos’s linearizable order.
Managing Leases and Real-Time Contracts
ZooKeeper’s lease mechanism is critical for failure detection and leader election. Clients must heartbeat within a lease interval to keep their session alive. If the heartbeat is missed, the session expires and all ephemeral znodes associated with it are removed. This requires real-time guarantees that Delos does not natively provide.
Zelos implements session leases on top of Delos’s log by recording session heartbeats as log entries. Each replica tracks the last heartbeat time for every session. When a session’s lease expires, Zelos initiates session termination through the shared log, just like any other state change. The real-time component is handled by each replica’s local clock, albeit with explicit consideration for clock skew across the ensemble.
Transparent Migration Path
Meta’s fleet has numerous services that use ZooKeeper’s API directly. Rewriting all of them is not feasible. Zelos therefore exposes the same client-facing API as ZooKeeper, including the wire protocol, so existing clients can connect without modification.
The migration strategy relies on running Zelos and legacy ZooKeeper clusters side by side, then moving clients over incrementally. This requires that data and session state be synchronized between the two systems during the transition. Zelos replicates the entire ZooKeeper data tree — znodes, their data, ACLs, and ephemeral ownership — into the Delos-backed state machine. When a client switches from a legacy cluster to a Zelos cluster, its session state is re-established on the new system.
Because Zelos is a feature-compatible ZooKeeper implementation at the API level, legacy applications continue to function unchanged. The underlying consensus, however, is handled by Delos, which provides better scalability and modularity than ZAB.
From Reordering to Leases: Zelos’ Session Layer
ZooKeeper’s contract with a client is backed by a session: a totally ordered, infallible stream of operations. The underlying Delos shared log is linearizable per appended entry, but a Delos reconfiguration or transient network issue can reorder those appends — a problem for any system that needs strict per-session ordering.
Sending one command at a time per session would be trivially correct but far too slow. Zelos’ answer is speculative execution. Commands are dispatched ahead to the log in parallel, assuming append order will hold. When the rare reorder does happen, Zelos detects it while reading from the log, aborts the affected events, and reissues them pessimistically. Correctness is preserved; the common case gets its parallel dispatch.
This logic lives in Delos’ SessionOrderingEngine, which exposes an infallible stream over the shared log. Every proposal is tagged with its node ID and a monotonically increasing proposal ID. Replicas apply proposals only if they are in sequence; an out-of-order proposal is rejected and its sender learns the session has broken. At that point, the engine stops issuing new work, waits for already-appended proposals to settle, and then replays anything it had to abort.
Reads complicate matters: ZooKeeper requires total ordering of reads and writes within a session. Zelos solves this by blocking a read until any write that precedes it has been applied locally, after which dependent reads may proceed with no further synchronization. The RequestProcessor layer intercepts every request and enforces this. Delos’ lightweight logical snapshots let Zelos take a snapshot before executing a write, so reads that follow can be answered out of order with minimal work on the critical path.
Sessions as Leases
ZooKeeper’s session semantics extend beyond ordering: a client heartbeats its session to keep it alive, and the ensemble leader tracks those heartbeats to detect failures and expire sessions. Ephemeral nodes created under those sessions get cleaned up automatically, and watches on them coordinate failover between replicas. When a leader fails, session state is replicated via consensus and a new leader picks up seamlessly.
Zelos can’t rely on that model because Delos has no concept of ensemble leader. Instead, Zelos splits session management into a two-level scheme. A client establishes a session with a single replica, which tracks it locally through the Local Session Manager (LSM); this layer does the same heartbeating and expiration work ZooKeeper’s leader does. But an LSM is fragile — if the replica goes down, the session manager goes with it. So Zelos adds a replicated Global Session Manager (GSM), a distributed state machine running on every replica. Session creation and expiration are replicated through it, and it also watches the health of each LSM.
A heartbeat from a local LSM via the shared log covers all sessions that LSM services — a far cheaper scheme than tracking heartbeats for each session individually, which is what ZooKeeper’s leader does. If an LSM fails, connecting clients notice via their own heartbeat channel and move to a different replica’s LSM; changes in session ownership are replicated through the GSM. Handles the edge case where a client and its LSM both fail at once by timing out the session — the GSM sees the LSM is dead and that no transfer occurred within the predefined session timeout.
A failure-detection scheme built on heartbeats is one that depends on wall-clock time, which is a hazard in any replicated state machine. Replicas applying a heartbeat log entry would each read a slightly different system clock, so one replica could conclude another is dead while its peers disagree. The GSM avoids this with a custom protocol called TimeKeeper. TimeKeeper accepts arbitrary clock skew between replicas but presumes relative clock drift is small over a window comparable to the maximum session timeout. Instead of comparing timestamps, each TimeKeeper replica sends tick messages at fixed intervals, attached to the log position of the latest LSM heartbeat it knows about. An LSM is considered dead only after every TimeKeeper has ticked past a tolerated count since the last received heartbeat — a reasonably sized margin for skewed clocks.
The GSM’s logic is generic enough that it ships as a reusable SMREngine inside Delos, usable by any application in need of distributed leasing. Thanks to the engine-stack framework, the production implementation of this session-management machinery is only a few hundred lines.
Migrating Without Downtime
Migrating Meta’s existing ZooKeeper workloads onto Zelos can’t cause downtime — many infrastructure consumers are too sensitive for that. Zelos leverages a well-known ZooKeeper behavior: a session can be transparently disconnected for reasons such as leader election. By spoofing a leader-election event, the wrapper client cleanly syncs away from a ZooKeeper ensemble and onto a Zelos replica, without ever violating observed ZooKeeper semantics.
That migration is valid only if all clients move at once and the Zelos side hosts the same visible state as the ZooKeeper ensemble it replaces. Zelos therefore boots in follower mode, participating in the ZooKeeper ensemble’s ZAB consensus protocol and writing state updates to its own on-disk storage. A specially created client wraps both protocol stacks and watches for a new node in the ZooKeeper tree — the barrier node. Its creation cues the infrastructure that the transfer is starting. The Zelos ensemble switches from ZAB follower to its own consensus protocol leader. Connecting clients watch for the barrier node, disconnect under the pretense of a leader election, connect to the new Zelos ensemble, and verify that ensemble has indeed seen the barrier; once observed, the new state is at least as current as the position that the ZooKeeper ensemble held at shutdown. Meta has used this flow to migrate half of its ZooKeeper workloads with zero observed downtime.
Evolution Beyond Session Ordering
One immutable layer fits most but not all workloads, and Delos’ composable architecture reflects that. A number of migrated use cases didn’t need strict session-ordering semantics at all. Dropping the session-ordered engine and stripping the request processor down rendered a materially higher throughput on those ensembles. That pragmatic divergence is only possible because the ZooKeeper API is implemented as a stack over Delos, not reimplemented from scratch per use case.
The future direction is sharding. Existing Meta teams often grow past a single ensemble and split workloads across multiple — then carry the burden of maintaining their own mapping. Delos is slated to offer general-purpose building blocks for sharding, which would map one logical Zelos namespace onto many physical ensembles, transparently inside the platform so all Delos-backed apps inherit it. It’s ambitious work, but it’s where the platform’s largest payoffs sit.
