You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-dev@hadoop.apache.org by "Amar Kamat (JIRA)" <ji...@apache.org> on 2008/09/10 16:34:44 UTC
[jira] Created: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
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
Reporter: Amar Kamat
{{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12635954#action_12635954 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
To see an impact of this bug, I submitted three jobs (using the default scheduler), and changed the priority of one of them. In the jobqueue_details.jsp page, I saw that the job which changed priority is listed twice ! It is the same object being referred to, but as Amar pointed out, since it is not deleted, it shows up twice. I think schedulers could be affected by this, for e.g. if they do not check for a job's run state, they may think the job in the run list or queued list is still to be considered and work on them.
It seems like a blocker based on this. Setting it as such. If someone feels not, please comment here.
> 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
> Reporter: Amar Kamat
>
> {{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12638730#action_12638730 ]
Amar Kamat commented on HADOOP-4149:
------------------------------------
bq. This definitely seems to work. My only worry is that it will depend very heavily on the fact that we have the old job status. If there is any case where this will not be available, the solution breaks.
HADOOP-4053 will make sure that old and new statuses are available. So is your concern still valid?
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12637440#action_12637440 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
O(n) is O( n ). *Smile*
> 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.
[jira] Updated: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Amar Kamat updated HADOOP-4149:
-------------------------------
Attachment: HADOOP-4149-v1.5.patch
Attaching a patch using {{JobSchedulingInfo}}. Modified {{TestJobInProgressListener}} and {{TestCapacityScheduler}} to test job-queues.
Testing in progress.
> 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
>
> Attachments: HADOOP-4149-v1.5.patch
>
>
> {{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.
[jira] Updated: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Hemanth Yamijala updated HADOOP-4149:
-------------------------------------
Priority: Blocker (was: Major)
Affects Version/s: 0.19.0
Fix Version/s: 0.19.0
> 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
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12637502#action_12637502 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
This definitely seems to work. My only worry is that it will depend very heavily on the fact that we have the old job status. If there is any case where this will not be available, the solution breaks. For e.g. in the default scheduler, the {{JobQueueJobInProgressListener}} removes the object from the queue even in {{jobRemoved}} which will not have the old job status.
> 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.
[jira] Updated: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Amar Kamat updated HADOOP-4149:
-------------------------------
Status: Patch Available (was: Open)
> 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
>
> Attachments: HADOOP-4149-v1.5.patch, HADOOP-4149-v1.7.patch
>
>
> {{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12640933#action_12640933 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
Looks good overall.
Few minor comments:
- I think {{STARTTIME_JOB_COMPARATOR}} in {{JobQueuesManager}} should also compare Job IDs if start times are the same. This will handle a corner case where start times are somehow the same.
- I think the tests (in both TestJobInProgressListener and TestCapacityScheduler) can be a little simpler:
-- Submit two jobs and verify their order
-- Change the priority of the first to be lower, and verify the order is reversed.
-- Change the start time of the first, and verify the order is reversed again.
- In TestCapacityScheduler, the initialization should be done for the job which is in the front of the waiting queue.
- It should also verify that when completed, the job is not present in the running queue, instead of the waiting queue.
Please post results of test-patch and ant test after these changes are made.
> 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
>
> Attachments: HADOOP-4149-v1.5.patch
>
>
> {{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hudson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12642314#action_12642314 ]
Hudson commented on HADOOP-4149:
--------------------------------
Integrated in Hadoop-trunk #640 (See [http://hudson.zones.apache.org/hudson/job/Hadoop-trunk/640/])
> 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
>
> Attachments: HADOOP-4149-v1.5.patch, HADOOP-4149-v1.7.patch
>
>
> {{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12638937#action_12638937 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
HADOOP-4053 only assures that old and new statuses are available if the {{JobChangeEvent}} is a {{JobStatusChangeEvent}}. Hence, my concern is still valid. Also, as I pointed out, some of the schedulers may remove objects from the queue in {{jobRemoved}} as well.
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12637439#action_12637439 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
I think we need the list of objects maintained by the schedulers to be in sorted order, where the sorting is done based on parameters like job priority or start times. This is true irrespective of whether we use {{JobInProgress}} or any new object like the proposed {{JobSchedulingInfo}}. And a {{SortedSet}}, like a {{TreeSet}} seems to be required here. However, this also means that when we want to delete (or update) an object, we would need to iterate over all the objects in the structure to find the one we want to remove. This is because our sort ordering is based on different parameters from how we treat the objects as equal (which for all practical purposes should be based on the Job id).
I also think updates are rare operations, compared to accessing the list in a sorted order, which happens almost everytime the scheduler needs to look at a new job. Hence, I think it makes sense to go with an implementation that has an O(n) scan for removals.
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Vivek Ratan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12637266#action_12637266 ]
Vivek Ratan commented on HADOOP-4149:
-------------------------------------
HADOOP-3445 faces the same issue. JobQueuesManager.QueueInfo implements its own removal method that deletes an object from a TreeSet based on referential equality, rather than value equality that the TreeSet uses.
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Vivek Ratan (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12630207#action_12630207 ]
Vivek Ratan commented on HADOOP-4149:
-------------------------------------
looks like what you need is delete based on referential integrity, which is not what the TreeSet does. You could write your own remove method that uses "==" to find the right job object to remove. Or maybe extend the TreeSet class and overwrite remove().
> 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
> Reporter: Amar Kamat
>
> {{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.
[jira] Assigned: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Amar Kamat reassigned HADOOP-4149:
----------------------------------
Assignee: Amar Kamat
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12637466#action_12637466 ]
Amar Kamat commented on HADOOP-4149:
------------------------------------
bq. Use JobSchedulingInfo : Define a new class that bundles all the information required for scheduling
This will also require a _map_ from {{JobID}} to {{JobScheduingInfo}} so that upon a {{jobUpdated}} we can get the appropriate {{JobSchedulingInfo}} to be remove/updated. With HADOOP-4053, we can get away with the _map_ as we will have the old job-status and hence the {{JobScheduingInfo}} can be (re)constructed. Thoughts?
> 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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12635952#action_12635952 ]
Hemanth Yamijala commented on HADOOP-4149:
------------------------------------------
I realized that changes in priority could affect the scheduler list because of this bug. Should this be a blocker for Hadoop 0.19 ?
> 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
> Reporter: Amar Kamat
>
> {{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Hemanth Yamijala (JIRA)" <ji...@apache.org>.
[ 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.
[jira] Updated: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Amar Kamat updated HADOOP-4149:
-------------------------------
Attachment: HADOOP-4149-v1.7.patch
Attaching a patch the addresses Hemanth's concern.
1) Changed _STARTTIME_JOB_COMPARATOR_ to consider job-id
2) Removed unnecessary priority change in {{TestJobInProgressListener}}
3) {{TestCapacityScheduler}} now changes the start-time first and then the priority to make sure that job1 is first in the list. Tests now also check for the ordering apart from size.
Output of _test-patch_ on my box :
{code}
[exec] +1 overall.
[exec]
[exec] +1 @author. The patch does not contain any @author tags.
[exec]
[exec] +1 tests included. The patch appears to include 9 new or modified tests.
[exec]
[exec] +1 javadoc. The javadoc tool did not generate any warning messages.
[exec]
[exec] +1 javac. The applied patch does not increase the total number of javac compiler warnings.
[exec]
[exec] +1 findbugs. The patch does not introduce any new Findbugs warnings.
{code}
_ant test_ also passed on my box. Running through hudson.
> 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
>
> Attachments: HADOOP-4149-v1.5.patch, HADOOP-4149-v1.7.patch
>
>
> {{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.
[jira] Updated: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Owen O'Malley (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Owen O'Malley updated HADOOP-4149:
----------------------------------
Resolution: Fixed
Hadoop Flags: [Reviewed]
Status: Resolved (was: Patch Available)
I just committed this. Thanks, Amar!
> 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
>
> Attachments: HADOOP-4149-v1.5.patch, HADOOP-4149-v1.7.patch
>
>
> {{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.
[jira] Commented: (HADOOP-4149)
JobQueueJobInProgressListener.jobUpdated() might not work as expected
Posted by "Amar Kamat (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HADOOP-4149?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12637413#action_12637413 ]
Amar Kamat commented on HADOOP-4149:
------------------------------------
One way to get around this problem is to use an object other than {{JobInProgress}} which is completely under the scheduler's control. We can do something like
- Use {{JobStatus}} : The drawback is that we might not be able to change {{JobStatus}} if scheduler adds/needs more info
- Use {{JobSchedulingInfo}} : Define a new class that bundles all the information required for scheduling
- Change the datastructure and make sure that _insert_ and _delete_ happen in such a way that the structure is consistent and sorted.
- Do a forceful removal as done in the {{CapacityScheduler}}
I think #2 seems to be a cleaner solution, thoughts?
> 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.