Celld's Bucket-Based Ownership Protocol with Compare-and-Swap (CAS) Operations

Celld uses conditional writes (compare-and-swap) against an S3-compatible object store to guarantee that exactly one node owns a Durable Object (cell) at any moment, eliminating the need for external consensus services.

Celld implements a completely decentralized ownership protocol that relies on an S3-compatible object store as the single source of truth for cell ownership. Rather than using a bespoke consensus algorithm, the system leverages compare-and-swap (CAS) operations to coordinate exclusive access to cells across distributed nodes. This bucket-based approach ensures strong consistency while maintaining fault tolerance and scalability.

How the Bucket-Based CAS Protocol Works

The protocol operates in three distinct stages, all mediated through the object store's conditional write semantics.

Reading the Current Owner

Before attempting to claim a cell, a node must fetch the current ownership record from cells/<cell>/own.json. This operation returns both the owner record and the object's ETag, which serves as a version identifier for subsequent CAS operations.

In crates/celld/ownership_store.rs, the read_owner method handles this lookup:

// ownership_store.rs L66-L73
let Some((owner, etag)) = self.read_json::<OwnerWireOwned>(&key).await? else {
    return Ok(None);
};

The returned OwnerRecord contains the owner's node ID and an epoch counter that monotonically increases each time the cell is successfully claimed.

Claiming Ownership with Conditional Writes

To claim a cell, the node constructs a new OwnerWire containing its node ID and the desired epoch, then issues a PUT with an If‑Match condition that matches the previously-read ETag. This ensures the write only succeeds if no other node has modified the record since the read.

// ownership_store.rs L99-L112
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),
}

If the ETag matches, S3 accepts the write and returns the new ETag, resulting in CasOutcome::Applied. If another node has claimed the cell in the interim, the ETag changes, causing the conditional write to fail with CasOutcome::Rejected.

Releasing Ownership Safely

When a node wishes to release a cell, it writes an empty node field while preserving the epoch, again guarded by the latest ETag. If the ETag no longer matches—indicating another node has taken ownership—the release is rejected to prevent accidentally overwriting a valid claim.

// ownership_store.rs L78-L90
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),
}

Leasing Node Identity

Nodes also publish a node-lease record at nodes/<node>.json containing load metrics and a lease expiration timestamp. This lease is updated using the same CAS semantics to prevent split-brain scenarios where multiple instances believe they represent the same node identity.

// ownership_store.rs L141-L168
let body = serde_json::to_vec(&NodeLeaseWire { … })?;
let etag = match &guard { CasGuard::Absent => None, CasGuard::Match(etag) => Some(etag) };
match self.lease_bucket.put_cas(&key, body, etag).await? {
    Some(etag) => Ok(LeaseCasOutcome::Applied { etag }),
    None => Ok(LeaseCasOutcome::Rejected),
}

Why Object-Store CAS Enables Distributed Consensus

The bucket-based approach provides several critical properties that replace traditional consensus machinery:

• Single source of truth: All ownership data lives in the object store, eliminating the need for a separate control plane or consensus service.
• Atomicity: S3's PUT with If-Match is atomic; either the whole object is replaced or the request fails, preventing split-brain scenarios.
• Fault tolerance: If a node crashes while holding a lease, the lease record eventually expires based on expires_ms. Other nodes detect stale records via capacity_record_is_recent and may then attempt to acquire the cell.
• Scalable discovery: Nodes enumerate peer leases using read_capacity_peers and filter out stale records, keeping the protocol lightweight even for large fleets.

Practical Code Examples

Reading the Current Owner of a Cell

// Example – fetch owner of "counter"
let owner = ownership_store.read_owner("counter").await?;
if let Some(rec) = owner {
    println!("Owner: {:?}, epoch: {}", rec.node, rec.epoch);
} else {
    println!("Cell is currently unowned");
}

Attempting to Claim a Cell

// Example – claim "counter" with epoch 42
use celld_logic::CasGuard;
let guard = CasGuard::Absent; // no prior record
let outcome = ownership_store.cas_owner("counter", guard, 42).await?;
match outcome {
    CasOutcome::Applied => println!("Successfully claimed!"),
    CasOutcome::Rejected => println!("Failed – another node won the race"),
}

Releasing Ownership

// Example – release "counter" that we own at epoch 42
let outcome = ownership_store.release_owner("counter", 42).await?;
if let CasOutcome::Applied = outcome {
    println!("Cell released");
}

Publishing a Node Lease

// Example – renew our node lease
let record = NodeLeaseRecord {
    node: my_node.clone(),
    addr: "10.0.0.2:8080".into(),
    expires_ms: ownership_store::now_ms() + lease_ttl,
    peer_protocol: 1,
    generation: ownership_store.process_generation().unwrap_or("").into(),
};
let guard = CasGuard::Match(previous_etag); // from last read
let lease_outcome = ownership_store.cas_node_lease(guard, &record).await?;

Key Source Files

File	Role
crates/celld/ownership_store.rs	Implements the bucket-based CAS adapter, including read_owner, cas_owner, release_owner, and cas_node_lease.
crates/celld/bucket.rs	Wraps the S3 client and provides the put_cas method that performs conditional writes.
crates/celld/protocol.rs	Defines the wire protocol (OwnerRecord, NodeLeaseRecord, CasGuard, CasOutcome, LeaseCasOutcome) used by the ownership store.
crates/celld/logic/*.rs	Core logic that decides which node should own a cell, based on the lease records read from the bucket.

Summary

• Celld uses S3 conditional writes (If-Match) to implement a distributed lock mechanism without consensus algorithms.
• The protocol stores ownership records in cells/<cell>/own.json and node leases in nodes/<node>.json.
• Compare-and-swap operations ensure that exactly one node can claim or release a cell at any given time.
• The CasGuard and CasOutcome types in ownership_store.rs provide a Rust-native interface to object-store CAS semantics.
• Expiring node leases and epoch counters prevent dead cells and enable automatic failover when nodes crash.

Frequently Asked Questions

What happens if two nodes attempt to claim the same cell simultaneously?

Only one node will succeed. Both nodes read the current ETag and issue conditional PUT requests with If-Match. S3's strong consistency guarantees that exactly one request will match the current ETag and succeed, returning CasOutcome::Applied. The other request will fail with CasOutcome::Rejected because the ETag changed when the first write succeeded.

How does Celld handle node failures during ownership?

If a node crashes while holding a cell, its node lease (nodes/<node>.json) eventually expires because it is no longer being renewed. The expires_ms field in the lease record indicates validity. Other nodes detect stale leases via capacity_record_is_recent and may then attempt to claim orphaned cells using the standard CAS protocol.

Why does Celld use S3 conditional writes instead of a consensus algorithm like Raft?

The bucket-based ownership protocol leverages existing object-store consistency guarantees rather than implementing Paxos or Raft. This eliminates the operational complexity of managing a consensus cluster, reduces network overhead (only three parties: reader, writer, and S3), and scales naturally with the object store's capacity. The trade-off is higher latency for ownership operations compared to in-memory consensus, but this is acceptable for Durable Object workloads where persistence is already required.

What is the role of the epoch counter in the ownership protocol?

The epoch is a monotonically increasing counter stored in the OwnerRecord that increments each time a cell changes ownership. It helps track ownership transitions and ensures that nodes can detect stale ownership records when coordinating handoffs between claims.

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