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