hadoop-yarn-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Xianyin Xin (JIRA)" <j...@apache.org>
Subject [jira] [Created] (YARN-3553) TreeSet is not a nice container for organizing schedulableEntities.
Date Tue, 28 Apr 2015 12:40:06 GMT
Xianyin Xin created YARN-3553:
---------------------------------

             Summary: TreeSet is not a nice container for organizing schedulableEntities.
                 Key: YARN-3553
                 URL: https://issues.apache.org/jira/browse/YARN-3553
             Project: Hadoop YARN
          Issue Type: Wish
          Components: scheduler
            Reporter: Xianyin Xin


For TreeSet, element is identified by comparator, not the object reference. If any *attributes
that used for comparing two elements* of an specific element is modified by other methods,
the TreeSet will be in an un-sorted state, and cannot become sorted forever except that we
reconstruct another TreeSet with the elements. To avoid this, one must be *very careful* when
they try to modify the attributes (such as increase or decrease the used capacity of a schedulabeEntity)
of an object.

An example in AbstractComparatorOrderingPolicy.java, Line63,

{code}
  protected void reorderSchedulableEntity(S schedulableEntity) {
    //remove, update comparable data, and reinsert to update position in order
    schedulableEntities.remove(schedulableEntity);
    updateSchedulingResourceUsage(
        schedulableEntity.getSchedulingResourceUsage());
    schedulableEntities.add(schedulableEntity);
  }
{code}

This method try to remove the schedulableEntity first and then insert it so as to reorder
the set. However, the changes of the schedulableEntity should be done in the middle of the
above two operations. But the comparator of the class is not clear, so we don't know which
attributes of the schedulableEntity was changed. If we changed the schedulableEntity outside
the method and then inform the orderingPolicy that we made such a change, the operation "schedulableEntities.remove(schedulableEntity)"
would not work since the element of a TreeSet is identified by comparator. Any implement class
of this abstract class should overwrite this method, but few does. AND, if we want to make
any modification of a schedulableEntity, we must remember the order: remove, modify the attributes(used
for comparing), insert.

YARN-897 is an example that we fell into the trap. If the comparator become complex in future,
e.g., we consider other types of resources in comparator, such traps will be more and disperse
anywhere, which makes it easy to let a TreeSet become a un-sorted state.



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

Mime
View raw message