Building a Redis clone in Go - Part 17 (allkeys-lru and allkeys-lfu)

Welcome back, guys. This is going to be part 17 of the Go Redis Clone series. It's remarkable we've filmed 17 parts of this series. We're going to implement the AllKeysLRU and the AllKeysLFU eviction policies. So let's get started right away. Let me just recap. In the previous video, we fixed some issues with the AOF file synchronization, where it was basically just backing up or restoring the first key and ignoring all of the other ones after that. All right, so we fixed that issue in the previous part. In this part, we're going to implement the AllKeysLRU and LFU eviction policies. So let me add both cases over here. Let's say LRU and LFU over here. There we go. So this is going to be a very short and simple video because we already have all of the building blocks that we need to implement both of these eviction policies. All we need to do is sort the samples list by the condition over here. So in LRU, we want to sort it by least recently used keys, and in LFU, we want to sort the samples list by the least frequently used. All right, and we already have all of the building blocks that we need to do this. We have the LastAccess and Accesses fields in every single item. All right, so sorting it should be very, very easy. And once we sort it, we just need to call this EvictUntilMemoryFreed function, and this will just keep deleting items from the samples until we freed up enough memory, and then we'll break and return. Awesome. So let's implement this. So first of all, least recently used. Let's call sort.Slice over here, and let me also add a comment over here as well: sort by least recently used. So the sort function is going to take the samples list that you want to sort and then a function that basically tells us how to sort the slice, basically. So in the function call, they basically call this a less function, and all you really need to do is basically compare two elements from the slice and tell whether the element I is less than element J or not. All right, so this will make more sense as I implement this, but basically return a boolean. We'll say samples[i], so the ith element in the samples list, grab the V field, which will be the item, grab its LastAccess and call the After function on it. Then grab the samples[j] item V, which is the actual item inside the sample, and use its LastAccess field over here, which will be time.Time. So basically, all we're saying is whether the samples[i] item's LastAccess happened after the samples[j] item or not, and this will basically sort the slice by least recently used. Once it is sorted, all we need to do is call EvictUntilMemoryFreed, pass in the new samples list that has been sorted by least recently used, and that's done. All we need to do is done. Awesome. Now, moving on to LFU, we want to sort the slice by the... What just happened? Oh, there we go. Okay, we want to sort the slice by least frequently used. All right, let me add the comment as well. So pass in the samples list, and in the function, in the less function over here, let's say samples[i].V, which is the item, .Accesses. There it is. Is less than samples[j].V.Accesses. So basically, if this sample was accessed less than this sample, then this sample, the ith sample, will come first in the order, and this jth sample will come second in the order. Now, once this has been sorted by least frequently used, again, all we need to do is EvictUntilMemoryFreed and pass in the samples list, and we're done. We don't really have a very large data set to test this on, but we can, like, simulate this in a way. So let's test this out. Let's say the max memory policy over here will be AllKeysLRU in our eviction policy, and then let's run the server and open up Redis CLI. Try to set a new key. Let's call it 123456, and you can see it evicted two fields to store it: the job and the name key. So LRU works. We can do the same thing for LFU. Restart the server. Okay, where is CLI? And by the way, you can see that the maximum memory that we allow is 256, but when you synchronize the AOF records, it actually bypasses those limits over here. Why? Because if I show you the AOF file over here, you can see that in the AOF sync function, we're passing in a completely blank app state with a completely blank config, right? This blank config does not have a max memory value set, right? So as far as the AOF sync is concerned, it does not have a max memory limit, right? Because this config is empty over here, which is why it bypasses the memory limits over here when we synchronize the AOF records. And we will fix this in a future video, but just letting you know this is why we are going beyond the memory limit of the server. All right, anyway, we're using LFU eviction now. Let's try to set a new key again and just give it a large number or something, and it's going to evict a bunch of keys until it's made some space. And now the current memory being used is 207 bytes. And I can run the KEYS command and see that the only keys available now are new key and job, right? Name and age were evicted, as you can see in the logs over here, and now we only have these two keys in the database. Obviously, I can GET them as well, and that works too. So we've implemented the AllKeysLRU and LFU eviction policies, as well as the NoEviction policy, which basically does nothing but return an error, and also the AllKeysRandom eviction policy, which just basically removes keys from the database randomly. So yeah, we've implemented most of these simple ones over here. Let me just quickly, let me just quickly explain both of the, all of the remaining eviction policies as well. So the volatile eviction policies only act on keys that have an expiry set, right? And if you have no keys in your database that are set to expire, if all keys in your database are persistent, then these volatile policies will just behave like NoEviction, and they will just return a maximum memory error, right? But other than that, implementing them all is very simple, right? You basically just want to filter out the keys that can be expired, and then you can just run the same functions on those expirable keys, right? VolatileRandom will just randomly delete expirable keys. LRU and LFU will order the expirable keys and then delete them. TTL is a bit different. TTL will basically delete the keys that are set to expire the fastest, right? So if you have, like, two keys in your database, one is set to expire in five seconds and the other is set to expire in 10 seconds, VolatileTTL will first delete the key set to expire in five seconds and then the key set to expire in 10 seconds. So that's what that does. And yeah, we're going to implement all of these in the future videos. Thank you for watching this one. As always, thank you so much for supporting this series. We filmed 17 parts of this series, which is insane. So if you're still watching this, thank you so much. Like, comment, subscribe, and I will see you in the next video, where we will continue implementing all of these remaining eviction policies. Until then, take care and bye-bye.