jojochuang commented on code in PR #10335: URL: https://github.com/apache/ozone/pull/10335#discussion_r3532114450
########## hadoop-hdds/docs/content/design/efficient-snapdiff.md: ########## @@ -0,0 +1,254 @@ +--- +title: Snapshot Diff Optimization +summary: Describe proposal for an optimized snapshot diff that uses mostly sequential reads and batch puts +date: 2025-05-22 +jira: HDDS-9154 +status: draft +author: Saketa Chalamchala +--- +<!-- + 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. +--> + +## 1. Introduction +This document outlines the technical design, architectural choices, and algorithmic improvements to optimize Ozone's Snapshot Diff feature. The design addresses performance bottlenecks in both the **Full Diff** and **DAG-based Diff** paths. The primary goals are to reduce random I/O, minimize CPU overhead from deserialization, and streamline the classification of differences. + + ## Goals + - Reduce random I/O. + - Minimize CPU cost of deserializing KeyInfo and DirectoryInfo for comparisons. + - Keep baseline diff semantics for CREATE/DELETE/RENAME/MODIFY where possible. + +--- + +## 2. Core Design Choices & Optimizations + +### 2.1. Sequential Reads & Table Iterators +**Baseline Issue:** Baseline full diff enumerates keys via SST readers (plus per-key `db.get` lookups), and the DAG-based diff relies heavily on random point lookups (`db.get()`) against the snapshot RocksDB instances to fetch the old and new states of keys identified in the delta SST files. For buckets with millions of keys, this random I/O degrades performance and thrashes the OS page cache. +**Optimized Design:** The optimization shifts mostly to sequential reads. For the Full Diff path, it uses native RocksDB **Table Iterators** to scan the entire `directoryTable` and `fileTable` sequentially. For the DAG-based path, it uses a **K-way Merge Iterator** over the delta SST files to sequentially extract the latest visible versions without needing to query the main snapshot DBs. This sequential I/O pattern maximizes disk throughput and cache efficiency. + +### 2.2. Lightweight Parsing +**Baseline Issue:** The baseline implementation fully deserializes `OmKeyInfo` and `OmDirectoryInfo` protobuf messages to compare objects, which is extremely CPU and memory intensive when scanning millions of keys. +**Optimized Design:** Introduces a lightweight `SnapshotDiffValueParser` that reads the raw protobuf byte stream directly. It extracts only the required fields (like `updateID`, `parentID`, `name` and compare signature fields) without instantiating full Java objects. It dynamically builds a compare signature by hashing only meaningful fields (content-change: latest block layout, size, `fileChecksum` and metadata-change: ACLs, metadata, tags), skipping volatile fields like `modificationTime` or `creationTime` to identify modified entries. + +#### Pseudo-code: Selective Parsing and Signature +```java +ParsedObjectInfo parseRequiredKeyInfo(byte[] raw, boolean meaningfulOnly) { + ParsedObjectInfo parsed = new ParsedObjectInfo(); + CodedInputStream input = CodedInputStream.newInstance(raw); + while (!input.isAtEnd()) { + int tag = input.readTag(); + switch (WireFormat.getTagFieldNumber(tag)) { + case KEYINFO_OBJECT_ID_FIELD: + parsed.setObjectId(input.readUInt64()); + break; + case KEYINFO_PARENT_ID_FIELD: + parsed.setParentId(input.readUInt64()); + break; + case KEYINFO_KEY_NAME_FIELD: + parsed.setName(input.readString()); + break; + case KEYINFO_UPDATE_ID_FIELD: + parsed.setUpdateId(input.readUInt64()); + break; + default: + input.skipField(tag); + break; + } + } + return parsed; +} + +ParsedObjectInfo parseSignatureKeyInfo(byte[] raw, boolean meaningfulOnly) { + ParsedObjectInfo parsed = new ParsedObjectInfo(); + CodedInputStream input = CodedInputStream.newInstance(raw); + while (!input.isAtEnd()) { + int tag = input.readTag(); + switch (WireFormat.getTagFieldNumber(tag)) { + case KEYINFO_METADATA_FIELD: + case KEYINFO_ACLS_FIELD: + case KEYINFO_TAGS_FIELD: + case KEYINFO_FILE_CHECKSUM_FIELD: + updateSignature(tag, input, parsed); + break; + case KEYINFO_BLOCK_LOCATIONS_FIELD: + updateSignature(extractLatestBlockInfo(tag, input), parsed); + default: + input.skipField(tag); + break; + } + } + return parsed; +} +``` + +### 2.3. Sequence/UpdateID Gating +**Baseline Issue:** The baseline performs full object comparisons including timestamps to detect modifications, which is susceptible to clock skew and is computationally expensive. +**Optimized Design:** Use snapshot-specific gates that align with the transactional guarantees of the deployment mode. +- **Full diff (w/ OM HA only):** `updateID > fromSnapshot.lastTransactionInfo.txIndex`. This compares two OM/Ratis log indices. +- **DAG diff:** Extend raw SST iterators to expose internal sequence numbers, gate with `entry.sequence > fromSnapshot.dbTxSequenceNumber`. + +### 2.4. Deferred Classification & Path Resolution +**Baseline Issue:** Baseline builds the diff key set first and then classifies entries during `generateDiffReport`, which requires resolving paths for all candidates. This causes unnecessary path lookups for entries that might ultimately be ignored. +**Optimized Design:** Diff classification is strictly deferred to the final **Merge Join** stage. Path resolution is also deferred until an entry is definitively classified as a diff. This prevents wasting I/O and CPU on resolving paths for entries that might ultimately be ignored or unchanged. + +### 2.5. Batch Puts to Snapshot Diff DB +**Baseline Issue:** Writing intermediate lists and final diff reports often relies on individual RocksDB `put` operations, incurring high JNI overhead. +**Optimized Design:** The design advocates for using RocksDB `WriteBatch` operations. By batching writes to the `snap-diff-report-table` and intermediate `PersistentList`/`PersistentMap` structures, we significantly improve write throughput and reduce disk sync overhead. + +### 2.6. Delete Report Consistency +**Baseline Issue:** With baseline full diff, deleting a directory emits `DELETE` entries for the directory but reports sub-directories and sub-files inconsistently depending on how far deep cleaning of the `toSnapshot` progressed. In DAG-based diff, only the deleted directory and any sub-directory/sub-file that was explicitly deleted before the top-level directory are reported. For the same snapshots, diff output can vary based on timing (before vs after deep cleaning) or mode (full diff vs DAG-based diff). +**Optimized Design:** Only top level deleted directories are reported. This keeps diff results stable regardless of snapshot deep cleaning and which diff path was used. + +### 2.7. Dependency Ordered Reporting +**Baseline Issue:** With baselines, diff report entries are ordered by diff type, `DELETES` are reported first followed by `RENAMES, CREATES, MODIFIES` in order. When the report is replayed this order does not safely cover all scenarios. + +For example, +* Snapshot 1 has file `A/B` and directory `C`. +* Snapshot 2 renames `A/B` to `C/B` and deletes directory `A`. +* The diff entries are `RENAME A/B -> C/B` and `DELETE A`. +If deletes are replayed first, `A/B` is removed before the rename and the rename fails. The correct replay order is `RENAME A/B -> C/B` followed by `DELETE A`. + +**Optimized Design:** Ensure the report can be replayed safely by ordering entries based on their dependencies rather than their diff type. + +**Dependency Rules:** +1. Parents must appear before children for `CREATE/RENAME/MODIFY`. +2. Children must appear before parents for `DELETE`. +3. If a rename or create targets a path that is being deleted, the delete must come first. +4. If a rename frees a source path that is re-created in the same diff, the rename must come first. + +**Building the dependency graph:** +- Each diff entry becomes a node in a directed graph. +- Add edges using the rules above: + - For hierarchy ordering, add edges from parent to child for `CREATE/RENAME/MODIFY`. + - For deletes, use the same parent-child edges but emit them in reverse order later. + - For path conflicts, add edges from the delete node to the rename/create node that reuses the deleted path, and from rename to create if the rename frees a path that is re-created. + +**Emitting entries using the graph:** Review Comment: Kahn's algorithm: topological order algorithm -- 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]
