This is an automated email from the ASF dual-hosted git repository.
smengcl pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ozone.git
The following commit(s) were added to refs/heads/master by this push:
new 5be6afae7af HDDS-15389. Top-level delete entry retention utilities for
snapshot diff. (#10750)
5be6afae7af is described below
commit 5be6afae7af5c342baddf11270af87a77261b7a3
Author: SaketaChalamchala <[email protected]>
AuthorDate: Tue Aug 11 11:35:18 2026 -0700
HDDS-15389. Top-level delete entry retention utilities for snapshot diff.
(#10750)
---
.../ozone/om/snapshot/SnapshotDiffManager.java | 102 ++++++++++++++++
.../ozone/om/snapshot/TestSnapshotDiffManager.java | 129 +++++++++++++++++++++
2 files changed, 231 insertions(+)
diff --git
a/hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapshotDiffManager.java
b/hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapshotDiffManager.java
index e885e2b4f68..9909f5792d7 100644
---
a/hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapshotDiffManager.java
+++
b/hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapshotDiffManager.java
@@ -80,6 +80,7 @@
import java.util.Collection;
import java.util.Collections;
import java.util.EnumMap;
+import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
@@ -96,6 +97,7 @@
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.BiFunction;
import java.util.function.Consumer;
+import java.util.function.Predicate;
import java.util.stream.Collectors;
import javax.management.ObjectName;
import org.apache.commons.io.file.PathUtils;
@@ -1354,6 +1356,106 @@ private String resolveBucketRelativePath(boolean
isFSOBucket,
.substring(1);
}
+ /**
+ * Returns whether any ancestor of the given parent is a deleted directory.
+ * The walk stops at renamed directories because their descendant deletes are
+ * not subsumed by a deleted ancestor above them. Returns true when the
parent
+ * chain cannot be resolved in the live from-snapshot directory graph, so the
+ * delete entry can be skipped from the final report.
+ *
+ * @param objectIdToParentId from-snapshot directory parent graph keyed by
stable
+ * objectId; must not be the to-snapshot graph
+ * @param renamedDirectoryIds objectIds of directories renamed in the diff
(from
+ * snapshot objectIds, not destination paths)
+ */
+ @VisibleForTesting
+ boolean hasDeletedAncestor(long parentObjectId, Set<Long>
deletedDirectoryIds,
+ Set<Long> renamedDirectoryIds, Map<Long, Long> objectIdToParentId,
+ long bucketObjectId, Map<Long, Boolean> ancestorMemo) {
+ Objects.requireNonNull(objectIdToParentId, "objectIdToParentId must not be
null");
+ Objects.requireNonNull(renamedDirectoryIds, "renamedDirectoryIds must not
be null");
+
+ if (parentObjectId == bucketObjectId) {
+ return false;
+ }
+ Boolean cached = ancestorMemo.get(parentObjectId);
+ if (cached != null) {
+ return cached;
+ }
+
+ List<Long> path = new ArrayList<>();
+ long current = parentObjectId;
+ boolean result;
+ while (true) {
+ if (current == bucketObjectId) {
+ result = false;
+ break;
+ }
+ cached = ancestorMemo.get(current);
+ if (cached != null) {
+ result = cached;
+ break;
+ }
+ if (renamedDirectoryIds.contains(current)) {
+ result = false;
+ ancestorMemo.put(current, false);
+ break;
+ }
+ if (deletedDirectoryIds.contains(current)) {
+ result = true;
+ ancestorMemo.put(current, true);
+ break;
+ }
+ Long nextParent = objectIdToParentId.get(current);
+ if (nextParent == null) {
+ result = true;
+ ancestorMemo.put(current, true);
+ break;
+ }
+ path.add(current);
+ current = nextParent;
+ }
+ for (Long node : path) {
+ ancestorMemo.put(node, result);
+ }
+ return result;
+ }
+
+ /**
+ * Filters mixed directory and file delete entries, retaining only those
without
+ * a deleted directory ancestor. FSO buckets only.
+ *
+ * @param objectIdToParentId from-snapshot directory parent graph keyed by
stable
+ * objectId, built from a full fromSnapshot directoryTable scan
+ * @param renamedDirectoryIds objectIds of directories renamed in the diff
(from
+ * snapshot objectIds); pass an empty set when there are no renames
+ */
+ @VisibleForTesting
+ <T extends WithParentObjectId> List<T> filterTopLevelDeletedEntries(
+ Collection<T> deletedEntries,
+ Predicate<T> isDirectory,
+ Map<Long, Long> objectIdToParentId,
+ Set<Long> renamedDirectoryIds,
+ long bucketObjectId) {
+ Objects.requireNonNull(objectIdToParentId, "objectIdToParentId must not be
null");
+ Objects.requireNonNull(renamedDirectoryIds, "renamedDirectoryIds must not
be null");
+ Set<Long> deletedDirectoryIds = new HashSet<>();
+ for (T deletedEntry : deletedEntries) {
+ if (isDirectory.test(deletedEntry)) {
+ deletedDirectoryIds.add(deletedEntry.getObjectID());
+ }
+ }
+ Map<Long, Boolean> ancestorMemo = new HashMap<>();
+ List<T> filteredDeletes = new ArrayList<>();
+ for (T deletedEntry : deletedEntries) {
+ if (!hasDeletedAncestor(deletedEntry.getParentObjectID(),
deletedDirectoryIds,
+ renamedDirectoryIds, objectIdToParentId, bucketObjectId,
ancestorMemo)) {
+ filteredDeletes.add(deletedEntry);
+ }
+ }
+ return filteredDeletes;
+ }
+
@SuppressWarnings({"checkstyle:ParameterNumber", "checkstyle:MethodLength"})
Pair<Long, String> generateDiffReport(
final String jobId,
diff --git
a/hadoop-ozone/ozone-manager/src/test/java/org/apache/hadoop/ozone/om/snapshot/TestSnapshotDiffManager.java
b/hadoop-ozone/ozone-manager/src/test/java/org/apache/hadoop/ozone/om/snapshot/TestSnapshotDiffManager.java
index 3dc468d409e..69507a6d749 100644
---
a/hadoop-ozone/ozone-manager/src/test/java/org/apache/hadoop/ozone/om/snapshot/TestSnapshotDiffManager.java
+++
b/hadoop-ozone/ozone-manager/src/test/java/org/apache/hadoop/ozone/om/snapshot/TestSnapshotDiffManager.java
@@ -1674,6 +1674,112 @@ public void testGetSnapshotDiffReportWhenDone() throws
Exception {
.containsExactlyElementsOf(expectedEntries);
}
+ @ParameterizedTest(name = "{0}")
+ @MethodSource("filterTopLevelDeletedEntryScenarios")
+ public void testFilterTopLevelDeletedEntries(
+ String scenarioDescription,
+ List<WithParentObjectId> deletedEntries,
+ Set<Long> renamedDirectoryIds,
+ Map<Long, Long> objectIdToParentId,
+ Set<Long> expectedObjectIds) {
+ long bucketObjectId = 0L;
+ Map<Long, Long> parentMap = objectIdToParentId != null
+ ? objectIdToParentId
+ : buildDirATreeParentMap(bucketObjectId);
+
+ List<WithParentObjectId> filteredDeletes = snapshotDiffManager
+ .filterTopLevelDeletedEntries(deletedEntries,
OmDirectoryInfo.class::isInstance,
+ parentMap, renamedDirectoryIds, bucketObjectId);
+
+ assertThat(filteredDeletes)
+ .extracting(WithParentObjectId::getObjectID)
+ .containsExactlyInAnyOrderElementsOf(expectedObjectIds);
+ }
+
+ private static Stream<Arguments> filterTopLevelDeletedEntryScenarios() {
+ long bucketObjectId = 0L;
+ OmDirectoryInfo dirA = newDeletedDir(100L, bucketObjectId);
+ OmDirectoryInfo dirB = newDeletedDir(101L, 100L);
+ OmDirectoryInfo dirC = newDeletedDir(102L, 101L);
+ OmDirectoryInfo dirD = newDeletedDir(103L, 101L);
+ OmKeyInfo fileA = newDeletedFile(104L, 102L);
+ OmKeyInfo fileUnderDirB = newDeletedFile(105L, 101L);
+ return Stream.of(
+ Arguments.of(
+ "full candidate set keeps only top-level deleted dirA",
+ Arrays.asList(dirA, dirB, dirC, fileA, dirD),
+ Collections.emptySet(),
+ null,
+ Sets.newHashSet(dirA.getObjectID())),
+ Arguments.of(
+ "partial DAG candidates with dirA dirD and fileA keep only dirA",
+ Arrays.asList(dirA, dirD, fileA),
+ Collections.emptySet(),
+ null,
+ Sets.newHashSet(dirA.getObjectID())),
+ Arguments.of(
+ "deleted dirB with partial candidates keeps only dirB",
+ Arrays.asList(dirB, dirD, fileA),
+ Collections.emptySet(),
+ null,
+ Sets.newHashSet(dirB.getObjectID())),
+ Arguments.of(
+ "sibling deleted dirs dirD and dirC suppress fileA under deleted
dirC",
+ Arrays.asList(dirD, dirC, fileA),
+ Collections.emptySet(),
+ null,
+ Sets.newHashSet(dirD.getObjectID(), dirC.getObjectID())),
+ Arguments.of(
+ "unrelated deleted dirD and fileA are both kept",
+ Arrays.asList(dirD, fileA),
+ Collections.emptySet(),
+ null,
+ Sets.newHashSet(dirD.getObjectID(), fileA.getObjectID())),
+ Arguments.of(
+ "renamed dirB retains file delete when dirA is also deleted",
+ Arrays.asList(dirA, fileUnderDirB),
+ Sets.newHashSet(dirB.getObjectID()),
+ null,
+ Sets.newHashSet(dirA.getObjectID(), fileUnderDirB.getObjectID())),
+ Arguments.of(
+ "broken parent chain in live directory graph skips delete from
report",
+ Collections.singletonList(fileA),
+ Collections.emptySet(),
+ ImmutableMap.of(102L, 101L),
+ Collections.emptySet()),
+ Arguments.of(
+ "delete with parent absent from live directory graph is skipped",
+ Collections.singletonList(newDeletedFile(104L, 999L)),
+ Collections.emptySet(),
+ null,
+ Collections.emptySet()));
+ }
+
+ @Test
+ public void testFilterTopLevelDeletedEntriesRejectsNullArguments() {
+ long bucketObjectId = 0L;
+ OmDirectoryInfo dirA = newDeletedDir(100L, bucketObjectId);
+ List<OmDirectoryInfo> deletedEntries = Collections.singletonList(dirA);
+
+ assertThrows(NullPointerException.class, () -> snapshotDiffManager
+ .filterTopLevelDeletedEntries(deletedEntries,
OmDirectoryInfo.class::isInstance,
+ null, Collections.emptySet(), bucketObjectId));
+ assertThrows(NullPointerException.class, () -> snapshotDiffManager
+ .filterTopLevelDeletedEntries(deletedEntries,
OmDirectoryInfo.class::isInstance,
+ Collections.emptyMap(), null, bucketObjectId));
+ }
+
+ private static Map<Long, Long> buildDirATreeParentMap(long bucketObjectId) {
+ return ImmutableMap.<Long, Long>builder()
+ .put(100L, bucketObjectId)
+ .put(101L, 100L)
+ .put(102L, 101L)
+ .put(103L, 101L)
+ .put(104L, 102L)
+ .put(105L, 101L)
+ .build();
+ }
+
@Test
public void
testGetSnapshotDiffReportReportOnlyInProgressIncludesProgressDetails()
throws IOException {
@@ -1687,4 +1793,27 @@ public void
testGetSnapshotDiffReportReportOnlyInProgressIncludesProgressDetails
ctx.volumeName, ctx.bucketName, ctx.fromSnapshotName,
ctx.toSnapshotName, "", 1000);
assertEquals(IN_PROGRESS, response.getJobStatus());
}
+
+ private static OmDirectoryInfo newDeletedDir(long objectId, long parentId) {
+ return OmDirectoryInfo.newBuilder()
+ .setObjectID(objectId)
+ .setParentObjectID(parentId)
+ .setName("dir-" + objectId)
+ .setOwner("test")
+ .setCreationTime(0L)
+ .setModificationTime(0L)
+ .build();
+ }
+
+ private static OmKeyInfo newDeletedFile(long objectId, long parentId) {
+ return new OmKeyInfo.Builder()
+ .setObjectID(objectId)
+ .setParentObjectID(parentId)
+ .setVolumeName(VOLUME_NAME)
+ .setBucketName(BUCKET_NAME)
+ .setKeyName("file-" + objectId)
+ .setReplicationConfig(new ECReplicationConfig(3, 2))
+ .build();
+ }
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
