How Celld's Distributed Ownership Protocol Works Without Consensus or Membership Services

Celld implements distributed ownership without a dedicated consensus or membership layer by using optimistic concurrency control with conditional writes to an external object store, combined with lease-based node authority and a deterministic event-sourced state machine.

Celld, maintained by the denoland organization, is a distributed system that manages cell ownership across nodes without relying on traditional consensus algorithms like Raft or Paxos. The protocol stores authoritative state in an S3-compatible object store and processes transitions through a deterministic core (celld-logic) that handles events such as OwnerRead, NodeLeaseRead, and OwnerCasCompleted to produce side-effects via adapters.

Ownership Records Live in Object Storage

The distributed ownership protocol stores authoritative cell ownership data in an external object store rather than in memory or a separate consensus log. Each cell maintains an owner record at the path cells/<cell>/own.json, containing the owning node ID and an ever-increasing epoch.

In crates/celld/ownership_store.rs, the read_owner function retrieves this record along with its etag for conditional operations:

// crates/celld/ownership_store.rs – read_owner
let key = format!("cells/{cell}/own.json");
let Some((owner, etag)) = self.read_json::<OwnerWireOwned>(&key).await? else {
    return Ok(None);
};
Ok(Some(OwnerRecord {
    node: (!owner.node.is_empty()).then_some(owner.node),
    epoch: owner.epoch,
    etag,
}))

Updates use conditional-write (CAS) operations that succeed only if the supplied etag matches the stored version. The cas_owner function in the same file implements this logic:

// crates/celld/ownership_store.rs – cas_owner
let key = format!("cells/{cell}/own.json");
let body = serde_json::to_vec(&OwnerWire { node: &self.node, epoch })?;
let etag = match &guard { CasGuard::Absent => None, CasGuard::Match(etag) => Some(etag) };
match self.bucket.put_cas(&key, body, etag).await? {
    Some(_) => Ok(CasOutcome::Applied),
    None => Ok(CasOutcome::Rejected),
}

This optimistic concurrency model eliminates the need for a consensus protocol to serialize ownership changes.

Node-Lease Authorization and Authority

Every node publishes a node-lease record at nodes/<node>.json that includes liveness information (expires_ms) and a per-process generation token. The core logic determines if a node is authoritative by checking node_authoritative() in crates/logic/lib.rs:

// crates/logic/lib.rs – node_authoritative()
match &self.node_authority {
    NodeAuthority::Held(_) => true,
    NodeAuthority::Reading { pending, .. } | NodeAuthority::Writing { pending, .. } => {
        pending.prior.is_some()
    }
    _ => false,
}

The system reads leases from a dedicated lease bucket separate from the ownership bucket to avoid race conditions during renewal. This separation ensures that a node can verify its own authority without contending with ownership operations:

// crates/celld/ownership_store.rs – read_self_node_lease
self.read_node_lease_with(&self.lease_bucket, owner).await

Membership Inference Without a Gossip Protocol

Celld does not maintain a separate membership list or use gossip-based discovery. Instead, the protocol infers fleet membership by enumerating live node-lease records stored under the nodes/ prefix.

In crates/celld/ownership_store.rs, the read_capacity_peers function lists all node objects and filters out stale entries using the lease TTL:

// crates/celld/ownership_store.rs – read_capacity_peers
for object in self.bucket.list("nodes/").await? {
    if !capacity_record_is_recent(object.last_modified.timestamp(), current_ms, self.lease_ttl_ms) {
        continue;
    }
    // …collect recent node IDs…
}

The resulting CapacityPeer list provides advisory load information for placement decisions, allowing the system to make scheduling choices without a centralized membership service.

Event-Driven Ownership Acquisition Flow

The core state machine processes ownership requests through deterministic stages defined in crates/logic/lib.rs. Each stage emits specific events that drive the protocol forward without blocking consensus calls:

1. Read owner (OwnerRead): Calls ownership.read_owner(cell) to determine current ownership
2. Read node lease (NodeLeaseRead): Verifies the owner node's liveness via read_node_lease
3. Read capacity peers (CapacityPeersRead): Enumerates valid nodes when no owner exists
4. Conditional acquire (OwnerCasCompleted): Executes cas_owner with the appropriate CasGuard

The handling of OwnerRead exemplifies this flow, queuing subsequent effects based on the read result:

// crates/logic/lib.rs – handling OwnerRead (excerpt)
Event::OwnerRead { op, now_ms, result } => {
    match result {
        Ok(Some(owner)) => Effect::ReadNodeLease { op, cell, owner: owner.node },
        Ok(None) => Effect::ReadCapacityPeers { op, cell },
        Err(_) => /* treat as failure */
    }
}

Timestamps are supplied by the runtime (e.g., now_ms in each Event) rather than read from the system clock directly, ensuring deterministic replayability and testability without consensus infrastructure.

Conflict Resolution via Optimistic CAS

The distributed ownership protocol resolves conflicts through optimistic CAS guarantees rather than consensus rounds. When two nodes race to acquire ownership of the same cell, only one will observe an etag matching its expected version; the other receives CasOutcome::Rejected and must retry the acquisition path.

Stale ownership is cleared through the release_owner function, which also uses conditional writes to prevent accidental overwrites:

// crates/celld/ownership_store.rs – release_owner
let Some(current) = self.read_owner(cell).await? else { return Ok(CasOutcome::Rejected) };
if current.node.as_deref() != Some(self.node.as_str()) || current.epoch != epoch {
    return Ok(CasOutcome::Rejected);
}
let body = serde_json::to_vec(&OwnerWire { node: "", epoch })?;
match self.bucket.put_cas(&key, body, Some(&current.etag)).await? {
    Some(_) => Ok(CasOutcome::Applied),
    None => Ok(CasOutcome::Rejected),
}

Lease expiration provides a natural tie-breaker. When a node's lease expires (detected via now_ms > expires_ms), the core treats the node as fenced and no longer authorizes ownership changes for it. Other nodes can then safely acquire the lease and subsequently claim cells formerly held by the expired node.

Summary

• Celld stores ownership records and node leases in an S3-compatible object store, using paths like cells/<cell>/own.json and nodes/<node>.json.
• Optimistic CAS operations serialize ownership changes without a consensus protocol, ensuring only one node succeeds per epoch.
• Lease-based authority determines node liveness, with expiration acting as a fencing mechanism for failed nodes.
• Fleet membership is inferred by scanning live lease records rather than maintaining a separate membership service.
• An event-sourced deterministic core processes all state transitions through events like OwnerRead and OwnerCasCompleted, making the protocol repeatable and debuggable.

Frequently Asked Questions

How does Celld prevent split-brain scenarios without consensus?

Celld prevents split-brain through optimistic concurrency control and lease expiration. The object store's conditional write operations ensure that only one node can successfully write an owner record for a given epoch. If a node fails, its lease expires after lease_ttl_ms, fencing it from making further ownership changes and allowing other nodes to safely acquire its former cells.

What happens when two nodes try to acquire the same cell simultaneously?

When nodes race to acquire ownership, the CAS (Compare-And-Swap) mechanism in crates/celld/ownership_store.rs rejects all but one write operation. The losing node receives CasOutcome::Rejected and must re-read the current owner, potentially discovering the winner's lease. The protocol retries up to MAX_ACQUIRE_RECONCILES before failing the request.

Why does Celld use a separate lease bucket for node leases?

The lease bucket separation prevents race conditions between ownership operations and lease renewals. By storing node leases in a distinct S3 bucket from cell ownership records, a node can renew its own lease (via read_self_node_lease) without interfering with concurrent ownership transfers, ensuring that authority checks remain consistent during high-contention scenarios.

Can Celld's ownership protocol work with non-S3 object stores?

Yes, the protocol works with any S3-compatible object store that supports conditional writes (PUT with If-Match semantics). The ownership_store.rs adapter abstracts the specific storage backend, requiring only basic object operations: list, get with etag, and conditional put. This allows Celld to run on MinIO, Cloudflare R2, AWS S3, or other compatible services without modification to the core logic.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}