System Design Interview: Cache| Low Level Design | Design Principles | LLD | Machine Coding | OOPs

Подписаться 22 тыс.

Просмотров 51 тыс.

50% 1

In this video, we are going to build a low level design for Cache system.
Cache that we will design will have to support following operations:
Put: This will allow user to put a value against a key in the cache.
Get: This will allow user to get the previously saved value using key.
Eviction: Cache should also support removal of some key in case cache is full, and we try to add new key value.
Thanks for watching. Hope you find this video helpful. Let me know your feedback in the comments.
Do subscribe to the channel!!
I have uploaded the full source code of the solution in my GitHub account. It can be found here: github.com/ano...
LLD System Design Playlist: • Low Level System Design
You can follow me on:
LinkedIn: / anomaly2104
Instagram: / anomaly2104
Facebook: / anomaly2104
Twitter: / anomaly2104
Blog: blog.uditagarwa...
#system #design #interviews #interview #coding #programming #faang #tech #technology #developer #coder #code #java#systemdesign #architecture #software #partitioning #sde #sdi #systemdesigninterview #software #development #program #lowleveldesign #lld #oops #designpatterns #designprinciples

Опубликовано:

5 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 103

@anomaly2104 8 месяцев назад

Become Zero to Hero in Multi-threading by Registering here: enginebogie.com/u/anomaly2104/offerings/PATH/e9522ac1-4e4c-4217-92ba-f691f34c321b Become Zero to Hero in LLD by Registering here: enginebogie.com/u/anomaly2104/offerings/PATH/e6cce7f1-6a56-4fe3-bb82-48e1876e4596 Connect with me at: enginebogie.com/u/anomaly2104

@aakash1763 3 года назад

one minor improvement I think while eviction you are only detaching the first node but also we need to remove from the hashmap

@darkstudio3170 2 года назад

exactly

@yatri6329 5 месяцев назад

Yes I think there should be a reference of Storage in Eviction class so while removing the node the key - value pair should also removed from HashMap

@sciphilo754 3 года назад

Hey Udit, what you're doing is absolutely amazing. Great example of a code following modularity and SOLID principles. You should have a lot more subscribers!

@AshwaniYadavIIT Год назад

This is one of the best LLD videos I've ever seen! The explanations are clear and concise, and the pacing is perfect. I especially appreciate the way you break down complex concepts into smaller, more manageable chunks. I'm definitely going to be using this video as a reference as I work on my own coding projects.

@Emmanuel-px9lk 4 года назад

Please do low level design every week !

@anomaly2104 4 года назад

Can't promise, but will try to make more content on LLD.

@Mohit_Gupta24 3 месяца назад

Hello Udit, Great Example to demonstrate LRU Implementation. However one observation, In HashMapBasedStorage, the put operation is first checking the storage Full and throwing exception when the size of hash map is equal to initial capacity. But this will also fail when the client is trying to update a value for existing key. In such case, as the key is already present in the Map, the cache should be able to replace the old value from new value directly, make it most recently used, rather than throwing an exception and evicting the key and then again adding the same key.

@anomaly2104 2 месяца назад

Hey Mohit My goal of this video was mainly to showcase design while not algorithm around it so thats why I did not focus on whether the code is logically correct. So definitely you are correct that there are some edge case missing in the logic which can definitely be fixed.

@DaGuyWithCommonSense 4 года назад

You are amazing at what you do. Your LLD tutorials are extremely helpful. You earned yourself a subscriber today.

@anomaly2104 4 года назад

Thanks :)

@indavarapuaneesh2871 2 года назад

One suggestion: If you want to have a cache system that supports parallel/concurrent reads then the Cache factory should create a singleton cache instance. This way it becomes a thread safe operation. And also currently the Storage class doesn't support concurrent reads. You could have used concurrent HashMap there. That would have sealed the deal there.

@dopeteddygaming7267 Год назад

1) for most prod code singleton behavior can be handled through di frameworks guice/dagger 2) Making singleton doesnt automatically make it thread safe 3) using concurrent hashmap doesnt solve concurrency issues it solves only visibility, you still would have synchronization issues.

@noelvarghese370 4 месяца назад

This is one of the best LLD videos I have seen, thank you so much!

@anishprasad7024 4 года назад

Please create a basic small app using spring boot as well where we can get the idea of creating models and using proper annotations(for saving data in DB can use H2) as well and better way to create rest apis. All I am requesting for writing spring boot application using database and using LLD concepts

@samanthjain1743 3 года назад

Udit, It could have been better if you had considered the multi-threaded scenario where multi-threaded have access to cache (few are inserting/modifying and few are removing). In general, multi-threaded considerations in low-level design/implementation adds additional value I think.

@dopeteddygaming7267 Год назад

pretty simple for cache simply use concurrent hasmap and add synchronized keyword. Singleton can be handled using guice/dagger for di

@shamlikiruba Год назад

Such a detailed video with great explanation. Thank you so much Udit!

@VY-zt3ph Год назад

It was a very smart design. I had previosly done leetocde question and I tried using that impl and got stuck badly. Your approach is very much simpler and cleaner.

@NohandleReqd Год назад

Great explanation, Just a small tip. You should always go Bottom up while explaining. So the Smallest classes in the beginning, and the large classes consuming objects of the smaller class later. this was the explainability is easier.

@Paradise-kv7fn 3 года назад

Wouldn't it better if instead of throwing and catching an exception when the storage is full(when configured by the capacity) and trying the put call again, we actually have an if check directly to call envitKey() if required.

@vedprakashyadav3598 4 года назад

Best tutorial I have seen on coding and programming (y)

@anomaly2104 4 года назад

Thank you :)

@sachin_getsgoin 3 года назад

There is design idea called "Principle of least astonishment". Using exception to execute regular flow is not considered as a good design. Put method should improved and exception block should not be used to execute regular flow. Also the storage class is not thread safe.

@prashantnagrurkar2784 2 года назад

agree

@parulchoudhary6129 11 месяцев назад

hey udit, thank you for the amazing explanation , i have come across this question during interview : in interview do we have to create each n every class and make the code run . what should be the best way to present LLD for any problem in interview as we are bounded by the time and want to make best out of it?

@TheSridharraj 3 года назад

Kindly handle the multithreading issues as well so that the solution will become complete.

@YashRaithatha1989 3 года назад

Awesome ! Thanks for creating such an insightful video. This channel is highly under-rated. Superb. Thanks a ton.

@anomaly2104 3 года назад

Thanks Yash

@pattigarivineethkumar3224 6 месяцев назад

just loved it...❤‍🔥

@anomaly2104 6 месяцев назад

Thank you

@ankitagrawal8355 4 года назад

As always, one of the best video, thank you so much for this series.

@anomaly2104 4 года назад

Glad you enjoy it!

@mohittheanand 3 года назад

The whole content was great and very detailed. But I am confused at one point. Shouldn't the eviction policy be using the Storage class otherwise it feels we are doing the same thing twice. Once adding the key to storage instance and then also adding it in evictionPolicy class. Thanks :)

@anonymousgod2006 3 года назад

Ya I think key will be added in both of them. Eviction Policy requires only key information and not data which might not be a big payload. For making design scalable and adaptable for different Storage and eviction policy, he made that design choice.

@paraschawla3757 3 года назад

Shouldn't evictKey() also need to remove evictKey from Map in EvictionPolicy as well? @Override public Key evictKey() { DoublyLinkedListNode first = dll.getFirstNode(); if(first == null) { return null; } dll.detachNode(first); return first.getElement(); } Correction something like -> this.map.remove(first);

@murali1790able 3 года назад

Yes, its a bug 😃 , looks like many people r blindly watching. Good video though!

@sachingangwar9889 3 года назад

@paras The purpose of evictkey is to just evict the key from main Cache, removing from the map is a part of Cache class, just after the successful eviction.

@sidforreal 2 года назад

there are actually two differnt map, one for storage and one for eviction policy. You just need to focus on the storage one The correct approach would be actually, we should take storage in constructor of eviction class

@AashutoshRathi 3 года назад

That's simply brilliant design.

@vipulpachauri5498 3 года назад

Best content on internet for LLD. Kudos !!! @UditAgarwal

@vennyroxz 4 года назад

Thanks for the great content. Please make more LLD videos.

@anomaly2104 4 года назад

Thanks Venny :)

@priyaranjansingh6814 3 года назад

Perfect explanation! Although I was just thinking in the eviction policy how we can use eviction based on expiry(TTL).

@AkashJadhavIT 4 года назад

Thank you for this tutorial sir :) . is there any LLD solution for Designing #Slack or #Microsoft_Teams, communication and collaboration platform. would it be possible for you too make tutorial on this?

@anomaly2104 4 года назад

Will add it to my list.

@sachinjindal4921 3 года назад

Really helpful Explanation. I am wondering if you can make videos over custom thread pools.

@rahuljainbit 3 года назад

@udit: video is extremely good. I answers all basic features of a cache. Can you share inputs on how to handle class in multi thread scenario? I think couple of sections in code are to be under lock. Please let me know your opinion.

@amrithm5666 4 года назад

Awesome Content Udit !! Just a suggestion, you could also mention about Thread Safety as well :)

@anomaly2104 4 года назад

Thanks Amrith :)

@sushmitagoswami7320 2 года назад

You are best! Hats off!

@nakulkumar4197 2 года назад

Two questions: 1. StorageFullException : You have just thrown them from method but havent mentioned anything about taking capacity/size of cache that needs to be taken as input and HashMapBasedStorage will check if capacity is reached then to throw exception. Is my understanding correct here? 2. If TimeBasedEviction is to be done i.e., with every key there is a time limit associated or default timeout is set. How one should implement that? At the time of accessing checking time is expired then we will be keeping unnecessary keys. Keeping a daemon running in background for reducing time, that will keeping on scanning millions of keys if cache is going to be huge.

@pranovkumar7787 4 года назад

Thanks for the content , i have few doubts. 1)How will the design change if we need to support multiple concurrent read and single write in the cache. I am confused here because the Eviction policy's DLL becomes a bottleneck, for allowing multiple concurrent reads , as with every need we to update the DLLs pointers as well. Please help me understand how this can be achieved. Thanks in advance.

@FWTteam 3 года назад

Thank you, You explained very well. Code repo is helpful.

@rashminpatel3716 2 года назад

clear explanation and well design thanks for sharing !!

@iamankitgarg 4 года назад

Thanks Udit for the wonderful explanation.

@anomaly2104 4 года назад

Most welcome!

@ManojVarma125 4 года назад

Thanks. Simply it's Just SOLID :)

@anomaly2104 4 года назад

Thanks :)

@ravijaiswal9153 3 года назад

Instead of creating a new class for DoublyLinkedList, can't we use the standard LinkedList in java with type as Object as it will also be generic, like "LinkedList dll"

@ismile47 2 года назад

Great videos and code. Better you include uml diagrams as well for this designs

@KolliMadhukar Месяц назад

Though I feel that this explanation is good but it cannot be replicated in a real LLD interview because of the time constraints

@prateekdiliphalwe2537 3 года назад

This is helpful , thanks! I have a question: In your final code in GitHub, when you do storage.put(key, value), at that point of time don't you need to create a DLL node for the same and insert it into the DLL based on the availability of the cache slots. If not available then delete the LRU node from DLL(key) and then add the new node? Usually in LLD questions, I am able to identify entities, come up with class interfaces but not able to visualize the code with main(). Like in above question, let's say if you want to create DLL node, how can you access theLRUEviction object's Data member inside the method. Please let me know If I am missing anything. Thanks!

@yatri6329 5 месяцев назад

I think there should be instance of Storage in Eviction class also can we give size of the cache?

@priyatamroy392 3 года назад

Why key is not removed from mapper as well in evictKey() ?

@medamsaisirisha847 5 месяцев назад

I have a doubt with regards to Storage , inside LRU Eviction Policy we are taking seperate HashMap and then we are using HashMapStorage class in the Cache wrapper class. Could you please explain why we didn't use the HashMapStorage object inside the EvitctionPolicy?

@PRoy-p5h Месяц назад

Why doubly linked List is implemented where LinkedList from Java Collections API can be used.

@bhawanimkd7334 2 года назад

Great explanation , keep up the good work.

@afzal048 2 года назад

you have not put condition for storage full (size of cache) anywhere

@amarlearning 4 года назад

Very nice explanation. Thank you :)

@anomaly2104 4 года назад

Glad it was helpful!

@utkarshgupta2909 2 года назад

Udit what about if we use CacheBuilder inplace of cacheFactory here, by keeping default implementations as LRU and HashMap and let the user decide if they want some thing else.? Finally user after selecting the strategy like LRU and DynamoStorage eg. will call build to get the cache which will save to dynamo and will be based on LRU eve=iction

@mahendragaur4641 3 года назад

Why are we using multiple storage ? One hashmap in storage class and another one in eviction policy. Isn't it redundant storage of same data ?

@anomaly2104 3 года назад

Hi Mahendra, The 2 storages are very different. One storage is for the actual data which is cached and second storage is for evictions. In evictions storage, we are not storing full data. Only keys with times are stored there.

@ankushgats 3 года назад

Hey Udit this is very well explained and designed solution. Thank you for your efforts. One problem i think we have is: we are duplicating data in storage and eviction policy class. Eviction is to avoid running out of memory but eviction functionality itself doubling our memory usage. What do you suggest?

@Aditya-yn5lk 2 года назад

But I think he is not storing value in the Eviction policy, He is maintaining the key only in the eviction policy.

@omi04 4 года назад

Excellent explanation.

@anomaly2104 4 года назад

Glad it was helpful!

@bikashdas5095 2 года назад

Awesome. Loved it.

@viinii36 2 года назад

One question is are we not creating two storages indirectly: One for storage and the other in the eviction policy we are again creating and storing in hashmap and ddl.

@nitinpandey7478 3 года назад

Nicely explained!!

@sharp_shooter21 4 года назад

Nice Explanation Udit

@anomaly2104 4 года назад

Thank you 🙂

@mohank7202 3 года назад

deque can also be used in place of doublylinkedList ?

@prashantnagrurkar2784 2 года назад

you are writing biz logic in catch block, is that correct way?

@ahtasham6373 2 года назад

I have a question. Do you derive/draw classes and object before writing the code? If so, then what tools do you use and which charts or diagrams do you make? Like class diagrams or sequence diagrams?

@apoorvchaturvedi2493 4 года назад

Nicely explained 👍

@anomaly2104 4 года назад

Thanks Apoorv :)

@whatisthisyogesh 3 года назад

Can we use this exact same in our machine coding round also ?

@sanathmugeraya6061 3 года назад

What are the files that have to be imported prior to solving this lld question? Or we can directly start writing the classes

@diboracle123 2 года назад

what is the space complexity ?

@soumavanag5025 3 года назад

Thank you:)

@kunalkadian Год назад

Mast 👌

@PavanLearns 6 месяцев назад

why we are not using springboot with java here?

@anomaly2104 6 месяцев назад

You want to use springboot for what purpose here?

@kunal4350 4 года назад

Can you make LLD for tick tac toe game please?

@abhireddy8164 4 года назад

sir what is the use of cache factory directory in code sir.

@anomaly2104 4 года назад

Cache factory is serving the purpose of providing the standard caches. Right now, it has only one method which gives a default cache. This default cache is actually the most popular cache using LRU. Purpose of factories in general is to give common things like here cache in itself is very configuration like it supports different storages and eviction policies but factory is providing few standard caches.

@abhireddy8164 4 года назад

Ok sir.Thank you for clearing my doubt sir