[
https://issues.apache.org/jira/browse/HDDS-17739?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Siyao Meng updated HDDS-17739:
------------------------------
Affects Version/s: 2.3.0
> Ordered snapshot diff: path reuse skip in the dependency graph returns a non
> replayable order or a false cycle
> --------------------------------------------------------------------------------------------------------------
>
> Key: HDDS-17739
> URL: https://issues.apache.org/jira/browse/HDDS-17739
> Project: Apache Ozone
> Issue Type: Bug
> Affects Versions: 2.3.0
> Reporter: Siyao Meng
> Priority: Major
> Attachments:
> MC-2-MC-3-order-modify-by-from-snapshot-paths-only.patch,
> TestBugMC2ReoccupiedPathOrderedReplay.java,
> TestBugMC3NestedRecreateFalseCycle.java
>
>
> h3. Mechanism
> {{SnapDiffDependencyGraph}} orders the entries of an FSO snapshot diff when
> the client asks for an ordered report. Among its edges,
> {{addPathPrefixToSnapshotEdges}} puts a CREATE or RENAME target on an
> ancestor path of the newer snapshot before every entry below it. To avoid
> false cycles for a MODIFY reported at an old path that a new object now
> occupies, {{shouldSkipReoccupiedPathToSnapshotEdge}} drops that edge when the
> ancestor path is in the set built by {{buildReoccupiedPaths}} (paths that are
> a DELETE path or a RENAME source and are also a CREATE path or RENAME
> target). Two things are wrong with that skip:
> # It is applied to RENAME entries too, and decided by the RENAME's source
> path. The edges come from the prefixes of the RENAME's target path, and a
> RENAME target below a reoccupied path is by construction below the new
> occupier, so the edge is always needed. Dropping it hides a real cycle and
> the graph returns an order that does not replay.
> # For MODIFY it only treats a path as freed when that exact path was deleted
> or renamed away. A path freed because an ancestor was renamed or deleted is
> not in the set (a DELETE below a deleted directory is not reported), so the
> edge is kept and closes a cycle although a valid order exists.
> h3. Trigger
> Optimized snapshot diff enabled
> ({{ozone.om.snapshot.diff.optimized.enabled}}, default false, not in any
> release yet), an FSO bucket, and a snapshot diff requested with the ordered
> flag.
> * Wrong order: {{mkdir a; create a/a; snapshot 1; mv a b; mkdir a; mv b/a
> a/a; snapshot 2}}. The report entries are {{RENAME a/a -> a/a}}, {{RENAME a
> -> b}}, {{CREATE a}}. The file rename needs the old {{a}} as its source
> parent and the new {{a}} as its target parent, so no order of these entries
> replays.
> * False cycle: {{mkdir -p a/a; create a/a/a; snapshot 1; mv a b; mkdir -p
> a/a; overwrite b/a/a; snapshot 2}}. The entries are {{MODIFY a/a/a}},
> {{RENAME a -> b}}, {{CREATE a}}, {{CREATE a/a}}, and that order replays (the
> MODIFY is reported at its path in snapshot 1).
> h3. Impact
> * Wrong order: the job ends DONE with the reason "Report is dependency
> ordered." and the order {{RENAME a/a -> a/a, RENAME a -> b, CREATE a}}.
> Applying it to a copy of snapshot 1 through the file system leaves the file
> at {{b/a}}, while snapshot 2 has it at {{a/a}}. A client that relies on the
> ordered label to replay the report gets a different namespace without any
> error.
> * False cycle: the ordered job ends FAILED with "Dependency graph cycle for
> job ...". The diff is deterministic, so every ordered request for the pair
> recomputes the diff and fails again. An unordered request returns the report.
> h3. Reproduction
> Two self contained mini cluster classes,
> [^TestBugMC2ReoccupiedPathOrderedReplay.java] and
> [^TestBugMC3NestedRecreateFalseCycle.java] (target path and Maven command in
> each class comment). They enable the optimized diff with a forced full diff
> and native diff disabled, use only public client calls, and pass on
> unmodified source when the bug is present. The first replays the ordered
> report through the Ozone file system on a second bucket that holds the
> snapshot 1 tree and compares it with snapshot 2. The second shows the ordered
> job FAILED and the unordered job DONE with the entries above.
> h3. Patch
> [^MC-2-MC-3-order-modify-by-from-snapshot-paths-only.patch], against
> d3b75c75bf9ad475551202477c3a21a3f4b968b7. It also applies to master at
> bbc8505e00d.
> Both symptoms come from the same skip, so one change fixes both. MODIFY
> entries no longer get edges from ancestor paths of the newer snapshot, and
> the reoccupied path skip ({{buildReoccupiedPaths}},
> {{shouldSkipReoccupiedPathToSnapshotEdge}}) is removed, so CREATE and RENAME
> always keep those edges. A MODIFY is reported at its path in the older
> snapshot ({{SnapDiffDependencyEntry}} contract, followed by
> {{MergeJoinSnapDiffWriter}}), which exists before any new ancestor is
> created, and it is still ordered by the older snapshot edges (before an
> ancestor DELETE or RENAME source). Keeping the skip for MODIFY and extending
> it to paths freed through an ancestor would fire for every MODIFY with a new
> occupier above it, which is what the patch states directly.
> Covered in the existing {{TestSnapDiffDependencyGraph}}:
> {{testRenameSourceReuseWithDescendantRenameIntoNewOccupierDetectsCycle}}
> (first trigger, expects a cycle) and
> {{testRenameSourceReuseByNestedCreateWithDescendantModify}} (second trigger,
> expects the replayable order), and
> {{testDeleteAndRecreateNestedPathWithDescendantModifyAndRename}} (the second
> defect with a deleted ancestor: {{DELETE B, MODIFY B/A/B, RENAME B/A/B -> A,
> CREATE B, CREATE B/A}}, a false cycle at this commit, expects {{MODIFY B/A/B,
> RENAME B/A/B -> A, DELETE B, CREATE B, CREATE B/A}}).
> {{testDeleteAndRecreateWithOldTreeChildModifyAndRename}} asserted an order
> for the first defect's shape with a deleted ancestor ({{DELETE A, CREATE A,
> RENAME A/child -> A/renamed, MODIFY A/child}}), which replays the rename
> inside the old {{A}} and then deletes it; it now expects a cycle. Comments of
> four existing tests that described the removed skip are updated. Without the
> change the four tests above fail; with it {{TestSnapDiffDependencyGraph}},
> {{TestMergeJoinSnapDiffWriter}} and {{TestSnapshotDiffManager}} pass (124
> tests), the existing one level reuse cases that the skip was added for still
> pass, and checkstyle is clean. With the patch the first reproduction ends
> FAILED with "Dependency graph cycle" instead of a wrong ordered report, and
> the second ends DONE "Report is dependency ordered." with {{MODIFY a/a/a,
> RENAME a -> b, CREATE a, CREATE a/a}}. {{TestOptimizedSnapshotDiff}} needs
> the native library and was not run.
> Behaviour change: a real cycle still fails the ordered job at this commit.
> With this patch alone, diffs like the first trigger (a common directory
> rotation such as {{mv a b; mkdir a; mv b/x a/x}}) and the shape of the
> changed test go from a wrong DONE ordered report to a FAILED ordered job on
> every ordered request. HDDS-17738 makes them return an unordered report
> instead, so this patch should land together with or after HDDS-17738. With
> both patches the first reproduction ends DONE "Report is dependency
> unordered.".
> Found by TLA+ model checking and code review of the OM optimized snapshot
> diff paths under HDDS-15926, on commit
> d3b75c75bf9ad475551202477c3a21a3f4b968b7. Checked against HDDS issues and
> apache/ozone pull requests for duplicates before filing. The attached patch
> is a proposal for review. Generated with Specula (Claude Opus 5.5).
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
