Implementing LRUCache in Golang

Cache: The more the data grows, the more the data database transactions grow, and the importance of cache grows.

Introduction

While scaling our microservices, we might have a question about whether we should implement caching mechanisms or optimize our database layers. Both have their own pros and cons depending upon our requirements and architecture. In this article, we would mainly be discussing caching and implementing simplistic LRUCache.

Implementing a caching mechanism or cache store helps us reducing the load on our database engines (indirectly saving us some money as well!!)

Why caching?

Even though horizontally scaling the application would add more resources and allow the database to serve our API requests. However, we would reach a certain point where the database can’t handle the request traffic.

On an API level, we can add multiple optimizations like pagination, database pooling, CQRS (Command-Query Request Segregation), caching as per our requirements.

There are many implementations of caches readily available,

• Redis
• Memcached
• Hazelcast

We would be discussing an in-memory cache abstraction i.e. LRUCache (Least Recently Used Cache)

Implementation

Let’s start by defining the structure of our cache.

KeyValue Pair

LRUCache struct

LRUCache:

• Capacity: Number of elements that can be stored in the cache.
• List: DoublyLinkedList for storing the cache values using container/list provided by go packages.
• Elements: Map to store the keys and pointer to the values stored in the list.

We would be defining the below methods for our cache.

1. Get
2. Put
3. Keys
4. Remove
5. Purge

Get

As the cache stores the values in a map with keys and values stored in a list.

We check whether our key is present in the map, return the value stored in the list for the key or return -1.

While returning the value, we also move it to the front of the list to maintain the logic of least recently used.

Get

Put

Storing the values in cache follows the below steps:

• If the key is found in the cache, move it to the front of the list and store the new value.
• Else, check the current capacity of the cache, in case of overflowing we remove the back entry from the list.
• Store the new element at the front of the list.

As the above steps suggest while checking the capacity we remove the back element from the cache, which defines our use case of least recently used.

Put

RecentlyUsed

Returns the value from the front of the list.

RecentlyUsed

Remove

Here we check whether the cache consists of the key intended to be removed, if found we remove the key from the list.

Remove

With this, we have completed our definition for all our methods required for our LRUCache implementation.

Code related to the implementation is available here