Build a Key-Value LRU Cache Module in Node.js with Typescript
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](/images/JjwdZPpH8moB.491x497.jpg)
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 totarget * 110%
, which gives us some wiggle room in dropping caches. So we'll be performing a once-for-all deletion whenmax
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