Cache JavaScript localStorage avec taille limite et éviction LRU (least-recently used)

Question

Je cherche un moyen de faire dans le navigateur ce que Memcached offre, c'est-à-dire la possibilité de configurer une limite de taille (par exemple le quota localStorage) et il expulsera automatiquement les anciens éléments pour maintenir le cache sous la limite.

L'avantage est qu'il n'est jamais nécessaire de procéder à des suppressions explicites, tant que les clés du cache sont versionnées et horodatées. J'ai vu certaines bibliothèques qui font la même chose avec une limite de "nombre d'éléments", mais la limite de taille serait plus utile pour rester sous le quota du navigateur.

Answer 1

Cela ne peut pas être mis en œuvre parfaitement, car il n'y a aucune garantie sur la façon dont les navigateurs stockent le contenu du stockage local, mais une mise en œuvre suffisamment proche peut être créée.

Nous pouvons partir du fait qu'une chaîne en JS est une Valeur entière non signée de 16 bits (parce que tout est stocké sous forme de chaîne dans le localStorage ). Cela signifie que nous pouvons facilement obtenir la taille de n'importe quelle chaîne en octets avec content.length * 16 / 8 .

Il ne nous reste donc plus qu'à créer un cache qui suit la taille du contenu stocké et la taille des clés sous lesquelles il stocke le contenu.

Une implémentation très primitive et naïve pourrait être :

class Cache {

  private keyStoreKey: string;
  private cacheSizeKey: string;

  /**
   * List of the keys stored in this cache.
   */
  private storedKeys: string[] = [];

  /**
   * The size of the stored values in bytes
   */
  private cacheSize: number = 0;

  constructor(
    private prefix: string, 
    private sizeLimit: number,
  ) {
    if(this.sizeLimit < 100) {
      // the minimal size of the cache is 24 + prefix, otherwise, it would enter 
      // a loop trying to remove every element on any insert operation.
      throw new Error('Cache size must be above 100 bytes');
    }

    this.keyStoreKey = `${prefix}:k`;
    this.cacheSizeKey = `${prefix}:s`;

    this.cacheSize = localStorage.getItem(this.cacheSizeKey) ? Number.parseInt(localStorage.getItem(this.cacheSizeKey)) : 0;
    this.storedKeys = localStorage.getItem(this.keyStoreKey) ? localStorage.getItem(this.keyStoreKey).split(',') : [];
  }

  /**
   * The size of the keys in bytes
   */
  public get keyStoreSize() {
    return this.calculateLenght(this.storedKeys.join(`${this.prefix}:v:,`));
  }

  public get totalUsedSize() {
    return this.cacheSize + this.keyStoreSize + this.calculateLenght(this.keyStoreKey) + this.calculateLenght(this.cacheSizeKey);
  }

  /**
   * Returns the size of the given string in bytes.
   * 
   * The ECMAScript specification defines character as single 16-bit unit of UTF-16 text
   */
  private calculateLenght(content: string): number {
    return content.length * 16 / 8;
  }

  /**
   * Saves an item into the cahce.
   * 
   * NOTE: name cannot contain commas.
   */
  public set(name: string, content: string) {
    const newContentSize = this.calculateLenght(content);

    if(!(this.storedKeys).some(storedName => storedName === name)) {
      this.storedKeys.unshift(name);

      this.cacheSize += newContentSize;
    } else {
      this.storedKeys = this.storedKeys.filter(n => n !== name);
      this.storedKeys.unshift(name);      

      const oldContentSize = this.calculateLenght(localStorage.getItem(`${this.prefix}:v:${name}`));

      this.cacheSize = this.cacheSize - oldContentSize + newContentSize;
    }

    while(this.totalUsedSize > this.sizeLimit && this.storedKeys.length > 0) {
      this.removeOldestItem();
    }

    localStorage.setItem(this.cacheSizeKey, this.cacheSize.toString());  
    localStorage.setItem(`${this.prefix}:debug:totalSize`, this.totalUsedSize.toString());  
    localStorage.setItem(this.keyStoreKey, this.storedKeys.join(','));
    localStorage.setItem(`${this.prefix}:v:${name}`, content);
  }

  /**
   * The oldest item is the last in the stored keys array
   */
  private removeOldestItem() {
    const name = this.storedKeys.pop();
    const oldContentSize = this.calculateLenght(localStorage.getItem(`${this.prefix}:v:${name}`));

    this.cacheSize -= oldContentSize;

    localStorage.removeItem(`${this.prefix}:v:${name}`);
  }
}

window['cache'] = new Cache('test', 200);

Je n'ai pas implémenté les fonctions de lecture des données, mais comme les clés sont stockées dans un tableau, vous pouvez facilement implémenter une fonction getMostRecent() ou getNthRecent(position) ou simplement une fonction get(key).

La mise en œuvre est en Tapuscrit si vous n'êtes pas familier avec le système, ignorez les parties inconnues.

Answer 2

Si vous souhaitez utiliser une solution qui existe déjà pour cette fonctionnalité, vous pouvez consulter cette bibliothèque. runtime-memcache met en œuvre lru et quelques autres systèmes de mise en cache( mru , timeout ) en javascript.

Il utilise une liste modifiée Doubly Linked List pour atteindre O(1) pour get , set y remove .