in 分布式数据库 数据库 ~ read.

调度器调度算法

继上次讲调度器, 这次简单描述一下所知的两种调度方式

plantree

一次性调度(AllAtOnce)

顺序发送所有Fragment,无明显顺序要求

自root递归遍历整个PlanTree,将各个FragmentID放入容器中,得到一个自leaf至root的有序集合;
对这个集合顺序执行调度

stage5 -> stage4 -> stage3 -> stage2 -> stage1 -> stage0

适用于,对延迟敏感的场景。一次性使所有任务得到并发执行,可以充分利用CPU,使CPU时钟开销最小化,一旦数据可用,就能被立即处理。

分阶段调度(Phased)

将所有的Fragment划分成不同的Phased,按Phased进行调度

所有的FragmentID放在图中的顶点,为这些顶点添加边:

  • 有先后依赖关系
    • Join的build到probe有一条边,因先构建Hash表
  • 从RemoteSourceNode到它的SourceFragment有一条边
  • 先遍历的节点到后遍历的节点有一条边

最终构成一个图,图中的每个强连通图,就是一个Phased

  • 每个Phased至少包含一个Source(ScanNode)
Phased0:  stage0 -> stage1 -> stage2 -> stage3
Phased1:                   -> stage4 -> stage5

确定了紧密连接的单元,这些单元同时启动避免死锁,同时由于分阶段调度,使得内存使用效率更高,一定程度上避免了CPU的空消耗。

实际案例

sql

对应的PlanTree大致如下

plans

  • AllAtOnce

stage5 -> stage4 -> stage3 -> stage2 -> stage8 -> stage7 -> stage6 -> stage1 -> stage0

  • Phased
stage0 -> stage1 -> stage2 -> stage3 -> stage5
                                     -> stage4
                           -> stage6 -> stage8
                                     -> stage7