LRU Cache

I hope you have worked with cache or know the use of it. Let’s design an LRU cache using OOPs and principles from scratch keeping the design extensible. After going through this article you should be confident enough to create any type of Cache design.

Try to implement it in your favorite IDE in parallel because nothing can match practical experience.

Requirements

• Design a cache system that can store and retrieve a single key-value pair.

• The cache should have a fixed capacity and follow the principle of the Least Recently Used (LRU) eviction policy.

• The system should allow efficient access to the most recently accessed key-value pair while ensuring the cache does not exceed its capacity.

• Implement methods to insert a key-value pair, retrieve the value associated with a given key, and handle cache evictions when the capacity is reached.

• Optimize the design for fast read and write operations.

Credits: The problem is taken from EngineBogie

Companies: Tekion Corp, Adobe, Tata 1mg, Salesforce, Amazon, UiPath, Walmart Global Tech India, Meta, Microsoft, Confluent, ThoughtSpot, Goldman Sachs, Kutumb

Understanding the requirements properly

1. Single key-value pair

   • The Key must be of data type String only

   • The cache can store values as List, Set, etc. Examples are shown below.

      {
          "key": "value" // valid
          "key": ["value1", "value2", "value3"] // valid
      }

2. Eviction Policy

• If we want to store a new pair in the cache once it is full, we must remove one pair from the cache and store the new pair. The removal of the pair must be based on the eviction policy.

• Yes, we must be able to support multiple eviction policies

3. Capacity

• The # of elements that can be stored in the cache. If we have to store new elements then we will have to use an eviction policy and remove the element from storage and store the new element.

4. Store and Retrieve values

• Store key value and update the access order if required.

• If the “key“ is already present in the cache then the corresponding value will be replaced with the new value.

• If “key“ is present return the value.

• Return null if the key is not present

5. Optimize for Read-Write operations

• We should be able to support both at O(1) time complexity.

At this point, we should be very clear that we are going to create low-level designs only for these requirements. Do not think of Multi-threading although check the expectations from the interviewer. They will just make the design more complex, and we will not be able to complete it.

Note: It is important to understand the thought process behind the design. If we are not clear about design choices then we will not be able to say which design is better or we will not be able to justify our solution. Hence, do not remember the design instead design with the tools you have.

Let’s Begin

Design

1. Core Classes

• At this point, I am not thinking of an eviction policy. I want to have a skeleton first and then include the policy.

    // We are clear that we need capacity, storage and eviction policy
    class Cache {
        private final Integer CAPACITY;
        private final Map<String, Object> storage;
        private final LruEvictionPolicy evictionPolicy;

        public Cache(Integer CAPACITY, LruEvictionPolicy evictionPolicy) {
            this.CAPACITY = CAPACITY;
            this.storage = new HashMap<>();
            this.evictionPolicy = evictionPolicy;
        }
    }

    // Not sure about the properties. Let us move on and figure out later
    class LruEvictionPolicy {
    }

    // Used to interact with Cache class
    class Driver {
        public static void main(String[] args) {
            Cache cache = new Cache(2, new LruEvictionPolicy()); // a cache of size 2
        }   
    }

2. Store the key-value in the cache

class Driver {
    public static void main(String[] args) {
        Cache cache = new Cache(2, new LruEvictionPolicy()); // a cache of size 2
        cache.put("1", "One"); // Store key "1" having value "One"
    }
}

class Cache {
    private final Integer CAPACITY;
    private final Map<String, Object> storage;
    private final LruEvictionPolicy evictionPolicy;

    // Constructor

    // New method
    public void put(String key, Object value) {
        storage.put(key, value);
    }
}

Is this correct?

• No, because we aren’t using CAPACITY and eviction policy

    public void put(String key, Object value) {
        if (storage.size() < CAPACITY) {
            storage.put(key, value);    
        }
    }

How about now?

• We aren’t using an eviction policy (Let us park this and see what problems we face)

• What happens if the storage is full? We should be able to evict a key-value pair from the cache and store the new key-value pair.

• We are designing for LRU cache hence the Least-Recently-Used key must be evicted.

• If we want to evict the LRU key then, we must store the order in which the key is accessed somewhere right?

• Just do not overthink, we can do this using LinkedList right?

class Cache {
    private final Integer CAPACITY;
    private final Map<String, Object> storage;
    private final LruEvictionPolicy evictionPolicy;
    private final LinkedList<String> accessOrder; // Store key access order

    public Cache(Integer CAPACITY, LruEvictionPolicy evictionPolicy) {
        this.CAPACITY = CAPACITY;
        this.storage = new HashMap<>();
        this.evictionPolicy = evictionPolicy;
        this.accessOrder = new LinkedList<>();
    }

    public void put(String key, Object value) {
        // Remove the LRU key
        if (storage.size() >= CAPACITY) {
            String firstKey = accessOrder.getFirst();
            accessOrder.removeFirst();
            storage.remove(firstKey);
        }

        // If key is already present in storage remove the key from access order list
        // and add it at the end of the list
        if (storage.containsKey(key)) {
            accessOrder.remove(key);
        }

        // Store the key in accessOrder and key-value in the storage
        storage.put(key, value);
        accessOrder.add(key);
    }
}

// Not used yet
class LruEvictionPolicy {
}

class Driver {
    public static void main(String[] args) {
        Cache cache = new Cache(2, new LruEvictionPolicy()); // a cache of size 2
        cache.put("1", "One"); // Store key "1" having value "One"
    }   
}

Could you think of problems in the above design? We achieved what is required but still, there are issues.

• Well, I can think of the below:

  • Eviction Policy is not used

  • put() method breaks the SRP principle

• The Eviction Policy must be responsible for evicting the key when capacity is full

Well, let us move the responsibility to the Eviction Policy class and update the Cache class accordingly.

class Cache {
    private final Integer CAPACITY;
    private final Map<String, Object> storage;
    private final LruEvictionPolicy evictionPolicy;

    public Cache(Integer CAPACITY, LruEvictionPolicy evictionPolicy) {
        this.CAPACITY = CAPACITY;
        this.storage = new HashMap<>();
        this.evictionPolicy = evictionPolicy;
        this.accessOrder = new LinkedList<>();
    }

    public void put(String key, Object value) {
        if (storage.size() >= CAPACITY) {
            evictionPolicy.evict(storage);
        }

        storage.put(key, value);
        evictionPolicy.recordAccess(key);
    }
}

class LruEvictionPolicy {
    private final LinkedList<String> accessOrder;

    public LruEvictionPolicy() {
        this.accessOrder = new LinkedList<>();
    }

    // LRU key will be present at first index
    // Remove the key-value pair from the storage as well
    public void evict(Map<String, Object> storage) {
        String firstKey = accessOrder.getFirst();
        accessOrder.removeFirst();
        storage.remove(firstKey);
    }

    // Key will be removed and added at the end. 
    public void recordAccess(String key) {
        accessOrder.remove(key);
        accessOrder.add(key);
    }
}

3. Get the stored value from the cache

class Cache {
    private final Integer CAPACITY;
    private final Map<String, Object> storage;
    private final LruEvictionPolicy evictionPolicy;

    public Cache(Integer CAPACITY, LruEvictionPolicy evictionPolicy) {
        this.CAPACITY = CAPACITY;
        this.storage = new HashMap<>();
        this.evictionPolicy = evictionPolicy;
    }

    public void put(String key, Object value) {
        if (storage.size() >= CAPACITY) {
            evictionPolicy.evict(storage);
        }

        storage.put(key, value);
        evictionPolicy.recordAccess(key);
    }

    // Get the value stored against key
    public Object get(String key) {
        Object value = storage.get(key);

        // Update access order if key is present
        if (value != null) {
            evictionPolicy.recordAccess(key);    
        }

        return value;
    }
}

class LruEvictionPolicy {
    private final LinkedList<String> accessOrder;

    public LruEvictionPolicy() {
        this.accessOrder = new LinkedList<>();
    }

    public void evict(Map<String, Object> storage) {
        String firstKey = accessOrder.getFirst();
        accessOrder.removeFirst();
        storage.remove(firstKey);
    }

    public void recordAccess(String key) {
        accessOrder.remove(key);
        accessOrder.add(key);
    }
}

class Driver {
    public static void main(String[] args) {
        Cache cache = new Cache(2, new LruEvictionPolicy()); // a cache of size 2
        cache.put("1", "One"); // Store key "1" having value "One"
        cache.get("1"); // returns "One"
        cache.get("0"); // returns null
    }   
}

The design looks perfect, isn’t it?

Now the fun begins, let us analyze the design carefully for extensibility.

Analysis of the design

Starting from the Cache class

1. Capacity

• The Cache can store any # of key values based on this. This is already handled.

• One edge case, do we allow a Cache of capacity “0“

2. Storage

• We have used Map but this could be DB storage, Redis, or any other type of storage. If we change this according to our needs then we will break OCP because we need to update the Cache class

• This breaks DIP. The cache is directly dependent on Map we must depend on the contract/interface.

• Let us fix this first.

• How?

  • Using interface as the contract

  • The new storage will adhere to this contract when implementing

    interface Storage {
        void put(String key, Object value);
        Object get(String key);
        void remove(String key);
        int getSize();
    }

    class MapStorage implements Storage {
        private final Map<String, Object> storage;

        public MapStorage() {
            this.storage = new HashMap<>();
        }

        @Override
        public void put(String key, Object value) {
            storage.put(key, value);
        }

        @Override
        public Object get(String key) {
            return storage.get(key);
        }

        @Override
        public void remove(String key) {
            storage.remove(key);
        }

        @Override
        public int getSize() {
            return storage.size();
        }
    }

Let us use this MapStorage in the Cache class

•             class Cache {
                  //...
                  private final Storage storage; // Changed from Map to Storage
  
                  // Initialize Storage as well
                  public Cache(Integer CAPACITY, LruEvictionPolicy evictionPolicy, Storage storage) {
                      //...
                      this.storage = storage;
                  }
  
                  public void put(String key, Object value) {
                      if (storage.getSize() >= CAPACITY) { // get size of storage: getSize()
                          evictionPolicy.evict(storage);
                      }
                      //...
                  }
  
                  // get() method
              }
  
              class LruEvictionPolicy {
                  //..
  
                  // Update the parameter type from Map to Storage
                  public void evict(Storage storage) {
                      String firstKey = accessOrder.getFirst();
                      accessOrder.removeFirst();
                      storage.remove(firstKey);
                  }
  
                  //..
              }
  
              class Driver {
                  public static void main(String[] args) {
                      Cache cache = new Cache(2, 
                                      new LruEvictionPolicy(), 
                                      new MapStorage());
                      //...
                  }   
              }
  

  This design allows us to inject any other storage type that will adhere to the Storage contract.

• Let us move to the next attribute in the Cache class

3. EvictionPolicy

• We will break OCP if we need a different eviction policy because we will have to update the Cache class from time to time to use different policies.

• This also breaks DIP - Depends on LruEvictionPolicy instead of interface

• Solution: Create an interface called EvictionPolicy

interface EvictionPolicy {
    void evict(Storage storage);
    void recordAccess(String key);
}

// No changes to implementation. We just implemented the "EvictionPolicy"
class LruEvictionPolicy implements EvictionPolicy {
    //..

    public void evict(Storage storage) {
        //..
    }

    public void recordAccess(String key) {
        //..
    }
}

Let us use this interface in the Cache class

class Cache {
    //..

    // Changed type from LruEvictionPolicy to EvictionPolicy
    private final EvictionPolicy evictionPolicy;

    // Change parameter type to EvictionPolicy
    public Cache(Integer CAPACITY, EvictionPolicy evictionPolicy, Storage storage) {
        this.CAPACITY = CAPACITY;
        this.storage = storage;
        this.evictionPolicy = evictionPolicy;
    }

    //..
}

This solution allows us to choose any eviction policy for the cache. It can be FIFO, LFU, Rando, etc. The new policy introduced must implement the EvictionPolicy interface

Congratulations!!!

If you have made it this far by understanding everything then pat your back. Trust me it is not so easy.

Hey, are you still curious about the other problems then, let us move ahead?

I’ll try to explain the problems but will leave it to you to code the solution.

Other Problems

1. One major thing that a cache must support is multiple data types as keys. If you look at the Cache class then String is used as a key that is hardcoded and we need to update this whenever we need Integer it as a key that breaks the OCP principle. We can use Java’s generics and make it flexible.

2. Keys storage can break OCP and DIP

   • The LruEvictionPolicy class has 1 problem where we are tracking the accessOrder using LinkedList, we can also use ArrayList, ArrayDeque, or LinkedHashMap. The underlying storage for recording keys can change.

   • We can use the interface if we have multiple implementations for storage and inject one of the implementations for LruEvictionPolicy class

3. Read-Write Optimization

   • If you look at the time complexity of recordAccess() and evict() methods it takes O(n) time

   • We can use LinkedHashMap to optimize to get O(1) time complexity

4. Default cache

   • If you look at our design we don’t have a default cache. We did not have this in our requirement we just stuck to the requirements.

   • Solution: We can create a factory pattern to get a default cache based on the input

5. Thread-Safety

   • If multiple threads access the cache, concurrent modifications can cause issues.

   • Solution: Synchronize the storage using a concurrent data structure.

   • We can take this up when we learn concurrency

By working on the above problems at least the first 4, we would have created a SOLID design that is extensible and scalable adhering to OOP concepts. I hope you enjoyed reading the article.

We will not be going into this depth for the other examples.