the best way to implement LRU cache
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
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.