Building a Redis clone in Go - Part 15 (Evicting Keys & allkeys-random eviction)

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, 10 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 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 same thing, basically, but for volatile keys, which are basically keys that can expire. So let's change all keys over here to volatile. 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 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? 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 codebase. 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 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. It samples a bunch of keys from your database, let's say 50 or 100 keys, right? By default, I think it only samples five keys at a time, but I'm not gonna 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 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 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 LRU or LFU algorithm. It's a more approximate version of that, right? And 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 or millions of keys, and having to do that every single time you run out of memory and you want to store new keys, that's 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, and 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`. 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 `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[1]`, convert this to an integer. Make sure to handle the error as well. If there's an error, let's say `log.Println`. 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.max memory samples` equals `mem samples`. 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.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` will take the key name, and it will return an item pointer and also the `ok` 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 `ok` 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 `ok` 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 remove all of this and just call `db.get`. Pass in the key name. This will return the item and `ok`. Let's declare that over here, and over here, let's just change `val` 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.tryExpire`, 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 the item, which will be an item pointer, and it 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. All right, and also fix this reference error over here. In `db.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.shouldExpire`, and this will basically return a boolean of this conditional. There we go. And then over here in the `tryExpire` function, we can just say `if item.shouldExpire`, if it should expire, we'd 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.tryExpire`, 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 `ok` field, which should, in this case, be false, right? Because if the item got expired, then it should just be false. 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.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 `Printf`. Let's say, "The item accessed um add a digit over here times add and print the time over here." So let's pass in the values, key name, and `item.accesses` and `item.lastAccess`. 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 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.go` for memory, package main, and add us an `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 struct over here. It will have a `k` field, which will be the key name, and the `B`, 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 struct 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 these maps in Go. Maps in Go are unordered by default, and there's no way to order them because maps in 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 an 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 require 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 zero, but the capacity will be max samples. And then let's loop over the entire database by saying `db.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's all we need to do. So we're taking advantage of those random order maps, right? As I said, maps in 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 five, 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 subfunction 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. We'll say if `db.memory` plus the required memory is less than `state.conf.maxMemory`, then we'll return true. Otherwise, we'll return false. And we're going to use this little subfunction in every single eviction policy over here to tell whether we've 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 created a little subfunction over here so that I can just reuse it again and again, right? I'm also going to create a new subfunction 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 samples list as such, and it will loop over the samples list and delete the sample key. And we can just do that by calling the delete function and passing in the key name, and check if we freed up enough memory by using this `enough mem freed` subfunction 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 the 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 Redis CLI. Set the name to a long string. We're using 115 bytes of memory. Let's set the 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? Did I mess something up? Oh, I did actually mess something up. This should be `all keys 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. Write a 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 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 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 yeah, thank you so much for watching.