Подходы (кратко, с последствиями) и ключевые вопросы.
Обозначения: общее число токенов $T$, число уникальных слов (истинное) $U$, число рабочих единиц (ядер/процессов/узлов) $P$.
1) Multithreading (в пределах одного узла)
- Идея: парсить документы параллельно потоками и обновлять общий словарь (concurrent hash map) или делать локальные словари в каждом потоке и потом сливать.
- Плюсы: низкая латентность, низкие накладные расходы на IPC.
- Минусы: конкуренция/блокировки при записи в общую структуру, GIL в Python (если есть), ограничение ОЗУ узла.
- Балансировка: раздать документы/чанки равномерно, ожидаемая нагрузка на поток $\approx T/P$.
- Агрегация: объединить локальные словари (суммирование счётчиков) — операция требует памяти и может быть частично параллельной (reduce-tree).
- Устойчивость: при падении процесса обычно теряются данные в памяти — нужно периодическое сохранение чекпоинтов (сериализация локальных словарей на диск).
2) Multiprocessing / распределение по процессам (multi-process на одном узле или нескольких)
- Идея: каждый процесс строит локальный словарь, затем центральный агрегатор или внешний механизм сливает результаты.
- Плюсы: обход проблем GIL, лучше изоляция, проще сброс на диск.
- Минусы: IPC/сериализация больших словарей, накладные расходы при слиянии.
- Балансировка: распределять входные файлы/чанки; при длиннохвостых частотах слов необходима стратификация данных или предварительный sampling для выявления hot keys.
- Агрегация: map-side partial aggregate + shuffle ключей по hash(word) к reducer'ам; или hierarchical merge (параллельный merge пар процессов).
- Устойчивость: процессы проще перезапускать; сохранить прогресс через контрольные точки (частичные итоговые словари на диск).
3) MapReduce (Hadoop/Spark batch)
- Идея: map — эмитить пары $(word,1)$ или локальные подсчёты; shuffle/partition по key; reduce — суммировать счётчики и выдавать уникальные слова.
- Плюсы: масштабируемость на кластер, встроенная устойчивость (перезапуск failed tasks), простая семантика.
- Минусы: высокая латентность и IO (shuffle), overhead при маленьких задачах.
- Балансировка:
- partitioning: использовать hash(word) → $partition=hash(word)\mathrm{mod}P$ для равномерного распределения; при key-skew — применять skew mitigation (разделение hot-keys с добавлением случайного префикса).
- предварительный combiner (map-side aggregation) сильно сокращает трафик shuffle.
- Агрегация: reduce суммирует счётчики; для подсчёта только уникальных слов достаточно флага присутствия (map отправляет 1), reduce считает существование и/или суммарную частоту.
- Устойчивость: полагается на переисполнение задач; данные и промежуточные блоки реплицируются в HDFS; idempotentные операции обеспечивают корректность при повторных запусках.
4) Stream processing (Flink, Kafka Streams, Spark Streaming)
- Идея: потоковая обработка документов/токенов с поддержкой stateful operators (keyed state по слову), окон (time/tumbling) или глобального состояния.
- Плюсы: низкая задержка, непрерывное обновление уникальных слов.
- Минусы: состояние может быть велико; требуется механизмы чекпоинтов и управления состоянием.
- Балансировка: key-by word → state распределяется по задачам; проблема key-skew решается динамическим ресалансированием или splitting heavy keys.
- Агрегация: поддержание набора или счётчика per-key; для глобального уникального множества — распределённое состояние + периодическое слияние.
- Устойчивость: фреймворки дают exactly-once или at-least-once семантику через чекпоинты и replay (Kafka); нужно idempotентное обновление состояния.
5) Приёмы оптимизации агрегации и экономии ресурсов
- Combiner / map-side aggregation: уменьшает shuffle объём.
- Partitioning: hash, range, consistent hashing; при skew — sampling → выделение hot keys.
- Hierarchical reduce (tree-aggregation): уменьшает пиковую нагрузку на один reducer.
- Внешняя сортировка / spill-to-disk при переполнении памяти.
- Probabilistic structures для больших $U$:
- Bloom filter для membership (нет подсчёта уникальных, но проверка присутствия).
- HyperLogLog для приближённого количества уникальных: относительная ошибка $\epsilon \approx 1.04/\sqrt{m}$ при $m$ регистрах; очень маленькая память по сравнению с явным множеством.
- Count-min + heavy-hitter detection для частотных слов.
- Компрессия и кодирование слов (dictionary encoding, hashing) для уменьшения трафика.
6) Проблемы балансировки нагрузки (ключевые моменты)
- Key skew (длинный хвост): несколько слов могут концентрировать большую часть токенов → reducer/partition перегружен.
- Решения: split hot keys (randomized prefixes), hot-key routing (вынос тяжёлых ключей на несколько worker'ов), adaptive re-partitioning.
- Нерегулярные размеры входных файлов: использовать динамическое распределение задач/локальные очереди.
- Сетевой и диск IO: shuffle heavy — оптимизировать combiner, компрессию и parallelism.
7) Устойчивость к сбоям
- Повторяемость (idempotence) операций и детерминированные мап/редьюс.
- Чекпоинты состояния (для потоков) и промежуточные сохранения (для batch).
- Репликация данных и перераспределение задач при падении узлов.
- Специфические техники: speculative execution (Spark), write-ahead logs для stateful operators.
- Согласованность vs производительность: exactly-once даёт сложность/накладные расходы; при подсчёте уникальных часто хватает at-least-once + idempotентность или приближённых структур (HLL).
Резюме (рекомендации)
- Малый/средний объём и один мощный узел: multiprocessing + local aggregates, spill-to-disk.
- Большой кластер и пакетная задача: MapReduce/Spark с combiner'ами, hash-partitioning, mitigation для hot-keys.
- Потоковые требования или непрерывное обновление: stream processing с ключевым state и регулярными чекпоинтами; для памяти — HyperLogLog.
- Всегда: предварительный sampling для выявления skew, map-side aggregation, и план по чекпоинтам/репликации для отказоустойчивости.