LRU Cache implementation with Custom Expiry

This is a LRU(Least Recently Used) Cache implemtation in Go. It is a cache data structure that invalidates cache entries based on the oldest and least fetched entries. It is a widely implemented type of cache commonly used in production where the cache has a fixed size and needs to hold the most requested data. The less "popular" the data is with clients, the more likely it would be invalidated from the cache.

This data structure is implemented using a doubly linked list and a map. It also includes a mutex to prevent unwanted access during write/read operations. When the TTL of a cache entry is reached, the entry is moved to the back/tail of the Doubly linked list. When the capacity of the cache is reached e.g. a cache with a size of 100, the element at the back of the list is removed and the latest entry is set to the front/head of the list.

How to run

To run this project:

1. Clone the repository:

   git clone https://github.com/Prodigy00/lru-cache-with-ttl.git

2. Navigate to the cloned repository directory.
3. Run the Go application:

   go run .

LRU Cache Invalidation Example (Capacity = 3)

This example illustrates the state of the LRU cache using a doubly linked list (where the front is Most Recently Used and the back is Least Recently Used) and a hash map.

Initial State: Cache Empty

• Doubly Linked List: (empty)
• Cache Map: {}

Operation: Set("A", 1)

• "A" is added as the most recently used item.
• Doubly Linked List: [A] (Front: A, Back: A)
• Cache Map: {"A": -> List Element for A}

Operation: Set("B", 2)

• "B" is added as the most recently used item.
• Doubly Linked List: [B] <-> [A] (Front: B, Back: A)
• Cache Map: {"A": -> List Element for A, "B": -> List Element for B}

Operation: Set("C", 3)

• "C" is added as the most recently used item. Capacity (3) is now full.
• Doubly Linked List: [C] <-> [B] <-> [A] (Front: C, Back: A)
• Cache Map: {"A": -> List Element for A, "B": -> List Element for B, "C": -> List Element for C}

Operation: Set("D", 4) - Invalidation!

• "D" is added as the most recently used item.
• The cache capacity is exceeded (current length is 4, capacity is 3).
• The Least Recently Used item, "A" (at the back of the list), is removed.
• Doubly Linked List: [D] <-> [C] <-> [B] (Front: D, Back: B)
• Cache Map: {"B": -> List Element for B, "C": -> List Element for C, "D": -> List Element for D}