Scalable LRU Cache in JavaScript for Faster Web Apps

Problem Description

You are building a backend service that needs to perform database lookups for various queries. However, the database is slow and it's not feasible to query it for every request. To speed up your service, you decide to implement a cache with a time-to-live (TTL) mechanism. The cache should store the results of previous queries for a configurable amount of time before expiring.

Write a cache class that can perform the following operations:

get(key: string): Promise<any> - Given a key, retrieve the corresponding value from the cache. If the value has expired, return null.
set(key: string, value: any, ttl: number): Promise<void> - Set a value in the cache for the given key with the specified TTL (in seconds).
del(key: string): Promise<void> - Delete the value corresponding to the given key from the cache.

Input

The input to this problem consists of function calls to the cache class.

Output

The output of get should be the cached value corresponding to the given key, or null if the value has expired or does not exist. The output of set and del should be void.

Constraints

Assume that the input key and value will always be strings, and that the TTL will always be a non-negative integer.

Example

const cache = new Cache();

await cache.set("foo", "bar", 10);
await cache.set("baz", "qux", 20);

console.log(await cache.get("foo")); // Output: "bar"
console.log(await cache.get("baz")); // Output: "qux"

await new Promise(resolve => setTimeout(resolve, 10000));

console.log(await cache.get("foo")); // Output: null
console.log(await cache.get("baz")); // Output: "qux"

await cache.del("baz");

console.log(await cache.get("baz")); // Output: null

Approach

We can use a JavaScript Map object to implement the cache, with the keys representing the cache keys and the values representing objects containing the cached value and its expiration time. To implement TTL, we can store the expiration time as a Unix timestamp (i.e., the number of seconds since January 1, 1970), and compare it to the current time whenever get is called.

To implement set, we can simply add a new key-value pair to the map with the specified expiration time. To implement del, we can delete the key-value pair from the map. We can use setTimeout to automatically delete expired keys after their TTL has passed.

Solution

class Cache {
  constructor() {
    this.cache = new Map();
  }

  async get(key) {
    const cached = this.cache.get(key);
    if (!cached) return null;
    if (cached.expire < Date.now()) {
      this.cache.delete(key);
      return null;
    }
    return cached.value;
  }

  async set(key, value, ttl) {
    const expire = Date.now() + ttl * 1000;
    this.cache.set(key, { value, expire });
    setTimeout(() => this.cache.delete(key), ttl * 1000);
  }

  async del(key) {
    this.cache.delete(key);
  }
}

Explanation

The Cache class is defined with a constructor that initializes an empty Map object to store the cached values. The get method retrieves the value corresponding to the given key from the map, and checks if the value has expired by comparing the current time (Date.now()) to the expiration time (cached.expire). If the value has expired, it is deleted from the map and null is returned. Otherwise, the cached value is returned.

The set method sets a new key-value pair in the map with the given expiration time, calculated as the current time plus the TTL (in seconds) times 1000 (to convert to milliseconds). The method also sets a setTimeout function to delete the key after the TTL has passed.

The del method simply deletes the key-value pair corresponding to the given key from the map.

Alternative Solution

Another approach to implementing a TTL cache is to use a doubly-linked list to keep track of the order in which keys were accessed. When a key is accessed, it is moved to the front of the list. When the cache is full and a new key needs to be added, the key at the end of the list (i.e., the least recently accessed key) is deleted.

To implement TTL, we can store the expiration time as a property of each node in the list, and use a setTimeout function to delete expired nodes after their TTL has passed.

Here's an implementation using this approach:

class Node {
  constructor(key, value, expire = null) {
    this.key = key;
    this.value = value;
    this.expire = expire;
    this.prev = null;
    this.next = null;
  }
}

class Cache {
  constructor(maxSize = 1000) {
    this.maxSize = maxSize;
    this.size = 0;
    this.cache = new Map();
    this.head = null;
    this.tail = null;
  }

  async get(key) {
    const node = this.cache.get(key);
    if (!node) return null;
    if (node.expire && node.expire < Date.now()) {
      this.delete(node);
      return null;
    }
    this.moveToFront(node);
    return node.value;
  }

  async set(key, value, ttl) {
    let node = this.cache.get(key);
    if (node) {
      node.value = value;
      node.expire = ttl ? Date.now() + ttl * 1000 : null;
      this.moveToFront(node);
      return;
    }
    node = new Node(key, value, ttl ? Date.now() + ttl * 1000 : null);
    this.cache.set(key, node);
    if (this.size === this.maxSize) {
      this.delete(this.tail);
    }
    this.addToFront(node);
  }

  async del(key) {
    const node = this.cache.get(key);
    if (!node) return;
    this.delete(node);
  }

  delete(node) {
    this.cache.delete(node.key);
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;
    this.size--;
  }

  moveToFront(node) {
    if (node === this.head) return;
    if (node.prev) node.prev.next = node.next;
    if (node.next) node.next.prev = node.prev;
    if (node === this.tail) this.tail = node.prev;
    node.prev = null;
    node.next = this.head;
    if (this.head) this.head.prev = node;
    this.head = node;
  }

  addToFront(node) {
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;  
      this.head = node;
    }
    this.size++;
  }

This implementation uses a doubly-linked list to keep track of the order in which keys were accessed. The list is maintained in the head and tail properties of the Cache class.

The get method first checks if the key exists in the cache. If it doesn't, it returns null. If the key exists, it checks if the value has expired by comparing the current time to the expiration time. If the value has expired, it is deleted from the cache and null is returned. Otherwise, the value is returned, and the corresponding node is moved to the front of the list using the moveToFront method.

The set method first checks if the key already exists in the cache. If it does, it updates the corresponding node with the new value and expiration time (if TTL is provided), and moves the node to the front of the list using the moveToFront method. If the key does not exist, it creates a new node with the given key, value, and expiration time (if TTL is provided), and adds it to the front of the list using the addToFront method. If the cache is already at maximum capacity, the least recently accessed node (i.e., the one at the end of the list) is deleted using the delete method.

The del method simply deletes the key-value pair corresponding to the given key from the cache using the delete method.

Overall, this implementation provides a more efficient way to maintain the cache size and order of keys, and also allows for more efficient expiration of keys by using a doubly-linked list to keep track of the order in which keys were accessed.

Nishanth Prabhu's Blog

Nishanth Prabhu's Blog

Implement a Cache with Time-to-Live (TTL)

Implementing a Scalable LRU Cache in JavaScript for Efficient Caching and Faster Web Applications