fifo-ttl-cache

The FIFOCache class provides a First-In-First-Out (FIFO) caching mechanism with a fixed Time-To-Live (TTL), ensuring automatic removal of outdated entries.

Unlike the widely used LRU Cache, a FIFO Cache does not prioritize keeping popular keys cached for extended durations. This simplicity reduces implementation overhead and generally offers faster response times. FIFO caches are particularly well-suited for scenarios where:

• Short-term key popularity: Useful for situations where certain keys experience brief periods of higher activity (e.g., a 15-minute spike). For instance, in a background service aggregating data from a customer’s IoT sensors, caching customer details during the aggregation process enhances performance without compromising data relevance.
• Uniform key distribution: Effective when key popularity is relatively consistent and predictable.
• Freshness of values is critical: Ideal for security-sensitive use cases or environments where up-to-date data is essential.
• The cache size closely matches the total number of potential keys: In scenarios where most of the possible keys are already cached, eviction due to limited capacity becomes negligible. As a result, the key-reordering mechanism of an LRU Cache offers little benefit and adds unnecessary overhead.

Table of Contents :bookmark_tabs:

• Key Features
• API
• Getter Methods
• Eviction Policy
• Event-Driven Eviction
• JavaScript's Map
• Use Case Example: Real-Time User Session Verification
• License

Key Features :sparkles:

• FIFO Cache: Automatically evicts the oldest entry (based on insertion time) when the cache reaches its capacity and a new entry with a non-existing key is added, irrespective of the entry’s popularity.
• Fixed TTL: Ensures all cached entries share the same Time-to-Live (TTL) duration, allowing for automatic eviction of stale entries.
• Efficiency :gear:: JavaScript's Map maintains the insertion order of keys, offering a reliable and often overlooked guarantee for iteration. This guarantee is leveraged in FIFOCache to eliminate the need for manually managing insertion order for eviction purposes.
• Comprehensive Documentation :books:: The class is thoroughly documented, enabling IDEs to provide helpful tooltips that enhance the coding experience.
• Tests :test_tube:: Fully covered by comprehensive unit tests.
• TypeScript support.
• No external runtime dependencies: Only development dependencies are used.
• ES2020 Compatibility: The tsconfig target is set to ES2020, ensuring compatibility with ES2020 environments.

API :globe_with_meridians:

The FIFOCache class provides the following methods:

• set: Adds or updates a key-value pair in the cache.
• get: Retrieves the value associated with the specified key, provided the key exists in the cache and its TTL has not expired.
• has: Determines whether the cache contains a valid, non-expired entry for the specified key. This method is particularly useful when the cache is employed as a Set-like structure, where the presence of a key is significant but the associated value is secondary or unnecessary.
• delete: Removes the cached entry associated with the specified key, if such a entry exists in the cache.
• clear: Removes all entries from the cache, leaving it empty.

If needed, refer to the code documentation for a more comprehensive description.

Getter Methods :mag:

The FIFOCache class provides the following getter methods to reflect the current state:

• size: The number of items currently stored in this instance.
• isEmpty: Indicates whether the cache does not contain any entries.

To eliminate any ambiguity, all getter methods have O(1) time and space complexity.

Eviction Policy :wastebasket:

Cache entries are evicted under the following conditions:

• The cache reaches its maximum capacity: The oldest key (based on insertion time) is removed.
• A key's value becomes outdated (its TTL has expired).

Event-Driven Eviction :dart:

The eviction policy of this class is event-driven, avoiding periodic callbacks for removing outdated entries. Instead, outdated keys are removed under the following circumstances:

• During a set operation: If adding a new entry exhausts the maximum allowed capacity, the oldest key (based on insertion time) is evicted.
• During a get operation: Outdated keys are validated and removed to prevent returning stale cached values.

While some cache variants employ actively scheduled eviction for each entry, this approach has notable drawbacks:

• Time Complexity Impact: Each setTimeout adds a task to Node.js's internal priority queue for scheduled events. When a large number of timers exist, managing this queue (e.g., inserting and removing timers) incurs additional overhead due to the logarithmic time complexity of queue operations.
• Event Loop Latency: A surge of timers firing simultaneously or in rapid succession can degrade event loop performance, delaying critical operations such as I/O processing and other asynchronous tasks.
• Space Complexity Impact: Each setTimeout occupies memory in the heap for its context and execution details. A cache with many entries can thus lead to significant memory consumption, which may not scale well in high-throughput or resource-constrained environments.
• GC Pressure: The existence of many timers increases garbage collection pressure because timers hold references to their associated data. These references can lead to delayed memory reclamation, particularly if the timers expire over a long period.

Periodic eviction of stale batches is another non-event-driven strategy often employed in FIFO caches, as insertion order simplifies batch identification. However, it is prone to retaining stale entries longer than necessary and can cause latency spikes during batch processing, making it less suitable for time-sensitive or high-demand applications.

Overall, the event-driven strategy ensures true O(1) eviction while avoiding indirect overhead on Node.js's internal structures.

JavaScript's Map :world_map:

JavaScript's Map maintains the insertion order of keys, offering a reliable and often overlooked guarantee for iteration. This guarantee is leveraged in FIFOCache to eliminate the need for manually managing insertion order for eviction purposes.

For details, refer to the MDN documentation:
"The Map object holds key-value pairs and remembers the original insertion order of the keys".

Use Case Example: Real-Time User Session Verification :key:

In high-traffic environments, maintaining the validity of user sessions is crucial for ensuring security and responsiveness. A FIFO cache is ideal for this scenario as it keeps only the freshest session data, ensuring that outdated or expired sessions are automatically evicted without complex prioritization. This approach is particularly effective when session popularity spikes periodically, such as during login events or bursts of user activity.

Below is an example of a UserSessionVerifier class leveraging a FIFO cache for efficient session management:

1import { FIFOCache } from 'fifo-ttl-cache';
2import { SessionVerifierOptions, SessionMetadata } from './user-session-interfaces';
3
4class UserSessionVerifier {
5  // Maps session IDs to their associated metadata.
6  private readonly _sessionCache: FIFOCache<string, SessionMetadata>;
7
8  constructor(options: Readonly<SessionVerifierOptions>) {
9    const { maxCapacity, ttlMs } = options;
10    this._sessionCache = new FIFOCache<string, SessionMetadata>(maxCapacity, ttlMs);
11  }
12
13  public async getMetadata(sessionId: string): SessionMetadata {
14    const cachedMetadata = this._sessionCache.get(sessionId);
15
16    if (cachedMetadata) {
17      return cachedMetadata;
18    }
19
20    try {
21      // Fetch and validate metadata from an external source (e.g., database, API)
22      const metadata = await this._fetchMetadata(sessionId);
23      this._sessionCache.set(sessionId, metadata);
24      return metadata;
25    } catch (err) {
26      throw new SessionValidationError(
27        `Failed validating sessionId ${sessionId}. Reason: ${err.message}`
28      );
29    }
30  }
31
32  public clearCache(): void {
33    this._sessionCache.clear();
34  }
35
36  private async _fetchMetadata(sessionId: string): Promise<SessionMetadata> {
37    // Logic to validate and fetch metadata from an external source goes here.
38  }
39}

License :scroll:

Apache 2.0