OpenStack中的调度（Scheduler）算法初步研究

轉載:http://blog.sina.com.cn/s/blog_3fe961ae0100yqzd.html

Nova是OpenStack的云计算控制器，是Iaas系统的主要部分。
Nova中的调度模块scheduler文件夹下，其主要任务就是运用某种调度算法，选择出一个运算结点去执行VM instance。在nova版本2011.2中，scheduler模块下有以下几个文件：

__init__.py：
介绍nova.scheduler模块，没有实质性功能。

api.py：
模块对外提供的接口，负责处理所有关于调度的请求。

driver.py：
定义了Scheduler类，这是所有调度类的父类。子类必须实现Scheduler的schedule(self, context, topic, *_args, **_kwargs)函数（"Must override at least this method for scheduler to work."），然后才能实现自己的调度算法。

chance.py：
定义了ChanceScheduler类，是随机调度算法实现。下面是chance.py的部分源代码：

class ChanceScheduler(driver.Scheduler):
    """Implements Scheduler as a random node selector."""
 
    def schedule(self, context, topic, *_args, **_kwargs):
        """Picks a host that is up at random."""
        #首先得到所有开启的主机的一个列表
        hosts = self.hosts_up(context, topic)
        if not hosts:
            raise driver.NoValidHost(_("Scheduler was unable to locate a host"
                                       " for this request. Is the appropriate"
                                       " service running?"))
        #随机从主机列表中选择一个主机返回
        return hosts[int(random.random() * len(hosts))]

虽然代码挺简单的，但是很有意义，因为这是目前Nova默认的调度算法。

manager.py：
定义了SchedulerManager类，这是nova中默认的调度管理器（见http://docs.openstack.org/bexar/openstack-compute/admin/content/ch05s08.html 中的scheduler_manager项），这里定义了默认使用的调度算法。

Nova2011.2版本：
flags.DEFINE_string('scheduler_driver',
                    'nova.scheduler.chance.ChanceScheduler',
                    'Driver to use for the scheduler')
 
Nova2011.3版本：
flags.DEFINE_string('scheduler_driver',
                    'nova.scheduler.multi.MultiScheduler',
                    'Default driver to use for the scheduler')

可以看出，Nova 2011.2版中默认使用随机算法，Nova 2011.3版本使用了MultiScheduler类来调度，但事实上调用的还是随机算法。

simple.py：
定义了SimpleScheduler类，实现了最小负载调度算法，但这并不是默认的调度算法，并且这个类似乎没有覆写Scheduler类的schedule方法，估计是供nova团队后续开发使用的吧。
SimpleScheduler类中提供了三种最小负载的选择（三个函数）：
schedule_run_instance：选择运行实例最少的主机；
schedule_create_volume：选择容量最小的主机；
schedule_set_network_host：选择网络负载最小的主机。
从源代码中看来，这三个函数似乎没有实现“最小负载”，只是在循环中将每一台主机的负载值跟最大负载值比较，如果小于最大负载值，就返回主机。
zone.py：
定义了ZoneScheduler类，继承自ChanceScheduler类，实现了在一个可用区域里选择随机结点的调度算法。与ChanceScheduler类不同的是，ZoneScheduler首先选择出可用区域，然后根据可用区域得到主机列表，然后再随机取一台主机。

zone_manager.py：
ZoneManager类监督所有与子区域的通讯。

另外，Nova较新的版本应该是 2011.3，其中的scheduler模块发生了一些改变，增加了很多文件，默认的调度算法也修改了。
下面是2011.3版本中scheduler模块新增的一些文件：

multi.py：定义了MultiScheduler类，继承自driver.Scheduler类。显然这是2011.3中新实现的一个调度类，也是2011.3版本默认的调度类。这个类之所以叫“MultiScheduler”，顾名思义，它可以将不同的调用请求路由（routing）到不同的子调度器。
这似乎让人看到了新调度算法的一线希望，不过很遗憾的是，从源代码看来，MultiScheduler还是调用了ChanceScheduler（随机算法），所以我没有多加研究。

abstract_scheduler.py：
定义了AbsractScheduler类，继承自driver.Scheduler类，是个抽象类，用于在本地或区域间创建实例。子类需要覆写三个函数：filter_hosts() 、 weigh_hosts()和schedule()。weigh_hosts()根据需要对每个主机赋予不同的权值，filter_hosts()则可以根据权值生成合适的主机列表。AbsractScheduler中默认的实现仅仅是将每台主机的权值设置为相同的，并返回包含所有主机的列表。

base_scheduler.py：
定义了BaseScheduler类，继承自AbsractScheduler类。如上所述，BaseScheduler覆写了filter_hosts() 和 weigh_hosts()方法。

另外还有其它一些文件：

host_filter.py、least_cost.py、vsa.py。

总结：目前nova的默认调度方法还是随机算法。
如果想修改默认的算法的话，应该首先要实现自己的算法调度器，然后将manager.py开头部分的flags变量修改成自己的算法实现。
如下：
Nova2011.2版本：

flags.DEFINE_string('scheduler_driver',
                    #修改这个变量
                    'nova.scheduler.chance.ChanceScheduler',
                    'Driver to use for the scheduler')

Nova2011.3版本：

flags.DEFINE_string('scheduler_driver',
                    #修改这个变量
                    'nova.scheduler.multi.MultiScheduler',
                    'Default driver to use for the scheduler')

官方的修改方法目前还没有研究清楚，大体上是通过修改配置来实现的。在官方网站上找到一篇讲解分布式调度算法的文章，还没有来得及看，先记录一下：http://nova.openstack.org/devref/distributed_scheduler.html 。