Cache eviction policy in Java— Part 1 of 5 — FIFO

A long time ago in a talk with a technical guy …..

I was asked how to design a cache algorithm and after looking into the brain the options available don’t fit in as a good answer.

After looking for some answers and going deep to this subject now I’m able to explain some Cache eviction in Java and some approaches.

In order to avoid TL;DR; the article will be divided in 5 parts with FIFO, LIFO, LFU, LRU and MRU.

Assumptions

The list must store at a maximum of 3 elements and the cache starts always with 3 players, Coutinho, Neto, and Messi all FCB’s ⚽️ players.

FIFO

The First In First Out algorithm stores the first item into the head of the list and last on the tail and the head is the element to leave the list.

In Java is possible to use LinkedList /ConcurrentLinkedDeque or even do by yourself 😃.

Using the picture below as an example is possibleto see how the FIFO algorithm works.

How to read the picture?

Index → Index of the list

Player → Object stored into the list

# Number -Add → New object to be added into the list

As expected, at the end of the list the players ter Stegen, Ronaldinho, and Messi are on the list.

Where I could use this kind of cache?

This algorithm is used if the use of an element makes it less likely to be used in the future[1].

Code

This is the constructor of the Fifo Cache. By default the accessor order is false. The logic to remove the element is inside the method removeEldestEntry.

❗️Remember → The cache list doesn’t need have a huge size, cache is used to be fast and few elements.

The test for it is based on list size and elements, and the asserts are made upon that.

Code

The code is available on my GitHub.

Next

The next subject will be LIFO.

References

[1] https://www.ehcache.org/documentation/2.8/apis/cache-eviction-algorithms.html

[2] https://github.com/luizgustavocosta/luiz-costa-tech/tree/master/cache-eviction-policies