You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ozone.apache.org by sa...@apache.org on 2022/05/04 06:42:16 UTC
[ozone] branch master updated: HDDS-6640. Node.isAncestor might return incorrect result (#3342)
This is an automated email from the ASF dual-hosted git repository.
sammichen 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 c33f6a58d8 HDDS-6640. Node.isAncestor might return incorrect result (#3342)
c33f6a58d8 is described below
commit c33f6a58d8a1a38ecf571b8f7e7f166db3354900
Author: Symious <yi...@foxmail.com>
AuthorDate: Wed May 4 14:42:10 2022 +0800
HDDS-6640. Node.isAncestor might return incorrect result (#3342)
---
.../apache/hadoop/hdds/scm/net/InnerNodeImpl.java | 3 +-
.../org/apache/hadoop/hdds/scm/net/NetUtils.java | 22 +++++++++-
.../hadoop/hdds/scm/net/NetworkTopologyImpl.java | 22 +++++-----
.../java/org/apache/hadoop/hdds/scm/net/Node.java | 28 +++++++++++++
.../org/apache/hadoop/hdds/scm/net/NodeImpl.java | 33 +++++++++++++--
.../hdds/scm/net/TestNetworkTopologyImpl.java | 48 +++++++++++++++++++---
6 files changed, 133 insertions(+), 23 deletions(-)
diff --git a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/InnerNodeImpl.java b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/InnerNodeImpl.java
index bb4a16497e..e0451d4b38 100644
--- a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/InnerNodeImpl.java
+++ b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/InnerNodeImpl.java
@@ -473,8 +473,7 @@ public class InnerNodeImpl extends NodeImpl implements InnerNode {
continue;
}
if (excludedScopes != null && excludedScopes.size() > 0) {
- if (excludedScopes.stream().anyMatch(scope ->
- node.getNetworkFullPath().startsWith(scope))) {
+ if (excludedScopes.stream().anyMatch(node::isDescendant)) {
continue;
}
}
diff --git a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetUtils.java b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetUtils.java
index 69bfed96f1..b13b006e77 100644
--- a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetUtils.java
+++ b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetUtils.java
@@ -105,13 +105,13 @@ public final class NetUtils {
}
// excludedScope is child of ancestor
List<String> duplicateList = mutableExcludedScopes.stream()
- .filter(scope -> scope.startsWith(ancestor.getNetworkFullPath()))
+ .filter(ancestor::isAncestor)
.collect(Collectors.toList());
mutableExcludedScopes.removeAll(duplicateList);
// ancestor is covered by excludedScope
mutableExcludedScopes.stream().forEach(scope -> {
- if (ancestor.getNetworkFullPath().startsWith(scope)) {
+ if (ancestor.isDescendant(scope)) {
// remove exclude node if it's covered by excludedScope
iterator.remove();
}
@@ -149,4 +149,22 @@ public final class NetUtils {
}
return ancestorList;
}
+
+ /**
+ * Ensure {@link NetConstants#PATH_SEPARATOR_STR} is added to the suffix of
+ * the path.
+ * @param path path to add suffix
+ * @return the normalised path
+ * If <i>path</i>is empty, then {@link NetConstants#PATH_SEPARATOR_STR} is
+ * returned
+ */
+ public static String addSuffix(String path) {
+ if (path == null) {
+ return null;
+ }
+ if (!path.endsWith(NetConstants.PATH_SEPARATOR_STR)) {
+ return path + NetConstants.PATH_SEPARATOR_STR;
+ }
+ return path;
+ }
}
diff --git a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetworkTopologyImpl.java b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetworkTopologyImpl.java
index 206a0fd73b..cdead1b091 100644
--- a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetworkTopologyImpl.java
+++ b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NetworkTopologyImpl.java
@@ -534,7 +534,7 @@ public class NetworkTopologyImpl implements NetworkTopology {
" generation " + ancestorGen);
}
// affinity ancestor should has overlap with scope
- if (affinityAncestor.getNetworkFullPath().startsWith(scope)) {
+ if (affinityAncestor.isDescendant(scope)) {
finalScope = affinityAncestor.getNetworkFullPath();
} else if (!scope.startsWith(affinityAncestor.getNetworkFullPath())) {
return null;
@@ -542,6 +542,7 @@ public class NetworkTopologyImpl implements NetworkTopology {
// reset ancestor generation since the new scope is identified now
ancestorGen = 0;
}
+ Node scopeNode = getNode(finalScope);
// check overlap of excludedScopes and finalScope
List<String> mutableExcludedScopes = null;
@@ -549,12 +550,13 @@ public class NetworkTopologyImpl implements NetworkTopology {
mutableExcludedScopes = new ArrayList<>();
for (String s: excludedScopes) {
// excludeScope covers finalScope
- if (finalScope.startsWith(s)) {
+ if (scopeNode.isDescendant(s)) {
return null;
}
// excludeScope and finalScope share nothing case
- if (s.startsWith(finalScope)) {
- if (mutableExcludedScopes.stream().noneMatch(s::startsWith)) {
+ if (scopeNode.isAncestor(s)) {
+ if (mutableExcludedScopes.stream().
+ noneMatch(n -> getNode(s).isDescendant(n))) {
mutableExcludedScopes.add(s);
}
}
@@ -581,7 +583,6 @@ public class NetworkTopologyImpl implements NetworkTopology {
ancestorGen);
// calculate available node count
- Node scopeNode = getNode(finalScope);
int availableNodes = getAvailableNodesCount(
scopeNode.getNetworkFullPath(), mutableExcludedScopes, mutableExNodes,
ancestorGen);
@@ -746,13 +747,12 @@ public class NetworkTopologyImpl implements NetworkTopology {
return 0;
}
if (!CollectionUtils.isEmpty(mutableExcludedNodes)) {
- mutableExcludedNodes.removeIf(
- next -> !next.getNetworkFullPath().startsWith(scope));
+ mutableExcludedNodes.removeIf(next -> !next.isDescendant(scope));
}
List<Node> excludedAncestorList =
NetUtils.getAncestorList(this, mutableExcludedNodes, ancestorGen);
for (Node ancestor : excludedAncestorList) {
- if (scope.startsWith(ancestor.getNetworkFullPath())) {
+ if (ancestor.isAncestor(scope)) {
return 0;
}
}
@@ -762,9 +762,9 @@ public class NetworkTopologyImpl implements NetworkTopology {
for (String excludedScope: excludedScopes) {
Node excludedScopeNode = getNode(excludedScope);
if (excludedScopeNode != null) {
- if (excludedScope.startsWith(scope)) {
+ if (excludedScopeNode.isDescendant(scope)) {
excludedCount += excludedScopeNode.getNumOfLeaves();
- } else if (scope.startsWith(excludedScope)) {
+ } else if (excludedScopeNode.isAncestor(scope)) {
return 0;
}
}
@@ -780,7 +780,7 @@ public class NetworkTopologyImpl implements NetworkTopology {
}
} else {
for (Node ancestor : excludedAncestorList) {
- if (ancestor.getNetworkFullPath().startsWith(scope)) {
+ if (ancestor.isDescendant(scope)) {
excludedCount += ancestor.getNumOfLeaves();
}
}
diff --git a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/Node.java b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/Node.java
index 0007e54677..9884888a1d 100644
--- a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/Node.java
+++ b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/Node.java
@@ -98,4 +98,32 @@ public interface Node {
* @return true if this node is an ancestor of <i>n</i>
*/
boolean isAncestor(Node n);
+
+ /**
+ * Judge if this node is an ancestor of the node representing by the nodePath.
+ * Ancestor includes itself and parents case.
+ *
+ * @param nodePath the node path
+ * @return true if this node is an ancestor of <i>n</i>
+ */
+ boolean isAncestor(String nodePath);
+
+ /**
+ * Judge if this node is a descendant of node <i>n</i>.
+ * Descendant includes itself and all child generations.
+ *
+ * @param n a node
+ * @return true if this node is an descendant of <i>n</i>
+ */
+ boolean isDescendant(Node n);
+
+ /**
+ * Judge if this node is a descendant of the node representing by the
+ * nodePath.
+ * Descendant includes itself and all child generations.
+ *
+ * @param nodePath the scope
+ * @return true if this node is under a specific scope
+ */
+ boolean isDescendant(String nodePath);
}
diff --git a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NodeImpl.java b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NodeImpl.java
index 3a926fa71d..93a32b7913 100644
--- a/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NodeImpl.java
+++ b/hadoop-hdds/common/src/main/java/org/apache/hadoop/hdds/scm/net/NodeImpl.java
@@ -196,10 +196,37 @@ public class NodeImpl implements Node {
*/
@Override
public boolean isAncestor(Node node) {
+ if (node == null) {
+ return false;
+ }
+ return isAncestor(node.getNetworkFullPath());
+ }
+
+ @Override
+ public boolean isAncestor(String nodePath) {
+ if (nodePath == null) {
+ return false;
+ }
return this.getNetworkFullPath().equals(PATH_SEPARATOR_STR) ||
- node.getNetworkLocation().startsWith(this.getNetworkFullPath()) ||
- node.getNetworkFullPath().equalsIgnoreCase(
- this.getNetworkFullPath());
+ nodePath.equalsIgnoreCase(this.getNetworkFullPath()) ||
+ NetUtils.addSuffix(nodePath).startsWith(
+ NetUtils.addSuffix(this.getNetworkFullPath()));
+ }
+ @Override
+ public boolean isDescendant(Node node) {
+ if (node == null) {
+ return false;
+ }
+ return isDescendant(node.getNetworkFullPath());
+ }
+
+ @Override
+ public boolean isDescendant(String nodePath) {
+ if (nodePath == null) {
+ return false;
+ }
+ return NetUtils.addSuffix(this.getNetworkFullPath()).startsWith(
+ NetUtils.addSuffix(nodePath));
}
@Override
diff --git a/hadoop-hdds/common/src/test/java/org/apache/hadoop/hdds/scm/net/TestNetworkTopologyImpl.java b/hadoop-hdds/common/src/test/java/org/apache/hadoop/hdds/scm/net/TestNetworkTopologyImpl.java
index e50eca2e69..0a3251dd9b 100644
--- a/hadoop-hdds/common/src/test/java/org/apache/hadoop/hdds/scm/net/TestNetworkTopologyImpl.java
+++ b/hadoop-hdds/common/src/test/java/org/apache/hadoop/hdds/scm/net/TestNetworkTopologyImpl.java
@@ -32,6 +32,7 @@ import org.apache.hadoop.hdds.scm.ScmConfigKeys;
import static org.apache.hadoop.hdds.scm.net.NetConstants.DATACENTER_SCHEMA;
import static org.apache.hadoop.hdds.scm.net.NetConstants.LEAF_SCHEMA;
import static org.apache.hadoop.hdds.scm.net.NetConstants.NODEGROUP_SCHEMA;
+import static org.apache.hadoop.hdds.scm.net.NetConstants.NODE_COST_DEFAULT;
import static org.apache.hadoop.hdds.scm.net.NetConstants.PATH_SEPARATOR_STR;
import static org.apache.hadoop.hdds.scm.net.NetConstants.RACK_SCHEMA;
import static org.apache.hadoop.hdds.scm.net.NetConstants.REGION_SCHEMA;
@@ -44,6 +45,8 @@ import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import static org.junit.Assume.assumeTrue;
+
+import org.junit.Assert;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.Timeout;
@@ -189,6 +192,13 @@ public class TestNetworkTopologyImpl {
assertEquals(cluster.getNode(""), cluster.getNode("/"));
assertEquals(null, cluster.getNode("/switch1/node1"));
assertEquals(null, cluster.getNode("/switch1"));
+
+ if (cluster.getNode("/d1") != null) {
+ List<String> excludedScope = new ArrayList<>();
+ excludedScope.add("/d");
+ Node n = cluster.getNode(0, "/d1", excludedScope, null, null, 0);
+ assertNotNull(n);
+ }
}
@Test
@@ -410,7 +420,7 @@ public class TestNetworkTopologyImpl {
scope = "~" + path;
frequency = pickNodesAtRandom(100, scope, null, 0);
for (Node key : dataNodes) {
- if (key.getNetworkFullPath().startsWith(path)) {
+ if (key.isDescendant(path)) {
assertTrue(frequency.get(key) == 0);
}
}
@@ -544,8 +554,7 @@ public class TestNetworkTopologyImpl {
List<Node> ancestorList = NetUtils.getAncestorList(cluster,
excludedList, ancestorGen);
for (Node key : dataNodes) {
- if (excludedList.contains(key) ||
- key.getNetworkFullPath().startsWith(path) ||
+ if (excludedList.contains(key) || key.isDescendant(path) ||
(ancestorList.size() > 0 &&
ancestorList.stream()
.map(a -> (InnerNode) a)
@@ -650,8 +659,7 @@ public class TestNetworkTopologyImpl {
excludedList.contains(key)) {
continue;
} else if (pathList != null &&
- pathList.stream().anyMatch(path ->
- key.getNetworkFullPath().startsWith(path))) {
+ pathList.stream().anyMatch(key::isDescendant)) {
continue;
} else if (key.getNetworkFullPath().equals(
affinityNode.getNetworkFullPath())) {
@@ -905,6 +913,36 @@ public class TestNetworkTopologyImpl {
assertNull(chosenNode);
}
+ @Test
+ public void testIsAncestor() {
+ NodeImpl r1 = new NodeImpl("r1", "/", NODE_COST_DEFAULT);
+ NodeImpl r12 = new NodeImpl("r12", "/", NODE_COST_DEFAULT);
+ NodeImpl dc = new NodeImpl("dc", "/r12", NODE_COST_DEFAULT);
+ Assert.assertFalse(r1.isAncestor(dc));
+ Assert.assertFalse(r1.isAncestor("/r12/dc2"));
+ Assert.assertFalse(dc.isDescendant(r1));
+ Assert.assertFalse(dc.isDescendant("/r1"));
+
+ Assert.assertTrue(r12.isAncestor(dc));
+ Assert.assertTrue(r12.isAncestor("/r12/dc2"));
+ Assert.assertTrue(dc.isDescendant(r12));
+ Assert.assertTrue(dc.isDescendant("/r12"));
+ }
+
+ @Test
+ public void testGetLeafOnLeafParent() {
+ InnerNodeImpl root = new InnerNodeImpl("", "", null, 0, 0);
+ InnerNodeImpl r12 = new InnerNodeImpl("r12", "/", root, 1, 0);
+ InnerNodeImpl dc = new InnerNodeImpl("dc", "/r12", r12, 2, 0);
+ NodeImpl n1 = new NodeImpl("n1", "/r12/dc", dc, 2, 0);
+ dc.add(n1);
+
+ List<String> excludedScope = new ArrayList<>();
+ excludedScope.add("/r1");
+ Assert.assertFalse(n1.isDescendant("/r1"));
+ Assert.assertEquals(n1, dc.getLeaf(0, excludedScope, null, 0));
+ }
+
private static Node createDatanode(String name, String path) {
return new NodeImpl(name, path, NetConstants.NODE_COST_DEFAULT);
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@ozone.apache.org
For additional commands, e-mail: commits-help@ozone.apache.org