1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 """This module provides the base class for writing custom "mappers" and the
20 default greedy mapper used in Haizea. A mapper is a class with a single function
21 "map" that takes a set of requested resources (typically corresponding to
22 VMs) and maps them to physical nodes (if such a mapping exists).
23 """
24
25 from haizea.common.utils import abstract
26 import operator
27
28
29
30
31 class_mappings = {"greedy": "haizea.core.scheduler.mapper.GreedyMapper"}
32
34 """Base class for mappers
35
36 """
37
39 """Constructor
40
41 Arguments
42 slottable -- A fully constructed SlotTable
43 policy -- A fully constructed PolicyManager
44 """
45 self.slottable = slottable
46 self.policy = policy
47
48
49 - def map(self, requested_resources, start, end, strictend, onlynodes = None):
50 """The mapping function
51
52 The mapping function takes a set of requested resources and maps
53 them to physical resources (based on the availability
54 in the slot table) in a specified time interval. The mapper
55 may return a mapping that only satisfies part of the specified
56 time interval.
57
58 Arguments:
59 requested_resources -- A dictionary mapping lease nodes (integers) to
60 ResourceTuples (representing the desired amount of resources for
61 that lease node)
62 start -- Starting time of the interval during which the resources
63 are required
64 end -- Ending time of the interval
65 strictend -- If True, the only valid mappings are those that span
66 the entire requested interval. If False, the mapper is allowed to
67 return mappings that only span part of the interval (this reduced
68 interval must always start at "start"; the earlier end time is
69 returned as a return value)
70 onlynodes -- List of physical nodes. Only look for a mapping in
71 these nodes.
72
73 Returns:
74 mapping -- A dictionary mapping lease nodes to physical nodes
75 maxend -- The end of the interval for which a mapping was found.
76 As noted in argument "strictend", this return value might not
77 be the same as "end"
78 preempting -- Leases that would have to be preempted for the
79 mapping to be valid.
80
81 If no mapping is found, the three return values are set to None
82 """
83 abstract()
84
85
87 """Haizea's default greedy mapper
88
89 Haizea uses a greedy algorithm to determine how VMs are mapped to
90 physical resources at a specific point in time (determining that point
91 in time, when using best-effort scheduling, is determined in the lease
92 and VM scheduling classes).
93
94 The way the algorithm works is by, first, greedily ordering the
95 physical nodes from "most desirable" to "least desirable". For example,
96 a physical node with no leases scheduled on it in the future is preferable
97 to one with leases (since this reduces the probability of having to
98 preempt leases to obtain a mapping). This ordering, however, is done by the
99 policy engine (see the GreedyPolicy class in the host_selection module) so,
100 to be a truly greedy algorithm, this mapper must be used in conjunction with
101 the "greedy" host selection policy).
102
103 Then, the algorithm traverses the list of nodes and tries to map as many
104 lease nodes into each physical node before moving on to the next. If
105 the list of physical nodes is exhausted without finding a mapping for all
106 the lease nodes, then the algorithm tries to find a mapping by preempting
107 other leases.
108
109 Before doing this, the mapper must first determine what leases could be
110 preempted. This decision is delegated to the policy engine, which returns
111 a list of leases ordered from "most preemptable" to "least preemptable".
112 The mapper attempts a mapping assuming that the first lease is going
113 to be preempted, then assuming the first and the second, etc.
114
115 If no mapping is found with preemption, then there is no mapping at the
116 requested time.
117
118 """
119
121 """Constructor
122
123 Arguments
124 slottable -- A fully constructed SlotTable
125 policy -- A fully constructed PolicyManager
126 """
127 Mapper.__init__(self, slottable, policy)
128
129 - def map(self, lease, requested_resources, start, end, strictend, onlynodes=None):
130 """The mapping function
131
132 See documentation in Mapper for more details
133 """
134
135
136 aw = self.slottable.get_availability_window(start)
137
138 nodes = aw.get_nodes_at(start)
139 if onlynodes != None:
140 nodes = list(set(nodes) & onlynodes)
141
142
143 pnodes = self.policy.sort_hosts(nodes, start, lease)
144
145
146 vnodes = self.__sort_vnodes(requested_resources)
147
148
149 leases = aw.get_leases_between(start, end)
150
151
152 leases = self.policy.sort_leases(lease, leases, start)
153
154 preemptable_leases = leases
155 preempting = []
156
157
158
159
160
161 mapping = {}
162 done = False
163 while not done:
164
165 vnodes_pos = 0
166 cur_vnode = vnodes[vnodes_pos]
167 cur_vnode_capacity = requested_resources[cur_vnode]
168 maxend = end
169
170
171
172
173
174
175
176
177 for pnode in pnodes:
178
179
180 need_to_map = self.slottable.create_empty_resource_tuple()
181 need_to_map.incr(cur_vnode_capacity)
182 avail=aw.get_ongoing_availability(start, pnode, preempted_leases = preempting)
183
184
185 pnode_done = False
186 while not pnode_done:
187 if avail.fits(need_to_map, until = maxend):
188
189
190 mapping[cur_vnode] = pnode
191 vnodes_pos += 1
192 if vnodes_pos >= len(vnodes):
193
194 done = True
195 break
196 else:
197
198
199 cur_vnode = vnodes[vnodes_pos]
200 cur_vnode_capacity = requested_resources[cur_vnode]
201 need_to_map.incr(cur_vnode_capacity)
202 else:
203
204
205
206 if strictend:
207 pnode_done = True
208 else:
209
210
211 latest = avail.latest_fit(need_to_map)
212 if latest == None:
213 pnode_done = True
214 else:
215 maxend = latest
216
217 if done:
218 break
219
220
221
222 if len(preemptable_leases) == 0:
223 done = True
224 elif not done:
225
226
227 preempting.append(preemptable_leases.pop())
228
229 if len(mapping) != len(requested_resources):
230
231 return None, None, None
232 else:
233 return mapping, maxend, preempting
234
236 """Sorts the lease nodes
237
238 Greedily sorts the lease nodes so the mapping algorithm
239 will first try to map those that require the highest
240 capacity.
241 """
242
243
244 max_res = self.slottable.create_empty_resource_tuple()
245 for res in requested_resources.values():
246 for i in range(len(res._single_instance)):
247 if res._single_instance[i] > max_res._single_instance[i]:
248 max_res._single_instance[i] = res._single_instance[i]
249
250
251
252 norm_res = {}
253 for k,v in requested_resources.items():
254 norm_capacity = 0
255 for i in range(len(max_res._single_instance)):
256 if max_res._single_instance[i] > 0:
257 norm_capacity += v._single_instance[i] / float(max_res._single_instance[i])
258 norm_res[k] = norm_capacity
259
260 vnodes = norm_res.items()
261 vnodes.sort(key=operator.itemgetter(1), reverse = True)
262 vnodes = [k for k,v in vnodes]
263 return vnodes
264