sadanand48 commented on code in PR #10838: URL: https://github.com/apache/ozone/pull/10838#discussion_r3703439854
########## hadoop-hdds/docs/content/design/snapshot-trapped-deleted-bytes.md: ########## @@ -0,0 +1,524 @@ +--- +title: Snapshot Trapped Deleted Bytes Accounting +summary: Per-snapshot accounting of logical data trapped in deleted tables due to snapshot references +date: 2026-07-22 +jira: HDDS-15939 +status: proposed +author: Sadanand Shenoy +--- + +<!-- + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. See accompanying LICENSE file. +--> + +# Snapshot Trapped Deleted Bytes — Design Doc + +## Table of Contents + +1. [Motivation](#1-motivation) +2. [Background](#2-background) +3. [Goals and Non-Goals](#3-goals-and-non-goals) +4. [Terminology](#4-terminology) +5. [Current State](#5-current-state) +6. [Proposed Design](#6-proposed-design) + * [6.1 SnapshotInfo fields](#61-snapshotinfo-fields) + * [6.2 ObjectID ledger](#62-objectid-ledger) + * [6.3 Counter lifecycle](#63-counter-lifecycle) + * [6.4 ExpandAndAccountDirService](#64-expandandaccountdirservice) + * [6.5 Integration with existing services](#65-integration-with-existing-services) +7. [Flows](#7-flows) +8. [Race Conditions and Mitigations](#8-race-conditions-and-mitigations) +9. [Configuration](#9-configuration) +10. [API and Observability](#10-api-and-observability) +11. [Phased Implementation Plan](#11-phased-implementation-plan) +12. [Testing Strategy](#12-testing-strategy) +13. [Future Work](#13-future-work) + +--- + +## 1. Motivation + +When a key or directory is deleted in a bucket that has snapshots, the delete is not immediately +physical. Metadata moves to `deletedTable` / `deletedDirTable`, and blocks remain until background +services determine that no snapshot in the chain still references the object. + +Operators and quota systems need to answer: + +> **How much logical deleted data is trapped because of snapshot S?** + +Today: + +* `OmBucketInfo.snapshotUsedBytes` tracks **bucket-level** pending delete space (incremented on + delete, decremented on purge). +* `SnapshotInfo.exclusiveSize` is computed opportunistically during KeyDeletingService deep clean and + does not fully cover directory deletes or provide a complete trapped-delete breakdown. +* After snapshot create, `deletedTable` rows are **partitioned** into the new snapshot checkpoint and + removed from the active object store (AOS). Per-snapshot trapped bytes are not recorded at create + time. +* DirectoryDeletingService **does not expand** directories whose root exists in the pinning snapshot, + so file bytes under pinned dirs are invisible to `deletedTable`-only accounting. + +This design adds **per-snapshot trapped deleted metrics** with bounded OM cost and idempotent +accounting via an objectID ledger. + +--- + +## 2. Background + +### 2.1 Delete and snapshot chain lifecycle (simplified) + +``` +User deletes key + → row in AOS deletedTable + → bucket.usedBytes↓, bucket.snapshotUsedBytes↑ + +Snapshot S2 created + → bucket-prefix rows copied into S2 checkpoint DB + → stripped from AOS deletedTable / deletedDirTable + +KeyDeletingService (KDS) + → ReclaimableKeyFilter: if key not in previous snapshot → purge eligible + → SCM deleteKeyBlocks → OMKeyPurgeRequest → row removed, snapshotUsedBytes↓ + +DirectoryDeletingService (DDS) + → ReclaimableDirFilter: if dir root in previous snapshot → purgeDir=false + → otherwise expand subtree → files to deletedTable → KDS purges blocks + +SnapshotDeletingService (SDS) + → on snapshot delete: move deletedTable/deletedDirTable rows to next snapshot or AOS +``` + +### 2.2 Reclaimable filter semantics + +| Filter | `true` (reclaimable) means | +|--------|----------------------------| +| `ReclaimableKeyFilter` | Deleted key **not** referenced in immediate previous snapshot's key/file table | +| `ReclaimableDirFilter` | Deleted dir root **not** in immediate previous snapshot's directory table | +| `ReclaimableRenameEntryFilter` | Rename target **not** in previous snapshot | + +`true` = eligible for purge/deep clean. It does **not** mean purge has completed. + +--- + +## 3. Goals and Non-Goals + +### Goals + +1. Expose **per-snapshot** trapped deleted **file bytes** and **namespace** counts. +2. Count **directory roots** separately (`trappedDirNamespace`) without walking subtrees at snapshot + create. +3. Account for file bytes under **pinned** (non-reclaimable) directories via a dedicated background + service without blocking DirectoryDeletingService. +4. Prevent double counting using a **minimal objectID ledger** (small cache + DB; three fields only). +5. Decrement counters on **successful purge** (same durability boundary as `purgeSnapshotUsedBytes`). +6. Ship in **small phased PRs** behind feature flags. + +### Non-Goals + +1. Replacing `bucket.snapshotUsedBytes` as the **quota authority** (it remains the bucket total). +2. Full `keyTable` scan at snapshot create (must stay O(deleted rows in bucket)). +3. Synchronous subtree walks on the delete or snapshot-create Ratis path. +4. SCM / datanode physical byte reporting (OM logical size only in v1). +5. Removing `exclusiveSize` / `exclusiveSizeDeltaFromDirDeepCleaning` in the first release (may + deprecate later). +6. Changes to `QuotaRepairTask` (out of scope; existing repair tool unchanged). + +--- + +## 4. Terminology + +| Term | Meaning | +|------|---------| +| **AOS** | Active object store — live OM metadata, not a snapshot checkpoint | +| **Store snapshot** | The snapshot whose DB holds a `deletedTable` / `deletedDirTable` row | +| **Pinning snapshot** | The oldest snapshot in the chain that still references the object's data | +| **Trapped deleted bytes** | Logical data size of deleted objects not yet purged due to snapshot retention | +| **Deep clean** | Background pass that finishes scanning a snapshot's deleted tables (existing flags) | +| **Expand and account** | Read-only subtree walk that attributes file bytes without promoting to purge | + +--- + +## 5. Current State + +| Mechanism | What it measures | Gap | +|-----------|------------------|-----| +| `OmBucketInfo.snapshotUsedBytes` | Bucket total trapped delete bytes | No per-snapshot breakdown | +| `SnapshotInfo.referencedSize` | Estimated live bucket size at create | Not trapped deletes | +| `SnapshotInfo.exclusiveSize` | Keys exclusive to snapshot (KDS side effect) | Incomplete; dirs partial | +| `exclusiveSizeDeltaFromDirDeepCleaning` | Dir deep clean delta | Replaces not accumulates; pinned dirs skipped | +| Recon `DeletedKeysInsightHandler` | Full table scan | Off hot path; no per-snapshot pinning model | + +--- + +## 6. Proposed Design + +### 6.1 SnapshotInfo fields + +New fields on `SnapshotInfo` (Java + `OmClientProtocol.proto`): + +| Field | Type | Set / incremented | Decremented | +|-------|------|-------------------|-------------| +| `trappedKeyBytes` | `long` | Snapshot create (`deletedTable` sum); ExpandAndAccountDirService; DDS promote to `deletedTable` (reclaimable dir) | Successful key purge | +| `trappedKeyNamespace` | `long` | Same | Successful key purge | +| `trappedDirNamespace` | `long` | Snapshot create (count of **root** rows in `deletedDirTable`) | DDS removes root from `deletedDirTable` | + +**Intentionally no `trappedDirBytes` at create** — dir rows carry no file payload. + +`trappedKeyBytes` uses **replicated** logical size (same units as `bucket.snapshotUsedBytes` and KDS +`purgedBytes`) so create / promote increments reconcile with purge decrements. . + +**Displayed total trapped deleted file bytes for snapshot S:** + +``` +totalTrappedDeletedBytes(S) = S.trappedKeyBytes +``` + +`trappedDirNamespace` is namespace-only (pending dir roots), not byte size. + +### 6.2 ObjectID ledger (minimal) + +New OM table: `snapshotTrappedLedgerTable` (name TBD). + +**Key:** `{volumeId}/{bucketId}/{objectId}` + +**Value:** three fields only — no bytes, namespace, or updateId stored in the ledger. + +```protobuf +message SnapshotTrappedLedgerEntry { + enum State { + ACCOUNTED_KEY = 0; // counted in trappedKeyBytes / trappedKeyNamespace + ACCOUNTED_DIR_ROOT = 1; // counted in trappedDirNamespace only + DIR_EXPAND_ACCOUNTED = 2; // dir root: subtree byte scan complete (skip re-walk) + PURGED = 3; + } + required uint64 object_id = 1; + required UUID snapshot_id = 2; // snapshot that owns the trapped counter increment + required State state = 3; +} +``` + +`snapshot_id` meaning: + +* **File / key:** the snapshot whose `trappedKey*` was incremented (store snapshot at create; + **pinning** snapshot after ExpandAndAccount or DDS promote). +* **Dir root:** the store snapshot whose `trappedDirNamespace` was incremented at create. + +Byte and namespace amounts live only on `SnapshotInfo` counters (and in the purge request sizes at +decrement time). The ledger answers only: *has this objectID been accounted, for which snapshot, and +in what phase of lifecycle?* + +**Cache:** bounded in-memory map on OM leader mirroring the same three fields (`objectId` → +`{snapshotId, state}`). Write-through to DB on insert/CAS. No richer cached payload. + +**Rules:** + +* Increment snapshot counters **only** when `putIfAbsent` on ledger succeeds. +* Decrement **only** when CAS `ACCOUNTED_* → PURGED` (or `DIR_EXPAND_ACCOUNTED → PURGED` for dir + root after purge) succeeds. +* One ledger row per objectID; prevents double counting across create, expand, DDS promote, and purge. +* Purge decrement uses **purge payload sizes** (`BucketPurgeKeysSize` / dir purge), not ledger-stored + bytes. + +### 6.3 Counter lifecycle + +#### Increment paths + +| Event | `trappedKeyBytes` | `trappedKeyNamespace` | `trappedDirNamespace` | Ledger | +|-------|-------------------|----------------------|----------------------|--------| +| Snapshot create: `deletedTable` row | += size (store snapshot) | += count | — | `ACCOUNTED_KEY` | +| Snapshot create: `deletedDirTable` root | — | — | += 1 | `ACCOUNTED_DIR_ROOT` | +| ExpandAndAccountDirService: file under pinned dir | += size (**pinning** snapshot) | += 1 | — | `ACCOUNTED_KEY` on `putIfAbsent` success | +| DDS promotes file to `deletedTable` | += size (**pinning** snapshot) on `putIfAbsent` success; **no increment** if ledger row already exists | += 1 on success; skip if exists | — | `ACCOUNTED_KEY` on first account only | + +All three file increment paths use the same gate: **`ledger.putIfAbsent(objectId, pinningSnapshotId, ACCOUNTED_KEY)`** → increment `trappedKey*` only when the insert succeeds. + +#### DDS promote to `deletedTable` (reclaimable directory expansion) + +When DirectoryDeletingService deep-cleans a **reclaimable** deleted dir root, it promotes files from +`fileTable` into `deletedTable`. Those files were not in `deletedTable` at snapshot create (only the +dir root was). It can so happen that the DDS thread first picks up the dir before the Expand thread. + +Per file promoted: + +``` +pinningSnapshot = resolve pinning snapshot (same logic as ReclaimableKeyFilter) + +if ledger.putIfAbsent(objectId, pinningSnapshotId, ACCOUNTED_KEY) succeeds: + pinningSnapshot.trappedKeyBytes += replicatedSize + pinningSnapshot.trappedKeyNamespace += 1 + promote row to deletedTable +else: + # Ledger row already exists (snapshot create or ExpandAndAccount got there first) + promote row only — do not increment trappedKey* +``` + +| Prior ledger state | DDS promote behavior | +|------------------|----------------------| +| Absent | `putIfAbsent` → increment **pinning** snapshot `trappedKey*` → promote | +| `ACCOUNTED_KEY` (create / expand) | Promote only — prevents double count after expand → reclaimable transition | +| `PURGED` | Should not promote; treat as invariant violation | + +Hook location: `OMDirectoriesPurgeResponseWithFSO` (or shared helper invoked when batching file rows +into `deletedTable`). + +#### Decrement paths + +| Event | Where | Condition | +|-------|-------|-----------| +| Key purge success | `OMKeyPurgeRequest` | Ledger CAS → PURGED; decrement **pinning** snapshot (Phase 3: store snapshot via `fromSnapshotInfo`) | +| Dir root purged | `OMDirectoriesPurgeResponseWithFSO` | Root removed; `trappedDirNamespace -= 1` | +| Bucket total | existing `purgeSnapshotUsedBytes` | unchanged semantics | + +**Important:** Decrement happens on **successful purge Ratis txn**, not when `ReclaimableKeyFilter` returns `true`. Purge is already snapshot-aware via `PurgeKeysRequest.snapshotTableKey` → `fromSnapshotInfo`. + +#### AOS purge (no `fromSnapshotInfo`) + +* Decrement `bucket.snapshotUsedBytes` only (existing). +* Do not decrement any `SnapshotInfo.trappedKey*` unless ledger attributes bytes to a pinning snapshot + (Phase 5+). + +### 6.4 ExpandAndAccountDirService + +**Purpose:** Account for file bytes under directories that DDS cannot expand because +`ReclaimableDirFilter == false` (dir root exists in pinning snapshot). + +**Trigger:** DDS enqueues a job when it encounters a non-reclaimable dir root (does not block DDS +iteration). + +**Job input:** + +``` +{ storeSnapshotId | AOS, + deletedDirDbKey, + dirObjectId, + expectedPreviousSnapshotId } +``` + +**Algorithm (batched, low priority):** + +1. Re-validate snapshot chain (`expectedPreviousSnapshotId`). +2. Re-check `ReclaimableDirFilter`; if now reclaimable → exit (DDS owns expansion). +3. Read-only walk `fileTable` under dir root (and subdirs still in `directoryTable`). +4. For each file: resolve pinning snapshot (same logic as `ReclaimableKeyFilter`). +5. `ledger.putIfAbsent(objectId, pinningSnapshotId, ACCOUNTED_KEY)` → on success, increment pinning + snapshot `trappedKey*`. +6. If no unaccounted files remain under root → CAS dir root ledger + `ACCOUNTED_DIR_ROOT → DIR_EXPAND_ACCOUNTED` (skip re-walk on subsequent runs). + +**Does not:** + +* Move rows to `deletedTable` (DDS still owns promotion when reclaimable). +* Call SCM or purge blocks. +* Update `trappedDirNamespace` (root already counted at create). + +**Ratis pressure mitigation:** accumulate counter deltas in memory; one batched `SetSnapshotProperty` or +inline `SnapshotInfo` update per task — **not** one transaction per file. + +### 6.5 Integration with existing services + Review Comment: generated one in the PR description -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
