ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT
  • 450 DSA Cracker
  • 5G NR
  • O-RAN

System Design Topic 6: LRU Cache

prodevelopertutorial February 15, 2019

In this topic, we shall know about LRU cache and why it is important in System Design.

LRU is used for cache eviction. Cache eviction is a process where stored cache will be released when it reaches a certain limit. There are many algorithms used for cache eviction like LRU – Least Recently Used, FIFO – First In First Out, LIFO – Last In First Out, TLRU – Time Aware Least Recent Used. Among those LRU is the more used one.

During cache eviction, which item to be removed is very important. You cannot remove the most recently used item, you cannot remove the most used item that is used frequently.

LRU stands for Least Recently Used. This policy states that if your cache limit is reached while removing the cache removes the least used item.

How to implement it?

LRU is implemented by Doubly Linked List (DLL) and Hashmap.

system design tutorial

So in our example, we have 6 DLL nodes and 6 values in a HashMap. DLL is used to store the cache value. Whenever there is a new cache it will be stored at the front, by this way the least used will be at the back.

While inserting a new value, we shall first check the DLL and if there is a value matching to the new value, then we move that node in the beginning. Else the new value will be inserted in the beginning.

But why do we need HashMap?

For searching the value in DLL it will take O(n) time. Hence to reduce the time complexity we use HashMap. Hence by using HashMap, we can search in constant time O(1).

So when the cache is full, we remove the last node of DLL and move the new item at the start of the linked list.

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Follow this blog to learn more about C, C++, Linux, Competitive Programming concepts, Data Structures.

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2022 ProDeveloperTutorial.com