org.apache.hadoop.hbase.master
Class LoadBalancer

java.lang.Object
  extended by org.apache.hadoop.hbase.master.LoadBalancer

public class LoadBalancer
extends Object

Makes decisions about the placement and movement of Regions across RegionServers.

Cluster-wide load balancing will occur only when there are no regions in transition and according to a fixed period of a time using balanceCluster(Map).

Inline region placement with immediateAssignment(java.util.List, java.util.List) 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.

On cluster startup, bulk assignment can be used to determine locations for all Regions in a cluster.

This classes produces plans for the AssignmentManager to execute.


Nested Class Summary
static class LoadBalancer.RegionPlan
          Stores the plan for the move of an individual region.
 
Method Summary
 List<LoadBalancer.RegionPlan> balanceCluster(Map<HServerInfo,List<HRegionInfo>> clusterState)
          Generate a global load balancing plan according to the specified map of server information to the most loaded regions of each server.
static Map<HRegionInfo,HServerInfo> immediateAssignment(List<HRegionInfo> regions, List<HServerInfo> servers)
          Generates an immediate assignment plan to be used by a new master for regions in transition that do not have an already known destination.
static HServerInfo randomAssignment(List<HServerInfo> servers)
           
static Map<HServerInfo,List<HRegionInfo>> retainAssignment(Map<HRegionInfo,HServerAddress> regions, List<HServerInfo> servers)
          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.
static Map<HServerInfo,List<HRegionInfo>> roundRobinAssignment(List<HRegionInfo> regions, List<HServerInfo> servers)
          Generates a bulk assignment plan to be used on cluster startup using a simple round-robin assignment.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

balanceCluster

public List<LoadBalancer.RegionPlan> balanceCluster(Map<HServerInfo,List<HRegionInfo>> clusterState)
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. The algorithm is currently implemented as such:
  1. Determine the two valid numbers of regions each server should have, MIN=floor(average) and MAX=ceiling(average).
  2. Iterate down the most loaded servers, shedding regions from each so each server hosts exactly MAX regions. Stop once you reach a server that already has <= MAX regions.

    Order the regions to move from most recent to least.

  3. Iterate down the least loaded servers, assigning regions so each server has exactly MIN regions. Stop once you reach a server that already has >= MIN 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 MIN. If so we end up with a number of regions required to do so, neededRegions. It is also possible that we were able 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.
  4. If neededRegions 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 MAX regions to having MIN regions).
  5. 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 MIN.
  6. If we still have more regions that need assignment, again iterate the least loaded servers, this time giving each one (filling them to MAX) until we run out.
  7. All servers will now either host MIN or MAX regions. In addition, any server hosting >= MAX regions is guaranteed to end up with MAX regions at the end of the balancing. This ensures the minimal number of regions possible are moved.
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)

Parameters:
clusterState - Map of regionservers and their load/region information to a list of their most loaded regions
Returns:
a list of regions to be moved, including source and destination, or null if cluster is already balanced

roundRobinAssignment

public static Map<HServerInfo,List<HRegionInfo>> roundRobinAssignment(List<HRegionInfo> regions,
                                                                      List<HServerInfo> servers)
Generates a bulk assignment plan to be used on cluster startup using a simple round-robin assignment.

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.

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

Parameters:
regions - all regions
servers - all servers
Returns:
map of server to the regions it should take, or null if no assignment is possible (ie. no regions or no servers)

retainAssignment

public static Map<HServerInfo,List<HRegionInfo>> retainAssignment(Map<HRegionInfo,HServerAddress> regions,
                                                                  List<HServerInfo> servers)
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.

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.

Any leftover regions without an existing server to be assigned to will be assigned randomly to available servers.

Parameters:
regions - regions and existing assignment from meta
servers - available servers
Returns:
map of servers and regions to be assigned to them

immediateAssignment

public static Map<HRegionInfo,HServerInfo> immediateAssignment(List<HRegionInfo> regions,
                                                               List<HServerInfo> servers)
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.

Parameters:
regions -
servers -
Returns:
map of regions to the server it should be assigned to

randomAssignment

public static HServerInfo randomAssignment(List<HServerInfo> servers)


Copyright © 2011 The Apache Software Foundation. All Rights Reserved.