# Recursive Directory Delete: Batched, Race-Aware Redesign Status: proposal (rev 6 — final; both reviewers approved, pre-implementation pin-downs folded in) Scope: `pkg/datastore` (`DeleteDirRecursive`, `DeleteEmptyDir`), `pkg/backend` (`RemoveAllCtx`), `pkg/server` (`handleDelete`), `pkg/client` (retry behavior) ## 1. Background `Store.DeleteDirRecursive` (`pkg/datastore/store.go:2009`) deletes an entire directory subtree in a single synchronous transaction. For a subtree with N files the transaction: 1. Collects all file IDs with an unbounded `SELECT DISTINCT file_id FROM file_nodes WHERE path = ? OR path LIKE ?` (store.go:2019). 2. Pessimistically locks every inode (`SELECT ... FOR UPDATE`, batched by 1000) and holds the locks until commit (store.go:2035, `lockFileIDsForDeleteTx`). 3. Deletes all `file_nodes` rows with one unbounded `DELETE ... WHERE path = ? OR path LIKE ?` (store.go:2039). 4. Scans for orphaned inodes, marks them `DELETED`, deletes their tags (batched by 1000, store.go:2044-2055). 5. Enqueues one `file_gc_tasks` row **per file** in a loop — N individual INSERT statements, N network round trips, all inside the same transaction (store.go:2059-2067). In production this manifests as statement/lock-wait timeouts (1205), TiDB "transaction too large" failures, and generic latency/5xx alerts on the delete path. ## 2. Problem analysis ### 2.1 Full-table scans on every delete `file_nodes` has indexes on `path_hash`, `(parent_path_hash, name)`, `file_id`, and `inode_id` — but **no index on `path`** (see `pkg/tenant/db9/schema.go:21-36` and the equivalent TiDB schemas). The predicate `path = ? OR path LIKE '/%'` cannot use any index, so steps 1 and 3 above each scan the tenant's entire `file_nodes` table — even when deleting a tiny directory. ### 2.2 Unescaped LIKE pattern (correctness) The pattern is built as `dirPath + "%"` without escaping (store.go:2020, 2039). `%` and `_` are valid characters in drive9 file names, so deleting `/a_b/` also matches `/axb/...` rows of sibling directories. The codebase already has a correct helper — `pathPrefixPredicate` (store.go:2393) with `ESCAPE '\\'` — but the recursive delete path does not use it. (Related, out of scope: `RenameDir` uses the same unescaped `path LIKE` pattern, store.go:632-634 — same bug class, worth a follow-up fix.) ### 2.3 TOCTOU blob leak (correctness) The transaction collects file IDs with a **snapshot read** (step 1), but the `DELETE` in a pessimistic transaction is a **current read**. A file created (committed) under the target directory after step 1 but before step 3 has its `file_nodes` row deleted, yet its file ID is not in the collected set: its inode is never marked `DELETED` and no GC task is enqueued. The blob leaks permanently. Note the shape of a correct fix: it is not enough to switch to "delete only the rows we selected". If a new row survives deletion while its parent dentries are deleted, the row becomes an **invisible orphan** — unreachable by `ls` (no parent chain), never GC'd. That is strictly worse than today. The fix must guarantee: anything created under the tree before the delete commits is either deleted (and GC-enqueued) or left in a fully intact parent chain. See the confirm loops in §4.1/§4.2. ### 2.4 Transaction size and lock footprint - ~3-4N row mutations across 4-5 tables in one transaction, holding pessimistic locks on the whole subtree for the full duration. Concurrent writers anywhere in the subtree queue behind it and eventually fail with lock-wait timeout. - N sequential INSERT round trips for GC tasks dominate wall-clock time (~1 ms × N; 100k files ≈ 100 s). - Large transactions hit TiDB's `txn-total-size-limit` / entry-count limits and lose async-commit, so commit itself becomes slow and failure-prone. - The HTTP handler waits for the whole tree (`pkg/backend/dat9.go:552` → `RemoveAllCtx`); the server sets no `ReadTimeout`/`WriteTimeout` (`pkg/server/server.go:1603`), so the effective deadline is the gateway/client. When the client disconnects, `r.Context()` is cancelled, the whole transaction rolls back with **zero progress**, and a retry starts from scratch — amplifying load. ### 2.5 Constraints from the schema and create path (verified, shapes the whole design) Any batched design must respect how the tree and creation actually work today: - **The root is implicit.** There is no `file_nodes` row for `/` (`ErrInvalidRootDentry`, store.go:31; `EnsureParentDirsTx` stops at `parent == "/"`, store.go:1362). Every top-level row has `parent_path = "/"`. Any "does the parent exist?" logic anywhere in this design must treat `/` as always-existing without a lookup. - `InsertNodeTx` (store.go:1425) performs **no parent-existence check** — it is a bare INSERT (plus an inode lock for files). - Every create path goes through `EnsureParentDirsTx` (store.go:1338/1357), which **recreates missing ancestor dentries** with deterministic node IDs via `INSERT ... ON DUPLICATE KEY UPDATE` / `INSERT IGNORE`. Example: `CreateAndWrite` (pkg/backend/dat9.go:847) runs `EnsureParentDirsTx → InsertNodeTx` in one transaction; mkdir/symlink/copy/rename follow the same pattern. - `file_nodes` stores `parent_path` as a **string**, not a parent node_id. A recreated directory at the same path is indistinguishable from the original by path alone (no generation identity). - TiDB has **no gap locks**: `SELECT 1 ... LIMIT 1 FOR UPDATE` ("has children?") locks only existing rows, and `INSERT INTO file_nodes` does not lock the parent dentry. So "check empty → delete dir dentry" is inherently racy; the mitigation is a post-DELETE re-check inside the same transaction (§4.2), which shrinks the window to the commit boundary but cannot eliminate it without a delete-in-progress marker (§4.4). - In-flight multipart uploads (`uploads.target_path`) finalize through the same ensure-parents + insert path, so an upload started before a delete can materialize nodes inside the tree mid-sweep. Consequences (implementation checklist): - **Never delete a directory dentry before its subtree is fully gone.** If an intermediate dir dentry is removed while descendants remain, the `parent_path` chain is broken: a resume pass walking by `parent_path_hash` from the root can never rediscover the stranded rows, and their blobs leak. - **Never delete the root dentry first.** Three failure modes: (a) a retried `RemoveAllCtx` fails at `resolveNodePath` (dat9.go:2043) with `ErrNotFound` and the caller believes the delete succeeded while the sweep is unfinished; (b) a concurrent `EnsureParentDirsTx` recreates the root, new data lands under it, and a resume pass deletes the **new** tree (path reuse without generation identity); (c) the "stragglers stop because creates fail under a deleted dir" assumption is false — creates do not fail, they recreate. - Keeping the root dentry row in place until the sweep finishes doubles as the tombstone: `idx_path` (`path_hash` UNIQUE) guarantees the path cannot be recreated while the row exists, which also solves the generation problem for the in-flight operation. - **Leaf-first alone is not sufficient**: a subdir that is non-empty when first visited must be revisited and unlinked **after** it drains (post-order lift). A queue that only pushes "directories to scan" and never re-evaluates a drained directory for unlinking leaves an empty-dentry skeleton behind and the root can never be deleted. - **A drain batch that deletes nothing must not loop.** If a full `LIMIT batchSize` batch consists entirely of not-yet-empty subdirectories, "batch was full → continue" spins forever on the same rows. Progress is measured in deleted rows, not batch fullness. ### 2.6 Existing precedent `PurgeTenantData` (`pkg/datastore/purge.go:57`) demonstrates the batching mechanics: `DELETE ... LIMIT 10000` in a loop, no wrapping transaction, each batch committing independently. Note the analogy is mechanical only — purge has no directory-tree semantics and no concurrent creates, so its resumability argument does not transfer; §4.2 derives resumability from traversal order instead. ## 3. Goals - No unbounded single transaction on the recursive delete path; bounded batch size and bounded lock-hold time per transaction. - Close the TOCTOU blob-leak race and the LIKE-escaping over-match. - No full-table scans: subtree traversal must use the `(parent_path_hash, name)` index. - Idempotent and resumable **without schema changes**: a crashed/interrupted delete is completed by re-calling the same entry point, and never mistakes a recreated path for the tree being deleted. - Preserve current synchronous, atomic semantics for small directories. - Safe under concurrent create/write/rename/hardlink against the tree being deleted (POSIX `rm -r`-equivalent races are acceptable; deleting a *recreated* tree or leaving invisible orphans is not). - No "partial success" third state: the API returns success only when the root is gone. - Every loop is bounded by budget (transaction count, wall-clock, context) and fails with a retryable error, never spins. Non-goals: - Blob GC worker behavior; `DeleteFileWithRefCheck` (single file). - Async user-facing job API / 202 responses (optional follow-up, §4.4). - **Directory-inode cleanup** (unchanged from today): dentries for directories carry `inode_id`s (created by `EnsureParentDirsTx`), and nothing marks them `DELETED` — they leak on every directory delete, including the current implementation. The reconciliation sweep (§4.2.1) deliberately does **not** touch them either; see the scoping rules there. Tracked as a separate follow-up (§4.4). - Rejecting new creates inside a tree whose delete is in flight (requires a deleting marker on the root + checks on every create path; §4.4). Without it, the residual commit-boundary window of 2.5 can only be shrunk, not closed — if production data shows the window matters, this follow-up becomes the root fix and should be prioritized. ## 4. Design ### 4.1 Phase 1 — correctness fixes inside the existing single transaction Stopgap that lands correctness fixes and the biggest latency win without changing the single-transaction structure. Scope is deliberately narrow: it fixes **2.2 (LIKE escape), 2.3 (TOCTOU), and the N-round-trip GC enqueue**; it does **not** fix 2.1 (full-table scans) or 2.4 (big transaction / long locks). **Performance honesty**: each confirm-loop round below is a full-tenant scan plus a filesort (`ORDER BY path DESC` on an unindexed column), and there are N/batchSize rounds — total cost O((N/batchSize) × tableSize). For small/medium trees this is fine; for very large trees it can be slower than today's implementation. Phase 1 is therefore justified as the correctness baseline for the fast path; it must ship together with Phase 2, not long before it. 1. **Escape the LIKE pattern** via `pathPrefixPredicate`. Write the self-match as `(path_hash = ? AND path = ?)` so the exact match can use `idx_path`; the LIKE arm remains a full scan (stopgap only). 2. **Bounded confirm-loop delete.** A bare "SELECT FOR UPDATE → DELETE by node_id" pass would leave rows created after the SELECT in place while their parent dentries are deleted — an invisible-orphan leak worse than 2.3 itself. So Phase 1 loops inside the transaction: ```sql -- repeat until a round selects 0 rows, at most maxRounds times: SELECT node_id, file_id, is_directory FROM file_nodes WHERE AND node_id <> ORDER BY path DESC -- deepest paths first: children before parents LIMIT deleteFileIDBatchSize FOR UPDATE; -- current read + lock DELETE FROM file_nodes WHERE node_id IN (...); -- by primary key -- feed this round's file_ids into the orphan/mark/tag/GC pipeline ``` `ORDER BY path DESC` drains children before their parent dentries (directory paths always end in `/`, so a child's path sorts after its parent's); rows committed mid-loop are caught by the next round (same transaction, current read). The loop is bounded by `maxRounds` and ctx — under sustained concurrent writes it exits by rolling back and returning `ErrDeleteIncomplete` (retryable), not by spinning. (The unbounded lock footprint is unchanged from today — accepted, this is the stopgap.) 3. **Root last, same-transaction restart.** After the loop drains, delete the root dentry and re-run the children probe (`dirHasChildrenTx`) in the same transaction. On race, **do not roll back the whole transaction, and do not re-insert the root row** — the root stays deleted inside this transaction; resume the confirm loop (step 2), whose `node_id <> ` filter already excludes it. Retry the root delete only after a fresh childless probe, up to K attempts; **K counts into the same `maxRounds` budget** so the single transaction cannot retry forever. On exhaustion, roll back and return `ErrDeleteIncomplete`. 4. **Batch the GC enqueue.** Replace the per-file `EnqueueFileGCTaskTx` loop with a multi-row INSERT chunked at `deleteFileIDBatchSize`, using the same duplicate-tolerance semantics as the existing `enqueueFileGCTask` SQL (file_gc_tasks.go:54-58: duplicates are no-ops) — align the exact `INSERT IGNORE` vs `ON DUPLICATE KEY UPDATE` form with that implementation so unique-key behavior stays identical. The multi-row form must also tolerate duplicate `file_id`s within one batch (hardlinks). ### 4.2 Phase 2 — post-order batched sweep (core change) Traversal invariants (from 2.5): - **I1** A directory dentry is deleted only inside a transaction that verified it childless, with a post-DELETE re-check in the same transaction. - **I2** The root dentry is the last row deleted; while it exists it pins the path against recreation (`idx_path` uniqueness). The operation additionally captures the root `node_id` up front and re-validates that exact generation in every sweep transaction and in the final root delete (a fenced delete constrained by `node_id`). If the row disappears or a different node now occupies the path, the operation stops immediately — it never re-seeds against or deletes a replacement tree. - **I3** Every orphan/GC decision derives from rows deleted in the same transaction. - **I4** A directory that was non-empty at first visit is re-evaluated for unlinking after it drains (post-order lift) — no empty-dentry skeleton is left behind. - **I5** A drain batch that deleted zero rows breaks out (descend first); "batch full" is never a progress signal. ``` DeleteDirRecursive(dirPath): # 0. Best-effort: abort in-flight uploads targeting the subtree. # uploads has only exact-match indexes (target_path_hash), no prefix index — # a bounded scan of active uploads for THIS TENANT (all queries carry the # fs_id scope), matching the escaped target_path prefix in application code; # mark the uploads row aborted (not just the S3 multipart session — a # finalized-later upload must not pass its status check). Cost is bounded by # the tenant's active-upload count. Any finalize that still races through is # absorbed by the root non-empty retry in step 3. # 1. Fast path (single transaction, same atomicity as today): # index-walk enumerate the whole subtree via parent_path_hash, cap # deleteBatchSize nodes (files AND directory dentries). If it fits: # delete children post-order (deepest first), delete root last, re-check # root childless post-DELETE; on race, roll back and fall through to the # sweep. If enumeration overflows the cap: roll back, continue. # Remember the enumerated size estimate for budget derivation (see Notes). # 2. Batched sweep. queue = stack{dirPath} # LIFO with set dedup: naturally post-order-ish; # deep dirs processed before their ancestors txCount = 0; deadline = now + maxDuration while queue not empty: parent = pop(queue) loop: # drain this parent in batches if ctx done or txCount >= maxBatches or now > deadline: return ErrDeleteIncomplete tx.begin rows = SELECT node_id, path, file_id, is_directory FROM file_nodes WHERE parent_path_hash = ? AND parent_path = ? ORDER BY name LIMIT deleteBatchSize FOR UPDATE -- indexed range scan; NO keyset cursor — -- always the first N currently-present names, -- so concurrent inserts surface in later batches deleted = 0 for row in rows: if file: DELETE node by node_id; collect file_id; deleted++ if directory: -- row already locked FOR UPDATE by the batch SELECT if dirHasChildrenTx(row.path): -- same tx, LIMIT 1 queue.add(row.path) -- descend later; keep dentry else: DELETE empty dir dentry by node_id -- RowsAffected == 0 is fine: a concurrent rmdir beat us -- to it (idempotent); treat as deleted deleted++ if dirHasChildrenTx(row.path): -- post-DELETE re-check (I1) tx.rollback queue.add(row.path) -- the raced subdir queue.add(parent) -- revisit parent promptly; -- don't wait for step 3 continue outer loop orphan pipeline for this batch's file_ids: lock inodes FOR UPDATE (sort file_ids first to reduce deadlock surface) orphaned = file_ids with no remaining file_nodes ref (current read) UPDATE inodes SET status='DELETED' for orphaned DELETE file_tags for orphaned batched INSERT file_gc_tasks for orphaned (same semantics as 4.1.4) tx.commit txCount++ -- budget counts COMMITTED transactions (drain -- and lift alike); matches batches_total metric if deleted == 0: break -- I5: full batch of non-empty subdirs; -- descend into them first, do not spin if len(rows) < deleteBatchSize: break -- level drained # POST-ORDER LIFT (I4): parent is drained (or only holds queued subdirs) if parent != dirPath: if ctx done or txCount >= maxBatches or now > deadline: return ErrDeleteIncomplete -- budget check applies to lifts too tx.begin row = SELECT node_id FROM file_nodes WHERE path_hash = ? AND path = ? FOR UPDATE if no row: tx.commit; txCount++; liftTxCount++ -- already gone (concurrent -- rmdir): idempotent elif dirHasChildrenTx(parent): tx.commit; txCount++; liftTxCount++ -- legit children still queued, -- or racing creates. Do NOT -- re-queue parent: each child's -- own lift pushes parent back; -- step-3 re-seed finds the rest. else: DELETE parent dentry by node_id -- RowsAffected == 0: idempotent ok if dirHasChildrenTx(parent): -- post-DELETE re-check (I1) tx.rollback -- racing create; the step-3 root -- re-seed will rediscover it else: tx.commit; txCount++; liftTxCount++ queue.add(parentPath(parent)) -- ancestor may be empty now # root is not unlinked here; step 3 owns it # 3. Root last (bounded): for attempt in 1..K: err = DeleteEmptyDir(dirPath) -- extended with a post-DELETE re-check in -- the same tx (I1) if err == nil: return summary{NodesDeleted, OrphansEnqueued, TxCount} if err != ErrDirectoryNotEmpty: return err queue.push(dirPath); run step 2 again -- stragglers/racing creates return ErrDirectoryNotEmpty -- concurrent writers outpaced us; caller may retry ``` Why the lift's "non-empty → don't re-queue" is safe and terminates: after the first full pass, every surviving row still has an intact parent chain up to `dirPath` (I1/I2). A queued subdirectory's own lift pushes its parent back onto the stack, so legitimately non-empty parents are revisited exactly when their last child disappears. Rows created concurrently behind the frontier make some ancestor non-empty at lift time; they are not chased immediately, but the step-3 root deletion fails with `ErrDirectoryNotEmpty` and re-seeds `dirPath`, and the re-walk reaches every surviving row top-down. Under quiescence this converges; under sustained writes the budget (txCount/deadline/ctx) terminates the request with `ErrDeleteIncomplete`. Notes: - **Resumable by construction** (I1/I2/I4): a non-empty directory dentry is never deleted, so every surviving row is reachable from `dirPath` via the `(parent_path_hash, name)` index. A crash at any point leaves a walkable tree; re-calling `DeleteDirRecursive(dirPath)` continues. All steps are idempotent (re-marking `DELETED` is a no-op, GC insert dedupes on `file_id`, re-deleting an already-gone dentry is `RowsAffected == 0` → success). - **Retry at the entry layer works**: the root dentry exists until step 3 succeeds, so `RemoveAllCtx → resolveNodePath` still resolves it; no fake 404. If the root is gone at entry, a previous run completed — return `ErrNotFound` as today (truthful "already deleted"). - **No generation confusion**: while the root row exists the path cannot be recreated; after it is deleted the sweep is done and a recreated path is a new tree no in-flight sweep references. - **Error semantics**: success means the root is gone. Non-convergence under concurrent writers returns `ErrDirectoryNotEmpty`; budget exhaustion returns `ErrDeleteIncomplete`; both are retryable by the caller, and only error returns keep "re-calling converges" true. HTTP mapping is explicit (§4.3), not "generic 500". - **Budget discipline and sizing.** `txCount` is incremented **after a successful commit**, for drain and lift transactions alike (deadlock retries don't burn budget), and is the same counter exported as `delete_dir_recursive_batches_total`; the budget check runs before **every** transaction, lift included. Transaction cost varies hugely by tree shape: a file-heavy tree costs ≈ N/batchSize drain transactions, but a deep chain of single-child directories costs ≈ 2 × dirCount transactions (one 0- or 1-deletion drain + one lift per level), each touching a handful of rows. **Do not set `maxBatches` as a fixed constant derived from file counts** — it would truncate legitimate deep-tree deletes. Derive the budget from the fast-path enumeration (step 1 already walks the tree: `maxBatches ≈ 2 × (files/batchSize + dirs) × headroom`), with `maxDuration`/ctx as the hard backstop. The `delete_dir_recursive_lift_tx_total` metric exists to show whether directory-dense trees warrant the batched-lift optimization (§4.4). - **Lock ordering**: the create path locks inode → file_nodes; the sweep locks file_nodes → inode. Opposite orders can deadlock; each batch transaction gets a bounded retry (deadlock **and** lock-wait/1205, with backoff — align with the existing retryable-error classification and extend it if it only covers deadlocks). Sorting `file_id`s before the inode lock further shrinks the deadlock window. Do not reorder the create path in this change. - **Return value**: `RemoveAllCtx` ignores the `[]*File` result today (dat9.go:570). Phase 2 stops materializing the full orphan slice and returns the summary struct — an internal signature change across `pkg/datastore` and its single caller. Existing tests keep their *behavioral* assertions (tree gone, GC tasks enqueued) but are updated to observe them via GC-task queries instead of the return value. - **`DeleteEmptyDir` change ripples**: adding the post-DELETE re-check to `DeleteEmptyDir` also changes plain `rmdir` behavior (for the better — same race). Call this out in the PR description; it is intentional, not scope creep. - **Scope/legacy**: every new query goes through `s.scope` (shared `fs_id`) and the `useLegacyFiles` branch follows the same batched pipeline, mirroring the existing helpers (`lockFileIDsForDeleteTx`, `markFilesDeletedTx`). - **Residual window** (honest accounting — this design is race-aware, not race-free): I1's post-DELETE re-check shrinks the empty-dir race to the commit boundary, but TiDB's lack of gap locks means a create committing exactly between re-check and commit can still orphan a row. The window is single-statement wide and the orphan is detectable and repairable by the reconciliation sweep (§4.2.1); closing it entirely requires the delete-in-progress marker (§4.4). Semantic change to document (release notes): for large directories the delete is no longer atomic. While the sweep runs, the root path still resolves and `ls` shows a gradually emptying directory; any absolute path whose node has not yet been deleted remains readable (GetNode is `path_hash + path`, independent of ancestor dentries). This matches POSIX `rm -r` (unlinkat per entry). The Phase 2 sweep is still synchronous over HTTP: it bounds *progress loss* (a disconnect rolls back at most one batch, and a retry resumes), not *total duration* — a huge tree can still exceed a gateway deadline; that is what §4.4 addresses. ### 4.2.1 Orphan reconciliation sweep (required companion of Phase 2) Because §4.2's residual window cannot be closed without a schema-level marker, Phase 2 must not launch without a reconciliation job. It is a small, bounded periodic task, not an optional nice-to-have. > **Amendment (post-#39 production tuning).** Two refinements landed after the > original rollout, driven by slow-query evidence from large shared-schema > clusters: (1) the stranded-inode scan is a **two-phase** page — a pure > clustered-PK keyset page over `inodes` (bounding rows *examined*, as before), > then batched `IN (...)` lookups per referenced table/column — replacing the > per-row correlated `NOT EXISTS (file_id = id OR inode_id = id)` projections > whose OR predicates defeated decorrelation; the repair-time re-checks are > likewise split into two single-column point queries. (2) The piggyback > periodic round is **gated on a due `delete_reconcile_pending` marker**: a > tenant with no outstanding delete is never full-table scanned by the > backstop (kick-driven sweeps after deletes are unchanged), and a successful > sweep that repaired rows or stopped mid-pass re-arms the marker with a > single atomic upsert (`RearmDeleteReconcilePending`: owed marker moves to > the follow-up time, newer-delete marker untouched, missing marker > inserted) so multi-round convergence and audit completion are preserved > without a clear-then-insert loss window. The throttle interval is > configurable via `DRIVE9_DELETE_RECONCILE_INTERVAL`. **Scheduling**: a **per-tenant background worker**, consistent with the existing worker pattern — each tenant's `Store` already carries its `fs_id` scope, and the scan runs against that store with `node_id` / `inode_id` cursors, bounded per round. The cursors are held **in-worker per tenant** (`DeleteReconcileState`): a capped round resumes where it stopped, a completed pass resets, and a pod restart or shard-owner change re-covers earlier rows — repairs persist, so this only delays tail coverage, never loses repairs. No cross-tenant job in this change. **Schema coverage**: the stranded-inode scan below is specified for the split schema (`inodes`/`contents`); on `useLegacyFiles` stores the reconciliation job is disabled initially (the legacy `files` equivalent is a follow-up if any legacy deployment still matters) — the broken-chain dentry scan is schema-agnostic and runs on both. The recursive-delete backend path (`RemoveAllCtx`) emits a dedicated `delete_reconcile` work kick **after every recursive delete that touched the tree (`summary != nil`), success or error, even when zero orphans were enqueued**. The §4.2 residual window can strand a broken-chain dentry with no `file_gc` work at all, so the repair pass must be scheduled by the delete itself rather than piggybacked on unrelated semantic/file-GC activity. The kick is durable via the tenant notify outbox (sharded to the tenant's worker). On the consumer side the worker runs the throttled sweep **directly for the kick, outside the 5-minute piggyback-maintenance cadence**, and when the per-tenant reconcile throttle is still active it arms exactly one delayed re-kick so the repair still runs once the window opens — even for a tenant that goes completely idle after the delete. The delayed request is also **durable across pod restarts**: dispatching a `delete_reconcile` outbox row and every throttled/failed sweep upsert a `delete_reconcile_pending` row in the always-provisioned meta DB (due timestamp per tenant), and the outbox poller re-dispatches due pending rows on its cursor-flush cadence until the worker completes a successful sweep and deletes the row. A pod that dies between dispatch and the delayed retry therefore loses nothing: the pending row is independent of the once-consumed outbox cursor. The sweep's success path clears only markers due no later than its own start time, so a marker written mid-sweep by a newer delete survives for the next poller scan; this cutoff assumes a single clock domain (cross-pod NTP skew is bounded and the periodic piggyback reconcile remains the backstop). The producer side is **fail-closed durable before the delete can touch the tree**: `RemoveAllCtx` invokes a synchronously-persisting backend hook BEFORE `DeleteDirRecursive`, and aborts the delete if that write fails. The marker is future-dated (crash-recovery only) by `deleteReconcilePersistLeadTime`, which is kept strictly larger than the recursive-delete wall-clock budget plus poller/scan and clock-skew margins, so a delete cannot outlive its own protection. The post-delete notifier refresh guarantees the row exists and never pulls a future-dated marker earlier (it must not strip another in-flight delete's protection); per-delete immediacy comes from the in-process worker kick, and the marker's future due keeps the sweep-start cutoff clear safe. A crash between any delete commit and the notifier/coalescer therefore still finds the owed marker after restart, and a failed pre-delete write means the delete never runs. The outbox poller also records the marker on **every** pod that reads a `delete_reconcile` row — owner or not — before any pod advances its cursor; shard ownership gates only the kick, never whether durability is recorded, so an owner failover after the row was consumed still finds the pending marker. It runs in **repair mode by default** — as the only backstop for the residual window, a dry-run-only default would count orphans without ever fixing them. The `dryRun` parameter remains for tests and audit tooling. **Broken-chain dentries.** For each scanned row, classify: - `parent_path == "/"` → **always valid, skip without any lookup.** The root is implicit (2.5): there is no `file_nodes` row for `/`, so a parent point-check for a top-level row always misses. Getting this rule wrong means the first reconciliation run classifies every top-level file and directory in the tenant as an orphan and deletes it — the test suite must assert zero hits on top-level rows. - Otherwise the parent must exist **and** be a directory: `SELECT 1 FROM file_nodes WHERE path_hash = ? AND path = ? AND is_directory = 1` (existence alone is not sufficient — a same-path file row does not parent anything). Repair, per candidate, in its own small transaction: `SELECT ... FOR UPDATE` the candidate row by `node_id`, **re-run the parent check in the same transaction** (current read — the first scan was a snapshot), and only then delete the dentry and run the standard orphan pipeline for its `file_id`. A candidate whose parent reappeared (its chain was mid-`EnsureParentDirsTx` when scanned) is skipped. **Convergence is multi-round by design**: repairing a broken-chain *directory* deletes only its own dentry, which strands its children one level down; subsequent reconciliation rounds pick those up (files get the orphan pipeline + GC, subdirectories get repaired in later rounds). This is safe because each round only deletes rows whose chain is broken *at scan time* and re-verified under lock. A test plants a broken-chain directory with an intact subtree and asserts full repair over multiple rounds, with a GC task per file. **Stranded file inodes.** Scope is files only — the directory-inode leak stays a Non-goal, and this scan must not "accidentally fix" it: - Candidate set: `inodes` in `CONFIRMED` status **joined to `contents`** (a directory inode has no `contents` row, so the join excludes them), with no `file_nodes` reference **via either column** (`file_id = id OR inode_id = id` — directory dentries reference through `inode_id`, file dentries through `file_id`), and no `file_gc_tasks` row. - Lock ordering follows the existing orphan pipeline: the scan is a snapshot read; before marking, `SELECT ... FOR UPDATE` the candidate inode and re-run the NOT EXISTS checks as current reads in the same transaction, then `UPDATE ... DELETED` and enqueue the GC task. This keeps reconciliation from racing a create that has inserted its inode but not yet committed its dentry (they commit together, but the re-check makes the pipeline robust to future multi-transaction create flows as well). Metrics: `drive9_delete_reconcile_orphans_found_total{type=dentry|inode, mode=dry_run|repair}` — a sustained non-zero rate in repair mode is the signal to prioritize §4.4's delete-in-progress marker. ### 4.3 Caller changes - `RemoveAllCtx`: after path resolution, the directory branch FIRST invokes the fail-closed durable pre-write (`SetDeleteReconcilePersister` — the server maps it to a synchronous meta-DB `delete_reconcile_pending` upsert future-dated by `deleteReconcilePersistLeadTime`) and aborts without deleting if that write fails. `DeleteDirRecursive` keeps the `(ctx, dirPath)` entry and returns the summary struct; after it returns, the notifier refreshes the marker (never pulling another in-flight delete's future-dated protection earlier) and kicks the worker for immediacy. - `handleDelete` / error mapping: `ErrDirectoryNotEmpty` → 409 (existing path); `ErrDeleteIncomplete` → **503 with `Retry-After`** (a fixed small constant, or derived from `maxDuration`) — wire it explicitly in the backend-error mapping so it does not collapse into an untagged generic 500. Both are retryable; there are no success-with-partial responses. - **Client retry**: the Go SDK bounded retry (backoff honoring a clamped `Retry-After`) lives in the client repository (this repo is server-only). - Per-batch retry wrapper: bounded retries on deadlock + lock-wait timeout with exponential backoff, independent of the outer request deadline. ### 4.4 Optional follow-ups (not in this change) - **Delete-in-progress marker** (root fix for the residual race): a tombstone flag on the root dentry (or a small `delete_jobs` table) checked by all create paths, so creates under a deleting tree are rejected instead of racing the sweep. Requires schema/API changes and read/write path filtering. Prioritize when `delete_reconcile_orphans_found_total` shows the window matters. - **Async delete for huge trees**: enqueue a durable task (reuse the `semantic_tasks` machinery) driving the §4.2 sweep in the background, return `202 Accepted` + task ID past a size threshold. - **Batched lift**: if `delete_dir_recursive_lift_tx_total` shows directory-dense trees dominating, delete all emptied directories of one level in a single transaction instead of one transaction per directory (cuts deep-chain cost by an order of magnitude). - **Directory-inode GC** (pre-existing leak, Non-goals): if picked up, fold it into the reconciliation sweep as a separate candidate class with explicitly defined empty-ref GC semantics. - **Legacy-schema reconciliation**: the `files`-table equivalent of §4.2.1's stranded-inode scan, if any `useLegacyFiles` deployment still matters. - **`RenameDir` LIKE escaping** (2.2 related work). ## 5. Observability - Keep `observeStoreOp(ctx, "delete_dir_recursive", ...)` for the outer call; record total batches, nodes, orphans, duration, and outcome class: `ok` / `incomplete_budget` / `directory_not_empty` / `error`. Log one `zap` info line per sweep with the same fields. No `partial` flag (there is no partial success) and no `resumed` flag — without a delete-in-progress marker, a walkable tree cannot be distinguished from a fresh request, so the field would be fiction. - Per-batch: `delete_dir_recursive_batch` timing plus counters `delete_dir_recursive_batches_total` (== txCount, committed transactions only), `delete_dir_recursive_lift_tx_total` (subset committed by lifts; feeds the §4.4 batched-lift decision), `delete_dir_recursive_nodes_deleted_total`, `delete_dir_recursive_orphans_total`, `delete_dir_recursive_batch_retries_total`, `delete_dir_recursive_incomplete_total{reason=budget|lock_wait}`, `delete_reconcile_orphans_found_total{type,mode}`. ## 6. Testing Unit (package `datastore`, MySQL-backed via `internal/testmysql`; failpoint tests in `*_failpoint_test.go` via `scripts/run_failpoint_tests.py`): - Existing `TestDeleteDirRecursive` / `TestDeleteDirRecursiveDoesNotDeleteSiblingPrefix` (store_test.go:975, 1030) keep their behavioral assertions; assertions that read the returned orphan list are re-pointed at GC-task queries (return type changes). - LIKE metacharacters: `/a_b/` with sibling `/axb/` — only the target subtree is deleted (regression for 2.2). - TOCTOU: failpoint-insert a file mid-sweep **through the real create path** (`EnsureParentDirsTx` + `InsertNodeTx`); assert no blob leak and no invisible orphan: the file is either swept (with GC task) or left in an intact parent chain. - Deep-tree post-order: depth ≥ 3 with intermediate dirs non-empty at first visit; after completion assert **zero directory dentries remain** under the root (this assertion is what kills a sweep missing the post-order lift), then abort mid-sweep via failpoint and re-run to completion. - **Drain livelock (I5)**: a single directory with > 2×deleteBatchSize **non-empty subdirectories**; assert the delete completes without `ErrDeleteIncomplete` (regression for the zero-deletion-batch spin). - **Deep chain**: a ~1000-level chain of single-child directories completes within budget (regression for sizing `maxBatches` by file count; validates the enumeration-derived budget). - Resume entry: after a mid-sweep abort, re-calling `RemoveAllCtx` must not return NotFound-success while rows remain. - Error-on-partial: with a failpoint writer keeping the root non-empty past K rounds, the API returns an error (not success), and a later `RemoveAll` completes the delete. - Empty-dir delete race (drain path): failpoint a create between the childless check and the dentry DELETE; the post-DELETE re-check must roll the batch back and re-queue. (The lift path's post-check failure instead rolls back and defers to the step-3 re-seed — keep the two cases as separate tests.) - Lift idempotency: a concurrent plain `rmdir` deletes an already-drained subdir before the lift runs; the lift treats the missing/`RowsAffected == 0` dentry as success. - Concurrent create: `CreateAndWrite` into the target tree during the sweep; assert convergence and no deletion of data created after the API returned success (path-recreation generation case). - Budget semantics: a directory requiring more committed transactions than the derived budget fails with `ErrDeleteIncomplete` (guards against counting queue pops or attempted transactions); a retry then completes the delete. - Hardlinks: one link inside the tree + one outside; only the last reference enqueues GC. - Rename-out mid-sweep: renamed-away subtree survives intact; no stale-prefix deletion. - Wide directory: single dir with > 2×deleteBatchSize files; multi-batch, no misses. - Small-dir fast path: subtree ≤ deleteBatchSize completes in one transaction (assert via failpoint commit counting), root deleted last within it; a subtree just over the cap rolls the fast path back and completes via the sweep. - Per-batch retry: deadlock/lock-wait injection. - Client retry: SDK `RemoveAll` retries a 503/`Retry-After` response with backoff and surfaces terminal failure only after the bound. - Reconciliation: - plant a normal **top-level** file and dir plus a real broken-chain dentry — repair mode fixes only the latter (zero top-level hits; regression for the implicit-root rule); - plant a broken-chain **directory with an intact subtree** — multiple repair rounds converge: every file gets a GC task, every dentry is removed; - plant a stranded CONFIRMED file inode; assert it is marked DELETED with a GC task; - plant a CONFIRMED **directory** inode with no references; assert the sweep leaves it alone (Non-goal scoping); - in-flight create race: assert the lock-then-recheck pipeline does not kill an inode whose dentry commits between scan and mark. - Shared-tenant `fs_id` scope matrix, if the package's test harness covers it. E2E: extend `e2e/fuse-concurrency-stress.sh` with (a) large-directory `rm -r` under concurrent sibling writers (no 1205s), (b) `rm -r` with the client killed mid-way followed by a retry that completes (resume), (c) `mkdir` at the same path racing the sweep (no new-tree deletion). ## 7. Rollout Decision change after review: **no rollout flag** — the batched implementation is the default and only recursive-delete behavior (the legacy single-transaction path was removed, not kept behind `DRIVE9_RECURSIVE_DELETE_BATCHED`). 1. Ship the batched delete (fast path + sweep), the 503/client-retry mapping, and the §4.2.1 reconciliation job in repair mode together; release notes call out the non-atomicity semantics change, the new retryable error returns (409/503), the `DeleteEmptyDir` re-check ripple on plain `rmdir`, the abort of in-flight uploads under a deleted tree, and the fact that reconciliation now actively repairs (deletes orphan rows) by default. 2. Revisit §4.4 items with production data; the delete-in-progress marker is the first candidate if `delete_reconcile_orphans_found_total` stays non-zero. Suggested PR split: (1) store core — fast path + sweep, error types; (2) server mapping — 503 + `Retry-After`; (3) client retry; (4) reconciliation worker (repair by default); (5) tests per §6. PRs 1-3 land together; 4 follows immediately; 5 rides along with each.