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
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.
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!
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.
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.
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.
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.
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.
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
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.
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.
Thanks for the implementation ,it really helps alot. just have one small doubt ,when we are hitting the cache ,why are we moving that particular element to last, shouldn't it be moved to first after head node ?By doing so ,aren't we violating what algorithm says ?By this approach only we would be knowing that last element was recently accessed, but as a general perspective people would expect recently used one in front no? Please correct me if I am wrong here
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?
@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.
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.
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 :)
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.
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?
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.
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.
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.
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!
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?
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);
@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.
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
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?
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
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.
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"
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?
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.
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.
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
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.
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!
one minor improvement I think while eviction you are only detaching the first node but also we need to remove from the hashmap
exactly
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
Please do low level design every week !
Can't promise, but will try to make more content on LLD.
This is one of the best LLD videos I have seen, thank you so much!
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.
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.
You are amazing at what you do. Your LLD tutorials are extremely helpful. You earned yourself a subscriber today.
Thanks :)
Such a detailed video with great explanation. Thank you so much Udit!
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.
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.
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.
just loved it...❤🔥
Thank you
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
Best content on internet for LLD. Kudos !!! @UditAgarwal
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.
pretty simple for cache simply use concurrent hasmap and add synchronized keyword. Singleton can be handled using guice/dagger for di
Best tutorial I have seen on coding and programming (y)
Thank you :)
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.
Awesome ! Thanks for creating such an insightful video. This channel is highly under-rated. Superb. Thanks a ton.
Thanks Yash
Thanks for the implementation ,it really helps alot. just have one small doubt ,when we are hitting the cache ,why are we moving that particular element to last, shouldn't it be moved to first after head node ?By doing so ,aren't we violating what algorithm says ?By this approach only we would be knowing that last element was recently accessed, but as a general perspective people would expect recently used one in front no? Please correct me if I am wrong here
Thanks for the great content. Please make more LLD videos.
Thanks Venny :)
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?
That's simply brilliant design.
Really helpful Explanation.
I am wondering if you can make videos over custom thread pools.
clear explanation and well design
thanks for sharing !!
Awesome Content Udit !! Just a suggestion, you could also mention about Thread Safety as well :)
Thanks Amrith :)
@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.
Perfect explanation! Although I was just thinking in the eviction policy how we can use eviction based on expiry(TTL).
Great videos and code. Better you include uml diagrams as well for this designs
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.
As always, one of the best video, thank you so much for this series.
Glad you enjoy it!
Kindly handle the multithreading issues as well so that the solution will become complete.
Thank you, You explained very well. Code repo is helpful.
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 :)
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.
Great explanation , keep up the good work.
Thanks Udit for the wonderful explanation.
Most welcome!
Nice Explanation Udit
Thank you 🙂
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?
Will add it to my list.
Excellent explanation.
Glad it was helpful!
Mast 👌
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.
You are best! Hats off!
Nicely explained 👍
Thanks Apoorv :)
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.
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.
agree
Why key is not removed from mapper as well in evictKey() ?
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!
I think there should be instance of Storage in Eviction class also can we give size of the cache?
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?
But I think he is not storing value in the Eviction policy, He is maintaining the key only in the eviction policy.
Thanks. Simply it's Just SOLID :)
Thanks :)
Nicely explained!!
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);
Yes, its a bug 😃 , looks like many people r blindly watching. Good video though!
@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.
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
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?
Very nice explanation. Thank you :)
Glad it was helpful!
you have not put condition for storage full (size of cache) anywhere
Awesome. Loved it.
Though I feel that this explanation is good but it cannot be replicated in a real LLD interview because of the time constraints
Why doubly linked List is implemented where LinkedList from Java Collections API can be used.
deque can also be used in place of doublylinkedList ?
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
Can we use this exact same in our machine coding round also ?
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 ?
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.
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"
you are writing biz logic in catch block, is that correct way?
what is the space complexity ?
Thank you:)
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?
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.
What are the files that have to be imported prior to solving this lld question? Or we can directly start writing the classes
why we are not using springboot with java here?
You want to use springboot for what purpose here?
sir what is the use of cache factory directory in code sir.
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.
Ok sir.Thank you for clearing my doubt sir
Can you make LLD for tick tac toe game please?