aurora-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jordan Ly (JIRA)" <>
Subject [jira] [Created] (AURORA-1949) PreemptionVictimFilterImpl comparator violates transitivity causing exceptions
Date Tue, 26 Sep 2017 23:10:00 GMT
Jordan Ly created AURORA-1949:

             Summary: PreemptionVictimFilterImpl comparator violates transitivity causing
                 Key: AURORA-1949
             Project: Aurora
          Issue Type: Bug
          Components: Scheduler
            Reporter: Jordan Ly
            Priority: Critical

The PreemptionVictimFilterImpl uses a comparator to sort ResourceBags in order to preempt
the biggest tasks first when searching for a victim. However, the current implementation causes
an exception which causes the Scheduler to fail:

SEVERE: Service PreemptorService [FAILED] has failed in the RUNNING state.
java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeLo(
        at java.util.TimSort.mergeAt(
        at java.util.TimSort.mergeCollapse(
        at java.util.TimSort.sort(
        at java.util.Arrays.sort(
        at org.apache.aurora.scheduler.preemptor.PreemptionVictimFilter$PreemptionVictimFilterImpl.filterPreemptionVictims(
        at org.apache.aurora.scheduler.preemptor.PendingTaskProcessor.lambda$run$0(
        at org.mybatis.guice.transactional.TransactionalMethodInterceptor.invoke(
        at org.apache.aurora.common.inject.TimedInterceptor.invoke(
        at org.apache.aurora.common.inject.TimedInterceptor.invoke(
        at org.apache.aurora.scheduler.preemptor.PreemptorModule$PreemptorService.runOneIteration(
        at java.util.concurrent.Executors$
        at java.util.concurrent.FutureTask.runAndReset(
        at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.access$301(
        at java.util.concurrent.ScheduledThreadPoolExecutor$
        at java.util.concurrent.ThreadPoolExecutor.runWorker(
        at java.util.concurrent.ThreadPoolExecutor$

Looking at the code, it seems it violates transitivity:

    static final Ordering<ResourceBag> ORDER = new Ordering<ResourceBag>() {
      public int compare(ResourceBag left, ResourceBag right) {
        Set<ResourceType> types = ImmutableSet.<ResourceType>builder()
            .addAll(left.streamResourceVectors().map(e -> e.getKey()).iterator())
            .addAll(right.streamResourceVectors().map(e -> e.getKey()).iterator())

        boolean allZero = true;
        boolean allGreaterOrEqual = true;
        boolean allLessOrEqual = true;

        for (ResourceType type : types) {
          int compare = left.valueOf(type).compareTo(right.valueOf(type));
          if (compare != 0) {
            allZero = false;

          if (compare < 0) {
            allGreaterOrEqual = false;

          if (compare > 0) {
            allLessOrEqual = false;

        if (allZero) {
          return 0;

        if (allGreaterOrEqual) {
          return 1;

        if (allLessOrEqual) {
          return -1;

        return 0;

The example below illustrates the error:

Resource: X Y Z
Bag A:       2 0 2
Bag B:       1 2 1
Bag C:       2 2 1

We can see that A = B, B < C, and C = A which would cause an exception.

There are a couple of routes we can take to solve this. What we really want is to be able
to define partial ordering (comparator does total ordering) so we can do a topological sort.
Additionally, we can give priority to particular resources (Dominant Resource Fairness).

This message was sent by Atlassian JIRA

View raw message