the best way to implement LRU cache

Question

I want to create an efficient implementation of LRU cache. I've found that the most convenient way is to use LinkedHashMap but unfortunately it's quite slow if many threads are using a cache. My implementation is here:

/**
 * Class provides API for FixedSizeCache.
 * Its inheritors represent classes         
 * with concrete strategies     
 * for choosing elements to delete
 * in case of cache overflow. All inheritors
 * must implement {@link #getSize(K, V)}. 
 */
public abstract class FixedSizeCache <K, V> implements ICache <K, V> {
    /**
     * Current cache size.
     */
    private int currentSize;


    /**
     *  Maximum allowable cache size.
     */
    private int maxSize;


    /**
     * Number of {@link #get(K)} queries for which appropriate {@code value} was found.
     */
    private int keysFound;


    /**
     * Number of {@link #get(K)} queries for which appropriate {@code value} was not found.
     */
    private int keysMissed;


    /** 
     * Number {@code key-value} associations that were deleted from cache
     * because of cash overflow.
     */
    private int erasedCount; 


    /**
     * Basic data structure LinkedHashMap provides
     * convenient way for designing both types of cache:
     * LRU and FIFO. Depending on its constructor parameters
     * it can represent either of FIFO or LRU HashMap.
     */
    private LinkedHashMap <K, V> entries;


    /** 
     * If {@code type} variable equals {@code true}
     * then LinkedHashMap will represent LRU HashMap.
     * And it will represent FIFO HashMap otherwise.
     */ 
    public FixedSizeCache(int maxSize, boolean type) {

        if (maxSize <= 0) {
            throw new IllegalArgumentException("int maxSize parameter must be greater than 0");
        }

        this.maxSize = maxSize;
        this.entries = new LinkedHashMap<K, V> (0, 0.75f, type);
    }


    /** 
     * Method deletes {@code key-value} associations 
     * until current cache size {@link #currentSize} will become 
     * less than or equal to maximum allowable
     * cache size {@link #maxSize}
     */
    private void relaxSize()  {

        while (currentSize > maxSize) {

             // The strategy for choosing entry with the lowest precedence
             // depends on {@code type} variable that was used to create  {@link #entries} variable. 
             // If it was created with constructor LinkedHashMap(int size,double loadfactor, boolean type)
             // with {@code type} equaled to {@code true} then variable {@link #entries} represents
             // LRU LinkedHashMap and iterator of its entrySet will return elements in order
             // from least recently used to the most recently used.
             // Otherwise, if {@code type} equaled to {@code false} then {@link #entries} represents
             // FIFO LinkedHashMap and iterator will return its entrySet elements in FIFO order -
             // from oldest in the cache to the most recently added.

            Map.Entry <K, V> entryToDelete = entries.entrySet().iterator().next();

            if (entryToDelete == null) {
                throw new IllegalStateException(" Implemented method int getSize(K key, V value) " +
                        " returns different results for the same arguments.");  
            }

            entries.remove(entryToDelete.getKey());
            currentSize -= getAssociationSize(entryToDelete.getKey(), entryToDelete.getValue());
            erasedCount++;
        }

        if (currentSize < 0) {
            throw new IllegalStateException(" Implemented method int getSize(K key, V value) " +
                    " returns different results for the same arguments.");
        }
    }


    /** 
     * All inheritors must implement this method
     * which evaluates the weight of key-value association.
     * Sum of weights of all key-value association in the cache
     * equals to {@link #currentSize}.  
     * But developer must ensure that
     * implementation will satisfy two conditions:
     * <br>1) method always returns non negative integers;
     * <br>2) for every two pairs {@code key-value} and {@code key_1-value_1}
     * if {@code key.equals(key_1)} and {@code value.equals(value_1)} then 
     * {@code getSize(key, value)==getSize(key_1, value_1)};
     * <br> Otherwise cache can work incorrectly.
     */
    protected abstract int getSize(K key, V value);


    /** 
     * Helps to detect if the implementation of {@link #getSize(K, V)} method
     * can return negative values. 
     */
    private int getAssociationSize(K key, V value)  {

        int entrySize = getSize(key, value);

        if (entrySize < 0 ) {
            throw new IllegalStateException("int getSize(K key, V value) method implementation is invalid. It returned negative value.");
        }

        return entrySize;
    }


   /**
    * Returns the {@code value} corresponding to {@code key} or
    * {@code null} if  {@code key} is not present in the cache. 
    * Increases {@link #keysFound} if finds a corresponding {@code value}
    * or increases {@link #keysMissed} otherwise. 
    */
    public synchronized final V get(K key)  {

        if (key == null) {
            throw new NullPointerException("K key is null");
        }

        V value = entries.get(key);
        if (value != null) {
            keysFound++;
            return value;
        }

        keysMissed++;
        return value;
    }


    /** 
     * Removes the {@code key-value} association, if any, with the
    *  given {@code key}; returns the {@code value} with which it
    *  was associated, or {@code null}.
    */
    public synchronized final V remove(K key)  {

        if (key == null) {
            throw new NullPointerException("K key is null");
        }

        V value = entries.remove(key);

        // if appropriate value was present in the cache than decrease
        // current size of cache

        if (value != null) {
            currentSize -= getAssociationSize(key, value);
        }

        return value;
    }


   /**
    * Adds or replaces a {@code key-value} association.
    * Returns the old {@code value} if the
    * {@code key} was present; otherwise returns {@code null}.
    * If after insertion of a {@code key-value} association 
    * to cache its size becomes greater than
    * maximum allowable cache size then it calls {@link #relaxSize()} method which
    * releases needed free space. 
    */
    public synchronized final V put(K key, V value)  {

        if (key == null || value == null) {
            throw new NullPointerException("K key is null or V value is null");
        }

        currentSize += getAssociationSize(key, value);      
        value = entries.put(key, value);

        // if key was not present then decrease cache size

        if (value != null) {
            currentSize -= getAssociationSize(key, value);
        }

        // if cache size with new entry is greater
        // than maximum allowable cache size
        // then get some free space

        if (currentSize > maxSize) {
            relaxSize();
        }

        return value;
    }


    /**
     * Returns current size of cache. 
     */
    public synchronized int currentSize() {
        return currentSize;
    }


    /** 
     * Returns maximum allowable cache size. 
     */ 
    public synchronized int maxSize() {
        return maxSize;
    }


    /** 
     * Returns number of {@code key-value} associations that were deleted
     * because of cache overflow.   
     */
    public synchronized int erasedCount() {
        return erasedCount;
    }


    /** 
     * Number of {@link #get(K)} queries for which appropriate {@code value} was found.
     */
    public synchronized int keysFoundCount() {
        return keysFound;
    }


    /** 
     * Number of {@link #get(K)} queries for which appropriate {@code value} was not found.
     */
    public synchronized int keysMissedCount() {
        return keysMissed;
    }


    /**
     * Removes all {@code key-value} associations
     * from the cache. And turns {@link #currentSize},
     * {@link #keysFound}, {@link #keysMissed} to {@code zero}.  
     */
    public synchronized void clear() {
        entries.clear();
        currentSize = 0;
        keysMissed = 0;
        keysFound = 0;
        erasedCount = 0;
    }


    /**
     * Returns a copy of {@link #entries}
     * that has the same content.
     */
    public synchronized LinkedHashMap<K, V> getCopy() {
        return new LinkedHashMap<K, V> (entries);
    }
}

This implementation is quite slow (because of synchronization) if we have many threads are trying to call lets say get() method. Is there a better way?

Answer 1

I don't know if this is beneficial, but if you can replace your LinkedHashMap with a ConcurrentHashMap then you'll improve your throughput - a ConcurrentHashMap uses sharding to permit multiple simultaneous readers and writers. It is also thread-safe, so you won't need to synchronize your readers and writers.

Barring that, replace your use of the synchronized keyword with a ReadWriteLock. This will allow multiple simultaneous readers.

Answer 2

Try not to reimplement what is available: Guava Caches. It has almost all the features that you need: size-based eviction, concurrency, weighting. If it fits your needs use it. If not than try to implement yours, but always evaluate first (in my opinion). Just an advise.

Answer 3

You need to run a performance test like this

Map<Object, Object> map = Collections.synchronizedMap(new LinkedHashMap<Object, Object>(16, 0.7f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
        return size() > 1000;
    }
});
Integer[] values = new Integer[10000];
for (int i = 0; i < values.length; i++)
    values[i] = i;

long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < values.length; j++) {
        map.get(values[j]);
        map.get(values[j / 2]);
        map.get(values[j / 3]);
        map.get(values[j / 4]);
        map.put(values[j], values[j]);
    }
}
long time = System.nanoTime() - start;
long rate = (5 * values.length * 1000) * 1000000000L / time;
System.out.printf("Performed get/put operations at a rate of %,d per second%n", rate);

prints on my 2.5 GHz i5 laptop

Performed get/put operations at a rate of 27,170,035 per second

How many million operations per second do you need?

Answer 4

As said before, the main cause of trouble is updating the shared data structure within the LRU algorithm. To overcome this you can use partitioning or, alternatively, use another eviction algorithm then LRU. There are modern algorithms that perform better then LRU. See my comparison on that topic on the cache2k benchmarks page.

The cache2k eviction implementations CLOCK and CLOCK-Pro have full read concurrency without locking.

Answer 5

LRU scheme on its right own involves exclusive modification of a shared structure. So the contention is given and there is nothing much that you can do.

If you don't need strict LRU and can tolerate some inconsistency of the eviction policy the stuff looks up and it's brighter. You entries (value wrappers) need some usage statistics and you need some expiration policy based on the said usage statistics.

Then you can have LRU alike structure based on ConcurrentSkipListMap (i.e. you may think of it as database index), when the cache is about to be expired use that index and expire the elements based upon it. You will need double checking and so on but it's doable. Updating the index is far for free but scales quite. Keep in mind that ConcurrentSkipListMap.size() is an expensive operation O(n), so you shall not rely on either. The implementation is not hard but not trivial either and unless you have enough contention (cores) synchronized(LHM) is probably the easiest approach.