首页 理论教育分布式数据库技术-负载均衡解决方案

分布式数据库技术-负载均衡解决方案

【摘要】:负载均衡在分布式和并行环境中都很受关注,在并行计算中尤为重要。因此负载均衡很重要。让负载均衡最小化是有效实现并行结构的关键任务。负载均衡策略有以下四个问题需要考虑。1)扩散方法扩散方法中,每个过载的处理器将其一部分负载传给低载的邻居处理器,实现局部负载均衡。3)基于排队理论的方法基于排队理论的方法试图用排队论和概率论来解决负载均衡问题。

负载均衡在分布式和并行环境中都很受关注,在并行计算中尤为重要。

超级计算机和集群机都需要进行适当调节,使性能达到所期待的程度。并行分割成固定数目的进程并运行在并行节点上,每个进程完成一部分工作。如果负载不均衡,则有的节点很快完成了任务,有的则要很长时间才能完成。因此负载均衡很重要。

让负载均衡最小化是有效实现并行结构的关键任务。负载均衡策略有以下四个问题需要考虑。

●可以使用哪些负载信息?

●平衡的条件,即何时平衡?

●选哪个节点做平衡决策

●如何管理负载迁移?

按照这四个要点,参考文献[3]深入讨论了负载均衡策略问题。

可以在任何进程执行之前静态制定负载均衡决策,也可以在进程执行期间动态制定决策。静态方法检查计算负载的全局分布过程,在进程执行前指定将哪个负载交由哪个资源。动态方法检查资源计算过程,并与资源使用期望相比实时进行调整。

1.确定性方法

确定性方法(deterministic methods)是按照预先定义的策略迭代方式实施。确定性方法又可以分为扩散方法(diffusion methods)、维度交换方法(dimension change methods)、梯度模型方法(gradient model methods)和最小方向方法(minimum-direction methods)等。扩散方法中的处理器每一步都和所有邻居交换负载。维度交换方法中的处理器按照一张表一次性地和邻居交换负载,再使用新的负载和下一个邻居交换。梯度模型方法中的处理器沿着系统里负载最小的方向传输过剩的负载。最小方向方法在基础范围内选择负载最小的处理器作为目的处理器。

1)扩散方法

扩散方法中,每个过载的处理器将其一部分负载传给低载的邻居处理器,实现局部负载均衡。整个过程是一个迭代过程,直至达到一个稳定的平衡。处理器被组织成一个网格,就像一个空间坐标一样,最相邻的节点间进行交换。坐标系统和并行体系结构对应,相对来说,处理器的相邻程度与通信容易相关。

2)维度交换方法(www.chuimin.cn)

维度交换方法是在涉及超立方体结构并行系统时开始研究,每个处理器的邻居按照超立方体的每一维来审视。每次处理器检查自己的负载和与一个邻居进行交换,一旦遍历所有的邻居(即超级立方体的一维),负载均衡策略的迭代过程则记为休眠(sweep)。后来,该方法扩展到其他体系结构。

3)梯度模型方法

梯度模型方法中,由网络中处理器的负载区别构成一个梯度。梯度模型方法和维度交换方法的主要区别是,前者是负载迁移到整个网络负载最小的处理器中,后者是迭代地与相邻处理器进行交换。梯度模型方法也有缺陷。如果将处理器中最重的负载传给负载最小的处理器,则会产生一个巨大的扰动,可能一个处理器中的负载突然变得很轻(例如,当前一个作业完成)。如果只有几个轻载处理器,那么多个过载处理器会将部分负载传给欠载的处理器,产生溢出效应(overflow effect)。溢出效应是将一个原本欠载的处理器马上变得过载。

4)最小方向方法

最小方向方法里,选择域中使用最少的处理器作为负载传输的目标处理器。可以将一个域设置成只含两个处理器的最小组,也可以设置为整个系统。

2.随机方法

负载采用随机方法(stochastic methods)分布,以使系统进入一种高概率的均衡状态。随机方法负载均衡可以分成三类:随机分配方法(randomized allocation methods)、基于物理优化的方法(physical optimization based methods)和基于排队理论的方法(queuing theory based methods)。

1)随机分配方法

随机分配方法是随机选择一个处理器,以迁移某些负载。不像确定性方法,这类方法很少依靠系统状态信息。处理器可以在直接邻居里随机选择,也可在包括远程邻居的所有处理器里随机选择。

2)基于物理优化的方法

基于物理优化的方法将一个负载均衡问题映射成一个组合优化问题,如模拟退火法(simulated annealing)、基因算法(genetic algorithm)等。基于物理优化的方法的缺点是计算开销大,且要求在有限时间里实现负载均衡。

3)基于排队理论的方法

基于排队理论的方法试图用排队论和概率论来解决负载均衡问题。