hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From st...@apache.org
Subject svn commit: r1344457 [2/2] - in /hbase/trunk: ./ hbase-server/ hbase-server/src/main/java/org/apache/hadoop/hbase/master/ hbase-server/src/main/java/org/apache/hadoop/hbase/master/balancer/ hbase-server/src/test/java/org/apache/hadoop/hbase/ hbase-serv...
Date Wed, 30 May 2012 20:53:16 GMT
Added: hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java?rev=1344457&view=auto
==============================================================================
--- hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java
(added)
+++ hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/BalancerTestBase.java
Wed May 30 20:53:15 2012
@@ -0,0 +1,223 @@
+/**
+ * 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.hbase.master.balancer;
+
+import static org.junit.Assert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Random;
+import java.util.SortedSet;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.ServerName;
+import org.apache.hadoop.hbase.master.RegionPlan;
+import org.apache.hadoop.hbase.util.Bytes;
+
+/**
+ * Class used to be the base of unit tests on load balancers. It gives helper
+ * methods to create maps of {@link ServerName} to lists of {@link HRegionInfo}
+ * and to check list of region plans.
+ *
+ */
+public class BalancerTestBase {
+
+  private static Random rand = new Random();
+  static int regionId = 0;
+
+  /**
+   * Invariant is that all servers have between floor(avg) and ceiling(avg)
+   * number of regions.
+   */
+  public void assertClusterAsBalanced(List<ServerAndLoad> servers) {
+    int numServers = servers.size();
+    int numRegions = 0;
+    int maxRegions = 0;
+    int minRegions = Integer.MAX_VALUE;
+    for (ServerAndLoad server : servers) {
+      int nr = server.getLoad();
+      if (nr > maxRegions) {
+        maxRegions = nr;
+      }
+      if (nr < minRegions) {
+        minRegions = nr;
+      }
+      numRegions += nr;
+    }
+    if (maxRegions - minRegions < 2) {
+      // less than 2 between max and min, can't balance
+      return;
+    }
+    int min = numRegions / numServers;
+    int max = numRegions % numServers == 0 ? min : min + 1;
+
+    for (ServerAndLoad server : servers) {
+      assertTrue(server.getLoad() >= 0);
+      assertTrue(server.getLoad() <= max);
+      assertTrue(server.getLoad() >= min);
+    }
+  }
+
+  protected String printStats(List<ServerAndLoad> servers) {
+    int numServers = servers.size();
+    int totalRegions = 0;
+    for (ServerAndLoad server : servers) {
+      totalRegions += server.getLoad();
+    }
+    float average = (float) totalRegions / numServers;
+    int max = (int) Math.ceil(average);
+    int min = (int) Math.floor(average);
+    return "[srvr=" + numServers + " rgns=" + totalRegions + " avg=" + average + " max="
+ max
+        + " min=" + min + "]";
+  }
+
+  protected List<ServerAndLoad> convertToList(final Map<ServerName, List<HRegionInfo>>
servers) {
+    List<ServerAndLoad> list = new ArrayList<ServerAndLoad>(servers.size());
+    for (Map.Entry<ServerName, List<HRegionInfo>> e : servers.entrySet()) {
+      list.add(new ServerAndLoad(e.getKey(), e.getValue().size()));
+    }
+    return list;
+  }
+
+  protected String printMock(List<ServerAndLoad> balancedCluster) {
+    SortedSet<ServerAndLoad> sorted = new TreeSet<ServerAndLoad>(balancedCluster);
+    ServerAndLoad[] arr = sorted.toArray(new ServerAndLoad[sorted.size()]);
+    StringBuilder sb = new StringBuilder(sorted.size() * 4 + 4);
+    sb.append("{ ");
+    for (int i = 0; i < arr.length; i++) {
+      if (i != 0) {
+        sb.append(" , ");
+      }
+      sb.append(arr[i].getServerName().getHostname());
+      sb.append(":");
+      sb.append(arr[i].getLoad());
+    }
+    sb.append(" }");
+    return sb.toString();
+  }
+
+  /**
+   * This assumes the RegionPlan HSI instances are the same ones in the map, so
+   * actually no need to even pass in the map, but I think it's clearer.
+   *
+   * @param list
+   * @param plans
+   * @return
+   */
+  protected List<ServerAndLoad> reconcile(List<ServerAndLoad> list, List<RegionPlan>
plans) {
+    List<ServerAndLoad> result = new ArrayList<ServerAndLoad>(list.size());
+    if (plans == null) return result;
+    Map<ServerName, ServerAndLoad> map = new HashMap<ServerName, ServerAndLoad>(list.size());
+    for (ServerAndLoad sl : list) {
+      map.put(sl.getServerName(), sl);
+    }
+    for (RegionPlan plan : plans) {
+      ServerName source = plan.getSource();
+      updateLoad(map, source, -1);
+      ServerName destination = plan.getDestination();
+      updateLoad(map, destination, +1);
+    }
+    result.clear();
+    result.addAll(map.values());
+    return result;
+  }
+
+  protected void updateLoad(final Map<ServerName, ServerAndLoad> map,
+                            final ServerName sn,
+                            final int diff) {
+    ServerAndLoad sal = map.get(sn);
+    if (sal == null) sal = new ServerAndLoad(sn, 0);
+    sal = new ServerAndLoad(sn, sal.getLoad() + diff);
+    map.put(sn, sal);
+  }
+
+  protected Map<ServerName, List<HRegionInfo>> mockClusterServers(int[] mockCluster)
{
+    int numServers = mockCluster.length;
+    Map<ServerName, List<HRegionInfo>> servers = new TreeMap<ServerName, List<HRegionInfo>>();
+    for (int i = 0; i < numServers; i++) {
+      int numRegions = mockCluster[i];
+      ServerAndLoad sal = randomServer(0);
+      List<HRegionInfo> regions = randomRegions(numRegions);
+      servers.put(sal.getServerName(), regions);
+    }
+    return servers;
+  }
+
+  private Queue<HRegionInfo> regionQueue = new LinkedList<HRegionInfo>();
+
+  protected List<HRegionInfo> randomRegions(int numRegions) {
+    List<HRegionInfo> regions = new ArrayList<HRegionInfo>(numRegions);
+    byte[] start = new byte[16];
+    byte[] end = new byte[16];
+    rand.nextBytes(start);
+    rand.nextBytes(end);
+    for (int i = 0; i < numRegions; i++) {
+      if (!regionQueue.isEmpty()) {
+        regions.add(regionQueue.poll());
+        continue;
+      }
+      Bytes.putInt(start, 0, numRegions << 1);
+      Bytes.putInt(end, 0, (numRegions << 1) + 1);
+      HRegionInfo hri = new HRegionInfo(Bytes.toBytes("table" + i), start, end, false, regionId++);
+      regions.add(hri);
+    }
+    return regions;
+  }
+
+  protected void returnRegions(List<HRegionInfo> regions) {
+    regionQueue.addAll(regions);
+  }
+
+  private Queue<ServerName> serverQueue = new LinkedList<ServerName>();
+
+  protected ServerAndLoad randomServer(final int numRegionsPerServer) {
+    if (!this.serverQueue.isEmpty()) {
+      ServerName sn = this.serverQueue.poll();
+      return new ServerAndLoad(sn, numRegionsPerServer);
+    }
+    String host = "srv" + rand.nextInt(100000);
+    int port = rand.nextInt(60000);
+    long startCode = rand.nextLong();
+    ServerName sn = new ServerName(host, port, startCode);
+    return new ServerAndLoad(sn, numRegionsPerServer);
+  }
+
+  protected List<ServerAndLoad> randomServers(int numServers, int numRegionsPerServer)
{
+    List<ServerAndLoad> servers = new ArrayList<ServerAndLoad>(numServers);
+    for (int i = 0; i < numServers; i++) {
+      servers.add(randomServer(numRegionsPerServer));
+    }
+    return servers;
+  }
+
+  protected void returnServer(ServerName server) {
+    serverQueue.add(server);
+  }
+
+  protected void returnServers(List<ServerName> servers) {
+    this.serverQueue.addAll(servers);
+  }
+
+}

Added: hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestBaseLoadBalancer.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestBaseLoadBalancer.java?rev=1344457&view=auto
==============================================================================
--- hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestBaseLoadBalancer.java
(added)
+++ hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestBaseLoadBalancer.java
Wed May 30 20:53:15 2012
@@ -0,0 +1,231 @@
+/**
+ * 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.hbase.master.balancer;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.hbase.HBaseConfiguration;
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.MediumTests;
+import org.apache.hadoop.hbase.ServerName;
+import org.apache.hadoop.hbase.master.LoadBalancer;
+import org.apache.hadoop.hbase.master.RegionPlan;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+@Category(MediumTests.class)
+public class TestBaseLoadBalancer extends BalancerTestBase {
+
+  private static LoadBalancer loadBalancer;
+  private static final Log LOG = LogFactory.getLog(TestStochasticLoadBalancer.class);
+
+  int[][] regionsAndServersMocks = new int[][] {
+      // { num regions, num servers }
+      new int[] { 0, 0 }, new int[] { 0, 1 }, new int[] { 1, 1 }, new int[] { 2, 1 },
+      new int[] { 10, 1 }, new int[] { 1, 2 }, new int[] { 2, 2 }, new int[] { 3, 2 },
+      new int[] { 1, 3 }, new int[] { 2, 3 }, new int[] { 3, 3 }, new int[] { 25, 3 },
+      new int[] { 2, 10 }, new int[] { 2, 100 }, new int[] { 12, 10 }, new int[] { 12, 100
}, };
+
+  @BeforeClass
+  public static void beforeAllTests() throws Exception {
+    Configuration conf = HBaseConfiguration.create();
+    loadBalancer = new MockBalancer();
+    loadBalancer.setConf(conf);
+  }
+
+  public static class MockBalancer extends BaseLoadBalancer {
+
+    @Override
+    public List<RegionPlan> balanceCluster(Map<ServerName, List<HRegionInfo>>
clusterState) {
+      return null;
+    }
+
+  }
+
+  /**
+   * Tests immediate assignment.
+   *
+   * Invariant is that all regions have an assignment.
+   *
+   * @throws Exception
+   */
+  @Test
+  public void testImmediateAssignment() throws Exception {
+    for (int[] mock : regionsAndServersMocks) {
+      LOG.debug("testImmediateAssignment with " + mock[0] + " regions and " + mock[1] + "
servers");
+      List<HRegionInfo> regions = randomRegions(mock[0]);
+      List<ServerAndLoad> servers = randomServers(mock[1], 0);
+      List<ServerName> list = getListOfServerNames(servers);
+      Map<HRegionInfo, ServerName> assignments = loadBalancer.immediateAssignment(regions,
list);
+      assertImmediateAssignment(regions, list, assignments);
+      returnRegions(regions);
+      returnServers(list);
+    }
+  }
+
+  /**
+   * All regions have an assignment.
+   * @param regions
+   * @param servers
+   * @param assignments
+   */
+  private void assertImmediateAssignment(List<HRegionInfo> regions, List<ServerName>
servers,
+      Map<HRegionInfo, ServerName> assignments) {
+    for (HRegionInfo region : regions) {
+      assertTrue(assignments.containsKey(region));
+    }
+  }
+
+  /**
+   * Tests the bulk assignment used during cluster startup.
+   *
+   * Round-robin. Should yield a balanced cluster so same invariant as the load
+   * balancer holds, all servers holding either floor(avg) or ceiling(avg).
+   *
+   * @throws Exception
+   */
+  @Test
+  public void testBulkAssignment() throws Exception {
+    for (int[] mock : regionsAndServersMocks) {
+      LOG.debug("testBulkAssignment with " + mock[0] + " regions and " + mock[1] + " servers");
+      List<HRegionInfo> regions = randomRegions(mock[0]);
+      List<ServerAndLoad> servers = randomServers(mock[1], 0);
+      List<ServerName> list = getListOfServerNames(servers);
+      Map<ServerName, List<HRegionInfo>> assignments =
+          loadBalancer.roundRobinAssignment(regions, list);
+      float average = (float) regions.size() / servers.size();
+      int min = (int) Math.floor(average);
+      int max = (int) Math.ceil(average);
+      if (assignments != null && !assignments.isEmpty()) {
+        for (List<HRegionInfo> regionList : assignments.values()) {
+          assertTrue(regionList.size() == min || regionList.size() == max);
+        }
+      }
+      returnRegions(regions);
+      returnServers(list);
+    }
+  }
+
+  /**
+   * Test the cluster startup bulk assignment which attempts to retain
+   * assignment info.
+   * @throws Exception
+   */
+  @Test
+  public void testRetainAssignment() throws Exception {
+    // Test simple case where all same servers are there
+    List<ServerAndLoad> servers = randomServers(10, 10);
+    List<HRegionInfo> regions = randomRegions(100);
+    Map<HRegionInfo, ServerName> existing = new TreeMap<HRegionInfo, ServerName>();
+    for (int i = 0; i < regions.size(); i++) {
+      ServerName sn = servers.get(i % servers.size()).getServerName();
+      // The old server would have had same host and port, but different
+      // start code!
+      ServerName snWithOldStartCode =
+          new ServerName(sn.getHostname(), sn.getPort(), sn.getStartcode() - 10);
+      existing.put(regions.get(i), snWithOldStartCode);
+    }
+    List<ServerName> listOfServerNames = getListOfServerNames(servers);
+    Map<ServerName, List<HRegionInfo>> assignment =
+        loadBalancer.retainAssignment(existing, listOfServerNames);
+    assertRetainedAssignment(existing, listOfServerNames, assignment);
+
+    // Include two new servers that were not there before
+    List<ServerAndLoad> servers2 = new ArrayList<ServerAndLoad>(servers);
+    servers2.add(randomServer(10));
+    servers2.add(randomServer(10));
+    listOfServerNames = getListOfServerNames(servers2);
+    assignment = loadBalancer.retainAssignment(existing, listOfServerNames);
+    assertRetainedAssignment(existing, listOfServerNames, assignment);
+
+    // Remove two of the servers that were previously there
+    List<ServerAndLoad> servers3 = new ArrayList<ServerAndLoad>(servers);
+    servers3.remove(0);
+    servers3.remove(0);
+    listOfServerNames = getListOfServerNames(servers3);
+    assignment = loadBalancer.retainAssignment(existing, listOfServerNames);
+    assertRetainedAssignment(existing, listOfServerNames, assignment);
+  }
+
+  private List<ServerName> getListOfServerNames(final List<ServerAndLoad> sals)
{
+    List<ServerName> list = new ArrayList<ServerName>();
+    for (ServerAndLoad e : sals) {
+      list.add(e.getServerName());
+    }
+    return list;
+  }
+
+  /**
+   * Asserts a valid retained assignment plan.
+   * <p>
+   * Must meet the following conditions:
+   * <ul>
+   * <li>Every input region has an assignment, and to an online server
+   * <li>If a region had an existing assignment to a server with the same
+   * address a a currently online server, it will be assigned to it
+   * </ul>
+   * @param existing
+   * @param servers
+   * @param assignment
+   */
+  private void assertRetainedAssignment(Map<HRegionInfo, ServerName> existing,
+      List<ServerName> servers, Map<ServerName, List<HRegionInfo>> assignment)
{
+    // Verify condition 1, every region assigned, and to online server
+    Set<ServerName> onlineServerSet = new TreeSet<ServerName>(servers);
+    Set<HRegionInfo> assignedRegions = new TreeSet<HRegionInfo>();
+    for (Map.Entry<ServerName, List<HRegionInfo>> a : assignment.entrySet())
{
+      assertTrue("Region assigned to server that was not listed as online",
+        onlineServerSet.contains(a.getKey()));
+      for (HRegionInfo r : a.getValue())
+        assignedRegions.add(r);
+    }
+    assertEquals(existing.size(), assignedRegions.size());
+
+    // Verify condition 2, if server had existing assignment, must have same
+    Set<String> onlineHostNames = new TreeSet<String>();
+    for (ServerName s : servers) {
+      onlineHostNames.add(s.getHostname());
+    }
+
+    for (Map.Entry<ServerName, List<HRegionInfo>> a : assignment.entrySet())
{
+      ServerName assignedTo = a.getKey();
+      for (HRegionInfo r : a.getValue()) {
+        ServerName address = existing.get(r);
+        if (address != null && onlineHostNames.contains(address.getHostname())) {
+          // this region was prevously assigned somewhere, and that
+          // host is still around, then it should be re-assigned on the
+          // same host
+          assertEquals(address.getHostname(), assignedTo.getHostname());
+        }
+      }
+    }
+  }
+
+}

Added: hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestDefaultLoadBalancer.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestDefaultLoadBalancer.java?rev=1344457&view=auto
==============================================================================
--- hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestDefaultLoadBalancer.java
(added)
+++ hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestDefaultLoadBalancer.java
Wed May 30 20:53:15 2012
@@ -0,0 +1,133 @@
+/**
+ * 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.hbase.master.balancer;
+
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.hbase.HBaseConfiguration;
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.MediumTests;
+import org.apache.hadoop.hbase.ServerName;
+import org.apache.hadoop.hbase.master.LoadBalancer;
+import org.apache.hadoop.hbase.master.RegionPlan;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+/**
+ * Test the load balancer that is created by default.
+ */
+@Category(MediumTests.class)
+public class TestDefaultLoadBalancer extends BalancerTestBase {
+  private static final Log LOG = LogFactory.getLog(TestDefaultLoadBalancer.class);
+
+  private static LoadBalancer loadBalancer;
+
+  @BeforeClass
+  public static void beforeAllTests() throws Exception {
+    Configuration conf = HBaseConfiguration.create();
+    conf.set("hbase.regions.slop", "0");
+    loadBalancer = new DefaultLoadBalancer();
+    loadBalancer.setConf(conf);
+  }
+
+  // int[testnum][servernumber] -> numregions
+  int[][] clusterStateMocks = new int[][] {
+      // 1 node
+      new int[] { 0 },
+      new int[] { 1 },
+      new int[] { 10 },
+      // 2 node
+      new int[] { 0, 0 },
+      new int[] { 2, 0 },
+      new int[] { 2, 1 },
+      new int[] { 2, 2 },
+      new int[] { 2, 3 },
+      new int[] { 2, 4 },
+      new int[] { 1, 1 },
+      new int[] { 0, 1 },
+      new int[] { 10, 1 },
+      new int[] { 14, 1432 },
+      new int[] { 47, 53 },
+      // 3 node
+      new int[] { 0, 1, 2 },
+      new int[] { 1, 2, 3 },
+      new int[] { 0, 2, 2 },
+      new int[] { 0, 3, 0 },
+      new int[] { 0, 4, 0 },
+      new int[] { 20, 20, 0 },
+      // 4 node
+      new int[] { 0, 1, 2, 3 },
+      new int[] { 4, 0, 0, 0 },
+      new int[] { 5, 0, 0, 0 },
+      new int[] { 6, 6, 0, 0 },
+      new int[] { 6, 2, 0, 0 },
+      new int[] { 6, 1, 0, 0 },
+      new int[] { 6, 0, 0, 0 },
+      new int[] { 4, 4, 4, 7 },
+      new int[] { 4, 4, 4, 8 },
+      new int[] { 0, 0, 0, 7 },
+      // 5 node
+      new int[] { 1, 1, 1, 1, 4 },
+      // more nodes
+      new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
+      new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 10 }, new int[] { 6, 6, 5, 6, 6, 6, 6, 6, 6,
1 },
+      new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 54 }, new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0,
55 },
+      new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 56 }, new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0,
16 },
+      new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 8 }, new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1,
9 },
+      new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 10 }, new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1,
123 },
+      new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 155 },
+      new int[] { 0, 0, 144, 1, 1, 1, 1, 1123, 133, 138, 12, 1444 },
+      new int[] { 0, 0, 144, 1, 0, 4, 1, 1123, 133, 138, 12, 1444 },
+      new int[] { 1538, 1392, 1561, 1557, 1535, 1553, 1385, 1542, 1619 } };
+
+  /**
+   * Test the load balancing algorithm.
+   *
+   * Invariant is that all servers should be hosting either floor(average) or
+   * ceiling(average)
+   *
+   * @throws Exception
+   */
+  @Test
+  public void testBalanceCluster() throws Exception {
+
+    for (int[] mockCluster : clusterStateMocks) {
+      Map<ServerName, List<HRegionInfo>> servers = mockClusterServers(mockCluster);
+      List<ServerAndLoad> list = convertToList(servers);
+      LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
+      List<RegionPlan> plans = loadBalancer.balanceCluster(servers);
+      List<ServerAndLoad> balancedCluster = reconcile(list, plans);
+      LOG.info("Mock Balance : " + printMock(balancedCluster));
+      assertClusterAsBalanced(balancedCluster);
+      for (Map.Entry<ServerName, List<HRegionInfo>> entry : servers.entrySet())
{
+        returnRegions(entry.getValue());
+        returnServer(entry.getKey());
+      }
+    }
+
+  }
+
+  @org.junit.Rule
+  public org.apache.hadoop.hbase.ResourceCheckerJUnitRule cu =
+      new org.apache.hadoop.hbase.ResourceCheckerJUnitRule();
+}

Added: hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java
URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java?rev=1344457&view=auto
==============================================================================
--- hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java
(added)
+++ hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/master/balancer/TestStochasticLoadBalancer.java
Wed May 30 20:53:15 2012
@@ -0,0 +1,183 @@
+/**
+ * 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.hbase.master.balancer;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.List;
+import java.util.Map;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.commons.math.stat.descriptive.DescriptiveStatistics;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.hbase.HBaseConfiguration;
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.MediumTests;
+import org.apache.hadoop.hbase.ServerName;
+import org.apache.hadoop.hbase.master.RegionPlan;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+@Category(MediumTests.class)
+public class TestStochasticLoadBalancer extends BalancerTestBase {
+  private static StochasticLoadBalancer loadBalancer;
+  private static final Log LOG = LogFactory.getLog(TestStochasticLoadBalancer.class);
+
+  @BeforeClass
+  public static void beforeAllTests() throws Exception {
+    Configuration conf = HBaseConfiguration.create();
+    loadBalancer = new StochasticLoadBalancer();
+    loadBalancer.setConf(conf);
+  }
+
+  // int[testnum][servernumber] -> numregions
+  int[][] clusterStateMocks = new int[][]{
+      // 1 node
+      new int[]{0},
+      new int[]{1},
+      new int[]{10},
+      // 2 node
+      new int[]{0, 0},
+      new int[]{2, 0},
+      new int[]{2, 1},
+      new int[]{2, 2},
+      new int[]{2, 3},
+      new int[]{2, 4},
+      new int[]{1, 1},
+      new int[]{0, 1},
+      new int[]{10, 1},
+      new int[]{514, 1432},
+      new int[]{47, 53},
+      // 3 node
+      new int[]{0, 1, 2},
+      new int[]{1, 2, 3},
+      new int[]{0, 2, 2},
+      new int[]{0, 3, 0},
+      new int[]{0, 4, 0},
+      new int[]{20, 20, 0},
+      // 4 node
+      new int[]{0, 1, 2, 3},
+      new int[]{4, 0, 0, 0},
+      new int[]{5, 0, 0, 0},
+      new int[]{6, 6, 0, 0},
+      new int[]{6, 2, 0, 0},
+      new int[]{6, 1, 0, 0},
+      new int[]{6, 0, 0, 0},
+      new int[]{4, 4, 4, 7},
+      new int[]{4, 4, 4, 8},
+      new int[]{0, 0, 0, 7},
+      // 5 node
+      new int[]{1, 1, 1, 1, 4},
+      // more nodes
+      new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
+      new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
+      new int[]{6, 6, 5, 6, 6, 6, 6, 6, 6, 1},
+      new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 54},
+      new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 55},
+      new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 56},
+      new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 16},
+      new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 8},
+      new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 9},
+      new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 10},
+      new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 123},
+      new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 155},
+  };
+
+  /**
+   * Test the load balancing algorithm.
+   *
+   * Invariant is that all servers should be hosting either floor(average) or
+   * ceiling(average)
+   *
+   * @throws Exception
+   */
+  @Test
+  public void testBalanceCluster() throws Exception {
+
+    for (int[] mockCluster : clusterStateMocks) {
+      Map<ServerName, List<HRegionInfo>> servers = mockClusterServers(mockCluster);
+      List<ServerAndLoad> list = convertToList(servers);
+      LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
+      List<RegionPlan> plans = loadBalancer.balanceCluster(servers);
+      List<ServerAndLoad> balancedCluster = reconcile(list, plans);
+      LOG.info("Mock Balance : " + printMock(balancedCluster));
+      assertClusterAsBalanced(balancedCluster);
+      for (Map.Entry<ServerName, List<HRegionInfo>> entry : servers.entrySet())
{
+        returnRegions(entry.getValue());
+        returnServer(entry.getKey());
+      }
+    }
+
+  }
+
+  @Test
+  public void testSkewCost() {
+    for (int[] mockCluster : clusterStateMocks) {
+      double cost = loadBalancer.computeSkewLoadCost(mockClusterServers(mockCluster));
+      assertTrue(cost >= 0);
+      assertTrue(cost <= 1.01);
+    }
+    assertEquals(1,
+      loadBalancer.computeSkewLoadCost(mockClusterServers(new int[] { 0, 0, 0, 0, 1 })),
0.01);
+    assertEquals(.75,
+      loadBalancer.computeSkewLoadCost(mockClusterServers(new int[] { 0, 0, 0, 1, 1 })),
0.01);
+    assertEquals(.5,
+      loadBalancer.computeSkewLoadCost(mockClusterServers(new int[] { 0, 0, 1, 1, 1 })),
0.01);
+    assertEquals(.25,
+      loadBalancer.computeSkewLoadCost(mockClusterServers(new int[] { 0, 1, 1, 1, 1 })),
0.01);
+    assertEquals(0,
+      loadBalancer.computeSkewLoadCost(mockClusterServers(new int[] { 1, 1, 1, 1, 1 })),
0.01);
+    assertEquals(0,
+        loadBalancer.computeSkewLoadCost(mockClusterServers(new int[] { 10, 10, 10, 10, 10
})), 0.01);
+  }
+
+  @Test
+  public void testTableSkewCost() {
+    for (int[] mockCluster : clusterStateMocks) {
+      double cost = loadBalancer.computeTableSkewLoadCost(mockClusterServers(mockCluster));
+      assertTrue(cost >= 0);
+      assertTrue(cost <= 1.01);
+    }
+  }
+
+  @Test
+  public void testCostFromStats() {
+    DescriptiveStatistics statOne = new DescriptiveStatistics();
+    for (int i =0; i < 100; i++) {
+      statOne.addValue(10);
+    }
+    assertEquals(0, loadBalancer.costFromStats(statOne), 0.01);
+
+    DescriptiveStatistics statTwo = new DescriptiveStatistics();
+    for (int i =0; i < 100; i++) {
+      statTwo.addValue(0);
+    }
+    statTwo.addValue(100);
+    assertEquals(1, loadBalancer.costFromStats(statTwo), 0.01);
+
+    DescriptiveStatistics statThree = new DescriptiveStatistics();
+    for (int i =0; i < 100; i++) {
+      statThree.addValue(0);
+      statThree.addValue(100);
+    }
+    assertEquals(0.5, loadBalancer.costFromStats(statThree), 0.01);
+  }
+}

Modified: hbase/trunk/pom.xml
URL: http://svn.apache.org/viewvc/hbase/trunk/pom.xml?rev=1344457&r1=1344456&r2=1344457&view=diff
==============================================================================
--- hbase/trunk/pom.xml (original)
+++ hbase/trunk/pom.xml Wed May 30 20:53:15 2012
@@ -795,6 +795,11 @@
         <version>${commons-logging.version}</version>
       </dependency>
       <dependency>
+        <groupId>org.apache.commons</groupId>
+        <artifactId>commons-math</artifactId>
+        <version>${commons-math.version}</version>
+      </dependency>
+      <dependency>
         <groupId>log4j</groupId>
         <artifactId>log4j</artifactId>
         <version>${log4j.version}</version>
@@ -1012,12 +1017,6 @@
         <version>${mockito-all.version}</version>
         <scope>test</scope>
       </dependency>
-      <dependency>
-        <groupId>org.apache.commons</groupId>
-        <artifactId>commons-math</artifactId>
-        <version>${commons-math.version}</version>
-        <scope>test</scope>
-      </dependency>
     </dependencies>
   </dependencyManagement>
 



Mime
View raw message