1. 背景

默认情况下，FairScheduler对资源进行调度时，会使用FSParentQueue.assignContainer先对队列进行排序，然后再调度应用：

TreeSet<FSQueue> sortedChildQueues = new TreeSet<>(policy.getComparator());
    readLock.lock();
    try {
      long startDuration = System.nanoTime();
      sortedChildQueues.addAll(childQueues);
      scheduler.fsOpDurations.addACSortForPQCallDuration(
          System.nanoTime() - startDuration);
      for (FSQueue child : sortedChildQueues) {
        assigned = child.assignContainer(node);
        if (!Resources.equals(assigned, Resources.none())) {
          break;
        }
      }
    }

但是，经过美团文章：https://www.infoq.cn/article/dh5UpM_fJrtj1IgxQDsq的分析，FairScheduler会随着作业数、队列数的增加，排序时间线性增加。

其排序优化流程如下：

1. 将synchronized这种粗粒度锁优化称为读写锁，降低锁粒度。
2. 将排序流程从调度流程中独立出来，以异步并行线程的方式进行排序。

其流程如下：

本文将重点介绍异步并行线程实现思路。

2. 异步并行排序实现思路

首先，定义异步线程。其特征如下：

• 异步线程是死循环，以1ms间隔无限制地执行排序任务。
• 每次排序时，通过FairSchueduler获取rootQueue，并封装成为ScheduleSortInfo。
• 队列是一棵多叉树，在排序时，使用后续排序深度优先搜索。

首先，看看队列的数据结构。如下ScheduleSortInfo就是队列的具体信息。ScheduleSortInfo调用getChildren能够返回List<ScheduleSortInfo>，说明队列时多叉树：

public class ScheduleSortInfo implements Schedulable {

private List<ScheduleSortInfo> children;
public List<ScheduleSortInfo> getChildren() {
    return children;
  }
}

排序线程如下，其使用后续排序，通过深度优先搜索。最终rootSortInfo这棵树内的所有元素都是有序：

public void run() {
    while (!Thread.currentThread().isInterrupted()) {
      try {
        Thread.sleep(1);
        long start = System.nanoTime();
        //
        ScheduleSortInfo rootSortInfo =
            fsSortManager.getQueueManager().getRootQueue().getScheduleInfo();
        //开始排序，后序排序，深度优先搜索
        doFSRootQueueSort(rootSortInfo, fsSortManager.getSortThreadPool());

        try {
          sortedWriteLock.lock();
          currentSchedulingSortedChild = rootSortInfo.getChildren();
        } finally {
          sortedWriteLock.unlock();
        }

        fsSortManager.getFSOpDurations()
            .addFSSortCallDuration(System.nanoTime() - start);
      } catch (RejectedExecutionException e) {
        LOG.warn(
            "FSSort Thread interrupted. Exiting. RejectedExecutionException");
        return;
      } catch (InterruptedException e) {
        LOG.warn("FSSort Thread interrupted. Exiting. InterruptedException");
        return;
      } catch (Exception e) {
        LOG.error("Exception in fair scheduler FSSortThread", e);
      }
    }
  }

在进行调度时，进入FSParentQueue.assignContainer方法，获取异步线程排好序的子队列：

FSParentQueue定义新接口，直接获取排好序的子队列：

通过深度优先的方式获得叶子节点后，FSLeafQueue确认该节点是叶子节点，就开始分配任务：

public Resource assignContainer(FSSchedulerNode node,
                                  List<ScheduleSortInfo> sortInfoChildren) {
    Resource assigned = Resources.none();

    if (sortInfoChildren == null || sortInfoChildren.size() <= 0) {
      return assigned;
    }
    return assignContainer(node);
  }

流程结束。

3. 性能测试

使用SLS工具，分别对比未开并行排序和开启并行排序的FairScheduler。根据调度Container QPS 指标 ，预计提升 22 % 左右：

4. 指标review

将功能上线后，allocated container 提升， 高峰期 平均 400 -> 600， 提升 50%：

备注：CapcacityScheduler不用上线该patch，因为它支持多线程异步调度，不同线程会执行自己的排序流程，等同于并行排序。