1 # Copyright (c) 2014 The Chromium OS Authors. All rights reserved. 2 # Use of this source code is governed by a BSD-style license that can be 3 # found in the LICENSE file. 4 5 6 """Cache module for rdb requests/host objects. 7 8 This module supplies the following api: 9 1. A cache backend. 10 2. A cache manager for the backend. 11 3. A memoize decorator to encapsulate caching logic. 12 13 This cache manager functions as a lookaside buffer for host requests. 14 Its correctness is contingent on the following conditions: 15 1. The concurrency of the rdb remains 0. 16 2. Clients of the cache don't trust the leased bit on the cached object. 17 3. The cache is created at the start of a single batched request, 18 populated during the request, and completely discarded at the end. 19 20 Rather than caching individual hosts, the cache manager maintains 21 'cache lines'. A cache line is defined as a key: value pair, where 22 the key is as returned by get_key, and the value is a list of RDBHosts 23 that match the key. The following limitations are placed on cache lines: 24 1. A new line can only contain unleased hosts. 25 2. A key can only be set once, with a single line, before removal. 26 3. Every 'get' deletes the entire line. 27 28 Consider the following examples: 29 Normal case: 3 grouped requests, all with the same deps/acls, but different 30 priorities/parent_job_ids. The requests (X+Y+Z) > matching hosts (K): 31 (request1, count=X)- hits the database, takes X hosts, caches (K-X) 32 (request2, count=Y) - hits the cache and is fully satisfied, caches (K-(X+Y)) 33 (request3, count=Z) - hits the cache, needs to acquire (X+Y+Z)-K next tick]: 34 35 Host Count | RDB | Cache 36 ------------------------------------------------------------------ 37 X: | request1 | {} 38 K: | find_hosts(deps, acls) | 39 X: | leased_hosts | 40 K-X: | ---------------------------> | {key: [K-X hosts]} 41 Y<K-X: | request2 <---[K-X hosts]---- | {} 42 Y: | leased_hosts | 43 K-(X+Y): | ---------------------------> | {key: [K-(X+Y) hosts]} 44 Z>K-(X+Y): | request3 <-[K-(X+Y) hosts]-- | {} 45 Z-(K-(X+Y)):| leased_hosts | 46 47 Since hosts are only released by the scheduler there is no way the 48 third request could have been satisfied completely even if we had checked 49 the database real-time. 50 51 Stale cache entries: 3 grouped requests that don't have the same deps/acls. 52 P(1,2,3) are priorities, with P3 being the highest: 53 (request1(deps=[a,b], P3), Count=X) - Caches hosts 54 (request2(deps=[a], P2), Count=Y) - hits the database 55 (request3(deps=[a,b], P1)], Count=Z) - Tries to use cached hosts but fails 56 57 Host Count | RDB | Cache 58 ------------------------------------------------------------------ 59 X: | request1(deps=[a,b]) | {} 60 K: | find_hosts(deps=[a,b]) | 61 X: | leased_hosts | 62 K-X: | ---------------------------> | {deps=[a,b]: [(K-X) hosts]} 63 Y<K-X: | request2(deps=[a]) | {} 64 K-X: | find_hosts(deps=[a]) | 65 Y: | leased_hosts | 66 K-(X+Y): | ---------------------------> | {deps=[a]: [(K-(X+Y)) hosts], 67 | | | overlap | 68 | | deps=[a, b], [(K-X) hosts]} 69 Z: | request3(deps=[a,b])<-[K-X]--| {deps=[a]: [K-(X+Y) hosts]} 70 Z-(K-(X+Y)):| leased_hosts | {deps=[a]: [N-Y hosts]} 71 72 Note that in the last case, even though the cache returns hosts that 73 have already been assigned to request2, request3 cannot use them. This is 74 acceptable because the number of hosts we lease per tick is << the number 75 of requests, so it's faster to check leased bits real time than query for hosts. 76 """ 77 78 79 import abc 80 import collections 81 import logging 82 83 import common 84 from autotest_lib.client.common_lib import utils 85 from autotest_lib.client.common_lib.global_config import global_config 86 from autotest_lib.scheduler import rdb_utils 87 88 try: 89 from chromite.lib import metrics 90 except ImportError: 91 metrics = utils.metrics_mock 92 93 94 MEMOIZE_KEY = 'memoized_hosts' 95 96 def memoize_hosts(func): 97 """Decorator used to memoize through the cache manager. 98 99 @param func: The function/method to decorate. 100 Before calling this function we check the cache for values matching 101 its request argument, and anything returned by the function is cached 102 cached under the same request. 103 """ 104 def cache(self, request, count, **kwargs): 105 """Caching function for the memoize decorator. 106 107 @param request: The rdb request, as defined in rdb_requests. 108 @param count: The count of elements needed to satisfy the request. 109 @param kwargs: 110 Named args for the memoized function. This map should not contain 111 the key MEMOIZED_KEY, as this is reserved for the passing of 112 the cached/memoized hosts to the function itself. 113 """ 114 cache_key = self.cache.get_key(request.deps, request.acls) 115 try: 116 kwargs[MEMOIZE_KEY] = self.cache.get_line(cache_key) 117 except rdb_utils.CacheMiss: 118 pass 119 hosts = func(self, request, count, **kwargs) 120 self.cache.set_line(cache_key, hosts) 121 return hosts 122 return cache 123 124 125 class CacheBackend(object): 126 """Base class for a cache backend.""" 127 __metaclass__ = abc.ABCMeta 128 129 def set(self, key, value): 130 """Set a key. 131 132 @param key: The key to set. 133 @param value: The value to cache. 134 """ 135 pass 136 137 138 def get(self, key): 139 """Get the value stored under a key. 140 141 @param key: The key to retrieve the value for. 142 @return: The value stored under the key. 143 @raises KeyError: If the key isn't present in the cache. 144 """ 145 pass 146 147 148 def delete(self, key): 149 """Delete the key, value pair from the cache. 150 151 @param key: The key used to find the key, value pair to delete. 152 @raises KeyError: If the key isn't already in the cache. 153 """ 154 pass 155 156 157 def has_key(self, key): 158 """Check if the key exists in the cache. 159 160 @param key: The key to check. 161 @return: True if the key is in the cache. 162 """ 163 return False 164 165 166 class DummyCacheBackend(CacheBackend): 167 """A dummy cache backend. 168 169 This cache will claim to have no keys. Every get is a cache miss. 170 """ 171 172 def get(self, key): 173 raise KeyError 174 175 176 class InMemoryCacheBackend(CacheBackend): 177 """In memory cache backend. 178 179 Uses a simple dictionary to store key, value pairs. 180 """ 181 def __init__(self): 182 self._cache = {} 183 184 def get(self, key): 185 return self._cache[key] 186 187 def set(self, key, value): 188 self._cache[key] = value 189 190 def delete(self, key): 191 self._cache.pop(key) 192 193 def has_key(self, key): 194 return key in self._cache 195 196 # TODO: Implement a MemecacheBackend, invalidate when unleasing a host, refactor 197 # the AcquireHostRequest to contain a core of (deps, acls) that we can use as 198 # the key for population and invalidation. The caching manager is still valid, 199 # regardless of the backend. 200 201 class RDBHostCacheManager(object): 202 """RDB Cache manager.""" 203 204 key = collections.namedtuple('key', ['deps', 'acls']) 205 use_cache = global_config.get_config_value( 206 'RDB', 'use_cache', type=bool, default=True) 207 208 def __init__(self): 209 self._cache_backend = (InMemoryCacheBackend() 210 if self.use_cache else DummyCacheBackend()) 211 self.hits = 0 212 self.misses = 0 213 self.stale_entries = [] 214 215 216 def mean_staleness(self): 217 """Compute the average stale entries per line. 218 219 @return: A floating point representing the mean staleness. 220 """ 221 return (reduce(lambda x, y: float(x+y), self.stale_entries)/ 222 len(self.stale_entries)) if self.stale_entries else 0 223 224 225 def hit_ratio(self): 226 """Compute the hit ratio of this cache. 227 228 @return: A floating point percentage of the hit ratio. 229 """ 230 if not self.hits and not self.misses: 231 return 0 232 requests = float(self.hits + self.misses) 233 return (self.hits/requests) * 100 234 235 236 def record_stats(self): 237 """Record stats about the cache managed by this instance.""" 238 hit_ratio = self.hit_ratio() 239 staleness = self.mean_staleness() 240 logging.debug('Cache stats: hit ratio: %.2f%%, ' 241 'avg staleness per line: %.2f%%.', hit_ratio, staleness) 242 metrics.Float('chromeos/autotest/scheduler/rdb/cache/hit_ratio').set( 243 hit_ratio) 244 metrics.Float( 245 'chromeos/autotest/scheduler/rdb/cache/mean_staleness').set( 246 staleness) 247 248 249 @classmethod 250 def get_key(cls, deps, acls): 251 """Return a key for the given deps, acls. 252 253 @param deps: A list of deps, as taken by the AcquireHostRequest. 254 @param acls: A list of acls, as taken by the AcquireHostRequest. 255 @return: A cache key for the given deps/acls. 256 """ 257 # All requests with the same deps, acls should hit the same cache line. 258 # TODO: Do something smarter with acls, only one needs to match. 259 return cls.key(deps=frozenset(deps), acls=frozenset(acls)) 260 261 262 def get_line(self, key): 263 """Clear and return the cache line matching the key. 264 265 @param key: The key the desired cache_line is stored under. 266 @return: A list of rdb hosts matching the key, or None. 267 268 @raises rdb_utils.CacheMiss: If the key isn't in the cache. 269 """ 270 try: 271 cache_line = self._cache_backend.get(key) 272 except KeyError: 273 self.misses += 1 274 raise rdb_utils.CacheMiss('Key %s not in cache' % (key,)) 275 self.hits += 1 276 self._cache_backend.delete(key) 277 return list(cache_line) 278 279 280 def _check_line(self, line, key): 281 """Sanity check a cache line. 282 283 This method assumes that a cache line is made up of RDBHost objects, 284 and checks to see if they all match each other/the key passed in. 285 Checking is done in terms of host labels and acls, note that the hosts 286 in the line can have different deps/acls, as long as they all have the 287 deps required by the key, and at least one matching acl of the key. 288 289 @param line: The cache line value. 290 @param key: The key the line will be stored under. 291 @raises rdb_utils.RDBException: 292 If one of the hosts in the cache line is already leased. 293 The cache already has a different line under the given key. 294 The given key doesn't match the hosts in the line. 295 """ 296 # Note that this doesn't mean that all hosts in the cache are unleased. 297 if any(host.leased for host in line): 298 raise rdb_utils.RDBException('Cannot cache leased hosts %s' % line) 299 300 # Confirm that the given line can be used to service the key by checking 301 # that all hosts have the deps mentioned in the key, and at least one 302 # matching acl. 303 h_keys = set([self.get_key(host.labels, host.acls) for host in line]) 304 for h_key in h_keys: 305 if (not h_key.deps.issuperset(key.deps) or 306 not key.acls.intersection(h_key.acls)): 307 raise rdb_utils.RDBException('Given key: %s does not match key ' 308 'computed from hosts in line: %s' % (key, h_keys)) 309 if self._cache_backend.has_key(key): 310 raise rdb_utils.RDBException('Cannot override a cache line. It ' 311 'must be cleared before setting. Key: %s, hosts %s' % 312 (key, line)) 313 314 315 def set_line(self, key, hosts): 316 """Cache a list of similar hosts. 317 318 set_line will no-op if: 319 The hosts aren't all unleased. 320 The hosts don't have deps/acls matching the key. 321 A cache line under the same key already exists. 322 The first 2 cases will lead to a cache miss in the corresponding get. 323 324 @param hosts: A list of unleased hosts with the same deps/acls. 325 @raises RDBException: If hosts is None, since None is reserved for 326 key expiration. 327 """ 328 if hosts is None: 329 raise rdb_utils.RDBException('Cannot set None in the cache.') 330 331 # An empty list means no hosts matching the request are available. 332 # This can happen if a previous request leased all matching hosts. 333 if not hosts or not self.use_cache: 334 self._cache_backend.set(key, []) 335 return 336 try: 337 self._check_line(hosts, key) 338 except rdb_utils.RDBException as e: 339 logging.error(e) 340 else: 341 self._cache_backend.set(key, set(hosts)) 342
