If you're aware of how caching works and LRU and came here curious about the design of how distributed caches work, start at 23:42 . And very well put content, as always :)

You are a Hero, man! These are all the topics that we actually need. And sadly find no decent tutorial videos online! Thanks.

Given the time you were on the spot, my expectation was higher! I was more expecting HA & DR as well..! As usual, you are awesome.

Thanks for the video. I have a question. For ensuring availability, how about having a load balance which decides which server to hit. It would be more convenient design because only write operation need to be synced to both servers, whereas read operation can happen via any server. This would also ensure minimum latency for requests. Expecting your response

Thanks for this! Great content across your channel.. I feel stronger on system design :)

When you delete the head of the LRU linked list to make space in the cache, wouldn't you also need to invalidate its address stored in the hash table.

The best thing i like in this course is your style of wearing the cap in presentation.

Thanks for the video tutorials, thats first :), but I still hv some questions/comments, may b i am wrong, but let me tell u that..plz correct me if i m wrong...1. Not clear - how ur design got impacted with the estimation that u made at first, how ur design could get changed in case of 5 request/sec tps 2. How a value in hastable results into constant time lookup in linked list 3. Only apart from the last part, all other areas are also applicable for monolithic system., so it seems like that distributed philosophy is needed to be adderessed more

Thanks for the explanation, helped a lot!

Thank you so much for giving a lot around thought process and guiding the though process while designing complete system around any concept/problem. Thank you. Your in detailed content be the saviour for me in lead interview. Thank you.

Nice explanation. Thanks for the awesome videos. :)

It misses very important part: how does LRU eviction work ? In your design we add to cache as many items as we want leading to out of memory. I think you shall have mentioned that LRUs are limited either by the number of elements or their total size. If adding a new element would exceed limit then we need to evict one element(*) and we pick this element from the front of linked list and based on it's key we remove entry from hash table and delete node in linked list. * - if w limit LRU by memory size we might keep removing elements till memory goes back below threshold.

Again Very nice Video.. thanks sir :)... waiting more videos like this....

thanks bro!! it was an awesome video, i was really searching for an good caching video!!, it was explanatory!!

who else noticed 'cashing' in the beginning whiteboard ? Great content bro

Regarding log reconstruction, I suppose log data will be written to disk only after sufficient data is accumulated or a certain period has passed to reduce the disk access latency. If that is the case then how do you make sure data is not lost during that period?

Thanks a lot +Narendra. This is an invaluable video.

Really good video .. How are typically range queries handled? Firstly they condition may vary and also the range may vary? Most probably the same condition or range may never be used for a while? Do normally range queries get cached?

Brother your videos are fantastic. I just have a suggestion to use a better microphone for more clear recording. Thanks for this video.

How switching to master slave pattern solves the syncing issue between the replicas? If we are only writing to master, how does the slave get updated? By snapshot? That will still havé inconsistency right?

29:17 snapshot + log replay. Normally restore from recent snapshot first, then replay the remaining log. All previous logs before the recent snapshot timestamp can be reclaimed.

Very nicely explained. Could you come up with a video on 'Designing Distributed Scheduler' ?

Thank you for the AWESOME tutorial

I really didnt see any distributed cache system in most of the video... the title should be changed to working of cache.

One question Naren, on design, as we have event loop in place, suppose we have two requests put and get, so get will have to wait until put request completed and than event loop will read this. Doesn't this event loop be a multithreaded ?

Hi Narendra - great videos indeed, pls keep them coming! By the way how to do handle concurrency (writes) issues?

Great, can you make a video on "Design a Amazon locker system" and "Chicken nugget problem". I understand it takes a lot of work to make a video, and i appreciate your work a lot. It would be helpful if you can make a design interview video on locker system soon.

Liked your content. Partly the content is inspired (I don't mean copy paste here) by Cassandra architecture. Or in other words, we can always draw parallel (conceptually) with these distributed architecture frameworks. Thanks for raising my awareness.

I was asked a system design question. LinkedIn wants to Integrate with Dropbox. LinkedIn does not do business about document storage. However LinkedIn had 400 webservers and after integration with Dropbox, they do not want to scale up. Is it possible to make such integration without adding more servers?

hi. Can you make some video on how to handle heavy traffic ,loadbalancing ,zookeeper. how all these factors helps to increase response time

Great explanation

ARC is probably the best cache eviction algorithm as it takes care of both recency and number of hits. Its generally not seen in open source as IBM holds a patent for the algo.

RAM is blocking part, in event loop design RAM would still be blocking to the threads from the pool, ie. only one tread can access it. So how is it better from other designs? Is cache is shradded and duplicates are maintained?

Wow!! One video and you cleared thousands of doubts !!

Personally I don't think the hash table and linked list approach used here is good for an LRU caching data structure. Especially since with caching, you want fast access. The linked list approach described with the index positions requires O(n) access to loop through the linked list. You can use a hash table and linked list to have O(1) access by having the hash table keys mapped to each linked list node (instead of a key mapped to a chain of nodes). So if you have the table keys [1, 2, 3, 4, 5] and the linked list A B C D E, you could have the mapping [1: B, 2: A, 3: C, 4: E, 5: D]. The most recently accessed object is moved to the top of the linked list which is very simple to do for a double linked list (O(1) time). The key reference remains the same - only the node positions change. The point is as new data is added to the cache, the last node is deallocated if the limit is reached. Reading is O(1), moving to top is O(1), and deallocating is O(1).

Could you use a bitmap instead of a link list to determine the LRU faster?

Your channel is very helpful. Is it possible to make video on Traffic Light System Design because I have found this questions in many Big Tech Companies Interview. Appreciated for this video on Distributed caching and expecting more from you. You are almost like celebrity for us.

Good one. Do we need to talk about the updates to distributed hash map ? like locking the buckets etc ?

Just to clarify So, the two architectures used in high availability section is a) active-active cluster and b) active passive cluster?

Thanks for the video. This is very helpful for those like us who are starting with system design. Would you also mind sharing any resources like blogs/books etc.

Dude, that is cool!

Very nice! Thank you!

Great Info sir 👏

Very good video but certain details missed like when the node in the d list is removed what are the changes in hash map value changes? I know it's very difficult to pack everything. Never mind it's a great learning experience

One question - in lru when you delete node from end of linked list, how it's reference is removed from hashtable

Awesome it will be great help if you can talk more about LFU thanks in Advance :)

awesome explanation.

@narendra . Is it possible to optimize the collison case , currently it is o(n) if there are n values for the same key. Also how do you handle the case where mulitple threads are modifying the same key ?

When implementing LRU cache, What if there is collision in insertion? So if another (new) key also has hash value 3 and how do we insert it into double linked list?

Do we cache images and how we do that and doesn't that increases size of database?

Very nice video and very good content. Thanks a lot 😊

Does the write around pattern deletes the entry in the cache before updating db? otherwise the cache read would return inconsistent data. 4:14

how eviction will works in case of distributed system ?

Thanks for vid, one thing that seemed off, you said getting from the cache is a constant cost, O(1) but wouldn't it be based on the size of the linked list n so it would be O(n) linear search or at O(n/2) if we traverse from either end? Again top video with so much details!

This is a great video thanks a lot. Two questions. 1. what's the pros and cons for two approaches for fault tolerant repectively - regular internal snapshot and log reconstruction 2. can you post a link or a video for master and slave and how it works for availability? I'm not sure how the slave can sync up the data with master without syncing up

Nice Video..Thank you

really appreciated

How is key collision handled in your 2 nd scenario when double link list is maintained?

How do you handle Cache collision in LRU eviction mechanism, since you are using single entry in bucket, pointing to doubly-linked list?

Searching element in linked list by index has O(n) time complexity since we need iterate from 0 to index value, so we lose hash table O(1) time, right? In this case, why we need hash table at all, if we need to search through the linked list every time we access the value?

Is linked list used for distributed system as well, wouldn't that be too slow if used in multi-threaded environment?

Very Good. Thank You.

Hey, you are doing a great job. Thanks for teaching us such important things. I have a question. 1. If we are replicating server using master-slave architecture for availability. Isn't that suffiecient for making it fault tolerant? Why do we need logging events or capturing snapshots events in such case?

For log reconstruction, only write operation is needed, so we can omit read operations. As for the fault tolerance, since it's only cache, I think we can just start up a new clean server instead of doing the replication.

For the LRU policy, how are reads still going to be O(1) if the values are stored in list? When you re-access key 2 and placed the node at the end of the list you are not updating the indexes in the hash table. How does the cache know which index in the list contains my key (2) when its re-accessed without looking sequentially in the list?

In LRU in hashing bucket what will happen if the collision happens which one linked list address will it keep

In the Write Around pattern, how does the Read operation know that the latest data in the cache could be invalid? The writes always go around the cache, so imagine the following situation. Write to address A1, read from A1, and it causes miss and cache update, then write again to the address A1. Now if I read again from address 1, how would the cache know that it has to re-read the data even though some data is already there?

thank you so much!

Good stuff, thank you. One more thing we can do to improve resiliency when downstream services are unavailable is to use two TTLs (Time to live) : a SOFT TTL and a HARD TTL.

when we have replicas for high availability then why do we need to worry about fault tolerance?If once fails, other will take up and failing both at same time will have less probability and if that happens in worst case,we can rebuild from database?

Just one point, I am not quite clear here. You mentioned like while finding a node and delete it in constant time from Doubly linked list in LRU. Deleting and adding it at the end is fine but to get the node in doubly linked list will in O(n) time. can you please elaborate little more on that please?

Hey, can someone help me to understand when someone would create their own cache when we already have the systems like redis and memcached ?

nice to see LP on your t-shirt.

"Cashing Best Practices" @ 2min. Best section title ever.

if we have linkedlist for each bucket , then why space issues will come , as linkedlist can extend in size

How does write around cache result in a cache miss? Assume data is both in cache and DB. If you update that data and write directly to DB without going through the cache, then the cache would have stale data, and would respond with that stale data. How would a cache miss happen?

Thanks a lot for a well-explained video. Concepts look simple after watching them. Just one question. Why is it a requirement to have a fault tolerant cache? Data is anyway persisted in DB, hence if the server containing cache restarts, cache will anyway be built as the requests come in. Am I missing something here?

Narendra, I really found all your videos extremely helpful. If there is way to make one time donations please let me know!

It lacks many things present in distrubuted cache for example how Redis cluster shards and routes data (only a fraction of it was discussed), how redis client makes a connection to the redis cluster, etc. It focused more on storage on single node than a distrubuted cache.

buckets should be indexed 0-9 instead of 1-10 for hash % 10 to land in buckets Also - at one point caching is spelled 'cashing' and patterns is spelled 'patters'

Thank you bro! lol! we love u!

How do make sure requests are served in the same order they are requested, as 2 different requests might be updating the same key. Queue could help but since there is a thread pool behind it, you can not guarantee ordering. Also how would you avoid locking issues if 2 threads are updating the same key simultaneously?

In ur implementation of lru..u missed to tell us wht wud happen in case of hash collision... How wud it impact the linked list

Nice a nice video!!!! thanks

Very informative videos. I have confusion and need more visibility. If we talk about the Cache write-through/write-back approach, our cache would be 1st level of storage and the application will write/read data from the cache. My confusion is that my application will fire the JDBC SQL query to fetch data and data will be responded back through the cache. How my cache having the capability to understand JDBC query ... Even if we consider the default cache implementation, data 1st write to Db, and while read request, the 1st hibernate layer will search whether the data is available with cache, if yes that respond back through cache data. In this scenario also no call will send to DB and respond back using cache data. how my cache having JDBC SQL understanding.

Thank you.

I have doubt regarding caching Consider I have "cache aside pattern" and "in memory cache" in application server is used. I'm looking for Invalidation logic when there is an update. This was the context. I read for critical data like password/financial information we use Write Back policy to ensure consistency. In write through one instance's in memory cache entry gets updated and others can remain stale. So, there is inconsistency in write through My question is same can happen in Write Back, one instance's in memory cache entry gets deleted(invalidated) and we update DB..other instances in memory cache still have that entry. So there is inconsistency in write Back as well? Why do we prefer write back for critical data because same issue is there in write back. If answer is invalidate all instances' in memory cache entry then same can be done for Write through. Which makes me ask question 2. My another question is : We can update all instances' in memory cache entry and then update DB. In this way consistency is maintained so why not we use Write through for critical data like password financial information?

Ccould you tell me some books for system design

good job

Why not a min heap w/ update ability on Timestamp of last access? Linked List is still linear to find the actual element.

I am confused that why some terms are created for the same meanning, why we use snapshot rather than replication or replica?

i guess in write back there is no service for data sync , whenever data is removed from the cache , then it is copied to DB , Correct me if i am wrong

WIth LRU linkedlist, how can we handle collision. Will it be Linkedlist of linkedlist.

is distributed cache attached to any server .. U said 1 sever is down then we will have cache miss .. If cache was distributed then we should not lose data from cache no ???

LINKIN PARK T-shirt??? I love this video already!

I think most of the talk was on cache rather than distributed cache. May be some parts of sharding/quorum aspects might also need to be included here.

When you delete the linked list the address are still present in the hash table. When you access the address you will get garbage value. How to overcome this?

Question : How about using queue instead of using linked list? to get the LRU nodes?

Hi Sir, could you make system design tutorial w.r.t of credit or debit card systems and other payment systems. will be helpful. thq

I was looking forward to the part where the data to be cached is so large, that it can't fit in 1 host. And we can scale that horizontally.