Weak LRU Cache

Weak-referencing is powerful new feature in JavaScript and specifically has tremendous value in building caches that can actually leverage and work in harmony JavaScript’s garbage collection (GC) mechanism to maximize efficiency in caching objects in a way that GC can collect cached objects, but cached objects still can be accessed from the up until the point when they collected. Here we introduce the weak-lru-cache package as a high-performance cache that uses weak-referencing values in combination with a LRU/LRFU expiration strategy.

Usage

We have previously written about the power of using weak-referenced maps for the purpose of caching. That previous post gives a good explanation of how a weak-reference-value map works and how it differs from a WeakMap (that uses weak-references for keys). However, this was previously based on a native node module that required C++ code to interact with the garbage collector, and this involved overhead in translating keys from JS values to binary data (std::string) that could be used in the C maps (std::unordered_map). Now that weak-references are available natively in JavaScript (as WeakRef), WeakRef and Map can be combined for a high-performance implementation of weak-valued map that doesn’t require any of the overhead of translation to C structures.

Installing and using weak-lru-cache is very straightforward. npm install it and then import and create an instance:

import { WeakLRUCache } from 'weak-lru-cache';
let myCache = new WeakLRUCache();

The WeakLRUCache is a type of Map that consists of weak-references (WeakRef instances) to values. However, we can directly set values in the cache, and then later to try to get values (if they are still in the cache) with getValue and setValue:

myCache.setValue(3, { greet: 'hello, world' })
// later
myCache.getValue(3) // if still in the cache it will return object above

Strategy

When you add a new object to the cache, weak-lru-cache creates new WeakRef to the object, as a cache entry in its map/cache. The WeakRef will actually start with a strong reference to the object, and the entry will also be added to the LRU/LRFU cache as well. The LRFU cache will track the object, using its multi-segment, generational tracker. If the object is accessed again, in new “generation”, it will be promoted to a higher segment to be protected from immediate expiration. If the object it not accessed again while other objects fill the cache, the object will expire from the LRFU. An entry in a higher segment that is not accessed can be demoted and eventually expired as well.

Once the entry is expired from LRFU, the strong reference is removed, and the entry remains in the cache with only a weak reference until the object is collected. The weak-lru-cache also uses the new FinalizationRegistry to receive notification of when to remove a cache entry from its cache map. This keeps the map properly maintained and cleaned up as entries expire and are collected.

The weak-lru-cache also uses a timer based expiration for the LRFU. Every 10 minutes, up to 1/16 of the cache is expired (and converted to weak references), to help keep the cache from cleaned up.

It is important to note that only objects can be weakly referenced (not primitives like numbers and string). If you do use a primitive value with the weak-lru-cache, it will go into the LRFU cache, and once expired it will be immediately removed from the cache map.

The weak-lru-cache also provides the ability to specify expiration priority. This can be used for indicating that some objects should be expire sooner. For example, larger objects could be given a higher expiration priority in order to constrain the size of the cache. Also a negative expiration priority can be used to force objects to stay in the cache indefinitely (until a higher priority is given). This can be useful if, for example, you want to guarantee that a specific object remains in the cache during some processing. The priority can later be updated when the entry can be subjected to expiration.

Efficient Caching

The weak-lru-cache combines the new capabilities of interacting with garbage collection with a highly efficient, and tunable expiration strategy. By working in synergy with garbage collection, data can be cached longer, remaining accessible while waiting for collection, without taking any extra memory. The weak reference strategy also provides a means of caching objects and guaranteeing only a single copy of an object for a key. And the expiration strategy ensures smart caching is applied, with recent and frequently accessed objects more likely to be cached and readily available.