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, all right? 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 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 are going to use a header of 16 bytes. This header is just going to contain some metadata about the string. 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 going to take about 32 bytes. All right, so now we have all these headers, right? We want to add these to the actual data inside the key. And that 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 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 go over to conf 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 of that over here. Let's say case in the parse line function in config. Let's say max memory. And this will return. Oh, sorry. This will be assigned to cont.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 256 MB 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? The 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's just do some basic housekeeping over here. Let's say strings.TrimSpace and also say strings.ToLower 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. All right, 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. All right, you'll see what this does in just a second. Let's create a switch statement and say the first case is strings.HasSuffix. 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.TrimSuffix. So remove the suffix, right, which will be KB over here, and that 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, 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 256. I speak way too fast. 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 err := strconv. 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? Because multiplier is an int64. No, it's an integer. Okay, so just change multiply to an int64. There we go. And over here, instead of using Atoi, let's just say ParseInt 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 int64 over here, and with that, we are done with the parse memory 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 maxMemory and err is equal to this parseMem 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 0, right? Actually, conf.maxMemory will be 0, 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 max memory directive. Let's do the same for the eviction. Eviction is going to be very simple, actually. We can say maxMemoryPolicy, and then we can just say const 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 maxMemoryPolicy. And for now, let's just say no eviction, all right? So basically, let me just 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's implement both of those things now. Let's grab this key object over here that we're declaring, and at the top of the function over here in set, let's say key equals this key struct. Let's say the key memory equals key.approximateMemoryUsage. 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 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 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 := db.store. So basically, if the old key exists, then we should say the old memory equals old.approximateMemoryUsage, pass in K as the key name, and then let's say db.memory and subtract the old memory as such. 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, ok := 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.approximateMemoryUsage 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 to get a null pointer reference. You've seen that 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. 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. 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.delete r.bulk. Okay, the key name is arg.bulk. Got it. So do that. And this will not only delete the key, but also track the memory usage and update it so we can see in real time how much memory we're 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 Hassan." You 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 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, 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 called `evictKeys`, 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're 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't need to do anything complicated over here. We're just going to say if `state.conf.eviction` 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 appState`. 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.conf.maxMemory`, and this will need to be converted into an integer to be able to be compared 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's 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 `evictKeys` 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 `evictKeys` 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.evictKeys` 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 we 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 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, and 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, oh, 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 have 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 which keys to delete in the database to make room for new keys. All right, 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.