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 the or restoring the first key and ignoring all of the other ones after that. Alright, so we fixed that issue in the previous part. In this part we're going to implement the all keys LRU and LFU eviction policy. 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 so in LRU we want to sort it as sorted by least recently used keys and in LFU we want to sort the samples 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 last access and the accesses fields in every single item. Alright, so sorting it should be very very easy. And once we sort it, we just need to call this evictUntilMemoryFree 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 dot slice function is going to take the samples list that you want to sort and then a function that basically tells us what the 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. Alright, so this will make more sense as I implement this but basically return a boolean will say samples I so the I element in the samples list grab the V field which will be the item grab its last access 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 last access field over here which will be time.time so basically all we're saying is whether the samples I items last access 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 evict until memory freed 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 dot V which is the item dot accesses there it is is less less than samples j.v.accesses. So basically if this sample was accessed less than this sample, then this sample, the IE sample will come first in the order and this j sample will come second in the order Now once this has been sorted by least frequently used again all we need to do is evict until memory freed and pass in the samples list And we don't really have a very large data set to test this on, but we can simulate this in a way. So let's test this out. Let's say the max memory policy over here will be all keys LRU in our eviction policy. and then let's run the server and open up ready CLI try to set a new key let's call it one two three four five six and you can see it evicted two fields to store it the job and the name key so LR you 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 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 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 all keys LRU and LFU eviction policies as well as the no eviction policy which basically does nothing but return an error and also the all keys random 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 no eviction 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 on those expirable keys right volatile random 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 volatile ttl 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've 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