Package haizea :: Package core :: Package scheduler :: Module mapper
[hide private]
[frames] | no frames]

Source Code for Module haizea.core.scheduler.mapper

  1  # -------------------------------------------------------------------------- # 
  2  # Copyright 2006-2009, University of Chicago                                 # 
  3  # Copyright 2008-2009, Distributed Systems Architecture Group, Universidad   # 
  4  # Complutense de Madrid (dsa-research.org)                                   # 
  5  #                                                                            # 
  6  # Licensed under the Apache License, Version 2.0 (the "License"); you may    # 
  7  # not use this file except in compliance with the License. You may obtain    # 
  8  # a copy of the License at                                                   # 
  9  #                                                                            # 
 10  # http://www.apache.org/licenses/LICENSE-2.0                                 # 
 11  #                                                                            # 
 12  # Unless required by applicable law or agreed to in writing, software        # 
 13  # distributed under the License is distributed on an "AS IS" BASIS,          # 
 14  # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   # 
 15  # See the License for the specific language governing permissions and        # 
 16  # limitations under the License.                                             # 
 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  # This dictionary provides a shorthand notation for any mappers 
 29  # included in this module (this shorthand notation can be used in 
 30  # the configuration file) 
 31  class_mappings = {"greedy": "haizea.core.scheduler.mapper.GreedyMapper"} 
 32   
33 -class Mapper(object):
34 """Base class for mappers 35 36 """ 37
38 - def __init__(self, slottable, policy):
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
86 -class GreedyMapper(Mapper):
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
120 - def __init__(self, slottable, policy):
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 # Generate an availability window at time "start" 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 # Get an ordered list of physical nodes 143 pnodes = self.policy.sort_hosts(nodes, start, lease) 144 145 # Get an ordered list of lease nodes 146 vnodes = self.__sort_vnodes(requested_resources) 147 148 # Get the leases that intersect with the requested interval. 149 leases = aw.get_leases_between(start, end) 150 # Ask the policy engine to sort the leases based on their 151 # preemptability 152 leases = self.policy.sort_leases(lease, leases, start) 153 154 preemptable_leases = leases 155 preempting = [] 156 157 # Try to find a mapping. Each iteration of this loop goes through 158 # all the lease nodes and tries to find a mapping. The first 159 # iteration assumes no leases can be preempted, and each successive 160 # iteration assumes one more lease can be preempted. 161 mapping = {} 162 done = False 163 while not done: 164 # Start at the first lease node 165 vnodes_pos = 0 166 cur_vnode = vnodes[vnodes_pos] 167 cur_vnode_capacity = requested_resources[cur_vnode] 168 maxend = end 169 170 # Go through all the physical nodes. 171 # In each iteration, we try to map as many lease nodes 172 # as possible into the physical nodes. 173 # "cur_vnode_capacity" holds the capacity of the vnode we are currently 174 # trying to map. "need_to_map" is the amount of resources we are 175 # trying to map into the current physical node (which might be 176 # more than one lease node). 177 for pnode in pnodes: 178 # need_to_map is initialized to the capacity of whatever 179 # lease node we are trying to map now. 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 # Try to fit as many lease nodes as we can into this physical node 185 pnode_done = False 186 while not pnode_done: 187 if avail.fits(need_to_map, until = maxend): 188 # In this case, we can fit "need_to_map" into the 189 # physical node. 190 mapping[cur_vnode] = pnode 191 vnodes_pos += 1 192 if vnodes_pos >= len(vnodes): 193 # No more lease nodes to map, we're done. 194 done = True 195 break 196 else: 197 # Advance to the next lease node, and add its 198 # capacity to need_to_map 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 # We couldn't fit the lease node. If we need to 204 # find a mapping that spans the entire requested 205 # interval, then we're done checking this physical node. 206 if strictend: 207 pnode_done = True 208 else: 209 # Otherwise, check what the longest interval 210 # we could fit in this physical node 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 # If there's no more leases that we could preempt, 221 # we're done. 222 if len(preemptable_leases) == 0: 223 done = True 224 elif not done: 225 # Otherwise, add another lease to the list of 226 # leases we are preempting 227 preempting.append(preemptable_leases.pop()) 228 229 if len(mapping) != len(requested_resources): 230 # No mapping found 231 return None, None, None 232 else: 233 return mapping, maxend, preempting
234
235 - def __sort_vnodes(self, requested_resources):
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 # Find the maximum requested resources for each resource type 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 # Normalize the capacities of the lease nodes (divide each 251 # requested amount of a resource type by the maximum amount) 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