smengcl commented on code in PR #10778: URL: https://github.com/apache/ozone/pull/10778#discussion_r3644281227
########## hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapDiffDependencyGraph.java: ########## @@ -0,0 +1,252 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.hadoop.ozone.om.snapshot; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Queue; +import java.util.Set; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType; + +/** + * Directed graph of snapshot diff entries and Kahn topological sort for + * dependency-ordered report emission. + * + * <p>Dependency rules encoded by edges (edge {@code u -> v} means {@code u} + * must appear before {@code v}): + * <ul> + * <li>Parent CREATE/RENAME/MODIFY before child CREATE/RENAME/MODIFY.</li> + * <li>Child DELETE before parent DELETE.</li> + * <li>Non-delete entry before DELETE of its parent object.</li> + * <li>DELETE before CREATE/RENAME that targets the same path.</li> + * <li>RENAME before CREATE that reuses the rename source path.</li> + * </ul> + * + * <p>A RENAME target path cannot match a CREATE path in the same diff report. + */ +public final class SnapDiffDependencyGraph { + + private final List<SnapDiffDependencyEntry> nodes = new ArrayList<>(); + private final Map<Integer, Set<Integer>> adjacencyList = new HashMap<>(); + private final Map<Integer, Integer> inDegree = new HashMap<>(); + + /** + * @throws IllegalStateException if entries contain a RENAME target path that + * matches a CREATE path, or if dependency edges form a cycle + */ + public SnapDiffDependencyGraph(List<SnapDiffDependencyEntry> entries) { + for (SnapDiffDependencyEntry entry : entries) { + addNode(entry); + } + buildDependencyEdges(); + } + + /** + * Returns entries in dependency order using Kahn's algorithm. + * + * @return topologically sorted dependency entries + * @throws IllegalStateException if the graph contains a cycle + */ + public List<SnapDiffDependencyEntry> getOrderedEntries() { + Queue<Integer> zeroInDegree = new ArrayDeque<>(); + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + if (inDegree.get(nodeId) == 0) { + zeroInDegree.add(nodeId); + } + } + + List<SnapDiffDependencyEntry> orderedEntries = new ArrayList<>(nodes.size()); + while (!zeroInDegree.isEmpty()) { + int nodeId = zeroInDegree.remove(); + orderedEntries.add(nodes.get(nodeId)); + for (int dependentNodeId : adjacencyList.get(nodeId)) { + int updatedInDegree = inDegree.get(dependentNodeId) - 1; + inDegree.put(dependentNodeId, updatedInDegree); + if (updatedInDegree == 0) { + zeroInDegree.add(dependentNodeId); + } + } + } + + if (orderedEntries.size() != nodes.size()) { + throw new IllegalStateException( + "Cycle detected in snapshot diff dependency graph"); + } + return orderedEntries; + } + + /** + * Converts dependency-ordered entries to report entries. + */ + public static List<DiffReportEntry> toOrderedReportEntries( + List<SnapDiffDependencyEntry> orderedEntries) { + List<DiffReportEntry> reportEntries = + new ArrayList<>(orderedEntries.size()); + for (SnapDiffDependencyEntry entry : orderedEntries) { + reportEntries.add(entry.getReportEntry()); + } + return reportEntries; + } + + private int addNode(SnapDiffDependencyEntry entry) { + int nodeId = nodes.size(); + nodes.add(entry); + adjacencyList.put(nodeId, new HashSet<>()); + inDegree.put(nodeId, 0); + return nodeId; + } + + private void addEdge(int fromNodeId, int toNodeId) { + if (fromNodeId == toNodeId) { + return; + } + if (adjacencyList.get(fromNodeId).add(toNodeId)) { + inDegree.put(toNodeId, inDegree.get(toNodeId) + 1); + } + } + + private void buildDependencyEdges() { + // One objectId can map to multiple non-delete nodes, for example RENAME + MODIFY. + Map<Long, List<Integer>> nonDeleteNodesByObjectId = new HashMap<>(); + // Each objectId has at most one DELETE entry after top-level delete retention. + Map<Long, Integer> deleteNodesByObjectId = new HashMap<>(); + Map<String, List<Integer>> createNodesByPath = new HashMap<>(); + Map<String, List<Integer>> deleteNodesByPath = new HashMap<>(); + Map<String, List<Integer>> renameNodesBySourcePath = new HashMap<>(); + Map<String, List<Integer>> renameNodesByTargetPath = new HashMap<>(); + + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + SnapDiffDependencyEntry entry = nodes.get(nodeId); + if (entry.isDelete()) { + deleteNodesByObjectId.put(entry.getObjectId(), nodeId); + addToPathIndex(deleteNodesByPath, entry.getSourcePath(), nodeId); + } else { + nonDeleteNodesByObjectId + .computeIfAbsent(entry.getObjectId(), ignored -> new ArrayList<>()) + .add(nodeId); + DiffType diffType = entry.getDiffType(); + if (diffType == DiffType.CREATE) { + addToPathIndex(createNodesByPath, entry.getSourcePath(), nodeId); + } else if (diffType == DiffType.RENAME) { + addToPathIndex(renameNodesBySourcePath, entry.getSourcePath(), nodeId); + addToPathIndex(renameNodesByTargetPath, entry.getTargetPath(), nodeId); + } + } + } + + validateRenameTargetDoesNotMatchCreatePath(renameNodesByTargetPath, + createNodesByPath); + + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + SnapDiffDependencyEntry entry = nodes.get(nodeId); + long parentObjectId = entry.getParentObjectId(); + if (parentObjectId <= 0L) { + continue; + } + + Integer parentDeleteNodeId = deleteNodesByObjectId.get(parentObjectId); + if (entry.isDelete()) { + if (parentDeleteNodeId != null) { + addEdge(nodeId, parentDeleteNodeId); + } + } else { + addEdgesFromNodes( + nonDeleteNodesByObjectId.getOrDefault(parentObjectId, + Collections.emptyList()), + nodeId); + if (parentDeleteNodeId != null) { + addEdge(nodeId, parentDeleteNodeId); + } + } + } + + addPathConflictEdges(deleteNodesByPath, createNodesByPath, + renameNodesByTargetPath); + addRenameBeforeCreateEdges(renameNodesBySourcePath, createNodesByPath); Review Comment: Renames also need path dependencies on other renames. For `A -> B` and `B -> C`, `B -> C` must run first to free `B`. Currently only `RENAME -> CREATE` is covered, so input order `[A -> B, B -> C]` is returned unchanged and the first rename cannot be replayed. Please add the corresponding rename-to-rename edge, with chain and cycle tests. ########## hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapDiffDependencyGraph.java: ########## @@ -0,0 +1,252 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.hadoop.ozone.om.snapshot; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Queue; +import java.util.Set; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType; + +/** + * Directed graph of snapshot diff entries and Kahn topological sort for + * dependency-ordered report emission. + * + * <p>Dependency rules encoded by edges (edge {@code u -> v} means {@code u} + * must appear before {@code v}): + * <ul> + * <li>Parent CREATE/RENAME/MODIFY before child CREATE/RENAME/MODIFY.</li> + * <li>Child DELETE before parent DELETE.</li> + * <li>Non-delete entry before DELETE of its parent object.</li> + * <li>DELETE before CREATE/RENAME that targets the same path.</li> + * <li>RENAME before CREATE that reuses the rename source path.</li> + * </ul> + * + * <p>A RENAME target path cannot match a CREATE path in the same diff report. + */ +public final class SnapDiffDependencyGraph { + + private final List<SnapDiffDependencyEntry> nodes = new ArrayList<>(); + private final Map<Integer, Set<Integer>> adjacencyList = new HashMap<>(); + private final Map<Integer, Integer> inDegree = new HashMap<>(); + + /** + * @throws IllegalStateException if entries contain a RENAME target path that + * matches a CREATE path, or if dependency edges form a cycle + */ + public SnapDiffDependencyGraph(List<SnapDiffDependencyEntry> entries) { + for (SnapDiffDependencyEntry entry : entries) { + addNode(entry); + } + buildDependencyEdges(); + } + + /** + * Returns entries in dependency order using Kahn's algorithm. + * + * @return topologically sorted dependency entries + * @throws IllegalStateException if the graph contains a cycle + */ + public List<SnapDiffDependencyEntry> getOrderedEntries() { + Queue<Integer> zeroInDegree = new ArrayDeque<>(); + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + if (inDegree.get(nodeId) == 0) { + zeroInDegree.add(nodeId); + } + } + + List<SnapDiffDependencyEntry> orderedEntries = new ArrayList<>(nodes.size()); + while (!zeroInDegree.isEmpty()) { + int nodeId = zeroInDegree.remove(); + orderedEntries.add(nodes.get(nodeId)); + for (int dependentNodeId : adjacencyList.get(nodeId)) { + int updatedInDegree = inDegree.get(dependentNodeId) - 1; + inDegree.put(dependentNodeId, updatedInDegree); + if (updatedInDegree == 0) { + zeroInDegree.add(dependentNodeId); + } + } + } + + if (orderedEntries.size() != nodes.size()) { + throw new IllegalStateException( + "Cycle detected in snapshot diff dependency graph"); + } + return orderedEntries; + } + + /** + * Converts dependency-ordered entries to report entries. + */ + public static List<DiffReportEntry> toOrderedReportEntries( + List<SnapDiffDependencyEntry> orderedEntries) { + List<DiffReportEntry> reportEntries = + new ArrayList<>(orderedEntries.size()); + for (SnapDiffDependencyEntry entry : orderedEntries) { + reportEntries.add(entry.getReportEntry()); + } + return reportEntries; + } + + private int addNode(SnapDiffDependencyEntry entry) { + int nodeId = nodes.size(); + nodes.add(entry); + adjacencyList.put(nodeId, new HashSet<>()); + inDegree.put(nodeId, 0); + return nodeId; + } + + private void addEdge(int fromNodeId, int toNodeId) { + if (fromNodeId == toNodeId) { + return; + } + if (adjacencyList.get(fromNodeId).add(toNodeId)) { + inDegree.put(toNodeId, inDegree.get(toNodeId) + 1); + } + } + + private void buildDependencyEdges() { + // One objectId can map to multiple non-delete nodes, for example RENAME + MODIFY. + Map<Long, List<Integer>> nonDeleteNodesByObjectId = new HashMap<>(); + // Each objectId has at most one DELETE entry after top-level delete retention. + Map<Long, Integer> deleteNodesByObjectId = new HashMap<>(); + Map<String, List<Integer>> createNodesByPath = new HashMap<>(); + Map<String, List<Integer>> deleteNodesByPath = new HashMap<>(); + Map<String, List<Integer>> renameNodesBySourcePath = new HashMap<>(); + Map<String, List<Integer>> renameNodesByTargetPath = new HashMap<>(); + + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + SnapDiffDependencyEntry entry = nodes.get(nodeId); + if (entry.isDelete()) { + deleteNodesByObjectId.put(entry.getObjectId(), nodeId); + addToPathIndex(deleteNodesByPath, entry.getSourcePath(), nodeId); + } else { + nonDeleteNodesByObjectId + .computeIfAbsent(entry.getObjectId(), ignored -> new ArrayList<>()) + .add(nodeId); + DiffType diffType = entry.getDiffType(); + if (diffType == DiffType.CREATE) { + addToPathIndex(createNodesByPath, entry.getSourcePath(), nodeId); + } else if (diffType == DiffType.RENAME) { + addToPathIndex(renameNodesBySourcePath, entry.getSourcePath(), nodeId); + addToPathIndex(renameNodesByTargetPath, entry.getTargetPath(), nodeId); + } + } + } + + validateRenameTargetDoesNotMatchCreatePath(renameNodesByTargetPath, + createNodesByPath); + + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + SnapDiffDependencyEntry entry = nodes.get(nodeId); + long parentObjectId = entry.getParentObjectId(); + if (parentObjectId <= 0L) { + continue; + } + + Integer parentDeleteNodeId = deleteNodesByObjectId.get(parentObjectId); + if (entry.isDelete()) { + if (parentDeleteNodeId != null) { + addEdge(nodeId, parentDeleteNodeId); + } Review Comment: The `DELETE` branch ignores a parent `RENAME`. For `[RENAME A -> B, DELETE A/child]`, the input order remains unchanged and the delete then addresses a path that has moved. Please add a child `DELETE ->` parent `RENAME` edge and a test for this case. ########## hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapDiffDependencyGraph.java: ########## @@ -0,0 +1,252 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.hadoop.ozone.om.snapshot; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Queue; +import java.util.Set; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType; + +/** + * Directed graph of snapshot diff entries and Kahn topological sort for + * dependency-ordered report emission. + * + * <p>Dependency rules encoded by edges (edge {@code u -> v} means {@code u} + * must appear before {@code v}): + * <ul> + * <li>Parent CREATE/RENAME/MODIFY before child CREATE/RENAME/MODIFY.</li> + * <li>Child DELETE before parent DELETE.</li> + * <li>Non-delete entry before DELETE of its parent object.</li> + * <li>DELETE before CREATE/RENAME that targets the same path.</li> + * <li>RENAME before CREATE that reuses the rename source path.</li> + * </ul> + * + * <p>A RENAME target path cannot match a CREATE path in the same diff report. + */ +public final class SnapDiffDependencyGraph { + + private final List<SnapDiffDependencyEntry> nodes = new ArrayList<>(); + private final Map<Integer, Set<Integer>> adjacencyList = new HashMap<>(); + private final Map<Integer, Integer> inDegree = new HashMap<>(); + + /** + * @throws IllegalStateException if entries contain a RENAME target path that + * matches a CREATE path, or if dependency edges form a cycle + */ + public SnapDiffDependencyGraph(List<SnapDiffDependencyEntry> entries) { + for (SnapDiffDependencyEntry entry : entries) { + addNode(entry); + } + buildDependencyEdges(); + } + + /** + * Returns entries in dependency order using Kahn's algorithm. + * + * @return topologically sorted dependency entries + * @throws IllegalStateException if the graph contains a cycle + */ + public List<SnapDiffDependencyEntry> getOrderedEntries() { + Queue<Integer> zeroInDegree = new ArrayDeque<>(); + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + if (inDegree.get(nodeId) == 0) { + zeroInDegree.add(nodeId); + } + } + + List<SnapDiffDependencyEntry> orderedEntries = new ArrayList<>(nodes.size()); + while (!zeroInDegree.isEmpty()) { + int nodeId = zeroInDegree.remove(); + orderedEntries.add(nodes.get(nodeId)); + for (int dependentNodeId : adjacencyList.get(nodeId)) { + int updatedInDegree = inDegree.get(dependentNodeId) - 1; + inDegree.put(dependentNodeId, updatedInDegree); Review Comment: `getOrderedEntries()` mutates the graph’s stored `inDegree`. After one call, a second call can enqueue every node and return input order instead of dependency order. Please sort using a local copy of the indegrees or cache the result, and add a repeated-call test. ########## hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapDiffDependencyEntry.java: ########## @@ -0,0 +1,91 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.hadoop.ozone.om.snapshot; + +import java.nio.charset.StandardCharsets; +import java.util.Objects; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType; + +/** + * Metadata for a classified snapshot diff entry used to build the dependency + * graph for dependency-ordered report emission. + */ +public final class SnapDiffDependencyEntry { + + private final long objectId; + private final long parentObjectId; + private final DiffReportEntry reportEntry; + + public SnapDiffDependencyEntry(long objectId, long parentObjectId, + DiffReportEntry reportEntry) { Review Comment: A cross-parent rename needs both parent IDs. For `A/B -> C/B` with `DELETE A` and `CREATE C`, `C` must be created before the rename, while `A` must remain until after it. A single `parentObjectId` can enforce only one of these dependencies. Please carry the source and target parent IDs, or equivalent explicit dependencies. ########## hadoop-ozone/ozone-manager/src/main/java/org/apache/hadoop/ozone/om/snapshot/SnapDiffDependencyGraph.java: ########## @@ -0,0 +1,252 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.hadoop.ozone.om.snapshot; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Queue; +import java.util.Set; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry; +import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType; + +/** + * Directed graph of snapshot diff entries and Kahn topological sort for + * dependency-ordered report emission. + * + * <p>Dependency rules encoded by edges (edge {@code u -> v} means {@code u} + * must appear before {@code v}): + * <ul> + * <li>Parent CREATE/RENAME/MODIFY before child CREATE/RENAME/MODIFY.</li> + * <li>Child DELETE before parent DELETE.</li> + * <li>Non-delete entry before DELETE of its parent object.</li> + * <li>DELETE before CREATE/RENAME that targets the same path.</li> + * <li>RENAME before CREATE that reuses the rename source path.</li> + * </ul> + * + * <p>A RENAME target path cannot match a CREATE path in the same diff report. + */ +public final class SnapDiffDependencyGraph { + + private final List<SnapDiffDependencyEntry> nodes = new ArrayList<>(); + private final Map<Integer, Set<Integer>> adjacencyList = new HashMap<>(); + private final Map<Integer, Integer> inDegree = new HashMap<>(); + + /** + * @throws IllegalStateException if entries contain a RENAME target path that + * matches a CREATE path, or if dependency edges form a cycle + */ + public SnapDiffDependencyGraph(List<SnapDiffDependencyEntry> entries) { + for (SnapDiffDependencyEntry entry : entries) { + addNode(entry); + } + buildDependencyEdges(); + } + + /** + * Returns entries in dependency order using Kahn's algorithm. + * + * @return topologically sorted dependency entries + * @throws IllegalStateException if the graph contains a cycle + */ + public List<SnapDiffDependencyEntry> getOrderedEntries() { + Queue<Integer> zeroInDegree = new ArrayDeque<>(); + for (int nodeId = 0; nodeId < nodes.size(); nodeId++) { + if (inDegree.get(nodeId) == 0) { + zeroInDegree.add(nodeId); + } + } + + List<SnapDiffDependencyEntry> orderedEntries = new ArrayList<>(nodes.size()); + while (!zeroInDegree.isEmpty()) { + int nodeId = zeroInDegree.remove(); + orderedEntries.add(nodes.get(nodeId)); + for (int dependentNodeId : adjacencyList.get(nodeId)) { + int updatedInDegree = inDegree.get(dependentNodeId) - 1; + inDegree.put(dependentNodeId, updatedInDegree); + if (updatedInDegree == 0) { + zeroInDegree.add(dependentNodeId); + } + } + } + + if (orderedEntries.size() != nodes.size()) { + throw new IllegalStateException( + "Cycle detected in snapshot diff dependency graph"); + } + return orderedEntries; + } + + /** + * Converts dependency-ordered entries to report entries. + */ + public static List<DiffReportEntry> toOrderedReportEntries( + List<SnapDiffDependencyEntry> orderedEntries) { + List<DiffReportEntry> reportEntries = + new ArrayList<>(orderedEntries.size()); + for (SnapDiffDependencyEntry entry : orderedEntries) { + reportEntries.add(entry.getReportEntry()); + } + return reportEntries; + } + + private int addNode(SnapDiffDependencyEntry entry) { + int nodeId = nodes.size(); + nodes.add(entry); + adjacencyList.put(nodeId, new HashSet<>()); + inDegree.put(nodeId, 0); Review Comment: Each node allocates an empty `HashSet` plus boxed entries in two `HashMap`s, before the temporary path and object indexes. The default changed-key limit is one billion, so this representation can exhaust OM heap far below the configured limit. Please consider primitive, lazy, or batched graph state and add scale coverage. -- 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]
