Interview task: 2 level cache
Some months ago I have passed one technical interview and the main aspect of this interview was a practical task: implement 2 level cache. I have heard before about this task but never do it. Task is not so simple as it is considered to be at first glance, so I decide to share with my implementation.
First of all, full details of task:
- Cache should implement the following interface:
public interface Cache - Cache should have 2 levels: L1 - memory, L2 - file system.
- Cache should support different eviction policies.
- Cache size and eviction policy should be configurable.
- Code should be covered by unit tests using JUnit/TestNG + any mock library Mockito, EasyMock, etc.
- Project should be build via Maven, Gradle, Ant or similar tool.
- Cache should be thread safe.
I should notice, that I have small experience with caches and moreover I use 3rd party caches without inventing my own, so I have very small knowledge about the internals of caches. As you can see from task details, it requires some dig into caches logic.
First of all, I need to find out what kind of evictions policies exist. I find good document of most popular policies on Ehcache site. I decide to start from FIFO policy as it seems to be the simplest one.
Secondly, it was very useful to draw couple schemas of object's transfers between cache's level and persistent storage. It will give clear step by step logic for object's placing in every cache layer. Let's start with putting object in cache:
- If the first lvl of the cache has no free space for a new element, perform evict from the first lvl.
- If the second lvl has no free space for evicted element that was evicted from the first lvl, perform evict from the second lvl.
- Put new element into the first lvl cache.
Now let's look at getting object from cache:
- Try to get the element from 1 lvl of cache.
- If nothing was obtained in step 1, try to get the element from 2 lvl of cache.
- If nothing was obtained in step 2, try to get the element from persistent storage.
- In a case on steps 2 and 3 was not null result, put this result in the cache (in this case it will appear on top of cache, in its 1 lvl).
Step 4 will point us to the logic of put operation, that were described above.
Next, let's discuss how fast cache should be. There is no limit on performance in init, but the main aim of cache reduce the cost of getting elements from persistent storage. The best option is to get O(1) performance on both cache levels while getting an element. Another important operation of cache is an eviction. It is not so frequent and simple as getting of the object, but nevertheless, sometimes performing get operation mean perform one or two evict operations, so it is also important to make it as fast as possible.
Now, we are very close to starting implementation. Let's talk about what entities should exists on the implementation level.
- Cache itself as a point of connection of all other systems. It will be connected to any upstream system via interface that was declared in init task description:
public interface Cache - Cache consists of some levels. It seems that any layer will have same methods, but it will differ with the internal logic of saving and getting an object in different ways. So it also worth to create one more interface for cache layers, so upper code will deal with any layer in same way and we can easily cache layer implementation without reworking of upstream logic:
public interface CacheLayer -
Every cache layer should have the ability to perform eviction according to some policy. It is also worth to do evict operation as a separate entity with an interface. It will give the ability to change policy without any effort on rework. For proper performing of eviction, sometimes we need to analyse what object was obtained from cache or was put in it (for example, to determine what object is least recently used). So cache layer should also pass get() and put() calls to eviction layer, that is why in interface methods get and put are introduced.
public interface EvictionPolicy
Having a deal with get() and put() methods in EvictionPolicy interface will cause duplicate of code, because in every implementation of CacheLayer we have to explicitly call those methods, something like this:
public ExampleCacheLayer<K,V> implements CacheLayer<K,V> {
...
EvictionPolicy<K,V> policy = new MyEvictionPolicy();
public void get(K key) {
policy.get(key);
...
//other logic of CacheLayer get
};
public void put(K key, V value) {
policy.put(key);
...
//other logic of CacheLayer put
};
}In every implementation of CacheLayer we can not forget to add this calls, otherwise, the eviction will not work as expected. In such situation, it is better to make auto call of put and get methods of policy. It could be done via abstract class:
public abstract class AbstractCacheLayer<K,V> implements CacheLayer<K,V> {
protected EvictionPolicy<K,V> evictionPolicy;
public AbstractCacheLayer(EvictionPolicy<K,V> evictionPolicy) {
this.evictionPolicy = evictionPolicy;
}
@Override
public V get(K key) {
evictionPolicy.get(key);
return performGet(key);
}
@Override
public void put(K key, V value) {
evictionPolicy.put(key,value);
performPut(key,value);
}
protected abstract V performGet(K key);
protected abstract void performPut(K key, V value);
Take a look: in AbstractCacheLayer there are public methods `put()` and `get()`, which actually will be called by upper code. In every method performed an obligatory call to policy methods and then call redirected to abstract protected methods `performGet()` and `performPut()`, which will be implemented with actual logic of CacheLayer implementation by a child class. So we have eliminated duplication of code and implementation of CacheLayer should not bother about calls to policy methods. Of course, implementation of CacheLayer now should be created with `extends AbstractCacheLayer`.
Ok, now we are ready to start implementation. Here is first cache layer:
public class FirstLvlCacheLayer<K,V> extends AbstractCacheLayer<K,V> {
private Map<K,V> memCache;
private final int boundSize;
private int cacheSize;
private CacheLayer<K,V> nextLayer;
public FirstLvlCacheLayer(EvictionPolicy evictionPolicy, int boundSize, CacheLayer<K,V> nextLayer) {
super(evictionPolicy);
this.memCache = new ConcurrentHashMap<K,V>();
if (boundSize <= 0) {
throw new IllegalArgumentException("Cache size should be greater than 0");
}
this.boundSize = boundSize;
this.cacheSize = 0;
this.nextLayer = nextLayer;
}
@Override
protected V performGet(K key) {
return memCache.get(key);
}
@Override
protected synchronized void performPut(K key, V value) {
if (cacheSize >= boundSize) {
K evictKey = evictionPolicy.evict();
if (nextLayer != null && memCache.containsKey(evictKey)) {
nextLayer.put(evictKey, memCache.get(evictKey));
}
remove(evictKey);
}
memCache.put(key, value);
cacheSize++;
}
@Override
public int getSize() {
return cacheSize;
}
@Override
public synchronized void remove(K key) {
if (memCache.containsKey(key)) {
memCache.remove(key);
cacheSize--;
}
}
}
As a backbone of first lvl cache here used ConcurentHashMap. It gives the performance of getting operation O(1) and gives good multithread support out of the box. There is a problem with controlling the size of such HashMap, cause according to documentation method size() of ConcurentHashMap does not guarantee returning of the actual value of HashMap size. But maintaining size below the limit is the critical part of the cache, so that is why cacheSize variable was introduced, its store actual size of HashMap. This variable being wrote and read from syncronize methods, so it has no problems with the multithread environment. There is only one not synchronized method - getSize() and it can return outdated value of size, but for upper code, it is not so critical, from my point of view.
The most complex method is `performPut()` method. In case first level cache filled up to the limit, it asks eviction policy to choose element the will be deleted from cache layer. Once evict element chosen, we put it in second level cache and remove this element from the first level.
Now, it is time to take look on second level cache:
public class SecondLvlCacheLayer<K,V> extends AbstractCacheLayer<K,V> {
public static final String CACHE_FOLDER = "cache";
private final int boundSize;
private int cacheSize;
private ConcurrentHashMap<K,UUID> fileNames;
public SecondLvlCacheLayer(EvictionPolicy<K,V> evictionPolicy, int boundSize) {
super(evictionPolicy);
if (boundSize <= 0) {
throw new IllegalArgumentException("Cache size should be greater than 0");
}
this.boundSize = boundSize;
this.cacheSize = 0;
this.fileNames = new ConcurrentHashMap<K,UUID>();
File folder = new File(CACHE_FOLDER);
if (!folder.exists()) {
folder.mkdirs();
}
cleanCacheFolder(folder);
}
@Override
protected V performGet(K key) {
V value = null;
FileInputStream fis = null;
ObjectInputStream oin = null;
UUID fileName = fileNames.get(key);
if (fileName == null) {
return value;
}
File cacheFile = new File(CACHE_FOLDER + File.separatorChar + fileName);
if(!cacheFile.exists()) {
return value;
}
try {
fis = new FileInputStream(cacheFile);
oin = new ObjectInputStream(fis);
value = (V)oin.readObject();
}catch (IOException ex){
System.out.println("Problem with file reading value with key " + key + ':' + ex.getMessage());
}catch (ClassNotFoundException ex){
System.out.println("Class does not support serialization:" + ex.getMessage());
}finally {
try {
if (oin != null) {
oin.close();
}
}catch(IOException ex){
System.out.println("Problem while closing object input stream: " + ex.getMessage());
}
}
return value;
}
@Override
protected synchronized void performPut(K key, V value) {
if (cacheSize >= boundSize) {
K evictKey = evictionPolicy.evict();
remove(evictKey);
}
FileOutputStream fos = null;
ObjectOutputStream oos = null;
UUID fileName = UUID.randomUUID();
try {
File cacheFile = new File(CACHE_FOLDER + File.separatorChar + fileName.toString());
if(!cacheFile.exists()) {
cacheFile.createNewFile();
}
fos = new FileOutputStream(cacheFile);
oos = new ObjectOutputStream(fos);
oos.writeObject(value);
cacheSize++;
fileNames.put(key, fileName);
}catch (IOException ex){
System.out.println("Problem with file writing: " + ex.getMessage());
}finally {
try {
if (oos != null) {
oos.close();
}
}catch(IOException ex){
System.out.println("Problem while closing object output stream: " + ex.getMessage());
}
}
}
@Override
public int getSize() {
return cacheSize;
}
@Override
public synchronized void remove(K key) {
UUID fileName = fileNames.get(key);
if (fileName != null) {
File file = new File(CACHE_FOLDER + File.separatorChar + fileName.toString());
if (file.exists()) {
file.delete();
}
cacheSize--;
}
}
public String getFileNameForKey(K key) {
UUID fileName = fileNames.get(key);
return fileName != null ? fileName.toString() : null;
}
private void cleanCacheFolder(File folder) {
File[] files = folder.listFiles();
if (files != null) {
for (File f: files) {
if (!f.isDirectory()) {
f.delete();
}
}
}
}
}
This class seems to be much more complicated that code of the first level cache, but here just lot of lines used with trivial file I/O. The main idea of the second level cache is almost the same as in the first level - ConcurentHashMap, which stores keys, but instead of values (as it were in the first level), it stores a name of a file with value. This allows us to get value in O(1) time.
Let's deal with eviction policy now. I have implemented two eviction policy: FIFO (the first inserted value, will be pushed out of cache the first) and Least Recently Used ( an element which was not touched in the cache for the longest time will be pushed out). The Fifo policy is really simple - it is used ConcurrentLinkedQueue under the hood and gives us O(1) on eviction. Meanwhile, LRU policy is not so easy: it necessary to store the timestamp of the call to an element and during eviction find the key with the smallest timestamp.
public class LRUEvictPolicy implements EvictionPolicy {
private ConcurrentHashMap timeOfUse;
public LRUEvictPolicy() {
this.timeOfUse = new ConcurrentHashMap();
}
@Override
public synchronized K evict() {
K result = null;
List sortedKeys = new ArrayList(timeOfUse.keySet());
if (sortedKeys.size() > 0) {
Collections.sort(sortedKeys, new Comparator() {
public int compare(K key1, K key2) {
return timeOfUse.get(key1).compareTo(timeOfUse.get(key2));
}
});
result = sortedKeys.get(0);
timeOfUse.remove(result);
}
return result;
}
@Override
public void get(K key) {
timeOfUse.replace(key, new Long(System.nanoTime()));
}
@Override
public void put(K key, V value) {
timeOfUse.put(key, new Long(System.nanoTime()));
}
}
This type of eviction requires O(N*logN).
To test this cache let's create some datastore, for example, list of top10 google keywords and create test class, which will measure all the staff:
public class App
{
public static void main( String[] args )
{
final int THREAD_NUMBER = 5;
final int THREAD_CYCLES = 10;
final CyclicBarrier startBarrier = new CyclicBarrier(THREAD_NUMBER);
final CountDownLatch endLatch = new CountDownLatch(THREAD_NUMBER);
final AtomicLong totalTime = new AtomicLong(0);
final AtomicInteger notFoundErrors = new AtomicInteger(0);
final Random randomGenerator = new Random();
CacheLayer secondLvl = new SecondLvlCacheLayer(new FifoEvictPolicy(), 3);
CacheLayer firstLvl = new FirstLvlCacheLayer(new FifoEvictPolicy(), 3, secondLvl);
final Cache cache = new TwoLevelCacheImpl(firstLvl, secondLvl, new SimpleDataSourceImpl());
for (int i = 0; i < THREAD_NUMBER; i++) {
new Thread("New Thread #" + i) {
public void run(){
try{
System.out.println("Thread " + Thread.currentThread().getName() + " awaits");
startBarrier.await();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (BrokenBarrierException e) {
e.printStackTrace();
}
System.out.println("Thread " + Thread.currentThread().getName() + " started");
for (int i = 0; i < THREAD_CYCLES; i++) {
//find what to ask from cache
List keySet = new ArrayList(SimpleDataSourceImpl.topGoogleWords.keySet());
String keyToRetrive = keySet.get(randomGenerator.nextInt(keySet.size()));
//cache work
long start = System.nanoTime();
Integer result = cache.get(keyToRetrive);
long end = System.nanoTime();
//valide cache result
if (!SimpleDataSourceImpl.topGoogleWords.get(keyToRetrive).equals(result)) {
notFoundErrors.incrementAndGet();
}
totalTime.addAndGet(end - start);
}
endLatch.countDown();
}
}.start();
}
try{
endLatch.await();
}catch(InterruptedException e){
e.printStackTrace();
}
System.out.println("Total time: " + totalTime.longValue() + " for " + THREAD_CYCLES * THREAD_NUMBER + " data requests");
System.out.println("Time per request: " + ((double)totalTime.longValue()/(double)(THREAD_CYCLES * THREAD_NUMBER)) + " ns");
System.out.println("First lvl hits: " + ((TwoLevelCacheImpl)cache).getFirstLvlHits() + ". Second lv hits: " + ((TwoLevelCacheImpl)cache).getSecondLvlHits());
System.out.println("Errors of not equal result from cache: " + notFoundErrors.intValue());
}
}