Implementing DEL, EXPIRE, and Cleanup in Redis | Redis Internals

本站添加: 2026-05-07

[00:00:00]so in the previous video we implemented get put and TTL in this video we would be implementing delete expire and we will see how red is does Auto expiration of keys which means Auto deletion of expired keys right so first like always let's see whether behavior of a normal ready server is and then we would be re-implementing it in our own golang based implementation like always top right contains the normal ready server running on Port 6379 and bottom left is where we are connecting it through ready CLI now let's say I set a particular key K with value V right now if I do a delete here you can see that delete is taking an argument which is key if I pass in K the key would be deleted the return value is one what does this one mean this one is the number of keys which are deleted so delete if I do delete K again e k is already deleted what would be the return value and return 0. so one is the number of keys that were successfully deleted because key K didn't exist like after we deleted it does not exist anymore when we hit the delete again on the same key it returns 0 right now if I set multiple Keys key K1 V1 set key K2 V2 and now if I do delete K1 K2 K3 K4 two keys exist K1 and K2 but I am triggering delete of K1 K2 K3 K4 it returns me 2. 2 implies that out of these four two keys were deleted and two keys didn't exist it's a no op operation so now if I do run this command again we are getting 0 because K 1 k 2 K 3 k for all four doesn't exist right that's why it is returning me zero this is what we would have to re-implement right so this is how delete Works second is let's see how expired works let me set a particular key K with value V and now I am triggering now what a use case of expire is let's say I set a particular key and while setting I didn't provide any expiration but then I realized hey now I want to set an expiration to this key so that's where what I can do is I can pass in expire function with k with key K and the second argument is the number of seconds let's say I want to expire this key by 10 seconds as I fire this now if I do TTL of K you can see the time elapsed or the time to live for that is consistently decreasing and decreasing and decreasing and decreasing right so this is how your TTL was set with expire right now if I what happens if I pass in a key that does not exist let's say I pass in ABC this key does not exist first because I didn't pass second argument it gave me syntax error now if I pass in argument it returns me 0. what does this 0 mean if this 0 implies that the operation was unsuccessful it could be because e does not exist it could be because any reason so if your radius was able to set an expiration it would return 1 if it was unable to set an expiration it would return 0. so here if I do a set K comma B and if I do expire k in 10 seconds it returns me 1 because setting like setting the expiration was successful right this is what the return value of x bar is now given that we know how delete and expired behave we would be re-implementing it on going base but it is not done yet because we also like after we go through that we would be taking a look at how reduce does Auto deletion so if the key is expired it would need to Auto delete the key right we would be implementing that as well so that is a very interesting algorithm that we would look at at the end so first let's start re-implementing this and see and do a very and do an extremely detailed Code walkthrough so what we would do is we would start with our normal eval.go file eval.go file is where we are implementing all the commands and here we add delete and expire command delete again all the arguments passed over here and an i o read writer similarly for expire so here if I check if I'll delete what do we see eval delete whatever argument we have passed are the keys and we just have to iterate over them and explicitly delete it from the hash map that we are the hash table that we have we are just doing that we are iterating over all the keys and we are triggering a delete this delete is a store function written in store.go file the objective of this is so that we mask the any complexities that might aware oh sorry that might come up so what it does is it just triggers a delete from the hashmap store delete the key right that's what it is doing and it is returning true if the delete was successful and is returning false if the delete was unsuccessful right and until because he does not exist as simple as that so if key exists we are deleting it and returning true if key does not exist we are returning false because this is what we need to do count plus plus because the return value of delete is the number of keys that are deleted right so we just added over the keys Trigger or delete if the delete was successful we do delete plus plus otherwise we don't increment it there and at the end we just encode and return so return value is an integer with which states the number of keys that are deleted right and now that we have this if I check the encode function because it's an integer just one change I've made over here is we earlier just added in 64. now I added all flavors of integer because count deleted was a simple integer type that's why I've added all flavors of integer over here encoded in the exact same way colon percentage d slash r slash n right and this is how you would be implementing delete operation iterating over all the arguments deleting it from the hash map if deleted count plus plus and at the end written the integer count right now let's see how expired Works expired function sets the expiration first of all we do a basic check on the arguments because we require exactly two arguments over here so if the length of arguments is less than equal to 1 it's an error condition right second is the first argument becomes the key and the second argument you have to convert you have to consider it as an integers of 64 which would be the duration in seconds of expiry right we set it over here in case it is not an integer error would be set so we would can type error value is not an integer out of range this is the exact radius error that it throws then what we are doing is we are getting the key because to set the expiration you have to get the object from the hash map we got the object over here in case the key does not exist in case that object doesn't exist what do we do we return 0.

[00:06:39]because if with expiration if key we saw that if key didn't exist we return 0 right because the operation was unsuccessful we were not able to set so what red is document says that 0 if timeout was not set example key doesn't exist or operation skip due to provided arguments any reason if timeout was unsuccessful a setting timeout was unsuccessful we written zero otherwise we set the expiration so expiration is set to what we store expires at the absolute time at which the key would be expired so it would be time.now.unixmillis plus expiration duration in seconds into 1000 because we store it in milliseconds right and at the end we just return one as an integer response a classic implementation of delete and expire right so this is how delete and expires are implemented so now let's look into how Auto deletion happens we saw how delete is implemented we saw how expired is implemented now let's talk about how Auto deletion would happen because now here up until this implementation we deleted something from the hash table only when the delete command was issued right while getting it we were checking if it is expired we were returning not found right but we did not explicitly delete it so let's see how deletion how redis does key Auto deletion because if you have set an expiry after that expiration time is reached I would want to actually delete the key from the hash table how do we do that that is where let's quickly take a look at how redis expires the key so in redis we can set expiration to the keys by typing expire K 10 expired key and the seconds right now here why do we have to set expiration so that there is no burden for manual deletion you can just set and forget you just set the expression forget your radius would do the cleanup we have to now write that cleanup job so how does that happen so the first intuition that you might think hey it could be another thread that is running but remember red is a single threaded that is where this is such a beautiful implementation so redis expires or radius Auto deletes the key in two modes first is the passive mode so and and the second one is the active mode so first take let's take a look at the passive mode so what passive mode says is that a key is passively expired when some client tries to access it and the key is found to be expired which means that if you are getting an object from the hash table and if that object has some expiration set right and if that key is found to be expired you would be immediately deleting it right so you are accessing an object from the hash table you got that object if the expiration time is already passed then you would be triggering an explicit deletion and then returning null to your user that key does not exist that is a passive word which means that if your expired key is ever accessed if an expired object is ever accessed you are explicitly deleting it problem solved but what about the keys that are never accessed which means a key expiration is set but that key is never get for some reason then key would be lying there only so that is where you have another mode which is an active mode so what active mode does this is a beautiful probabilistic or rather beautiful statistical algorithm that it does now bit of math slight bit of math but very interesting algorithm so here what it does is given that the passive mode of deletion would take care of most the keys like most of the keys that needs to be deleted would be taken care from the passive board right because a key is very likely that you put it in the cache is very likely to be accessed and if that would be deleted so now the keys that are in question are the ones that are never accessed that would not be much right that would not be many keys like this so that is where what active mode does is active mode works with a very simple uh with a very simple statistical theory that if you take a random sample from a population that random sample would represent the distribution of the population right so here if you randomly pick a sample of 20. right if you pick up if you randomly pick a sample of 20 the number of expired keys or the or the percentage of expired keys in this sample of 20 would be very close to the percentage of expired keys in the actual population so that is what it does is redis runs a loop right a simple Loop that executes 10 times every second which means every uh every mile every 100 millisecond it executes it's a timer it's an interrupt that happens we'll see how it is implemented uh 10 times every second it runs what it does is it tests random Keys having some expiration set so out of all the keys that are that you have added in the radius it would pick 20 keys at random whose expiration is set out of those 20 keys that it has picked at random it would see how many keys of them are expired it would first of all delete them if these deleted keys or if this expired keys are more than 25 percent then it would repeat the process right this is what would this is what is going to happen so this would be a continuous process that is running whose job is to pick 20 key or pick 20 keys at random out of these 20 Keys find out how many of them are expired first of all delete them see if these are more than 25 percent if it is which means that if your sample contains more than 25 percent of expired keys not deleted your population would also contain more than 25 percent of keys that are expired but not deleted this is what it plays with right and this is such a beautiful algorithm why because this is not the only way to delete it you are anyway having a passive word which would be doing the mo which would be doing the bulk of the deletion the active mode is only taking care of the keys that are never accessed that are expired but never accessed right so that would not be huge right for a normal generic use case this would not be huge so this is where it plays very beautiful with Place very beautifully with Statistics where it says that if my sample has 25 percent if my sample is more than 25 percent of expired keys that are not deleted my population will also have more than 25 percent of expired Keys which are not deleted so I have to repeat this process now why is it doing so first of all it does not have to iterate through all the keys because that is extremely costly redis is trying to minimize the overhead burden you might think hey let me have another data structure in which I'm keeping all the X expired keys to make it faster or something why to add that extra memory burden redis is already an in-memory database it needs memory to store keys and values not some additional data structures right the second reasoning you can give is hey if I'm not creating another data structure then why can't I just iterate through all the keys that is costly imagine you have million Keys having expiration set of one year or something right why you are wasting time doing that so that is where this quick sampling rate see in most cases the passive mode will do the job right for edge cases where you would have a chance of memory leak you are just playing byte so no additional data structures no additional space requirements just a random sampling testing it and here it does this exactly 20 exactly 20 keys and how does it comes to this number 20 it's normal Central limit theorem right detail like proof of it is a little out of this scope but if you Google it you'll find an amazing resource on it right okay so the 20 Keys it samples out of the 20 it sees how many are expired but not deleted it deletes them and repeats the process if it is more than 25 percent as simple as this right it does not have to go through all this part now where do we put this a normal intuition would say hey let this be a separate thread radius is single threaded you cannot have a separate credit so then how would you do that that is where it's all about structuring the code redis does it in a different way but to make the explanation simpler we would put it in a place that makes it with that makes it very sensible very easy to understand and then I'll tell you how to make it complicated right okay so now let's see how this fits so again we'll do an extremely deep Code walkthrough on CN how would you write an auto deletion so given that this cannot be a separate thread where do we put it the only place where we can put it in our event Loop right the event Loop that we wrote that is where we have to put it the infinite for Loop that is testing that is waiting on e-pole weight just before that we would add it but what's the Frequency all the radius runs it 10 times every second will not run it very frequently let's say we run it at a frequency of at Max or at a frequency of once every second right so I'm setting up a current frequency this could be a configuration if you want to a current frequency of 1 second so time the duration of time one dot second and we would maintain last time when it ran right so let's say last time it ran was now when my server is starting this is exactly the time when it was executed first right so what we can do is in the async server that we have written the gigantic for Loop that we wrote which is where the first thing we would do is execute this Cron where the thing is we would check if time dot now is after your last Quran execution time add cron frequency which means that now that my time so when this Loop would execute when my control flow would come over here it would check that hey is this like is my current time more than last execution plus ground frequency which means if the time if the enough time is passed then I am running this delete expired Keys as a simple crop and then I am setting my last screen execution time equal to time dot now very simple and then our normal flow would work which is which is where we are doing equal weight and reading the events and accepting the connections and doing that part right that would work just fine we are just plugging our logic at the first thing in my in finite for Loop that we are running right so if enough time has passed delete the expired keys under this does not guarantee that it would run exactly once every second every time the control flow would come over here it would run it right a better way now here you can see that you cannot con because it is single threaded it's not separate thread that would run exactly one second after every second it is single thread until and unless my code execution flow does not come over here or my control flow does not come over here this would not execute which is fine which is perfectly fine right there is nothing wrong in it right how redis does it it uses interrupts right and then you can configure a kernel level interrupt and then it would run it not making overly complicated this would work just fine because we are just understanding how single threaded high performance database systems could be built right so now let's see what my delete expired Keys function look like everything else is pretty clear where I am doing time dot now if my time dot now is after last runtime execution plus current frequency then I am triggering this right so now what it would do it is another infinite for Loop in which although I should have had it uh bound it but that fine we are just writing a dummy implementation of it what we are doing is we are writing an infinite follow-up whose job is to do an expired sample right and it is just doing expired sample and getting the fraction if it is fraction is less than 0.25 then break so which means if I have deleted more than 25 percent of the keys which means in my sample if there were more than 25 percent of the keys that were expired but not deleted then I would have to continue otherwise I am breaking the loop right and I'm just printing in the log deleted the X deleted expired but undiluted keys total number of keys which are present right now after the deletion is stored is uh the length of storage which is the length of the hash I'm just printing it for our purpose indeed the deletion has happened right okay so now that delete expired cases set over here now what expired sample does expired sample does this part so what we do is again writing a sampling code versus golang's map iteration is pretty random the order in which a hash map or a or a map of golang is iterated is random depends on the hashing function that it is used so that is where let's assume that iteration of a hash is not in any order but in a random order so what we are doing is because we have a limit of 20 we would be and we can sample 20 keys that are expired that has some expiry set so the flow is I'm hydrating through the hash map right iterating through the hash map if object.expired at is not equal to -1 which means some expiry is set I am doing limit minus minus and if expired at is less than equal to time.now.unix millisecond which means the key is expired already expired I am triggering a delete and I am doing expired count plus plus and if I have found 20 such Keys whose expired is not oh sorry whose expired is set this limit would become 0 I am breaking the loop here right so which means that this Loop would run up until I find 20 such Keys whose expiration is set right and then because expat count would hold the number of keys that have actually deleted then I can just take a fraction of it expired count divided by 20.

[00:20:32]right so if this fraction is less than 25 more less than 25 percent which means less than 0.25 more than say about 0.25 we would be taking up this call right this is the active mode of deletion now you see how it would work right in the single threaded that are we in the event Loop the first thing that we are doing is seeing if my last execution of this cron was before or rather it was done well before which means I I'm well past my current frequency I would trigger this in which I am sampling 20 and say how many of them are expired I am deleting those expired and returning the fraction if this fraction is less than 25 I am breaking the loop otherwise the loop would continue a normal active deletion uh flow would happen like this right now what about passive deletion now here you see the beauty of it that's why we have abstracted the implementation so here if you check the store.go file what we know that every time a file every time a key is accessed we check for the expiration if it is already expired we are deleting it or we have to delete it right so that is where in the get function and which is one of the reason why I didn't expose my hash map literally in my event L5 so that IB can have we can mask this thing over here so in the get function we are getting the value for a particular key if value is not equal to nil which means value exists I am checking the expiration if expiration is less than the time.now.unixmill is then I am deleting the key and returning the which is what would be written over here if the key does not exist if the value exists and it is not expired I am just returning B which means an unexpired key would delete as is if the key is mid to expiration we are act we are passively deleting it right so this is like a lazy deletion right so with this lazy deletion if an key is accessed and found to be expired it's deleted right if key is not expired it is moved forward and then periodically we are running this job which is an active deletion cycle in a single threaded event Loop whose job is to periodically randomly sample 20 keys and see if like see how many of them are expired but not deleted you delete them and once you have deleted it you re repeat the loop until that fraction comes down below 25 percent this is how redis does expiration of keys and this is how you would be implementing or you would be re-implementing it in golang so now let's look at a very quick demonstration of this I am running our server on Port 7379 and now what do we do is I'm just connecting the redis client on closed 7379 here you can see the first output is deleted expat but undiluted keys total key is equal to zero right now I have nothing there were no keys to be deleted the output of this is total number of keys are zero right now let me do a set of key K with value v no expiration set it does okay if I check TTL of K I get minus 1 right because no expiration is set and now what I'm doing is I'm setting expire of e k to value 10 which means in 10 seconds this key would be expired if I checked this here you can see the timer starting and on the on the top you can see total number of keys is one Keys is one case is 1 is a zero right so we did not delete it the loop automatically deleted the particular key and here you can see how my total number of keys are zero right because the loop that we are running its job is to actively delete the keys right why if the key is getting access it would be automatically deleted if it is expired so let's take that as an example as well so let's say I set K comma V do expiry 10 and I am doing normal get here you would see as soon as I'm get doing get get get get and if the key would have expired an m and I would have done a get on it it would start returning me nil so without me accessing it because I'm doing a get of it which means I'm accessing an expired key well I'm accessing a key which is found to be expired it is automatically deleted lazy deletion so passive deletion in action Loop in action and this is how you would be implementing Auto deletion right and now that we are on the topping let's quickly see how we can set expiration of it with all the edge cases at K comma V if I forgot to set expiration I can just do this I can type in let me first do a deletion normal deletion of key K1 K2 K3 K4 I should see Zero because key K1 K2 K3 K4 doesn't exist but key K exists if I do this it returns 0 0 but as soon as I am adding K to it integer is one because one key was deleted right delete functionality working if I do this again output is zero right similarly with expire if I am passing a key that does not exist it would return Me 0 because operation is not completed there was no key to set right but if I do set K comma V and then I set expire at 10 and output is 1 right a classic implementation of delete and uh expire right great we implemented delete expiration saw how radius does Auto deletion active mode passive mode be implemented everything right okay so what's next now here you can see a very nice thing which is pending the nice thing which is pending is although we deleted it right we expired we deleted the keys explicitly by deleting we did order Edition for the keys which are expired but what if because your ready stores everything in Ram what would happen if I'm just inserting Keys bluntly right someday your RAM would get filled what happens when there is no more space to allocate right no like you Runner you are running a malloc but that has no space to allocate something what would happen in that case your program crashes but you don't want your server to crash right because your end user requester will get paid so what do you do a classic cash thing is you do eviction which means that when your cash is full you do eviction so in the next video we would look at how redis does eviction we would Implement a very simple eviction strategy which works on the number of keys will not make it overly complicated we'll just implement it that hey at Max my ready server or our Reds implementation can have let's say five Keys just as an example right and we would see as soon as we are trying to add the sixth key it would evict one and put our the new key that we are trying to insert in it a classic eviction strategy right this is what we would be implementing in the next one I hope you found it amazing that is it for this one I'll see you in the next one thanks