Кэш JavaScript localStorage с ограничением по размеру и исключением из числа недавно использовавшихся (LRU)

Question

Я ищу способ сделать в браузере то, что предлагает Memcached, то есть возможность настроить ограничение размера (например, квоту localStorage), и он будет автоматически выселять старые элементы, чтобы ограничить кэш.

Преимущество заключается в том, что явного удаления не требуется, если ключи кеша имеют версии / метки времени. Я видел некоторые библиотеки, которые схожи с ограничением "количество элементов", но ограничение размера было бы более полезным, чтобы оставаться в рамках квоты браузера.

Answer 1

Это не может быть реализовано идеально, потому что нет никаких гарантий относительно того, как браузеры хранят содержимое локального хранилища, но может быть создана достаточно близкая реализация.

Мы можем начать с того факта, что строка в JS представляет собой 16-разрядное целое число без знака (поскольку все хранится в виде строки в localStorage). Это означает, что мы можем легко получить размер любой строки в байтах с content.length * 16 / 8,

Так что теперь нам нужно только создать кеш, который отслеживает размер хранимого контента и размер ключей, под которым он хранит контент.

Очень примитивная и наивная реализация может быть:

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);

Я не реализовал функции для чтения данных, но поскольку ключи хранятся в массиве, вы можете легко реализовать getMostRecent() или getNthRecent(position) или просто простую функцию get(key).

Реализация в Typescript, если вы не знакомы с ним, просто игнорируйте неизвестные части.

Answer 2

Если вы хотите использовать решение, которое уже существует для этой функции, вы можете проверить эту библиотеку runtime-memcache реализуетlru и несколько других схем кеширования (mru, timeout) в javascript.

Он использует модифицированный двусвязный список для достижения O(1) для get, set а также remove.