Implementing INFO and allkeys-random Eviction | Redis Internals

Indexed: 2026-05-22

[00:00:00]so in this one let's Circle back to an eviction strategy called All Keys random last time we implemented simple first eviction strategy the idea was to evict the first key that we can iterate to right but now we take it to the next level all keys random the idea is pretty simple out of all the keys that exist in the radius DB or in our database we would be picking keys at random and we would be evicting it right so let's take a quick look at implementation for that so here I've changed the eviction strategy to All Keys random which will be implementing but apart from that I am setting my keys limit to 100 we are still relying on the maximum number of keys as our threshold that our database at Max supports 100 keys right apart from that and this is mostly for a demonstration in production this would not happen like this but this is for demonstration purpose then I am defining a thing called eviction ratio this means that it would dictate that whenever my eviction is triggered how many keys would I be evicting right this is the idea behind it how many keys would I be evicting whenever my eviction would be kicking in so 0.4 implies that I would be evicting 40 percent of the keys although that's not a production great thing you would be evicting only few keys and not 40 percent of it but this is just for demonstration purpose so that we can see our eviction algorithm working right now let's take a look at the eviction strategy we'll go to eviction.go file and see what how we can implement this so first of all what we do is we look at uh evict all keys at random which is what we have added in our switch statement as well key all keys random effect all key is random over here and what it does is it first identifies the number of keys that it needs to evict which is the total number of keys that it has the maximum limit and the eviction ratio eviction ratio is 0.4 so 40 percent of the key is limit is the number of keys that we would want to evict and we iterate through the hash table once we iterate through that we would be deleting every count number of keys from that by invoking delete on it right as simple as this now here what we are relying on is we are we are relying on the randomness of the iteration of it it's not entirely random but the idea is that the way higher hash table or golang's hash table is adjusted whenever we are inserting a particular key it is passed through the hash function depending on which it would get any one of the slot now given that we don't know what the output of the hash would be we can treat this as a fairly random distribution right so this is how we would be implementing the all keys random strategy here we are relying on the randomness of the hash function right but depending on your implementation you can implement it however you want but this is the easiest one to implement right and this is how you support that as simple as this but now how do we know that our eviction is really working which means that when we are doing a large number of key sets like we are putting a lot of keys in our database what needs to happen is that let's say we given that we have set our keys limit to 100 how do we know that we are not breaching that so that is where any and every database supports statistics so does redis right so let's take a look at what stats are all about in redis will take a very quick example over here so like always top right is where we are running our regular redis server right and on the bottom left what do I have is on the bottom left I have are uh will be connecting through our CLI so dot slash redis CLI is what I'm passing over here and I'm connecting to Port 6379 which is normal ready sport I have connected to it right so let's see if I do set K1 V1 a key set right and now if I fire info you get some output now this info is the redis command that when you fire it gives you the statistics about the database at that given instant right so if I fire in for right now what is the info about my database at this moment is what is outputted over here the section that we are interested in is key space so this key space section that we have over here sorry so this key space section that we have over here is what it holds or it tells the number of keys that are there right so now in database 0 the number of keys are 1 expires 0 to average CTL 0.

[00:04:34]we don't care about X bars and average detail we are interested in number of keys right this is what now we would be implementing right so we want to see how these stats look like we want to support this stat so that we can see if we are ever like our key eviction in action right so before we do that let's take a quick look at what stats are all about and what's the response format of it so stats are extremely crucial for database it helps us monitor our database really well set up alert set up like give it gives us transparency it gives us confidence that our database is working fine right and we can use info command to get the statistic we just saw as an example now what does info command returns info command returns information about the database information is classified into multiple sections each section starts with a section title which starts with hash space section title so for example what we are interested in is key space so hash space key space is what the section title would be then a new line then you would get key and a value followed by slash r slash n right so for key space it would be hash space key space db0 colon some value now here value itself is key is equal to 4 your here your key is db0 and the value is key is equal to 4 right here your key is DB1 and value itself is key is equal to 7 right so you can have as much as you want the idea here is pretty simple your keys are important and values is like depending on the format you would be writing the parser to understand it right and then you had a other Matrix like server metrics like what version it is running what's the memory consumption of it what's the cache Miss ratio and what not all of that would be visible there all Arrangement key value key value the key colon value key colon value followed by slash R slasher right this is how it is done but now when you would want to visualize it you would want to given that redis gives us point in time statistics so when you fire an info command you will get output of that you will not get historical output so that is where you need a way to see the historical trends of it so how do you do that that is where tools like grafana comes in grafana is a visualization tool I mean right so graphene has a visualization tool can you can plot very fancy charts on grafana and see how your database fared over time we have a radius DB running redisdb supports info command that gives us point in time response so what do we want we want something that gets this information from redis persisted some database which grafana can use to render it right that is why we are using Prometheus Prometheus is a Time series DB that pulls the data out from any database and it puts it in its time series DB format which grafana can understand and plot the graph right so this is where but Prometheus cannot support all the DB so that's where you have plugins that's why you have exporters right so we'll use a regular radius export or nothing fancy we lose existing Prometheus we'll use existing radius exporter because we are building redis compliant database it was much easier for us so rdb implementation would be implementing info command that exports the information in the exact same format that your redis exporter like that your normal radius DB exports in which means that redis exporter would not even know that is it talking to dice DB or redis it would mean exactly the same thing for it so redis exporter would read would continuously fire info and would be collecting this metric and exposing it on an end point Prometheus will read this endpoint and persist it in its time series DB and graphana will use it for visualization right so this is what we would be mimicking on the local so that we can see how our number of keys is changing over time right so this is just about visualization but when we do that we'll see the importance of making a DB our dice DB compliant to reduce that we are not have to re-implement anything we are just using existing toolings to just see our implementation in action right okay so let's take a look at the implementation part of it so here what we do is we implement the part where we just looked at eviction I'll close the eviction now we'll start with stats because for stats we are implementing info command so let me take you through the eval file where we are defining all the commands so if I go below you can see three commands being implemented the main one is info what info command does is we saw the format what we are interested in is number of keys other sections we don't care right all we carry is key space sections which is what we would be responding so hash space so we created a buffer where then we are writing hash space key space slash r slash n and then for all the key space stats that I have I'm just concatenating it putting it into buffer db0 colon key is equal to percentage DX part 0 average detail zero we don't care about X bars and average TTL all we are interested in is keys right so that's what we are implementing and then here we are doing key space of I of keys bra what is this here it's just a global object so for example I support four databases within my redis so in redis you can have 16 databases within radius Itself by default it goes into db0 right so db0 to db15 is what you can have so here I'm just because we are building a small one I'm just sealing it at four right we are having 4 DB so by default when we are doing gets and sets and everything by default it goes to db0 right so an update DB status one function that I have exposed whose job is to for which DB for which metric what's the value so for db0 for db0 I want to set keys to be 1 2 3 4 and so on and so forth right this is what we are trying to store right so that is what I am creating this object for but where would we do that that is where our store file comes in every time we are putting an object what we would do is we would do key space stat of 0 of keys plus plus so for the 0th index because it's a map of string of int setting the key string to Value Plus plus which means if 0 it becomes 1 1 it becomes 2 3 4 and so on and so forth so every time we are putting it this Global dictionary gets updated and whenever we are deleting it the same thing gets minus minus so this way at the global dictionary level we would have the number of keys at that given instant right so which means that our info command when it is iterating through that it would get the exact number of keys at that given moment and we can render it or we can send it to the client in a bulk string response right so let's see this in action so here what do I have is I have a Arc I have our classic implementation of our terminal where top right normal radius we don't get about that right now because we have implemented our own info so on the top left what do we have is we have our our implementation so we are doing go run main.gov now our DB is running on Port 7379 on Port 7379 I'll use my radius CLI to connect to Port 7379 which is rdb and the clan got connected now here I do let's say I first fire info command here you will see everything is zero db0 DB1 db2 db3 number of keys are zero let's say now I do set K1 V1 as soon as I did that firing info you can see db0 key is equal to 1 everything else is 0. we have not even implemented that right so it goes to zero my keys are changing let's say I do set K to V1 I'll say number of cases too right similarly K3 V1 number of Key System right so now the number of keys are increasing right so now here how do we visualize it so here we can visualize this particular part with our browser so here this is the grafana instance that I have running in which I am plotting The Matrix for last uh for basically last 15 minutes right so here I have this graphana Matrix running in which you can see the graph let me just clear it up so that it looks neater and cleaner so now you can see that this is refreshed right now you can see the number of keys is three right let me just add more more keys to that right let me just add more keys to that and we can see that the chart will now shoot up now if I do set K4 V1 and then I do set K5 V1 and I do set k6v1 right so here if I do this what do I get is I get our charts when I refresh it I can see this particular thing shooting up right so you can see the number of keys getting increased so here you can see that graph right on how the number of keys are there so I have written a very quick utility where I can bombard this server with a lot of set request right and what we would do is we would be firing a lot of set request over here so that we can see our eviction strategy in action so here I have written a storm utility it's again checked in the code base normal bulk request that we are firing go run storm set main.co it will continuously keep on firing random keys in our database and here you can see the number of keys are increasing you can see the chart and see that the number of keys are increasing I am just constantly refreshing it now the number of keys have returned have reached 100 almost about to reach 100 the latest value is 71 here you can see at the bottom the latest value 71 now you can see this is increasing and then decreasing again the last value is what you are seeing that the yellow dot is the last value which is being inserted which is being the number of keys now here you see even as the time increases my number of keys would never go beyond 100.

[00:14:47]but if you see the yellow dot goes up and then comes down it goes up and then comes down White is coming down because our eviction ratio is 40 percent so every time our lru is running every time our lru is uh yeah basically every time our eviction is running it is evicting 40 percent of the keys right so it would come down go back up come back down go back up and come back down right and this is how you would see your eviction but you would never see it go beyond 100 right now see the graph is again rising up and this is and the value that it is plotting is once like I am refreshing it again and again you would not see point in time things but you would see once every second it is registering one data point but here you can see the number of keys is never never cross 100.

[00:15:36]the yellow thing it clearly you you can clearly see a Sawtooth pattern emerging you're setting a large number of keys it would increase then when it hits 100 it would be evicting 40 percent of it it would drop down to around 60 and then again adding again dropping again adding right so this is what you would see a Sawtooth pattern but at no stage the number of keys in our database will cross 100 although we are constantly bombarding it we are constantly bombarding it here you can see on the bottom right my script is running it is constantly running set some key and some value constantly bombarding it but it has no impact on rdb our DB is running just fine capping it at 100 uh basically 100 keys right and this is where you see your eviction strategy in action right we implemented all case at random with a certain threshold right our eviction ratio and why we choose eviction ratio is 7 is 40 so that so that we can see this clear pattern if you reduce your eviction ratio to let's say 10 like let's say 10 percent or five percent you would see that just just slight swiggles there right but with this 40 it would be sharply declining which the number of keys would sharply Decline and then rise up and then Decline and then rise up and then decline so you can tweak a eviction ratio with your as per your use case right but typically redis also does very small number of actions 5 to 10 keys at Max it does not evict a large number of keys at all right but this is where you see this in action now here what have we achieved what have we achieved is we implemented two things all key is random eviction algorithm second statistics right given that I didn't have to build any single thing because that we are re-implementing radius we are using existing redis tooling to visualize this part and and how beautiful is this because we see given that for us its understanding but we being able to reuse existing toolic makes our life so simple we are using existing ready CLI itself we are not have to write explicit CLI for ourselves right and which is what I would highly highly highly highly encourage you to implement it so easy so simple and so fun to be honest right so yeah again the source code the entire source code can be found on github.com dice DB slash dice go through the commit go through comment number eight or nine you'll like the like the commit messages are self-explanatory go to this commit see the changes that we have made we might not have did the best implementation for key space stat but it's enough for us to see our eviction strategy in action and then over time when a database matures we can make it as complex as fancy as we would want to right but idea Remains the Same understanding is much more important than anything else and we think we did a very decent job there so yeah that is for this one now what's next the next is about approximated lru algorithm in detail we would know like we would learn about how redis actually does that a couple of videos back when I was talking about redis object we saw lru bits said that there was 24 bits for that and that is uses for approximation algorithm so next video we will understand how it does that theoretically we'll understand what is exactly happening behind the scenes and then the video after that we would be implementing it by going through the actual redises source code to see that exact same thing in action and that's such a beautiful piece of code a very interesting algorithm very simple to implement mix lru super super super efficient at scale right so yeah that is it for this one I hope you found it amusing you saw how we implemented all keys in random eviction strategy we implemented our own stats we visualize it through grafana stored in in Prometheus so that we can see this nice baby pattern so yeah that is it for this one I'll see you in the next one thanks