NoCache

Table of Contents

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

Cyrus Kao
Last modified on .

I created a simple key-value LRU (Least Recently Used) cache module for storing user sessions of this blog. And with the power of Javascript ES6 Map object, it's easy to implement a efficient cache system. In this guide we'll be building this module from scratch in Node.js with Typescript.

There is a lot of Javascript LRU cache implementations online using Set for actual values and Map for indexing key and last usage. To save memory, my implementation will only use Map. And there is also a small tweak to improve the performance on deletions.

LRU cache
A simple LRU cache example

Build Your Own Cache Module

Follow this section to write your own cache module in Typescript, or to use the library directly.

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

Module

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

App

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

Use Directly

To use the cache module without building your own, install kv-lru-cache from npm:

$ npm i kv-lru-cache

Then import kv-lru-cache and it's ready to use:

import Cache from 'kv-lru-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

Comments

Sign in to leave a comment.