[YARN-10178] Global Scheduler async thread crash caused by 'Comparison method violates its general contract

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 3.2.1
• Fix Version/s: 3.4.0, 2.10.2, 3.3.2, 3.2.4
• Component/s: capacity scheduler
• Target Version/s: 3.4.0
• Assignee: Andras Gyori
• Reporter: tuyu
• Created: 03/Mar/20 06:22
• Updated: 04/Jan/22 22:42
• Resolved: 21/Dec/21 19:56

Description

Global Scheduler Async Thread crash stack

ERROR org.apache.hadoop.yarn.server.resourcemanager.ResourceManager: Received RMFatalEvent of type CRITICAL_THREAD_CRASH, caused by a critical thread, Thread-6066574, that exited unexpectedly: java.lang.IllegalArgumentException: Comparison method violates its general contract!                                                                     at java.util.TimSort.mergeHi(TimSort.java:899)
        at java.util.TimSort.mergeAt(TimSort.java:516)
        at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
        at java.util.TimSort.sort(TimSort.java:254)
        at java.util.Arrays.sort(Arrays.java:1512)
        at java.util.ArrayList.sort(ArrayList.java:1462)
        at java.util.Collections.sort(Collections.java:177)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.policy.PriorityUtilizationQueueOrderingPolicy.getAssignmentIterator(PriorityUtilizationQueueOrderingPolicy.java:221)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.ParentQueue.sortAndGetChildrenAllocationIterator(ParentQueue.java:777)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.ParentQueue.assignContainersToChildQueues(ParentQueue.java:791)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.ParentQueue.assignContainers(ParentQueue.java:623)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.CapacityScheduler.allocateOrReserveNewContainers(CapacityScheduler.java:1635)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.CapacityScheduler.allocateContainerOnSingleNode(CapacityScheduler.java:1629)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.CapacityScheduler.allocateContainersToNode(CapacityScheduler.java:1732)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.CapacityScheduler.allocateContainersToNode(CapacityScheduler.java:1481)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.CapacityScheduler.schedule(CapacityScheduler.java:569)
        at org.apache.hadoop.yarn.server.resourcemanager.scheduler.capacity.CapacityScheduler$AsyncScheduleThread.run(CapacityScheduler.java:616)

JAVA 8 Arrays.sort default use timsort algo, and timsort has few require

1.x.compareTo(y) != y.compareTo(x)
2.x>y,y>z --> x > z
3.x=y, x.compareTo(z) == y.compareTo(z)

if not Arrays paramters not satify this require,TimSort will throw 'java.lang.IllegalArgumentException'

look at PriorityUtilizationQueueOrderingPolicy.compare function,we will know Capacity Scheduler use this these queue resource usage to compare

AbsoluteUsedCapacity
UsedCapacity
ConfiguredMinResource
AbsoluteCapacity

In Capacity Scheduler Global Scheduler AsyncThread use PriorityUtilizationQueueOrderingPolicy function to choose queue to assign container,and construct a CSAssignment struct, and use submitResourceCommitRequest function add CSAssignment to backlogs

ResourceCommitterService will tryCommit this CSAssignment,look tryCommit function,there will update queue resource usage

public boolean tryCommit(Resource cluster, ResourceCommitRequest r,
    boolean updatePending) {
  long commitStart = System.nanoTime();
  ResourceCommitRequest<FiCaSchedulerApp, FiCaSchedulerNode> request =
      (ResourceCommitRequest<FiCaSchedulerApp, FiCaSchedulerNode>) r;
 
  ...
  boolean isSuccess = false;
  if (attemptId != null) {
    FiCaSchedulerApp app = getApplicationAttempt(attemptId);
    // Required sanity check for attemptId - when async-scheduling enabled,
    // proposal might be outdated if AM failover just finished
    // and proposal queue was not be consumed in time
    if (app != null && attemptId.equals(app.getApplicationAttemptId())) {
      if (app.accept(cluster, request, updatePending)
          && app.apply(cluster, request, updatePending)) { // apply this resource
        ...
        }
    }
  }
  return isSuccess;
}
}

public boolean apply(Resource cluster, ResourceCommitRequest<FiCaSchedulerApp,
    FiCaSchedulerNode> request, boolean updatePending) {
...
    if (!reReservation) {
        getCSLeafQueue().apply(cluster, request); 
    }
...
}

LeafQueue.apply invok allocateResource

void allocateResource(Resource clusterResource,
    Resource resource, String nodePartition) {
  try {
    writeLock.lock(); // only lock leaf queue lock
    queueUsage.incUsed(nodePartition, resource);
 
    ++numContainers;
 
    CSQueueUtils.updateQueueStatistics(resourceCalculator, clusterResource,
        this, labelManager, nodePartition); // there will update queue statistics
  } finally {
    writeLock.unlock();
  }
}

we found ResourceCommitterService will only lock leaf queue to update queue statistics, but AsyncThread use sortAndGetChildrenAllocationIterator only lock queue root queue lock

ParentQueue.java
private Iterator<CSQueue> sortAndGetChildrenAllocationIterator(
      String partition) {
    try {
      readLock.lock();
      return queueOrderingPolicy.getAssignmentIterator(partition);
    } finally {
      readLock.unlock();
    }
  }

so if multi async thread compare queue usage statistics and ResourceCommitterService apply leaf queue change statistics concurrent, will break TimSort algo required, and cause thread crash

Issue Links

• fixes: YARN-8737 Race condition in ParentQueue when reinitializing and sorting child queues in the meanwhile
• is related to: YARN-10058 Capacity Scheduler dispatcher hang when async thread crash