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 :)
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
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).
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.
but how does snapshotting and log replaying work if node is down for a long while and a new master has completely new snapshot and other log (log is cleared after snapshotting). Is the snapshot passed to the slave which just restarted or how does this happen. Otherwise, even though the node replays the log it still has stale data comparing to its peers
@@DenisG631 For sure, slave nodes or active-active nodes will have the sync-up periodically, if the server goes down, the next-chozen server will start the latest snapshot itself have(it may be earlier than the down server's snapshot), and replay all the logs since this new server's snapshot.
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.
Yes. we will need to remove it from hash table as well. For this we already have the value that needs to be removed (on that node). We can pass that value through hash function and remove that value from the hash table.
@@castrothomas7127 How will you determine priority on the request? It will have the same priority so they will be used in the order they were received and basically will nothing more than just big array which we are trying to avoid. To determine priority you will have to have additional service running through the whole queue constantly or maybe adding additional data structures to store some statistics and so on...
lack of distributed part. Lots of challenging problems are not discussed. how to partition data ? how to use consistent hashing, how to rebalancing data? replication, cluster management, hot keys issue log compaction etc.
In-memory snapshotting leads to bad performance .. so how about designing a background thread to fanout in-memory state on disk. And then generate snapshot of disk state.
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.
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?
You accept writes at Master nodes, and let the replication log propogate to the secondary nodes. That is the basic Multi Leader replication. But but but, There seems to be multiple masters in the last explanation, in such a case even masters would need to sync up with themselves. If that sync is via network (which it ofc is), what is the point of using it in a caching system!! Better invalidate and then make DB queries.
In my opinion this design is not entirely scalable and does not addresses the scenario about how data will be distributed across clusters deeply. Consistent Hashing will help in that scenario and it will also help in fault tolerance. You will not loop an event queue in that scenario. Also event queue does not guarantee high availability and time of get/put will be more than O(1).
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.
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.
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.
@@jasonparraga3391 : The distributed cache has been already discussed in the other video of consistent hashing which he mentioned during this video. The link is also given!
I guess typical ideas apply. Master/Slave replication. Master for reads+writes/Slaves for reads only. Typical Leader detection. Nothing particular to distributed cache since can be applied to almost any distributed system
The distributed cache design is so close to a distributed database design, I could not tell much difference there. For example, you need to increase the scalability - add shards; to increase availability - add replica; to avoid data loss during machine crash - write a log into disk. Even the modern databases (e.g. SSTable) store the fresh data inside of memory to improve the latency before saving to persistence storage. I would say, the boundary between a cache and database is really vague now (for example, Redis claims itself a database too).
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?
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!
the list is never accesed linearly in this case because it's only used for "sorting". getting is still O(1) because the fields in the hash table are pointing to the nodes and that's how we access them
@@vmod3985 I got that we have the association between the hash table and the linked list, but I still having problem to understanding why he said O(1). My concern is because in my mind we need to go through node by node in the linked list to find the index.
@@ythalorossy The HashTable keeps the node's address or the node itself as value against the given key (thus O(1)). The linkedList is there to maintain the Least Recently Used node at the end of it.
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.
If you are in hurry, please note you can play this at the speed of 1.75 & still can understand everything he is explaining. Say thanks to me later if this comment is useful.
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'
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.
Imagine cache nodes being rebooted in production, and having no data. All reads to go database putting a lot of pressure on systems. High chances of increased error rate s till the time cache gets populated
Nice. In case cache system is down, we any how have replica as we put multiple servers for availability, Why do we log file? If all master slave crashes with very low probability, then log file can also have probability to get lost,now if we replicate log file also,we are making it complex, and given the scale, log file will be too huge. I think if we lost both master slave in worst, let it auto build from and get stable, let me know what you guys think.
Honestly, I kinda like most of your videos, but this one is really bad, please make a new video on Distributed cache, like Part-2 or something. I was expecting how REDIS work, how there communication between multiple cache servers, how would it sync with DB, will cache be eventually consistent or have strong consistency. Would the cache be single point of failure if multiple servers have to access it, if that is the case how DB and cache are in sync, So many questions, nothing was answered.
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 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 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?
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?
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?
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?
(25:20 Event Library) About event library schduling the tasks we can use tevent: tevent.samba.org/tevent_thread.html Code github.com/amitkumar50/Code-examples/blob/master/tevent/adding_events_to_queue.c
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?
In both mechanisms of making fault tolerant, you are mentioning both as async as well as in both we are just creating a log file, so whats the difference, its quite vague!!
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.
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
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?
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
Have a look at the OpenJDK implementation of LinkedHashMap. Every element has 3 pointers and is simultaneously in 2 different linked lists: one singly-linked list for the hash chain, and a doubly-linked list for LRU purposes.
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?
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?
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?
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 ???
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?
Excellent question! The way I am thinking, we could store the value as timestamp_value. If the new write is of an older timestamp, we could drop that write
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?
The Title says Redis System Design and distributed cache system. No mention of Redis nor any mention of distributed cache and the guy would use Queue to write and respond. I would give -F
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 ?
![ตีสิบเดย์ [FULL] | นางเอกหมอลำเงินล้าน "อุ๋งอิ๋ง เพชรบ้านแพง" & ไฮโซสาวสุดฮอต "ลิลลี่ เหงียน"](http://i.ytimg.com/vi/jPxQS_EgrJ4/mqdefault.jpg)
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 :)
I have implemented these cache on system in code levels. Checkout the leetcode LRU cache problem.
You are a Hero, man! These are all the topics that we actually need. And sadly find no decent tutorial videos online! Thanks.
Hey, 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.
who else noticed 'cashing' in the beginning whiteboard ?
Great content bro
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
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).
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.
but how does snapshotting and log replaying work if node is down for a long while and a new master has completely new snapshot and other log (log is cleared after snapshotting).
Is the snapshot passed to the slave which just restarted or how does this happen.
Otherwise, even though the node replays the log it still has stale data comparing to its peers
@@DenisG631 For sure, slave nodes or active-active nodes will have the sync-up periodically, if the server goes down, the next-chozen server will start the latest snapshot itself have(it may be earlier than the down server's snapshot), and replay all the logs since this new server's snapshot.
The best thing i like in this course is your style of wearing the cap in presentation.
bhai koi style nhi h...... baal nhi h iss bhai k .. mera bhi same scene h and m bhi cap lagata hu
I really didnt see any distributed cache system in most of the video... the title should be changed to working of cache.
You need to check the big picture and assemble the puzzles here. He has spit the design into several parts.
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.
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.
Yes. we will need to remove it from hash table as well.
For this we already have the value that needs to be removed (on that node). We can pass that value through hash function and remove that value from the hash table.
"Cashing Best Practices" @ 2min. Best section title ever.
Dude what if instead of doubly linked list you use priority queue... And the priority is given depending on how often it is used
@@castrothomas7127 How will you determine priority on the request? It will have the same priority so they will be used in the order they were received and basically will nothing more than just big array which we are trying to avoid. To determine priority you will have to have additional service running through the whole queue constantly or maybe adding additional data structures to store some statistics and so on...
Really a great explanation. 🎉
lack of distributed part. Lots of challenging problems are not discussed. how to partition data ? how to use consistent hashing, how to rebalancing data? replication, cluster management, hot keys issue log compaction etc.
In-memory snapshotting leads to bad performance .. so how about designing a background thread to fanout in-memory state on disk. And then generate snapshot of disk state.
@@blackcatcaptain2022 Should also be a combination of both log and snapshot.. log should only maintain state from last snapshot
@@y5it056 yes of course.
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.
Wow!! One video and you cleared thousands of doubts !!
LINKIN PARK T-shirt??? I love this video already!
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?
You accept writes at Master nodes, and let the replication log propogate to the secondary nodes. That is the basic Multi Leader replication. But but but, There seems to be multiple masters in the last explanation, in such a case even masters would need to sync up with themselves. If that sync is via network (which it ofc is), what is the point of using it in a caching system!! Better invalidate and then make DB queries.
In my opinion this design is not entirely scalable and does not addresses the scenario about how data will be distributed across clusters deeply. Consistent Hashing will help in that scenario and it will also help in fault tolerance. You will not loop an event queue in that scenario. Also event queue does not guarantee high availability and time of get/put will be more than O(1).
But an event queue would be needed because you do not want to lose your requests in case there is throttling.
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.
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.
Brother your videos are fantastic. I just have a suggestion to use a better microphone for more clear recording. Thanks for this video.
awesome explanation.
thanks bro!! it was an awesome video, i was really searching for an good caching video!!, it was explanatory!!
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.
Again Very nice Video.. thanks sir :)... waiting more videos like this....
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.
you shard cache? never heard of it
@@fenggeliu4241 yes we can, and such cache systems are called distributed cache systems.
Agree! Would appreciate more focus on the distributed aspect.
@@jasonparraga3391 : The distributed cache has been already discussed in the other video of consistent hashing which he mentioned during this video. The link is also given!
I guess typical ideas apply.
Master/Slave replication. Master for reads+writes/Slaves for reads only.
Typical Leader detection. Nothing particular to distributed cache since can be applied to almost any distributed system
The bucket range will be from 0-9 at 6:00, it will be never coming to 10 (x%10 range from 0-9)
The distributed cache design is so close to a distributed database design, I could not tell much difference there. For example, you need to increase the scalability - add shards; to increase availability - add replica; to avoid data loss during machine crash - write a log into disk. Even the modern databases (e.g. SSTable) store the fresh data inside of memory to improve the latency before saving to persistence storage. I would say, the boundary between a cache and database is really vague now (for example, Redis claims itself a database too).
Thank you for the AWESOME tutorial
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?
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!
the list is never accesed linearly in this case because it's only used for "sorting". getting is still O(1) because the fields in the hash table are pointing to the nodes and that's how we access them
@@vmod3985 I got that we have the association between the hash table and the linked list, but I still having problem to understanding why he said O(1). My concern is because in my mind we need to go through node by node in the linked list to find the index.
@@ythalorossy The HashTable keeps the node's address or the node itself as value against the given key (thus O(1)). The linkedList is there to maintain the Least Recently Used node at the end of it.
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.
Hey can we discuss amazon locker
Very nice video and very good content. Thanks a lot 😊
If you are in hurry, please note you can play this at the speed of 1.75 & still can understand everything he is explaining. Say thanks to me later if this comment is useful.
How is key collision handled in your 2 nd scenario when double link list is maintained?
I think LFU better choice than LRU
Thanks for video
In this scenario definitely. But it is harder to implement and to explain
Dude, that is cool!
nice to see LP on your t-shirt.
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'
Thanks for this! Great content across your channel.. I feel stronger on system design :)
In LRU in hashing bucket what will happen if the collision happens which one linked list address will it keep
Nice explanation. Thanks for the awesome videos. :)
Thanks a lot +Narendra. This is an invaluable video.
Just to clarify
So, the two architectures used in high availability section is a) active-active cluster and b) active passive cluster?
Nice Video..Thank you
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.
Imagine cache nodes being rebooted in production, and having no data. All reads to go database putting a lot of pressure on systems. High chances of increased error rate s till the time cache gets populated
Nice. In case cache system is down, we any how have replica as we put multiple servers for availability, Why do we log file? If all master slave crashes with very low probability, then log file can also have probability to get lost,now if we replicate log file also,we are making it complex, and given the scale, log file will be too huge. I think if we lost both master slave in worst, let it auto build from and get stable, let me know what you guys think.
Great Info sir 👏
Thanks for the explanation, helped a lot!
Great explanation
Your topics are great and your explanations also.
But it’s hard to hear!
Hey, can someone help me to understand when someone would create their own cache when we already have the systems like redis and memcached ?
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.
It is explained in the consistent hashing video.
Honestly, I kinda like most of your videos, but this one is really bad, please make a new video on Distributed cache, like Part-2 or something. I was expecting how REDIS work, how there communication between multiple cache servers, how would it sync with DB, will cache be eventually consistent or have strong consistency. Would the cache be single point of failure if multiple servers have to access it, if that is the case how DB and cache are in sync, So many questions, nothing was answered.
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.
Thanks @Bipin, this means a lot.
Now we have a new super-hero, who 'saved' Thor, Hulk, Flash, Spidy and all - to the (Avenger?) cache.. cheers!
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 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?
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?
Narendra, I really found all your videos extremely helpful. If there is way to make one time donations please let me know!
Very nicely explained. Could you come up with a video on 'Designing Distributed Scheduler' ?
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?
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?
Awesome it will be great help if you can talk more about LFU thanks in Advance :)
(25:20 Event Library) About event library schduling the tasks we can use tevent:
tevent.samba.org/tevent_thread.html
Code github.com/amitkumar50/Code-examples/blob/master/tevent/adding_events_to_queue.c
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?
due to TTL. key is valid only for a certain period of time
hi. Can you make some video on how to handle heavy traffic ,loadbalancing ,zookeeper. how all these factors helps to increase response time
Excuse me, but flash is not a turd!
Other than that - great explanation, bro :)
Hi Narendra - great videos indeed, pls keep them coming! By the way how to do handle concurrency (writes) issues?
In both mechanisms of making fault tolerant, you are mentioning both as async as well as in both we are just creating a log file, so whats the difference, its quite vague!!
good job
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.
here you go dzone.com/
highscalability.com/
medium.com/netflix-techblog
eng.uber.com/
martinfowler.com/
www.oreilly.com/feed/four-short-links
news.ycombinator.com/
ai.google/research/
hackernoon.com/
machinelearningmastery.com/
www.analyticsvidhya.com/
www.kaggle.com/
www.codingthearchitecture.com/
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
good demo, but title shall not called Redis design, Only 1 line is talked about Redis, which is "Regular Interval Snapshot". Nice session
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?
Time:20:51 Removal from doubly LL is not O(1) it same as singly LL. We need to search element, and we are only aware of Head & tail pointers.
Can be done in O(1) if hashmap stores pointer to dll node as value
Is linked list used for distributed system as well, wouldn't that be too slow if used in multi-threaded environment?
would have been better if you move LRU in a separate video. Not much content on distrubuted Redis Cache
good one
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
Thanks and I have already made a video on consistent hashing. Please take a look at description of the video.
Queue should be FIFO correct? Otherwise LRU would go for toss
How do you handle Cache collision in LRU eviction mechanism, since you are using single entry in bucket, pointing to doubly-linked list?
+1
Keeping a list of addresses in the hash table should still work.
Have a look at the OpenJDK implementation of LinkedHashMap. Every element has 3 pointers and is simultaneously in 2 different linked lists: one singly-linked list for the hash chain, and a doubly-linked list for LRU purposes.
Very Good. Thank You.
Kindly create a separate video for event driven architecture
Good one. Do we need to talk about the updates to distributed hash map ? like locking the buckets etc ?
Very nice! Thank you!
Thank you.
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?
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
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?
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 ???
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?
Excellent question!
The way I am thinking, we could store the value as timestamp_value. If the new write is of an older timestamp, we could drop that write
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?
By deleting it from the hash table, it's kinda obvious isn't it?
Do we cache images and how we do that and doesn't that increases size of database?
The Title says Redis System Design and distributed cache system. No mention of Redis nor any mention of distributed cache and the guy would use Queue to write and respond. I would give -F
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 ?
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
It says distributed cache? I did not find the distributed part neither how eviction will be handled in case of distributed cache serves???