Thursday, November 19, 2015

LRU Cache in Java - Part 1

Introduction

Caching is an optimization technique which can dramatically boost application performance when used appropriately. There are a lot of different approaches to implement caching ranging from simple homegrown classes to full-blown caching solutions. In this post I will demonstrate how to implement LRU (least recently used) cache in Java in a few lines of code.

What is LRU Cache?

LRU cache is a data structure which stores key-value pairs and has fixed capacity. When an attempt is made to add an element to a cache, current cache size (number of key-value pairs already in the cache) is compared to its capacity (maximum allowed number of key-value pairs). Further actions depend on the result of the comparison:
  • If size is less than capacity then:
    1. New key-value pair is added to the cache.
    2. New key-value pair is marked as the most recently used one.
  • Otherwise:
    1. The least recently used key-value pair is evicted from the cache.
    2. New key-value pair is added to the cache.
    3. New key-value pair is marked as the most recently used one.
In other words, LRU cache is a key-value mapping data structure which grows to a certain size and removes the least recently used key-value pairs to prevent exceeding given capacity.

Implementation

In order to be efficient LRU cache implementation should carry out the following operations in a constant (or at least amortized constant) time:
  • Find a value with the given key.
  • Insert (replace) a value with the given key.
  • Figure out the least recently used key-value pair.
The first and the second property can be easily implemented with a hash map. The goal of the third one can be achieved with a linked list. After looking up an item in the hash map it can be moved to the head of the linked list (item's position in the hash map remains unchanged). Hence the tail of the list will always contain the least recently used item.

As you can see, we need a kind of hybrid data structure which stores its elements in a hash map, but at the same time maintains certain ordering of the elements in a linked list. Do we need to implement it from scratch? The answer is no. Java Collections Framework provides such a data structure: meet LinkedHashMap.

In accordance with documentation, LinkedHashMap is a hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

Unfortunately, insertion-order doesn't work for LRU cache implementation. Is there a way to tell LinkedHashMap to use access-order instead? Luckily, there is a constructor which allows for doing this:
public LinkedHashMap(int initialCapacity, float loadFactor,
        boolean accessOrder) {
// ...
}
Assigning true to the accessOrder parameter will tell LinkedHashMap instance to use access-order instead of insertion-order.

So far so good, now we need a way to enforce cache eviction policy. One approach is to find all methods which insert elements in a LinkedHashMap (put, putAll, putIfAbsent, etc.) and override them appropriately. However this approach is fragile and cumbersome. A better one exists. There is a method called removeEldestEntry which is invoked after new element is inserted in a LinkedHashMap to find out if the eldest entry should be removed. It is the best place to enforce cache eviction policy.

Now it is time to gather all the pieces of the puzzle together. Here is the complete implementation of LRU cache in Java:
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    public LRUCache(final int capacity) {
        super(16, 0.75F, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
        return size() >= capacity;
    }
}
Thanks for reading!

1 comment: