What are we building?
An LRU cache is a type of memory storage system that keeps track of recently used items. The term "Least Recently Used" indicates that, when the cache is full and a new item needs to be stored, the system will remove the item that hasn't been used for the longest time.
LRU caching is efficient for scenarios where certain items are used more frequently than others. It helps speed up data access by keeping the most relevant and recently used items readily available in memory.
In this article, we'll explore the implementation of an LRU cache through the following axis:
- Initialisation
- Insertion of Data
- Retrieval of Data
- Removal of Data
- Resizing
- Cache Statistics
- Callbacks and Events
- Persistence
- Time-to-live (TTL)
- Custom Eviction Policies
There's a lot to cover, so buckle up!
Overall class definition
Before diving into the actual implementation, let's first define a high-level API for our cache:
Initialisation
For initialisation, we pass the capacity of our cache to the constructor and get back a cache object with all methods needed to perform the operations below.
The capacity is the maximum number of elements that the cache can store. That number cannot be lesser than 1.
const cache = new LRUCache<K, V>(capacity: number);
Insertion of Data
Data inside the cache is addressable by their key which associates it to a value. The keys are unique, meaning that inserting different data with the same key will overwrite any existing data.
Elements are appended to the cache until its size exceeds its capacity, at which point the least recently used element is evicted from the cache.
cache.put(key: K, value: V);
Retrieval of Data
Data can be retrieved from the cache based on their key. Different methods allow for different effects on the returned value and the internal working of the cache.
Getting an element from the cache will return the value of that element if it exists in the cache. After retrieving that element, we update the cache to mark it as the most recently used item in the cache, impacting its potential eviction. Reading an element from the cache is equivalent to "using" that element.
const value: V | undefined = cache.get(key: K);
A similar method but slightly different effects is peek which returns the value of an element if it exists but doesn't update the cache. Peeking at an element isn't equivalent to "using" that element.
const value: V | undefined = cache.peek(key: K);
Finally, if all we care about is checking that an element exists in the cache, has returns a boolean based on the key. This method also doesn't update the cache.
const isKeyInCache: boolean = cache.has(key: K);
Removal of Data
Data can be removed from the cache outside of the eviction policy with the remove method, which removes an element based on its key if it exists.
cache.remove(key: K);
Finally, to remove all elements in the cache, the clear method can be used.
cache.clear();
Resizing
The resize method allows for the capacity of the cache to be dynamically updated after the cache's initialisation. If the new capacity is lower than the current cache's size, the least recently used elements will be evicted until the size is equal to the new capacity.
Note that the new capacity cannot be lesser than 1.
cache.resize(capacity: number);
Cache Statistics
To add some observability into the functioning of the cache, a stats getter calculates and returns a set of statistics.
const stats: LRUCacheStats = cache.stats;
The stats calculated are:
- hit rate
- miss rate
- eviction rate
- effectiveness
type LRUCacheStats = {
// Hit Rate = (Number of Cache Hits) / (Total Number of Cache Accesses)
hitRate: number;
// Miss Rate = (Number of Cache Misses) / (Total Number of Cache Accesses)
missRate: number;
// Eviction Rate = (Number of Evictions) / (Total Number of Cache Accesses)
evictionRate: number;
// Effectiveness = (Number of Evictions) / (Total Number of Cache Hits)
effectiveness: number;
};
Callbacks and Events
To allow for custom logic on interesting events, a basic event emitter implementation is added to the cache. This permits attaching handlers on events and implementing custom logic. In some cases, the cache item concerned by the event is passed to the handler.
Registering a handler for an event is done using the on() method.
const cacheCallback: CacheEventCallback = cache.on(event: CacheEvent, handler: CacheEventHandler);
The returned object provides an unregister() method to remove the handler from the event.
type CacheEventCallback = {
unregister: () => void;
}
Interesting cache events include:
- insertion: when a new item is added to the cache (including exiting items)
- eviction: when an item is evicted from the cache due to the LRU policy
- removal: when an item is manually removed from the cache
- full: when the cache is at capacity
- empty: when the cache has no items
type CacheEvent = "insertion" | "eviction" | "removal" | "full" | "empty"
The cache event handler is potentially passed an item (for insertion, eviction, and removal), which has 2 properties:
key: the key of the item in the cachevalue: the value of the item in the cache
type CacheEventHandler<K, V> = (
event: CacheEvent,
item?: { key: K; value: V },
) => void;
Persistence
Currently, the cache is only stored in memory, meaning that a browser refreshing or a server shutting down will wipe the cache. In most cases, this is fine, but for the cases where it's not, let's look at what persistence might look like.
First, we'd like to add a persistence parameter to the LRUCache constructor.
const cache = new LRUCache<K, V>(capacity: number, persistence: LRUCachePersistence);
Let's also add a setter so that we can add or change the persistence implementation of our cache after instantiation (also know as dependency injection).
const cache = new LRUCache<string,number>(2);
const persistence = new LRUCachePersistence();
cache.persistence = persistence;
The LRUCachePersistence class needs, at a minimum, to implement a method to persist a cache, and to restore it back. It also needs a cacheKey to support multiple caches and identify the right one to potentially restore.
class LRUCachePersistence<K, V> {
#cacheKey: string;
persist: (cache: Map<K, V>) => void = () => {}
restore: () => Map<K, V> = () => new Map()
...
};
To persist a cache, we call the persist() method on the cache, which will delegate to the persist() method on the persistence object. Restoring is similar.
const cache = new LRUCache<K, V>(capacity, persistence);
cache.persist();
...
cache.restore();
Albeit being a good default, having to manually call cache.persist() might be a bit of a chore in some scenarios where we'd like every change to the cache be persisted automatically. To indicate that, we add an autoPersist property to LRUCache which then dictates the automatic persistence behaviour.
const cache = new LRUCache<K, V>(capacity: number, persistence: LRUCachePersistence, autoPersist: boolean);
Time-to-live (TTL)
To enhance the cache even further, a ttl value can be set in the constructor (and a ttl setter) of the cache. This value indicates how many milliseconds each item added to cache is valid for, with elements expiring being evicted.
const cache = new LRUCache<K, V>(capacity: number, options: { ttl: number });
cache.ttl = 1234;
The eviction process is by default a cleanup on access (reactive cleanup), meaning that when an item is retrieve from the cache, it first checks its ttl. If the item is expired, the item is evicted and undefined is returned. Note that getting an element from the cache resets its ttl.
An optional proactive cleanup can be turned on by providing a cleanup interval to the constructor (and ttlCleanupInterval setter) of the cache.
const cache = new LRUCache<K, V>(capacity: number, options: { ttl: number, ttlCleanupInterval: number });
cache.ttlCleanupInterval = 1234;
In addition to the reactive cleanup, the proactive cleanup will remove items that expire regardless of the access. This can help remove expired items that might be overextending their presence in the cache.
Per-item ttls can also be set via the put method, with an optional third argument ttl.
cache.put(key: K, value: V, ttl?: number);
Custom Eviction Policies
Finally, to complete the API of our over-engineered cache, let's add the possibility to define custom eviction policies!
const cache = new Cache<K, V>(capacity: number, options: { evictionPolicy: CacheEvictionPolicy })
In essence, this is an options passed to the constructor. It is a function that returns a key K to be evicted when the cache is at capacity and a new element is inserted.
It takes the cache as unique argument and returns the key that needs to be evicted. By default, that should be the least recently used element in the cache.
// Returns the key of the element to evict when cache is full
type CacheEvictionPolicy<K, V> = (cache: Cache<K, V>) => K;
Detailed implementation
Now that we've seen the high-level specifications of our cache, let's dive into its implementation!
Underlying Data Structure
To build an efficient cache, we need to use some efficient underlying data structure. Ideally, we would like to have constant complexity (O(1)) on reads and writes to our cache. That means that the time to read and write data into our cache remains constant regardless of the size of the cache. Hash tables provide an average complexity of O(1), even though the worst case scenario might still be linear O(n), meaning that the time to read and write date grow proportionally to the size of the cache.
Objects in JavaScript are implemented as hash tables in most engines. They provide the same guarantees as hash tables, with a constant average complexity for reads and write. They unfortunately don't provide guarantees on the order of its elements, meaning that we would need to track that in a different data structure as we need to keep track of the least recently used element. Luckily, JavaScript has another data structure, that is similar to Objects in terms of complexity, but that guarantees the ordering of keys: Map. Even though the spec only requires a sub-linear average complexity, Maps are implemented in V8 using deterministic hash maps, making it the ideal underlying data structure for our cache implementation!
class LRUCache<K, V> {
/**
* @private
* @type {Map<K, V>} - The underlying map that holds the cache
*/
#map: Map<K, V>;
}
Initialisation
To initialise a cache, we pass its capacity to the constructor. We store that value in a private property, similar to the #map:
class LRUCache<K, V> {
/**
* @private
* @type {number} - The maximum number of items the cache can hold
*/
#capacity: number;
}
We need to take care of the edge cases where the cache is initialise with a negative or zero value for its capacity. The constructor also initialises the underlying #map data structure, which will store the values in the cache.
constructor(capacity: number) {
if (capacity < 1) {
throw new Error("Capacity must be greater than 0");
}
this.#capacity = capacity;
this.#map = new Map();
}
Insertion of Data
Inserting data into our cache is done using the put method which takes a key and a value as arguments. The put method then adds the key-value pair to the underlying #map.
put(key: K, value: V): void {
this.#map.set(key, value);
}
There are 2 cases that need to be handled:
- the cache is already at capacity when adding the provided key-value pair
- data for the provided
keyalready exists in the cache
For the case where the cache is at capacity, we need to evict an existing element to make room for the newly provided element. As we are implementing an LRU cache, we evict the least recently used element of the cache. As we are storing data in an underlying Map, we have a guarantee that elements inserted into the Map are in order of insertion, meaning that the oldest element in the cache is always the first. We can retrieve the value of first element's key of a Map by iterating over Map.keys(). This can be implemented as a getter on the LRUCache class:
get first(): K | undefined {
return this.#map.keys().next().value;
}
We also need another getter to check if the cache is at capacity when inserting new data. To do so we need to check the size of the underlying Map with the value of #capacity passed to the constructor:
get size(): number {
return this.#map.size;
}
Using those getters, we can amend our put method to evict the least recently used element in our cache when it is at capacity.
put(key: K, value: V): void {
if (this.size === this.capacity) {
this.#map.delete(this.first!);
}
this.#map.set(key, value);
}
The current implementation still fails in cases where we are adding a new value with an existing key into our cache. Indeed, in that case, with the current implementation, we might remove the oldest element in the cache, even though the size of the Map wouldn't be changing as we are ultimately just replacing an element's value. Another issue is that the newly passed item will take the place of the existing element, when we'd like it to move all the way at the end of the Map as it should be considered a new element.
To solve for both issues, if the Map already contains a given key, we remove that key. If that is the case, we don't need the check for the eviction case either. Finally, we append the element into the Map.
put(key: K, value: V): void {
if (this.#map.has(key)) {
this.#map.delete(key);
} else if (this.size === this.capacity) {
this.#map.delete(this.first!);
}
this.#map.set(key, value);
}
Retrieval of Data
We can now add data into our cache, so let's look at retrieving that data!
To do so, we will implement a get method on our cache that takes a key as argument, and returns either the associated value if it is present in the cache, or undefined if it is not present.
get(key: K): V | undefined {
return this.#map.get(key);
}
When retrieving an element from the cache, we also need to update its "age" within the cache, as retrieving an element counts as "using" it. To achieve that, we delete and reset the element if it is found in the cache, effectively appending it to the end of the #map.
get(key: K): V | undefined {
const value = this.#map.get(key);
if (value) {
this.#map.delete(key);
this.#map.set(key, value);
return value;
}
}
The first iteration of the get method can sometimes come handy though, if for example you want to retrieve data without altering the order of usage in the cache. That option is provided via the peek method:
peek(key: K): V | undefined {
return this.#map.get(key);
}
Finally, you might just be interested in knowing if a key is already set in the cache. Again, for this operation we don't want to alter the cache itself, so the implementation is fairly straightforward:
has(key: K): boolean {
return this.#map.has(key);
}
Removal of Data
We now have a functioning LRU cache. Elements can be added to the cache, they can be retrieved from the cache, and the least recently used element is evicted whenever the cache reaches its capacity. Some more utility methods we might want to implement are around manual removal of data.
Removing a specific key from the cache is done using a remove method that takes as argument the key to remove. This effectively remove the value from the underlying #map.
remove(key: K): void {
this.#map.delete(key);
}
In the same vein, we can implement a clear method that removes all data inside the cache.
clear(): void {
this.#map.clear();
}
Note that we don't need to update the current size of our cache (how many elements are in the cache), as that's read via a getter that returns whichever size the underlying #map currently has.
Dynamic Resizing
Looking at some more advanced use cases, it might be useful to be able to resize an existing cache instead of just being stuck with the capacity set at initialisation. To achieve that, we implement a resize method that takes an new capacity value as argument.
resize(capacity: number): void {
if (capacity < 1) {
throw new Error("Capacity must be greater than 0");
}
this.#capacity = capacity;
}
The above implementation is incomplete though, as we might end up in a situation where the new capacity is lower than the current cache size. In that scenario the size of the cache will always be beyond the cache capacity. As such, when reseting the capacity of an existing cache, if its current size is greater than the new capacity value, we need to evict elements from the cache until the size is equal to the cache's capacity.
resize(capacity: number): void {
if (capacity < 1) {
throw new Error("Capacity must be greater than 0");
}
this.#capacity = capacity;
while (this.size > this.capacity) {
this.#map.delete(this.first!);
}
}
We achieve that by evicting the oldest element while the size is greater than the capacity.
Cache Statistics
To allow for some observability of the cache, we want to compute and expose the following statistics:
- hit rate
- miss rate
- eviction rate
- effectiveness
To compute those values we need to keep track internally of the number of accesses to the cache, the number of hits, misses, and policy evictions. For accesses, we only count retrievals by calling the get method. Note that manually evictions (either due to a resizing or by calling the remove method) are not counted as well.
#stats = {
hit: 0,
miss: 0,
eviction: 0,
access: 0,
};
We need to update the get and put methods to count the number of hits, misses, evictions, and accesses to the cache:
get(key: K): V | undefined {
const value = this.#map.get(key);
if (value) {
this.#map.delete(key);
this.#map.set(key, value);
this.#stats.hit += 1;
} else {
this.#stats.miss += 1;
}
this.#stats.access += 1;
return value;
}
put(key: K, value: V): void {
if (this.#map.has(key)) {
this.#map.delete(key);
} else if (this.size === this.capacity) {
this.#map.delete(this.first!);
this.#stats.eviction += 1;
}
this.#map.set(key, value);
}
Finally, we calculate the statistics whenever we access the stats getter.
get stats(): LRUCacheStats {
const hitRate = this.#stats.access
? this.#stats.hit / this.#stats.access
: 0;
const missRate = this.#stats.access
? this.#stats.miss / this.#stats.access
: 0;
const evictionRate = this.#stats.access
? this.#stats.eviction / this.#stats.access
: 0;
const effectiveness = this.#stats.hit
? this.#stats.eviction / this.#stats.hit
: 0;
return {
hitRate,
missRate,
evictionRate,
effectiveness,
};
}
Note that in JavaScript, the Number type is a double-precision 64-bit binary format IEEE 754 value. That means that rates might not be exact as they are decimal values, and that beyond 2^53 - 1 (Number.MAX_SAFE_INTEGER) integer representations are no longer exact so the underlying internal counters might be inaccurate.
Callbacks and Events
To facilitate attaching custom logic to interesting cache events, we implement a basic event emitter and handler within the cache itself.
To store those event handlers, we add a new private property to the cache:
#eventHandlers: Record<CacheEvent, Array<CacheEventHandler<K, V>>> = {
[CacheEvent.Insertion]: [],
[CacheEvent.Eviction]: [],
[CacheEvent.Removal]: [],
[CacheEvent.Full]: [],
[CacheEvent.Empty]: [],
};
The shape of that property is a mapping of CacheEvent to an array of CacheEventHandlers.
enum CacheEvent {
Insertion = "insertion",
Eviction = "eviction",
Removal = "removal",
Full = "full",
Empty = "empty",
}
type CacheEventHandler<K, V> = (
event: CacheEvent,
item?: { key: K; value: V },
) => void;
Attaching event handlers is performed with the on() method. It returns an object with an unregister() method to remove the handler from the event.
on(event: CacheEvent, callback: CacheEventHandler<K, V>): CacheEventCallback {
if (!this.#eventHandlers[event]) {
throw new Error(`Invalid event: ${event}`);
}
this.#eventHandlers[event].push(callback);
const unregister = () => {
this.#eventHandlers[event] = this.#eventHandlers[event].filter(
(cb) => cb !== callback,
);
};
return { unregister };
}
type CacheEventCallback = {
unregister: () => void;
};
A private method #emit() is then used to emit cache events and trigger the related event handlers. Optionally, an item is also passed to the handlers.
#emit(event: CacheEvent, key?: K, value?: V): void {
this.#eventHandlers[event].forEach((handler) => {
handler(event, key && value ? { key, value } : undefined);
});
}
Finally, we emit the necessary events from other methods of the cache, for example:
remove(key: K): void {
this.#emit(CacheEvent.Removal, key, this.#map.get(key));
this.#map.delete(key);
if (this.size === 0) {
this.#emit(CacheEvent.Empty);
}
}
Persistence
There are different ways of implementing persistence for our cache. In our case we are going to implement an external LRUCachePersistence class and pass an instance of that class into our cache. That instance is then set to an internal #persistence property. This allows for flexibility in persistence strategies, as it can be defined outside of the cache logic itself.
At a high level, the LRUCachePersistence is defined as:
#cacheKeyproperty (and correspondingkeygetter): which can be used in the persistence logic to identify a specific cachepersistproperty, assigned to a function: which contains the logic to serialise and store a cache's datarestoreproperty, assigned to a function: which contains the logic to deserialise and return a cache's data
class LRUCachePersistence<K, V> {
#cacheKey: string;
persist: (cache: Map<K, V>) => void = (cache) => { ... };
restore: () => Map<K, V> = () => { ... };
constructor(
cacheKey: string = uuidv4(),
autoPersist: boolean = false,
logic?: { persist: (cache: Map<K, V>) => void; restore: () => Map<K, V> },
) { ... }
get key(): string { ... }
}
A few interesting things to notice so far:
persistandrestoreare properties holding functions, not methods. This is due to the fact that they can be overwritten in theconstructorif customlogicis passed.persistandrestoredeal withMapinstead ofLRUCacheinstances. This allows forLRUCachePersistenceto not be tightly coupled withLRUCache, meaning it can be used to persist other caches as long as they can serialise and deserialise their data into aMap.
The default implementation of persist and restore leverage localStorage, but any custom logic can be passed into the constructor to replace that.
persist: (cache: Map<K, V>) => void = (cache) => {
localStorage.setItem(
this.#cacheKey,
JSON.stringify(
Array.from(cache.entries()).map(([k, v]) => ({ key: k, value: v })),
),
);
};
restore: () => Map<K, V> = () => {
const data = localStorage.getItem(this.#cacheKey);
if (data) {
return new Map(
JSON.parse(data).map(({ key, value }: { key: K; value: V }) => [
key,
value,
]),
);
}
return new Map();
}
For consistency with the format of item in the event handlers, we are serialising the Map into an Array of objects with a key and a value property.
The persistence can be set for a cache, either in the constructor or via a setter. The instance then leaves inside an internal #persistence property of the cache.
constructor(
capacity: number,
persistence?: LRUCachePersistence<K, V>,
) {
if (capacity < 1) {
throw new Error("Capacity must be greater than 0");
}
this.#capacity = capacity;
this.#map = new Map();
this.#persistence = persistence;
}
set persistence(persistence: LRUCachePersistence<K, V> | undefined) {
this.#persistence = persistence;
}
The cache is in charge of calling the persist() and restore() methods of its #persistence property. Those methods are surfaced on the cache instance with ... persist() and restore() methods!
persist(): void {
if (!this.#persistence) {
throw new Error("Persistence is not set");
}
this.#persistence.persist(this.#map);
}
restore(): void {
if (!this.#persistence) {
throw new Error("Persistence is not set");
}
this.#map = this.#persistence.restore();
}
This is great, but we can go on step further! Currently, if we'd like to persist the data in our cache, we'd need to manually call cache.persist(). This is probably fine for most use cases, but wouldn't it be more convenient if we could tell our cache to persist itself automatically on every change? Let's build just that!
We add a new #autoPersist property to our LRUCache class, which is set either via the constructor or a setter. Now, every time there is a change to the cache's data, we check if the #autoPersist flag is set, and if so, we call persist().
remove(key: K): void {
...
this.#map.delete(key);
if (this.#autoPersist) {
this.persist();
}
...
}
Time-to-live (TTL)
Implementing a time-to-live (TTL) function for items in the cache provides even more control on the cache's behaviour. The idea behind attaching TTL to cache items, is for these items to be removed from the cache after a given period of time, regardless of other eviction policies. The benefit here is that we can get rid of stale values without needing to fill in the cache, or without having newer values at hand.
There are 2 main implementations of TTL eviction in caches: reactive or proactive.
A reactive cleanup approach is implemented by checking the expiry of an item on lookup. The main advantages of this approach are its simplicity (cleanup is tied to cache operations) and its efficiency (only checks on cache operations). On the other hand, there are risks of having inconsistent performance on cache operations (as they now also need to check expiry and cleanup) and accumulation of stale data (as data only gets cleaned up on cache operations).
A proactive cleanup approach is implemented using an internal clock and checking all items in the cache periodically. If this sounds like garbage collection, maybe it is! The main advantages here are timely eviction, consistency, and no performance penalty on cache operations. On the other hand, it is more complex to implement, and it might lead to performance issues or stale data depending on the frequency of the internal clock.
Gentle reminder that this is an article about over-engineering a cache, so of course we will be implementing both a reactive cleanup, and an optional proactive cleanup mechanism!
To start, we add a #ttl and a #ttlMap properties to our cache. The #ttl property holds the TTL for all items in the cache, whereas the #ttlMap holds the expiry date for each element by key.
/**
* @private
* @type {number} - The default time-to-live (TTL) for cache items (in ms)
*/
#ttl?: number;
/**
* @private
* @type {Map<K, number>} - The map that holds the time-to-live (TTL) for
* cache items
*/
#ttlMap: Map<K, number>;
We read the value of #ttl in the constructor, where we also instantiate #ttlMap. Note that we always instantiate it to simplify the code afterwards.
constructor(
capacity: number,
options: {
...
ttl?: number;
} = {},
) {
...
this.#ttl = options.ttl;
this.#ttlMap = new Map();
}
Once we have the #ttl, we insert a new entry in #ttlMap whenever a new item is added to the cache. Similarly, we remove any entry in #ttlMap when it is removed from the cache.
put(key: K, value: V, ttl?: number): void {
if (this.#map.has(key)) {
this.#map.delete(key);
this.#ttlMap.delete(key);
} else if (this.size === this.capacity) {
const key = this.first!;
this.#emit(CacheEvent.Eviction, key, this.#map.get(key));
this.#map.delete(key);
this.#ttlMap.delete(key);
this.#stats.eviction += 1;
}
this.#map.set(key, value);
this.#emit(CacheEvent.Insertion, key, value);
if (this.#ttl) {
this.#ttlMap.set(key, Date.now() + this.#ttl);
}
if (this.#autoPersist) {
this.persist();
}
if (this.size === this.capacity) {
this.#emit(CacheEvent.Full);
}
}
We need to do the same thing when getting an item from the cache, as that updates the item.
get(key: K): V | undefined {
this.#stats.access += 1;
const value = this.#map.get(key);
if (value) {
this.#map.delete(key);
this.#map.set(key, value);
this.#ttlMap.delete(key);
if (this.#ttl) {
this.#ttlMap.set(key, Date.now() + ttl);
}
if (this.#autoPersist) {
this.persist();
}
this.#stats.hit += 1;
} else {
this.#stats.miss += 1;
}
return value;
}
Finally, we also need to update the remove, clear and resize methods to remove the same elements from both #map and #ttlMap.
All items in the cache now have an expiry date, but we need to add the reactive cleanup mechanism! To do so, we first implement a private method #ttlEvict which takes a key: K as an argument and returns true if the item has expired (and hence, has been evicted) or false otherwise.
#ttlEvict(key: K): boolean {
if (this.#ttlMap.has(key)) {
const ttl = this.#ttlMap.get(key);
if (ttl && Date.now() > ttl) {
this.#emit(CacheEvent.Eviction, key, this.#map.get(key));
this.#map.delete(key);
this.#ttlMap.delete(key);
if (this.#autoPersist) {
this.persist();
}
return true;
}
}
return false;
}
Note that we need to add all the bells and whistles from the previously implemented features, namely the events and the persistence!
This private method can now be used in all places where we do cache operations to check on the expiry of an item. Note that if the cache doesn't have a TTL configured, this check is still fairly efficient because we are doing a lookup on a Map by its key.
get(key: K): V | undefined {
this.#stats.access += 1;
if (this.#ttlEvict(key)) {
this.#stats.miss += 1;
return undefined;
}
...
}
Similar logic also needs to be added to both the peek and has methods!
Optionally, a proactive cleanup strategy is in effect when a ttlCleanupInterval value is passed to the constructor.
constructor(
capacity: number,
options: {
...
ttl?: number;
ttlCleanupInterval?: number;
} = {},
) {
...
this.#ttl = options.ttl;
this.#ttlMap = new Map();
if (
options.ttlCleanupInterval !== undefined &&
options.ttlCleanupInterval < 1
) {
throw new Error("TTL cleanup interval must be greater than 0");
}
this.#ttlClearCleanupInterval = this.#ttlSetCleanup(
options.ttlCleanupInterval,
);
}
A private method #ttlSetCleanup performs the proactive cleanup for the given interval. This method starts an internal clock that calls #ttlEvict on every item of the #ttlMap.
#ttlSetCleanup(interval: number = 0): (() => void) | undefined {
if (!interval) {
return;
}
const timeout = setInterval(() => {
this.#ttlMap.forEach((_, key) => this.#ttlEvict(key));
}, interval);
return () => clearInterval(timeout);
}
The cleanup interval can be updated (or unset) using a setter. This is also why we need to keep track of the clearInterval function in a private property #ttlClearCleanupInterval to reset the internal clock.
set ttlCleanupInterval(interval: number) {
this.ttlClearCleanupInterval();
if (!interval) {
this.#ttlClearCleanupInterval = undefined;
return;
}
if (interval < 1) {
throw new Error("TTL cleanup interval must be greater than 0");
}
this.#ttlClearCleanupInterval = this.#ttlSetCleanup(interval);
}
Finally, we want to be able to set custom TTLs for items when they are appended to the cache. To do that, we need to update the put method and add an extra ttl argument. It still needs to default to whatever value might have been passed in the constructor, which is stored in the #ttl property of the cache.
put(key: K, value: V, ttl?: number): void {
...
if (ttl) {
this.#ttlMap.set(key, { ttl, expiresAt: Date.now() + ttl });
} else if (this.#ttl) {
this.#ttlMap.set(key, {
ttl: this.#ttl,
expiresAt: Date.now() + this.#ttl,
});
}
...
}
We must not forget to also update the get method, which updates an element and its TTL.
get(key: K): V | undefined {
...
const value = this.#map.get(key);
if (value) {
...
if (this.#ttl) {
const ttl = this.#ttlMap.get(key)!.ttl;
this.#ttlMap.set(key, {
ttl,
expiresAt: Date.now() + ttl,
});
}
...
}
...
return value;
}
Custom Eviction Policies
So far, we've built a cache with a hardcoded least-recently-used (LRU) eviction policy. In a way, we have optimised it for that purpose, but we can also make it more extensible to allow for other kinds of eviction policies. To do that, we need to add support for custom eviction policies!
An eviction policy is a function that takes the cache as unique argument and returns the key K to evict.
type CacheEvictionPolicy<K, V> = (cache: Cache<K, V>) => K;
The way we are implementing this is via another options in the constructor. It will have a default value, and it will be attached to the internal property #evictionPolicy. By default, we still have an LRU cache as the oldest element in the cache will be evicted based on the default eviction policy.
constructor(
capacity: number,
{
...
evictionPolicy = (cache) => cache.first!,
}: CacheOptions<K, V> = {},
) {
...
this.#evictionPolicy = evictionPolicy;
...
}
We now need to make a small change in 2 methods: put and resize.
put(key: K, value: V, ttl?: number): void {
if (this.#map.has(key)) {...}
else if (this.size === this.capacity) {
const key = this.#evictionPolicy(this); // <- Using the custom eviction policy
this.#emit(CacheEvent.Eviction, key, this.#map.get(key));
this.#map.delete(key);
this.#ttlMap.delete(key);
this.#stats.eviction += 1;
}
...
}
resize(capacity: number): void {
...
while (this.size > this.capacity) {
const key = this.#evictionPolicy(this); // <- Using the custom eviction policy
this.#emit(CacheEvent.Eviction, key, this.#map.get(key));
this.#map.delete(key);
}
...
}
We can easily implement an MRU (most recently used) cache, as we already have a last getter in our cache implementation.
get last(): K | undefined {
return Array.from(this.#map.keys()).pop();
}
const cache = new Cache<string, number>(2, {
evictionPolicy: (cache) => cache.last!,
});
cache.put("a", 1);
cache.put("b", 2);
cache.get("a"); // <- Most recently used item
cache.put("c", 3);
cache.has("a"); // false
Implementing FIFO (first in, first out) and LIFO (last in, first out) eviction policies is a bit more involved, but still relatively simple. We first need to create a new class CacheWithList which inherits from our cache class. Then we need to add a list property to keep track of the order in which items are added to the list.
class CacheWithList<K, V> extends Cache<K, V> {
list?: K[];
constructor(capacity: number, options?: CacheOptions<K, V>) {
super(capacity, options);
this.list = [];
}
put(key: K, value: V, ttl?: number) {
super.put(key, value, ttl);
this.list!.push(key);
}
}
Then we can use different eviction policies for different types of cache.
// FIFO
const cache = new CacheWithList<string, number>(2, {
evictionPolicy: (cache: CacheWithList<string, number>) =>
cache.list!.shift()!,
});
// LIFO
const cache = new CacheWithList<string, number>(2, {
evictionPolicy: (cache: CacheWithList<string, number>) =>
cache.list!.pop()!,
});
// RR (random)
const cache = new CacheWithList<string, number>(2, {
evictionPolicy: (cache: CacheWithList<string, number>) => {
const index = Math.floor(Math.random() * cache.list!.length);
const key = cache.list![index];
cache.list!.splice(index, 1);
return key;
},
});
Similarly, we can add the family of frequency-based cache eviction policies using the same idea of extending our base cache class.
class CacheWithFrequencies<K, V> extends Cache<K, V> {
frequencies?: Map<K, number>;
constructor(capacity: number, options?: CacheOptions<K, V>) {
super(capacity, options);
this.frequencies = new Map();
}
get(key: K): V | undefined {
const value = super.get(key);
if (value) {
this.frequencies!.set(key, (this.frequencies!.get(key) || 0) + 1);
} else {
this.frequencies!.delete(key);
}
return value;
}
put(key: K, value: V, ttl?: number) {
super.put(key, value, ttl);
this.frequencies!.set(key, 0);
}
remove(key: K) {
super.remove(key);
this.frequencies!.delete(key);
}
}
We can play with different eviction policies to generate different kinds of cache that use frequencies for eviction.
// LFU (least frequentyl used)
const cache = new CacheWithFrequencies<string, number>(2, {
evictionPolicy: (cache: CacheWithFrequencies<string, number>) => {
let min = Infinity;
let lfu = "";
for (const [key, freq] of cache.frequencies!) {
if (freq < min) {
min = freq;
lfu = key;
}
}
return lfu;
},
});
// MFU (most frequently used)
const cache = new CacheWithFrequencies<string, number>(2, {
evictionPolicy: (cache: CacheWithFrequencies<string, number>) => {
let max = -Infinity;
let mfu = "";
for (const [key, freq] of cache.frequencies!) {
if (freq > max) {
max = freq;
mfu = key;
}
}
return mfu;
},
});
Ultimately, there is the possibility to create as complex an eviction policy as we'd like, while still being able to use persistence, TTL, events, and all the other niceties we've built so far.
And if you just want simplicity though, this is all you need to get a decent cache:
const cache = new Cache<string, string>(42);
GitHub code + npm package
All this code is available on GitHub and as an npm package!
AntonioVdlC
