DEV Community: Armando

Enhancing Cache with Configurable Data Persistence

Armando — Sun, 22 Dec 2024 07:20:12 +0000

Building on the foundations of this guide on creating an in-memory cache, we’ll take it further by introducing configurable data persistence. By leveraging the Adapter and Strategy patterns, we’ll design an extensible system that decouples storage mechanisms from the caching logic, allowing seamless integration of databases or services as needed.

The Vision: Decoupling Like an ORM

The goal is to make the cache extensible without altering its core logic. Inspired by ORM systems, our approach involves a shared API abstraction. This allows storage — such as localStorage, IndexedDB, or even a remote database—to work interchangeably with minimal code changes.

The Storage Adapter Base Class

Here’s the abstract class defining the API for any persistence system:

export abstract class StorageAdapter {
  abstract connect(): Promise<void>;
  abstract add(key: string, value: unknown): Promise<void>;
  abstract get(key: string): Promise<unknown | null>;
  abstract getAll(): Promise<Record<string, unknown>>;
  abstract delete(key: string): Promise<void>;
  abstract clear(): Promise<void>;
}

Any storage solution must extend this base class, ensuring consistency in interaction. For instance, here’s the implementation for IndexedDB:

Example: IndexedDB Adapter

This adapter implements the StorageAdapter interface to persist cache data in an IndexedDB store.

import { StorageAdapter } from './storage_adapter';

/**
 * IndexedDBAdapter is an implementation of the StorageAdapter 
 * interface designed to provide a persistent storage mechanism 
 * using IndexedDB. This adapter can be reused for other cache 
 * implementations or extended for similar use cases, ensuring 
 * flexibility and scalability.
 */
export class IndexedDBAdapter extends StorageAdapter {
  private readonly dbName: string;
  private readonly storeName: string;
  private db: IDBDatabase | null = null;

  /**
   * Initializes the adapter with the specified database and store 
   * names. Defaults are provided to make it easy to set up without 
   * additional configuration.
   */
  constructor(dbName: string = 'cacheDB', storeName: string = 'cacheStore') {
    super();
    this.dbName = dbName;
    this.storeName = storeName;
  }

  /**
   * Connects to the IndexedDB database and initializes it if 
   * necessary. This asynchronous method ensures that the database 
   * and object store are available before any other operations. 
   * It uses the `onupgradeneeded` event to handle schema creation 
   * or updates, making it a robust solution for versioning.
   */
  async connect(): Promise<void> {
    return await new Promise((resolve, reject) => {
      const request = indexedDB.open(this.dbName, 1);

      request.onupgradeneeded = (event) => {
        const db = (event.target as IDBOpenDBRequest).result;
        if (!db.objectStoreNames.contains(this.storeName)) {
          db.createObjectStore(this.storeName, { keyPath: 'key' });
        }
      };

      request.onsuccess = (event) => {
        this.db = (event.target as IDBOpenDBRequest).result;
        resolve();
      };

      request.onerror = () => reject(request.error);
    });
  }

  /**
   * Adds or updates a key-value pair in the store. This method is 
   * asynchronous to ensure compatibility with the non-blocking 
   * nature of IndexedDB and to prevent UI thread blocking. Using 
   * the `put` method ensures idempotency: the operation will 
   * insert or replace the entry.
   */
  async add(key: string, value: unknown): Promise<void> {
    await this._withTransaction('readwrite', (store) => store.put({ key, value }));
  }

  /**
   * Retrieves the value associated with a key. If the key does not 
   * exist, null is returned. This method is designed to integrate 
   * seamlessly with caching mechanisms, enabling fast lookups.
   */
  async get(key: string): Promise<unknown | null> {
    return await this._withTransaction('readonly', (store) =>
      this._promisifyRequest(store.get(key)).then((result) =>
        result ? (result as { key: string; value: unknown }).value : null
      )
    );
  }

  /**
   * Fetches all key-value pairs from the store. Returns an object 
   * mapping keys to their values, making it suitable for bulk 
   * operations or syncing with in-memory caches.
   */
  async getAll(): Promise<Record<string, unknown>> {
    return await this._withTransaction('readonly', (store) =>
      this._promisifyRequest(store.getAll()).then((results) =>
        results.reduce((acc: Record<string, unknown>, item: { key: string; value: unknown }) => {
          acc[item.key] = item.value;
          return acc;
        }, {})
      )
    );
  }

  /**
   * Deletes a key-value pair by its key. This method is crucial 
   * for managing cache size and removing expired entries. The 
   * `readwrite` mode is used to ensure proper deletion.
   */
  async delete(key: string): Promise<void> {
    await this._withTransaction('readwrite', (store) => store.delete(key));
  }

  /**
   * Clears all entries from the store. This method is ideal for 
   * scenarios where the entire cache needs to be invalidated, such 
   * as during application updates or environment resets.
   */
  async clear(): Promise<void> {
    await this._withTransaction('readwrite', (store) => store.clear());
  }

  /**
   * Handles transactions in a reusable way. Ensures the database 
   * is connected and abstracts the transaction logic. By 
   * centralizing transaction handling, this method reduces 
   * boilerplate code and ensures consistency across all operations.
   */
  private async _withTransaction<T>(
    mode: IDBTransactionMode,
    callback: (store: IDBObjectStore) => IDBRequest | Promise<T>
  ): Promise<T> {
    if (!this.db) throw new Error('IndexedDB is not connected');
    const transaction = this.db.transaction([this.storeName], mode);
    const store = transaction.objectStore(this.storeName);
    const result = callback(store);
    return result instanceof IDBRequest ? await this._promisifyRequest(result) : await result;
  }

  /**
   * Converts IndexedDB request events into Promises, allowing for 
   * cleaner and more modern asynchronous handling. This is 
   * essential for making IndexedDB operations fit seamlessly into 
   * the Promise-based architecture of JavaScript applications.
   */
  private async _promisifyRequest<T>(request: IDBRequest): Promise<T> {
    return await new Promise((resolve, reject) => {
      request.onsuccess = () => resolve(request.result as T);
      request.onerror = () => reject(request.error);
    });
  }
}

Integrating the Adapter into the Cache

The cache accepts an optional StorageAdapter. If provided, it initializes the database connection, loads data into memory, and keeps the cache and storage in sync.

private constructor(capacity: number, storageAdapter?: StorageAdapter) {
  this.capacity = capacity;
  this.storageAdapter = storageAdapter;

  if (this.storageAdapter) {
    this.storageAdapter.connect().catch((error) => {
      throw new Error(error);
    });

    this.storageAdapter.getAll().then((data) => {
      for (const key in data) {
        this.put(key, data[key] as T);
      }
    }).catch((error) => {
      throw new Error(error);
    });
  }

  this.hash = new Map();
  this.head = this.tail = undefined;

  this.hitCount = this.missCount = this.evictionCount = 0;
}

Why Adapter and Strategy Patterns?

Using the Adapter pattern:

Decouples the cache from specific storage mechanisms.
Ensures extensibility for new storage backends.

Combining with the Strategy pattern:

Enables runtime selection of the persistence layer.
Simplifies testing by mocking different adapters.

Key Design Practices

Abstract API: Keeps the cache logic agnostic of storage details.
Singleton Cache: Ensures shared state consistency.
Async Initialization: Avoids blocking operations during setup.
Lazy Loading: Only loads persisted data when a storage adapter is provided.

Next Steps

This design is robust but leaves room for enhancements:

Optimize sync logic for better performance.
Experiment with additional adapters like Redis or SQLite.

Try It Out! 🚀

If you’d like to test the cache in action, it’s available as an npm package: adev-lru. You can also explore the full source code on GitHub: adev-lru repository. I welcome any recommendations, constructive feedback, or contributions to make it even better! 💡

Happy coding! 🚀

How to Create an In-Memory Cache

Armando — Wed, 18 Dec 2024 14:14:04 +0000

In many projects, I’ve noticed that while a cache could be handy — especially on the client side— it’s often overlooked. Client-side caching is critical in enhancing user experience by reducing latency and offloading repeated server requests. For example, in applications with infinite scrolling or frequently updated dashboards, caching previously fetched data prevents unnecessary API calls, ensuring smoother interactions and faster rendering times.

In one of my recent projects, implementing a cache reduced API call volume by over 40%, leading to noticeable performance improvements and cost savings. This underlines why client-side caching should be considered a foundational optimization strategy. A cache tends to be one of the last features considered, despite its significant impact on performance with relatively simple implementation, whether due to development time constraints or other priorities.

A cache can be implemented at various levels in architecture: from backend caching using Redis, a CDN for static content, to an in-memory cache on the client or even using localStorage or IndexedDB for persistency. Ideally, these strategies should be combined to reduce the load and cost of databases and APIs, as well as the lag from client-server requests, especially for data that has already been fetched before.

In this article, we’ll explore how to design and implement an LRU (Least Recently Used) cache with TTL (Time-to-Live) support in JavaScript, creating a package similar to my adev-lru. By the end, you’ll have a working example that showcases the core principles and functionality of an effective caching solution.

What is an LRU Cache?

An LRU (Least Recently Used) cache ensures that the most recently accessed items remain in memory while evicting the least recently accessed ones when their capacity is exceeded. This strategy works by maintaining an order of usage: each accessory updates the item’s position in the cache, with the least accessed items being removed first.

Compared to other caching strategies, LRU balances simplicity and efficiency, making it well-suited for scenarios where recent usage is a reliable indicator of future access. For example, applications that cache API responses, thumbnails, or frequently accessed user preferences can leverage LRU to reduce redundant fetch operations without over-complicating the eviction process.

Unlike LFU (Least Frequently Used), which tracks access frequency and requires additional bookkeeping, LRU avoids this complexity while still achieving excellent performance in many real-world use cases. Similarly, FIFO (First In, First Out) and MRU (Most Recently Used) offer alternative eviction policies but may not align as well with usage patterns where recent activity is critical. By combining LRU with TTL (Time-to-Live) support in my implementation, it also handles scenarios where data needs automatic expiration, further enhancing its applicability in dynamic environments like live dashboards or streaming services. It’s especially useful in applications where access to the most recent data is critical.

Implementation

The LRUCache class is built to be efficient, support flexible configurations, and handle automatic evictions. Below are some key methods:

Creating the Cache

public static getInstance<T>(capacity: number = 10): LRUCache<T> {
    if (LRUCache.instance == null) {
        LRUCache.instance = new LRUCache<T>(capacity);
    }
    return LRUCache.instance;
}

This method ensures there is only one instance of the cache in the application, a design choice that simplifies resource management. By implementing the cache as a singleton, we avoid redundant memory usage and ensure consistent data across the application. This is particularly valuable in scenarios where multiple components or modules need access to the same cached data, as it prevents conflicts and ensures synchronization without requiring additional coordination logic. If no capacity is specified, it defaults to 10.

Adding an Item to the Cache

public put(key: string, value: T, ttl: number = 60_000): LRUCache<T> {
    const now = Date.now();
    let node = this.hash.get(key);
    if (node != null) {
        this.evict(node);
    }
    node = this.prepend(key, value, now + ttl);
    this.hash.set(key, node);
    if (this.hash.size > this.capacity) {
        const tailNode = this.pop();
        if (tailNode != null) {
            this.hash.delete(tailNode.key);
        }
    }
    return this;
}

This method adds or updates an item in the cache. When a key already exists, its corresponding item is evicted and re-added at the front of the cache. To do this the cache uses a Doubly Linked List to save the data as nodes and maintain the ability to delete data from the end of the list — Tail— and move it to the beginning of the list — Head —, to guarantee a constant O(1) read of every node’s data a Hash Table is used to save a pointer to each node of the list. This process aligns with the LRU principle by ensuring that recently accessed items are always prioritized, effectively marking them as “most recently used.” By doing so, the cache maintains an accurate order of usage, which is critical for making eviction decisions when the capacity is exceeded. This behavior ensures that resources are optimally managed, minimizing the retrieval time for frequently accessed data. If the key already exists, the item is moved to the front to mark it as recently used.

Retrieving an Item from the Cache

public get(key: string): T | undefined {
    const node = this.hash.get(key);
    const now = Date.now();
    if (node == null || node.ttl < now) {
        return undefined;
    }
    this.evict(node);
    this.prepend(node.key, node.value, node.ttl);
    return node.value;
}

This method retrieves stored items. If the item has expired, it is removed from the cache.

Performance Metrics

To evaluate the cache’s efficiency, I implemented performance metrics like hit rate, misses, and evictions:

private getHitRate(): number {
    const totalRequests = this.hitCount + this.missCount;
    return totalRequests === 0 ? 0 : this.hitCount / totalRequests;
}

Clearing the Cache

public clear(): void {
    this.hash.clear();
    this.head = this.tail = undefined;
}

This method clears all items and resets the cache state.

In my implementation, I have also added other methods like getOption which instead of returning T | undefined it return an instance of the monad Option for those who prefer a more functional approach. I also added a Writer monad to track every operation on the cache for logging purposes.

You can see all the other methods involved in this algorithm, very well commented, on this repository: https://github.com/Armando284/adev-lru

Comparing Cache Algorithms

An LRU cache is not the only option. Choosing the right caching algorithm depends heavily on the application’s specific requirements and access patterns. Below is a comparison of LRU with other commonly used caching strategies and guidance on when to use each:

LFU (Least Frequently Used): This algorithm evicts items that are accessed the least number of times. It’s ideal for scenarios where usage frequency over time is a better predictor of future access than recency. However, it typically requires additional bookkeeping to track access counts, making it more complex and computationally expensive than LRU. Use LFU for applications like recommendation engines or machine learning pipelines where historical usage patterns are critical.
FIFO (First In, First Out): This approach removes the oldest items, regardless of how often they are accessed. While it is simple to implement, FIFO might not be suitable for most use cases as it doesn’t consider usage patterns. It can work for applications with fixed, predictable workflows, such as caching static configurations or preloaded assets.
MRU (Most Recently Used): MRU evicts the most recently accessed items, the opposite of LRU. This strategy is best suited for situations where older data is more likely to be reused, such as rollback systems or certain types of undo operations.

When to Use LRU

LRU strikes a balance between simplicity and effectiveness, making it ideal for applications where recent activity correlates strongly with future use. For instance:

Web and API Caching: LRU is well-suited for reducing redundant API calls, especially in scenarios like paginated views, infinite scrolling, or frequent polling of live data.
Multimedia Applications: Cache recently played or viewed items like videos or images.
UI State Management: Store recently accessed component states to improve rendering performance.

In contrast, if access patterns show that frequency or insertion order is more relevant, algorithms like LFU or FIFO might be a better choice. Evaluating these trade-offs ensures that the caching strategy aligns with your application’s goals and resource constraints.

LFU (Least Frequently Used): Removes the least accessed items based on frequency.
FIFO (First In, First Out): Evicts the oldest item, regardless of recent usage.
MRU (Most Recently Used): Removes the most recently added items, contrary to LRU.

Conclusion

Implementing an in-memory cache can significantly enhance an application’s performance, reducing response times and improving user experience.

If you want to see a full LRU Cache in action you can use my npm package https://www.npmjs.com/package/adev-lru I would also love to get your feedback to keep improving it.

Try the package and share your thoughts or contribute if you feel like helping more 😁!