March 10, 2012

NavigableMap & time-based caches

Tags: Java, Technical

I often find myself writing time-based caches. Something like storing the last X hours of ticks from a data feed. Most teams I join usually have a utility class to help with such tasks. In a recent move I joined a team that didn’t have such a utility, but did have a need for such a cache. Before coding, I thought I do a quick check to see if anything new had come along to help. At this point I discovered the Java 6 NavigableMap interface.

NavigableMap defines a type of sorted map with handy methods for obtaining submaps. So to get a map of the entries greater than a particular value use the tailMap method. The corresponding method for the submap less than a value is headMap. These methods return a view on the original map. So changes to the submap are reflected in the original map. The JDK provides concurrent and non-concurrent implementations of the interface.

This is very useful for a time-based cache. Create a NavigableMap sorted on the time (I used the epoch milliseconds returned by System.currentTimeMillis()) then tailMap returns the entries younger than a given time, and headMap those older. So to trim the cache of entries older than a certain time use headMap(System.currentTimeMillis() - maxAge).clear(). So easy!

Here is a complete time-based cache class for use as an example.

public class TimeSeriesCache<V> {

    private static final int MILLIS_IN_MINUTE = 60 * 1000;
    private static final int CLEAR_OLD_PERIOD_MINUTES = 1;

    private final NavigableMap<Long, V> series = new ConcurrentSkipListMap<Long, V>();
    private final Set<TickListener<K, Long, V>> subscribers;

    public TimeSeriesCache(int maxAgeMinutes) {
        if (maxAgeMinutes > 0) {
            final int maxAge = maxAgeMinutes * MILLIS_IN_MINUTE;
                    new Runnable() {
                        @Override public void run() {
                            series.headMap(System.currentTimeMillis() - maxAge).clear();


    public Collection<V> getSeriesAfter(Long fromTimestamp) {
        return series.tailMap(fromTimestamp).values();

    public void add(V value) {
        series.put(System.currentTimeMillis(), value);

    public void add(Long timestamp, V value) {
        series.put(timestamp, value);