Simple LRU cache with an expiration time

Question

How can I improve the performance of the code below?

package utils.session;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.TimeUnit;
/**
 * <p>
 * A very simple LRU cache implementation, used for our server side session
 * management.
 * </p>
 * 
 * @author [email protected]
 */
public class SessionCache {
 private static ConcurrentHashMap<String, Entry> cache = new ConcurrentHashMap<>();
 static class Entry {
 private final Object value;
 private final Long expiration;
 private Long lastUseTime;
 public Entry(Object value, Long expiration) {
 this.value = value;
 this.expiration = expiration;
 this.lastUseTime = System.currentTimeMillis();
 }
 public boolean isExpired() {
 return (lastUseTime + expiration) < System.currentTimeMillis();
 }
 public Object getValue() {
 return this.value;
 }
 public void updateUseTime() {
 this.lastUseTime = System.currentTimeMillis();
 }
 }
 static {
 /**
 * Scan our LRU cache every 30 minutes, remove expired keys.
 */
 new Thread(new Runnable() {
 @Override
 public void run() {
 try {
 while (true) {
 for (String key : cache.keySet()) {
 if (cache.get(key).isExpired())
 cache.remove(key);
 }
 Thread.sleep(TimeUnit.MINUTES.toMillis(30));
 }
 } catch (Exception e) {
 e.printStackTrace();
 }
 }
 }).start();
 }
 /**
 * Put a new object into cache, and speicify its expiration time. Everytime we
 * get the object from cache, its expiration time would be updated.
 */
 public static void put(String key, Object value, Long expiration) {
 cache.put(key, new Entry(value, expiration));
 }
 /**
 * Get instance from cache, no need to be thread-safe.
 */
 public static Object get(String key) {
 Entry entry = cache.get(key);
 if (!entry.isExpired()) {
 entry.updateUseTime();
 return entry.getValue();
 } else {
 cache.remove(key);
 return null;
 }
 }
}

• Emanuele Paolini: I would use a single HashMap holding a class with both Object and timestamp. This way you only need one get operation instead of two.
• vnp: I don't see how it is LRU
• WoooHaaaa: @vnp, I've updated my code, please help to have a look, thanks !

Answer 1

I still don't see how it is LRU, but that's beside the point.

One obvious problem is a race between testing for cache.get(key).isExpired() and cache.remove(key) on the next line. It is very well possible for another thread to preempt right in between just to get() that object.

A thread performing get() would believe that it updated useTime, yet the entry would have been removed.

Depending on the use case, the consequences could be catastrophic, or harmless.

Answer 2

Instead of ConcurrentHashMap , I prefer you can use ConcurrentSkipListMap. Because its sorted map. You can fetch from lastEntry check the isExpired.

Limitations:

Sorting occurred based on key. So Please define new key object with existing String and expire time.