org.apache.hadoop.yarn.server.resourcemanager.scheduler.fair.policies
Class ComputeFairShares

java.lang.Object
  extended by org.apache.hadoop.yarn.server.resourcemanager.scheduler.fair.policies.ComputeFairShares

public class ComputeFairShares
extends Object

Contains logic for computing the fair shares. A Schedulable's fair share is Resource it is entitled to, independent of the current demands and allocations on the cluster. A Schedulable whose resource consumption lies at or below its fair share will never have its containers preempted.


Constructor Summary
ComputeFairShares()
           
 
Method Summary
static void computeShares(Collection<? extends Schedulable> schedulables, org.apache.hadoop.yarn.api.records.Resource totalResources, ResourceType type)
          Given a set of Schedulables and a number of slots, compute their weighted fair shares.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ComputeFairShares

public ComputeFairShares()
Method Detail

computeShares

public static void computeShares(Collection<? extends Schedulable> schedulables,
                                 org.apache.hadoop.yarn.api.records.Resource totalResources,
                                 ResourceType type)
Given a set of Schedulables and a number of slots, compute their weighted fair shares. The min and max shares and of the Schedulables are assumed to be set beforehand. We compute the fairest possible allocation of shares to the Schedulables that respects their min and max shares. To understand what this method does, we must first define what weighted fair sharing means in the presence of min and max shares. If there were no minimum or maximum shares, then weighted fair sharing would be achieved if the ratio of slotsAssigned / weight was equal for each Schedulable and all slots were assigned. Minimum and maximum shares add a further twist - Some Schedulables may have a min share higher than their assigned share or a max share lower than their assigned share. To deal with these possibilities, we define an assignment of slots as being fair if there exists a ratio R such that: Schedulables S where S.minShare > R * S.weight are given share S.minShare - Schedulables S where S.maxShare < R * S.weight are given S.maxShare - All other Schedulables S are assigned share R * S.weight - The sum of all the shares is totalSlots. We call R the weight-to-slots ratio because it converts a Schedulable's weight to the number of slots it is assigned. We compute a fair allocation by finding a suitable weight-to-slot ratio R. To do this, we use binary search. Given a ratio R, we compute the number of slots that would be used in total with this ratio (the sum of the shares computed using the conditions above). If this number of slots is less than totalSlots, then R is too small and more slots could be assigned. If the number of slots is more than totalSlots, then R is too large. We begin the binary search with a lower bound on R of 0 (which means that all Schedulables are only given their minShare) and an upper bound computed to be large enough that too many slots are given (by doubling R until we use more than totalResources resources). The helper method resourceUsedWithWeightToResourceRatio computes the total resources used with a given value of R. The running time of this algorithm is linear in the number of Schedulables, because resourceUsedWithWeightToResourceRatio is linear-time and the number of iterations of binary search is a constant (dependent on desired precision).



Copyright © 2014 Apache Software Foundation. All Rights Reserved.