hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dhr...@apache.org
Subject svn commit: r619434 - in /hadoop/core/trunk: CHANGES.txt src/java/org/apache/hadoop/net/NetworkTopology.java src/test/org/apache/hadoop/net/TestNetworkTopology.java
Date Thu, 07 Feb 2008 14:54:34 GMT
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);
+      }
     }
   }
 }



Mime
View raw message