You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by st...@apache.org on 2011/08/23 23:05:39 UTC

svn commit: r1160887 [1/2] - in /hbase/trunk: ./ src/main/java/org/apache/hadoop/hbase/master/ src/test/java/org/apache/hadoop/hbase/master/

Author: stack
Date: Tue Aug 23 21:05:38 2011
New Revision: 1160887

URL: http://svn.apache.org/viewvc?rev=1160887&view=rev
Log:
HBASE-4240 Allow Loadbalancer to be pluggable

Added:
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/DefaultLoadBalancer.java
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancerFactory.java
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/RegionPlan.java
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/ServerAndLoad.java
    hbase/trunk/src/test/java/org/apache/hadoop/hbase/master/TestDefaultLoadBalancer.java
Removed:
    hbase/trunk/src/test/java/org/apache/hadoop/hbase/master/TestLoadBalancer.java
Modified:
    hbase/trunk/CHANGES.txt
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/AssignmentManager.java
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/HMaster.java
    hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancer.java
    hbase/trunk/src/test/java/org/apache/hadoop/hbase/master/TestMasterFailover.java

Modified: hbase/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hbase/trunk/CHANGES.txt?rev=1160887&r1=1160886&r2=1160887&view=diff
==============================================================================
--- hbase/trunk/CHANGES.txt (original)
+++ hbase/trunk/CHANGES.txt Tue Aug 23 21:05:38 2011
@@ -395,6 +395,7 @@ Release 0.91.0 - Unreleased
    HBASE-4237  Directly remove the call being handled from the map of outstanding RPCs
                (Benoit Sigoure)
    HBASE-4199  blockCache summary - backend (Doug Meil)
+   HBASE-4240  Allow Loadbalancer to be pluggable
 
   TASKS
    HBASE-3559  Move report of split to master OFF the heartbeat channel

Modified: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/AssignmentManager.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/AssignmentManager.java?rev=1160887&r1=1160886&r2=1160887&view=diff
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/AssignmentManager.java (original)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/AssignmentManager.java Tue Aug 23 21:05:38 2011
@@ -59,7 +59,7 @@ import org.apache.hadoop.hbase.executor.
 import org.apache.hadoop.hbase.executor.EventHandler.EventType;
 import org.apache.hadoop.hbase.regionserver.RegionOpeningState;
 import org.apache.hadoop.hbase.ipc.ServerNotRunningYetException;
-import org.apache.hadoop.hbase.master.LoadBalancer.RegionPlan;
+import org.apache.hadoop.hbase.master.RegionPlan;
 import org.apache.hadoop.hbase.master.handler.ClosedRegionHandler;
 import org.apache.hadoop.hbase.master.handler.DisableTableHandler;
 import org.apache.hadoop.hbase.master.handler.EnableTableHandler;
@@ -101,6 +101,8 @@ public class AssignmentManager extends Z
 
   private TimeoutMonitor timeoutMonitor;
 
+  private LoadBalancer balancer;
+
   /*
    * Maximum times we recurse an assignment.  See below in {@link #assign()}.
    */
@@ -172,6 +174,7 @@ public class AssignmentManager extends Z
     this.zkTable = new ZKTable(this.master.getZooKeeper());
     this.maximumAssignmentAttempts =
       this.master.getConfiguration().getInt("hbase.assignment.maximum.attempts", 10);
+    this.balancer = LoadBalancerFactory.getLoadBalancer(conf);
   }
 
   /**
@@ -1364,7 +1367,7 @@ public class AssignmentManager extends Z
     if (serverToExclude != null) servers.remove(serverToExclude);
     if (servers.isEmpty()) return null;
     RegionPlan randomPlan = new RegionPlan(state.getRegion(), null,
-      LoadBalancer.randomAssignment(servers));
+      balancer.randomAssignment(servers));
     boolean newPlan = false;
     RegionPlan existingPlan = null;
     synchronized (this.regionPlans) {
@@ -1564,7 +1567,7 @@ public class AssignmentManager extends Z
       return;
     Map<ServerName, List<HRegionInfo>> bulkPlan = null;
     // Generate a round-robin bulk assignment plan
-    bulkPlan = LoadBalancer.roundRobinAssignment(regions, servers);
+    bulkPlan = balancer.roundRobinAssignment(regions, servers);
     LOG.info("Bulk assigning " + regions.size() + " region(s) round-robin across " +
                servers.size() + " server(s)");
     // Use fixed count thread pool assigning.
@@ -1598,7 +1601,7 @@ public class AssignmentManager extends Z
     Map<ServerName, List<HRegionInfo>> bulkPlan = null;
     if (retainAssignment) {
       // Reuse existing assignment info
-      bulkPlan = LoadBalancer.retainAssignment(allRegions, servers);
+      bulkPlan = balancer.retainAssignment(allRegions, servers);
     } else {
       // assign regions in round-robin fashion
       assignUserRegions(new ArrayList<HRegionInfo>(allRegions.keySet()), servers);

Added: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/DefaultLoadBalancer.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/DefaultLoadBalancer.java?rev=1160887&view=auto
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/DefaultLoadBalancer.java (added)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/DefaultLoadBalancer.java Tue Aug 23 21:05:38 2011
@@ -0,0 +1,723 @@
+/**
+ * Copyright 2011 The Apache Software Foundation
+ *
+ * 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;
+
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.Random;
+import java.util.TreeMap;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.hbase.ClusterStatus;
+import org.apache.hadoop.hbase.HDFSBlocksDistribution;
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.HTableDescriptor;
+import org.apache.hadoop.hbase.ServerName;
+import org.apache.hadoop.hbase.TableExistsException;
+import org.apache.hadoop.hbase.regionserver.HRegion;
+import org.apache.hadoop.hbase.util.Bytes;
+
+import com.google.common.collect.MinMaxPriorityQueue;
+
+/**
+ * Makes decisions about the placement and movement of Regions across
+ * RegionServers.
+ *
+ * <p>Cluster-wide load balancing will occur only when there are no regions in
+ * transition and according to a fixed period of a time using {@link #balanceCluster(Map)}.
+ *
+ * <p>Inline region placement with {@link #immediateAssignment} can be used when
+ * the Master needs to handle closed regions that it currently does not have
+ * a destination set for.  This can happen during master failover.
+ *
+ * <p>On cluster startup, bulk assignment can be used to determine
+ * locations for all Regions in a cluster.
+ *
+ * <p>This classes produces plans for the {@link AssignmentManager} to execute.
+ */
+public class DefaultLoadBalancer implements LoadBalancer {
+  private static final Log LOG = LogFactory.getLog(LoadBalancer.class);
+  private static final Random RANDOM = new Random(System.currentTimeMillis());
+  // slop for regions
+  private float slop;
+  private Configuration config;
+  private ClusterStatus status;
+  private MasterServices services;
+
+  public void setClusterStatus(ClusterStatus st) {
+    this.status = st;
+  }
+
+  public void setMasterServices(MasterServices masterServices) {
+    this.services = masterServices;
+  }
+
+  @Override
+  public void setConf(Configuration conf) {
+    this.slop = conf.getFloat("hbase.regions.slop", (float) 0.2);
+    if (slop < 0) slop = 0;
+    else if (slop > 1) slop = 1;
+    this.config = conf;
+  }
+
+  @Override
+  public Configuration getConf() {
+    return this.config;
+  }
+
+  /*
+  * The following comparator assumes that RegionId from HRegionInfo can
+  * represent the age of the region - larger RegionId means the region
+  * is younger.
+  * This comparator is used in balanceCluster() to account for the out-of-band
+  * regions which were assigned to the server after some other region server
+  * crashed.
+  */
+   private class RegionInfoComparator implements Comparator<HRegionInfo> {
+       @Override
+       public int compare(HRegionInfo l, HRegionInfo r) {
+          long diff = r.getRegionId() - l.getRegionId();
+          if (diff < 0) return -1;
+          if (diff > 0) return 1;
+          return 0;
+       }
+   }
+
+
+   RegionInfoComparator riComparator = new RegionInfoComparator();
+   
+   private class RegionPlanComparator implements Comparator<RegionPlan> {
+    @Override
+    public int compare(RegionPlan l, RegionPlan r) {
+      long diff = r.getRegionInfo().getRegionId() - l.getRegionInfo().getRegionId();
+      if (diff < 0) return -1;
+      if (diff > 0) return 1;
+      return 0;
+    }
+  }
+
+  RegionPlanComparator rpComparator = new RegionPlanComparator();
+
+  /**
+   * Generate a global load balancing plan according to the specified map of
+   * server information to the most loaded regions of each server.
+   *
+   * The load balancing invariant is that all servers are within 1 region of the
+   * average number of regions per server.  If the average is an integer number,
+   * all servers will be balanced to the average.  Otherwise, all servers will
+   * have either floor(average) or ceiling(average) regions.
+   *
+   * HBASE-3609 Modeled regionsToMove using Guava's MinMaxPriorityQueue so that
+   *   we can fetch from both ends of the queue. 
+   * At the beginning, we check whether there was empty region server 
+   *   just discovered by Master. If so, we alternately choose new / old
+   *   regions from head / tail of regionsToMove, respectively. This alternation
+   *   avoids clustering young regions on the newly discovered region server.
+   *   Otherwise, we choose new regions from head of regionsToMove.
+   *   
+   * Another improvement from HBASE-3609 is that we assign regions from
+   *   regionsToMove to underloaded servers in round-robin fashion.
+   *   Previously one underloaded server would be filled before we move onto
+   *   the next underloaded server, leading to clustering of young regions.
+   *   
+   * Finally, we randomly shuffle underloaded servers so that they receive
+   *   offloaded regions relatively evenly across calls to balanceCluster().
+   *         
+   * The algorithm is currently implemented as such:
+   *
+   * <ol>
+   * <li>Determine the two valid numbers of regions each server should have,
+   *     <b>MIN</b>=floor(average) and <b>MAX</b>=ceiling(average).
+   *
+   * <li>Iterate down the most loaded servers, shedding regions from each so
+   *     each server hosts exactly <b>MAX</b> regions.  Stop once you reach a
+   *     server that already has &lt;= <b>MAX</b> regions.
+   *     <p>
+   *     Order the regions to move from most recent to least.
+   *
+   * <li>Iterate down the least loaded servers, assigning regions so each server
+   *     has exactly </b>MIN</b> regions.  Stop once you reach a server that
+   *     already has &gt;= <b>MIN</b> regions.
+   *
+   *     Regions being assigned to underloaded servers are those that were shed
+   *     in the previous step.  It is possible that there were not enough
+   *     regions shed to fill each underloaded server to <b>MIN</b>.  If so we
+   *     end up with a number of regions required to do so, <b>neededRegions</b>.
+   *
+   *     It is also possible that we were able to fill each underloaded but ended
+   *     up with regions that were unassigned from overloaded servers but that
+   *     still do not have assignment.
+   *
+   *     If neither of these conditions hold (no regions needed to fill the
+   *     underloaded servers, no regions leftover from overloaded servers),
+   *     we are done and return.  Otherwise we handle these cases below.
+   *
+   * <li>If <b>neededRegions</b> is non-zero (still have underloaded servers),
+   *     we iterate the most loaded servers again, shedding a single server from
+   *     each (this brings them from having <b>MAX</b> regions to having
+   *     <b>MIN</b> regions).
+   *
+   * <li>We now definitely have more regions that need assignment, either from
+   *     the previous step or from the original shedding from overloaded servers.
+   *     Iterate the least loaded servers filling each to <b>MIN</b>.
+   *
+   * <li>If we still have more regions that need assignment, again iterate the
+   *     least loaded servers, this time giving each one (filling them to
+   *     </b>MAX</b>) until we run out.
+   *
+   * <li>All servers will now either host <b>MIN</b> or <b>MAX</b> regions.
+   *
+   *     In addition, any server hosting &gt;= <b>MAX</b> regions is guaranteed
+   *     to end up with <b>MAX</b> regions at the end of the balancing.  This
+   *     ensures the minimal number of regions possible are moved.
+   * </ol>
+   *
+   * TODO: We can at-most reassign the number of regions away from a particular
+   *       server to be how many they report as most loaded.
+   *       Should we just keep all assignment in memory?  Any objections?
+   *       Does this mean we need HeapSize on HMaster?  Or just careful monitor?
+   *       (current thinking is we will hold all assignments in memory)
+   *
+   * @param clusterState Map of regionservers and their load/region information to
+   *                   a list of their most loaded regions
+   * @return a list of regions to be moved, including source and destination,
+   *         or null if cluster is already balanced
+   */
+  public List<RegionPlan> balanceCluster(
+      Map<ServerName, List<HRegionInfo>> clusterState) {
+    boolean emptyRegionServerPresent = false;
+    long startTime = System.currentTimeMillis();
+
+    int numServers = clusterState.size();
+    if (numServers == 0) {
+      LOG.debug("numServers=0 so skipping load balancing");
+      return null;
+    }
+    NavigableMap<ServerAndLoad, List<HRegionInfo>> serversByLoad =
+      new TreeMap<ServerAndLoad, List<HRegionInfo>>();
+    int numRegions = 0;
+    StringBuilder strBalanceParam = new StringBuilder("Server information: ");
+    // Iterate so we can count regions as we build the map
+    for (Map.Entry<ServerName, List<HRegionInfo>> server: clusterState.entrySet()) {
+      List<HRegionInfo> regions = server.getValue();
+      int sz = regions.size();
+      if (sz == 0) emptyRegionServerPresent = true;
+      numRegions += sz;
+      serversByLoad.put(new ServerAndLoad(server.getKey(), sz), regions);
+      strBalanceParam.append(server.getKey().getServerName()).append("=").
+        append(server.getValue().size()).append(", ");
+    }
+    strBalanceParam.delete(strBalanceParam.length() - 2,
+      strBalanceParam.length());
+    LOG.debug(strBalanceParam.toString());
+
+    // Check if we even need to do any load balancing
+    float average = (float)numRegions / numServers; // for logging
+    // HBASE-3681 check sloppiness first
+    int floor = (int) Math.floor(average * (1 - slop));
+    int ceiling = (int) Math.ceil(average * (1 + slop));
+    if (serversByLoad.lastKey().getLoad() <= ceiling &&
+       serversByLoad.firstKey().getLoad() >= floor) {
+      // Skipped because no server outside (min,max) range
+      LOG.info("Skipping load balancing because balanced cluster; " +
+        "servers=" + numServers + " " +
+        "regions=" + numRegions + " average=" + average + " " +
+        "mostloaded=" + serversByLoad.lastKey().getLoad() +
+        " leastloaded=" + serversByLoad.firstKey().getLoad());
+      return null;
+    }
+    int min = numRegions / numServers;
+    int max = numRegions % numServers == 0 ? min : min + 1;
+
+    // Using to check banance result.
+    strBalanceParam.delete(0, strBalanceParam.length());
+    strBalanceParam.append("Balance parameter: numRegions=").append(numRegions)
+        .append(", numServers=").append(numServers).append(", max=").append(max)
+        .append(", min=").append(min);
+    LOG.debug(strBalanceParam.toString());
+    
+    // Balance the cluster
+    // TODO: Look at data block locality or a more complex load to do this
+    MinMaxPriorityQueue<RegionPlan> regionsToMove =
+      MinMaxPriorityQueue.orderedBy(rpComparator).create();
+    List<RegionPlan> regionsToReturn = new ArrayList<RegionPlan>();
+
+    // Walk down most loaded, pruning each to the max
+    int serversOverloaded = 0;
+    // flag used to fetch regions from head and tail of list, alternately
+    boolean fetchFromTail = false;
+    Map<ServerName, BalanceInfo> serverBalanceInfo =
+      new TreeMap<ServerName, BalanceInfo>();
+    for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server:
+        serversByLoad.descendingMap().entrySet()) {
+      ServerAndLoad sal = server.getKey();
+      int regionCount = sal.getLoad();
+      if (regionCount <= max) {
+        serverBalanceInfo.put(sal.getServerName(), new BalanceInfo(0, 0));
+        break;
+      }
+      serversOverloaded++;
+      List<HRegionInfo> regions = server.getValue();
+      int numToOffload = Math.min(regionCount - max, regions.size());
+      // account for the out-of-band regions which were assigned to this server
+      // after some other region server crashed 
+      Collections.sort(regions, riComparator);
+      int numTaken = 0;
+      for (int i = 0; i <= numToOffload; ) {
+        HRegionInfo hri = regions.get(i); // fetch from head
+        if (fetchFromTail) {
+          hri = regions.get(regions.size() - 1 - i);
+        }
+        i++;
+        // Don't rebalance meta regions.
+        if (hri.isMetaRegion()) continue;
+        regionsToMove.add(new RegionPlan(hri, sal.getServerName(), null));
+        numTaken++;
+        if (numTaken >= numToOffload) break;
+        // fetch in alternate order if there is new region server
+        if (emptyRegionServerPresent) {
+          fetchFromTail = !fetchFromTail;
+        }
+      }
+      serverBalanceInfo.put(sal.getServerName(),
+        new BalanceInfo(numToOffload, (-1)*numTaken));
+    }
+    int totalNumMoved = regionsToMove.size();
+
+    // Walk down least loaded, filling each to the min
+    int neededRegions = 0; // number of regions needed to bring all up to min
+    fetchFromTail = false;
+
+    Map<ServerName, Integer> underloadedServers = new HashMap<ServerName, Integer>();
+    for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server:
+        serversByLoad.entrySet()) {
+      int regionCount = server.getKey().getLoad();
+      if (regionCount >= min) {
+        break;
+      }
+      underloadedServers.put(server.getKey().getServerName(), min - regionCount);
+    }
+    // number of servers that get new regions
+    int serversUnderloaded = underloadedServers.size();
+    int incr = 1;
+    List<ServerName> sns =
+      Arrays.asList(underloadedServers.keySet().toArray(new ServerName[serversUnderloaded]));
+    Collections.shuffle(sns, RANDOM);
+    while (regionsToMove.size() > 0) {
+      int cnt = 0;
+      int i = incr > 0 ? 0 : underloadedServers.size()-1;
+      for (; i >= 0 && i < underloadedServers.size(); i += incr) {
+        if (regionsToMove.isEmpty()) break;
+        ServerName si = sns.get(i);
+        int numToTake = underloadedServers.get(si);
+        if (numToTake == 0) continue;
+
+        addRegionPlan(regionsToMove, fetchFromTail, si, regionsToReturn);
+        if (emptyRegionServerPresent) {
+          fetchFromTail = !fetchFromTail;
+        }
+
+        underloadedServers.put(si, numToTake-1);
+        cnt++;
+        BalanceInfo bi = serverBalanceInfo.get(si);
+        if (bi == null) {
+          bi = new BalanceInfo(0, 0);
+          serverBalanceInfo.put(si, bi);
+        }
+        bi.setNumRegionsAdded(bi.getNumRegionsAdded()+1);
+      }
+      if (cnt == 0) break;
+      // iterates underloadedServers in the other direction
+      incr = -incr;
+    }
+    for (Integer i : underloadedServers.values()) {
+      // If we still want to take some, increment needed
+      neededRegions += i;
+    }
+
+    // If none needed to fill all to min and none left to drain all to max,
+    // we are done
+    if (neededRegions == 0 && regionsToMove.isEmpty()) {
+      long endTime = System.currentTimeMillis();
+      LOG.info("Calculated a load balance in " + (endTime-startTime) + "ms. " +
+          "Moving " + totalNumMoved + " regions off of " +
+          serversOverloaded + " overloaded servers onto " +
+          serversUnderloaded + " less loaded servers");
+      return regionsToReturn;
+    }
+
+    // Need to do a second pass.
+    // Either more regions to assign out or servers that are still underloaded
+
+    // If we need more to fill min, grab one from each most loaded until enough
+    if (neededRegions != 0) {
+      // Walk down most loaded, grabbing one from each until we get enough
+      for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server :
+        serversByLoad.descendingMap().entrySet()) {
+        BalanceInfo balanceInfo =
+          serverBalanceInfo.get(server.getKey().getServerName());
+        int idx =
+          balanceInfo == null ? 0 : balanceInfo.getNextRegionForUnload();
+        if (idx >= server.getValue().size()) break;
+        HRegionInfo region = server.getValue().get(idx);
+        if (region.isMetaRegion()) continue; // Don't move meta regions.
+        regionsToMove.add(new RegionPlan(region, server.getKey().getServerName(), null));
+        totalNumMoved++;
+        if (--neededRegions == 0) {
+          // No more regions needed, done shedding
+          break;
+        }
+      }
+    }
+
+    // Now we have a set of regions that must be all assigned out
+    // Assign each underloaded up to the min, then if leftovers, assign to max
+
+    // Walk down least loaded, assigning to each to fill up to min
+    for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server :
+        serversByLoad.entrySet()) {
+      int regionCount = server.getKey().getLoad();
+      if (regionCount >= min) break;
+      BalanceInfo balanceInfo = serverBalanceInfo.get(server.getKey().getServerName());
+      if(balanceInfo != null) {
+        regionCount += balanceInfo.getNumRegionsAdded();
+      }
+      if(regionCount >= min) {
+        continue;
+      }
+      int numToTake = min - regionCount;
+      int numTaken = 0;
+      while(numTaken < numToTake && 0 < regionsToMove.size()) {
+        addRegionPlan(regionsToMove, fetchFromTail,
+          server.getKey().getServerName(), regionsToReturn);
+        numTaken++;
+        if (emptyRegionServerPresent) {
+          fetchFromTail = !fetchFromTail;
+        }
+      }
+    }
+
+    // If we still have regions to dish out, assign underloaded to max
+    if (0 < regionsToMove.size()) {
+      for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server :
+        serversByLoad.entrySet()) {
+        int regionCount = server.getKey().getLoad();
+        if(regionCount >= max) {
+          break;
+        }
+        addRegionPlan(regionsToMove, fetchFromTail,
+          server.getKey().getServerName(), regionsToReturn);
+        if (emptyRegionServerPresent) {
+          fetchFromTail = !fetchFromTail;
+        }
+        if (regionsToMove.isEmpty()) {
+          break;
+        }
+      }
+    }
+
+    long endTime = System.currentTimeMillis();
+
+    if (!regionsToMove.isEmpty() || neededRegions != 0) {
+      // Emit data so can diagnose how balancer went astray.
+      LOG.warn("regionsToMove=" + totalNumMoved +
+        ", numServers=" + numServers + ", serversOverloaded=" + serversOverloaded +
+        ", serversUnderloaded=" + serversUnderloaded);
+      StringBuilder sb = new StringBuilder();
+      for (Map.Entry<ServerName, List<HRegionInfo>> e: clusterState.entrySet()) {
+        if (sb.length() > 0) sb.append(", ");
+        sb.append(e.getKey().toString());
+        sb.append(" ");
+        sb.append(e.getValue().size());
+      }
+      LOG.warn("Input " + sb.toString());
+    }
+
+    // All done!
+    LOG.info("Done. Calculated a load balance in " + (endTime-startTime) + "ms. " +
+        "Moving " + totalNumMoved + " regions off of " +
+        serversOverloaded + " overloaded servers onto " +
+        serversUnderloaded + " less loaded servers");
+
+    return regionsToReturn;
+  }
+
+  /**
+   * Add a region from the head or tail to the List of regions to return.
+   */
+  void addRegionPlan(final MinMaxPriorityQueue<RegionPlan> regionsToMove,
+      final boolean fetchFromTail, final ServerName sn, List<RegionPlan> regionsToReturn) {
+    RegionPlan rp = null;
+    if (!fetchFromTail) rp = regionsToMove.remove();
+    else rp = regionsToMove.removeLast();
+    rp.setDestination(sn);
+    regionsToReturn.add(rp);
+  }
+
+  /**
+   * Stores additional per-server information about the regions added/removed
+   * during the run of the balancing algorithm.
+   *
+   * For servers that shed regions, we need to track which regions we have
+   * already shed.  <b>nextRegionForUnload</b> contains the index in the list
+   * of regions on the server that is the next to be shed.
+   */
+  private static class BalanceInfo {
+
+    private final int nextRegionForUnload;
+    private int numRegionsAdded;
+
+    public BalanceInfo(int nextRegionForUnload, int numRegionsAdded) {
+      this.nextRegionForUnload = nextRegionForUnload;
+      this.numRegionsAdded = numRegionsAdded;
+    }
+
+    public int getNextRegionForUnload() {
+      return nextRegionForUnload;
+    }
+
+    public int getNumRegionsAdded() {
+      return numRegionsAdded;
+    }
+
+    public void setNumRegionsAdded(int numAdded) {
+      this.numRegionsAdded = numAdded;
+    }
+  }
+
+  /**
+   * Generates a bulk assignment plan to be used on cluster startup using a
+   * simple round-robin assignment.
+   * <p>
+   * Takes a list of all the regions and all the servers in the cluster and
+   * returns a map of each server to the regions that it should be assigned.
+   * <p>
+   * Currently implemented as a round-robin assignment.  Same invariant as
+   * load balancing, all servers holding floor(avg) or ceiling(avg).
+   *
+   * TODO: Use block locations from HDFS to place regions with their blocks
+   *
+   * @param regions all regions
+   * @param servers all servers
+   * @return map of server to the regions it should take, or null if no
+   *         assignment is possible (ie. no regions or no servers)
+   */
+  public Map<ServerName, List<HRegionInfo>> roundRobinAssignment(
+      List<HRegionInfo> regions, List<ServerName> servers) {
+    if (regions.isEmpty() || servers.isEmpty()) {
+      return null;
+    }
+    Map<ServerName, List<HRegionInfo>> assignments =
+      new TreeMap<ServerName,List<HRegionInfo>>();
+    int numRegions = regions.size();
+    int numServers = servers.size();
+    int max = (int)Math.ceil((float)numRegions/numServers);
+    int serverIdx = 0;
+    if (numServers > 1) {
+      serverIdx = RANDOM.nextInt(numServers);
+    }
+    int regionIdx = 0;
+    for (int j = 0; j < numServers; j++) {
+      ServerName server = servers.get((j + serverIdx) % numServers);
+      List<HRegionInfo> serverRegions = new ArrayList<HRegionInfo>(max);
+      for (int i=regionIdx; i<numRegions; i += numServers) {
+        serverRegions.add(regions.get(i % numRegions));
+      }
+      assignments.put(server, serverRegions);
+      regionIdx++;
+    }
+    return assignments;
+  }
+
+  /**
+   * Generates a bulk assignment startup plan, attempting to reuse the existing
+   * assignment information from META, but adjusting for the specified list of
+   * available/online servers available for assignment.
+   * <p>
+   * Takes a map of all regions to their existing assignment from META.  Also
+   * takes a list of online servers for regions to be assigned to.  Attempts to
+   * retain all assignment, so in some instances initial assignment will not be
+   * completely balanced.
+   * <p>
+   * Any leftover regions without an existing server to be assigned to will be
+   * assigned randomly to available servers.
+   * @param regions regions and existing assignment from meta
+   * @param servers available servers
+   * @return map of servers and regions to be assigned to them
+   */
+  public Map<ServerName, List<HRegionInfo>> retainAssignment(
+      Map<HRegionInfo, ServerName> regions, List<ServerName> servers) {
+    Map<ServerName, List<HRegionInfo>> assignments =
+      new TreeMap<ServerName, List<HRegionInfo>>();
+    for (ServerName server : servers) {
+      assignments.put(server, new ArrayList<HRegionInfo>());
+    }
+    for (Map.Entry<HRegionInfo, ServerName> region : regions.entrySet()) {
+      ServerName sn = region.getValue();
+      if (sn != null && servers.contains(sn)) {
+        assignments.get(sn).add(region.getKey());
+      } else {
+        int size = assignments.size();
+        assignments.get(servers.get(RANDOM.nextInt(size))).add(region.getKey());
+      }
+    }
+    return assignments;
+  }
+
+  /**
+   * Returns an ordered list of hosts that are hosting the blocks for this
+   * region.  The weight of each host is the sum of the block lengths of all
+   * files on that host, so the first host in the list is the server which
+   * holds the most bytes of the given region's HFiles.
+   *
+   * @param fs the filesystem
+   * @param region region
+   * @return ordered list of hosts holding blocks of the specified region
+   */
+  @SuppressWarnings("unused")
+  private List<ServerName> getTopBlockLocations(FileSystem fs,
+    HRegionInfo region) {
+    List<ServerName> topServerNames = null;
+    try {
+      HTableDescriptor tableDescriptor = getTableDescriptor(
+        region.getTableName());
+      if (tableDescriptor != null) {
+        HDFSBlocksDistribution blocksDistribution =
+          HRegion.computeHDFSBlocksDistribution(config, tableDescriptor,
+          region.getEncodedName());
+        List<String> topHosts = blocksDistribution.getTopHosts();
+        topServerNames = mapHostNameToServerName(topHosts);
+      }
+    } catch (IOException ioe) {
+      LOG.debug("IOException during HDFSBlocksDistribution computation. for " +
+        "region = " + region.getEncodedName() , ioe);
+    }
+    
+    return topServerNames;
+  }
+
+  /**
+   * return HTableDescriptor for a given tableName
+   * @param tableName the table name
+   * @return HTableDescriptor
+   * @throws IOException
+   */
+  private HTableDescriptor getTableDescriptor(byte[] tableName)
+    throws IOException {
+    HTableDescriptor tableDescriptor = null;
+    try {
+      if ( this.services != null)
+      {
+        tableDescriptor = this.services.getTableDescriptors().
+          get(Bytes.toString(tableName));
+    }
+    } catch (TableExistsException tee) {
+      LOG.debug("TableExistsException during getTableDescriptors." +
+        " Current table name = " + tableName , tee);
+    } catch (FileNotFoundException fnfe) {
+      LOG.debug("FileNotFoundException during getTableDescriptors." +
+        " Current table name = " + tableName , fnfe);
+    }
+
+    return tableDescriptor;
+    }
+
+  /**
+   * Map hostname to ServerName, The output ServerName list will have the same
+   * order as input hosts.
+   * @param hosts the list of hosts
+   * @return ServerName list
+   */  
+  private List<ServerName> mapHostNameToServerName(List<String> hosts) {
+    if ( hosts == null || status == null) {
+      return null;
+    }
+
+    List<ServerName> topServerNames = new ArrayList<ServerName>();
+    Collection<ServerName> regionServers = status.getServers();
+
+    // create a mapping from hostname to ServerName for fast lookup
+    HashMap<String, ServerName> hostToServerName =
+      new HashMap<String, ServerName>();
+    for (ServerName sn : regionServers) {
+      hostToServerName.put(sn.getHostname(), sn);
+        }
+
+    for (String host : hosts ) {
+      ServerName sn = hostToServerName.get(host);
+      // it is possible that HDFS is up ( thus host is valid ),
+      // but RS is down ( thus sn is null )
+      if (sn != null) {
+        topServerNames.add(sn);
+      }
+    }
+    return topServerNames;
+  }
+
+
+  /**
+   * Generates an immediate assignment plan to be used by a new master for
+   * regions in transition that do not have an already known destination.
+   *
+   * Takes a list of regions that need immediate assignment and a list of
+   * all available servers.  Returns a map of regions to the server they
+   * should be assigned to.
+   *
+   * This method will return quickly and does not do any intelligent
+   * balancing.  The goal is to make a fast decision not the best decision
+   * possible.
+   *
+   * Currently this is random.
+   *
+   * @param regions
+   * @param servers
+   * @return map of regions to the server it should be assigned to
+   */
+  public Map<HRegionInfo, ServerName> immediateAssignment(
+      List<HRegionInfo> regions, List<ServerName> servers) {
+    Map<HRegionInfo,ServerName> assignments =
+      new TreeMap<HRegionInfo,ServerName>();
+    for(HRegionInfo region : regions) {
+      assignments.put(region, servers.get(RANDOM.nextInt(servers.size())));
+    }
+    return assignments;
+  }
+
+  public ServerName randomAssignment(List<ServerName> servers) {
+    if (servers == null || servers.isEmpty()) {
+      LOG.warn("Wanted to do random assignment but no servers to assign to");
+      return null;
+    }
+    return servers.get(RANDOM.nextInt(servers.size()));
+  }
+
+}

Modified: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/HMaster.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/HMaster.java?rev=1160887&r1=1160886&r2=1160887&view=diff
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/HMaster.java (original)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/HMaster.java Tue Aug 23 21:05:38 2011
@@ -63,7 +63,7 @@ import org.apache.hadoop.hbase.ipc.HBase
 import org.apache.hadoop.hbase.ipc.HMasterInterface;
 import org.apache.hadoop.hbase.ipc.HMasterRegionInterface;
 import org.apache.hadoop.hbase.ipc.RpcServer;
-import org.apache.hadoop.hbase.master.LoadBalancer.RegionPlan;
+import org.apache.hadoop.hbase.master.RegionPlan;
 import org.apache.hadoop.hbase.master.handler.DeleteTableHandler;
 import org.apache.hadoop.hbase.master.handler.DisableTableHandler;
 import org.apache.hadoop.hbase.master.handler.EnableTableHandler;
@@ -354,7 +354,7 @@ implements HMasterInterface, HMasterRegi
 
     this.assignmentManager = new AssignmentManager(this, serverManager,
         this.catalogTracker, this.executorService);
-    this.balancer = new LoadBalancer(conf);
+    this.balancer = LoadBalancerFactory.getLoadBalancer(conf);
     zooKeeper.registerListenerFirst(assignmentManager);
 
     this.regionServerTracker = new RegionServerTracker(zooKeeper, this,

Modified: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancer.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancer.java?rev=1160887&r1=1160886&r2=1160887&view=diff
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancer.java (original)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancer.java Tue Aug 23 21:05:38 2011
@@ -1,5 +1,5 @@
 /**
- * Copyright 2010 The Apache Software Foundation
+ * Copyright 2011 The Apache Software Foundation
  *
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
@@ -19,34 +19,13 @@
  */
 package org.apache.hadoop.hbase.master;
 
-import java.io.FileNotFoundException;
-import java.io.IOException;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.NavigableMap;
-import java.util.Random;
-import java.util.TreeMap;
-
-import org.apache.commons.logging.Log;
-import org.apache.commons.logging.LogFactory;
-import org.apache.hadoop.conf.Configuration;
-import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.conf.Configurable;
 import org.apache.hadoop.hbase.ClusterStatus;
-import org.apache.hadoop.hbase.HDFSBlocksDistribution;
 import org.apache.hadoop.hbase.HRegionInfo;
-import org.apache.hadoop.hbase.HTableDescriptor;
 import org.apache.hadoop.hbase.ServerName;
-import org.apache.hadoop.hbase.TableExistsException;
-import org.apache.hadoop.hbase.regionserver.HRegion;
-import org.apache.hadoop.hbase.util.Bytes;
 
-import com.google.common.collect.MinMaxPriorityQueue;
+import java.util.List;
+import java.util.Map;
 
 /**
  * Makes decisions about the placement and movement of Regions across
@@ -64,764 +43,56 @@ import com.google.common.collect.MinMaxP
  *
  * <p>This classes produces plans for the {@link AssignmentManager} to execute.
  */
-public class LoadBalancer {
-  private static final Log LOG = LogFactory.getLog(LoadBalancer.class);
-  private static final Random RANDOM = new Random(System.currentTimeMillis());
-  // slop for regions
-  private float slop;
-  private Configuration config;
-  private ClusterStatus status;
-  private MasterServices services;
-
-  LoadBalancer(Configuration conf) {
-    this.slop = conf.getFloat("hbase.regions.slop", (float) 0.2);
-    if (slop < 0) slop = 0;
-    else if (slop > 1) slop = 1;
-    this.config = conf;
-  }
-  
-  public void setClusterStatus(ClusterStatus st) {
-    this.status = st;
-  }
-
-  public void setMasterServices(MasterServices masterServices) {
-    this.services = masterServices;
-  }
-  
-  /* 
-   * The following comparator assumes that RegionId from HRegionInfo can
-   * represent the age of the region - larger RegionId means the region
-   * is younger.
-   * This comparator is used in balanceCluster() to account for the out-of-band
-   * regions which were assigned to the server after some other region server
-   * crashed.
-   */
-   static class RegionInfoComparator implements Comparator<HRegionInfo> {
-       @Override
-       public int compare(HRegionInfo l, HRegionInfo r) {
-          long diff = r.getRegionId() - l.getRegionId();
-          if (diff < 0) return -1;
-          if (diff > 0) return 1;
-          return 0;
-       } 
-   }
-   static RegionInfoComparator riComparator = new RegionInfoComparator();
-   
-   static class RegionPlanComparator implements Comparator<RegionPlan> {
-    @Override
-    public int compare(RegionPlan l, RegionPlan r) {
-      long diff = r.getRegionInfo().getRegionId() - l.getRegionInfo().getRegionId();
-      if (diff < 0) return -1;
-      if (diff > 0) return 1;
-      return 0;
-    }
-  }
-  static RegionPlanComparator rpComparator = new RegionPlanComparator();
-
-  /**
-   * Data structure that holds servername and 'load'.
-   */
-  static class ServerAndLoad implements Comparable<ServerAndLoad> {
-    private final ServerName sn;
-    private final int load;
-    ServerAndLoad(final ServerName sn, final int load) {
-      this.sn = sn;
-      this.load = load;
-    }
-
-    ServerName getServerName() {return this.sn;}
-    int getLoad() {return this.load;}
-
-    @Override
-    public int compareTo(ServerAndLoad other) {
-      int diff = this.load - other.load;
-      return diff != 0? diff: this.sn.compareTo(other.getServerName());
-    }
-  }
+public interface LoadBalancer extends Configurable {
 
   /**
-   * Generate a global load balancing plan according to the specified map of
-   * server information to the most loaded regions of each server.
-   *
-   * The load balancing invariant is that all servers are within 1 region of the
-   * average number of regions per server.  If the average is an integer number,
-   * all servers will be balanced to the average.  Otherwise, all servers will
-   * have either floor(average) or ceiling(average) regions.
-   *
-   * HBASE-3609 Modeled regionsToMove using Guava's MinMaxPriorityQueue so that
-   *   we can fetch from both ends of the queue. 
-   * At the beginning, we check whether there was empty region server 
-   *   just discovered by Master. If so, we alternately choose new / old
-   *   regions from head / tail of regionsToMove, respectively. This alternation
-   *   avoids clustering young regions on the newly discovered region server.
-   *   Otherwise, we choose new regions from head of regionsToMove.
-   *   
-   * Another improvement from HBASE-3609 is that we assign regions from
-   *   regionsToMove to underloaded servers in round-robin fashion.
-   *   Previously one underloaded server would be filled before we move onto
-   *   the next underloaded server, leading to clustering of young regions.
-   *   
-   * Finally, we randomly shuffle underloaded servers so that they receive
-   *   offloaded regions relatively evenly across calls to balanceCluster().
-   *         
-   * The algorithm is currently implemented as such:
-   *
-   * <ol>
-   * <li>Determine the two valid numbers of regions each server should have,
-   *     <b>MIN</b>=floor(average) and <b>MAX</b>=ceiling(average).
-   *
-   * <li>Iterate down the most loaded servers, shedding regions from each so
-   *     each server hosts exactly <b>MAX</b> regions.  Stop once you reach a
-   *     server that already has &lt;= <b>MAX</b> regions.
-   *     <p>
-   *     Order the regions to move from most recent to least.
-   *
-   * <li>Iterate down the least loaded servers, assigning regions so each server
-   *     has exactly </b>MIN</b> regions.  Stop once you reach a server that
-   *     already has &gt;= <b>MIN</b> regions.
-   *
-   *     Regions being assigned to underloaded servers are those that were shed
-   *     in the previous step.  It is possible that there were not enough
-   *     regions shed to fill each underloaded server to <b>MIN</b>.  If so we
-   *     end up with a number of regions required to do so, <b>neededRegions</b>.
-   *
-   *     It is also possible that we were able to fill each underloaded but ended
-   *     up with regions that were unassigned from overloaded servers but that
-   *     still do not have assignment.
-   *
-   *     If neither of these conditions hold (no regions needed to fill the
-   *     underloaded servers, no regions leftover from overloaded servers),
-   *     we are done and return.  Otherwise we handle these cases below.
-   *
-   * <li>If <b>neededRegions</b> is non-zero (still have underloaded servers),
-   *     we iterate the most loaded servers again, shedding a single server from
-   *     each (this brings them from having <b>MAX</b> regions to having
-   *     <b>MIN</b> regions).
-   *
-   * <li>We now definitely have more regions that need assignment, either from
-   *     the previous step or from the original shedding from overloaded servers.
-   *     Iterate the least loaded servers filling each to <b>MIN</b>.
-   *
-   * <li>If we still have more regions that need assignment, again iterate the
-   *     least loaded servers, this time giving each one (filling them to
-   *     </b>MAX</b>) until we run out.
-   *
-   * <li>All servers will now either host <b>MIN</b> or <b>MAX</b> regions.
-   *
-   *     In addition, any server hosting &gt;= <b>MAX</b> regions is guaranteed
-   *     to end up with <b>MAX</b> regions at the end of the balancing.  This
-   *     ensures the minimal number of regions possible are moved.
-   * </ol>
-   *
-   * TODO: We can at-most reassign the number of regions away from a particular
-   *       server to be how many they report as most loaded.
-   *       Should we just keep all assignment in memory?  Any objections?
-   *       Does this mean we need HeapSize on HMaster?  Or just careful monitor?
-   *       (current thinking is we will hold all assignments in memory)
-   *
-   * @param clusterState Map of regionservers and their load/region information to
-   *                   a list of their most loaded regions
-   * @return a list of regions to be moved, including source and destination,
-   *         or null if cluster is already balanced
+   * Set the current cluster status.  This allows a LoadBalancer to map host name to a server
+   * @param st
    */
-  public List<RegionPlan> balanceCluster(
-      Map<ServerName, List<HRegionInfo>> clusterState) {
-    boolean emptyRegionServerPresent = false;
-    long startTime = System.currentTimeMillis();
-
-    int numServers = clusterState.size();
-    if (numServers == 0) {
-      LOG.debug("numServers=0 so skipping load balancing");
-      return null;
-    }
-    NavigableMap<ServerAndLoad, List<HRegionInfo>> serversByLoad =
-      new TreeMap<ServerAndLoad, List<HRegionInfo>>();
-    int numRegions = 0;
-    StringBuilder strBalanceParam = new StringBuilder("Server information: ");
-    // Iterate so we can count regions as we build the map
-    for (Map.Entry<ServerName, List<HRegionInfo>> server: clusterState.entrySet()) {
-      List<HRegionInfo> regions = server.getValue();
-      int sz = regions.size();
-      if (sz == 0) emptyRegionServerPresent = true;
-      numRegions += sz;
-      serversByLoad.put(new ServerAndLoad(server.getKey(), sz), regions);
-      strBalanceParam.append(server.getKey().getServerName()).append("=").
-        append(server.getValue().size()).append(", ");
-    }
-    strBalanceParam.delete(strBalanceParam.length() - 2,
-      strBalanceParam.length());
-    LOG.debug(strBalanceParam.toString());
-
-    // Check if we even need to do any load balancing
-    float average = (float)numRegions / numServers; // for logging
-    // HBASE-3681 check sloppiness first
-    int floor = (int) Math.floor(average * (1 - slop));
-    int ceiling = (int) Math.ceil(average * (1 + slop));
-    if (serversByLoad.lastKey().getLoad() <= ceiling &&
-       serversByLoad.firstKey().getLoad() >= floor) {
-      // Skipped because no server outside (min,max) range
-      LOG.info("Skipping load balancing because balanced cluster; " +
-        "servers=" + numServers + " " +
-        "regions=" + numRegions + " average=" + average + " " +
-        "mostloaded=" + serversByLoad.lastKey().getLoad() +
-        " leastloaded=" + serversByLoad.firstKey().getLoad());
-      return null;
-    }
-    int min = numRegions / numServers;
-    int max = numRegions % numServers == 0 ? min : min + 1;
-
-    // Using to check banance result.
-    strBalanceParam.delete(0, strBalanceParam.length());
-    strBalanceParam.append("Balance parameter: numRegions=").append(numRegions)
-        .append(", numServers=").append(numServers).append(", max=").append(max)
-        .append(", min=").append(min);
-    LOG.debug(strBalanceParam.toString());
-    
-    // Balance the cluster
-    // TODO: Look at data block locality or a more complex load to do this
-    MinMaxPriorityQueue<RegionPlan> regionsToMove =
-      MinMaxPriorityQueue.orderedBy(rpComparator).create();
-    List<RegionPlan> regionsToReturn = new ArrayList<RegionPlan>();
-
-    // Walk down most loaded, pruning each to the max
-    int serversOverloaded = 0;
-    // flag used to fetch regions from head and tail of list, alternately
-    boolean fetchFromTail = false;
-    Map<ServerName, BalanceInfo> serverBalanceInfo =
-      new TreeMap<ServerName, BalanceInfo>();
-    for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server:
-        serversByLoad.descendingMap().entrySet()) {
-      ServerAndLoad sal = server.getKey();
-      int regionCount = sal.getLoad();
-      if (regionCount <= max) {
-        serverBalanceInfo.put(sal.getServerName(), new BalanceInfo(0, 0));
-        break;
-      }
-      serversOverloaded++;
-      List<HRegionInfo> regions = server.getValue();
-      int numToOffload = Math.min(regionCount - max, regions.size());
-      // account for the out-of-band regions which were assigned to this server
-      // after some other region server crashed 
-      Collections.sort(regions, riComparator);
-      int numTaken = 0;
-      for (int i = 0; i <= numToOffload; ) {
-        HRegionInfo hri = regions.get(i); // fetch from head
-        if (fetchFromTail) {
-          hri = regions.get(regions.size() - 1 - i);
-        }
-        i++;
-        // Don't rebalance meta regions.
-        if (hri.isMetaRegion()) continue;
-        regionsToMove.add(new RegionPlan(hri, sal.getServerName(), null));
-        numTaken++;
-        if (numTaken >= numToOffload) break;
-        // fetch in alternate order if there is new region server
-        if (emptyRegionServerPresent) {
-          fetchFromTail = !fetchFromTail;
-        }
-      }
-      serverBalanceInfo.put(sal.getServerName(),
-        new BalanceInfo(numToOffload, (-1)*numTaken));
-    }
-    int totalNumMoved = regionsToMove.size();
-
-    // Walk down least loaded, filling each to the min
-    int neededRegions = 0; // number of regions needed to bring all up to min
-    fetchFromTail = false;
-
-    Map<ServerName, Integer> underloadedServers = new HashMap<ServerName, Integer>();
-    for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server:
-        serversByLoad.entrySet()) {
-      int regionCount = server.getKey().getLoad();
-      if (regionCount >= min) {
-        break;
-      }
-      underloadedServers.put(server.getKey().getServerName(), min - regionCount);
-    }
-    // number of servers that get new regions
-    int serversUnderloaded = underloadedServers.size();
-    int incr = 1;
-    List<ServerName> sns =
-      Arrays.asList(underloadedServers.keySet().toArray(new ServerName[serversUnderloaded]));
-    Collections.shuffle(sns, RANDOM);
-    while (regionsToMove.size() > 0) {
-      int cnt = 0;
-      int i = incr > 0 ? 0 : underloadedServers.size()-1;
-      for (; i >= 0 && i < underloadedServers.size(); i += incr) {
-        if (regionsToMove.isEmpty()) break;
-        ServerName si = sns.get(i);
-        int numToTake = underloadedServers.get(si);
-        if (numToTake == 0) continue;
-
-        addRegionPlan(regionsToMove, fetchFromTail, si, regionsToReturn);
-        if (emptyRegionServerPresent) {
-          fetchFromTail = !fetchFromTail;
-        }
-
-        underloadedServers.put(si, numToTake-1);
-        cnt++;
-        BalanceInfo bi = serverBalanceInfo.get(si);
-        if (bi == null) {
-          bi = new BalanceInfo(0, 0);
-          serverBalanceInfo.put(si, bi);
-        }
-        bi.setNumRegionsAdded(bi.getNumRegionsAdded()+1);
-      }
-      if (cnt == 0) break;
-      // iterates underloadedServers in the other direction
-      incr = -incr;
-    }
-    for (Integer i : underloadedServers.values()) {
-      // If we still want to take some, increment needed
-      neededRegions += i;
-    }
-
-    // If none needed to fill all to min and none left to drain all to max,
-    // we are done
-    if (neededRegions == 0 && regionsToMove.isEmpty()) {
-      long endTime = System.currentTimeMillis();
-      LOG.info("Calculated a load balance in " + (endTime-startTime) + "ms. " +
-          "Moving " + totalNumMoved + " regions off of " +
-          serversOverloaded + " overloaded servers onto " +
-          serversUnderloaded + " less loaded servers");
-      return regionsToReturn;
-    }
-
-    // Need to do a second pass.
-    // Either more regions to assign out or servers that are still underloaded
-
-    // If we need more to fill min, grab one from each most loaded until enough
-    if (neededRegions != 0) {
-      // Walk down most loaded, grabbing one from each until we get enough
-      for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server :
-        serversByLoad.descendingMap().entrySet()) {
-        BalanceInfo balanceInfo =
-          serverBalanceInfo.get(server.getKey().getServerName());
-        int idx =
-          balanceInfo == null ? 0 : balanceInfo.getNextRegionForUnload();
-        if (idx >= server.getValue().size()) break;
-        HRegionInfo region = server.getValue().get(idx);
-        if (region.isMetaRegion()) continue; // Don't move meta regions.
-        regionsToMove.add(new RegionPlan(region, server.getKey().getServerName(), null));
-        totalNumMoved++;
-        if (--neededRegions == 0) {
-          // No more regions needed, done shedding
-          break;
-        }
-      }
-    }
-
-    // Now we have a set of regions that must be all assigned out
-    // Assign each underloaded up to the min, then if leftovers, assign to max
-
-    // Walk down least loaded, assigning to each to fill up to min
-    for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server :
-        serversByLoad.entrySet()) {
-      int regionCount = server.getKey().getLoad();
-      if (regionCount >= min) break;
-      BalanceInfo balanceInfo = serverBalanceInfo.get(server.getKey().getServerName());
-      if(balanceInfo != null) {
-        regionCount += balanceInfo.getNumRegionsAdded();
-      }
-      if(regionCount >= min) {
-        continue;
-      }
-      int numToTake = min - regionCount;
-      int numTaken = 0;
-      while(numTaken < numToTake && 0 < regionsToMove.size()) {
-        addRegionPlan(regionsToMove, fetchFromTail,
-          server.getKey().getServerName(), regionsToReturn);
-        numTaken++;
-        if (emptyRegionServerPresent) {
-          fetchFromTail = !fetchFromTail;
-        }
-      }
-    }
-
-    // If we still have regions to dish out, assign underloaded to max
-    if (0 < regionsToMove.size()) {
-      for (Map.Entry<ServerAndLoad, List<HRegionInfo>> server :
-        serversByLoad.entrySet()) {
-        int regionCount = server.getKey().getLoad();
-        if(regionCount >= max) {
-          break;
-        }
-        addRegionPlan(regionsToMove, fetchFromTail,
-          server.getKey().getServerName(), regionsToReturn);
-        if (emptyRegionServerPresent) {
-          fetchFromTail = !fetchFromTail;
-        }
-        if (regionsToMove.isEmpty()) {
-          break;
-        }
-      }
-    }
-
-    long endTime = System.currentTimeMillis();
-
-    if (!regionsToMove.isEmpty() || neededRegions != 0) {
-      // Emit data so can diagnose how balancer went astray.
-      LOG.warn("regionsToMove=" + totalNumMoved +
-        ", numServers=" + numServers + ", serversOverloaded=" + serversOverloaded +
-        ", serversUnderloaded=" + serversUnderloaded);
-      StringBuilder sb = new StringBuilder();
-      for (Map.Entry<ServerName, List<HRegionInfo>> e: clusterState.entrySet()) {
-        if (sb.length() > 0) sb.append(", ");
-        sb.append(e.getKey().toString());
-        sb.append(" ");
-        sb.append(e.getValue().size());
-      }
-      LOG.warn("Input " + sb.toString());
-    }
-
-    // All done!
-    LOG.info("Done. Calculated a load balance in " + (endTime-startTime) + "ms. " +
-        "Moving " + totalNumMoved + " regions off of " +
-        serversOverloaded + " overloaded servers onto " +
-        serversUnderloaded + " less loaded servers");
+  public void setClusterStatus(ClusterStatus st);
 
-    return regionsToReturn;
-  }
 
   /**
-   * Add a region from the head or tail to the List of regions to return.
+   * Set the master service.
+   * @param masterServices
    */
-  void addRegionPlan(final MinMaxPriorityQueue<RegionPlan> regionsToMove,
-      final boolean fetchFromTail, final ServerName sn, List<RegionPlan> regionsToReturn) {
-    RegionPlan rp = null;
-    if (!fetchFromTail) rp = regionsToMove.remove();
-    else rp = regionsToMove.removeLast();
-    rp.setDestination(sn);
-    regionsToReturn.add(rp);
-  }
+  public void setMasterServices(MasterServices masterServices);
 
   /**
-   * @param regions
-   * @return Randomization of passed <code>regions</code>
+   * Perform the major balance operation
+   * @param clusterState
+   * @return
    */
-  static List<HRegionInfo> randomize(final List<HRegionInfo> regions) {
-    Collections.shuffle(regions, RANDOM);
-    return regions;
-  }
+  public List<RegionPlan> balanceCluster(Map<ServerName, List<HRegionInfo>> clusterState);
 
   /**
-   * Stores additional per-server information about the regions added/removed
-   * during the run of the balancing algorithm.
-   *
-   * For servers that shed regions, we need to track which regions we have
-   * already shed.  <b>nextRegionForUnload</b> contains the index in the list
-   * of regions on the server that is the next to be shed.
-   */
-  private static class BalanceInfo {
-
-    private final int nextRegionForUnload;
-    private int numRegionsAdded;
-
-    public BalanceInfo(int nextRegionForUnload, int numRegionsAdded) {
-      this.nextRegionForUnload = nextRegionForUnload;
-      this.numRegionsAdded = numRegionsAdded;
-    }
-
-    public int getNextRegionForUnload() {
-      return nextRegionForUnload;
-    }
-
-    public int getNumRegionsAdded() {
-      return numRegionsAdded;
-    }
-
-    public void setNumRegionsAdded(int numAdded) {
-      this.numRegionsAdded = numAdded;
-    }
-  }
-
-  /**
-   * Generates a bulk assignment plan to be used on cluster startup using a
-   * simple round-robin assignment.
-   * <p>
-   * Takes a list of all the regions and all the servers in the cluster and
-   * returns a map of each server to the regions that it should be assigned.
-   * <p>
-   * Currently implemented as a round-robin assignment.  Same invariant as
-   * load balancing, all servers holding floor(avg) or ceiling(avg).
-   *
-   * TODO: Use block locations from HDFS to place regions with their blocks
-   *
-   * @param regions all regions
-   * @param servers all servers
-   * @return map of server to the regions it should take, or null if no
-   *         assignment is possible (ie. no regions or no servers)
-   */
-  public static Map<ServerName, List<HRegionInfo>> roundRobinAssignment(
-      List<HRegionInfo> regions, List<ServerName> servers) {
-    if (regions.isEmpty() || servers.isEmpty()) {
-      return null;
-    }
-    Map<ServerName, List<HRegionInfo>> assignments =
-      new TreeMap<ServerName,List<HRegionInfo>>();
-    int numRegions = regions.size();
-    int numServers = servers.size();
-    int max = (int)Math.ceil((float)numRegions/numServers);
-    int serverIdx = 0;
-    if (numServers > 1) {
-      serverIdx = RANDOM.nextInt(numServers);
-    }
-    int regionIdx = 0;
-    for (int j = 0; j < numServers; j++) {
-      ServerName server = servers.get((j + serverIdx) % numServers);
-      List<HRegionInfo> serverRegions = new ArrayList<HRegionInfo>(max);
-      for (int i=regionIdx; i<numRegions; i += numServers) {
-        serverRegions.add(regions.get(i % numRegions));
-      }
-      assignments.put(server, serverRegions);
-      regionIdx++;
-    }
-    return assignments;
-  }
-
-  /**
-   * Generates a bulk assignment startup plan, attempting to reuse the existing
-   * assignment information from META, but adjusting for the specified list of
-   * available/online servers available for assignment.
-   * <p>
-   * Takes a map of all regions to their existing assignment from META.  Also
-   * takes a list of online servers for regions to be assigned to.  Attempts to
-   * retain all assignment, so in some instances initial assignment will not be
-   * completely balanced.
-   * <p>
-   * Any leftover regions without an existing server to be assigned to will be
-   * assigned randomly to available servers.
-   * @param regions regions and existing assignment from meta
-   * @param servers available servers
-   * @return map of servers and regions to be assigned to them
-   */
-  public static Map<ServerName, List<HRegionInfo>> retainAssignment(
-      Map<HRegionInfo, ServerName> regions, List<ServerName> servers) {
-    Map<ServerName, List<HRegionInfo>> assignments =
-      new TreeMap<ServerName, List<HRegionInfo>>();
-    for (ServerName server : servers) {
-      assignments.put(server, new ArrayList<HRegionInfo>());
-    }
-    for (Map.Entry<HRegionInfo, ServerName> region : regions.entrySet()) {
-      ServerName sn = region.getValue();
-      if (sn != null && servers.contains(sn)) {
-        assignments.get(sn).add(region.getKey());
-      } else {
-        int size = assignments.size();
-        assignments.get(servers.get(RANDOM.nextInt(size))).add(region.getKey());
-      }
-    }
-    return assignments;
-  }
-
-  /**
-   * Returns an ordered list of hosts that are hosting the blocks for this
-   * region.  The weight of each host is the sum of the block lengths of all
-   * files on that host, so the first host in the list is the server which
-   * holds the most bytes of the given region's HFiles.
-   *
-   * @param fs the filesystem
-   * @param region region
-   * @return ordered list of hosts holding blocks of the specified region
+   * Perform a Round Robin assignment of regions.
+   * @param regions
+   * @param servers
+   * @return
    */
-  @SuppressWarnings("unused")
-  private List<ServerName> getTopBlockLocations(FileSystem fs,
-    HRegionInfo region) {
-    List<ServerName> topServerNames = null;
-    try {
-      HTableDescriptor tableDescriptor = getTableDescriptor(
-        region.getTableName());
-      if (tableDescriptor != null) {
-        HDFSBlocksDistribution blocksDistribution =
-          HRegion.computeHDFSBlocksDistribution(config, tableDescriptor,
-          region.getEncodedName());
-        List<String> topHosts = blocksDistribution.getTopHosts();
-        topServerNames = mapHostNameToServerName(topHosts);
-      }
-    } catch (IOException ioe) {
-      LOG.debug("IOException during HDFSBlocksDistribution computation. for " +
-        "region = " + region.getEncodedName() , ioe);
-    }
-    
-    return topServerNames;
-  }
+  public Map<ServerName, List<HRegionInfo>> roundRobinAssignment(List<HRegionInfo> regions, List<ServerName> servers);
 
   /**
-   * return HTableDescriptor for a given tableName
-   * @param tableName the table name
-   * @return HTableDescriptor
-   * @throws IOException
+   * Assign regions to the previously hosting region server
+   * @param regions
+   * @param servers
+   * @return
    */
-  private HTableDescriptor getTableDescriptor(byte[] tableName)
-    throws IOException {
-    HTableDescriptor tableDescriptor = null;
-    try {
-      if ( this.services != null)
-      {
-        tableDescriptor = this.services.getTableDescriptors().
-          get(Bytes.toString(tableName));
-    }
-    } catch (TableExistsException tee) {
-      LOG.debug("TableExistsException during getTableDescriptors." +
-        " Current table name = " + tableName , tee);
-    } catch (FileNotFoundException fnfe) {
-      LOG.debug("FileNotFoundException during getTableDescriptors." +
-        " Current table name = " + tableName , fnfe);
-    }
-
-    return tableDescriptor;
-    }
+  public Map<ServerName, List<HRegionInfo>> retainAssignment(Map<HRegionInfo, ServerName> regions, List<ServerName> servers);
 
   /**
-   * Map hostname to ServerName, The output ServerName list will have the same
-   * order as input hosts.
-   * @param hosts the list of hosts
-   * @return ServerName list
-   */  
-  private List<ServerName> mapHostNameToServerName(List<String> hosts) {
-    if ( hosts == null || status == null) {
-      return null;
-    }
-
-    List<ServerName> topServerNames = new ArrayList<ServerName>();
-    Collection<ServerName> regionServers = status.getServers();
-
-    // create a mapping from hostname to ServerName for fast lookup
-    HashMap<String, ServerName> hostToServerName =
-      new HashMap<String, ServerName>();
-    for (ServerName sn : regionServers) {
-      hostToServerName.put(sn.getHostname(), sn);
-        }
-
-    for (String host : hosts ) {
-      ServerName sn = hostToServerName.get(host);
-      // it is possible that HDFS is up ( thus host is valid ),
-      // but RS is down ( thus sn is null )
-      if (sn != null) {
-        topServerNames.add(sn);
-      }
-    }
-    return topServerNames;
-  }
-
-
-  /**
-   * Generates an immediate assignment plan to be used by a new master for
-   * regions in transition that do not have an already known destination.
-   *
-   * Takes a list of regions that need immediate assignment and a list of
-   * all available servers.  Returns a map of regions to the server they
-   * should be assigned to.
-   *
-   * This method will return quickly and does not do any intelligent
-   * balancing.  The goal is to make a fast decision not the best decision
-   * possible.
-   *
-   * Currently this is random.
-   *
+   * Sync assign a region
    * @param regions
    * @param servers
-   * @return map of regions to the server it should be assigned to
+   * @return
    */
-  public static Map<HRegionInfo, ServerName> immediateAssignment(
-      List<HRegionInfo> regions, List<ServerName> servers) {
-    Map<HRegionInfo,ServerName> assignments =
-      new TreeMap<HRegionInfo,ServerName>();
-    for(HRegionInfo region : regions) {
-      assignments.put(region, servers.get(RANDOM.nextInt(servers.size())));
-    }
-    return assignments;
-  }
-
-  public static ServerName randomAssignment(List<ServerName> servers) {
-    if (servers == null || servers.isEmpty()) {
-      LOG.warn("Wanted to do random assignment but no servers to assign to");
-      return null;
-    }
-    return servers.get(RANDOM.nextInt(servers.size()));
-  }
+  public Map<HRegionInfo, ServerName> immediateAssignment(List<HRegionInfo> regions, List<ServerName> servers);
 
   /**
-   * Stores the plan for the move of an individual region.
-   *
-   * Contains info for the region being moved, info for the server the region
-   * should be moved from, and info for the server the region should be moved
-   * to.
-   *
-   * The comparable implementation of this class compares only the region
-   * information and not the source/dest server info.
+   * Get a random region server from the list
+   * @param servers
+   * @return
    */
-  public static class RegionPlan implements Comparable<RegionPlan> {
-    private final HRegionInfo hri;
-    private final ServerName source;
-    private ServerName dest;
-
-    /**
-     * Instantiate a plan for a region move, moving the specified region from
-     * the specified source server to the specified destination server.
-     *
-     * Destination server can be instantiated as null and later set
-     * with {@link #setDestination(ServerName)}.
-     *
-     * @param hri region to be moved
-     * @param source regionserver region should be moved from
-     * @param dest regionserver region should be moved to
-     */
-    public RegionPlan(final HRegionInfo hri, ServerName source, ServerName dest) {
-      this.hri = hri;
-      this.source = source;
-      this.dest = dest;
-    }
-
-    /**
-     * Set the destination server for the plan for this region.
-     */
-    public void setDestination(ServerName dest) {
-      this.dest = dest;
-    }
-
-    /**
-     * Get the source server for the plan for this region.
-     * @return server info for source
-     */
-    public ServerName getSource() {
-      return source;
-    }
-
-    /**
-     * Get the destination server for the plan for this region.
-     * @return server info for destination
-     */
-    public ServerName getDestination() {
-      return dest;
-    }
-
-    /**
-     * Get the encoded region name for the region this plan is for.
-     * @return Encoded region name
-     */
-    public String getRegionName() {
-      return this.hri.getEncodedName();
-    }
-
-    public HRegionInfo getRegionInfo() {
-      return this.hri;
-    }
-
-    /**
-     * Compare the region info.
-     * @param o region plan you are comparing against
-     */
-    @Override
-    public int compareTo(RegionPlan o) {
-      return getRegionName().compareTo(o.getRegionName());
-    }
-
-    @Override
-    public String toString() {
-      return "hri=" + this.hri.getRegionNameAsString() + ", src=" +
-        (this.source == null? "": this.source.toString()) +
-        ", dest=" + (this.dest == null? "": this.dest.toString());
-    }
-  }
+  public ServerName randomAssignment(List<ServerName> servers);
 }

Added: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancerFactory.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancerFactory.java?rev=1160887&view=auto
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancerFactory.java (added)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/LoadBalancerFactory.java Tue Aug 23 21:05:38 2011
@@ -0,0 +1,43 @@
+/**
+ * Copyright 2011 The Apache Software Foundation
+ *
+ * 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;
+
+import org.apache.hadoop.conf.Configuration;
+import org.apache.hadoop.util.ReflectionUtils;
+
+/**
+ * The class that creates a load balancer from a conf.
+ */
+public class LoadBalancerFactory {
+
+  /**
+   * Create a loadblanacer from the given conf.
+   * @param conf
+   * @return
+   */
+  public static LoadBalancer getLoadBalancer(Configuration conf) {
+
+    // Create the balancer
+    Class<? extends LoadBalancer> balancerKlass = conf.getClass("hbase.maser.loadBalancer.class",DefaultLoadBalancer.class, LoadBalancer.class);
+    return ReflectionUtils.newInstance(balancerKlass, conf);
+
+  }
+}

Added: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/RegionPlan.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/RegionPlan.java?rev=1160887&view=auto
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/RegionPlan.java (added)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/RegionPlan.java Tue Aug 23 21:05:38 2011
@@ -0,0 +1,88 @@
+package org.apache.hadoop.hbase.master;
+
+import org.apache.hadoop.hbase.HRegionInfo;
+import org.apache.hadoop.hbase.ServerName;
+
+/**
+ * Stores the plan for the move of an individual region.
+ *
+ * Contains info for the region being moved, info for the server the region
+ * should be moved from, and info for the server the region should be moved
+ * to.
+ *
+ * The comparable implementation of this class compares only the region
+ * information and not the source/dest server info.
+ */
+public class RegionPlan implements Comparable<RegionPlan> {
+  private final HRegionInfo hri;
+  private final ServerName source;
+  private ServerName dest;
+
+  /**
+   * Instantiate a plan for a region move, moving the specified region from
+   * the specified source server to the specified destination server.
+   *
+   * Destination server can be instantiated as null and later set
+   * with {@link #setDestination(ServerName)}.
+   *
+   * @param hri region to be moved
+   * @param source regionserver region should be moved from
+   * @param dest regionserver region should be moved to
+   */
+  public RegionPlan(final HRegionInfo hri, ServerName source, ServerName dest) {
+    this.hri = hri;
+    this.source = source;
+    this.dest = dest;
+  }
+
+  /**
+   * Set the destination server for the plan for this region.
+   */
+  public void setDestination(ServerName dest) {
+    this.dest = dest;
+  }
+
+  /**
+   * Get the source server for the plan for this region.
+   * @return server info for source
+   */
+  public ServerName getSource() {
+    return source;
+  }
+
+  /**
+   * Get the destination server for the plan for this region.
+   * @return server info for destination
+   */
+  public ServerName getDestination() {
+    return dest;
+  }
+
+  /**
+   * Get the encoded region name for the region this plan is for.
+   * @return Encoded region name
+   */
+  public String getRegionName() {
+    return this.hri.getEncodedName();
+  }
+
+  public HRegionInfo getRegionInfo() {
+    return this.hri;
+  }
+
+  /**
+   * Compare the region info.
+   * @param o region plan you are comparing against
+   */
+  @Override
+  public int compareTo(RegionPlan o) {
+    return getRegionName().compareTo(o.getRegionName());
+  }
+
+  @Override
+  public String toString() {
+    return "hri=" + this.hri.getRegionNameAsString() + ", src=" +
+      (this.source == null? "": this.source.toString()) +
+      ", dest=" + (this.dest == null? "": this.dest.toString());
+  }
+}

Added: hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/ServerAndLoad.java
URL: http://svn.apache.org/viewvc/hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/ServerAndLoad.java?rev=1160887&view=auto
==============================================================================
--- hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/ServerAndLoad.java (added)
+++ hbase/trunk/src/main/java/org/apache/hadoop/hbase/master/ServerAndLoad.java Tue Aug 23 21:05:38 2011
@@ -0,0 +1,31 @@
+package org.apache.hadoop.hbase.master;
+
+
+import org.apache.hadoop.hbase.ServerName;
+
+/**
+ * Data structure that holds servername and 'load'.
+ */
+class ServerAndLoad implements Comparable<ServerAndLoad> {
+  private final ServerName sn;
+  private final int load;
+
+  ServerAndLoad(final ServerName sn, final int load) {
+    this.sn = sn;
+    this.load = load;
+  }
+
+  ServerName getServerName() {
+    return this.sn;
+  }
+
+  int getLoad() {
+    return this.load;
+  }
+
+  @Override
+  public int compareTo(ServerAndLoad other) {
+    int diff = this.load - other.load;
+    return diff != 0 ? diff : this.sn.compareTo(other.getServerName());
+  }
+}
\ No newline at end of file