В чем разница между стратегиями кэширования?

Разница между стратегиями кэширования

Кэширование — это техника сохранения часто используемых данных для быстрого доступа. Существует несколько стратегий кэширования, каждая с преимуществами и недостатками. Рассмотрим основные.

1. LRU (Least Recently Used)

LRU — вытесняет наименее недавно использованные данные при переполнении кэша.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // Map сохраняет порядок
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    
    // Переместить в конец (самый свежий)
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // Удалить самый старый элемент
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    
    this.cache.set(key, value);
  }
}

// Использование
const cache = new LRUCache(2);
cache.put('a', 1); // кэш: {a: 1}
cache.put('b', 2); // кэш: {a: 1, b: 2}
cache.get('a');    // кэш: {b: 2, a: 1} — 'a' переместился в конец
cache.put('c', 3); // кэш: {a: 1, c: 3} — 'b' был вытеснен

Характеристики LRU:

• Вытесняет наименее недавно использованные данные
• Хорошо работает когда есть локальность доступа
• Средняя сложность: O(1) для get/put
• Подходит для браузерного кэша, CPU кэша

2. LFU (Least Frequently Used)

LFU — вытесняет наименее часто используемые данные.

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();        // key -> value
    this.frequency = new Map();    // key -> количество обращений
    this.minFreq = 0;
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    
    // Увеличить частоту
    const freq = this.frequency.get(key) || 0;
    this.frequency.set(key, freq + 1);
    return this.cache.get(key);
  }

  put(key, value) {
    if (this.capacity <= 0) return;
    
    // Если ключ существует, обновить
    if (this.cache.has(key)) {
      this.cache.set(key, value);
      const freq = this.frequency.get(key) || 0;
      this.frequency.set(key, freq + 1);
      return;
    }
    
    // Если кэш переполнен, удалить наименее используемый
    if (this.cache.size >= this.capacity) {
      let minKey = null;
      let minFreq = Infinity;
      
      for (let k of this.cache.keys()) {
        const freq = this.frequency.get(k) || 0;
        if (freq < minFreq) {
          minFreq = freq;
          minKey = k;
        }
      }
      
      this.cache.delete(minKey);
      this.frequency.delete(minKey);
    }
    
    // Добавить новый элемент
    this.cache.set(key, value);
    this.frequency.set(key, 1);
  }
}

// Использование
const cache = new LFUCache(2);
cache.put('a', 1);
cache.put('b', 2);
cache.get('a'); // 'a' используется чаще
cache.put('c', 3); // 'b' будет вытеснен, так как используется реже

Характеристики LFU:

• Вытесняет наименее часто используемые данные
• Хорошо для долгосрочных паттернов
• Высокая сложность: O(1) амортизированная
• Подходит для веб-кэша, объектных БД

3. FIFO (First In, First Out)

FIFO — вытесняет первый добавленный элемент (как очередь).

class FIFOCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.queue = [];
    this.cache = new Map();
  }

  get(key) {
    return this.cache.get(key) ?? -1;
  }

  put(key, value) {
    // Если ключ существует, просто обновить
    if (this.cache.has(key)) {
      this.cache.set(key, value);
      return;
    }
    
    // Если кэш переполнен, удалить первый элемент
    if (this.cache.size >= this.capacity) {
      const firstKey = this.queue.shift();
      this.cache.delete(firstKey);
    }
    
    this.queue.push(key);
    this.cache.set(key, value);
  }
}

// Использование
const cache = new FIFOCache(2);
cache.put('a', 1); // очередь: [a]
cache.put('b', 2); // очередь: [a, b]
cache.put('c', 3); // очередь: [b, c] — 'a' удалён как первый

Характеристики FIFO:

• Вытесняет первый добавленный элемент
• Простая реализация: O(1) для всех операций
• Не учитывает частоту использования
• Подходит для простых потоков данных, очередей

4. TTL (Time To Live)

TTL — вытесняет данные по времени истечения, независимо от использования.

class TTLCache {
  constructor(defaultTTL = 60000) { // По умолчанию 60 сек
    this.cache = new Map();
    this.defaultTTL = defaultTTL;
  }

  set(key, value, ttl = this.defaultTTL) {
    const expiresAt = Date.now() + ttl;
    this.cache.set(key, { value, expiresAt });
  }

  get(key) {
    const item = this.cache.get(key);
    
    if (!item) return -1;
    
    // Проверить, истекло ли время
    if (Date.now() > item.expiresAt) {
      this.cache.delete(key);
      return -1;
    }
    
    return item.value;
  }
}

// Использование
const cache = new TTLCache(5000); // 5 секунд
cache.set('a', 'значение');
console.log(cache.get('a')); // 'значение'

setTimeout(() => {
  console.log(cache.get('a')); // -1 (истекло)
}, 6000);

Характеристики TTL:

• Данные удаляются по истечении времени
• Полезно для сессии, токены
• Средняя сложность: требует проверки времени
• Подходит для HTTP кэша (Cache-Control: max-age)

5. Random Replacement (RR)

Random Replacement — удаляет случайный элемент при переполнении.

class RandomCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.set(key, value);
      return;
    }
    
    if (this.cache.size >= this.capacity) {
      // Удалить случайный элемент
      const randomKey = Array.from(this.cache.keys())[
        Math.floor(Math.random() * this.cache.size)
      ];
      this.cache.delete(randomKey);
    }
    
    this.cache.set(key, value);
  }
}

Характеристики RR:

• Простая реализация
• Не учитывает паттерны доступа
• Используется редко в реальных системах

Сравнительная таблица

Практический пример: Кэширование API результатов

class APICache {
  constructor(strategy = 'lru', capacity = 10) {
    this.strategy = strategy;
    this.capacity = capacity;
    this.cache = new Map();
    this.frequency = new Map();
  }

  async fetchWithCache(url) {
    // Проверить кэш
    if (this.cache.has(url)) {
      if (this.strategy === 'lfu') {
        this.frequency.set(url, (this.frequency.get(url) || 0) + 1);
      }
      return this.cache.get(url);
    }
    
    // Получить данные
    const response = await fetch(url);
    const data = await response.json();
    
    // Добавить в кэш
    if (this.cache.size >= this.capacity) {
      // Удалить в зависимости от стратегии
      const keyToDelete = this.strategy === 'lru'
        ? Array.from(this.cache.keys())[0]
        : Array.from(this.frequency.entries())
            .sort((a, b) => a[1] - b[1])[0][0];
      
      this.cache.delete(keyToDelete);
    }
    
    this.cache.set(url, data);
    if (this.strategy === 'lfu') {
      this.frequency.set(url, 1);
    }
    
    return data;
  }
}

// Использование
const apiCache = new APICache('lru', 5);
const data = await apiCache.fetchWithCache('/api/users');

Выбор стратегии

• LRU: когда важен последний доступ (браузер)
• LFU: когда важна частота использования (долгосрочные паттерны)
• FIFO: для простых потоков и очередей
• TTL: для экспираций (сессии, токены)
• RR: редко, только если нужна рандомизация