sadanand48 commented on code in PR #10838: URL: https://github.com/apache/ozone/pull/10838#discussion_r3711674544
########## hadoop-hdds/docs/content/design/snapshot-trapped-deleted-bytes.md: ########## @@ -0,0 +1,526 @@ +--- +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 deleteDbKey ledger](#62-deletedbkey-ledger-minimal) + * [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. [Upgrade Notes](#13-upgrade-notes) + +--- + +## 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 a deleteDbKey-based 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 deleteDbKey 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. + +--- + +## 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** | In this design, counter ownership follows the **store snapshot** (snapshot DB currently holding the deleted row) | +| **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 trapped ownership 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`); subtree dir credit when ExpandAndAccount walk completes | 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 deleteDbKey ledger (minimal) + +New OM table: `snapshotTrappedLedgerTable` (name TBD). + +**Key:** `deleteDbKey` (row key in `deletedTable` / `deletedDirTable`) + +**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, + ExpandAndAccount, and 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 deleteDbKey been accounted, for which snapshot, and +in what phase of lifecycle?* + +**Cache:** bounded in-memory map on OM leader mirroring the same three fields (`deleteDbKey` → +`{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 `deleteDbKey`; 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 non-reclaimable dir | += size (**store** snapshot) | += 1 | — | `ACCOUNTED_KEY` on `putIfAbsent` success | +| DDS promotes file to `deletedTable` | += size (**store** snapshot) on `putIfAbsent` success; **no increment** if ledger row already exists | += 1 on success; skip if exists | — | `ACCOUNTED_KEY` on first account only | +| ExpandAndAccountDirService subtree completed | — | — | += expanded subdir count (batched) | after CAS `ACCOUNTED_DIR_ROOT → DIR_EXPAND_ACCOUNTED` | + +All three file increment paths use the same gate: +**`ledger.putIfAbsent(deleteDbKey, storeSnapshotId, 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: + +``` +storeSnapshot = snapshot currently owning the delete DB + +if ledger.putIfAbsent(deleteDbKey, storeSnapshotId, ACCOUNTED_KEY) succeeds: + storeSnapshot.trappedKeyBytes += replicatedSize + storeSnapshot.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 **store** 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 **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 store snapshot + (Phase 5+). + +### 6.4 ExpandAndAccountDirService + +**Purpose:** Account for file bytes under directories that DDS cannot expand because +`ReclaimableDirFilter == false`. + +**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`). Review Comment: > DDS already scans child directories when the root is not reclaimable This is wrong, it doesn't scan it ```java boolean isDirReclaimable = reclaimableDirFilter.apply(pendingDeletedDirInfo); Optional<PurgePathRequest> request = prepareDeleteDirRequest( pendingDeletedDirInfo.getValue(), pendingDeletedDirInfo.getKey(), isDirReclaimable, allSubDirList, getOzoneManager().getKeyManager(), reclaimableFileFilter, remainNum); ``` And inside prepareDeleteDirRequest (lines 485-501, which I can see from the surrounding context), it does: ```java if (isDirReclaimable) { // It expands the directory and adds files to subFiles and dirs to subDirs ... } ``` > Define coordination with DDS, or collect the accounting during the existing DDS traversal. Yes this is addressed on line 241 -- 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]
