package test;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
* Thread safe object map, which clears objects after a specified time. The objects are stored in the
* underlying hashMap.
* @author rongkan
*
*/
public final class TimeLimitedCacheMap {
private final ConcurrentHashMap<String, Object> objectMap = new ConcurrentHashMap<String, Object>(10);
private final ConcurrentHashMap<String, Long> timeMap = new ConcurrentHashMap<String, Long>();
/* I need a shared lock, readwrite lock is an excellent candidate.
* evcition is run with writeLock, put/remove with readLock
*/
private final ReentrantReadWriteLock accessLock = new ReentrantReadWriteLock();
//private final ReentrantLock accessLock = new ReentrantLock();
private final Runnable evictor = new Runnable() {
/* evictor thread removes data, and changes map state. This is
* in conflict with put() and remove(). So we need sync for these operations
*
* In case you are wondering why evictor needs sync (it just calls remove() right?)
* eviction is a compound action that spans more than a single remove(). It enters
* into a conflict with put()
*
* evictor: start looping ------------------------------> keyset is stale, evictor removes the recent put & armagedon comes
* Thrd1:--------------------->put(same key, new object)
*
*/
@Override
public void run() {
// avoid runs on empty maps
if(timeMap.isEmpty()){
Thread.yield();
}
long currentTime = System.nanoTime();
accessLock.writeLock().lock();
Set<String> keys = new HashSet<String>(timeMap.keySet());
accessLock.writeLock().unlock();
/* First attempt to detect & mark stale entries, but don't delete
* The hash map may contain 1000s of objects dont' block it. The returned
* Set returned may be stale, implying:
* 1. contains keys for objects which are removed by user, using remove() (not a problem)
* 2. contains keys for objects which are updated by user, using put() [a big problem]
*/
Set<String> markedForRemoval = new HashSet<String>(10);
for (String key : keys) {
long lastTime = timeMap.get(key);
if(lastTime == 0){
continue;
}
long interval = currentTime - lastTime;
long elapsedTime = TimeUnit.NANOSECONDS.convert(interval, expiryTimeUnit);
if(elapsedTime > expiryTime){
markedForRemoval.add(key);
}
}
/* Actual removal call, which runs on the objects marked earlier.
* Assumption: marked objects.size() < hashmap.size()
* Do not delete blindly, check for staleness before calling remove
*/
accessLock.writeLock().lock();
for (String key : markedForRemoval) {
long lastTime = timeMap.get(key);
if(lastTime == 0){
continue;
}
long interval = currentTime - lastTime;
long elapsedTime = TimeUnit.NANOSECONDS.convert(interval, expiryTimeUnit);
if(elapsedTime > expiryTime){
remove(key);
}
}
accessLock.writeLock().unlock();
}
};
private final ScheduledExecutorService timer = Executors.newSingleThreadScheduledExecutor(new MyThreadFactory(true));
private final class MyThreadFactory implements ThreadFactory {
private boolean isDaemon = false;
public MyThreadFactory(boolean daemon){
isDaemon = daemon;
}
@Override
public Thread newThread(Runnable r) {
Thread t = new Thread(r);
t.setDaemon(isDaemon);
return t;
}
};
private final long expiryTime;
private final TimeUnit expiryTimeUnit;
/**
* Users can play around with evictionDelay and expiryTime.
* 1. Large evictionDelay => less frequent checks, hence chances of finding expired Objects are more
* 2. Lean evictionDelay => aggressive checks, and hence more sync overhead with put() and remove()
* 3. Large expiryTime => increases the time object stays in object map and less chance of cache miss (cache miss is bad)
* 4. Lean expiryTime => by itself does not force object to be removed aggressively, needs lean eviction to be configured
*
* In case you are wondering, above picture is not complete.
* Another key aspect is "Arrival Periodicty", or the rate at which put() is called.
*
* Ideally: expiryTime == arrival periodicity + 1 [read '+1' as slightly greater]
* evictionDelay == expiryTime + 1
*
* For random arrival times, which is a more common scenario, use the following pointers
* 1. eviction Delay > expiry Time
* Here user needs to think of the impact of stale hit (define how stale is stale!)
* 2. eviction Delay < arrival time
* This has higher chances of cache miss and accidental treatment as failure *
* 3. eviction Delay < expiry Time
* Unwanted eviction run(s) resulting in sync overhead on map
* 4. eviction Delay > arrival Time
* Unwanted eviction run(s) resulting in sync overhead on map
*
* @param initialDelay, time after which scheduler starts
* @param evictionDelay, periodicity with which eviction is carried out
* @param expiryTime, age of the object, exceeding which the object is to be removed
* @param unit
*/
public TimeLimitedCacheMap(long initialDelay, long evictionDelay, long expiryTime, TimeUnit unit){
timer.scheduleWithFixedDelay(evictor, initialDelay, evictionDelay, unit);
this.expiryTime = expiryTime;
this.expiryTimeUnit = unit;
}
/* The intention is to prevent user from modifying the object Map,
* I want all adds/removals to be suspended. synchronizing on objectMap
* would also work, but locks are easier to read without scope issues of {}
*
* Concurrent hashMap would have allowed put and remove to happen concurrently.
* I did not use conc-map, because
* 1. I want to update another map (timeMap)
* 2. I want to sync the operation with evictor thread
*
* The unfortunate invariants:
* 1. sync between evictor and put()
* 2. sync between evictor and remove()
* imply
* 3. sync lock between put() and remove()
*
* 3. is unfortunate side effect, as you need to sync all exposed invariants on the same lock.
* Lock duplication won't help. If I create putLock() and removeLock(), they will allow put() and remove()
* to happen concurrently, but will not help two put()/remove() calls to happen in parallel.
*/
public void put(String key, Object value) {
accessLock.readLock().lock();
Long nanoTime = System.nanoTime();
timeMap.put(key, nanoTime);
objectMap.put(key, value);
accessLock.readLock().unlock();
}
/* Read comments for put() they apply here as well.
* If had not allowed remove(), life would have been zillion times simpler.
* However, an undoable action is quite bad.
*/
public Object remove(Object key) {
accessLock.readLock().lock();
//accessLock.lock();
Object value = objectMap.remove(key);
timeMap.remove(key);
//accessLock.unlock();
accessLock.readLock().unlock();
return value;
}
/* Clone requires locking, to prevent the edge case where
* the map is updated with clone is in progress
*/
public Map<String, Object> getClonedMap(){
accessLock.writeLock().lock();
HashMap<String, Object> mapClone = new HashMap<String, Object>(objectMap);
accessLock.writeLock().unlock();
return Collections.unmodifiableMap(mapClone);
}
}
|
Posts
