Associative Cache in multithreading environment

Viewed 360

I'm trying to implement a version of N-way associative cache in assumption that it can be used by multiple threads. The data structure is pretty straightforward - a high level class to represent a set of cache lines and data structure to represent an individual cache line (I will omit unnecessary details):

public static class SetAssociativeCache<TKey, TValue> {
    
    private final int setCount;
    private final List<CacheSet<TKey, TValue>> sets;
    private final AtomicInteger itemsCount;

    ...

    public void set(TKey key, TValue value) {
    ...
    }

    public TValue get(TKey key) {
    ...
    }

    public void addOneItem() {
        itemsCount.incrementAndGet();
    }

    public void deleteOneItem() {
        itemsCount.decrementAndGet();
    }

    public int getCount() {
        return itemsCount.get();
    }
}

And

public class CacheSet<TKey, TValue> {
    private final int capacity;
    private final List<CacheItem<TKey, TValue>> store;
    private final LinkedList<Integer> usageTracker;
    private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    
    ...
    public void set(TKey key, TValue value) {
    ...
    addOneItem();
    ...
    }

    public TValue get(TKey key) {
    ...
    }
}

I would like to have following features in the implementation:

  • On a set operation, only cache line that corresponds to instead key is locked
  • The same for a get operation - only one cache line is blocked
  • And I also would like to have a total number of elements in the cache

Currently, I did manage to achieve it via ReentrantReadWriteLock on a cache set level (CacheSet) and an AtomicInteger variable that has a total number of elements in cache, on a cache level (SetAssociativeCache). On every insert, I call either addOneItem or deleteOneItem (on cache eviction). Even though the approach seems to work, I don't really like the fact that cache set has a link back to the parent class.

I think the better idea is to store the items count on a CacheSet level (CacheSet) and execute aggregation function on a Cache (SetAssociativeCache) level, but I can't think of any way to implement it without completely blocking set operations on all cache sets.

Could you please advise if there is a better or more elegant way to implement a behavior that I've explained above?

0 Answers
Related