The FIFO algorithm is a simplistic flavor of the LRU algorithm aiming to avoid the drawback of the LRU algorithm at the cost of a little less accurate behavior. Concretely, it will bypass the statistics on the usage and just rely on the time of entry into the cache—a bit like when you are waiting in a supermarket line.
Here is an illustration similar to the one we used to depict the LRU algorithm:
|
Action
|
Cache storage (unsorted)
|
Eviction list (sorted)
|
| - | [] | [] |
| add key/value E1 | [E1] | [E1] |
| add key/value E2 | [E1, E2] | [E1, E2] |
| add key/value E3 | [E1, E2, E3] | [E1, E2, E3] |
| read E2 | [E1, E2, E3] | [E1, E2, E3] |
The main difference here is the last entry, which doesn't impact the eviction order between E2 and ...
