What Happens When Redis Runs Out of Memory

hello Redis community Tel Aviv I was looking forward to meeting you also to enjoy all the hummus and best falafel in the world but most of all I'm looking forward to share some of my knowledge and some of my learnings with you all stuff I find is really interesting I hope you find it really interesting too so what happens when ready strands out of memory in this talk we are going to deep dive into Redis internals and try to understand this is my son there to try to understand the situation of what exactly happens in Redis when it when it's used as a cache when it runs out of memory so first let's understand what is cache cache is a component that stores data so it can be accessed faster in the future ideal cache would always have the data we need and will always delete evict the data that we are not going to request in the future 10 years ago exactly 10 years ago in March 2009 when Redis was first released he didn't have any of these features it didn't know what to delete what to evict what to you know keep therefore the for future requests but developers were still using Redis is a cache even then what they did to maintain a relatively constant amount level of memory was they tried to match the velocity of data going in and out of the system they used to set a TTL a time to live expiration time of every key and hoping that of course expecting that it will expire properly in the in in the time date set but obviously that's a lot of work being left to developers which is something that the server should be handling after all so just a few months after the first release of Freddy's Salvatorian introduced the max memory configuration directive now developers had the possibility to set a max maximum amount of memory that they wanted to use what happened with that when that memory was reached well it was quite simple read this would sample three keys and then it would evict the one with shortest time to live so it would only simple keys that did have time to live set if there weren't any keys like that it would just return an error and that was the first eviction policy implemented in Redis it did it was the default behavior back then but later it would become known as volatile TTL but so I read this question so this is not maybe the optimal way why are we deleting objects if there is no need to and why do we you are we using more memory if we don't need to let's try to look for something else maybe a better and more optimal way to do this LRU cache eviction policy least recently used it is basically an assumption that if we use the key recently we are very likely to use it again soon if we haven't used the key in a long time we are probably not going to use it soon or ever again and with that we have two questions so how are we going to track time how are we going to track one was the that key last used and how are we going to find those keys with longest idle time in our flat key space so this is the ready subject structure sorry this is the ready subject structure in it you can see a field the LRU filled with 24 bits assigned to it that we are using for keeping a track of when was the key last used and you would say 24 bits is very little we cannot track that much what time stamp would take much more but time stamps in Redis are different the LRU clock in Redis doesn't start in the normal epoch it starts when the server will start sorry it starts when the server was started okay I'm going to do the mum thing here okay there we go no it's done mum life so in order to save space the LRU clock of freddy's starts counting time when the server was started that's how in only 24 bits we are able to have a reasonable idea of when was the key last used it overflows only after 194 days and in that time if everything works well that cue should already be expired anyway so that's our first problem soft the next one is how are we going to find how are we going to find the key with the longest idle time in our flat key space and Salvatori said this is a quote since LRU is itself is it's in itself an approximation we are going to try and we don't need to use the perfect solution and find that exactly one key with the longest idle time so the idea he came up with was three random keys simple three random keys and evict the one with the longer highest idle time this was hard-coded in the beginning afterwards it became what we now know as as max memory samples direct directive that was the first LRU eviction policy it came with two flavors all keys and volatile so if you wanted to evict keys among the full keys kiss pace you would select all kids lru volatile LRU it would only affect kiss with a sad time to live and then you would use the LRU eviction policy if you had a normal distribution so you access 20% of the keys in 80% of the time in those cases the LRU eviction would make sense but if you have a normal uniform distribution of accesses then you don't really need to spend all that processing power for that you can just evict randomly so you can use the volatile random or all keys random eviction policies which were added about the same time that the work on LRU had been done with all keys random you would sample you would just evict randomly any key from the full key space with volatile random you would evict keys that have a TTL set and about that time a little bit later there was one more eviction policy added which was needed and requested by the developer community no eviction in that case is bread this was maybe not used as cash or for fraud just it was used as a normal database people didn't want their kids evicted so we got no eviction eviction policy him where yeah just an error would be returned and there wouldn't be any evictions happening so this is our timeline this is how all of this developed more or less and in March 2014 it was time to start thinking about the improving dialer you algorithm another quote from Salvatorian if you look at this algorithm across its executions you can see that we are thrashing a lot of interesting data if you're choosing one key among just three keys the probability of us evicting at good key is quite high so can we improve that somehow he came up with an idea to use a pool of best case so instead of you are getting tree or X random kids every time and evicting one between just those three or X keys we would still be sampling keys but putting all them all of them in a in a pool we would be populating the pool with good candidates in in the end we would be always evicting from the pool itself now let's go into a little bit more of detail how exactly that happens so we would start looping through all the databases and from every database we are going to get X Keys where X is specified in max memory samples for every key we are going to calculate its idle time how are we going to do that idle time order score it's called idle but it's actually a score and I'll explain later why because it's used for lf5 for volatile TTL - so how are we calculated the LRU time the idle time simple just get the current LRU clock and subtract from it the LRU keep time stamp the one in those 24 bits we previously talked about and then that goes in the eviction pool eviction bully the structure of 16 keys ordered from left to right with the lowest idle time to the highest idle time so meaning that the keys towards the end are the best candidates to expire so now for every key we get we start comparing it from the first element and compare it towards the right when we find if if it has smaller idle time than any of this it doesn't ever go in the pool if it if it gets in the pool then we look at the other elements if we have space to the right we shift all the elements to the right if we if we don't we shift all the elements to the left then the last element drops out of the pole it's not going to be a candidate for eviction anymore and then for when so that's populating the pool we do that every time we need to freedom memory for every database so first we populate the pool and then we go to do the eviction once we are sure that we have good candidates in the pool we start from the right going to the left and when we find the element we want to evict we take it out of the of the pool and then we go and evict that element with this approach we got a much better performance of the LRU algorithm here you can see how how it performed in Redis 2 8 well we were just sampling X random Keys with 5 samples and here after the pool was implemented with 5 samples you can see that with 10 samples we are getting very close to the theoretical LRU so with this simple approach we already improved our performance of the LRU algorithm many times and this is how the timeline looked at that moment now in the beginning we didn't have actually cross database cross they cross database eviction every time we needed to evict the keyword just looking in one database but then there was one issue reported that it got a lot of debate a lot of conversation and then what you saw now where we look through all the databases that was implemented in in the in the algorithm and that was about the same time when we also implemented the volatility the eviction pool for volatile TTL to July 2016 and that's also when work on LF you started lfyou is least frequently used ritum I'm not going to talk a lot about it because we have a session about it in about 20 minutes so you're going to learn a lot more about it but I just wanted to say yeah that it's a list frequently used so it's a little bit of a different approach instead of looking at keys that have been used least recently we have big kids that have been used least frequently and I'm going to leave more that in the next the after next session for now I would like to thank you all for your attention and see you next time [Applause]

Channel: Redis

Views: 20,112

Keywords:

Id: W8IEzoxRMz4

Length: 14min 2sec (842 seconds)

Published: Mon Apr 15 2019