Паттерны системных интервью

Low-level системное интервью в Google или Jane Street: 'Реализуйте thread-safe bounded buffer'. Или в Citadel: 'Спроектируйте memory allocator без фрагментации'. Эти задачи проверяют не только алгоритмы, а понимание concurrent primitives, OS механизмов, trade-offs в дизайне. Senior SWE в FAANG системных командах зарабатывают $400-600k. Паттерны из этого урока - прямое требование к таким позициям.

• **Google gRPC** - rate limiting через Token Bucket; burst capacity для кратковременных spike; distributed limiting через Redis; каждый дата-центр имеет локальный + глобальный счётчик
• **Linux Kernel Slab Allocator** - выделяет объекты фиксированных размеров (task_struct, inode) из пулов; нулевая фрагментация для known sizes; tcmalloc адаптировал для userspace (Chrome, Go runtime)
• **Go runtime scheduler** - work-stealing thread pool; 'goroutines' мультиплексируются на OS-потоки; graceful shutdown через context.Context; GOMAXPROCS потоков как воркеры

Цели урока

• Rate limiter: token bucket vs sliding window, distributed (Redis-based)
• Thread pool: очередь, worker threads, graceful shutdown, error propagation
• Memory allocator: free list, buddy, slab; trade-offs jemalloc vs tcmalloc
• Bounded buffer (producer-consumer): mutex + cond vars vs lock-free queue
• Структурировать ответ: clarify → API → state → concurrency → trade-offs

Проектирование Rate Limiter

Типичный вопрос на system design интервью в Amazon/Google: 'Спроектируйте rate limiter который ограничивает API до 1000 запросов в секунду на пользователя'. Нужно обсудить алгоритмы, хранилище, масштабирование и edge cases.

Алгоритмы: **Token Bucket** (накапливать токены до burst capacity, расходовать на запрос), **Leaky Bucket** (FIFO очередь с постоянным rate слива), **Fixed Window Counter** (счётчик за окно, boundary burst проблема), **Sliding Window Log** (точный, дорогой - хранить timestamp каждого запроса), **Sliding Window Counter** (компромисс).

Проектирование Thread Pool

Интервью вопрос в Microsoft/Meta: 'Реализуйте thread pool с фиксированным числом воркеров, очередью задач и graceful shutdown'. Проверяет знание concurrent primitives: mutex, condition variable, atomic operations.

Thread pool компоненты: **Task Queue** (потокобезопасная, обычно bounded или unbounded blocking queue), **Worker Threads** (N потоков, ждут задачи и выполняют), **Shutdown mechanism** (drain queue и завершить, или немедленное завершение). Паттерн: producer-consumer с condition variable.

Проектирование Memory Allocator

Интервью в Google/Citadel: 'Реализуйте упрощённый malloc/free'. Проверяет понимание heap layout, фрагментации, alignment, free lists. Реальные аллокаторы (jemalloc, tcmalloc) используются в Firefox, Chrome, Redis.

Стратегии: **First Fit** (первый подходящий блок), **Best Fit** (наименьший подходящий), **Buddy System** (разделение на степени 2, O(log n) merge). **Slab Allocator** (фиксированные размеры объектов - используется в ядре Linux). **tcmalloc**: thread-local caches + central heap для снижения contention.

Задачи на concurrency

Классические задачи concurrency которые спрашивают на low-level интервью: Философы за столом (deadlock), Producers-Consumers (bounded buffer), Readers-Writers (concurrent reads, exclusive writes), Sleeping Barber.

Инструменты: **Mutex** (взаимное исключение), **Semaphore** (счётный mutex), **Condition Variable** (ожидание условия), **Monitor** (mutex + CV), **Read-Write Lock** (concurrent reads, exclusive write). Паттерны: **Lock Ordering** (всегда брать блокировки в одном порядке против deadlock), **Try-lock with timeout** (обнаружить deadlock).

Ключевые идеи

• **Rate Limiter**: Token Bucket (burst допустим) vs Sliding Window Log (точный) vs Fixed Window (boundary burst); distributed -> Redis Lua script для атомарности
• **Thread Pool**: bounded queue + N воркеров + shutdown event; timeout на get() для graceful shutdown; exception в task не убивает воркер
• **Memory Allocator**: First Fit / Best Fit / Buddy System; coalescing при free() против внешней фрагментации; slab для fixed-size объектов
• **Concurrency**: Lock Ordering против deadlock (circular wait); Readers-Writers Lock; TOCTOU - mutex не всегда достаточно, нужна атомарность всей операции

Связанные темы

Системные интервью объединяют OS, concurrency и алгоритмы:

• Синхронизация и concurrency — Mutex, semaphore, condition variable - инструменты реализации rate limiter и thread pool
• Управление памятью — Heap layout, virtual memory - основа для проектирования memory allocator

Вопросы для размышления

• Distributed rate limiter в 3 регионах AWS. Локальный Redis за <1мс, глобальный Redis за ~20мс. Как реализовать rate limiting который работает с задержкой <2мс но не пропускает burst при локальных failover сценариях?
• Thread pool с bounded queue размером 100. Если все 100 слотов заняты и вызывается submit() - что предпочтительнее: блокировать caller, бросать exception или отклонять задачу с callback? Зависит от контекста - какого?
• Memory allocator для embedded системы (64KB heap, нет сборщика мусора, realtime ограничения). Почему Best Fit хуже First Fit для realtime и почему Buddy System стандарт для kernel allocators?

Связанные уроки

• arch-01-binary