1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.google.common.cache; 16 17 import static com.google.common.cache.TestingCacheLoaders.identityLoader; 18 import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener; 19 import static com.google.common.truth.Truth.assertThat; 20 import static java.util.Arrays.asList; 21 import static java.util.concurrent.TimeUnit.MILLISECONDS; 22 23 import com.google.common.cache.TestingCacheLoaders.IdentityLoader; 24 import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener; 25 import com.google.common.collect.Iterators; 26 import com.google.common.testing.FakeTicker; 27 import com.google.common.util.concurrent.Callables; 28 29 import junit.framework.TestCase; 30 31 import java.util.List; 32 import java.util.Set; 33 import java.util.concurrent.ExecutionException; 34 import java.util.concurrent.atomic.AtomicInteger; 35 36 /** 37 * Tests relating to cache expiration: make sure entries expire at the right times, make sure 38 * expired entries don't show up, etc. 39 * 40 * @author mike nonemacher 41 */ 42 @SuppressWarnings("deprecation") // tests of deprecated method 43 public class CacheExpirationTest extends TestCase { 44 45 private static final long EXPIRING_TIME = 1000; 46 private static final int VALUE_PREFIX = 12345; 47 private static final String KEY_PREFIX = "key prefix:"; 48 testExpiration_expireAfterWrite()49 public void testExpiration_expireAfterWrite() { 50 FakeTicker ticker = new FakeTicker(); 51 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 52 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 53 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 54 .expireAfterWrite(EXPIRING_TIME, MILLISECONDS) 55 .removalListener(removalListener) 56 .ticker(ticker) 57 .build(loader); 58 checkExpiration(cache, loader, ticker, removalListener); 59 } 60 testExpiration_expireAfterAccess()61 public void testExpiration_expireAfterAccess() { 62 FakeTicker ticker = new FakeTicker(); 63 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 64 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 65 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 66 .expireAfterAccess(EXPIRING_TIME, MILLISECONDS) 67 .removalListener(removalListener) 68 .ticker(ticker) 69 .build(loader); 70 checkExpiration(cache, loader, ticker, removalListener); 71 } 72 checkExpiration(LoadingCache<String, Integer> cache, WatchedCreatorLoader loader, FakeTicker ticker, CountingRemovalListener<String, Integer> removalListener)73 private void checkExpiration(LoadingCache<String, Integer> cache, WatchedCreatorLoader loader, 74 FakeTicker ticker, CountingRemovalListener<String, Integer> removalListener) { 75 76 for (int i = 0; i < 10; i++) { 77 assertEquals(Integer.valueOf(VALUE_PREFIX + i), cache.getUnchecked(KEY_PREFIX + i)); 78 } 79 80 for (int i = 0; i < 10; i++) { 81 loader.reset(); 82 assertEquals(Integer.valueOf(VALUE_PREFIX + i), cache.getUnchecked(KEY_PREFIX + i)); 83 assertFalse("Creator should not have been called @#" + i, loader.wasCalled()); 84 } 85 86 CacheTesting.expireEntries((LoadingCache<?, ?>) cache, EXPIRING_TIME, ticker); 87 88 assertEquals("Map must be empty by now", 0, cache.size()); 89 assertEquals("Eviction notifications must be received", 10, 90 removalListener.getCount()); 91 92 CacheTesting.expireEntries((LoadingCache<?, ?>) cache, EXPIRING_TIME, ticker); 93 // ensure that no new notifications are sent 94 assertEquals("Eviction notifications must be received", 10, 95 removalListener.getCount()); 96 } 97 testExpiringGet_expireAfterWrite()98 public void testExpiringGet_expireAfterWrite() { 99 FakeTicker ticker = new FakeTicker(); 100 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 101 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 102 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 103 .expireAfterWrite(EXPIRING_TIME, MILLISECONDS) 104 .removalListener(removalListener) 105 .ticker(ticker) 106 .build(loader); 107 runExpirationTest(cache, loader, ticker, removalListener); 108 } 109 testExpiringGet_expireAfterAccess()110 public void testExpiringGet_expireAfterAccess() { 111 FakeTicker ticker = new FakeTicker(); 112 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 113 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 114 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 115 .expireAfterAccess(EXPIRING_TIME, MILLISECONDS) 116 .removalListener(removalListener) 117 .ticker(ticker) 118 .build(loader); 119 runExpirationTest(cache, loader, ticker, removalListener); 120 } 121 runExpirationTest(LoadingCache<String, Integer> cache, WatchedCreatorLoader loader, FakeTicker ticker, CountingRemovalListener<String, Integer> removalListener)122 private void runExpirationTest(LoadingCache<String, Integer> cache, WatchedCreatorLoader loader, 123 FakeTicker ticker, CountingRemovalListener<String, Integer> removalListener) { 124 125 for (int i = 0; i < 10; i++) { 126 assertEquals(Integer.valueOf(VALUE_PREFIX + i), cache.getUnchecked(KEY_PREFIX + i)); 127 } 128 129 for (int i = 0; i < 10; i++) { 130 loader.reset(); 131 assertEquals(Integer.valueOf(VALUE_PREFIX + i), cache.getUnchecked(KEY_PREFIX + i)); 132 assertFalse("Loader should NOT have been called @#" + i, loader.wasCalled()); 133 } 134 135 // wait for entries to expire, but don't call expireEntries 136 ticker.advance(EXPIRING_TIME * 10, MILLISECONDS); 137 138 // add a single unexpired entry 139 cache.getUnchecked(KEY_PREFIX + 11); 140 141 // collections views shouldn't expose expired entries 142 assertEquals(1, Iterators.size(cache.asMap().entrySet().iterator())); 143 assertEquals(1, Iterators.size(cache.asMap().keySet().iterator())); 144 assertEquals(1, Iterators.size(cache.asMap().values().iterator())); 145 146 CacheTesting.expireEntries((LoadingCache<?, ?>) cache, EXPIRING_TIME, ticker); 147 148 for (int i = 0; i < 11; i++) { 149 assertFalse(cache.asMap().containsKey(KEY_PREFIX + i)); 150 } 151 assertEquals(11, removalListener.getCount()); 152 153 for (int i = 0; i < 10; i++) { 154 assertFalse(cache.asMap().containsKey(KEY_PREFIX + i)); 155 loader.reset(); 156 assertEquals(Integer.valueOf(VALUE_PREFIX + i), cache.getUnchecked(KEY_PREFIX + i)); 157 assertTrue("Creator should have been called @#" + i, loader.wasCalled()); 158 } 159 160 // expire new values we just created 161 CacheTesting.expireEntries((LoadingCache<?, ?>) cache, EXPIRING_TIME, ticker); 162 assertEquals("Eviction notifications must be received", 21, 163 removalListener.getCount()); 164 165 CacheTesting.expireEntries((LoadingCache<?, ?>) cache, EXPIRING_TIME, ticker); 166 // ensure that no new notifications are sent 167 assertEquals("Eviction notifications must be received", 21, 168 removalListener.getCount()); 169 } 170 testRemovalListener_expireAfterWrite()171 public void testRemovalListener_expireAfterWrite() { 172 FakeTicker ticker = new FakeTicker(); 173 final AtomicInteger evictionCount = new AtomicInteger(); 174 final AtomicInteger applyCount = new AtomicInteger(); 175 final AtomicInteger totalSum = new AtomicInteger(); 176 177 RemovalListener<Integer, AtomicInteger> removalListener = 178 new RemovalListener<Integer, AtomicInteger>() { 179 @Override 180 public void onRemoval(RemovalNotification<Integer, AtomicInteger> notification) { 181 if (notification.wasEvicted()) { 182 evictionCount.incrementAndGet(); 183 totalSum.addAndGet(notification.getValue().get()); 184 } 185 } 186 }; 187 188 CacheLoader<Integer, AtomicInteger> loader = new CacheLoader<Integer, AtomicInteger>() { 189 @Override public AtomicInteger load(Integer key) { 190 applyCount.incrementAndGet(); 191 return new AtomicInteger(); 192 } 193 }; 194 195 LoadingCache<Integer, AtomicInteger> cache = CacheBuilder.newBuilder() 196 .removalListener(removalListener) 197 .expireAfterWrite(10, MILLISECONDS) 198 .ticker(ticker) 199 .build(loader); 200 201 // Increment 100 times 202 for (int i = 0; i < 100; ++i) { 203 cache.getUnchecked(10).incrementAndGet(); 204 ticker.advance(1, MILLISECONDS); 205 } 206 207 assertEquals(evictionCount.get() + 1, applyCount.get()); 208 int remaining = cache.getUnchecked(10).get(); 209 assertEquals(100, totalSum.get() + remaining); 210 } 211 testRemovalScheduler_expireAfterWrite()212 public void testRemovalScheduler_expireAfterWrite() { 213 FakeTicker ticker = new FakeTicker(); 214 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 215 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 216 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 217 .expireAfterWrite(EXPIRING_TIME, MILLISECONDS) 218 .removalListener(removalListener) 219 .ticker(ticker) 220 .build(loader); 221 runRemovalScheduler(cache, removalListener, loader, ticker, KEY_PREFIX, EXPIRING_TIME); 222 } 223 testRemovalScheduler_expireAfterAccess()224 public void testRemovalScheduler_expireAfterAccess() { 225 FakeTicker ticker = new FakeTicker(); 226 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 227 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 228 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 229 .expireAfterAccess(EXPIRING_TIME, MILLISECONDS) 230 .removalListener(removalListener) 231 .ticker(ticker) 232 .build(loader); 233 runRemovalScheduler(cache, removalListener, loader, ticker, KEY_PREFIX, EXPIRING_TIME); 234 } 235 testRemovalScheduler_expireAfterBoth()236 public void testRemovalScheduler_expireAfterBoth() { 237 FakeTicker ticker = new FakeTicker(); 238 CountingRemovalListener<String, Integer> removalListener = countingRemovalListener(); 239 WatchedCreatorLoader loader = new WatchedCreatorLoader(); 240 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 241 .expireAfterAccess(EXPIRING_TIME, MILLISECONDS) 242 .expireAfterWrite(EXPIRING_TIME, MILLISECONDS) 243 .removalListener(removalListener) 244 .ticker(ticker) 245 .build(loader); 246 runRemovalScheduler(cache, removalListener, loader, ticker, KEY_PREFIX, EXPIRING_TIME); 247 } 248 testExpirationOrder_access()249 public void testExpirationOrder_access() { 250 // test lru within a single segment 251 FakeTicker ticker = new FakeTicker(); 252 IdentityLoader<Integer> loader = identityLoader(); 253 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 254 .concurrencyLevel(1) 255 .expireAfterAccess(11, MILLISECONDS) 256 .ticker(ticker) 257 .build(loader); 258 for (int i = 0; i < 10; i++) { 259 cache.getUnchecked(i); 260 ticker.advance(1, MILLISECONDS); 261 } 262 Set<Integer> keySet = cache.asMap().keySet(); 263 assertThat(keySet).has().exactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 264 265 // 0 expires 266 ticker.advance(1, MILLISECONDS); 267 assertThat(keySet).has().exactly(1, 2, 3, 4, 5, 6, 7, 8, 9); 268 269 // reorder 270 getAll(cache, asList(0, 1, 2)); 271 CacheTesting.drainRecencyQueues(cache); 272 ticker.advance(2, MILLISECONDS); 273 assertThat(keySet).has().exactly(3, 4, 5, 6, 7, 8, 9, 0, 1, 2); 274 275 // 3 expires 276 ticker.advance(1, MILLISECONDS); 277 assertThat(keySet).has().exactly(4, 5, 6, 7, 8, 9, 0, 1, 2); 278 279 // reorder 280 getAll(cache, asList(5, 7, 9)); 281 CacheTesting.drainRecencyQueues(cache); 282 assertThat(keySet).has().exactly(4, 6, 8, 0, 1, 2, 5, 7, 9); 283 284 // 4 expires 285 ticker.advance(1, MILLISECONDS); 286 assertThat(keySet).has().exactly(6, 8, 0, 1, 2, 5, 7, 9); 287 ticker.advance(1, MILLISECONDS); 288 assertThat(keySet).has().exactly(6, 8, 0, 1, 2, 5, 7, 9); 289 290 // 6 expires 291 ticker.advance(1, MILLISECONDS); 292 assertThat(keySet).has().exactly(8, 0, 1, 2, 5, 7, 9); 293 ticker.advance(1, MILLISECONDS); 294 assertThat(keySet).has().exactly(8, 0, 1, 2, 5, 7, 9); 295 296 // 8 expires 297 ticker.advance(1, MILLISECONDS); 298 assertThat(keySet).has().exactly(0, 1, 2, 5, 7, 9); 299 } 300 testExpirationOrder_write()301 public void testExpirationOrder_write() throws ExecutionException { 302 // test lru within a single segment 303 FakeTicker ticker = new FakeTicker(); 304 IdentityLoader<Integer> loader = identityLoader(); 305 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 306 .concurrencyLevel(1) 307 .expireAfterWrite(11, MILLISECONDS) 308 .ticker(ticker) 309 .build(loader); 310 for (int i = 0; i < 10; i++) { 311 cache.getUnchecked(i); 312 ticker.advance(1, MILLISECONDS); 313 } 314 Set<Integer> keySet = cache.asMap().keySet(); 315 assertThat(keySet).has().exactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 316 317 // 0 expires 318 ticker.advance(1, MILLISECONDS); 319 assertThat(keySet).has().exactly(1, 2, 3, 4, 5, 6, 7, 8, 9); 320 321 // get doesn't stop 1 from expiring 322 getAll(cache, asList(0, 1, 2)); 323 CacheTesting.drainRecencyQueues(cache); 324 ticker.advance(1, MILLISECONDS); 325 assertThat(keySet).has().exactly(2, 3, 4, 5, 6, 7, 8, 9, 0); 326 327 // get(K, Callable) doesn't stop 2 from expiring 328 cache.get(2, Callables.returning(-2)); 329 CacheTesting.drainRecencyQueues(cache); 330 ticker.advance(1, MILLISECONDS); 331 assertThat(keySet).has().exactly(3, 4, 5, 6, 7, 8, 9, 0); 332 333 // asMap.put saves 3 334 cache.asMap().put(3, -3); 335 ticker.advance(1, MILLISECONDS); 336 assertThat(keySet).has().exactly(4, 5, 6, 7, 8, 9, 0, 3); 337 338 // asMap.replace saves 4 339 cache.asMap().replace(4, -4); 340 ticker.advance(1, MILLISECONDS); 341 assertThat(keySet).has().exactly(5, 6, 7, 8, 9, 0, 3, 4); 342 343 // 5 expires 344 ticker.advance(1, MILLISECONDS); 345 assertThat(keySet).has().exactly(6, 7, 8, 9, 0, 3, 4); 346 } 347 testExpirationOrder_writeAccess()348 public void testExpirationOrder_writeAccess() throws ExecutionException { 349 // test lru within a single segment 350 FakeTicker ticker = new FakeTicker(); 351 IdentityLoader<Integer> loader = identityLoader(); 352 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 353 .concurrencyLevel(1) 354 .expireAfterWrite(5, MILLISECONDS) 355 .expireAfterAccess(3, MILLISECONDS) 356 .ticker(ticker) 357 .build(loader); 358 for (int i = 0; i < 5; i++) { 359 cache.getUnchecked(i); 360 } 361 ticker.advance(1, MILLISECONDS); 362 for (int i = 5; i < 10; i++) { 363 cache.getUnchecked(i); 364 } 365 ticker.advance(1, MILLISECONDS); 366 367 Set<Integer> keySet = cache.asMap().keySet(); 368 assertThat(keySet).has().exactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 369 370 // get saves 1, 3; 0, 2, 4 expire 371 getAll(cache, asList(1, 3)); 372 CacheTesting.drainRecencyQueues(cache); 373 ticker.advance(1, MILLISECONDS); 374 assertThat(keySet).has().exactly(5, 6, 7, 8, 9, 1, 3); 375 376 // get saves 6, 8; 5, 7, 9 expire 377 getAll(cache, asList(6, 8)); 378 CacheTesting.drainRecencyQueues(cache); 379 ticker.advance(1, MILLISECONDS); 380 assertThat(keySet).has().exactly(1, 3, 6, 8); 381 382 // get fails to save 1, put saves 3 383 cache.asMap().put(3, -3); 384 getAll(cache, asList(1)); 385 CacheTesting.drainRecencyQueues(cache); 386 ticker.advance(1, MILLISECONDS); 387 assertThat(keySet).has().exactly(6, 8, 3); 388 389 // get(K, Callable) fails to save 8, replace saves 6 390 cache.asMap().replace(6, -6); 391 cache.get(8, Callables.returning(-8)); 392 CacheTesting.drainRecencyQueues(cache); 393 ticker.advance(1, MILLISECONDS); 394 assertThat(keySet).has().exactly(3, 6); 395 } 396 runRemovalScheduler(LoadingCache<String, Integer> cache, CountingRemovalListener<String, Integer> removalListener, WatchedCreatorLoader loader, FakeTicker ticker, String keyPrefix, long ttl)397 private void runRemovalScheduler(LoadingCache<String, Integer> cache, 398 CountingRemovalListener<String, Integer> removalListener, 399 WatchedCreatorLoader loader, 400 FakeTicker ticker, String keyPrefix, long ttl) { 401 402 int shift1 = 10 + VALUE_PREFIX; 403 loader.setValuePrefix(shift1); 404 // fill with initial data 405 for (int i = 0; i < 10; i++) { 406 assertEquals(Integer.valueOf(i + shift1), cache.getUnchecked(keyPrefix + i)); 407 } 408 assertEquals(10, CacheTesting.expirationQueueSize(cache)); 409 assertEquals(0, removalListener.getCount()); 410 411 // wait, so that entries have just 10 ms to live 412 ticker.advance(ttl * 2 / 3, MILLISECONDS); 413 414 assertEquals(10, CacheTesting.expirationQueueSize(cache)); 415 assertEquals(0, removalListener.getCount()); 416 417 int shift2 = shift1 + 10; 418 loader.setValuePrefix(shift2); 419 // fill with new data - has to live for 20 ms more 420 for (int i = 0; i < 10; i++) { 421 cache.invalidate(keyPrefix + i); 422 assertEquals("key: " + keyPrefix + i, 423 Integer.valueOf(i + shift2), cache.getUnchecked(keyPrefix + i)); 424 } 425 assertEquals(10, CacheTesting.expirationQueueSize(cache)); 426 assertEquals(10, removalListener.getCount()); // these are the invalidated ones 427 428 // old timeouts must expire after this wait 429 ticker.advance(ttl * 2 / 3, MILLISECONDS); 430 431 assertEquals(10, CacheTesting.expirationQueueSize(cache)); 432 assertEquals(10, removalListener.getCount()); 433 434 // check that new values are still there - they still have 10 ms to live 435 for (int i = 0; i < 10; i++) { 436 loader.reset(); 437 assertEquals(Integer.valueOf(i + shift2), cache.getUnchecked(keyPrefix + i)); 438 assertFalse("Creator should NOT have been called @#" + i, loader.wasCalled()); 439 } 440 assertEquals(10, removalListener.getCount()); 441 } 442 getAll(LoadingCache<Integer, Integer> cache, List<Integer> keys)443 private void getAll(LoadingCache<Integer, Integer> cache, List<Integer> keys) { 444 for (int i : keys) { 445 cache.getUnchecked(i); 446 } 447 } 448 449 private static class WatchedCreatorLoader extends CacheLoader<String, Integer> { 450 boolean wasCalled = false; // must be set in load() 451 String keyPrefix = KEY_PREFIX; 452 int valuePrefix = VALUE_PREFIX; 453 WatchedCreatorLoader()454 public WatchedCreatorLoader() { 455 } 456 reset()457 public void reset() { 458 wasCalled = false; 459 } 460 wasCalled()461 public boolean wasCalled() { 462 return wasCalled; 463 } 464 setKeyPrefix(String keyPrefix)465 public void setKeyPrefix(String keyPrefix) { 466 this.keyPrefix = keyPrefix; 467 } 468 setValuePrefix(int valuePrefix)469 public void setValuePrefix(int valuePrefix) { 470 this.valuePrefix = valuePrefix; 471 } 472 load(String key)473 @Override public Integer load(String key) { 474 wasCalled = true; 475 return valuePrefix + Integer.parseInt(key.substring(keyPrefix.length())); 476 } 477 } 478 } 479