Параллельные вычисления
Parallel Computing на собеседовании
Финальный раунд в Google. Пять часов интервью позади. Последний вопрос: 'Как реализовать distributed rate limiter для 10 миллионов пользователей?' Это не про знание API - это про структурированное мышление о concurrency tradeoffs под давлением.
- Meta (Facebook) инженер на собеседовании: 'Спроектируйте producer-consumer систему для обработки 1 миллиона событий в секунду' - типичный E5/E6 вопрос
- Google SWE interview: 'Найдите race condition в этом коде' - 30% технических вопросов связаны с конкурентностью
- Amazon Principal Engineer: 'Как Circuit Breaker предотвращает каскадные сбои и какие метрики использовать для настройки threshold?' - уровень системного проектирования
Race Conditions: диагностика и решение
Race condition - результат зависит от относительного порядка выполнения потоков. Проявляется нерегулярно, трудно воспроизвести в debugger. Классика: check-then-act без синхронизации. На собеседовании спрашивают: найти, объяснить, исправить.
- Atomicity violation: check-then-act, read-modify-write без синхронизации
- Order violation: поток A зависит от результата B, но порядок не гарантирован
- Deadlock: два потока ждут блокировки в разном порядке (circular wait)
- Livelock: потоки активны, но не прогрессируют (retry loop)
- Starvation: поток никогда не получает CPU/блокировку из-за приоритетов
Почему balance++ в многопоточном коде не является атомарной операцией?
Проектирование конкурентных систем
Классика на FAANG: 'Спроектируйте rate limiter / producer-consumer / кэш с eviction'. Структура ответа: API (интерфейс), data structures (что хранить), synchronization strategy (как защитить), edge cases (что может пойти не так), extensions (как масштабировать).
Паттерн для ответа на system design: начать с простого (single-threaded), добавить синхронизацию, затем обсудить масштабирование (distributed, sharding). Guava Cache, Caffeine - production-ready LRU с ConcurrentHashMap + explicit LRU policy. Caffeine W-TinyLFU дает 95%+ hit rate на типичных workloads.
Почему ReadWriteLock не идеален для LRU Cache с LinkedHashMap?
Throughput vs Latency: трейдоффы производительности
Throughput - запросов в секунду. Latency - время одного запроса. Противоречие: batching увеличивает throughput за счёт latency. Пример: Kafka producer linger.ms=0 (низкая latency) vs linger.ms=100 (высокий throughput через batching). На собеседовании: уточнить требования до начала проектирования.
Little's Law: L = λW (число в системе = throughput * время). Для расчёта: если latency 200ms и нужен throughput 500 RPS, требуется 100 одновременных запросов в обработке. Это нижняя граница числа потоков/горутин. p50/p99/p999 latency важнее среднего - хвост распределения определяет user experience.
Latency сервиса 50ms, нужен throughput 1000 RPS. Минимальное число потоков?
Tradeoffs и типичные вопросы интервью
Финальный раунд: обсуждение tradeoffs. Не существует правильного ответа - только аргументированный выбор. Структура: 'В сценарии X подход A лучше потому что ... Но при Y лучше B потому что ...'. Показывает системное мышление, не зазубривание ответов.
- Lock-free vs lock-based: CAS (AtomicInteger) лучше при низкой contention, хуже при высокой (spinning)
- Optimistic vs pessimistic locking: optimistic (CAS/MVCC) лучше при редких конфликтах, pessimistic - при частых
- Fine-grained vs coarse-grained locking: мелкие блокировки дают конкурентность, крупные - простоту
- Immutability: полная безопасность без синхронизации, но overhead копирования при изменении
- Actor model vs shared memory: акторы проще reasoning, shared memory быстрее при низком overhead
ConcurrentHashMap.size() возвращает неточное значение при конкурентных операциях. Это баг или фича?
Ключевые идеи
- Race conditions: check-then-act и read-modify-write - главные паттерны. Решение: atomics, locks, immutability.
- Little's Law: L = λW - рассчитать нужное число потоков до начала проектирования.
- Tradeoffs: lock-free при низкой contention, pessimistic lock при высокой, immutability для read-heavy.
Связанные темы
Вопросы на собеседовании охватывают весь курс параллельного программирования:
- Concurrency на масштабе — Thread pools, backpressure, circuit breaker - типичные вопросы system design раунда
- Основы параллелизма — Race conditions, deadlock, memory model - база для технического раунда по concurrency
Вопросы для размышления
- Как объяснить интервьюеру выбор между optimistic и pessimistic locking для конкретного сценария?
- Почему p99 latency важнее p50 для пользовательского опыта, и как это влияет на выбор алгоритмов?
- Как бы выглядел дизайн thread-safe LRU cache для production: Caffeine vs собственная реализация?