分布式系统中的调度与负载均衡

在本文中，我们将详细探讨分布式系统中关于调度和负载均衡的概念。

分布式系统中的调度问题：

在分布式系统中，用于安排各个进程执行顺序的技术有以下几种：

1. 任务分配方法：在任务分配方法中，用户提交的流程由多个相关的任务组成。这些任务被分配到系统中的适当节点上，从而提升整个系统的性能。
2. 负载均衡方法：顾名思义，负载均衡方法就是让系统中的各个节点之间分担工作负载。
3. 负载共享方法：在负载共享方法中，可以确保没有任何节点处于空闲状态，同时，各个进程在等待处理时也能得到有效的利用。

注意：The Task Assignment Approach finds less applicability
practically as it assumes that characteristics of processes
like inter-process communication cost, etc. must be known in advance.

优秀的调度算法的特点：

以下是一個優秀的調度算法所應具備的特徵：

• 那些需要用户事先了解所提交进程的相关属性和资源需求的调度算法，会给用户带来不必要的负担。因此，一个好的调度算法并不需要用户事先对提交给它的进程进行详细的说明或描述。
• 一个好的调度算法必须能够动态地调整各个进程的调度方式。因为随着时间的推移，将一个进程分配到某个系统上的初始安排可能会发生变化，从而需要重新调整各个进程的分配情况，以平衡系统的负载。
• 该算法必须足够灵活，能够在系统负载发生变化时仍能正确处理迁移相关的决策。
• 该算法必须具备稳定性，这样才能让处理器得到最有效的利用。只有当“thrashing”所产生的开销被最小化时，才能实现这一点。同时，在进程迁移过程中，也不应出现时间浪费的情况。
• 理想情况下，应选择那些能够快速做出决策的算法。比如启发式方法，因为它们所需的计算时间较短，因此能得出接近最优的解。而穷举搜索虽然可以找到最优解，但所需的时间则较长。
• 一个好的调度算法能够确保系统的性能保持平衡。因为，全局状态信息越少越好，因为全局状态信息与系统开销成正比关系。所以，随着全局状态信息的增加，系统开销也会随之增加。
• 该算法不应受到系统中一个或多个节点故障的影响。此外，即使某个连接出现故障，导致某个组的节点被分成两个或更多个组，该算法仍然能够正常运行。因此，该算法必须具备去中心化的决策能力，即仅考虑可用节点的意见来做出决策，从而确保系统的容错性。
• 一个好的调度算法具有可扩展性的特点。 当系统中的节点数量增加时，该系统具有灵活的扩展能力。 如果算法选择了一种策略，即先询问所有节点的负载情况，然后再选择负载最少的节点来承担任务，那么这种策略并不适合使用。因为这种方式会导致系统的可扩展性较差，尤其是在系统包含大量节点的情况下，这种策略显然无法有效运作。 原因是，查询者几乎会同时收到大量的回复。而处理这些回复所需的时间则很长，当节点数量增加时，这种处理方式就会变得非常低效。 一种简单的方法就是只检查N个节点中的m个节点。
• 一个好的调度算法必须能够确保服务的公平性。因为在试图平衡系统所有节点上的工作负载时，那些负担较重的节点可能会比负担较轻的节点获得更多的好处。因为与独立系统相比，这些节点面临的响应时间问题更为严重。因此，解决方案在于采用负载共享的概念，即让某个节点共享部分资源，从而确保用户不会受到任何影响。

分布式系统中的负载均衡：

负载均衡方法指的是在分布式系统的各个处理单元之间分配负载的过程。 某个处理单元所承受的额外负载会被分配给那些负担较轻的其他处理单元，具体分配方式则遵循既定的限制条件。 换句话说，每个处理单元中的负载都得到了有效的控制，从而避免了过载或闲置的情况发生。这样做可以最大化系统的吞吐量，而这也是分布式系统的最终目标。 这种方法使得所有处理单元都处于忙碌状态，从而加快了整个任务的完成速度。这样一来，所有处理器都可以几乎同时完成任务。

负载均衡算法的类型：

• 静态负载均衡算法：在静态负载均衡算法中，在分配负载时，并不会考虑系统的当前状态。与动态负载均衡算法相比，这类算法更为简单。静态负载均衡算法的类型如下：
  • 确定性算法：在确定性算法中，节点的属性以及各个进程的特性都会被考虑进去，以决定进程应该被分配到哪个节点上。由于这种算法的确定性特性，很难实现优化，从而获得更好的结果。此外，这种算法的实现成本也较高。
  • 概率性算法：这类算法会考虑系统的统计特性，比如各个节点的数量、网络拓扑结构等，以此来制定进程分配的规则。不过，这种方法的性能并不一定更好。
• 动态负载均衡算法：动态负载均衡算法会考虑系统中每个节点或计算单元的当前负载情况。通过动态地重新分配工作负载，将负载从过载的节点转移到负担较轻的节点上，从而实现更快的处理速度。 动态算法在设计中要困难得多，但它们能够带来更好的结果，尤其是在不同任务的执行时间差异较大的情况下。 此外，由于不需要专门用于处理任务分配的节点，因此动态负载均衡架构通常具有更模块化的结构。 动态负载均衡算法的类型如下：
  • 集中式处理：在集中式负载均衡算法中，处理进程调度的任务由中央服务器节点来承担。这种方式的优点在于效率较高，因为所有信息都存储在一个节点上。不过，这种方式的缺点在于可靠性较低，因为容错能力较差。此外，随着请求数量的增加，还会出现其他问题。
  • 在分布式负载均衡算法中，负责分配进程的任务被分散到系统的各个节点上。与集中式负载均衡算法不同，这种算法不需要存储状态信息。因此，其处理速度非常快。

分布式负载均衡算法的类型：

• 在协同负载均衡算法中，顾名思义，调度决策是在系统中各个实体的协作下做出的。这种方法的优点在于其稳定性。不过，其缺点在于计算复杂度较高，因此相比非协同算法而言，需要更多的资源来处理这些任务。
• 非合作式负载均衡算法：在这种算法中，调度决策是由系统中的各个独立实体来决定的，因为这些实体都是自主运作的。其优点在于，由于这种非合作式的运作方式，所需的资源消耗相对较小。不过，这种算法的稳定性可能不如合作式算法那么好。

在设计负载均衡算法时遇到的问题：

在设计负载均衡算法时，需要考虑许多因素：

• 负载估算策略：在分布式系统中，确定一个节点的负载情况。
• 流程转移政策：决定是进行本地处理还是远程处理。
• 国家信息交流：确定在分布式系统中，如何在不同节点之间交换系统负载信息的策略。
• 位置政策：确定用于进程迁移的目标节点。
• 优先分配：该选项用于确定在节点上，执行任务时应该优先处理本地进程还是远程进程。
• 迁移限制政策：用于确定进程迁移的限值。