2

Please note that this is about a thread-safe LRU cache (not simply a LRU cache as specified in https://leetcode.com/problems/lru-cache/description/). It isn't a duplicate of LRU cache design question as there are some tricky aspects of Locking Hashtable/Linkedlist(LL) that aren't addressed in other multithreaded LRU design questions.

The credited approach on how to make LRU cache thread-safe in C++ seems to be all over the place. I noticed some links mentioning that locking both Hashtable/LL is ok while some others don't directly address the issue in C++ and just vaguely discuss various ways to do it.

  • Can someone describe a functional and efficient approach using locks that includes what's locked and when implementing a multithreaded version of the LRU cache in C++ https://leetcode.com/problems/lru-cache/description/ so all get/set operations are O(1) ?

  • how do caches such as memcached by Facebook implement multithreading support?

  • 1
    Well, at first, locks won't change complexity in any way while adding significant constant overhead. Second, you are limiting yourself not considering other synchronization methods, or no synchronization at all if we are speaking about single threaded applications, Redis for example. It performs quite well nevertheless single threaded. – Andrew Selivanov Aug 14 '18 at 8:53
  • @andrew any effective synchronization method to make it concurrent will do. Can you post code? Memcached has multi threaded lru so they probably use concurrent locks. – Joe Black Aug 14 '18 at 19:36
  • Whatd be the code to make it concurrent using locks? – Joe Black Aug 14 '18 at 19:37
1

I have implemented this using a multiple readers/single writer lock. This is a type of lock that allows multiple threads to read from the cache at the same time, but only allows a single thread to write to the cache. The basic gist of it is something like this (pseudocode):

void put(ItemType item, KeyType key)
{
    cacheLock.lockForWriting();

    // If it is already in the list and map remove it
    list.remove(key);
    map.remove(key);

    // Now put it back into both
    map [ key ] = item;
    list.append(key);

    // If we're past the size limit of the cache, remove the least recently used item
    if (list.size() > MAX_CACHE_SIZE)
    {
        ListNode *oldKey = list.head;
        list.head = list.head.next;
        map.remove(oldKey->key);
        delete oldKey;
    }

    cacheLock.unlock();
}

ItemType* get(KeyType key)
{
    cacheLock.lockForReading();
    ItemType* item  = map [ key ];
    cacheLock.unlock();

    // NOTE: This assumes that the cache is not the owner of this object
    // If it is, then you need to either make a copy of it inside the lock 
    // above or use smart pointers instead of raw  pointers
    // because when it gets kicked out of the cache it will be deleted.
    return item;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.