Programming Puzzle: Time-Based Cache

Since we were talking about cache recently, it’s worth it to look at implementing our own cache as a programming exercise. Last time we implemented an LRU cache. Let’s take it a step further and implement a time-based cache.

Why?

To re-iterate: There is really no need to use your own cache implementation in production. There are a variety of existing caching options (such as EHCache, Guava, and JCache), and you put yourself at risk by re-inventing the wheel.

That said, looking into how caches work is a fun exercise. It can give us a feel for the issues involved and hopefully an intuition for dealing with off-the-shelf caching implementations.

Out With The Old, In With The New: Now With Extreme Prejudice

Let’s look at a time-based cache. With this implementation, entries will expire and automatically be removed after a given amount of time, as opposed to the LRU cache where entries would only be removed if the cache was full.

We can maintain a map of entries by access time, and use that map to determine the length of time since last access. Additionally, Java 8 lambdas make it easy to do the scan and removal of old entries.

Note that this cache starts its own thread in the constructor to periodically scan the map and determine which entries need to be removed.

public class TimeBasedCache<K,V> extends HashMap<K,V> {

    private final ScheduledThreadPoolExecutor executor = new ScheduledThreadPoolExecutor(1);
    private final Map<Instant, K> accessTime = new HashMap<>();
    
    public TimeBasedCache(final long scanPeriodMs, final long maxLifetimeMs) {
        executor.scheduleAtFixedRate( ()-> doCacheInvalidation(maxLifetimeMs), scanPeriodMs, scanPeriodMs, TimeUnit.MILLISECONDS);
    }
    
    @Override
    @SuppressWarnings("unchecked")
    public V get(Object key) {
        accessTime.put(Instant.now(), (K)key);
        return super.get(key);
    }
    
    @Override
    public V put(K key, V value) {
        accessTime.put(Instant.now(), key);
        return super.put(key,value);
    }
    
    protected final void doCacheInvalidation(final long maxLifetimeMs) {
        Instant oldestAllowed = Instant.now().minus(maxLifetimeMs, ChronoUnit.MILLIS);
        accessTime.entrySet()
                .stream()
                .filter( (entry) -> entry.getKey().compareTo(oldestAllowed) < 0)
                .forEach((entry) -> super.remove(entry.getValue()));
    }
    
}

Room For Improvement

This cache extends HashMap and doesn’t override all set and put methods. Writing a cache interface and only using those methods for determining access time would be much better. Also this cache could wrap another cache (such as the LRU Cache) using the decorator pattern to compose caching behavior. Then it would be easy to create simple time-based caches, or time-based caches that also had a max size when backed by the LRU Cache.

The Test

The test is a little tricky because it is time-sensitive. Although time-based unit testing is generally best left for integration tests, in this case the test is simple and we can still run it in 60 milliseconds.

public class CacheTest {

    @Test
    public void testCache() throws Exception {

        TimeBasedCache<Long,String> timeCache = new TimeBasedCache<>(10,30);
        
        timeCache.put(1L, "a");
        Thread.sleep(10);
        timeCache.put(2L, "a");
        
        assertTrue(timeCache.containsKey(1L));
        assertTrue(timeCache.containsKey(2L));
        
        Thread.sleep(30);
        assertFalse(timeCache.containsKey(1L));
        assertTrue(timeCache.containsKey(2L));
        
        Thread.sleep(20);
        assertFalse(timeCache.containsKey(1L));
        assertFalse(timeCache.containsKey(2L));        
    }

}

Test Room For Improvement

To be a unit testing purist, we might test just the cache invalidation method and abstract away the creation of the current time that happens with Instant.now(). That would be closer to constituting an actual unit.

Additionally, the instantiation of a timer thread inside this cache precludes the possibility of using any other scheduling mechanism to schedule the scanning (such as Springs Scheduler Annotation).

Conclusion

This was a fun little exercise exploring time-based caching and testing. We can make the code better by: using a cache interface, being able to wrap another cache, unit testing the cache invalidation alone with time abstracted away, externalizing the scanning thread creation, and testing the actual time behavior in an integration test. Maybe we’ll do that in another post!

Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s