负载均衡

在计算中，负载平衡是将一组任务分配到一组资源（计算单元）上的过程，目的是使它们的整体处理更有效率。负载均衡可以优化响应时间，避免一些计算节点不均匀地过载而其他计算节点处于空闲状态。

负载均衡是并行计算机领域的研究课题。存在两种主要方法：静态算法，不考虑不同机器的状态；动态算法，通常更通用、更高效，但需要在不同计算单元之间交换信息，有丢失的风险 的效率。

负载平衡算法总是试图回答特定问题。除其他事项外，必须考虑任务的性质、算法的复杂性、运行算法的硬件架构以及所需的容错能力。因此，必须找到妥协以xxx地满足特定于应用程序的要求。

负载平衡算法的效率主要取决于任务的性质。因此，决策时可获得的任务信息越多，优化的潜力就越大。

完美了解每个任务的执行时间可以达到最佳负载分配。不幸的是，这实际上是一个理想化的案例。知道每个任务的准确执行时间是极其罕见的情况。

出于这个原因，有几种技术可以了解不同的执行时间。首先，在任务大小相对均匀的幸运场景中，可以考虑每个任务大约需要平均执行时间。另一方面，如果执行时间非常不规则，则必须使用更复杂的技术。一种技术是向每个任务添加一些元数据。根据类似元数据的先前执行时间，可以根据统计信息对未来的任务进行推断。

在某些情况下，任务相互依赖。这些相互依赖性可以通过有向无环图来说明。直觉上，有些任务只有在其他任务完成后才能开始。

假设预先知道每个任务所需的时间，则最佳执行顺序必须导致总执行时间最小化。

尽管这是一个 NP-hard 问题，因此很难准确求解。有一些算法，如作业调度程序，可以使用元启发式方法计算最佳任务分布。

对于负载平衡算法设计至关重要的任务的另一个特征是它们能够在执行期间分解为子任务。后面介绍的树形计算算法就充分利用了这种特殊性。

当负载平衡算法不考虑系统状态以分配任务时，它是静态的。因此，系统状态包括某些处理器的负载级别（有时甚至过载）等度量。相反，预先对整个系统做出假设，例如传入任务的到达时间和资源需求。

此外，处理器的数量、它们各自的功率和通信速度都是已知的。因此，静态负载平衡旨在将一组已知任务与可用处理器相关联，以最小化某个性能函数。诀窍在于这个性能函数的概念。

静态负载平衡技术通常集中在路由器或 Master 周围，它分配负载并优化性能功能。这种最小化可以考虑与要分配的任务相关的信息，并得出预期的执行时间。

静态算法的优点是它们易于设置并且在相当常规的任务（例如处理来自网站的 HTTP 请求）的情况下非常有效。然而，任务分配中仍然存在一些统计差异，这可能导致某些计算单元过载。

与静态负载分配算法不同，动态算法考虑了系统中每个计算单元（也称为节点）的当前负载。在这种方法中，任务可以动态地从过载节点移动到负载不足的节点，以便接收更快的处理。虽然这些算法的设计要复杂得多，但它们可以产生出色的结果，尤其是当执行时间因任务而异时。