5
\$\begingroup\$

I found this problem in a book and found it interesting. wrote this class to implement a Least Recently Used Cache with TTL. Goal -

  1. LRU cache with TTL
  2. Multithreaded.
  3. Functions: Get(key), Put(key,value), average()
  4. Runtime of get and put can be compromised (but still as fast as possible) for fast run time of avg()

Any inputs on correctness of the code, locking correctness, potential improvement in finer locking would be really helpful. Thank you.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <list>
#include <map>
#include <mutex> 
#include <condition_variable>
#include <thread>
#include <atomic>


const int TTLSeconds = 20;

/*Node that holds the key, value and the expiry time of a key, value pair*/
struct Node
{
    int key;
    int value;
    time_t expiryTime;
  
    Node(int key, int val, time_t expiryTime = time(nullptr) + TTLSeconds) : key(key), value(val), expiryTime(expiryTime) {}
};


struct IteratorsContainer
{
    std::list<Node>::iterator cacheIterator;
    std::list<int>::iterator keyIteratorInTimeBucket;
};

class LRUCache
{
    private:
        int capacity;
        
        /* MRU to LRU. Holds the nodes */
        std::list<Node> cache;
  
        /* TimeBuckets. <expiryTime, list<keys that expire at expiryTime>  */
        std::map<time_t, std::list<int>> timeBuckets;
  
        /* Holds iterator to cache and timeBuckets for each key 
          Could have used pair<list<Node>::iterator, list<int>::iterator> but 
          created a struct for better readability
        */
        std::unordered_map<int, IteratorsContainer> keyIteratorsMap;
  
        /* To calculate average */
        std::atomic<double> sum;
        std::atomic_int count;
  
        std::mutex mtx;
        
        /* cleanUpThread wakes up every n seconds and removes expired nodes */
        std::thread cleanUpThread;
        std::atomic_bool stopCleanUpThread;
  
        //Evict expired nodes
        void evictExpired();
  
        //Updates cache and moves entry to cache[0] 
        void updateCache(int key, int value);
  
        //Evict the least recently used. cache.back()
        void evictLRU();
  
    public:
        LRUCache(int capacity = 3) : capacity(capacity), sum(0.0), count(0)
        {
            stopCleanUpThread = false;
            cleanUpThread = std::thread(&LRUCache::evictExpired, this);
        }
  
        ~LRUCache()
        {
            stopCleanUpThread = true;
            if (cleanUpThread.joinable())
            {
                cleanUpThread.join(); 
            }
        }
        void stopCleanUp();
        int get(int key);
        void put(int key, int value);
        void printAverage();
  
        void callAverageEveryNSeconds();
};


void LRUCache::evictExpired()
{
    while (!stopCleanUpThread)
    {
        //Wake up and check every 1.5 seconds
        std::this_thread::sleep_for(std::chrono::milliseconds(1500));
      
        {
            std::lock_guard<std::mutex> lk(mtx);
            
            auto it = timeBuckets.begin();
          
            //worst case run time - O(nlogn)
            while (it != timeBuckets.end())
            {
                auto currentTime = time(nullptr);
              
                if (it->first > currentTime)
                {
                    // entries beyond these haven't expired
                    break; 
                }
              
                //Evict expired keys
                for (int key : it->second)
                {
                    std::cout << "Key " << key << " expired. Evicting\n";
                  
                    IteratorsContainer temp = keyIteratorsMap[key];
                    int val = temp.cacheIterator->value;
                    
                    cache.erase(temp.cacheIterator);
                    sum = sum - val;
                    --count;
                }
              
                auto current = it;
                ++it;
                timeBuckets.erase(current);
            }
        }
    }
}


void LRUCache::stopCleanUp()
{
    stopCleanUpThread = true; 
}


void LRUCache::updateCache(int key, int value)
{
    IteratorsContainer temp = keyIteratorsMap[key];
    
    int currentValue = temp.cacheIterator->value;
    auto currentExpiryTime = temp.cacheIterator->expiryTime;
    auto newExpiryTime = time(nullptr) + TTLSeconds;

    cache.erase(temp.cacheIterator);
    cache.push_front(Node(key, value, newExpiryTime));

    timeBuckets[currentExpiryTime].erase(temp.keyIteratorInTimeBucket); //O(logn)
    if (timeBuckets[currentExpiryTime].empty())
    {
        timeBuckets.erase(currentExpiryTime); 
    }
    timeBuckets[newExpiryTime].push_front(key);

    keyIteratorsMap[key] = {cache.begin(), timeBuckets[newExpiryTime].begin()};
  
    sum = sum - currentValue;
    sum = sum + value;
}


int LRUCache::get(int key) // O(logn)
{
    if ( keyIteratorsMap.find(key) == keyIteratorsMap.end())
    {
        return -1; 
    }
  
    IteratorsContainer temp = keyIteratorsMap[key];
    auto currentTime = time(nullptr);
    auto expiryTime = temp.cacheIterator->expiryTime;
    int value = temp.cacheIterator->value;
  
    if (expiryTime < currentTime)
    {
        return -1; 
    }
  
    std::lock_guard<std::mutex> lk(mtx);
    updateCache(key, value); //O(logn)
    
    return value;
}


void LRUCache::evictLRU()
{
    Node evictionCandidate = cache.back();
    IteratorsContainer temp = keyIteratorsMap[evictionCandidate.key];
    timeBuckets[evictionCandidate.expiryTime].erase(temp.keyIteratorInTimeBucket);
    if (timeBuckets[evictionCandidate.expiryTime].empty())
    {
        timeBuckets.erase(evictionCandidate.expiryTime);
    }
    cache.pop_back();
    keyIteratorsMap.erase(evictionCandidate.key);

    sum = sum - evictionCandidate.value;
    --count;
    std::cout << "Capacity reached. Key " << evictionCandidate.key << std::endl;
}

void LRUCache::put(int key, int value) // O(logn)
{
    /* For Testing */
    int sleepTime = rand() % 10000;
    std::this_thread::sleep_for(std::chrono::milliseconds(sleepTime));
    /* Test code ends */
  
    std::lock_guard<std::mutex> lk(mtx);
    if (keyIteratorsMap.find(key) != keyIteratorsMap.end())
    {
        std::cout << "Key exists. Update cache\n";
        updateCache(key, value); //O(logn)
        return;
    }
  
    if ((int)keyIteratorsMap.size() == capacity)
    {
        evictLRU(); //O(logn)
    }
  
    auto expiryTime = time(nullptr) + TTLSeconds;
    cache.push_front(Node(key, value, expiryTime));
    timeBuckets[expiryTime].push_front(key);
    keyIteratorsMap[key] = {cache.begin(), timeBuckets[expiryTime].begin()};

    sum = sum + value;
    ++count;
    
    std::cout << "Key " << key << " inserted. Value = " << value << " . Expiry = " << expiryTime << std::endl;
}

void LRUCache::printAverage() //O(1)
{
    if (count == 0)
    {
        std::cout << "Averge = " << 0.0 << std::endl;
        return;
    }
    std::cout << "Averge = " << sum/count << std::endl;
}

//Test function
void LRUCache::callAverageEveryNSeconds()
{
    int n = 0;
    int interval = 1500;
  
    while (n < 20)
    {
         std::this_thread::sleep_for(std::chrono::milliseconds(interval));
         printAverage();
         ++n;
    }
}

int main() 
{
    
    const int CACHE_SIZE = 5;
    const int MAX_THREADS = 6;
  
    LRUCache cache(CACHE_SIZE);
  
    //std::vector<std::thread> threadPool(6);
    std::thread threadPool[MAX_THREADS];
  
    for (int i = 0; i < MAX_THREADS; ++i)
    {
        int key = rand() % 100;
        int val = 100 + rand() % 100;
        threadPool[i] = std::thread(&LRUCache::put, &cache, key, val);
    }
  
    std::thread callAverage(&LRUCache::callAverageEveryNSeconds, &cache);
    
    std::this_thread::sleep_for(std::chrono::seconds(25));
  
    for (int i = 0; i < MAX_THREADS; ++i)
    {
        threadPool[i].join();
    }
    callAverage.join();
  
    return 0;
}```
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Very small: make TTLSeconds constexpr, such as constexpr int TTLSeconds = 20; \$\endgroup\$
    – NotAName
    Commented Jul 12, 2022 at 22:38

3 Answers 3

8
\$\begingroup\$

Move everything into class LRUCache

The constant TTLSeconds and the structs Node and IteratorsContainer are all just implementation details of LRUCache. Move everything into the latter, like so:

class LRUCache
{
    const int TTLSeconds = 20;

    struct Node {
        ...
    };

    struct IteratorsContainer {
        ...
    }

    int capacity;
    ...
};

This avoids polluting the global namespace, which is especially important for things with a generic name like Node.

Use std::chrono for everything related to time

It's weird to see you use std::chrono in some parts your code, but for the expiry times you use time_t and int. Use std::chrono for all things related to time. Note however that std::chrono supports multiple clocks, and you probably want to use std::chrono::steady_clock to measure time. This is how it can be used:

using clock = std::chrono::steady_clock;
using duration = clock::duration;
using time_point = clock::time_point;

const duration TTL = std::chrono::seconds(20);

struct Node {
    int key;
    int value;
    time_point expiryTime;

    Node(int key, int value, time_point expiryTime = clock::now()): ... {}
};

std::map<time_point, std::list<int>> timeBuckets;

Make it a template

Your LRUCache uses ints for keys and values. But what if you want to store something else? The solution is to make LRUCache a template, with the key and value types being template parameters:

template <class Key, class T>
class LRUCache {
    struct Node {
         Key key;
         T value;
         ...
    };

    struct IteratorsContainer {
         std::list<Node>::iterator cacheIterator;
         std::list<Key>::iterator keyIteratorInTimeBucket;
    };

    std::map<time_point, std::list<Key>> timeBUckets;
    std::unordered_map<Key, IteratorsContainer> keyIteratorsMap;
    ...

public:
    T get(Key key);
    void put(Key key, T value);
    ...
};

Remove code related to averages

Your LRUCache not only implements a LRU cache, but also has some functionality to calculate the average of the elements in the cache. Keep things simple and reduce the number of responsibilities of this class. By adding features like this, you actually make the code less generic and less useful. Ideally, LRUCache should just expose enough functionality that an external function can iterate over all the items in the cache and calculate something.

Evict expired events without using a thread

It should be possible to have an LRU cache that doesn't need a thread to clean up expired items. Instead, evict as necessary during put() and get(). In put(), you already do this. In get(), you check the expiry time of the node you are looking for, but you could make it so that if you find an expired item, you delete it immediately.

The thread doesn't make things more efficient. Either the interval it sleeps for is too large for the rate at which put() is called, in which case put() will do all the eviction work anyway, or it is too short and wastes CPU cycles for nothing, and even if the interval is perfectly balanced with regards to the frequency of put() and get() calls, the latter two functions still can't rely on the thread to have kicked in at the right time.

Without a thread you also don't have to deal with thread cleanup, and avoid having to wait 0.75 seconds on average when destroying an instance of LRUCache.

Use std::size_t for count, capacity and indices

An int might not be large enough to represent the maximum size a container can be. Furthermore, specifying a negative capacity leads to disaster. The right type for storing counts, sizes and indices is std::size_t.

Don't use a special value to indicate that an item was not in the cache

When your get() doesn't find an item or if it is already expired, it returns -1. But -1 is a valid int. What if I did a put(..., -1) before? The proper way to solve this is to use a separate value to indicate whether the item was found or not. For example (very simplified):

bool LRUCache::get(int key, int& value) {
    if (/* key in map and not expired */) {
        value = temp.cacheIterator->value;
        return true;
    } else {
        return false;
    }
}

If you can use C++17 or later, consider returning a std::optional type.

Missing locking in get()

In get(), you only take the lock right before updating the cache, but you don't use it for the part where you look up the value. Since another thread could be modifying the cache at the same time, bad things can happen. Just move the lock guard to the top of the function.

Simplifying cache management

There is a lot going on in your cache. There's lists and maps everywhere. Consider simplifying it. You should need only two things:

  1. An unordered map of keys to values and their expiry times.
  2. A container with the keys sorted on expiry time.

To insert an item, add it to the unordered map first, then add the key of the item you just inserted to the sorted container of expiry times. To evict the least recently used item, you just need to pop the first key from the sorted container of expiry times, and use that key to erase the corresponding element from the unordered map.

There are several ways to have a sorted container. A std::map is one way. However, as you probably noticed, you have an issue if you want to insert two items with the same timestamp. You can use std::multimap in that case, so you don't need to use a std::list yourself.

\$\endgroup\$
4
\$\begingroup\$

G. Sliepen's answer is pretty great, but has a fatal flaw in the final section "Simplifying Cache Management"! An unordered map, in general, can 'rehash itself' when items are inserted (see https://cplusplus.com/reference/unordered_map/unordered_map/insert/ ), which may invalidate any priorly-obtained iterators into that unordered map; specifically and worryingly for this recipe: those that are already stored in the auxiliary "container sorted on expiry time"! The recipe will work generally if you use a std::map instead of unordered_map.

\$\endgroup\$
4
  • \$\begingroup\$ Good point! I guess you could store just the key instead of an iterator; lookups into a std::unordered_map are then still O(1). \$\endgroup\$
    – G. Sliepen
    Commented Apr 15, 2023 at 22:08
  • \$\begingroup\$ Note that I've modified my answer to avoid risking someone not seeing your answer and doing the wrong thing. \$\endgroup\$
    – G. Sliepen
    Commented Apr 16, 2023 at 9:06
  • 1
    \$\begingroup\$ Oh yeah! That's a great additional observation about the average O(1) complexity of erase() by key (vs. erase() by iterator) when using an unordered_map! I appreciate your attention to this post (but do note your answer still refers to "iterator" in one spot - 2nd paragraph, 1st sentence). \$\endgroup\$ Commented Apr 17, 2023 at 7:41
  • \$\begingroup\$ Thanks for pointing that out! The goal of Stack Exchange is that answers are not just to help the original poster of the question, but also others who might want to learn from what is discussed here. So it's always good to fix mistakes, even in old answers :) \$\endgroup\$
    – G. Sliepen
    Commented Apr 17, 2023 at 7:57
0
\$\begingroup\$

maybe a bit late, but please pass by reference instead of pass by value when we can for example:

void LRUCache::updateCache(int key, int value) 

can be changed

void LRUCache::updateCache(const int& key, const int& value)

maybe when key and value are int it does not make program slower, but if the key and value are long string, it is really different.

\$\endgroup\$
2
  • \$\begingroup\$ can you be more specific where this applies? \$\endgroup\$
    – qwr
    Commented Jul 12, 2022 at 17:01
  • \$\begingroup\$ like you said, as long as you are not changing the const reference (which you have to purposely workaround to do), there should be no performance difference. \$\endgroup\$
    – qwr
    Commented Jul 12, 2022 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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