Home | History | Annotate | Download | only in cache
      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 
     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 
     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 
     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 
     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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    454     public WatchedCreatorLoader() {
    455     }
    456 
    457     public void reset() {
    458       wasCalled = false;
    459     }
    460 
    461     public boolean wasCalled() {
    462       return wasCalled;
    463     }
    464 
    465     public void setKeyPrefix(String keyPrefix) {
    466       this.keyPrefix = keyPrefix;
    467     }
    468 
    469     public void setValuePrefix(int valuePrefix) {
    470       this.valuePrefix = valuePrefix;
    471     }
    472 
    473     @Override public Integer load(String key) {
    474       wasCalled = true;
    475       return valuePrefix + Integer.parseInt(key.substring(keyPrefix.length()));
    476     }
    477   }
    478 }
    479