[
https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12639392#action_12639392
]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
After an offline discussion with Sameer, I realized we could do the following -
a hybrid approach between Amar's proposal and mine.
- We modify the underlying data structure to be a TreeMap. The key is a new
wrapper object that holds startTime, priority, jobId of a job. The value is JIP.
- The comparator to sort is the same as today
- When we want to remove an object, we see cases where the old information of
the job is available. For e.g. in jobUpdated(JobStatusChangeEvent), this is
available. Then, we can reconstruct the wrapper object, and do a delete.
- In cases where the wrapper object cannot be reconstructed, we do a linear
scan on the jobs, checking by jobid and remove.
- In {{JobQueueManager.getWaitingJobQueue}}, we return this
{{TreeMap.values()}}.
The advantage of this approach over what I proposed is that for almost all
cases for the time being, we have O( log n ) lookup.
> JobQueueJobInProgressListener.jobUpdated() might not work as expected
> ---------------------------------------------------------------------
>
> Key: HADOOP-4149
> URL: https://issues.apache.org/jira/browse/HADOOP-4149
> Project: Hadoop Core
> Issue Type: Bug
> Components: mapred
> Affects Versions: 0.19.0
> Reporter: Amar Kamat
> Assignee: Amar Kamat
> Priority: Blocker
> Fix For: 0.19.0
>
>
> {{JobQueueJobInProgressListener}} uses a {{TreeSet}} to store the sorted
> collection of {{JobInProgress}} objects. The comparator used to sort the JIPs
> follow the following order
> - priority (>=)
> - start time (<=)
> - job id [jt-identifier, job-index] (<=)
> If any JIP object is changed w.r.t priority or start-time, then the TreeSet
> will be inconsistent. Hence doing a delete might not work. Consider the
> following
> 1) jobs are submitted in the following order
> ||number||jobid||priority||
> |1|j1|NORMAL|
> |2|j2|LOW|
> |3|j3|NORMAL|
> 2) The sorted collection will be in the order : {{j1,j3,j2}}
> 3) If job3's priority is changed to LOW then the collection wont change but
> delete will bail out on j1 itself as the comparator will return a -ve number.
> TreeSet uses the comparator both for sorting and deleting. If i indicates
> the index in the collection and obj represents the object under
> consideration, then looks like TreeSet.remove(obj) follows something like :
> - continue to search if the compare(i, obj) is -ve
> - bail out if the compare(i, obj) is +ve
> - delete the obj of compare(i,obj) == 0
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
