Let’s revisit the cache implementation for storing frequently searched programs. One strategy to implement fixed size cache is to maintain the search count for each program and when the cache size is more than maximum allowed size, delete the programs which are least frequently searched. The ProgramSearchResult class uses variable of type AtomicInteger to store the search count.
The code given below in Listing 1, locks the servlet instance while executing the following steps which should be performed as one atomic operation. It ensures that concurrent threads while searching the same program number do not create multiple objects of ProgramSearchResult and set the value of search count in each object to 1. Thus it avoids multiple instances of ProgramSearchResult to be created for a program.
Steps to add program in cache:
private ConcurrentMap programsCache =
new ConcurrentHashMap();
private static final int MAX_ALLOWED_SIZE = 100;
doPost(...) {
...
try {
ProgramSearchResult result = null;
synchronized(this) {
//fetch the program from cache
result = programsCache.get(programNumber);
if(result != null) {
//program is found in cache
//increment the search count
result.incrementCount();
}
else {
//program is not found in cache
//Fetch it from the database
Program program = ProgramDAO.getInstance().
findByProgramNumber(programNumber);
ProgramSearchResult result =
new ProgramSearchResult();
result.setProgram(program);
result.incrementCount();
...
}
}
programsCache.putIfAbsent(programNumber,result);
/* Code to remove programs from the cache */
}
catch(EntityNotFoundException exp) {
//program is not found in database
...
}
}
Listing 1. Fetch the program from cache and if not found fetch it from database
Since, ConcurrentHashMap is thread-safe, the operation to add the new program in it need not be included within the synchronized block.
Given below are the steps to remove the program from the cache which should be performed as one atomic operation. Though, ConcurrentHashMap is thread-safe, it needs to be locked while executing these 3 steps as we do not want other threads to access the cache concurrently while this operation is being performed. The code for these steps is given below in Listing 2. The servlet instance need not be locked while removing the programs from the cache.
Steps to remove program from cache:
if(programsCache.size() > MAX_ALLOWED_SIZE) {
synchronized(programsCache) {
long leastCount = Long.MAX_VALUE;
//Get the least count
for(ProgramSearchResult result : programsCache.values()) {
//if a program with less search count is found
if(result.getCount() < leastCount) {
leastCount = result.getCount();
}
}
//Get least frequently searched program numbers
Set programNumbers = new HashSet();
for(ProgramSearchResult result : programsCache.values()) {
if(result.getCount() == leastCount) {
programNumbers.add(result.getProgram().
getProgramNumber());
}
}
//remove the least frequently searched program numbers
for(String programNumber : programNumbers) {
programsCache.remove(programNumber);
}
}
}
Listing 2. Remove least frequently searched programs from the cache
One more drawback of using this strategy for implementing cache is that the counter needs to be decremented.
An alternate and better strategy
The above strategy uses expensive locking and complex implementation. An alternate and better strategy for implementing the cache is to use another LIFO queue to store the searched program numbers as given below in Listing 3. When a program is searched, its program number is removed from the LIFO queue and added at its head if the program exists in database. Thus, the program number least frequently searched will be at the tail of the LIFO queue. The program with this program number is removed from the cache when the cache size exceeds the maximum allowed size. The LinkedList is used to implement the LIFO queue.
private ConcurrentMap programsCache =
new ConcurrentHashMap();
private LinkedList programNumbers = (LinkedList)
Collections.synchronizedList(new LinkedList());
doPost(...) {
...
try {
Program program = programsCache.get(programNumber);
if(program == null) {
//program is not found in cache
//Fetch it from the database
program = ProgramDAO.getInstance().
findByProgramNumber(programNumber);
...
}
programsCache.putIfAbsent(programNumber,program);
//if the program is found in cache or database
synchronized(programNumbers) {
//remove the program number from the linked list
programNumbers.remove(programNumber);
//add it as the first element of the linked list
programNumbers.addFirst(programNumber);
}
//code to remove programs from cache
if(programsCache.size() > MAX_ALLOWED_SIZE) {
//remove the least frequently searched program
programsCache.remove(programNumbers.removeLast());
}
}
catch(EntityNotFoundException exp) {
//program is not found in database
...
}
}
Listing 3. A partial-blocking cache implementation
LinkedList is not thread-safe. The Collections.synchronizedList() to wrap the linked list in a thread-safe list. In this cache, the operations to remove the program number from the LIFO queue and put it at the head when searched should be performed as one atomic operation.
We are not performing putIfAbsent() and remove() on ConcurrentHashMap as one atomic operation. So the cache size can grow beyond the maximum allowed when multiple threads are concurrently executing but for this trade-off there is no need of locking the ConcurrentHashMap instance as we know that when all threads have finished execution, the cache size will not be more than the maximum allowed size. Locking the ConcurrentHashMap while executing these two methods would lead to blocking other threads for its access.
Also, the size of the LIFO queue may not be same as the cache size when threads are executing concurrently but eventually after all the threads stop execution, the LIFO queue size will not be more than the maximum allowed size. For this trade-off and since this is a LIFO queue, there is no need to execute put() in ConcurrentHashMap, placing the searched program number at head of LinkedList and removing the least frequently searched program from ConcurrentHashMap as one atomic operation.
This partial-blocking cache implementation using LIFO queue in Listing 3 is thread-safe and has better performance than the strategy using search counters given in Listing 1. This strategy will work efficiently as long as the cache size is larger than number of concurrent threads accessing the servlet.
The maximum number of concurrent threads accessing the servlet can be found by using the code in Listing 4. For performance tuning, externalize the maximum allowed cache size by configuring it in the properties file and access it in the servlet. Keep monitoring the maximum number of concurrent threads from the log file periodically. Modify the maximum cache size in the properties file when required.
private AtomicInteger concurrentThreadCount = new AtomicInteger();
private AtomicInteger maxConcurrentThreadCount = new AtomicInteger();
...
doPost(...) {
concurrentThreadCount.incrementAndGet();
...
synchronized(this) {
if(maxConcurrentThreadCount.get() <
concurrentThreadCount.get()) {
maxConcurrentThreadCount.set(
concurrentThreadCount.get());
}
}
//record the maxConcurrentThreadCount.get() in logs
concurrentThreadCount.decrementAndGet();
}
Listing 4. Get maximum number of threads concurrently executing the doPost() method