Build a Key-Value LRU Cache Module in Node.js with Typescript

Main Code

We'll be creating a generic class for the module, so different cache instances could be created at runtime:

// creating generic type parameters `K`, `V` for the types of key and value
class Cache<K, V> {
	private readonly target: number;
	private readonly max: number;
	// use `Map` to store our key-value cache
	private readonly map = new Map<K, V>();

	// this constructor takes two parameter `target` and `max`, setting target capacity and maximum tolerence
	constructor(target: number, max = target + Math.max(Math.round(target / 10), 1)) {
		if (max < target) {
			throw new Error(`Max muse be >= target`);
		}

		this.target = target;
		this.max = max;
	}
}
TypeScript

By default, max is set to target * 110%, which gives us some wiggle room in dropping caches. So we'll be performing a once-for-all deletion when max is reached, instead of dropping a single item on each overflow. Which is a huge performance boost on a high capacity cache.

Create a public method to set cache. The update parameter indicates whether to move the existing item to the bottom of this.map:

class Cache<K, V> {
	...
	public set(key: K, value: V, update = true): void {
		if (this.map.has(key)) {
			if (update) {
				// delete the existing item then re-append it
				this.map.delete(key);
			}
			this.map.set(key, value);
		} else if (this.map.set(key, value).size > this.max) {
			// performorn deletions only if `size` of `this.map` is greater than `this.max`
			for (const key of this.map.keys()) {
				// delete oldest items from the top of `this.map`
				this.map.delete(key);
				// stop if `this.target` is reached
				if (this.map.size === this.target) {
					break;
				}
			}
		}
	}
}
TypeScript

And a public method to get cache by key. The update parameter indicates whether to move the existing item to the bottom of this.map:

class Cache<K, V> {
	...
	public get(key: K, update = true): V | undefined {
		if (update) {
			// check if `this.map` has `key`. the reason not using `get` here is because the return value of `get` could legitimately be `undefined` and existing at the same time
			if (this.map.has(key)) {
				const value = this.map.get(key) as V;
				// re-append the item to bottom
				this.map.delete(key);
				this.map.set(key, value);

				return value;
			}

			return;
		}

		return this.map.get(key);
	}
}
TypeScript

Expose native methods of this.map:

class Cache<K, V> {
	...
	public has(key: K): boolean {
		return this.map.has(key);
	}

	public delete(key: K): boolean {
		return this.map.delete(key);
	}

	public clear(): void {
		this.map.clear();
	}

	public forEach(callback: (value: V, key: K, map: Map<K, V>) => void, thisArg?: any): void {
		this.map.forEach(callback, thisArg);
	}

	public entries(): IterableIterator<[K, V]> {
		return this.map.entries();
	}

	public keys(): IterableIterator<K> {
		return this.map.keys();
	}

	public values(): IterableIterator<V> {
		return this.map.values();
	}
}
TypeScript

And the property size as well:

class Cache<K, V> {
	...
	public get size(): number {
		return this.map.size;
	}
}
TypeScript

Usage

Create a cache instance with target of 10 and maximum of 12 items:

const cache = new Cache<string, number>(10, 12);
TypeScript

Set some new items and see if the least-recently-used ones fall out:

for (let i = 0; i < 20; i++) {
	cache.set(i.toString(), i);
}

console.log(cache.values());
TypeScript

[Map Iterator] { 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }
Output

Full Example

cache.tsexport default class Cache<K, V> {
	private readonly target: number;
	private readonly max: number;
	private readonly map = new Map<K, V>();

	constructor(target: number, max = target + Math.max(Math.round(target / 10), 1)) {
		if (max < target) {
			throw new Error(`Max muse be >= target`);
		}

		this.target = target;
		this.max = max;
	}

	public set(key: K, value: V, update = true): void {
		if (this.map.has(key)) {
			if (update) {
				this.map.delete(key);
			}
			this.map.set(key, value);
		} else if (this.map.set(key, value).size > this.max) {
			for (const key of this.map.keys()) {
				this.map.delete(key);

				if (this.map.size === this.target) {
					break;
				}
			}
		}
	}

	public get(key: K, update = true): V | undefined {
		if (update) {
			if (this.map.has(key)) {
				const value = this.map.get(key) as V;

				this.map.delete(key);
				this.map.set(key, value);

				return value;
			}

			return;
		}

		return this.map.get(key);
	}

	public has(key: K): boolean {
		return this.map.has(key);
	}

	public delete(key: K): boolean {
		return this.map.delete(key);
	}

	public clear(): void {
		this.map.clear();
	}

	public forEach(callback: (value: V, key: K, map: Map<K, V>) => void, thisArg?: any): void {
		this.map.forEach(callback, thisArg);
	}

	public entries(): IterableIterator<[K, V]> {
		return this.map.entries();
	}

	public keys(): IterableIterator<K> {
		return this.map.keys();
	}

	public values(): IterableIterator<V> {
		return this.map.values();
	}

	public get size(): number {
		return this.map.size;
	}
}
TypeScript

index.tsimport Cache from './cache';
import express from 'express';

const cache = new Cache<string, User>(10, 15);
const app = express();

app.use((req, res, next) => {
  const session = req.cookies.session;

  req.user = cache.get(session);

  if (!req.user) {
    auth(session).then((user) => {
      req.user = user;
			cache.set(session, user);
    });
  }
	...
});
TypeScript