LRU implementation

This entry is part of the group of entries where we will implement and
understand a distribute cache. Today is the turn of the first piece of our awesome cache :D

Cache algorithm

First things first, What the heck is a cache algorithm?, basically a cache algorithm has the
logic for storing the data. Nothing more, nothing less, it's simple. there are
a lot of cache algorithms. The selection for this system is LRU

LRU

LRU (least recently used) is a cache algorithm, the name explains by its own,
LRU discards the least used data, this means that when the memory
of the cache is full, the cache will need to remove "items" from the cache and
when this happens LRU says that the least used "items" will be deleted from memory
in order to have space for the ones that are most used. A picture is worth a thousand words:

LRU flow

Implementation

The best way to learn thins is by practicing them... enough of chit chat and
lets dive in to the marvelous world of caches and Pythons!

First we need to create the body for our container class:

As we see a cache or container will have 4 basic methods. Well with set, get and
remove would be perfect too.

The first thing that we need are the elements where the data will be stored and
keep track of them. For this we will use a dictionary (key/value) where the data
will be identified by key. To keep track of the scoring of the "items" we will
use a double linked list, the order of the list will show us which items are the
most used (most used at the front of the list, least used at the rear of the list)
and of course the max items that the cache can store:

We have all the requirements to build our cache, so lets
add the adding elements logic.

When we add an element to the cache, we add in the
front of the list (we put the element in front of the list when we have a hit in the cache)
after inserting the item/element we check if the cache is full, in that case the last
element is removed, if you take a look you can see that only one element is removed,
that is because we look every time we insert one, this means that in the worst case
the cache will have only one more element that its max element threshold.

The getter is also very simple. First we look if we have the element, in the case
that the element isn't in the cache we return nothing, but if we have it (that's a hit!),
the element is moved to the front of the list, this is the most important thing
of the LRU algorithm, by doing this, the most used ones are sorting in the front
positions of the list and the least used stay in the back, so in each getter and setter
of data in the cache we are sorting by "use". As the final part we return the
element

And that's it, once we have undestood the algorithm, we realize that is pretty simple. This type of
cache is very powerful and is commonly used in many important projects like
Redis, Memcached or Groupcache

Here is all the code as one block:

The next part is the hashing algorithm (one of the funniest part) [To be updated]