lru-cache

A Javascript LRU-cache for node and/or browser, featuring:

• LRU cache logic
• Alternate keys
• Value getter for cache fails
• Singleton caches per value type
• Event registry for cache change events
• No dependencies

Table of Contents

1. What’s New
2. Installation
3. Motivation
4. Basic Usage
5. Quality
6. Develop
7. Detailed Usage
8. Performance
9. Questions
10. Roadmap

" class="reference-link">What’s New

Version 3.2.0

• LruCache methods get and getWithoutLruChange now take custom entry getter as optional third argument.
  • If provided, a custom entry getter takes precedence over one set by setEntryGetter

Version 3.1.0

• New LruCache method setEntryGetter
  • Use it to set a function that provides a key-value-alternateKeys object (as expected by set)
  • If in a call to get or getWithoutLruChange, the given key is not in the cache and an entryGetter is set, then the entry getter will be called
    • In case of a synchronous entry getter, the returned entry will be inserted into the cache and the value is returned to the caller of the get method
    • In case of an asynchronous entry getter, a Promise will be returned to the caller of the get method
      • Subsequent calls to get or getWithoutLruChange will return the same Promise, until it is resolved
      • The Promise resolves to the entry.value returned by the entry getter
      • After the Promise resolved, the entry will be in the cache
• New LruCache method has
  • To test if a key or alternate key is in the cache
  • Prior to 3.1.0, getWithoutLruChange could be used in all cases to test if a value is already cached. However, now the has method might be mandatory to do so in case an entry getter was set.

" class="reference-link">Installation

npm install --save @swarmy/lru-cache

" class="reference-link">Motivation

There are for sure more than a handful of different LRU-cache implementations flying around on npm.

What makes this one unique is that it features the use of alternate keys and an event registry for cache change events.

Alternate keys are useful in situations where certain cache consumers have no access to the primary key, or would have to construct or fetch the primary key in advance.

Cache events are useful to have a central point to handle object changes in an application with multiple models. E.g. register all models as listeners and ensure that all entity updates and deletes go over the cache. Than you can ensure that each update or delete of a certain entity, be it due to a change coming from a certain controller or due to a server push, will keep all models in sync. I have applications where I have no need to cache for performance reasons, but still use this pattern to keep my Redux state up to date (by having a single cache listener that dispatches a corresponding action).

" class="reference-link">Basic Usage

Caching

import {getCache} from "@swarmy/lru-cache";
// If you use in nodejs and prefer the old-fashioned way:
// var getCache = require("@swarmy/lru-cache").getCache;
...
const userCache = getCache("User");
userCache.set(user.id, user);
...
let user = userCache.get(userId);
if (!user) {
    user = await fetchUser(userId);
}
...

• For the same value type (here “User”), getCache will always return the same cache instance.
• For detailed description of all cache methods, have a look at
  • Detailed Usage
  • JSDoc

Cache Events

To register for all cache change events

import {registerCacheChangedHandler} from "@swarmy/lru-cache";
registerCacheChangedHandler(changeObject => {
    console.log("changes:", changeObject);
});

• For detailed description of all cache methods, have a look at
  • Detailed Usage
  • JSDoc

" class="reference-link">Quality

• Test results
• Test coverage
• Performance tests

" class="reference-link">Develop

git clone https://github.com/gneu77/lru-cache.git
cd lru-cache
npm install
// no you can do:
npm run build
npm run test
npm run test-performance
npm run generate-doc

" class="reference-link">Detailed Usage

" class="reference-link">Caching

The following 4 functions can be imported from lru-cache:

LruCache has the following methods:

" class="reference-link">Cache Events

• Especially in more complex UIs, there might be multiple models holding the same type of entity.
• If an entity gets updated, you need a strategy to ensure all models get updated correspondingly.
• Of course the developer implementing the update should not be required to know all models of all screens that might hold an entity of this type
  • Even if he would know them it would be a nightmare, if he had to update all the models
  • Even if he would update all the models, as soon as another developer changes one of the models half a year later, or adds a new model, the application would be broken
• Like always in programming there are many different approaches to this problem. The event-based approach described here is just one of them (not necessarily the best, but if you need caching anyways, then it’s handy to combine this):
  • Whenever an updated entity is retrieved, it is put into the cache, leading to a corresponding cache event
  • Whenever an entity is deleted, delete is also called on the cache, leading to a corresponding cache event
  • Whenever a new model is implemented, it is registered for cache events for the object types it is holding
  • Whenever a model receives a cache event, it can check whether it must replace or remove an entity

Here is the structure of the cache change event argument:

{
    valueTypes: Set(),
    <valueType>: {
        inserts: [{key, value, alternateKeys, order}],
        clearRemoves: [{key, value, alternateKeys, order}],
        lruRemoves: [{key, value, alternateKeys, order}],
        deleteRemoves: [{key}],
    },
    ...
}

• The order can be used to determine, if an insert happened before or after a remove.
• Note that by default, lruRemoves and clearRemoves are empty (usually these removes are not of any interest)
• In case of a cache delete, the corresponding entity might not have been in the cache (being removed in a clear or by LRU logic).
  • Thus, deleteRemoves only contain the key of the deleted entity.
  • For the same reason, the delete method cannot be used with an alternate key, because there would be no way to tell if the given argument is key or alternate key

" class="reference-link">Performance

• Compared to a native Javascript Map, the LRU logic implies performance impact on get, set and delete. It’s just the price to pay for having a LRU cache.
• Also compared to LRU maps that do not support alternate keys, there is a performance impact on get in case of cache misses.
  • See Performance tests
  • However, get, set and delete are still O(1). (setMaxSize has O(size-newMaxSize), if size>newMaxSize)
• Compared to a LRU cache without cache events, there is additional performance impact on get, set and delete.
  • Again see Performance tests
  • However, if you are caching for performance, then because the fetching of values is significantly more time consuming. So whether you save 400ms or only 399ms hardly makes a difference here.
  • If you are not caching for performance reasons, but to have the change events, well than again it’s just the price to pay for the event handling.

" class="reference-link">Questions

Why can I not differentiate between insert and update in the change events?

Garbage collected languages without weak references make the use of some patterns impossible. Two of these patterns affect this library:

1. One cannot implement an instance-cache, hence a cache that ensures to not discard an entry, as long as this entry is referenced from somewhere outside the cache. If upon calling the set method, the value is not already in the cache, there is no way to tell, if it was never there, or if it was there an has been LRU discarded.
2. One cannot implement event registries that reference listeners only weakly. Thus, it is up to the consumker of this library to ensure that no memory leaks occur due to not unregistered event listeners.

Why can I not just have a sorted list with all changes in the cache event, instead of sorting myself by order attribute?

• I just did not want to further increase the size of change object by another array holding redundant data.
• However, maybe in a future version, I will make it configurable to optionally include such a list.

" class="reference-link">Roadmap

3.2.x

• Fix issues that might occur
• Improve README
• Bring test coverage two 100%
• Add further performance tests

3.3.0

• Add option to use LruMap instead of LruCache (the LruMap is a currently not exported pure LRU cache, while the LruCache is a wrapper adding the event handling)

3.4.0

• Make shape and content of change events configurable (with the current shape being used as default).