Implementing LRU cache in PHP

“Least Recently Used” is a practical caching technique that holds frequently accessed data and discards unused items.

.com software
Dev Genius
Published in
3 min readAug 14, 2022

Photo by Andrey Sizov on Unsplash

The LRU cache is a Cache replacement policy, one of many, which:

are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones

The definition

It’s a cache strategy that holds items of a finite amount. When the cache is full and you try to insert another cache item, it should remove the “least used cache” item to make room for the newcomer.

LRU cache use-case

LRU cache algorithm increases code execution efficiency by caching frequently used data. The cache size limit reduces memory usage to a sensible amount. This strategy is useful for long-running processes handling large quantities of data.

How the LRU cache works

Imagine an empty cache for five numbers. Initially, it is empty:

Five empty cells in the cache

As we insert new numbers they are appended to the cache. When we insert 4 the cache looks like follows:

Number “4” in the first cell

Then we insert 8. This element is not yet in the cache so it goes to the front:

Numbers “8” and “4” in the first two cells

Then, we subsequently insert 15, then 16 and 23. Number 4 becomes the “least used element”.

Numbers “23”, “16”, “15”, “8” and “4” in all five cells

This is the time when things start to get interesting. We would like to add another number to the list 42. Since only five numbers are allowed, we remove the “least used number” and prepend the number to the list. The new “least used number” is 8:

Numbers “42”, “23”, “16”, “15” and “8” in all five cells

Now we would like to request number 8 from the cache. The number is in the list so it is pushed to the front of the list. The new “least used number” is 15:

Numbers “8”, “42”, “23”, “16” and “15” in all five cells

PHP implementation

We should begin with an interface. It will be annotated with generics to:

  • properly resolve variable types in PHPStorm
  • allow strict code validation for tools like Psalm/PHPStan

The interface

Interface for the cache

The implementation

Solid implementation in PHP

Example usage

Example task processing with User cache limited to 50 users

Any doubts? Thoughts? Please leave me a comment on what you think. Let’s together make our code beautiful. Subscribe to my publications for more articles like this to become a better developer.

Was this story of any value to you? Please support my work by leaving a 👏 clap as a token of appreciation. Did you know that you can clap more than once? 🥰 Thank You.

Published in Dev Genius

Coding, Tutorials, News, UX, UI and much more related to development

Written by .com software

Father • PHP developer • entrepreneur • working for a €1bn unicorn startup as a backend engineer >>> https://bit.ly/dotcom-software

Responses (2)

What are your thoughts?

Simple, powerful, perfect!

--

In the moveToFront method, I think we can also use the array_unshift function to make the incoming item moving to the front :).

--