1489b91d72cd225e902081dbd3f9e47448fe867f6Prashanth B# Copyright (c) 2014 The Chromium OS Authors. All rights reserved. 2489b91d72cd225e902081dbd3f9e47448fe867f6Prashanth B# Use of this source code is governed by a BSD-style license that can be 3489b91d72cd225e902081dbd3f9e47448fe867f6Prashanth B# found in the LICENSE file. 4489b91d72cd225e902081dbd3f9e47448fe867f6Prashanth B 5cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps"""RDB utilities. 6cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 7cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beepsDo not import rdb or autotest modules here to avoid cyclic dependencies. 8cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps""" 9cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 1052a239316b829106b540e57a0100496fed1fe5aaFang Dengimport collections 1152a239316b829106b540e57a0100496fed1fe5aaFang Deng 1252a239316b829106b540e57a0100496fed1fe5aaFang Dengimport common 1352a239316b829106b540e57a0100496fed1fe5aaFang Dengfrom autotest_lib.client.common_lib import priorities 145e2efb71ffebead22aa4f0744ad843ee79814b43Dan Shifrom autotest_lib.client.common_lib import utils 155e2efb71ffebead22aa4f0744ad843ee79814b43Dan Shi 165e2efb71ffebead22aa4f0744ad843ee79814b43Dan Shitry: 175e2efb71ffebead22aa4f0744ad843ee79814b43Dan Shi from chromite.lib import metrics 185e2efb71ffebead22aa4f0744ad843ee79814b43Dan Shiexcept ImportError: 195e2efb71ffebead22aa4f0744ad843ee79814b43Dan Shi metrics = utils.metrics_mock 2052a239316b829106b540e57a0100496fed1fe5aaFang Deng 217224dcb367e8f0f33526a0901713e533234be42fxixuan 222d8047e8b2d901bec66d483664d8b6322501d245Prashanth BRDB_STATS_KEY = 'rdb' 23cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 24cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beepsclass RDBException(Exception): 25cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps """Generic RDB exception.""" 26cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 27489b91d72cd225e902081dbd3f9e47448fe867f6Prashanth B def wire_format(self, **kwargs): 28cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps """Convert the exception to a format better suited to an rpc response. 29cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps """ 30cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps return str(self) 31cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 32cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 332d8047e8b2d901bec66d483664d8b6322501d245Prashanth Bclass CacheMiss(RDBException): 342d8047e8b2d901bec66d483664d8b6322501d245Prashanth B """Generic exception raised for a cache miss in the rdb.""" 352d8047e8b2d901bec66d483664d8b6322501d245Prashanth B pass 362d8047e8b2d901bec66d483664d8b6322501d245Prashanth B 372d8047e8b2d901bec66d483664d8b6322501d245Prashanth B 38b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth Bclass LabelIterator(object): 39b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B """An Iterator for labels. 40cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 41cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps Within the rdb any label/dependency comparisons are performed based on label 42cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps ids. However, the host object returned needs to contain label names instead. 43b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B This class returns label ids for iteration, but a list of all label names 44b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B when accessed through get_label_names. 45cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps """ 46cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 47b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B def __init__(self, labels): 48b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B self.labels = labels 49b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B 50cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 51b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B def __iter__(self): 52b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B return iter(label.id for label in self.labels) 53cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 54cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 55b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B def get_label_names(self): 56b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B """Get all label names of the labels associated with this class. 57cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 58cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps @return: A list of label names. 59cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps """ 60b474fdfd353cdb0888191f4b80e47e6b5343d891Prashanth B return [label.name for label in self.labels] 61cc9fc70587d37775673e47b3dcb4d6ded0c6dcb4beeps 6252a239316b829106b540e57a0100496fed1fe5aaFang Deng 6352a239316b829106b540e57a0100496fed1fe5aaFang Dengclass RequestAccountant(object): 6452a239316b829106b540e57a0100496fed1fe5aaFang Deng """A helper class that count requests and manages min_duts requirement. 6552a239316b829106b540e57a0100496fed1fe5aaFang Deng 6652a239316b829106b540e57a0100496fed1fe5aaFang Deng On initialization, this object takes a list of host requests. 6752a239316b829106b540e57a0100496fed1fe5aaFang Deng It will batch the requests by grouping similar requests together 6852a239316b829106b540e57a0100496fed1fe5aaFang Deng and generate a mapping from unique request-> count of the request. 6952a239316b829106b540e57a0100496fed1fe5aaFang Deng It will also generates a mapping from suite_job_id -> min_duts. 7052a239316b829106b540e57a0100496fed1fe5aaFang Deng 7152a239316b829106b540e57a0100496fed1fe5aaFang Deng RDB does a two-round of host aquisition. The first round attempts 7252a239316b829106b540e57a0100496fed1fe5aaFang Deng to get min_duts for each suite. The second round attemps to satisfy 7352a239316b829106b540e57a0100496fed1fe5aaFang Deng the rest requests. RDB calls get_min_duts and get_rest to 7452a239316b829106b540e57a0100496fed1fe5aaFang Deng figure out how many duts it should attempt to get for a unique 7552a239316b829106b540e57a0100496fed1fe5aaFang Deng request in the first and second round respectively. 7652a239316b829106b540e57a0100496fed1fe5aaFang Deng 7752a239316b829106b540e57a0100496fed1fe5aaFang Deng Assume we have two distinct requests 7852a239316b829106b540e57a0100496fed1fe5aaFang Deng R1 (parent_job_id: 10, need hosts: 2) 7952a239316b829106b540e57a0100496fed1fe5aaFang Deng R2 (parent_job_id: 10, need hosts: 4) 8052a239316b829106b540e57a0100496fed1fe5aaFang Deng And parent job P (job_id:10) has min dut requirement of 3. So we got 8152a239316b829106b540e57a0100496fed1fe5aaFang Deng requests_to_counts = {R1: 2, R2: 4} 8252a239316b829106b540e57a0100496fed1fe5aaFang Deng min_duts_map = {P: 3} 8352a239316b829106b540e57a0100496fed1fe5aaFang Deng 8452a239316b829106b540e57a0100496fed1fe5aaFang Deng First round acquiring: 8552a239316b829106b540e57a0100496fed1fe5aaFang Deng Call get_min_duts(R1) 8652a239316b829106b540e57a0100496fed1fe5aaFang Deng return 2, because P hasn't reach its min dut limit (3) yet 8752a239316b829106b540e57a0100496fed1fe5aaFang Deng requests_to_counts -> {R1: 2-2=0, R2: 4} 8852a239316b829106b540e57a0100496fed1fe5aaFang Deng min_duts_map -> {P: 3-2=1} 8952a239316b829106b540e57a0100496fed1fe5aaFang Deng 9052a239316b829106b540e57a0100496fed1fe5aaFang Deng Call get_min_duts(R2) 9152a239316b829106b540e57a0100496fed1fe5aaFang Deng return 1, because although R2 needs 4 duts, P's min dut limit is now 1 9252a239316b829106b540e57a0100496fed1fe5aaFang Deng requests_to_counts -> {R1: 0, R2: 4-1=3} 9352a239316b829106b540e57a0100496fed1fe5aaFang Deng min_duts_map -> {P: 1-1=0} 9452a239316b829106b540e57a0100496fed1fe5aaFang Deng 9552a239316b829106b540e57a0100496fed1fe5aaFang Deng Second round acquiring: 9652a239316b829106b540e57a0100496fed1fe5aaFang Deng Call get_rest(R1): 9752a239316b829106b540e57a0100496fed1fe5aaFang Deng return 0, requests_to_counts[R1] 9852a239316b829106b540e57a0100496fed1fe5aaFang Deng Call get_rest(R2): 9952a239316b829106b540e57a0100496fed1fe5aaFang Deng return 3, requests_to_counts[R2] 10052a239316b829106b540e57a0100496fed1fe5aaFang Deng 10152a239316b829106b540e57a0100496fed1fe5aaFang Deng Note it is possible that in the first round acquiring, although 10252a239316b829106b540e57a0100496fed1fe5aaFang Deng R1 requested 2 duts, it may only get 1 or None. However get_rest 10352a239316b829106b540e57a0100496fed1fe5aaFang Deng doesn't need to care whether the first round succeeded or not, as 10452a239316b829106b540e57a0100496fed1fe5aaFang Deng in the case when the first round failed, regardless how many duts 10552a239316b829106b540e57a0100496fed1fe5aaFang Deng get_rest requests, it will not be fullfilled anyway. 10652a239316b829106b540e57a0100496fed1fe5aaFang Deng """ 10752a239316b829106b540e57a0100496fed1fe5aaFang Deng 1087224dcb367e8f0f33526a0901713e533234be42fxixuan _host_ratio_metric = metrics.Float( 1097224dcb367e8f0f33526a0901713e533234be42fxixuan 'chromeos/autotest/scheduler/rdb/host_acquisition_ratio') 11052a239316b829106b540e57a0100496fed1fe5aaFang Deng 11152a239316b829106b540e57a0100496fed1fe5aaFang Deng 11252a239316b829106b540e57a0100496fed1fe5aaFang Deng def __init__(self, host_requests): 11352a239316b829106b540e57a0100496fed1fe5aaFang Deng """Initialize. 11452a239316b829106b540e57a0100496fed1fe5aaFang Deng 11552a239316b829106b540e57a0100496fed1fe5aaFang Deng @param host_requests: A list of request to acquire hosts. 11652a239316b829106b540e57a0100496fed1fe5aaFang Deng """ 11752a239316b829106b540e57a0100496fed1fe5aaFang Deng self.requests_to_counts = {} 11852a239316b829106b540e57a0100496fed1fe5aaFang Deng # The order matters, it determines which request got fullfilled first. 11952a239316b829106b540e57a0100496fed1fe5aaFang Deng self.requests = [] 12052a239316b829106b540e57a0100496fed1fe5aaFang Deng for request, count in self._batch_requests(host_requests): 12152a239316b829106b540e57a0100496fed1fe5aaFang Deng self.requests.append(request) 12252a239316b829106b540e57a0100496fed1fe5aaFang Deng self.requests_to_counts[request] = count 12352a239316b829106b540e57a0100496fed1fe5aaFang Deng self.min_duts_map = dict( 12452a239316b829106b540e57a0100496fed1fe5aaFang Deng (r.parent_job_id, r.suite_min_duts) 12552a239316b829106b540e57a0100496fed1fe5aaFang Deng for r in self.requests_to_counts.iterkeys() if r.parent_job_id) 12652a239316b829106b540e57a0100496fed1fe5aaFang Deng 12752a239316b829106b540e57a0100496fed1fe5aaFang Deng 12852a239316b829106b540e57a0100496fed1fe5aaFang Deng @classmethod 12952a239316b829106b540e57a0100496fed1fe5aaFang Deng def _batch_requests(cls, requests): 13052a239316b829106b540e57a0100496fed1fe5aaFang Deng """ Group similar requests, sort by priority and parent_job_id. 13152a239316b829106b540e57a0100496fed1fe5aaFang Deng 13252a239316b829106b540e57a0100496fed1fe5aaFang Deng @param requests: A list or unsorted, unordered requests. 13352a239316b829106b540e57a0100496fed1fe5aaFang Deng 13452a239316b829106b540e57a0100496fed1fe5aaFang Deng @return: A list of tuples of the form (request, number of occurances) 13552a239316b829106b540e57a0100496fed1fe5aaFang Deng formed by counting the number of requests with the same acls/deps/ 13652a239316b829106b540e57a0100496fed1fe5aaFang Deng priority in the input list of requests, and sorting by priority. 13752a239316b829106b540e57a0100496fed1fe5aaFang Deng The order of this list ensures against priority inversion. 13852a239316b829106b540e57a0100496fed1fe5aaFang Deng """ 13952a239316b829106b540e57a0100496fed1fe5aaFang Deng sort_function = lambda request: (request[0].priority, 14052a239316b829106b540e57a0100496fed1fe5aaFang Deng -request[0].parent_job_id) 14152a239316b829106b540e57a0100496fed1fe5aaFang Deng return sorted(collections.Counter(requests).items(), key=sort_function, 14252a239316b829106b540e57a0100496fed1fe5aaFang Deng reverse=True) 14352a239316b829106b540e57a0100496fed1fe5aaFang Deng 14452a239316b829106b540e57a0100496fed1fe5aaFang Deng 14552a239316b829106b540e57a0100496fed1fe5aaFang Deng def get_min_duts(self, host_request): 14652a239316b829106b540e57a0100496fed1fe5aaFang Deng """Given a distinct host request figure out min duts to request for. 14752a239316b829106b540e57a0100496fed1fe5aaFang Deng 14852a239316b829106b540e57a0100496fed1fe5aaFang Deng @param host_request: A request. 14952a239316b829106b540e57a0100496fed1fe5aaFang Deng @returns: The minimum duts that should be requested. 15052a239316b829106b540e57a0100496fed1fe5aaFang Deng """ 15152a239316b829106b540e57a0100496fed1fe5aaFang Deng parent_id = host_request.parent_job_id 15252a239316b829106b540e57a0100496fed1fe5aaFang Deng count = self.requests_to_counts[host_request] 15352a239316b829106b540e57a0100496fed1fe5aaFang Deng if parent_id: 15452a239316b829106b540e57a0100496fed1fe5aaFang Deng min_duts = self.min_duts_map.get(parent_id, 0) 15552a239316b829106b540e57a0100496fed1fe5aaFang Deng to_acquire = min(count, min_duts) 15652a239316b829106b540e57a0100496fed1fe5aaFang Deng self.min_duts_map[parent_id] = max(0, min_duts - to_acquire) 15752a239316b829106b540e57a0100496fed1fe5aaFang Deng else: 15852a239316b829106b540e57a0100496fed1fe5aaFang Deng to_acquire = 0 15952a239316b829106b540e57a0100496fed1fe5aaFang Deng self.requests_to_counts[host_request] -= to_acquire 16052a239316b829106b540e57a0100496fed1fe5aaFang Deng return to_acquire 16152a239316b829106b540e57a0100496fed1fe5aaFang Deng 16252a239316b829106b540e57a0100496fed1fe5aaFang Deng 16352a239316b829106b540e57a0100496fed1fe5aaFang Deng def get_duts(self, host_request): 16452a239316b829106b540e57a0100496fed1fe5aaFang Deng """Return the number of duts host_request still need. 16552a239316b829106b540e57a0100496fed1fe5aaFang Deng 16652a239316b829106b540e57a0100496fed1fe5aaFang Deng @param host_request: A request. 16752a239316b829106b540e57a0100496fed1fe5aaFang Deng @returns: The number of duts need to be requested. 16852a239316b829106b540e57a0100496fed1fe5aaFang Deng """ 16952a239316b829106b540e57a0100496fed1fe5aaFang Deng return self.requests_to_counts[host_request] 17052a239316b829106b540e57a0100496fed1fe5aaFang Deng 17152a239316b829106b540e57a0100496fed1fe5aaFang Deng 17292ae3ca1173534791c4488c9e9985f323ba33356Aviv Keshet # TODO(akeshet): Possibly this code is dead, see crbug.com/738508 for 17392ae3ca1173534791c4488c9e9985f323ba33356Aviv Keshet # context. 17452a239316b829106b540e57a0100496fed1fe5aaFang Deng def record_acquire_min_duts(cls, host_request, hosts_required, 17552a239316b829106b540e57a0100496fed1fe5aaFang Deng acquired_host_count): 17692ae3ca1173534791c4488c9e9985f323ba33356Aviv Keshet """Send stats about host acquisition. 17752a239316b829106b540e57a0100496fed1fe5aaFang Deng 17852a239316b829106b540e57a0100496fed1fe5aaFang Deng @param host_request: A request. 17952a239316b829106b540e57a0100496fed1fe5aaFang Deng @param hosts_required: Number of hosts required to satisfy request. 18052a239316b829106b540e57a0100496fed1fe5aaFang Deng @param acquired_host_count: Number of host acquired. 18152a239316b829106b540e57a0100496fed1fe5aaFang Deng """ 18252a239316b829106b540e57a0100496fed1fe5aaFang Deng try: 18352a239316b829106b540e57a0100496fed1fe5aaFang Deng priority = priorities.Priority.get_string(host_request.priority) 18452a239316b829106b540e57a0100496fed1fe5aaFang Deng except ValueError: 18552a239316b829106b540e57a0100496fed1fe5aaFang Deng return 1867224dcb367e8f0f33526a0901713e533234be42fxixuan cls._host_ratio_metric.set(acquired_host_count/float(hosts_required)) 187