denoland/celld

Public

An acknowledged alarm arm can lose its wake entry: a move-delete is invisible to the in-flight-delete gate

MI

## Summary

An acknowledged alarm arm can end up with no wake entry in the bucket. When an alarm moves off a minute and then back onto it, the move's `DELETE(old key)` is invisible to the in-flight-delete gate both PUT paths sequence behind, so the arm-time `PUT(old key)` races that delete. The delete can land second, erasing the entry of an alarm the node has already acknowledged to the application.

The wake entry is the only way the fleet rediscovers an alarm for a non-resident cell, so the alarm is then lost until a request happens to activate the cell again.

## Environment

- celld v0.2.0, commit `3f22aedd1ea4d413b93e84afb1ce385f04be84f1` - Not observed on a live fleet, so I cannot say how wide the window is in practice. It came out of a small model of the wake-entry transitions (https://gist.github.com/mizchi/2246bd394257b7a5cbbd3fef1556415d), and was then reproduced against the real `WakeFlusher`, `Bucket` and `due_scan` with a store that holds the DELETE open.

## The race

1. The alarm is armed at `EARLY`; `wake/<EARLY>/<cell>` is PUT and proven. 2. The alarm is postponed to `LATE`. `decide` returns `[Put(LATE), Delete(EARLY)]`; `PUT(LATE)` lands and `confirm_put` retracks the cell onto the `LATE` key, then `DELETE(EARLY)` goes on the wire. 3. The alarm tightens back to `EARLY` while that delete is still in flight. `spawn_arm_gate` (crates/celld/js.rs) takes `arm_op` -> `Put(EARLY)`, asks `await_no_inflight_delete`, is told nothing is in flight, PUTs `EARLY`, and `drain_arm_gates` releases the response: the arm is acknowledged. 4. `DELETE(EARLY)` lands last and removes the entry that acknowledgement promised.

## Why the gate misses it

`Entry.deleting` (crates/logic/wake.rs) can only describe a consume-delete of the key the core still tracks. A move-delete is handed to the executor *after* the replacement PUT confirmed, so `flushed` already holds the new key and `WakeCore::take_delete` takes its `e.key != key` branch: it returns `true` without recording anything. `delete_in_flight` therefore answers `false` while the old key's DELETE is on the wire, and both `WakeFlusher::reconcile` and `spawn_arm_gate` sequence behind exactly that answer.

## Impact

It does not take a crash to lose the alarm.

- `RuntimeManager::alarm_covered` is read right after `drain_arm_gates` (crates/celld/runtime.rs, and `ActivityGuard::drop` on the request path) and stored as `AlarmState::Armed { covered }`. In this race it is `true` at that instant. - `hibernate_candidate` and `shed_candidate` (crates/logic/lib.rs) trust that stored flag rather than re-checking, so the cell can be evicted after the entry is already gone. - `Effect::ReconcileWakeEntry` is only emitted when the alarm value changes (`if settled != observed_before`), so nothing re-asserts the entry on a later tick.

Result: an evicted cell with an armed alarm and no wake entry. `due_scan` cannot see it, and it does not fire until something else activates the cell. A crash in the same window loses it the same way.

## Reproduction

Sans-IO, no store needed — drop in `crates/logic/tests/`:

```rust use celld_logic::wake::{entry_key, Step, WakeCore};

#[test] fn move_delete_must_be_visible_to_same_cell_puts() { let cell = "alarm-cell"; let early = 60_000; let late = 120_000; let mut core = WakeCore::new(); core.confirm_put(cell, early, entry_key(early, cell));

let mut plan = core.reconcile_plan(cell, late, true); let Step::Put { key, due_ms, .. } = plan.next(&mut core).expect("replacement put") else { panic!("replacement put must precede move delete") }; plan.put_done(&mut core, key, due_ms); let Step::Delete { .. } = plan.next(&mut core).expect("old-key delete") else { panic!("expected old-key delete") };

assert!( core.delete_in_flight(cell), "a handed-out move delete must block a same-cell/same-key arm put" ); } ```

On v0.2.0 this fails: the handed-out move-delete leaves `delete_in_flight` false.

The end-to-end version drives the real `WakeFlusher` / `Bucket` / `due_scan` against an in-process S3-compatible store whose DELETE is held until the test releases it. It needs no new dependencies (axum and tokio are already celld dependencies); drop it in `crates/celld/tests/`. On v0.2.0 the raced case reports:

```text arm gate waited 416ns for the in-flight delete alarm_covered at ack: true bucket holds: ["wake/1970-01-01T00:02/alarm-cell"] flusher tracks the cell: false due_scan at EARLY: [] ```

while the control case — the same schedule with the delete allowed to settle first — passes.

<details> <summary>Full end-to-end probe</summary>

```rust // Expected-red end-to-end probe for the v0.2.0 move-delete wake-entry race. // // Unlike `wake_move_delete_probe.rs`, which only inspects `WakeCore` // bookkeeping, this drives the REAL executor (`celld::wake::WakeFlusher`), the // REAL object-store client (`celld::bucket::Bucket`) and the REAL discovery // path (`celld::wake::due_scan`) against an in-process S3-compatible store // whose DELETE can be held open. It reproduces the safety violation itself: // // acknowledged alarm arm => no durable wake entry // // Schedule (`raced` test): // 1. arm EARLY, entry PUT and proven; // 2. postpone to LATE: PUT(LATE) lands, DELETE(EARLY) goes on the wire and // is held by the store; // 3. the alarm moves back to EARLY. The arm gate (js.rs::spawn_arm_gate) // asks the flusher whether a delete is in flight -- it says no, because // a move-delete is never recorded -- so PUT(EARLY) races the held DELETE // and the arm is acknowledged; // 4. the DELETE is released and lands last, erasing the acknowledged arm's // only entry. // // The store releases the DELETE 200 ms after step 3 begins, so a fixed // implementation (one that makes the move-delete visible to // `await_no_inflight_delete`) sequences the arm PUT after it and turns this // test green. // // The `settled` test runs the same schedule with the delete allowed to finish // before the arm. It must stay green: a harness that cannot pass is a harness // that proves nothing.

use axum::body::Body; use axum::body::Bytes; use axum::extract::State; use axum::http::Method; use axum::http::StatusCode; use axum::http::Uri; use axum::response::Response; use axum::Router; use celld::bucket::Bucket; use celld::bucket::StaticCredentials; use celld::wake::due_scan; use celld::wake::WakeFlusher; use celld_logic::wake::entry_key; use celld_logic::wake::Op; use std::collections::HashMap; use std::sync::Arc; use std::sync::Mutex; use std::time::Duration; use tokio::sync::mpsc; use tokio::sync::Semaphore;

const BUCKET: &str = "celld-test"; const CELL: &str = "alarm-cell"; const EARLY: i64 = 60_000; const LATE: i64 = 120_000;

/// The S3 surface this probe needs: PUT / GET / HEAD / DELETE and /// ListObjectsV2 on path-style keys, plus a gate that holds each DELETE until /// the test hands out a permit. struct FakeS3 { objects: Mutex<HashMap<String, Vec<u8>>>, delete_gate: Semaphore, delete_arrived: mpsc::UnboundedSender<String>, }

fn decode_key(path: &str) -> String { let raw = path .trim_start_matches('/') .strip_prefix(BUCKET) .unwrap_or(path) .trim_start_matches('/'); percent_encoding::percent_decode_str(raw) .decode_utf8_lossy() .into_owned() }

fn with_headers(status: StatusCode, body: Body, len: usize) -> Response { Response::builder() .status(status) .header("ETag", "\"celld-fake\"") .header("Last-Modified", "Tue, 01 Jan 2030 00:00:00 GMT") .header("Content-Length", len.to_string()) .body(body) .unwrap() }

/// ListObjectsV2, enough of it for `Bucket::list`. fn list_response(state: &FakeS3, query: &str) -> Response { let prefix = query .split('&') .find_map(|p| p.strip_prefix("prefix=")) .map(|p| { percent_encoding::percent_decode_str(p) .decode_utf8_lossy() .into_owned() }) .unwrap_or_default(); let objects = state.objects.lock().unwrap(); let mut keys: Vec<&String> = objects.keys().filter(|k| k.starts_with(&prefix)).collect(); keys.sort(); let contents: String = keys .iter() .map(|k| { format!( "<Contents><Key>{k}</Key>\ <LastModified>2030-01-01T00:00:00.000Z</LastModified>\ <ETag>&quot;celld-fake&quot;</ETag>\ <Size>{}</Size><StorageClass>STANDARD</StorageClass></Contents>", objects[*k].len() ) }) .collect(); let xml = format!( "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\ <ListBucketResult xmlns=\"http://s3.amazonaws.com/doc/2006-03-01/\">\ <Name>{BUCKET}</Name><Prefix>{prefix}</Prefix><KeyCount>{}</KeyCount>\ <MaxKeys>1000</MaxKeys><IsTruncated>false</IsTruncated>{contents}\ </ListBucketResult>", keys.len() ); let len = xml.len(); Response::builder() .status(StatusCode::OK) .header("Content-Type", "application/xml") .header("Content-Length", len.to_string()) .body(Body::from(xml)) .unwrap() }

async fn handle( State(state): State<Arc<FakeS3>>, method: Method, uri: Uri, body: Bytes, ) -> Response { let query = uri.query().unwrap_or_default().to_string(); if method == Method::GET && query.contains("list-type=2") { return list_response(&state, &query); } let key = decode_key(uri.path()); match method { Method::PUT => { state.objects.lock().unwrap().insert(key, body.to_vec()); with_headers(StatusCode::OK, Body::empty(), 0) } Method::DELETE => { let _ = state.delete_arrived.send(key.clone()); // Held until the test releases it: this is the window in which a // same-key PUT must not be issued. state.delete_gate.acquire().await.unwrap().forget(); state.objects.lock().unwrap().remove(&key); with_headers(StatusCode::NO_CONTENT, Body::empty(), 0) } Method::GET | Method::HEAD => match state.objects.lock().unwrap().get(&key) { Some(bytes) => { let len = bytes.len(); let body = if method == Method::HEAD { Body::empty() } else { Body::from(bytes.clone()) }; with_headers(StatusCode::OK, body, len) } None => Response::builder() .status(StatusCode::NOT_FOUND) .body(Body::empty()) .unwrap(), }, _ => Response::builder() .status(StatusCode::METHOD_NOT_ALLOWED) .body(Body::empty()) .unwrap(), } }

async fn spawn_fake_s3() -> (Arc<FakeS3>, mpsc::UnboundedReceiver<String>, String) { let (tx, rx) = mpsc::unbounded_channel(); let state = Arc::new(FakeS3 { objects: Mutex::new(HashMap::new()), delete_gate: Semaphore::new(0), delete_arrived: tx, }); let app = Router::new().fallback(handle).with_state(state.clone()); let listener = tokio::net::TcpListener::bind("127.0.0.1:0").await.unwrap(); let addr = listener.local_addr().unwrap(); tokio::spawn(async move { let _ = axum::serve(listener, app).await; }); (state, rx, format!("http://{addr}")) }

fn open_bucket(endpoint: &str) -> Bucket { Bucket::open( &format!("s3://{BUCKET}"), Some(endpoint), "us-east-1", Some(StaticCredentials { access_key_id: "celld".into(), secret_access_key: "celld".into(), session_token: None, }), None, ) .expect("open fake bucket") }

/// EARLY armed, postponed to LATE, then moved back to EARLY. `race` decides /// whether the arm happens while the move-delete is still on the wire. async fn move_delete_then_rearm(race: bool) { let (store, mut deletes, endpoint) = spawn_fake_s3().await; let bucket = open_bucket(&endpoint); let flusher = Arc::new(WakeFlusher::new()); let early_key = entry_key(EARLY, CELL); let late_key = entry_key(LATE, CELL);

// 1. The alarm is armed at EARLY and its entry is proven durable. flusher.reconcile(&bucket, CELL, EARLY, false).await; assert!( store.objects.lock().unwrap().contains_key(&early_key), "initial arm must write its entry" ); assert!(flusher.covered(CELL, EARLY), "initial arm must be covered");

// 2. Postponed to LATE: PUT(LATE) then DELETE(EARLY), which the store holds. let mut mover = Some({ let flusher = flusher.clone(); let bucket = bucket.clone(); tokio::spawn(async move { flusher.reconcile(&bucket, CELL, LATE, false).await }) }); let on_the_wire = deletes .recv() .await .expect("move-delete must reach the store"); assert_eq!(on_the_wire, early_key, "the move deletes the old key"); assert!( store.objects.lock().unwrap().contains_key(&late_key), "put-before-delete: the replacement entry lands first" );

if race { // The store lets the held DELETE through shortly after the arm begins, // so an implementation that sequences the arm PUT behind it still // finishes rather than deadlocking. let store = store.clone(); tokio::spawn(async move { tokio::time::sleep(Duration::from_millis(200)).await; store.delete_gate.add_permits(1); }); } else { // Control: no race at all. The delete settles first. store.delete_gate.add_permits(1); mover.take().unwrap().await.expect("reconcile task"); }

// 3. The alarm moves back to EARLY. This is js.rs::spawn_arm_gate, inlined: // arm_op -> await_no_inflight_delete -> put -> confirm_arm, after which // drain_arm_gates releases the response that acknowledges the arm. let Some(Op::Put { key, due_ms }) = flusher.arm_op(CELL, EARLY) else { panic!("re-arming to an earlier minute must pay a synchronous PUT") }; assert_eq!(key, early_key); let gate_entered = std::time::Instant::now(); flusher.await_no_inflight_delete(CELL).await; let waited = gate_entered.elapsed(); let body = format!("{{\"cell\":{CELL:?},\"due_ms\":{due_ms}}}"); bucket.put(&key, body.into_bytes()).await.expect("arm-time put"); flusher.confirm_arm(CELL, due_ms, key.clone()); // Under v0.2 and `race` this is ~0 ms: the move-delete is invisible to the // gate, so the arm PUT races the held DELETE instead of following it. eprintln!("arm gate waited {waited:?} for the in-flight delete"); // What `RuntimeManager::alarm_covered` answers at ack time — it runs right // after `drain_arm_gates`, and the core stores it as // `AlarmState::Armed { covered }`, the flag `hibernate_candidate` / // `shed_candidate` later trust when they evict the cell. let covered_at_ack = flusher.covered(CELL, EARLY); eprintln!("alarm_covered at ack: {covered_at_ack}");

// 4. The held DELETE settles. if let Some(mover) = mover.take() { mover.await.expect("reconcile task"); }

let held: Vec<String> = { let objects = store.objects.lock().unwrap(); let mut keys: Vec<String> = objects.keys().cloned().collect(); keys.sort(); keys }; eprintln!("bucket holds: {held:?}"); eprintln!("flusher tracks the cell: {}", flusher.tracks(CELL)); assert!( covered_at_ack, "the arm gate acknowledged an arm it did not consider covered" );

// The discovery path a surviving node would use after this node dies. let due = due_scan(&bucket, EARLY).await; eprintln!("due_scan at EARLY: {due:?}");

assert!( held.contains(&early_key), "an acknowledged alarm arm must leave a durable wake entry, but the \ move-delete erased it" ); assert!( due.iter().any(|(cell, _)| cell == CELL), "an acknowledged alarm must be rediscoverable by bucket scan; this one \ is lost if the process stops here" ); }

/// Expected red on v0.2.0. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn acknowledged_arm_keeps_its_entry_when_it_races_a_move_delete() { move_delete_then_rearm(true).await; }

/// Control: the same schedule without the race must pass, or the probe above /// proves nothing. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn acknowledged_arm_keeps_its_entry_after_a_settled_move_delete() { move_delete_then_rearm(false).await; } ```

</details>

## Expected

An arm that has been acknowledged to the application is covered by a durable wake entry, per crates/celld/wake.rs: a stale entry costs one spurious wake, a missing one costs the alarm.

  1. BA

    Fixed in v0.2.1: celld now tracks a delete while it is in flight, so a move-delete is visible to the arm gate and an acknowledged alarm keeps its wake entry.

    https://github.com/denoland/celld/releases/tag/v0.2.1

  2. bartlomiejuclosed3 months ago on GitHub