Building a Redis clone in Go - Part 14 (Managing Memory & Evictions)

I'm back. All right, we're going to continue building this Go Redis clone. In this part of the series, we're going to build memory management and handling the maximum memory in this database server. So let's get started. First of all, we need to talk about eviction policies. So eviction policies in Redis are basically these policies that tell Redis how to handle the database store when it reaches maximum memory, right? So you know that Redis stores all of its data in memory, right? What happens if we run out of memory? That's what these eviction policies are going to help us decide, all right? So there's tons of different eviction policies to choose from and we're not going to implement all of them right now, but we are going to implement memory management and memory tracking features in this part, right? So that in future parts of this series, we can implement different eviction policies. Now the first thing we need to do over here is just track the memory usage of the database and the way we can do that is over here in this key struct right we can create a pointer receiver and just call this approximate memory usage alright and this method is going to basically calculate the approximate memory that this key is using in the database right now this is going to take the name of the key which will be a a string and now let's implement this. So first of all before we can actually calculate the memory usage we also need to consider the memory that the headers of each data type in this key are going to use. So let me explain. Things like strings right are going to use a header of 16 bytes right. This header is just going to contain some metadata about the string right. Every string in Go has a header like this and it's going to take about 16 bytes to store. We also have this time.time expiry field in every single key in the database and this is going to take about 24 bytes to store. All right now finally all of these keys are part of a map in Go right and every single item inside a map also has its own header. Basically a map in Go is going to store some metadata about every single item inside it and that's going to take about 32 bytes. Alright, so now we have all these headers right we want to add these to the actual data inside the key and that's about all we need to do to calculate the approximate memory usage. So let's just do a return string header plus the length of the key name plus string header plus the length of the value inside this key plus the expiry plus the map entry metadata size and over here in the function definition let's say this will return an integer and there we go that's all we need to do so now we can basically approximate how much memory every single key is going to use and notice that we're only approximating over here we're not trying to get the exact byte by byte memory usage of every key. We're just trying to approximate it, all right? Because calculating every single exact byte of the database store is just going to be very, very cumbersome, very, very error prone. So we're not going to do that. We're just going to approximate the memory usage of every single key and we're going to, yeah, just live with that. Now let's also go up over here to the database struct and add a memory field, which will be an integer. This will basically track how much memory the database is using at the current moment right and then let's go over to conf.go over here to add the maximum memory configuration directives to our config as well. So I'm going to add two new fields over here. One will be the max memory which will be an integer again and the other one will be eviction which will be a type of eviction and let's create this type down here as well right here let's say type eviction this will be a string and let's declare some eviction policies for now i'm just going to declare the no eviction eviction policy because right now in this part of the series we're just trying to build the memory management and tracking features in future parts we're going to implement the actual eviction policies. So this will just be I believe no eviction. So now we have these in our config struct. Now we need to actually configure them down here in the parse line function. But before I do that let's actually add the configuration directives in our config file as well. Let me add a comment over here and say memory and to declare the maximum memory that you can use in this server we just say max memory and then the number of bytes that you can use in this server all right so let's say something like 256 bytes you can also add symbols like kb mb or gb to just make it easier to represent different memory units over here right you can say 256 gb is the maximum memory that you can use or 256 kb or 256 mb and you can add things like these and the server itself will convert these back into bytes, right? A byte amount that it can use. So we need to do all that over here. Let's say case in the parse line function in config. Let's say max memory and this will return or sorry this will be assigned to conf.maxmem and I'm going to call a new function that we're going to create, parseMem, which will parse the actual memory unit, right? And I'll pass in the second argument, which will be this 256MB keyword, right? So let's create this function as well down here. Let's say func parseMem. There we go. This is going to take a string and it will return an int64, which will be the bytes, right? max memory that you can store in the server in bytes and also an error if there is an error during the execution of this function So first of all let just do some basic housekeeping over here Let say strings dot trim space and also say strings dot lower and pass in the string that we get. So basically convert it into lowercase and trim any space in the beginning or at the end of the string. Alright so just cleaning up the string a little bit before we actually try to parse it. Now create a variable called multiplier over here and assign it the value 1. Alright you'll see what this does in just a second. Let's create a switch statement and say the first case is strings dot has suffix. Pass in the string and then pass in let's say kb to start with in this case the multiplier will be 1024 right because every single kilobyte has 1024 bytes right so the multiplier is 1024 and now that we have that we can say the string that we get right s will be strings dot trim suffix so remove the suffix right which will be KB over here and that's all we need to do. Now just copy this and we can do the same thing for megabytes and gigabytes as well. Just change KB over here to MB and here as well and over here to GB and here as well. The multiplier in the case of MBs will just be 1024 multiplied by 1024 and in GBs just do the same thing three times and you're done basically. Let's add a final case over here for bytes all right and just change this to b and b over here as well and the multiplier will just be one so basically if you say something like 256 um there we go this will be considered raw bytes right not kilobytes not megabytes just bytes and if you say something like 256b this will also just be considered bytes right so that can be very helpful as well there we go Let's just say 256kb is the maximum memory that we can use in this server. Let's just say that. And now let's try to convert the memory into a string. Let's say num and error. str.atoy. Pass in the string over here. Handle the error as well. Let's say log.println. Actually don't even bother to print the error just return it Like this oh like this Why can't I there we go? Why am I so bad at this? And if everything is perfectly fine, then we say num multiplied by the multiplier and The error will just be nil there we go Why is this an error? So this multiplier is an int64. No, it's an integer. Okay, so just change multiplier to an int64. There we go. And over here, instead of using a toy, let's just say parse int. So we can actually specify how many bit size we want in this integer, right? So the base will be 10 and the bit size will be 64 so we get an inch 64 over here and with that we are done with the parse mem function now over here up here in the parse line function in the max memory case we can say and remove this conf over here we can say max memory and error is equal to this parse mem function call if the error does not equal to nil so if there's an error in this function let's just add a log over here cannot parse max memory defaulting to zero let's just say and then let's also print the error that we get over here let's say the max memory will be zero right actually conf dot max memory will be zero and then we can break over here otherwise if everything went successfully then we can say Conf.MaxMemory equals MaxMemory over here. And instead of this being an int, let's just make it an int64. Because when you convert this to raw bytes, I imagine it would be a very large number, right? So let's just make it an int64 just to make sure that we can actually hold this number with 100% accuracy, right? So with that we are done with the MaxMemory directive. let's do the same for the eviction eviction is going to be very simple actually we can say max memory policy and then we can just say cont.eviction equals eviction the type that we created and then just pass in the first argument over here and in our configuration we can add it over here as max memory policy and for now let's just say no eviction all right so basically let me just um quickly explain this if the eviction policy that you're using is no eviction right then redis will not you know evict or delete keys in the event of maximum memory usage right it will just return an error and say oh we've reached maximum memory you cannot store any more keys in this database right that's all it will do all right so for now no eviction is the best policy to use while we implement everything let's go back so we've configured everything in the config now we can go back to the db over here and actually write the code to track the memory usage all right and the way we're going to do that is in this set and in this delete method over here right so every time we set a new key we should approximate its memory usage and append it to the memory field in this database over here. Whereas every time we delete a new key or we delete an existing key, we should also subtract the memory usage of that key from the database memory over here So let implement both of those things now Let grab this key object over here that we declaring and at the top of the function over here in set let say key equals this key struct. Let's say the key memory equals key dot approximate memory usage. Let's turn this into a reference as well so you can use the method because this is a pointer receiver. There we go. and over here pass in the key awesome now we do need to pass in the name of the key as well which is k over here in the arguments right and this will return an integer which will be the memory usage of this key now down here we're storing the key in the actual database let's also say db.memory plus equals the key memory as well so this will track the memory usage every time we set a new key right but what happens if we set the same key twice right so let me just show you what that would look like right let's just add a log over here let's say memory and print the database memory over here right and then let's um start the server there we go open up a client as well let's say set name hassan you can see that the memory changed to 195 bytes right if i set the same key again you can see it changed to 293 bytes even though i didn't really make a change in the database right i just set the same key again right so we need to basically check if the key that we're trying to set already exists and if it does we should subtract the old memory and add the new memory of the key, right? So let's do that. Let's say if old OK, right, is db.store K. So basically, if the old key exists, right, then we should say the old memory equals old.approximate memory usage, pass in K as the key name. And then let's say db.memory and subtract the old memory as such. And now if I run the server again and try to set the same key twice, right? It's not going to do that. You can see memory is 98. If I do it again, it's still 98. All right, so we fixed that. Now we need to basically, every time we delete an existing key, we need to subtract its memory over here as well in the delete function. So let's do that as well. First of all, let's just access the key, right? By saying key, okay, db.store. and pass in k then before actually getting the memory of this key we need to make sure that it actually exists and if it doesn't then just return and fail gracefully all right and then we can say key memory equals key dot approximate memory usage and pass in the key name over here if we try to approximate the memory usage without checking if the key exists or not then we're going get a null pointer reference you've seen that in this in this server already we don't want that so make sure that the key exists then you can delete the key and subtract its memory from database memory and you can also add a log over here and say memory equals db.memory there we go now let's also make sure that we're actually using these set and delete functions in every single handler as well so first of all let's just go to the set handler over here and yes we are using db.set over here um and in the get handler if the key has expired then we're using db.delete perfect we should be doing the same thing and expire as well uh okay we don't need to do that over here but in ttl we should be doing it and yes we are and also in the delete handler over here yeah we're not doing it over here we should be using delete over here as well let's say DB dot delete our God well okay the key name is our God well got it so do that and this will not only delete the key would also track the memory usage and update it so we can see in real time how much memory were approximately using and yeah that's all we need to do now let's test this out let's run the server again let's run a client as well let's say set name to a son you'll see the memory is still 98 just keep an eye on these server logs over here and see the memory usage let's say the name is just a really long string all right and you'll see the memory is now 111 right so it increased let's say the number over here is a very long number over here and you'll see now the memory is 224 right so let me try deleting a key let me try deleting name and you'll see memory is 113 now right if i delete the num key as well memory is now zero so we're not using any memory in the in the database which probably means there's no keys in the database either right see there's no keys in the database anymore and we're using zero memory so memory tracking is working perfectly fine the last thing that we want to implement in this part of the series and this is getting really long already uh the last thing that we want to implement is actually the no eviction policy so let's do that as well let's create a function over here call it evict keys and this will be let's just say this is a pointer receiver to the database and this function should take the state the app state so we can use it to tell which eviction policy we're using and also a required memory field which will be an integer and this will basically tell us how much memory we need to free to set the new key that we trying to store so we can free up that much memory and then return right and it will return an error over here now for now we don need to do anything complicated over here we just going to say if state equals no eviction which is the only policy that we have right now let's just return an error and say maximum memory reached let's just say that and down here in the set function let's add a conditional let's say out of memory and this will be a conditional basically this will say if state.conf.maxMemory and we don't have the state variable over here we need to receive that as well so let's say state app state if the max memory that we've set in our configuration is greater than zero which means we've actually set a maximum memory value for this server and if the database memory plus the key memory the new key that we're trying to store is greater than or equal to the let's say the state dot font dot max memory and this will need to be converted into an integer to be able to be compared with with database memory over here. So to fix that, we can change this to be a memory of int64 as well. And over here in key.approxMemoryUsage, we can say int64 over here as well. And just convert this whole return value into an int64 object, there we go. And now we don't need to use this int converter over here and we're done basically. So if we've set a max memory value and the database current memory usage plus the new key is greater than or equal to the max memory in the server, then we'll say we're out of memory, right? And if we're out of memory, we're going to try and evict some keys by calling the evict keys method over here that we just declared. This will take the state and the required memory, which will be key memory, right? So this is the amount of memory that we need to free in order to store this new key in the database, right? Change this required memory over here in evict keys to an int64 and there we go and also Let's return nil as the error over here if there is no eviction policy that matches over here, right? just to satisfy the return condition and That's basically it. We're done over here. So the DB dot evict keys is going to return an error Let's also handle that as well. If the error does not equal to nil then we should return the error and This set function should return an error over here Down here. Let's also say return nil because if we get down here, that means the function executed successfully By the way, you can see there's so many tiny tiny details that we need to get right if you want to implement a working solution in these programs right anyway so this set function is being called in the set handler over here first of all let's just pass in the app state over here as well and also grab the error if they if the set function over here returns an error then we should return that error to the database as well to the client sorry this will be a type error and the error message can be error maximum memory reach or not even that but basically error plus the error that we get over there right from the set function call let's just do this save everything and let me go back to my redis configuration over here and instead of saying 256 kb let's just say 256 right so 256 bytes is the maximum memory of this database server right this is not a lot of memory but it will make it easier for us to test this out right so open up a client there we go let me just see how many keys we already have over here so we only have the name right so if I try to set it again it's not going to change anything if I try to set a very large number we got all the way to 208 bytes and the maximum memory is 256 right so let me try setting num2 and see if this gives me an error and it gives me an error awesome it says maximum memory reached right if I see all the keys in the database okay so something broke over here but basically it does work oh okay I got it right so the problem is we're locking the database up over here for writing and we're unlocking it down here right but if we return an error over here then we're not unlocking it right so let's add a DB mutex unlock over here if there is an error then we should release the lock and then we should return the error message so there we go let's restart the server open up a new client and let's say set num1 to a very large number and num2 you can see that we're using 204 bytes over here and set a new large number and you get a maximum memory reached error over here. If I grab all of the keys in the database you'll see that the name key and the num1 key has been set but num2 has not been set because we reached maximum memory over here. Awesome. So with that we are done with this part of the series. We implemented memory management, memory tracking. We are tracking how much memory that server is using and we're also making sure that we don't go above this maximum memory limit over here right. In future parts of this series, we're going to implement different eviction policies that will basically tell Redis how to delete keys and how to and which delete which keys to delete in the database to make room for new keys Alright, so we're going to do that in the future parts of this series. But for now, we're done with this. Yeah Thank you for watching like comment subscribe, and I will see you in the next video