调度深入解析
调度深入解析¶
注意：这份技术文档未针对用户阅读体验进行优化。
大多数 Dask 集合使用的默认共享内存调度器位于 dask/local.py 中。当新工作进程可用时，此调度器会动态地将任务分配给它们。它在共享内存环境中运行，不考虑数据本地性，所有工作进程都能平等地访问所有数据。
我们发现，通过尽量减少内存占用，可以更好地服务我们的工作负载。本文档介绍了我们在每任务一毫秒的调度预算内（无论任务数量多少）实现这一目标的策略。
通常我们面临以下情况：一个工作进程完成任务后返回。我们更新执行状态的数据结构，并需要为该工作进程提供一个新任务。通常有很多可用的任务，我们应该将哪个任务分配给工作进程呢？
问：我们应该将哪个可用任务分配给新就绪的工作进程？
这个问题简单而局部，但却极大地影响算法的性能。我们希望选择一个能让我们现在和将来都释放内存的任务。我们需要一种聪明且廉价的方式来打破可用任务集合之间的僵局。
在此阶段，我们选择“后进先出”的策略。也就是说，我们选择最近可用的任务，很可能是刚刚返回给我们的工作进程完成的任务使其可用。这鼓励了在开始新任务之前先完成当前任务的普遍主题。
我们使用堆栈来实现这一点。当一个工作进程完成任务后返回时，我们会找出现在可以使用新数据计算哪些新任务，并将这些任务（如果存在）放入堆栈顶部。我们从堆栈顶部取出一个项，并将其交给等待的工作进程。
然而，如果新完成的任务使多个新任务就绪，我们应该按什么顺序将它们放入堆栈呢？这是另一个打破僵局的机会。这在执行开始时尤其重要，因为我们通常会向堆栈添加大量叶子任务。在这种情况下我们的选择也极大地影响着许多情况下的性能。
我们希望鼓励深度优先的行为，即如果我们的计算由类似许多树的结构组成，我们希望在继续下一个子树之前完全探索一个子树。这鼓励我们的工作进程在继续处理新的块/子树之前先完成图中现有的块/子树。
因此，为了鼓励这种“深度优先的行为”，我们进行深度优先搜索（DFS），并根据节点在深度优先搜索遍历中的顺序为所有节点编号。我们在将任务添加到堆栈时使用此编号来打破僵局。请注意，虽然我们上面谈到了优化多独立子树的情况，但这种选择完全是局部的，并且在此情况之外也普遍适用。任何行为即使远程类似于多独立子树情况的任务都将从中受益，而且这种情况在正常工作负载中相当常见。
然而，我们忽略了另一个打破僵局的机会。执行深度优先搜索时，当我们到达一个有许多子节点的节点时，我们可以选择遍历子节点的顺序。我们通过选择其结果被最多节点依赖的子节点来解决这个僵局。这种依赖可以是直接的（对于将该数据作为输入的节点），也可以是间接的（对于图中任何祖先节点）。这强调优先遍历那些属于关键路径（具有依赖于此节点结果的长垂直链）的节点，以及其数据在未来被许多节点依赖的节点。在深度优先搜索中，我们选择首先深入这些子树，以便未来的计算不会因等待它们完成而受阻。
因此我们有三种打破僵局的策略
问：我应该运行这些可用任务中的哪一个？
答：后进先出
问：我应该先将这些任务中的哪一个放入堆栈？
答：在计算之前进行深度优先搜索，使用该顺序。
问：在执行深度优先搜索时，如何在子节点之间进行选择？
答：选择其数据被最多节点依赖的子节点
我们发现了需要每个这些决策的常见工作流类型。在数据分析中，我们尚未遇到一种常见的图类型，是这些启发式方法为了最小化内存使用目的而不能很好地处理的。