Архитектура (цель: подсчёт слов по терабайтам данных при ограниченной задержке)

Ключевая идея: распараллелить по ключу = слову, минимизировать сетевой shuffle и обеспечить инкрементальную обработку для низкой задержки. Предлагаем гибридную архитектуру: потоковая (для быстрых ответов) + пакетная (для окончательной точности) — «Lambda»/«Kappa»-подход.

1) Компоненты

Хранилище исходных данных: распределённый файловый слой (HDFS, S3) для исторических данных + Kafka для инкрементальной подачи новых документов.Планировщик/фреймворк: Apache Flink / Spark Structured Streaming (stateful stream processing) для низкой задержки; Apache Spark / Hadoop MapReduce для пакетной переработки (ретроспективная корректировка).Хранилище агрегатов/индекса: distributed key-value (Cassandra/Scylla) или OLAP/ES для интерактивных запросов.Координатор/метрики: Zookeeper/Coordination, metrics/alerting.

2) Поток обработки (быстрый путь)

Ingest: документы → Kafka.Parse & tokenize (партицируется по Kafka partition).Local combiner: мелкая агрегация по партиции (micro-batches или per-record state).Stateful keyed aggregation: ключ = слово, агрегаты хранятся локально в операторе (в памяти + checkpoint).Выдача: периодические инкременты в KV-store / query API.Окна/TTL: скользящие окна или tumbling для ответов за определённый интервал.

3) Пакетная корректировка (медленный путь, точность)

Периодический MapReduce / Spark job по исходному хранилищу для окончательных, точных глобальных подсчётов.Сверка/комбинация: объединение результатов stream (approx) + batch (exact), при необходимости перезапись агрегатов.

Данные локальность

Хости задач должны назначаться там, где хранятся блоки (YARN/Flink scheduler с data locality).Для Kafka — данные считываются локально с брокера/partition; партиционирование исходных документов по HDFS block + node-preference.

Разделение ключей и балансировка нагрузки

Партиционировать по хешу слова: (partition = hash(word) \bmod P).Для скиза (heavy-hitters) применить:
Two-phase aggregation: сначала local top-k, затем global merge.Skew mitigation: предварительный sample → выделить «горячие» слова и задать им отдельные reducer’ы; для остальных — равномерный hash.Sticky routing для горячих ключей: делить их по subkeys (word#shard).Комбайнеры (local combiners) сокращают объём shuffle: локальная агрегация перед отправкой.

Обработка отказов

MapReduce: перекат задач — перезапуск map/reduce. Идемпотентные операторы + checkpointing/atomic output.Spark: lineage → recompute потерянные partitions; для stream — checkpoint state + WAL.Flink: snapshot-based checkpointing (Chandy–Lamport style) для exactly-once состояния; при сбое — восстановление из checkpoint.Kafka: offset management + consumer group rebalancing; использование микробатчей и ack’ов.Идемпотентность sink’ов или transactional writes (Kafka transactions, DB upserts) для exactly-once внешних выводов.

Согласованность и компромиссы время отклика ↔ точность

Полная точность: batch MapReduce/Spark → высокий латент (минуты–часы), точность 100%.Низкая задержка: stream processing → быстрый отклик (миллисекунды–секунды) с поддержкой stateful exactly-once (через checkpoint + transactional sinks) или at-least-once + идемпотентные апдейты.Аппроксимация для ускорения/экономии памяти: Count-Min Sketch (CMS). Гарантия: (\hat{f}(x) \le f(x) + \epsilon |\mathbf{f}|_1) с вероятностью (1-\delta), где для CMS выбирают ширину (w=\lceil e/\epsilon\rceil) и глубину (d=\lceil \ln(1/\delta)\rceil). Это уменьшает память до (O(\frac{1}{\epsilon}\log\frac{1}{\delta})) против (O(|V|)) для точного счёта.Примеры компромиссов:
Если важна низкая латентность (реактивные дашборды) — отдаём предпочтение stream + sketches → быстрые, но приближённые значения.Если важна абсолютная точность (отчётность, биллинг) — batch recalculation с высокой задержкой и коррекцией stream-данных.

Производительность / затраты сети

Время выполнения (приближённая модель): [T \approx T{read} + T{compute} + T{shuffle} + T{write}.]Цель: минимизировать (T_{shuffle}) — использовать combiners, data locality, правильный партиционер.Память состояния: для точных агрегатов — (O(|V_{active}|)); для sketch — задано параметрами (\epsilon,\delta).

Сравнение подходов

1) MapReduce (Hadoop)

Плюсы: простая модель, гарантированная полная точность, высокая устойчивость.Минусы: высокая латентность (минуты+), большой сетевой shuffle, не подходит для низкой задержки.Применимость: периодические полные пересчёты, историческая аналитика.

2) Потоковая обработка (Flink, Spark Structured Streaming, Kafka Streams)

Плюсы: низкая задержка (субсек — секунды), stateful windows, exactly-once при правильной конфигурации, горизонтальное масштабирование.Минусы: управление состоянием и checkpointing усложняет архитектуру; при больших state — потребность в бэкенде для state (RocksDB); возможны приближения или инкрементальная ошибка.Применимость: real-time подсчёт, интерактивные дашборды, alerting.

3) Распределённые БД / Search (Cassandra, Elasticsearch)

Плюсы: низкая задержка чтения/записи, готовые запросы/фильтрация, быстрое масштабирование для чтения.Минусы: поддержание агрегатов в реальном времени требует апдейтов на запись — высокая нагрузка на I/O; consistency tradeoffs (обычно eventual); хранение индексов стоит дорого.Применимость: OLTP/OLAP/интерактивный доступ к текущим агрегатам, поиск по словам.

Рекомендация (практическая)

Для требований «низкая задержка + почти-точный ответ» — использовать потоковую платформу (Flink/Spark str. streaming) с:
local combiners, keyed state, checkpointing,heavy-hitter detection + skew mitigation,Count-Min Sketch для памяти/скорости, если допускаем погрешность (\epsilon).Для гарантии точности — периодический batch job (Spark/Hadoop) для полного пересчёта и корректировки/сверки агрегатов.Хранилище конечных агрегатов — распределённый KV (Cassandra) для быстрых точечных запросов + OLAP/ES для аналитики.

Кратко о требованиях к параметрам

Выберите ( \epsilon ) (макс относительная/абсолютная ошибка) и целевую задержку (L). От них зависят: размер sketch ((O(1/\epsilon))), checkpoint-частота (чем чаще — тем выше надёжность, выше нагрузка), размер window/micro-batch.Настройте мониторинг горячих ключей и динамическую перераспределение партиций.

Заключение

MapReduce — точен, но медленен. Потоковая обработка — низкая задержка, сложнее state/отказоустойчивость, можно получить exactly-once; часто в паре с batch-компонентом даёт лучшее соотношение latency/accuracy. Распределённые БД хороши как быстрый слой выдачи результатов и хранения агрегатов.