hadoop-yarn-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Wangda Tan (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (YARN-2056) Disable preemption at Queue level
Date Tue, 07 Oct 2014 05:16:35 GMT

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

Wangda Tan commented on YARN-2056:
----------------------------------

Hi [~eepayne],
Sorry to response so late,

I've carefully read and thought about what you mentioned, especially the algorithm. I think
it can resolve most issues, but it cannot guarante all case will be resolved. I think in your
algorithm, following case will be not correct.

{code}
total = 100
qA: used = 10, guaranteed = 10, pending = 100
qB: used = 25, guaranteed = 10, pending = 100 (non-preemptable)
qC: used = 0, guaranteed = 80, pending = 0

1. In the start, unassign = 100, It will first exclude qB, unassigned = 80
2. It will try to fill qA, qA = qA + 80 * (10/(10 + 80) = 18, unassigned = 72. qC will be
removed this turn
3. qB will not be added back here, becaused ideal_assign(qA) = 18, ideal_assign(qB) = 25.
4. All resource will be used by qA. The result should be
   ideal(qA) = 75, ideal(qB) = 25
{code}

And in addition, the remove-then-add-back algorithm seems not very straight-forward to me.

In my mind, this problem is like fulfilling water to a water tank like following, some of
the tank has stones, make some of them higher than others. Because of water flows, so the
result is most equilibrized (which water surface has same height, and some stone can be higher
than water surface).
{code}
   _____
  |     |   
__|  X  |  
|    X  |__   
|    X    |
|  X X   X|
|X X X   X|
-----------
 1 2 3 4 5
{code}

The algorithm may look like,
{code}
At the beginning, all queue will set ideal_assign = non-preemptable resource, and deduct non-preemptable
resource from total-remained resource (stones is here). All queue will keep in qAlloc

In each turn,
- All queues not completely satisfied ideal_guaranteed <= min(maximum_capacity, used +
pending) will NOT be removed. Like what we have today. (water hasn't reached ceiling of the
tank)
- Get normalized weight of each queue
- Get the queue with the minimum {ideal_assigned % guarantee}, say Q_min
- Get the target_height is = (Q_min.ideal_assigned + remained * Q_min.normalized_gurantee)
- For each queue, do TempQueue.offer like today
- The TempQueue.offer method looks like
  * If (q.ideal_assigned > target_height): skip
  * If (q.ideal_assigned <= target_height): accepted = min(q.maximum, q.used + q.pending,
target_height * q.guaranteed) - q.ideal_assigned
- If accepted becomes zero, remove the queue from qAlloc like today. 

The loop will exit until total-remained become zero (resource are exhausted) or qAlloc becomes
empty (all queue get satisfied). 
{code}

I think this algorithm can get a more balanced result. Does this make sense to you?

Thanks,
Wangda

> Disable preemption at Queue level
> ---------------------------------
>
>                 Key: YARN-2056
>                 URL: https://issues.apache.org/jira/browse/YARN-2056
>             Project: Hadoop YARN
>          Issue Type: Sub-task
>          Components: resourcemanager
>    Affects Versions: 2.4.0
>            Reporter: Mayank Bansal
>            Assignee: Eric Payne
>         Attachments: YARN-2056.201408202039.txt, YARN-2056.201408260128.txt, YARN-2056.201408310117.txt,
YARN-2056.201409022208.txt, YARN-2056.201409181916.txt, YARN-2056.201409210049.txt, YARN-2056.201409232329.txt,
YARN-2056.201409242210.txt
>
>
> We need to be able to disable preemption at individual queue level



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message