Lru Cache Design

LRU cache design

A linked list + hashtable of pointers to the linked list nodes is the usual way to implement LRU caches. This gives O(1) operations (assuming a decent hash). Advantage of this (being O(1)): you can do a multithreaded version by just locking the whole structure. You don't have to worry about granular locking etc.

Briefly, the way it works:

On an access of a value, you move the corresponding node in the linked list to the head.

When you need to remove a value from the cache, you remove from the tail end.

When you add a value to cache, you just place it at the head of the linked list.

Thanks to doublep, here is site with a C++ implementation: Miscellaneous Container Templates.

Implement LRU Cache in C++

dq.erase(mp[key].first);

This is (potentially) erases a value from the middle of the deque.

Erasing from a middle of a deque invalidates all other existing iterators to the dequeue. Only erasing from the beginning or the end of a deque does not invalidate any other iterators to the non-erased deque values.

At this point, all other iterators in your map are no longer valid. From this point on, using any other remaining iterators, via your map, becomes undefined behavior.

You will need to completely redesign your implementation. deque cannot be used in this manner.

C++ LRU cache - need suggestions on how to improve speed

Here's some optimizations that might help:

Take this segment of code from the get function:

    if(umap.count(key)){
        // remove it from the old position 
        klist.erase(umap[key].second);

The above will lookup key in the map twice. Once for the count method to see if it exists. Another to invoke the [] operator to fetch its value. Save a few cycles by doing this:

auto itor = umap.find(key);
if (itor != umap.end()) {
        // remove it from the old position 
        klist.erase(itor->second);

In the put function, you do this:

    if(umap.count(key)){
        klist.erase(umap[key].second);
        umap.erase(key);
    }

Same thing as get, you can avoid the redundant search through umap. Additionally, there's no reason to invoke umap.erase only to add that same key back into the map a few lines later.

Further, this is also inefficient

    umap[key].first = value;
    umap[key].second = --key_loc;

Similar to above, redundantly looking up key twice in the map. In the first assignment statement, the key is not in the map, so it default constructs a new value pair thing. The second assignment is doing another lookup in the map.

Let's restructure your put function as follows:

void put(int key, int value) {

    auto itor = umap.find(key);
    bool reinsert = (itor != umap.end());

    // if key already exists delete it from the klist only
    if (reinsert) {
        klist.erase(umap[key].second);
    }
    else {
        // if the unordered map is at max capacity
        if (umap.size() == cap) {
            umap.erase(klist.front());
            klist.pop_front();
        }
    }

    // finally update klist and umap
    klist.push_back(key);
    list<int>::iterator key_loc = klist.end();
    auto endOfList = --key_loc;

    if (reinsert) {
        itor->second.first = value;
        itor->second.second = endOfList;
    }
    else  {
        const pair<int, list<int>::iterator> itempair = { value, endOfList };
        umap.emplace(key, itempair);
    }
}

That's as far as you can probably go by using std::list. The downside of the list type is that there's no way to move an existing node from the middle to the front (or back) without first removing it and then adding it back. That's a couple of unneeded memory allocations to update the list. Possible alternative is that you just use your own double-linked list type and manually fixup the prev/next pointer yourself.

Implementing LRU Cache using doubly linked list and unordered map in c++

In feedin replace

if((it.second) == L.end())

with

if((it.second) == --L.end())

and ensure capacity can never be zero. This shouldn't be much of a restriction because there is no point to a LRU cache that can't cache anything.

Explanation:

I believe the mistake is in believing that L.end() returns an iterator referring to the last item in L. It doesn't. end() returns a sentinel marking the end of the list. It doesn't correspond to any elements in the list, and this is why it is useable as the item not found case in searches.

In feedin,

if((it.second) == L.end())

compares L iterators stored in M to an iterator that is guaranteed to not be in L and thus will not be in M. Nothing is ever found. To get an iterator for the last item in L, you need --L.end(). Note that --L.end() is valid when the list is not empty, something guaranteed by a capacity greater than 0.

How does an LRU cache fit into the CAP theorem?

First of all, a cache too small to hold all the data (where an eviction might happen and the LRU part is relevant) is not a good example for the CAP theorem, because even without looking at consistency, it can't even deliver partition tolerance and availability at the same time. If the data the client asks for is not in the cache, and a network partition prevents the cache from getting the data from the primary database in time, then it simply can't give the client any answer on time.

If we only talk about data actually in the cache, we might somewhat awkwardly apply the CAP-theorem only to that data. Then it depends on how exactly that cache is used.

A lot of caching happens on the same machine that also has the authoritative data. For example, your database management system (say PostgreSql or whatever) probably caches lots of data in RAM and answers queries from there rather than from the persistent data on disk. Even then cache invalidation is a hairy problem. Basically even without a network you either are OK with sometimes using outdated information (basically sacrificing consistency) or the caching system needs to know about data changes and act on that and that can get very complicated. Still, the CAP theorem simply doesn't apply, because there is no distribution. Or if you want to look at it very pedantically (not the usual way of putting it) the bus the various parts of one computer use to communicate is not partition tolerant (the third leg of the CAP theorem). Put more simply: If the parts of your computer can't talk to one another the computer will crash.

So CAP-wise the interesting case is having the primary database and the cache on separate machines connected by an unreliable network. In that case there are two basic possibilities: (1) The caching server might answer requests without asking the primary database if its data is still valid, or (2) it might check with the primary database on every request. (1) means consistency is sacrificed. If its (2), there is a problem the cache's design must deal with: What should the cache tell the client if it doesn't get the primary database's answer on time (because of a partition, that is some networking problem)? In that case there are basically only two possibilities: It might still respond with the cached data, taking the risk that it might have become invalid. This is sacrificing consistency. Or it may tell the client it can't answer right now. That is sacrificing availability.

So in summary

• If everything happens on one machine the CAP theorem doesn't apply
• If the data and the cache are connected by an unreliable network, that is not a good example of the CAP theorem, because you don't even get A&P even without C.
• Still, the CAP theorem means you'll have to sacrifice C or even more of A&P than the part a cache won't deliver in the first place.
• What exactly you end up sacrificing depends on how exactly the cache is used.

Is this a truly Thread-Safe LRU Cache Design with Minimal Blocking?

The pseudocode does not describe a thread-safe algorithm.

Consider that multiple threads may be waiting for a particular item to be fully downloaded. Each of them would be holding (in stack memory) the same item_iterator. Download finishes. When the first waiting thread wakes up, to maintain the LRU, it will invalidate iterator still being held by the others.

(Another problem I thought of is OK as long as the maximum number of participating threads is less than MAX_CACHE_SIZE.)

Is it sufficient fix to lookup fresh item_iterator after waking up? Maybe, but it is concerning that the main data structure being shared, the storage itself, is frequently mutated while threads are active in various states. It is not a robust design.

I would consider keeping the storage stable and evaluating the LRU a different way.

---

Related Topics