System Design: LRU Cache

on

Problem Statement

A cache is a in-memory hardware which is designed for fast access. All cache has memory limit which requires cache eviction policy. Basically whenever the memory of cache is full, we use policy to delete an item to make space for the new item.

There are many cache eviction policies:
  • First In First Out
  • Most/Least Recently Used
  • Most/Least Frequently Used
  • Random Replacement
Today we're going to discuss about LRU.
 
LRU is a cache eviction policy in which we remove the Least Recently Used item. Here Least Recently Used means the item that was accessed least recently.

Lets take an example of a LRU cache which holds 5 items and allows following operations:
  • Insert(item)
  • Get(item)
  • Delete(item)

Insert(item)

Inserts an element. As per LRU this is the most recently used item.
If the cache is full then the Least Recently Used item is deleted to make space for the new item.



Get(item)

Reterieves an item. 
As per LRU the item retreived becomes the most recently used item. This can be seen in the following:

Delete(item)

Deletes an item.




LRU cache should support the 3 operations in constant(O(1)) time. Let's look at how to do that:

How to LRU ?

Thinking about insert(item)

Looking at the insert we can see that the behavior is similar to a Queue.

A Queue allows inserting elements(enqueue) at the front and removing elements(deque) from the rear. enqueue/dequeue can be performed in O(1) time.

On insertion item is added to the rear(most recently used). If the memory is full one item is dequeued from the front(least recently used) to make space for the new item.


Queue solves insert(item) in O(1). Next we'll see get(item).

What about get(item) ?

Queue solves inserting elements, however it doesn't solve get(item) in O(1). Getting an element in a queue requires to scan the whole queue which will take O(N) time. Not what was intended.

So how to perform get(item) in O(1) ?

The answer is Hashing. Hashing can be used to get the item from the queue in O(1).


Ok, now retrieving an item is O(1). But is get(item) O(1) ? No. 
Remember in LRU when we get an item then we've to make it most recently used. This would mean to move it to the rear of the queue.

Right now queue is represented as an array. Shifting the accessed item will require O(N) time to shift the elements as shown below: 


How can fix that ? What if we implement the queue as a Doubly Linked List.

Doubly Linked List requires O(1) to shift any item to the rear. This is because we only need to change the pointers of the item being accessed. Here's how it's done:



And now we've O(1) get(item) and insert(item). The only operation remaining now is delete(item).
 
How about del(item) ?

Well, just like shifting items took O(1) time, delete operation also takes O(1) time. So we don't need to do anything extra.

Finally our LRU cache looks like:



This ensures LRU cache can perform get, delete and insert in O(1) time.

Comments

Post a Comment