System Design структуры данных (LRU, Bloom Filter, Consistent Hashing, LSM)

System Design собеседование редко требует написать сложный алгоритм с нуля, но обязательно проверяет понимание базовых структур данных, на которых построены кэши, БД, очереди и поисковые движки. Эта страница — компактный справочник по тому, что должен знать senior+ инженер: как устроены LRU/LFU, зачем нужен Bloom Filter, как работает consistent hashing в Cassandra/DynamoDB, в чём разница между LSM и B-Tree, и где применяются Skip Lists.

Когда применять

• LRU кэш — ограниченная по памяти кэш-прослойка с вытеснением «давно не использованных» записей. Memcached, Redis (с политикой allkeys-lru).
• LFU кэш — кэш, где важна частота обращений (а не время). CDN, hot-content кэши.
• Bloom Filter — быстрая проверка «возможно есть / точно нет» с минимальной памятью. Антиспам, дедупликация URL, Cassandra (проверка SSTable перед чтением).
• Consistent Hashing — sharding между N узлами с минимальным rehash при добавлении/удалении узла. DynamoDB, Cassandra, Riak.
• LSM Tree — write-optimized хранилище: быстрые вставки в memtable, периодический merge на диск. LevelDB, RocksDB, Cassandra, ScyllaDB.
• Skip List — упорядоченное множество с O(log n) операциями без сложного балансирования. Redis sorted sets (ZSET), LevelDB memtable.

Идея

LRU кэш

Комбинация HashMap + двусвязный список. HashMap → O(1) lookup; список → O(1) перенос узла в head при get/put и удаление tail при переполнении. В JS встроенный Map сохраняет порядок вставки — это позволяет реализовать LRU без явного списка: достаточно delete + set для «промоушена» ключа.

Bloom Filter

Битовый массив длины m + k независимых хеш-функций. add(x) ставит биты h_1(x), ..., h_k(x) в 1. mayContain(x) проверяет все эти биты: если хоть один 0 — точно нет; если все 1 — возможно есть (false positive). False negative невозможен, что критично для применения в БД.

Параметры: при оптимальном k = (m/n)·ln2 false positive rate ≈ (1 − e^(−kn/m))^k. Для n = 10⁶ и FPR = 1% нужно ~9.6 бит на элемент.

Consistent Hashing

Хеши узлов и ключей размещаются на кольце (0..2³² − 1). Ключ принадлежит первому узлу по часовой стрелке. При добавлении узла переезжает только 1/N доля ключей (а не все, как при hash % N). Virtual nodes (vnodes) — каждый физический узел имеет 100–256 точек на кольце для равномерности.

LSM Tree vs B-Tree

	B-Tree	LSM Tree
Запись	seek + update on disk	append в memtable, batched flush
Чтение	O(log n) с диска	проверка memtable + N SSTable + Bloom Filter
Write amplification	низкий	высокий (compaction)
Read amplification	низкий	высокий (несколько уровней)
Use case	OLTP, частые updates	write-heavy, time-series, logs

LSM: writes идут в memtable (in-memory sorted structure, обычно skip list). При переполнении memtable сбрасывается на диск как immutable SSTable. Compaction периодически сливает SSTables, удаляя дубли и tombstones.

Skip List

Многоуровневый связный список. Уровень узла — рандомный (геометрическое распределение, p=0.5). Поиск идёт сверху вниз: на каждом уровне продвигаемся вправо, пока следующий узел ≤ target. Ожидаемое O(log n), без блокировок (важно для Redis).

Реализация

LRU Cache на JS Map

class LRUCache<K, V> {
  private cache = new Map<K, V>();

  constructor(private capacity: number) {}

  get(key: K): V | -1 {
    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: K, value: V): void {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.capacity) {
      const oldest = this.cache.keys().next().value; // первый = самый старый
      this.cache.delete(oldest);
    }
    this.cache.set(key, value);
  }
}

Заметка

В реальном production-коде (например, в Java/C++) LRU обычно реализуется через явный двусвязный список + HashMap, потому что не во всех языках Map гарантирует order-of-insertion с O(1) reordering. В JS — это идиоматично.

Bloom Filter

class BloomFilter {
  private bits: Uint8Array;
  private size: number;
  private hashCount: number;

  constructor(size: number = 1000, hashCount: number = 3) {
    this.size = size;
    this.hashCount = hashCount;
    this.bits = new Uint8Array(size);
  }

  private hash(item: string, seed: number): number {
    let h = seed;
    for (let i = 0; i < item.length; i++) {
      h = ((h << 5) - h + item.charCodeAt(i)) | 0;
    }
    return Math.abs(h) % this.size;
  }

  add(item: string): void {
    for (let i = 0; i < this.hashCount; i++) {
      this.bits[this.hash(item, i)] = 1;
    }
  }

  mayContain(item: string): boolean {
    for (let i = 0; i < this.hashCount; i++) {
      if (this.bits[this.hash(item, i)] === 0) return false;
    }
    return true;
  }
}

Применение: Cassandra перед чтением SSTable проверяет Bloom Filter; если «точно нет» — экономит дисковую seek.

Consistent Hashing

class ConsistentHash {
  private ring = new Map<number, string>();
  private sortedKeys: number[] = [];
  private virtualNodes: number;

  constructor(nodes: string[] = [], virtualNodes: number = 150) {
    this.virtualNodes = virtualNodes;
    for (const node of nodes) this.addNode(node);
  }

  private hash(key: string): number {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = ((h << 5) - h + key.charCodeAt(i)) | 0;
    }
    return Math.abs(h);
  }

  addNode(node: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const h = this.hash(`${node}:${i}`);
      this.ring.set(h, node);
      this.sortedKeys.push(h);
    }
    this.sortedKeys.sort((a, b) => a - b);
  }

  removeNode(node: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const h = this.hash(`${node}:${i}`);
      this.ring.delete(h);
      const idx = this.sortedKeys.indexOf(h);
      if (idx !== -1) this.sortedKeys.splice(idx, 1);
    }
  }

  getNode(key: string): string | null {
    if (this.sortedKeys.length === 0) return null;
    const h = this.hash(key);
    // первый узел по часовой стрелке (binary search можно)
    for (const k of this.sortedKeys) if (k >= h) return this.ring.get(k)!;
    return this.ring.get(this.sortedKeys[0])!; // wrap-around
  }
}

При добавлении узла переезжают только ключи в одном секторе кольца (≈ K/N).

Сложность

Структура	Операция	Сложность
LRU Cache	get / put	O(1)
Bloom Filter	add / mayContain	O(k)
Consistent Hash	getNode	O(log V) с binary search, V = vnodes
LSM Tree	write	O(1) amortized в memtable
LSM Tree	read	O(log n) на уровень × число уровней
Skip List	search / insert	O(log n) expected

Типичные ошибки и подводные камни

• LRU без переноса при get: забыли delete + set → элемент не считается «недавно использованным».
• Bloom Filter false positive vs false negative: FP допустимы, FN — нет; не используйте для авторизации (where false positive = security hole).
• Consistent Hash без vnodes: при малом N распределение неравномерное; vnodes (100–200 на узел) дают ровную нагрузку.
• LSM compaction: размер write amplification (3–10×) надо учитывать при выборе SSD; tiered vs leveled compaction — разный trade-off.
• Skip List rebalancing: не нужен (вероятностный baking-in); важно правильно посеять рандом для воспроизводимости тестов.

Follow-up вопросы

• Чем LFU отличается от LRU и где предпочесть? LFU считает частоту обращений; LRU — время. LFU лучше для контента с устойчивой популярностью (CDN с топ-видео); LRU — для бурлящих паттернов (сессии, recent timeline).

• Почему Bloom Filter не поддерживает удаление? Сброс битов мог бы породить false negative (другой ключ использовал тот же бит). Решение — Counting Bloom Filter (счётчик на ячейку вместо бита), но больше памяти.

• Как Cassandra обновляет данные, если SSTable immutable? Запись новой версии ключа в memtable → новая SSTable. При чтении берётся самая свежая версия (по timestamp). Удаление = запись tombstone. Compaction убирает старые версии.

• Что такое CAP в контексте этих структур? Consistent Hashing помогает реализовать AP-системы (DynamoDB) — данные доступны при partition, но возможны конфликты (vector clocks для resolution). LSM сама по себе не про CAP, но используется в AP-БД.

• Когда Skip List проигрывает Red-Black Tree? Worst-case Skip List — O(n) (плохой рандом); RB-Tree гарантирует O(log n). Но Skip List проще параллелизовать (lock-free варианты), поэтому Redis выбрал его.

Чеклист на собес

• Знаешь как минимум 5 структур: LRU, Bloom, Consistent Hash, LSM, Skip List.
• Можешь реализовать LRU за 5 минут (Map в JS / LinkedHashMap в Java).
• Понимаешь trade-off LSM vs B-Tree (write-heavy vs read-heavy).
• Знаешь параметры Bloom Filter: m, k, n, FPR.
• Объясняешь, зачем нужны virtual nodes в consistent hashing.
• Можешь назвать конкретные продукты: Redis = Skip List, Cassandra = LSM + Bloom, DynamoDB = consistent hash.