Siyao Meng created HDDS-17739:
---------------------------------
Summary: 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
Reporter: Siyao Meng
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]
