Redis system design | Distributed cache System design

hello everyone my name is Lorraine and indecision let's learn system design for distributed cache before we go to system design here is a short announcement a big shout out to warren Watts who implemented core using java for consistent hashing calmly sketch and bloom filter and he's are encoding hero you can also implement core for all my system design or any of the algorithm which i teach and then send the links to me and i'm going to update those links in the respective videos description thank you in competition caching is high-speed data storage system which saves the transient data so that the further request will not hit the main memory or will not compute the actual computation and all the data will be served from the cache system and also all the computations results will be reused using the cache the data in the caching system usually is stored in faster access hardware like RAM RAM provides you faster i/o operation so that you can retrieve the data which is save in the RAM faster so that the further queries will be much faster or reduced latency caching is used everywhere it is used in different layers of technology like operating system CDN or DNS for example and also it is being used in many applications like for example websites social networking websites say for example Amazon acceptable etc and also it cash is being heavily used in games to improve the performance or latency for the read and write of the media content so caching best practices before you cash something you need to understand the validity of the data when you know the validity of the data or when you understand how long I can save this particular data so that's when we get high literate that means that the cache the data was cached in the caste system would be so from the cache otherwise it will cause you to cache miss that means that the data was not found in cache which results in more query to the actual database or operating system so we need to properly set the TTL that is time to leave as I always say in all of my videos before designing any system please take a couple of minutes to think about all the features or estimation you want to if you don't know please talk to your interviewer so for caching system here is distribution say we want to save up to terabytes of data in the cache because we are trying to build a very big cache system say for example for amazon.com or even for google.com or Gmail calm so what is it UPS we are expecting anywhere from 50,000 to 1 million queries per second ok and also what is the latest we are expecting is up is almost about one millisecond latency to get or set our gate output ok and what is the eviction policy if you want to use we let's go for LRU and I am going to explain something new eviction policy also so the fifth one is the availability so we are expecting obviously a hundred percent availability because no one expects 50 percent or 80 percent already we want our four servers to be up and running all this and obviously I mentioned that be able to design distributed cache system that means that it is scalable kind of scalable we need to add more and more servers so that we can scale the system horizontally so now let's learn what are the different kind of cache access patterns are there in any application there will be a cache and there will be memory in this case we are considering it as dB so the first one is right through system in this case right through as the name mentions it is true that means that whenever there is a write request constant it actually goes through the cache system and then this write actually will also happen in the DB and the acknowledgement of write successful will be sent back only when the data is completely saved in cash and also in the DB only that's when the acknowledgement will be sent back that the light is successful and the second pattern is right around in this case as the name says this is a right around system in which the request the write request will be going around the cache that means that the right right of us will go to the main memory or the DB in this case the BB will confirm that the right is complete in this case the acknowledgement will be sent back and the data will not be sent to the cache the data will be sent to the cache or retrieved from the cache only when there is a mid read request and the cache miss happens for the first time and then the cache will get that data back and then sales in the cache and then it responds and the third one is right back in this case so in the write-back cache system what happens is first the write update will go to the cache and then the data will be saved first in the cache then the acknowledgement will be sent back immediately and there will be one more service which will be syncing the rights which happen to the cache into the DB a synchronously that means that the service will take care of syncing the data or updating the data which is there in the cache to the DB so this is called as a write back cache access pattern when we say we have to design a caching system which has less latency or it should perform get or put operation faster what is the data structure we can use to implement the cache the kolodziejczak of the cache so the answer is that is hash table so as you know the hash table is much simpler it works in a very beautiful fashion so all we need is we need to have a hashing function we need a key and the value and also we need a case in the memory and each buckets should be numbered like this say for example we have 10 buckets over here so the size of this pocket is 10 ok we have the total size is 10 consider I want to save a value with the key taught to value say for example value something and the key is stopped what do we need to do is we had to pass this car to a hash function and we had to take that output suppose I got the output as 53 what we need to do is we are to divide the 53 with the total size of the bucket and then we have to take the reminder so that's the remainder is 3 in this case because 53% of 10 we get 3 so we had to go to the third bucket in the hash table and save this key and the value both here say will be saving Todd and gives value over here okay and then similarly if I want to say Hulk and its value we have to pass this help to the hash function we get a hash value called 71 and then we have to divide the certainty one by ten and you have to take the reminder okay and then that is one where did I go to that particular bucket and save the key and its respective value that is Hulk in its value and suppose take some case like we want to say hand and man in this case if we pass ant-man to the hash function we get 93 when I divide this we get the remainder three if you go to the location there is a collision because we have already saved our value in this particular bucket what do we do we can do there are different strategies to solve that one simple strategy is instead of saving that value directly beep in the linked list over here okay in here the value will be thought as a key and its value and here the value will be ant-man and its value so we build the chain like that so no matter how many collisions happen because of hashing property we will keep on saving those key and value respectively when the get operation happens similarly if you have to I will take the key and then get a hashing divided by 10 take the remainder come to that package and then check in the linked list for that particular key and value exactly for that key and get the value and then return back that's how fast it works and I have already explained how the distributed hashing works and how hashing works in another video which I have already posted in YouTube and the link is available over here and also this link I will post in the description of this video in that video I have already explained how hashing works briefly and also I have explained how we can distribute the hash in horizontal manner or how we can scale the hash using consistent hashing so we had to use consistent hashing to make this cash system distributed so that is the reason I'm not going to explain how to distribute the cash or how consistent hashing works or how hashing works descriptively please refer to that video to understand this so now I will directly general two cash addiction policies how do we get cash so when do we need to having the cash election means basically deletion or removing the key and value entry from the cache memory so what do we need to do that because cash is a lot expensive because RAM is expensive we can't keep on scaling that way and also we know that not all the cleared values pays which are saved in the cache will be always used so we know that or we have to somehow figure out what is the key value pair which is Bill not used recently or which is never used and that is simply sitting in the memory idle so we have to remove them so that we can make space for the new key value pair which the application is writing to the cache and that is called as cash election policy and we have to build an algorithm around it to make those unused or never used key value pairs which is saved in the cache so the best strategy is LRU LRU stands for least recent use there are different cash erection policies are there something like mru or our of that and the most algorithm which makes sense is LRU because it says that at least recently used that means that that particular key value pair or the cache entry was least recently used so if it is not used then it doesn't make sense to keep that in memory occupying a particular pocket in the hash table so Vanita Epic Touch so that other cache entry can be saved on that bucket bucket so the interesting problem is how do we implement least recently used cached say for example now we have two entries in a hash table so let's add one more entry say for example flash for flash suppose we got 57 or 56 ok consider we got 56 so when we divided by 10 the remainder we got 6 so we have to save flash at system bucket okay now all good now consider we are full of memory because we have saved even more given value pair so now there is one more entry coming in say for example in Spidey or maybe an already here so now we are trying to save this key and some value associated with it so consider this is our phone ok now we want to save this guy in somewhere so there is no space what we need to do so we need to do cache eviction that is we have to LRU so we have to somehow somehow figure out what is the least recently used key value of the bucket so that we can delete that bucket ok so there is a space available something like that so we keep on deleting the least recently used buckets so we have enough space to save this guy so if we don't have space anyway there is a collision occurs because linear probing or what having linked list we need memory right so we need to free up the memory in the hash table so we need to do LRU so how do we do that so let's take a simple approach consider we have a say something unless we maintain a list in which we keep on saving the keys which are recently used say first we accessed car so I say then maybe our access flash so I say - say consider we have saved this guy somewhere here so I access so that is PI e and then again access to car ok so this way we can keep on saving it the list this particular list keep on growing it will be growing like like crazy because we are accessing a lot of key in value pair because as I mentioned we are expecting about 50 K - 1 million query in the whole system for this particular server we might be expecting about thousands of requests right so this list will be growing in the weight of thousand keys added to this so in this case if I want to figure out what is the least recently used it is a lot difficult because I can't do anything with this ok even if I can do something say if I'm associated some date and time date a month and year and say for example time and minutes along with the keys even though what I want to do is even I have to keep on iterating with the list so it could easily take order of n so and since the list is already growing and we have a lot for injuries in the list it will take order n times and and that's not efficient we need to have some sort of mechanism in which we can easily figure out in order 1 that what is the least recently used cash so that we can edit that particular entry so how do we solve this problem of figuring out what he was accessed what he was not accessed at all or what he was least accessed so to do that let's take something which we know that is linked list a bi-directional linked list so to implement LRU so we need two data structures one is hash table and the other one is separate linked list which is bi-directional so what we do is say we haven't saved any of this let's come in on order first one and second one and third one okay now what a save thought to this particular hash table so thomas hash we got 53 and we know that bucket 12 in each set so I really what we do is we will say the value key and value over here right that is tar and its value so now instead of doing that over here let's give this a deal so before say something over here in our by-election latest will have to create a first node okay and here we will save the key and the value that is and its value and the address to this node will be saved over here so I'll on just mark the size of one or maybe I'll use a different color to mark that so mark this as one and I'll save that over here so whenever so this way we have everything intact say next time I wanna access the value in the keytar what what happens 53 you know third bucket and address to the linked list we go to that address Isis the value and return it back and still we are having the time complexity of order one and the same thing happens for Hulk also say for Hulk 71 we know bucket one so next we create okay we'll create the next node attached to that okay so every time when we create consider we are saving the last known our city these say start and n addresses okay so in this case start is this so that is 1 and earlier the end node also was one because we never had this okay consider that way so now to get that address so using the start the venoms went here and then we created this node and then we link it but make it by direction and then save the value Hulk here so consider this is the address to and the value hug Sarki hug and its respective value so we know that here now we update n to 2 so all good okay now any time if you are access this link list we can use the start and end addresses and we can access this data similarly if I want to say flash 56 go six package from oh I forgot to update the address here right so the address to will go here okay similarly for fire flash where you go to cyst window or bucket and here before doing that so now we have to access the end okay so we know that we come here and then we create one more than world okay consider this services three we update the into three and here we will save flash and we connect bi-directional and also value of flash is same and then this is that you should be updated over here so so now I'm all good right so now anytime if we get any key we can get the value in order of one time say for example beyond access hug hug seven is the hash value we go to one bucket one we know the address of the north so we go directly to this particular node and then we get the value for associated with Hulk which is written it back so everything is still working the way it was supposed to work now how this particular bi-directional link list will help us to figure out LRU so that's the trickiest part so if you see over here this Lincoln is represent the order at which these keys were accessed say we accessed card first second Hulk and flash third so at any point of the time okay if I want to know that what was accessed very early R which was accessed recently so we know that flash files access to police entry and tar was accessed very first if one want to clear something off I can easily clear this off because this was accessed first and this was accessed very recently so now I can easily remove because when and if this data was accessed recently this diagram being in the first of the wrist I mean from this Android to the right side of the linked list because it is in the left side we know that this was the very first element which was accessed and we can easily clear that off okay so that way somehow this representation is telling us the order at which these keys were accessed so anytime we can figure out what was recently accessed what was accessed what was the old and key which was accessed so okay now consider what happens the same keys are accessed again and again so consider Hulk was accessed again what happens now 71 we got a bucket run so we know the address over here we go to 2 so now since this is access for now this is the latest record which was accessed what we need to do is we'll have to remove this guy from here so in linkage removal is out of one because it's bi-directional all we need to do is we have to remove this Hulk here okay and then link these two guys so it is still by directional linguist and I paint that guy which we remove to the first of linked list ok how do we do the first because we know the end of the linked list from this entry so three lately over here and then say for example we got B I just say let us say 2 and then we update the value same thing is Hulk and its value over here and now the end value is 2 so let's take that also so now still all good now this representation is again telling us the order at which the keys are the data from the cash flows axis no still I know that this was very taxes very first and this is the very latest record which we axis so now if I want to clear that off I can easily clear from the right side left side of the linked list I can clear this I can clear this I can rename this alright if I have a bigger chain I can keep on clearing it from the left side or the starting end of the linked list that way we know the order at which the keys are accessed anytime when the key is accessed we can delete the node in the double interest in order of 1 and we can reopen to the right side of the bi-directional linked list in order phone so everything isn't is working still in constant time the only thing is it is the linked list is taking extra memory and that is fine because we have to have LRU addiction policy so this way we we know that what are the keys we can delete what are the keys which are least accessed so LRU is the most used cache addiction policy because of its simplicity and simple to implement but the problem with that is it just keeps record of which was the least accessed or which was the most recently accessed key and value pair but it doesn't anyway count the frequency of access or what key was accessed how many times for that there are other implementations which uses count biscuit I have already made a video on continent sketch on how we can calculate the frequency of any given key value pair which is coming in much faster frequency efficiently please go and watch the particular video to understand how we can actually use common sketch to calculate frequency with less memory with less accuracy so now how do we design the internals of our caching system so we know we have hash table and we know we are using RAM we know we have LRU cache eviction policy and everything but still we need to have a service which accepts the requests like get put delete requests and then we have to you know update the data into hash table and then we have to read the data if there is a get request and if there is a delete request me to delete that since we know that we are using RAM even though it is faster it is kind of blocking call right so we need to have an efficient way of serving these requests one way we can do is we can spawn n number of threads as and when we get the request or we can have a bigger thread pool which can handle that and these things will not scale and it will cause lot of problems the easiest way we can handle E is event-driven logic in which say for example and here we will have an event queue in which any requests I get put are delete request will first be placed into the event queue and then we will have a event loop which is running which is a single threaded operation which will be running indefinitely and we have a thread pool here which just takes care of the i/o operation to the RAM what happens when I get request output request is enter a is requested that particular request will be placed into the event queue the even true on the other hand will be keep on reading the queue and handing over the request to the threads which are free in the thread pool and once it hiders to the thread it will come back and then which reads the next event that way the event group is never blocked the text will do their homework the thread which receives the request will do the i/o operation and gets the data and also the the human proof would have given the callback function and that particular thread it will execute the callback or it transfers the data to event so it will execute the callback and the the response will be sent back to the request either through the event loop or some of the cancer and this is how we can handle the requests more efficiently so now how do we make our caching system fault-tolerant are persistent as we know order for cash table and the data is saved in the bank for faster access our faster I go operation what if our system for some reason movie stars or something happens and all the data in the lamp is lost that means that our caste system is not persistent so to make it persistent we have to do something ok somehow we can retrieve back all of that data so there are two approaches to that so first one is regular interval snapshot so the name snapshot indicates that we take a picture at a certain state and keep all of the data savings somewhere something like hard disk so what we do is so the so there is a read and write operation happening here on the hash table so we'll have a service running in the background that is a synchro monster running in the background so it would take a frozen copy of the hash table and place into the dump file and this will be saved in the hardest okay that's one way to keep our snapshots in the dumps file regularly a particular interval of the time and that's how the Vettes also does so the second way we can do is by log construction or sorry by log of reconstruction so in this case what we do is so instead of having a synchronous service - which takes a snapshot of the hash table and save it somewhere what we can have is the service which retrieves the hash table or see the key value data from the hash table we'll keep on doing its job and also it will be logging the entry or the operation into one log file so what happens is say read write say write key and value read key and value say delete key and bang something like this it should we keep on entering all the operation and the key in the value data into a log file which is the in harness so since it can't be part of the synchronous requests going on make this as a a sync call which we keep on updating into the log file or we'll have a some kind of over in here queue or something which enters the log so that the performance of the reader boy it will not be affected and in the queue we'll have one more service which leaves from the queue and then update into the buffer so what do we need this is not file as I already said log reconstruction if we have each and every you know operation will be performed on this particular hash table even though if your machine goes down and it restarts and come back if you have access to this log file we can reconstruct the whole data or the final copy of the data which was supposed to be there in the hash table by executing each and every instruction in now in the time sorted order that way we can still recreate the hash table because we know the operation we have the key we have the value all in it is we had to recreate the whole scenario in in in the flash of time and then we fill the data in a hash table so with these two strategies we can think that we made our cache system persistent or fault tolerant so now we'll learn how do you make our fault tolerant or persistence now let's learn how do we make our system available or 100% available okay so consider in a node we have or in our cluster we have two nodes that is known one are several one our server two and both have its own cache a table say we are using consistent hashing consider this is handling some key and value and this handing some care value so this all is good so the problem with this strategy is what if this server goes down okay now if this server is not available all the requests which are coming to - will how cache miss are 21 response so what happens is all the requests which are coming to this supposed to go to the server will will be go will be going to the DB and hence the reader drives on the DB will increase so we have to make something to avoid this kind of problems when the several goes down so what we can do is we can have a replica of this server say for example say we will say as a replication factor - that means that we'll have to replicate every data into two copies same we'll have one more server which acts as a mirror image okay okay that is one compliment or something okay but this also will have one more server so whatever the data which does that has the same bit of in this guy also have now the advantages of this setup is now the load is also reduce because the request which is going to the server one can also be shared with the several one compliment or the copy of sever one that way the real requests are kind of distributed we get the little less latency and the performance is a lot better but the problem is we have to keep seeking the updates from which happens between these two server there is a little latency even it gets a bright or read there is a latency for syncing between the data between these two servers the same happens here also when we have network between these two machine there can be inconsistency whether they beat the data so that's the problem with this solution so how do we solve this mmm or if you can actually do is instead of having the copy of the server which can be used for read and write both operation what we can simply do is instead of making the server as a mirror image let's make that server as the slave simply it has a slave one machine this is slave to machine so in this case also the data page and everything in here the second servers database rice and Asians all will be updated basically that it is synced between this but the recent rice always happens on the master servers that is on these two servers and the requests will never be touching the slave server until this masters goes down okay so this is one way to solve the problem yes that's the end of system design for distributed caching system please go through the videos which I mentioned in between the explanation one is consistent hashing that exactly tells you how to distribute the cache system okay and the second - count means sketch which exactly tells you how we can actually calculate or keep track of the frequency of access for any given key based on that also you can devise an algorithm which can predict which key to be dropped or which key to be evicted okay I have provided those links in the description please make sure you go through those videos and these are really good videos so task for this video is I know it is a lot difficult to implement the whole caching system instead at least try to implement the hash table or the whole hash map implementation and also if possible try to implement consistent hashing and please provide the links of your core which is for student get about anywhere and I'm going to update those links on this video's description if you like this video please subscribe tell your friends to subscribe and also like share and comment thank you

Channel: Tech Dummies Narendra L

Views: 192,429

Rating: 4.7483144 out of 5

Keywords: Amazon interview question, interview questions, interview preparations, algo and ds interview question, software interview preparation, developer interview questions, Facebook interview question, goog

Id: DUbEgNw-F9c

Length: 34min 10sec (2050 seconds)

Published: Sat Oct 06 2018