Author: dhruba
Date: Thu Feb 7 06:54:31 2008
New Revision: 619434
URL: http://svn.apache.org/viewvc?rev=619434&view=rev
Log:
HADOOP-2767. Fix for NetworkTopology erroneously skipping the last leaf
node on a rack. (Hairong Kuang and Mark Butler via dhruba)
Modified:
hadoop/core/trunk/CHANGES.txt
hadoop/core/trunk/src/java/org/apache/hadoop/net/NetworkTopology.java
hadoop/core/trunk/src/test/org/apache/hadoop/net/TestNetworkTopology.java
Modified: hadoop/core/trunk/CHANGES.txt
URL:
http://svn.apache.org/viewvc/hadoop/core/trunk/CHANGES.txt?rev=619434&r1=619433&r2=619434&view=diff
==============================================================================
--- hadoop/core/trunk/CHANGES.txt (original)
+++ hadoop/core/trunk/CHANGES.txt Thu Feb 7 06:54:31 2008
@@ -29,6 +29,9 @@
HADOOP-2194. dfs cat on a non-existent file throws FileNotFoundException.
(Mahadev Konar via dhruba)
+ HADOOP-2767. Fix for NetworkTopology erroneously skipping the last leaf
+ node on a rack. (Hairong Kuang and Mark Butler via dhruba)
+
Release 0.16.0 - 2008-02-07
INCOMPATIBLE CHANGES
Modified: hadoop/core/trunk/src/java/org/apache/hadoop/net/NetworkTopology.java
URL:
http://svn.apache.org/viewvc/hadoop/core/trunk/src/java/org/apache/hadoop/net/NetworkTopology.java?rev=619434&r1=619433&r2=619434&view=diff
==============================================================================
--- hadoop/core/trunk/src/java/org/apache/hadoop/net/NetworkTopology.java
(original)
+++ hadoop/core/trunk/src/java/org/apache/hadoop/net/NetworkTopology.java Thu
Feb 7 06:54:31 2008
@@ -90,7 +90,7 @@
/** Judge if this node is an ancestor of node <i>n</i>
*
- * @param n: a node
+ * @param n a node
* @return true if this node is an ancestor of <i>n</i>
*/
boolean isAncestor(Node n) {
@@ -101,7 +101,7 @@
/** Judge if this node is the parent of node <i>n</i>
*
- * @param n: a node
+ * @param n a node
* @return true if this node is the parent of <i>n</i>
*/
boolean isParent(Node n) {
@@ -173,7 +173,7 @@
}
/** Remove node <i>n</i> from the subtree of this node
- * @parameter n node to be deleted
+ * @param n node to be deleted
* @return true if the node is deleted; false otherwise
*/
boolean remove(Node n) {
@@ -241,30 +241,29 @@
}
}
- /** get <i>leaveIndex</i> leaf of this subtree
+ /** get <i>leafIndex</i> leaf of this subtree
* if it is not in the <i>excludedNode</i>*/
- private Node getLeaf(int leaveIndex, Node excludedNode) {
+ private Node getLeaf(int leafIndex, Node excludedNode) {
int count=0;
- int numOfExcludedLeaves = 1;
- if (excludedNode instanceof InnerNode) {
- numOfExcludedLeaves = ((InnerNode)excludedNode).getNumOfLeaves();
- }
+ // check if the excluded node a leaf
+ boolean isLeaf =
+ excludedNode == null || !(excludedNode instanceof InnerNode);
+ // calculate the total number of excluded leaf nodes
+ int numOfExcludedLeaves =
+ isLeaf ? 1 : ((InnerNode)excludedNode).getNumOfLeaves();
if (isRack()) { // children are leaves
+ if (isLeaf) { // excluded node is a leaf node
+ int excludedIndex = children.indexOf(excludedNode);
+ if (excludedIndex != -1 && leafIndex >= 0) {
+ // excluded node is one of the children so adjust the leaf index
+ leafIndex = leafIndex>=excludedIndex ? leafIndex+1 : leafIndex;
+ }
+ }
// range check
- if (leaveIndex<0 || leaveIndex>=this.getNumOfChildren()) {
+ if (leafIndex<0 || leafIndex>=this.getNumOfChildren()) {
return null;
}
- Node child = children.get(leaveIndex);
- if (excludedNode == null || excludedNode != child) {
- // child is not the excludedNode
- return child;
- } else { // child is the excludedNode so return the next child
- if (leaveIndex+1>=this.getNumOfChildren()) {
- return null;
- } else {
- return children.get(leaveIndex+1);
- }
- }
+ return children.get(leafIndex);
} else {
for(int i=0; i<children.size(); i++) {
InnerNode child = (InnerNode)children.get(i);
@@ -274,9 +273,9 @@
if (excludedNode != null && child.isAncestor(excludedNode)) {
numOfLeaves -= numOfExcludedLeaves;
}
- if (count+numOfLeaves > leaveIndex) {
+ if (count+numOfLeaves > leafIndex) {
// the leaf is in the child subtree
- return child.getLeaf(leaveIndex-count, excludedNode);
+ return child.getLeaf(leafIndex-count, excludedNode);
} else {
// go to the next child
count = count+numOfLeaves;
Modified:
hadoop/core/trunk/src/test/org/apache/hadoop/net/TestNetworkTopology.java
URL:
http://svn.apache.org/viewvc/hadoop/core/trunk/src/test/org/apache/hadoop/net/TestNetworkTopology.java?rev=619434&r1=619433&r2=619434&view=diff
==============================================================================
--- hadoop/core/trunk/src/test/org/apache/hadoop/net/TestNetworkTopology.java
(original)
+++ hadoop/core/trunk/src/test/org/apache/hadoop/net/TestNetworkTopology.java
Thu Feb 7 06:54:31 2008
@@ -19,9 +19,13 @@
package org.apache.hadoop.net;
+import java.util.HashMap;
+import java.util.Map;
+
+import junit.framework.TestCase;
+
import org.apache.hadoop.dfs.DatanodeDescriptor;
import org.apache.hadoop.dfs.DatanodeID;
-import junit.framework.TestCase;
public class TestNetworkTopology extends TestCase {
private final static NetworkTopology cluster = new NetworkTopology();
@@ -112,6 +116,56 @@
assertEquals(0, cluster.getNumOfLeaves());
for(int i=0; i<dataNodes.length; i++) {
cluster.add(dataNodes[i]);
+ }
+ }
+
+ /**
+ * This picks a large number of nodes at random in order to ensure coverage
+ *
+ * @param numNodes the number of nodes
+ * @param excludedScope the excluded scope
+ * @return the frequency that nodes were chosen
+ */
+ private Map<Node, Integer> pickNodesAtRandom(int numNodes,
+ String excludedScope) {
+ Map<Node, Integer> frequency = new HashMap<Node, Integer>();
+ for (DatanodeDescriptor dnd : dataNodes) {
+ frequency.put(dnd, 0);
+ }
+
+ for (int j = 0; j < numNodes; j++) {
+ Node random = cluster.chooseRandom(excludedScope);
+ frequency.put(random, frequency.get(random) + 1);
+ }
+ return frequency;
+ }
+
+ /**
+ * This test checks that chooseRandom works for an excluded node.
+ */
+ public void testChooseRandomExcludedNode() {
+ String scope = "~" + NodeBase.getPath(dataNodes[0]);
+ Map<Node, Integer> frequency = pickNodesAtRandom(100, scope);
+
+ for (Node key : dataNodes) {
+ // all nodes except the first should be more than zero
+ assertTrue(frequency.get(key) > 0 || key == dataNodes[0]);
+ }
+ }
+
+ /**
+ * This test checks that chooseRandom works for an excluded rack.
+ */
+ public void testChooseRandomExcludedRack() {
+ Map<Node, Integer> frequency = pickNodesAtRandom(100, "~" + "/d2");
+ // all the nodes on the second rack should be zero
+ for (int j = 0; j < dataNodes.length; j++) {
+ int freq = frequency.get(dataNodes[j]);
+ if (dataNodes[j].getNetworkLocation().startsWith("/d2")) {
+ assertEquals(0, freq);
+ } else {
+ assertTrue(freq > 0);
+ }
}
}
}
