An expirable LRU cache implementation

Question

I implemented an ExpireLRUCache class, which will clear the data when it times out. There are two ways to achieve this:

1. Use a timer to clear the expire data
2. Call the clean function in Add and Get

If I use a struct in class, and it use the template typename, how to deal with this?

I put the declaration of Node at the top, because it will be used when it is used. Is it reasonable?

template <typename K, typename V>
class ExpireLRUCache {
 private:
  using Timestamp = std::chrono::time_point<std::chrono::system_clock>;
  struct Node {
    K key;
    V value;
    Timestamp timestamp;
  };

 public:
  using NodePtr = std::shared_ptr<Node>;
  using NodeIter = typename std::list<NodePtr>::iterator;
  using ExpiredCallBack = std::function<void(K, V)>;
  
  // Default timeout is 3000ms.
  ExpireLRUCache(size_t max_size)
     : max_size_(max_size), time_out_(3000), expired_callback_(nullptr) {}

  ExpireLRUCache(size_t max_size, uint32_t time_out, ExpiredCallBack call_back)
     : max_size_(max_size), time_out_(time_out), expired_callback_(call_back) {}

  void Add(K key, V value);
  V Get(K key);

  size_t Size() const;

 private:
  void Expired();

  mutable std::mutex mutex_;
  std::list<NodePtr> list_;
  std::unordered_map<K, NodeIter> map_;

  size_t max_size_;
  // ms
  uint32_t time_out_;

  ExpiredCallBack expired_callback_;  
};

template <typename K, typename V>
void ExpireLRUCache<K, V>::Add(K key, V value) {
  std::lock_guard<std::mutex> lock(mutex_);
  // if full, delete oldest
  if (list_.size() >= max_size_) {
    auto oldest = list_.back();
    list_.pop_back();
    map_.erase(oldest->key);
  }

  // if exist, delete it in the list, and then add to the front
  // then overwrite in map.
  if (map_.find(key) != map_.end()) {
    NodeIter iter = map_[key];
    list_.erase(iter);
  }

  auto timestamp = std::chrono::system_clock::now();
  NodePtr node = std::make_shared<Node>(Node{key, value, timestamp});
  list_.push_front(node);
  map_[key] = list_.begin();
}

template <typename K, typename V>
V ExpireLRUCache<K, V>::Get(K key) {
  std::lock_guard<std::mutex> lock(mutex_);
  
  // Todo(zero): how to call
  Expired();

  if (map_.find(key) != map_.end()) {
    return (*map_[key])->value;
  } else {
    return V{};
  }
}

template <typename K, typename V>
void ExpireLRUCache<K, V>::Expired() {
  auto time_now = std::chrono::system_clock::now();

  while( !list_.empty() ) {
    auto oldest = list_.back();
    auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(
                    time_now - oldest->timestamp);
    if (diff.count() > time_out_) {
      list_.pop_back();
      map_.erase(oldest->key);
      expired_callback_(oldest->key, oldest->value);
    } else {
      break;
    }
  }
}

template <typename K, typename V>
size_t ExpireLRUCache<K, V>::Size() const {
  std::lock_guard<std::mutex> lock(mutex_);
  return map_.size();
}
```

Answer 1

I don't see why the typenames NodePtr and NodeIter are public. Node itself is private, and none of the public interface uses these two types, so I think they should be private, too.

---

I'm not sure I like this interface:

V Get(K key);

This means we can only cache value types. Not only that, but there's no way to indicate "not in the cache"; I see the implementation default-constructs a return value in that case - further limiting the types that can be used.

---

Expired() expects that the mutex is held, but is missing a comment stating that, so it took too long to confirm that it's used correctly.

---

What's going on here?

NodePtr node = std::make_shared<Node>(Node{key, value, timestamp});

Why construct a Node and pass it to make_shared() to copy? It would be better to make_shared() directly:

NodePtr node = std::make_shared<Node>(key, value, timestamp);

Answer 2

Excellent points by Toby on the code side, I'll focus on data structure usage.

I'm not sold on the way you use the map and list to store the data. By having the map store an iterator into the list you add an indirection on the get operation which is arguably the operation you should optimize for in a cache, as the cache relies on the same objects being frequently accessed for it to be useful for its purpose.

I would swap these around so that the map stores the value and an iterator into the list and the list stores a key into the map (iirc unordered_map iterators are not stable if the map resizes). This way get() avoids the indirection and you can still grab the exact list element to move to the top when refreshing an object in the cache.

Another option is to avoid the list and use a priority queue (typically a heap) storing {timestamp, key} and the map stores key->{value, timestamp}. On insert you blind insert into the map with a new timestamp and you blindly insert into the priority queue the new timestamp and key. Then if you've exceeded the size limit or you want to expire items. Pop the top item of the priority queue and lookup the key in the map, compare the timestamps, if they match, evict from the map, if not then there's an element later on in the priority queue that references the map element and we can just discard this timestamp in the queue and pop the next.

I have a feeling that the latter will be faster because you'll need less branching in the insert operation meaning CPU branch predictor is going to a better job at keeping the execution pipeline from stalling, the get operation will also be faster as it doesn't need the extra indirection. Expiration might have to process more elements in the priority queue but that likely won't matter because of CPU cache prefetching will be very efficient on the heap as opposed to a list.