Auto-generated transcript Welcome back guys to part 14 or part 15. Sorry, I ruined the intro. Part 15 of the Redis clone series. In the previous part, we implemented the no eviction policy over here, right? And we implemented memory management and memory tracking features in our database. In this part, we're going to implement the all keys random eviction policy. So all keys random, let's set that in our config, right and add it over here as well in the eviction list let's actually add all of the eviction policies right now so we have like I don't know ten different eviction policies let's say all keys random eviction is all keys random there we go there's also all keys LRU which is least recently used and then LFU which is least frequently used let's change the name over here as well all keys lfu all keys lru and then we have the the same thing basically but for volatile keys which are basically keys that can expire so let's change all keys over here to volatile uh they should be lowercase over here and volatile keys are basically keys that have an expire field set right so basically keys that are set to expire. The volatile eviction policies will only evict or delete keys that are set to expire. So that's that. And lastly there is a volatile TTL eviction policy and there we go. Okay so we have all of the eviction policies over here. In this video we're going to implement the all keys random eviction policy and what this basically does is it basically picks any random key from your database and just deletes it right it just deletes a bunch of random keys in your database to make room for the new keys that you're trying to set all right so this is kind of like the simplest eviction policy so we're going to implement this first and just make our way up from there right implementing more complex eviction policies in future videos now the very first thing i want to do is in db.go over here this key struct i don't like the word key over here because it's not only is it not storing the key name it's also storing the value which just makes no sense why is a struct called key storing the value uh the naming just doesn't make sense to me over here so i'm going to rename this to item over here right if you're in vs code you can just press f2 and rename the whole thing easily and this will also change all the references across the database across the code base otherwise no matter what ide or code editor you're using they should have a feature to rename an object and change all of its references as well but yeah just make sure that everywhere you use this um struct you're changing the name to item over here right or you could just stick with key but i just like the name item i think it just makes more sense to use that instead of key over here but anyway so now that we're actually implementing some eviction policies we want to figure out how redis actually decides which keys to delete all right so the way it does that is it samples a bunch of keys let me just write this over here so you can understand it samples a bunch of keys from your database let's say 50 or 100 keys right um by default i think it only it only samples five keys at a time but i'm not going to do that i'm just going to sample like let's say 50 or 100 keys i'll go with 50 probably but redis by default by default only samples five keys at a time i think and then inside those five keys whichever satisfies the condition of the eviction policy redis will just delete that key all right so for instance something like um if you're using all keys lru right least recently used this will basically delete the least recently used keys, right? So the oldest keys that you barely ever access, Redis will delete those keys for you if you use this eviction policy, right? But it's not 100% accurate, right? Because Redis only samples X amount of keys at a time, right? And then within those X amount of keys, whichever key satisfies the eviction condition, like least recently used or least frequently used, Redis will just delete that key right it may not be the most least recently used key it may not be the least frequently used key but if if it matches that condition inside this sample of keys right five keys in this instance in this case then Redis will delete that right so it's not a true true LRU or LFU algorithm it's a it's a more approximate version of that right and the reason the reason Redis does this is because it is a key value store that is expected to provide high throughput, high output and high fast performance, right? So having to loop over the entire database store, right, which could be thousands of millions of keys and having to do that every single time you run out of memory and you want to store new keys That just really really bad for performance right You would have to loop over the entire database right So Redis avoids that by just getting a small sample of keys from the database and just running the eviction policy on those keys and Deleting a bunch of keys from that sample. So that's what we're going to do as well First of all, hopefully you understand the entire process But first of all, let's go over to the config file and add another directive over here. Call it max memory samples. I'll say this is 50 to begin with. So basically Redis in this case in our server, our Redis server will basically take a sample of 50 keys and run the eviction policy on those 50 keys. All right. Let's also configure this in the conf.go file over here. Up top, I'll add a field called mem samples, memory samples. this will be an int then let's go down to the parse line function and add a case for max memory samples there we go and say um mem samples and error equals because we need to convert this into an integer right because this is a string to start off so let's say args one convert this to a string make sure to handle the error as well if there's an error let's say log.println um there we go cannot parse max memory samples defaulting to 50 and print the error over here as well there we go and say mem samples of the config is 50 and break out of the loop there we go if the conversion was successful then say conf.memsamples equals memsamples there we go and now we basically configure this over here now i did mention that in this video we're going to only implement the all keys random eviction policy but let's also lay the groundwork for lru and lfu right least recently used and least frequently used so to do that go over to db.go and go over to this item struct which was previously called keys. I'm going to add two new fields over here. I'm going to say last access which will be a time dot time. This is the last time that this key was accessed or this item was accessed and also accesses. So how many times this has been accessed right and these two fields will basically help us to implement LRU and LFU eviction policies. So to track both of these we need a get method over here right so we have a delete we have a set we also want to add a get helper method to this database struct so let's do that as well. Get this will take the key name and it will return an item pointer and also the okay field which will be a boolean so let's name both of these as well go allows us to name our return values which is pretty useful honestly so let's implement this first of all we want to lock the database for reading then let's grab the item by doing db.store pass in the key name if the item doesn't exist then we should just return the item which will be nil probably and the okay boolean over here right now once we've grabbed the item we can just release the lock over here and we can say return item and okay down here all right now let's go over to the get handler in the handlers file over here you can see that we're doing something similar over here right we're just grabbing the value from the store if it doesn't exist we return nil we also check the expiry over here right so let's do that as well first of all let's just um remove all of this and just call db.get pass in the key name this will return the item and okay let's declare that over here and over here let's just change while to item here as well and here as well there we go okay now we also want to check the expiry over here all right so let's grab the entire thing over here and let's create a function over here just a private helper method over here call it db dot um try expire so try to expire this key and if you can then great otherwise if it is a persistent key or if it hasn't expired yet then we can return it right so this will take the key name as well as well as the item which will be an item pointer and will return a boolean which will basically tell us whether the expiry was successful or not so over here let's return true if it got expired otherwise return false alright and also fix this reference error over here in DB dot delete we're going to pass in K which is the key name and also this whole conditional I want to move it to another method down here in the item struct I want to say something like item item should expire and this will basically return a boolean of this conditional. There we go and then over here in the try expire function we can just say i the item dot should expire. If it should it expired we expire it otherwise we return false there we go now back in the get function over here we can try to call this say db.try expired pass in the key and the item and say expired equals this if it was expired let's return nil for the item or just an empty item struct i guess plus the um okay field which should in this case be false right because if the item got expired then it should just be false right there we go change this to a pointer to satisfy the return condition and we are done with this as well and finally let's also update the fields over here for the item let's say accesses this should be incremented and last access should just be time dot now right so the current time and then we'll basically just unlock the database for reading and return the item and the ok boolean there we go make sure you call this in the get handler over here in the handlers file and yeah that's basically all you need to do so to make sure that this is working as well let's add a log over here let's say print f let's say the item accessed um add a digit over here times at and print the time over here so let's pass in the values key name and the item dot accesses and item dot last access all right and now let's try to run this whole thing let's run the server let's run a client let's say get name and you can see it got accessed one time at this particular time right if i try to do it again it was accessed two times on this time right and i just keep doing that and it will update the accesses integer and the last access time over here so we can get both of these fields now Awesome. Okay, so finally we are ready to implement the all keys random eviction policy. So let's go over here up top and say switch and the expression will be state.conf.eviction. The first condition will be all keys random. Now before we can actually evict any keys, we need to grab the sample of keys like we mentioned before, right? We need to grab a small sample of keys from the database that we can then evict and delete, right? so To do that. Let's create a new file. Call it mem dot go for memory Package main and add a some add a sample keys function over here This will take the app state and return a list of sample objects now each sample Will just be a sample struck over here. It will have a K field which will be the key name and the V which will be an item pointer by the way the reason I am creating this new struct over here and returning a list of that struck of samples over here is because you might think that you can just return the map itself right a small map something like what you have in the database right now right like a map like this right there's two problems with this maps in go are unordered by default and there's no way to order them because maps and go always have a random order right the only way to order items is to have a slice or a list of those items and that's basically the only way that you can have a have a order to items in your go program right and we need to have some sort of order if we're going to implement things like LRU and LFU right things like these required our sample size our list of sample keys to be ordered right so that is why I create a new struct over here and return a list of that struct all right first of all let's just grab the max samples that we can have which will be state.conf.memsamples then let's use the make function to create a slice of samples this will be a list of sample objects the length will be 0 but the capacity will be max sample and then let's loop over the entire database by saying DB dot store over here there we go and then let's append to the samples list create a sample object over here the K will be decay the value will just be the value and let's say if the length of the samples list is greater than or equal to integer is greater than or equal to the max samples right then we should break and finally down here return the samples list awesome that all we need to do so we taking advantage of those random order maps right as i said maps and go are always randomly ordered they don't have a specific order so every time we loop over the map right the database store over here it's going to give us a random order right and then we just keep filling up the items in our samples list and as soon as we get to the maximum samples as specified in our config file then we just break out of the loop and we return the samples list so we don't loop over the entire database we just loop until we get the maximum samples that we're allowed to have this can be 5 10 50 100 or whatever you set in your config file right so this will return the sample keys that we need let's go back to db.go over here and up here let's grab the samples list by running this sample keys function passing in the state and now we have a list of sample keys that we can evict and delete now let's also create a little sub function over here call it enough memory freed and this will be a function which basically tells us whether we freed up enough memory to store the new key right or not this will basically just return a boolean will say if DB dot memory plus the required memory is less than state dot con dot max memory then we'll return true otherwise we'll return false and we're going to use this little sub function in every single eviction policy over here to tell whether we freed up enough memory and we can return now or should we continue to delete keys until we free up enough memory all right and that is why i create a little sub function over here so that i can just reuse it again and again right i'm also going to create a new sub function over here call it evict until memory freed and this will basically evict keys until we have freed up enough memory to store the new key so create another function over here this isn't going to return anything but it is going to take the sample list as such and it will loop over the samples list and delete the sample key and we can just do that by following the delete function and passing in the key name and check if we freed up enough memory by using this enough mem freed sub function that we just declared right now call this if it returns true if we freed up enough memory then we can just break out of the loop and return from function otherwise we should just keep looping and keep deleting more and more samples until we've deleted enough of them to store the new keys awesome now in the all keys random case over here we just need to call evict until memory freed and pass in the samples list and that is all we need to do to implement this awesome now let's also add a log over here just so we know what's going on let's say evicting plus the key name all right now let's run the server and see if we implemented everything correctly open up ready CLI set the name to a long as string we're using 115 bytes of memory let's set the I guess age to a really old person 233 bytes of memory being used let's set another key num to a large number I know it's using even more memory now what the hell can I mess something up oh I did actually mess something up this should be all keys dash random all right since we had the wrong name of the eviction policy it just didn't get scanned over here and we got an empty eviction policy and if we have an empty eviction policy it's just going to return nil over here so that's a problem let's rerun the server now right is CLI open up a client set num1 a really large number 205 bytes of memory being used the maximum is 256 let's set num2 a really large number and you can see it just evicted the name key over here you can see evicting name and then we get less memory than 256 all right so we're we're basically staying below the limit of 256 bytes it just evicted the key name i can prove that by saying keys and you can see the only two keys that we're storing is num1 and num2 that we just declared up here we're not storing the name key over here if i try to get it it's just going to return nil so all keys random eviction policy is working perfectly in the future parts of this video or this video series we're going to implement all of the other eviction policies that we've added over here and uh yeah it's gonna be a fun time thank you for watching this one and i will see you in the next video make sure to like subscribe comment and do all of those wonderful things that drive up the algorithm for me and uh yeah thank you so much for watching