# Key Eviction Strategies in Redis and Implementing Simple First Eviction | Redis Internals

## Метаданные

- **Канал:** Arpit Bhayani
- **YouTube:** https://www.youtube.com/watch?v=EkaTFT9ox-I
- **Дата:** 03.05.2026
- **Длительность:** 20:23
- **Просмотры:** 2,253

## Описание

System Design for SDE-2 and above: https://arpitbhayani.me/masterclass
System Design for Beginners: https://arpitbhayani.me/sys-design

Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - https://app.codecrafters.io/join?via=arpitbbhayani

# Recommended videos and playlists

If you liked this video, you will find the following videos and playlists helpful

Redis Internals: https://www.youtube.com/watch?v=h30k7YixrMo&list=PLsdq-3Z1EPT0eElcdOON9fdaeaQjlyXDt
Redis Internals Reading Material: https://docs.google.com/document/d/1lHKI6bia3ZEPoAKgXWIm_SKv_Sii1qtN3EYMEdxKpEQ/edit?tab=t.0

System Design: https://www.youtube.com/watch?v=o7qLKfILuD8&list=PLsdq-3Z1EPT27BuTnJ_trF7BsaTpYLqst
Designing Microservices: https://www.youtube.com/watch?v=JPj6mhVLQN0&list=PLsdq-3Z1EPT0ug8eizS71G6LZb6-4FAFt
Database Engineering: https://www.youtube.com/watch?v=-htbah3eCYg&list=PLsdq-3Z1EPT2C-Da7Jscr7NptGcIZgQ2l&pp=gAQBiAQB
Concurrency In-depth: https://www.youtube.com/watch?v=2PjlaUnrAMQ&list=PLsdq-3Z1EPT3VjDhjMb5yBsgn0wn2-fjp
Research paper dissections: https://www.youtube.com/watch?v=LXhgFAZroG8&list=PLsdq-3Z1EPT2XEJ0AmF02LBK1RFNd-jK8
Outage Dissections: https://www.youtube.com/watch?v=LeT_s-UFw-U&list=PLsdq-3Z1EPT3_Z97svMs6S2y7tv1PcUmc

Hash Table Internals: https://www.youtube.com/watch?v=jjW8w8ED3Ns&list=PLsdq-3Z1EPT2UnueESBLReaVSLIo_BuAc
Bittorrent Internals: https://www.youtube.com/watch?v=v7cR0ZolaUA&list=PLsdq-3Z1EPT1rNeq2GXpnivaWINnOaCd0

# Things you will find amusing

Bookshelf: https://arpitbhayani.me/bookshelf
Papershelf: https://arpitbhayani.me/papershelf

# Other socials

I keep writing and sharing my practical experience and learnings every day, so if you resonate, then follow along. I keep it no fluff.

LinkedIn: https://linkedin.com/in/arpitbhayani
Twitter: https://twitter.com/arpit_bhayani

Thank you for watching and supporting! It means a ton.

I am on a mission to bring out the best engineering stories from around the world and make you all fall in love with engineering. If you resonate with this, then follow along. I always keep it no-fluff.

## Содержание

### [0:00](https://www.youtube.com/watch?v=EkaTFT9ox-I) Segment 1 (00:00 - 05:00)

so in the previous video we implemented delete expire and saw how Auto deletion would happen or rather Auto expiration would happen right and in this one we would look at eviction so why does a database like redis needs eviction because all the keys that you put in redis are stored in memory right because Ram is limited what we would want to ensure is that when we hit a certain limit then we cannot because we cannot go beyond that because our Ram would be full and now let's say uh if you insert a large amount of keys and if there is not enough RAM to allocate what would happen your process would crash right and you don't want your database to crash because of om which is out of memory error right so what do you do that's where you do eviction so for example hypothetically let's say we have a limit of 1 GB right and if we have exhausted that 1GB limit and if we are trying to set a new key we should do something with that right so which is where we have different eviction strategies right which is what we would be looking at this one right so how does ready service so first now we know uh that why do we need eviction right and now in this we'll see how radius evits so redis has a configuration parameter called max memory in which it says that hey you can configure it in the main redis. com file saying that hey my max memory consumption should be 1GB so it would not let it go beyond that right and when redis hits that particular limit it evicts some of the old data and there could be multiple strategies to evict right and depending on the configured strategy that you have it would do the eviction so depending on which strategy you put in it would try to find the best key that it can evict and it would throw it out to make a space for the new one so in this one we would first take a look at all possible ways that redis supports eviction of keys and then we would be implementing an extremely simple out of the box simple first eviction strategy it's not part of redis but just to understand it and how we would place our code in our own radius implementation just as a quick example of that we would Implement a very simple first eviction strategy right so first let's take a look at different eviction strategies and different performance optimizations that comes with it first strategy is called No eviction implies that when your radius hits the max memory limit we would not evict so after hitting the max memory limit if we try to put something in redis that new value that is being written will not be written so you would be discarding the incoming rights that are happening that is your no eviction strategy or no eviction policy second one is all keys lru is a very famous least recently used strategy that you have studied that you might have heard of a Toyota operating system because it's a very common cash eviction strategy so what alario says is that I would evict the key that is least recently used so it goes by the saying that if my key is not recently used it should be safe for me to evict that so if a k is not accessed in let's say last three hours there are very less chances of that to be accessed again if that is what your behavior is going to be you can configure all keys and are you so what it would do is it would have to maintain some way to find when a key was recently used and then it would be evicting the one that is least recently used second uh sorry the third one is all keys lfu stands for least frequently used so along with each of the key that you have put in it would maintain a frequency count that how many times was this key accessed and when it comes to eviction I would evade the key that was least frequently used because if it is least frequently used so you would be like this strategy would come in handy when you would want to evict a key that is least frequently used which means if a key is very less frequently used it is highly unlikely for me to access it again that is when you would adopt a least frequently used another strategy is volatile lru it's same as lru but instead of considering all keys volatile lru considers Keys having some expiration set which means it would keep the keys having no expiration set as is so those keys would not be evicted there are so many use case for that let's say if you want to put a key permanently in your radius and you don't want it to be evicted even if your cache is full this is where it comes in handy because all keys lru would be evicting the key irrespective expiration is set or not but volatile lru will be deleting volatile Keys which means keys on which some expiration is set and it would find the least recently used out of it and

### [5:00](https://www.youtube.com/watch?v=EkaTFT9ox-I&t=300s) Segment 2 (05:00 - 10:00)

would be evicting it then comes volatile lfu similar to lfu but instead of considering all the keys we are considering Keys having some expiration set right then the my personal favorite is all keys random now this random eviction strategy is very interesting so it would pick some keys at random and evict it no lru no lfu nothing so what it does is what it says is that hey let me just like if my cache is full let me just evict one key at random and you'd see why would you want to do that like you might be evicting a key that might just be used yeah it's true but you don't need additional data structures to manage which is the least recently used or least frequently used no extra data structure overhead just picking one key at random and evicting it you would be using this strategy when you have uniform access across all the keys if you know that your access is going to be uniform across all the keys all keys allow all keys are random or volatile random works really well by the way volatile random again all key random but with the keys that has some expiration set right and the final one is volatile TTL which means that it would pick a key that has the shortest time to leave which means the keys that is about to be expired it would be evicted very interesting strategies that you would see with redis now let's go deeper on how red is actually Implement cell Ru so that is where because if you think about it implementing lru you would have studied in a data structures course like you would require a doubly linked list and all but ready say I don't want to have extra memory overhead so what redis does is redis does approximated lru and it was introduced in radius version 3. 0 what approximated error does is that it is not an exact algorithm it means that it is approximated which means that it would not evict the best possible candidate but it would do a decent job at it so the core idea is sample sampling works the best here you see when it where it comes to approximation we are relying on sampling so you sample some of the keys and from them you pick the one that is least recently used right maybe with each key you are storing hey when was it last accessed and when you are sampling a bunch of keys to be evicted out of that pick the one that is least recently used that's a core idea you don't need to maintain additional data structure you are just sampling a bunch of keys and applying lro on top of it such a simple elegant very memory efficient implementation right but why redis does not use exactly are you because just imagine the amount of extra memory that it would require to maintain the data structure just imagine maintaining a doubly linked list to maintain accesses across which Keys was accessed when and then evicting from one so much of memory overhead redis would choose to use that extra memory to store the data rather than managing pointers that's why caches to be extremely efficient they don't rely on additional data structures at all they rely on sampling they rely on approximation right so in approximated lru what we do is instead of taking just one sample of K Keys We Pick N samples having K Keys now both of them are configurable right so if we take n samples each having K keys and out of that we pick the ones the one that is least recently used so this way if you were just picking one sample of let's say 5 or 10 keys right and then you would be doing least recently use out of it you might still evict the best like you might still not having the best one but if you are taking multiple samples like this you are increasing your chances to be as close to actual lru the best case lru as possible so this is the power of sampling so these configurations are con sorry these parameters are configurable so you can check the radius. com file to see these parameters in action but these are such interesting amazing cost efficient space efficient algorithms that you would love to explore right okay then if we would configure lfu like we saw a volatile LFE and all keys lfu right how it is implemented so lfu mode the new LFE mode was introduced in redis 4. 0 and this is again very interesting part very interesting algorithm so you say hey what's so interesting in managing frequency I'll just have a key and I'll just set up frequency variable to that and I'll do plus every time it is accessed but think about it every single key in redis for that you are having an integer and that integer you can store a million value in that right so up to a million range like zero to one million it would require four bytes imagine four bytes across all the keys you are wasting so much of space can you do it better this is where this approximation comes in so what it does is it

### [10:00](https://www.youtube.com/watch?v=EkaTFT9ox-I&t=600s) Segment 3 (10:00 - 15:00)

uses something called as a Morris counter it does not use normal lint plus because if it would be using it plus it means for every kit would require additional four bytes to just store this frequency now the idea is can you because redis has to be space efficient can you approximate your accounting so for example if I want to represent 1 million why do I require for basically four byte integer can I not do it with a shorter integer and can I not be extremely space efficient when I'm doing that this is where Morris counter comes in it's an extremely simple but mind-blowing implementation of an approximate counter so this is where your Advanced data structures part comes in and modest counter is a classic classic example of approximate data structure I have written a very exhaustive block on internals of Maurice counter back in 2020 I would highly encourage you to read that it's present at arpit by any dot me slash blog slash Morris counter read that in case you are interested on how probabilistic data structures are built so for you to store a million value 1 million as a value one million as an integer you'll not require four bytes you can do it with two or three and that's the magic behind it every byte saved with redis you can use it to store additional data because just imagine the overhead of storing forward integer with every key in most cases you might be just storing pennies like two value three four ten value can you not be extremely space efficient there this is where Morris counter comes in right and just to cover one part where would you use lfu the key idea behind using lfu you would use lfu when even if you see a dip in the axis of a particular key let's say this is an access pattern of a key it is and this is the height of it shows the frequency of access even if it is not frequently accessed but you still want to hold it that is where you would be using lfu so this is like a stock market even if a stock is down because you believe in it that this sometime in the future it would give me the return that's why you're still holding it that same analogy you can apply over here so in case you have a use case where you are willing to take that bet that even if this key because it was frequently used earlier even if right now there is not much usage on it I would still want to hold it that's why you would use the left View right and what Morris although we studied like hey it's a modest counter we are using to do approximate counting but what if your keys never accessed again would you still want to keep it in memory no so that is her what do you do is your frequency has a cap let's say a million it caps at a millennium counter caps at a million so at Max it can go to 1 million and then every minute there would be Decay with it there would be a logarithmic Decay you can find details of it it's simple logarithmic Decay function that you would find it in the documentation like a lot of math involved there that's why not covering it but the idea is this Decay is that every minute the value of this counter would be decaying so that if even if we are having if we see large frequent access of that particular key but if you are not seeing frequent access over a large duration the value would be reducing to zero eventually it making it eligible for eviction so that is where your counter saturates at million and then Decay and the value is decade every one minute this is the default configuration obviously you can configure it in the redis. com file right this is the theory behind different eviction strategies two very critical approximated algorithmic implementation of lru and lfu right again highly encouraging you to see the internal working of Maurice counter back in 2020 I've already written a very detailed blog audit I went through the research paper understood it in depth and with very illustrations mathematical explanation everything it's there on my website do check that out now that we have this part let's say we Implement something extremely simple just for us to understand where this code would be placed in our repository right so here I have our classic implementation like always now here what I'm doing is I'm creating I'm writing a an extremely simple key eviction algorithm called simple first right what we would do is whenever our cache is full we would be evicting the first key that we find right because we just are creating this low level structure because implementing lru and lfu and all of that with exactly how radius does is too hectic not a lot of you might be interested into that that's why we're just keeping it simple to just see where would we place our code you can make it as complex as you want Implement lru lfu approximated lru

### [15:00](https://www.youtube.com/watch?v=EkaTFT9ox-I&t=900s) Segment 4 (15:00 - 20:00)

approximated lfu and whatnot right but we are just keeping it simple to for now Implement a simple first eviction strategy right so what we would do is we would start with the store file and in the store file the first thing that we would do is first of all when we would want to so first of all we need to decide that when we would be triggering an eviction right so comes as a fact that when I'm hitting a limit what kind of limit reduce does max memory right for us to estimate how much memory we are requiring it's a little hectic so can we do something simpler let's say I put a limit on the number of keys that we have right so let's say I take in as a config that at Max my cache has my cash could hold at Max 5 keys not more than that right so let's say in this key limit I am storing key limit to be 5. so this is just a demonstration purpose right so let's say if I'm doing this and I'm storing my key limit as 5 which means at Max my cash would hold five you can change it to 5005 million whatever you want to like you can also change it to memory right but that's where you would have to keep track of every time you're allocating the memory what is the size of the object and then you would be keeping track of it right but just to even establish a low level code a simple low level code we can just write a simple first eviction thing which works on maximum keys that we can store right so if lenov store so while putting a key in the hash table that we have if the line of store is greater than equal to case limit we evict one right so this is where we are triggering our eviction and then we are storing the key or storing the newly key and object mapping in our hash table right this is where we are triggering it and what is written in evict we are returning or we are invoking the evict first strategy as a future extension we can support multiple Aviation strategies as we just saw lru lfu volatile error volatile lfu but no need of implementing it we are just adding it adding them as placeholder right now implementing the simple first eviction strategy right so what we are invoking is evict first what evict first would do sorry is that it is just iterating through my store deleting the first key that is fighting and returning it simple so we are just iterating over the hash table the first key that we find we're triggering a delete of it and returning it this way whenever we are hitting a limit we are simply a big ticket and once eviction is done I have one place free and I am putting my new key there right a very simple eviction first like first key that we iterate we are evicting it right extremely simple implementation right let's see this in action just to ensure that everything is working just fine right so here on I don't think we need normal ready server for this because we cannot mimic eviction at a large scale so what I'm doing is I'm just running my register or already supplementation per se which is running on Port 7379 connecting it over through our classic red is CLI now I've collected it I am doing a set K1 V1 then I'm doing a set K2 V1 k3v1 K4 sorry k5b1 I've added and K4 V1 so I have K1 K2 K3 k for K5 on the top you can see the total number of keys that you have are 5 here right and now what would happen if I had k6 to that the total keys are still 5 because it triggered eviction in the end my number of keys are capped over there it would have evicted one of this key at random right and the first one that it could iterate to and it is obviously not in a particular order it depends on the hash key but it would be deleting the first one that it encounters while iterating and then it would be evicting it making space for k6 K7 K8 and if you look at this the total keys are limited to five obviously this is not a production grade database we are mimicking it but at least what we know is how to structure where to put our code and now you can make it as complicated as you want simple as you want right so just add more eviction strategies because all we have to do is just add those particular counters add those particular last access time and whatnot so that you can very well do this lru lfu like implementation if you want to do that right and that is it for this one what we'll do in the next one so we saw Auto expiration we saw eviction now what next the most interesting like one of the most interesting features of it is pipeline right so in the next video we would look at pipelining where from our client we can pass in multiple commands and redis would compute all of them and

### [20:00](https://www.youtube.com/watch?v=EkaTFT9ox-I&t=1200s) Segment 5 (20:00 - 20:00)

return result in one shot it's not request and response instead we get a large number of commands together and then we would be Computing them buffering the results and sending the results in one shot this is what we would be implementing in the next one so yeah that is it for this one I hope you like this I'll see you in the next one thanks again

---
*Источник: https://ekstraktznaniy.ru/video/49980*