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
15package com.google.common.cache;
16
17import static com.google.common.cache.TestingCacheLoaders.identityLoader;
18import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener;
19import static com.google.common.truth.Truth.assertThat;
20import static java.util.Arrays.asList;
21import static java.util.concurrent.TimeUnit.MILLISECONDS;
22
23import com.google.common.cache.TestingCacheLoaders.IdentityLoader;
24import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener;
25import com.google.common.collect.Iterators;
26import com.google.common.testing.FakeTicker;
27import com.google.common.util.concurrent.Callables;
28
29import junit.framework.TestCase;
30
31import java.util.List;
32import java.util.Set;
33import java.util.concurrent.ExecutionException;
34import 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
43public 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