← Back to branch summary

~0x44/nova/extdoc

« back to all changes in this revision

Viewing changes to nova/scheduler/least_cost.py

  • Committer: NTT PF Lab.
  • Date: 2010-12-24 11:38:49 UTC
  • mto: This revision was merged to the branch mainline in revision 564.
  • Revision ID: openstack@lab.ntt.co.jp-20101224113849-z9nemzmki17bxnvw
Support IPv6

Show diffs side-by-side

added added

removed removed

Lines of Context:
nova/scheduler/least_cost.py
1
 
# Copyright (c) 2011 Openstack, LLC.
2
 
# All Rights Reserved.
3
 
#
4
 
#    Licensed under the Apache License, Version 2.0 (the "License"); you may
5
 
#    not use this file except in compliance with the License. You may obtain
6
 
#    a copy of the License at
7
 
#
8
 
#         http://www.apache.org/licenses/LICENSE-2.0
9
 
#
10
 
#    Unless required by applicable law or agreed to in writing, software
11
 
#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12
 
#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13
 
#    License for the specific language governing permissions and limitations
14
 
#    under the License.
15
 
"""
16
 
Least Cost Scheduler is a mechanism for choosing which host machines to
17
 
provision a set of resources to. The input of the least-cost-scheduler is a
18
 
set of objective-functions, called the 'cost-functions', a weight for each
19
 
cost-function, and a list of candidate hosts (gathered via FilterHosts).
20
 
 
21
 
The cost-function and weights are tabulated, and the host with the least cost
22
 
is then selected for provisioning.
23
 
"""
24
 
 
25
 
 
26
 
import collections
27
 
 
28
 
from nova import flags
29
 
from nova import log as logging
30
 
from nova.scheduler import base_scheduler
31
 
from nova import utils
32
 
from nova import exception
33
 
 
34
 
LOG = logging.getLogger('nova.scheduler.least_cost')
35
 
 
36
 
FLAGS = flags.FLAGS
37
 
flags.DEFINE_list('least_cost_scheduler_cost_functions',
38
 
        ['nova.scheduler.least_cost.noop_cost_fn'],
39
 
        'Which cost functions the LeastCostScheduler should use.')
40
 
 
41
 
 
42
 
# TODO(sirp): Once we have enough of these rules, we can break them out into a
43
 
# cost_functions.py file (perhaps in a least_cost_scheduler directory)
44
 
flags.DEFINE_integer('noop_cost_fn_weight', 1,
45
 
             'How much weight to give the noop cost function')
46
 
flags.DEFINE_integer('compute_fill_first_cost_fn_weight', 1,
47
 
             'How much weight to give the fill-first cost function')
48
 
 
49
 
 
50
 
def noop_cost_fn(host):
51
 
    """Return a pre-weight cost of 1 for each host"""
52
 
    return 1
53
 
 
54
 
 
55
 
def compute_fill_first_cost_fn(host):
56
 
    """Prefer hosts that have less ram available, filter_hosts will exclude
57
 
    hosts that don't have enough ram.
58
 
    """
59
 
    hostname, service = host
60
 
    caps = service.get("compute", {})
61
 
    free_mem = caps.get("host_memory_free", 0)
62
 
    return free_mem
63
 
 
64
 
 
65
 
def normalize_list(L):
66
 
    """Normalize an array of numbers such that each element satisfies:
67
 
        0 <= e <= 1
68
 
    """
69
 
    if not L:
70
 
        return L
71
 
    max_ = max(L)
72
 
    if max_ > 0:
73
 
        return [(float(e) / max_) for e in L]
74
 
    return L
75
 
 
76
 
 
77
 
def weighted_sum(domain, weighted_fns, normalize=True):
78
 
    """Use the weighted-sum method to compute a score for an array of objects.
79
 
    Normalize the results of the objective-functions so that the weights are
80
 
    meaningful regardless of objective-function's range.
81
 
 
82
 
    domain - input to be scored
83
 
    weighted_fns - list of weights and functions like:
84
 
        [(weight, objective-functions)]
85
 
 
86
 
    Returns an unsorted list of scores. To pair with hosts do:
87
 
        zip(scores, hosts)
88
 
    """
89
 
    # Table of form:
90
 
    #   { domain1: [score1, score2, ..., scoreM]
91
 
    #     ...
92
 
    #     domainN: [score1, score2, ..., scoreM] }
93
 
    score_table = collections.defaultdict(list)
94
 
    for weight, fn in weighted_fns:
95
 
        scores = [fn(elem) for elem in domain]
96
 
        if normalize:
97
 
            norm_scores = normalize_list(scores)
98
 
        else:
99
 
            norm_scores = scores
100
 
        for idx, score in enumerate(norm_scores):
101
 
            weighted_score = score * weight
102
 
            score_table[idx].append(weighted_score)
103
 
 
104
 
    # Sum rows in table to compute score for each element in domain
105
 
    domain_scores = []
106
 
    for idx in sorted(score_table):
107
 
        elem_score = sum(score_table[idx])
108
 
        domain_scores.append(elem_score)
109
 
    return domain_scores
110
 
 
111
 
 
112
 
class LeastCostScheduler(base_scheduler.BaseScheduler):
113
 
    def __init__(self, *args, **kwargs):
114
 
        self.cost_fns_cache = {}
115
 
        super(LeastCostScheduler, self).__init__(*args, **kwargs)
116
 
 
117
 
    def get_cost_fns(self, topic):
118
 
        """Returns a list of tuples containing weights and cost functions to
119
 
        use for weighing hosts
120
 
        """
121
 
        if topic in self.cost_fns_cache:
122
 
            return self.cost_fns_cache[topic]
123
 
        cost_fns = []
124
 
        for cost_fn_str in FLAGS.least_cost_scheduler_cost_functions:
125
 
            if '.' in cost_fn_str:
126
 
                short_name = cost_fn_str.split('.')[-1]
127
 
            else:
128
 
                short_name = cost_fn_str
129
 
                cost_fn_str = "%s.%s.%s" % (
130
 
                        __name__, self.__class__.__name__, short_name)
131
 
            if not (short_name.startswith('%s_' % topic) or
132
 
                    short_name.startswith('noop')):
133
 
                continue
134
 
 
135
 
            try:
136
 
                # NOTE(sirp): import_class is somewhat misnamed since it can
137
 
                # any callable from a module
138
 
                cost_fn = utils.import_class(cost_fn_str)
139
 
            except exception.ClassNotFound:
140
 
                raise exception.SchedulerCostFunctionNotFound(
141
 
                        cost_fn_str=cost_fn_str)
142
 
 
143
 
            try:
144
 
                flag_name = "%s_weight" % cost_fn.__name__
145
 
                weight = getattr(FLAGS, flag_name)
146
 
            except AttributeError:
147
 
                raise exception.SchedulerWeightFlagNotFound(
148
 
                        flag_name=flag_name)
149
 
            cost_fns.append((weight, cost_fn))
150
 
 
151
 
        self.cost_fns_cache[topic] = cost_fns
152
 
        return cost_fns
153
 
 
154
 
    def weigh_hosts(self, topic, request_spec, hosts):
155
 
        """Returns a list of dictionaries of form:
156
 
           [ {weight: weight, hostname: hostname, capabilities: capabs} ]
157
 
        """
158
 
        cost_fns = self.get_cost_fns(topic)
159
 
        costs = weighted_sum(domain=hosts, weighted_fns=cost_fns)
160
 
 
161
 
        weighted = []
162
 
        weight_log = []
163
 
        for cost, (hostname, service) in zip(costs, hosts):
164
 
            caps = service[topic]
165
 
            weight_log.append("%s: %s" % (hostname, "%.2f" % cost))
166
 
            weight_dict = dict(weight=cost, hostname=hostname,
167
 
                    capabilities=caps)
168
 
            weighted.append(weight_dict)
169
 
 
170
 
        LOG.debug(_("Weighted Costs => %s") % weight_log)
171
 
        return weighted