| /** |
| * 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.net; |
| |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.HashMap; |
| import java.util.List; |
| import java.util.Arrays; |
| |
| import org.apache.commons.lang3.tuple.Pair; |
| import org.apache.commons.math3.stat.inference.ChiSquareTest; |
| import org.apache.hadoop.conf.Configuration; |
| import org.junit.Assert; |
| import org.junit.Test; |
| |
| public class TestClusterTopology extends Assert { |
| |
| public static class NodeElement implements Node { |
| private String location; |
| private String name; |
| private Node parent; |
| private int level; |
| |
| public NodeElement(String name) { |
| this.name = name; |
| } |
| |
| @Override |
| public String getNetworkLocation() { |
| return location; |
| } |
| |
| @Override |
| public void setNetworkLocation(String location) { |
| this.location = location; |
| } |
| |
| @Override |
| public String getName() { |
| return name; |
| } |
| |
| @Override |
| public Node getParent() { |
| return parent; |
| } |
| |
| @Override |
| public void setParent(Node parent) { |
| this.parent = parent; |
| } |
| |
| @Override |
| public int getLevel() { |
| return level; |
| } |
| |
| @Override |
| public void setLevel(int i) { |
| this.level = i; |
| } |
| |
| } |
| |
| /** |
| * Test the count of nodes with exclude list |
| */ |
| @Test |
| public void testCountNumNodes() throws Exception { |
| // create the topology |
| NetworkTopology cluster = NetworkTopology.getInstance(new Configuration()); |
| NodeElement node1 = getNewNode("node1", "/d1/r1"); |
| cluster.add(node1); |
| NodeElement node2 = getNewNode("node2", "/d1/r2"); |
| cluster.add(node2); |
| NodeElement node3 = getNewNode("node3", "/d1/r3"); |
| cluster.add(node3); |
| NodeElement node4 = getNewNode("node4", "/d1/r4"); |
| cluster.add(node4); |
| // create exclude list |
| List<Node> excludedNodes = new ArrayList<Node>(); |
| |
| assertEquals("4 nodes should be available", 4, |
| cluster.countNumOfAvailableNodes(NodeBase.ROOT, excludedNodes)); |
| NodeElement deadNode = getNewNode("node5", "/d1/r2"); |
| excludedNodes.add(deadNode); |
| assertEquals("4 nodes should be available with extra excluded Node", 4, |
| cluster.countNumOfAvailableNodes(NodeBase.ROOT, excludedNodes)); |
| // add one existing node to exclude list |
| excludedNodes.add(node4); |
| assertEquals("excluded nodes with ROOT scope should be considered", 3, |
| cluster.countNumOfAvailableNodes(NodeBase.ROOT, excludedNodes)); |
| assertEquals("excluded nodes without ~ scope should be considered", 2, |
| cluster.countNumOfAvailableNodes("~" + deadNode.getNetworkLocation(), |
| excludedNodes)); |
| assertEquals("excluded nodes with rack scope should be considered", 1, |
| cluster.countNumOfAvailableNodes(deadNode.getNetworkLocation(), |
| excludedNodes)); |
| // adding the node in excluded scope to excluded list |
| excludedNodes.add(node2); |
| assertEquals("excluded nodes with ~ scope should be considered", 2, |
| cluster.countNumOfAvailableNodes("~" + deadNode.getNetworkLocation(), |
| excludedNodes)); |
| // getting count with non-exist scope. |
| assertEquals("No nodes should be considered for non-exist scope", 0, |
| cluster.countNumOfAvailableNodes("/non-exist", excludedNodes)); |
| // remove a node from the cluster |
| cluster.remove(node1); |
| assertEquals("1 node should be available", 1, |
| cluster.countNumOfAvailableNodes(NodeBase.ROOT, excludedNodes)); |
| } |
| |
| /** |
| * Test how well we pick random nodes. |
| */ |
| @Test |
| public void testChooseRandom() { |
| // create the topology |
| NetworkTopology cluster = NetworkTopology.getInstance(new Configuration()); |
| NodeElement node1 = getNewNode("node1", "/d1/r1"); |
| cluster.add(node1); |
| NodeElement node2 = getNewNode("node2", "/d1/r2"); |
| cluster.add(node2); |
| NodeElement node3 = getNewNode("node3", "/d1/r3"); |
| cluster.add(node3); |
| NodeElement node4 = getNewNode("node4", "/d1/r3"); |
| cluster.add(node4); |
| |
| // Number of test runs |
| int numTestRuns = 3; |
| int chiSquareTestRejectedCounter = 0; |
| |
| // Number of iterations to do the test |
| int numIterations = 100; |
| |
| for (int testRun = 0; testRun < numTestRuns; ++testRun) { |
| |
| // Pick random nodes |
| HashMap<String, Integer> histogram = new HashMap<String, Integer>(); |
| for (int i = 0; i < numIterations; i++) { |
| String randomNode = cluster.chooseRandom(NodeBase.ROOT).getName(); |
| if (!histogram.containsKey(randomNode)) { |
| histogram.put(randomNode, 0); |
| } |
| histogram.put(randomNode, histogram.get(randomNode) + 1); |
| } |
| assertEquals("Random is not selecting all nodes", 4, histogram.size()); |
| |
| // Check with 99% confidence alpha=0.01 as confidence = 100 * (1 - alpha) |
| ChiSquareTest chiSquareTest = new ChiSquareTest(); |
| double[] expected = new double[histogram.size()]; |
| long[] observed = new long[histogram.size()]; |
| int j = 0; |
| for (Integer occurrence : histogram.values()) { |
| expected[j] = 1.0 * numIterations / histogram.size(); |
| observed[j] = occurrence; |
| j++; |
| } |
| boolean chiSquareTestRejected = |
| chiSquareTest.chiSquareTest(expected, observed, 0.01); |
| |
| if (chiSquareTestRejected) { |
| ++chiSquareTestRejectedCounter; |
| } |
| } |
| |
| // Check that they have the proper distribution |
| assertFalse("Random not choosing nodes with proper distribution", |
| chiSquareTestRejectedCounter==3); |
| |
| // Pick random nodes excluding the 2 nodes in /d1/r3 |
| HashMap<String, Integer> histogram = new HashMap<String, Integer>(); |
| for (int i=0; i<numIterations; i++) { |
| String randomNode = cluster.chooseRandom("~/d1/r3").getName(); |
| if (!histogram.containsKey(randomNode)) { |
| histogram.put(randomNode, 0); |
| } |
| histogram.put(randomNode, histogram.get(randomNode) + 1); |
| } |
| assertEquals("Random is not selecting the nodes it should", |
| 2, histogram.size()); |
| |
| Node val = cluster.chooseRandom("/d1", "/d", Collections.emptyList()); |
| assertNotNull(val); |
| |
| } |
| |
| @Test |
| public void testChooseRandomExcluded() { |
| // create the topology |
| // a1 |
| // b1------|--------b2 |
| // | | |
| // c1-----|-----c2 c3 |
| // / \ | | |
| // / \ | | |
| // node1 node2 node3 node4 |
| |
| NetworkTopology cluster = NetworkTopology.getInstance(new Configuration()); |
| NodeElement node1 = getNewNode("node1", "/a1/b1/c1"); |
| cluster.add(node1); |
| NodeElement node2 = getNewNode("node2", "/a1/b1/c1"); |
| cluster.add(node2); |
| NodeElement node3 = getNewNode("node3", "/a1/b1/c2"); |
| cluster.add(node3); |
| NodeElement node4 = getNewNode("node4", "/a1/b2/c3"); |
| cluster.add(node4); |
| |
| Node node = cluster.chooseRandom("/a1/b1", "/a1/b1/c1", null); |
| assertSame("node3", node.getName()); |
| |
| node = cluster.chooseRandom("/a1/b1", "/a1/b1/c1", Arrays.asList(node1)); |
| assertSame("node3", node.getName()); |
| |
| node = cluster.chooseRandom("/a1/b1", "/a1/b1/c1", Arrays.asList(node3)); |
| assertNull(node); |
| |
| node = cluster.chooseRandom("/a1/b1", "/a1/b1/c1", Arrays.asList(node4)); |
| assertSame("node3", node.getName()); |
| } |
| |
| @Test |
| public void testNodeBaseNormalizeRemoveLeadingSlash() { |
| assertEquals("/d1", NodeBase.normalize("/d1///")); |
| assertEquals("/d1", NodeBase.normalize("/d1/")); |
| assertEquals("/d1", NodeBase.normalize("/d1")); |
| assertEquals("", NodeBase.normalize("///")); |
| assertEquals("", NodeBase.normalize("/")); |
| } |
| |
| private NodeElement getNewNode(String name, String rackLocation) { |
| NodeElement node = new NodeElement(name); |
| node.setNetworkLocation(rackLocation); |
| return node; |
| } |
| |
| private NodeElement getNewNode(NetworkTopology cluster, |
| String name, String rackLocation) { |
| NodeElement node = getNewNode(name, rackLocation); |
| cluster.add(node); |
| return node; |
| } |
| |
| @Test |
| @SuppressWarnings("unchecked") |
| public void testWeights() { |
| // create the topology |
| NetworkTopology cluster = NetworkTopology.getInstance(new Configuration()); |
| NodeElement node1 = getNewNode(cluster, "node1", "/r1"); |
| NodeElement node2 = getNewNode(cluster, "node2", "/r1"); |
| NodeElement node3 = getNewNode(cluster, "node3", "/r2"); |
| for (Pair<Integer, NodeElement> test: new Pair[]{Pair.of(0, node1), |
| Pair.of(2, node2), Pair.of(4, node3)}) { |
| int expect = test.getLeft(); |
| assertEquals(test.toString(), expect, cluster.getWeight(node1, test.getRight())); |
| assertEquals(test.toString(), expect, |
| cluster.getWeightUsingNetworkLocation(node1, test.getRight())); |
| } |
| // Reset so that we can have 2 levels |
| cluster = NetworkTopology.getInstance(new Configuration()); |
| NodeElement node5 = getNewNode(cluster, "node5", "/pod1/r1"); |
| NodeElement node6 = getNewNode(cluster, "node6", "/pod1/r1"); |
| NodeElement node7 = getNewNode(cluster, "node7", "/pod1/r2"); |
| NodeElement node8 = getNewNode(cluster, "node8", "/pod2/r3"); |
| for (Pair<Integer, NodeElement> test: new Pair[]{Pair.of(0, node5), |
| Pair.of(2, node6), Pair.of(4, node7), Pair.of(6, node8)}) { |
| int expect = test.getLeft(); |
| assertEquals(test.toString(), expect, cluster.getWeight(node5, test.getRight())); |
| assertEquals(test.toString(), expect, |
| cluster.getWeightUsingNetworkLocation(node5, test.getRight())); |
| } |
| } |
| } |