[jira] [Commented] (YARN-569) CapacityScheduler: support for preemption (using a capacity monitor)

["Carlo Curino (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/YARN-569?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13628937#comment-13628937 ] 

Carlo Curino commented on YARN-569:
-----------------------------------

------------- Comments of attached Graphs ----------
The attached graph highlights the need for preemption by means of an example designed to highlights this. We run 2 sort jobs over 128GB of data on a 10 nodes cluster, starting the first job in queue B (20% guaranteed capacity) and the second job 400sec later in queue A (80% guaranteed capacity).

We compare three scenarios:
# Default CapacityScheduler with A and B having maximum capacity set to 100%: the cluster utilization is high, B runs fast since it can use the entire cluster when A is not around, but A needs to wait for very long (almost 20 min) before obtaining access to its all of its guaranteed capacity (and over 250 secs to get any container beside the AM).
# Default CapacityScheduler with A and B have maximum capacity set to 80 and 20% respectively, A obtains its guaranteed resources immediately, but the cluster utilization is very low and jobs in B take over 2X longer since they cannot use spare overcapacity.
# CapacityScheduler + preemption: A and B are configured as in 1) but we preempt containers. We obtain both high-utilization, short runtimes for B (comparable to scenario 1), and prompt resources to A (within 30 sec). 

The second attached graph shows a scenario with 3 queues A, B, C with 40%, 20%, 40% capacity guaranteed. We show more "internals" of the policy by plotting, instantaneous resource utilization as above, total pending request, guaranteed capacity, ideal assignment of memory, ideal preemption, actual preemption.
 
Things to note:
# The idealized memory assignment and instaneous resource utilization are very close to each other, i.e., the combination of CapacityScheduler+Preemption tightly follows the the ideal distribution of resources
# When only one job is running it gets 100% of the cluster, when B, A are running they get 33% and 66% each (which is a fair overcapacity assignment from their 20%, 40% guaranteed capacity), when all three jobs are running (and they want at least their capacity worth of resources) they obtain their guaranteed capacity.
#actual preemption is a fraction of ideal preemption, this is because we account for natural completion of tasks (with a configurable parameter)
#in this experiment we do not bound the total amount of preemption per round (i.e., parameter set to 1.0)
 



                
> CapacityScheduler: support for preemption (using a capacity monitor)
> --------------------------------------------------------------------
>
>                 Key: YARN-569
>                 URL: https://issues.apache.org/jira/browse/YARN-569
>             Project: Hadoop YARN
>          Issue Type: Improvement
>          Components: capacityscheduler
>            Reporter: Carlo Curino
>         Attachments: 3queues.pdf, capacity.patch, CapScheduler_with_preemption.pdf
>
>
> There is a tension between the fast-pace reactive role of the CapacityScheduler, which needs to respond quickly to 
> applications resource requests, and node updates, and the more introspective, time-based considerations 
> needed to observe and correct for capacity balance. To this purpose we opted instead of hacking the delicate
> mechanisms of the CapacityScheduler directly to add support for preemption by means of a "Capacity Monitor",
> which can be run optionally as a separate service (much like the NMLivelinessMonitor).
> The capacity monitor (similarly to equivalent functionalities in the fairness scheduler) operates running on intervals 
> (e.g., every 3 seconds), observe the state of the assignment of resources to queues from the capacity scheduler, 
> performs off-line computation to determine if preemption is needed, and how best to "edit" the current schedule to 
> improve capacity, and generates events that produce four possible actions:
> # Container de-reservations
> # Resource-based preemptions
> # Container-based preemptions
> # Container killing
> The actions listed above are progressively more costly, and it is up to the policy to use them as desired to achieve the rebalancing goals. 
> Note that due to the "lag" in the effect of these actions the policy should operate at the macroscopic level (e.g., preempt tens of containers
> from a queue) and not trying to tightly and consistently micromanage container allocations. 
> ------------- Preemption policy  (ProportionalCapacityPreemptionPolicy): ------------- 
> Preemption policies are by design pluggable, in the following we present an initial policy (ProportionalCapacityPreemptionPolicy) we have been experimenting with.  The ProportionalCapacityPreemptionPolicy behaves as follows:
> # it gathers from the scheduler the state of the queues, in particular, their current capacity, guaranteed capacity and pending requests (*)
> # if there are pending requests from queues that are under capacity it computes a new ideal balanced state (**)
> # it computes the set of preemptions needed to repair the current schedule and achieve capacity balance (accounting for natural completion rates, and 
> respecting bounds on the amount of preemption we allow for each round)
> # it selects which applications to preempt from each over-capacity queue (the last one in the FIFO order)
> # it remove reservations from the most recently assigned app until the amount of resource to reclaim is obtained, or until no more reservations exits
> # (if not enough) it issues preemptions for containers from the same applications (reverse chronological order, last assigned container first) again until necessary or until no containers except the AM container are left,
> # (if not enough) it moves onto unreserve and preempt from the next application. 
> # containers that have been asked to preempt are tracked across executions. If a containers is among the one to be preempted for more than a certain time, the container is moved in a the list of containers to be forcibly killed. 
> Notes:
> (*) at the moment, in order to avoid double-counting of the requests, we only look at the "ANY" part of pending resource requests, which means we might not preempt on behalf of AMs that ask only for specific locations but not any. 
> (**) The ideal balance state is one in which each queue has at least its guaranteed capacity, and the spare capacity is distributed among queues (that wants some) as a weighted fair share. Where the weighting is based on the guaranteed capacity of a queue, and the function runs to a fix point.  
> Tunables of the ProportionalCapacityPreemptionPolicy:
> # 	observe-only mode (i.e., log the actions it would take, but behave as read-only)
> # how frequently to run the policy
> # how long to wait between preemption and kill of a container
> # which fraction of the containers I would like to obtain should I preempt (has to do with the natural rate at which containers are returned)
> # deadzone size, i.e., what % of over-capacity should I ignore (if we are off perfect balance by some small % we ignore it)
> # overall amount of preemption we can afford for each run of the policy (in terms of total cluster capacity)
> In our current experiments this set of tunables seem to be a good start to shape the preemption action properly. More sophisticated preemption policies could take into account different type of applications running, job priorities, cost of preemption, integral of capacity imbalance. This is very much a control-theory kind of problem, and some of the lessons on designing and tuning controllers are likely to apply.
> Generality:
> The monitor-based scheduler edit, and the preemption mechanisms we introduced here are designed to be more general than enforcing capacity/fairness, in fact, we are considering other monitors that leverage the same idea of "schedule edits" to target different global properties (e.g., allocate enough resources to guarantee deadlines for important jobs, or data-locality optimizations, IO-balancing among nodes, etc...).
> Note that by default the preemption policy we describe is disabled in the patch.
> Depends on YARN-45 and YARN-567, is related to YARN-568

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira