Implementing a Zero-Allocation S3-FIFO Cache in Node.js

#algorithms #javascript #node #performance

Disclaimer: As a non-native English speaker, I used AI to help translate and structure this article.

Implementing a Zero-Allocation S3-FIFO Cache in Node.js

When building a Node.js backend and reaching for an in-memory cache, lru-cache is the undisputed default choice for almost everyone—and for good reason. It is robust, feature-rich, and heavily proven in production.

However, as datasets grow, LRU algorithms naturally struggle with "one-hit wonders"—items that are requested once and never again. In a standard LRU cache, these items push out frequently accessed data, polluting the cache and dropping your hit rate prematurely.

The S3-FIFO (Simple and Scalable Scan-Resistant FIFO) caching algorithm addresses this fundamental flaw. Rather than being a niche solution, S3-FIFO is a general-purpose caching algorithm that uses a three-queue system to efficiently filter out one-hit wonders.

I built s3fifo to bring this algorithm to the Node.js ecosystem as a highly viable alternative to LRU. Beyond just implementing the algorithm, I built it with a strict performance goal: zero-allocation.

When should you consider `s3fifo`?

High throughput requirements: You need maximum operations per second.
Strict memory constraints: You want to avoid the Garbage Collection (GC) pauses typically associated with traditional object-based caches.
Sparse data access (Low cache coverage): Your total dataset is massive, and your cache can only afford to hold a small fraction of it (e.g., < 10%). In these cases, S3-FIFO's resistance to cache pollution significantly outperforms LRU.

Familiar API

Before diving into the internals, the API is designed to be a drop-in replacement for most standard Maps or LRU implementations:

import { S3Fifo } from "s3fifo";

const cache = new S3Fifo({ max: 1000, ttl: 60000 });
cache.set("key", "value");
cache.get("key"); 
cache.delete("key");

Here is a brief look at the implementation details and the technical reasoning behind them.

1. Avoiding Object Allocation Overhead

Traditional cache implementations often represent items as objects (e.g., linked list nodes with next and prev pointers). While this is simple to implement, creating and destroying thousands of objects per second adds continuous pressure to the V8 Garbage Collector (GC).

To minimize GC pauses, s3fifo uses pre-allocated flat arrays:

this.#meta = new Uint8Array(totalSize);
this.#keys = new Array(totalSize);
this.#values = new Array(totalSize);
this.#starts = new Float64Array(totalSize);
this.#ttls = new Float64Array(totalSize);

Once the cache is instantiated, no new objects are allocated for structural management. Inserting a new item simply writes primitive values and references to an available index in these typed arrays.

2. Array-based Ring Buffers

S3-FIFO requires three queues: Small (S), Main (M), and Ghost (G).
Using standard Array.push() and Array.shift() would be disastrous for performance because shift() runs in O(N) time.

Instead, the queues are implemented as fixed-size Ring Buffers. By enforcing queue sizes to be strict powers of 2, we can replace relatively expensive modulo operations (%) with ultra-fast bitwise AND (&):

// Pushing to a ring buffer
this.container[this.tail] = address;
this.tail = (this.tail + 1) & this.mask; // Bitwise modulo

3. The "Ghost" Ring via Bitwise Flags

The Ghost ring is a core concept in S3-FIFO. It tracks the keys of items recently evicted from the Small ring. If a Ghost key is requested again, it gets promoted directly to the Main ring.

Storing actual keys in a separate queue would require additional memory management. To solve this efficiently, s3fifo tracks states using a single byte (Uint8) in the #meta array:

const META_FREQ_MSK   = 0b00000011; // Lower 2 bits: Frequency (0-3)
const META_STALE_MSK  = 0b00000100; // 3rd bit: Is deleted?
const META_RESI_MSK   = 0b00010000; // 5th bit: Is resident? (1=S/M, 0=Ghost)

When an item is evicted to the Ghost ring, its META_RESI_MSK bit is flipped to 0, and its value reference is cleared for the GC. Structurally, it becomes a "Ghost" without requiring a separate physical node or array shift.

4. O(1) Lazy Deletion

Removing an item from the middle of an array-based ring buffer typically requires shifting elements, which is an O(N) operation.

To avoid this, delete() operations are handled lazily:

this.#meta[address] |= META_STALE_MSK;
this.#addressIndex.delete(key);

The item's META_STALE_MSK bit is flipped to 1, and it is removed from the Map index. The physical slot remains in the ring buffer. When the ring's head pointer eventually reaches this slot during natural eviction, the algorithm notices the stale bit and safely cleans it up in O(1) time.

5. Lazy TTL Evaluation

Supporting Time-To-Live (TTL) in caches often introduces overhead, either through background sweeping timers (setInterval) or complex priority queues.

s3fifo avoids background timers entirely. Expiration is evaluated lazily on get() and lazily cleaned up during natural ring eviction. This ensures that even with complex per-item TTL requirements, the cache remains entirely zero-allocation and lock-free from background processes.

6. Benchmark Results

Here is a comparison with lru-cache using a Zipfian distribution (skew=0.99, pool=100,000) on an AMD Ryzen 7 7700.

Average Hit Rate (%)

Cache Size (% of Pool)	lru-cache	s3fifo
1%	48.90%	58.32%
5%	65.01%	71.14%
25%	82.10%	82.67%

Average Throughput (ops/sec)

Cache Size (% of Pool)	lru-cache	s3fifo
1%	10.0M	15.3M
10%	8.7M	12.5M
50%	9.7M	14.6M

In workloads with low cache coverage (sparse environments), s3fifo provides noticeable improvements in both hit rate and throughput.

Conclusion

While lru-cache is a fantastic general-purpose default, s3fifo offers a modern, scan-resistant alternative with a zero-allocation architecture.

Although the library is fully typed and rigorously tested with 100% test coverage, it is still currently in its v0.1.x stage. I plan to add more features (like async fetching and broader configuration options) in the future.

If you find this approach interesting, give it a try! Contributors, feedback, and PRs are incredibly welcome to help mature the project.

GitHub: https://github.com/BJS-kr/s3fifo
NPM: https://www.npmjs.com/package/s3fifo