Источник
System Design Interview Review
Обзор книги Alex Xu от Александра Поломодова (Part 1 и Part 2)
System Design Interview: An Insider's Guide (System Design. Подготовка к сложному интервью)
Авторы: Alex Xu, Sahn Lam
Издательство: Independently Published
Объём: 276 страниц
Детальный разбор легендарной книги Alex Xu: масштабирование, estimation, rate limiter, consistent hashing, key-value store.
Оригинал
ПереводСтруктура книги
Масштабирование, оценка нагрузки, фреймворк интервью
12 реальных кейсов по проектированию систем
Список источников для углубленного изучения
1. Scale from Zero to Millions of Users
В этой главе автор начинает с размещения системы на одном сервере и постепенно масштабирует её до миллионов пользователей.
Ключевые темы главы
Резюме автора
- Keep web tier stateless
- Build redundancy at every tier
- Cache data as much as you can
- Support multiple data centers
- Host static assets in CDN
- Scale your data tier by sharding
- Split tiers into individual services
- Monitor your system and use automation tools
2. Back-of-the-envelope Estimation
Глава о приблизительных расчетах нагрузки — критически важный навык для System Design Interview.
Степени двойки
Latency Numbers
Availability
Рекомендация
Для более актуальных данных о latency рекомендуется посмотреть rule-of-thumb-latency-numbers от Google SRE.
3. A Framework for System Design Interviews
Глава о 4-шаговом фреймворке для прохождения System Design Interview — центральная методология книги.
Understand the Problem
High-level Design
Design Deep Dive
Wrap Up
4. Design a Rate Limiter
Система для ограничения количества запросов — первая практическая задача книги.
Алгоритмы Rate Limiting
Токены добавляются с фиксированной скоростью, запросы расходуют токены
Запросы обрабатываются с постоянной скоростью, излишек отбрасывается
Счетчик запросов в фиксированном временном окне
Лог timestamps запросов с скользящим окном
Гибрид fixed window и sliding log
Мнение автора обзора
Rate limiter скорее не отдельная задача, а кубик для других задач. Хотя при глубоком разборе это может быть нетривиальной задачей — например, можно почитать про YARL от Яндекса.
5. Design Consistent Hashing
Механизм для равномерного распределения данных по серверам с минимальным перераспределением при изменениях.
Что такое Consistent Hashing?
Особый вид хеширования, при котором изменение количества серверов требует перераспределения только n/m ключей (где n — количество ключей, m — количество слотов), в отличие от обычного хеширования, где перераспределяются почти все ключи.
Ключевые концепции
- Hash Ring — пространство ключей закольцовываетсяHash Ring — пространство ключей закольцовывается
- Virtual Nodes — каждый физический сервер имеет несколько виртуальных точек на кольцеVirtual Nodes — каждый физический сервер имеет несколько виртуальных точек на кольце
- Используется в Cassandra, DynamoDB, и других distributed системах
6. Design a Key-Value Store
Проектирование распределенного key-value хранилища с поддержкой get/put операций.
Требования к системе
- Размер пары key-value < 10 KB
- Возможность хранить big data
- High availability
- High scalability
- Automatic scaling
- Tunable consistency
- Low latency
CAP Theorem
- CP — система не обслуживает часть запросов, но сохраняет консистентность
- AP — система ослабляет консистентность ради доступности
- Partition tolerance обязателен в распределенных системах
Модели консистентности
Strong Consistency
Это linearizability: каждое чтение видит результат последней завершённой записи, как если бы существовала единственная копия данных.
Weak Consistency
Последующие чтения могут не видеть последние обновления.
Eventual Consistency
При достаточном времени все реплики станут консистентными.
Дополнительные темы главы
- Tunable Consistency — W + R > N для сильной консистентности
- Vector Clocks — для causal consistency и разрешения конфликтов
- Failure Detection — heartbeats, pings, gossip protocol
- Anti-entropy — механизмы борьбы с расхождением данных
- SSTable & LSM Trees — структуры хранения данных
7. Design a Unique ID Generator
Проектирование генератора уникальных идентификаторов для распределенных систем.
Требования
- IDs must be unique
- IDs are numerical values only
- IDs fit into 64-bit
- IDs are ordered by date
- Ability to generate over 10,000 unique IDs per second
Multi-master ReplicationПросто
Каждый из k серверов генерирует ID с шагом k:
- Сервер 1: 1, k+1, 2k+1...
- Сервер 2: 2, k+2, 2k+2...
UUIDПопулярно
128-bit идентификатор, генерируется без координации.
Ticket ServerЦентрализованно
Единый сервис генерирует последовательные ID для всех.
Twitter SnowflakeРекомендуется
64-bit ID с структурой:
- 1 bit — знак
- 41 bit — timestamp (ms)
- 10 bit — machine ID
- 12 bit — sequence number
Итоги по первой части книги
Первые семь глав книги формируют фундамент для System Design Interview:
Сильные стороны
- ✓ Понятный 4-шаговый фреймворк
- ✓ Хорошее введение в масштабирование
- ✓ Практичные алгоритмы (Rate Limiter)
- ✓ Полезные строительные блоки
На что обратить внимание
- ⚠ Упрощенное описание consistency models
- ⚠ Некоторые задачи — скорее "кубики"
- ⚠ Рекомендуется дополнить "Database Internals"
Разбор
System Design Interview Review — Part 2
Подробный обзор практических задач из второй части книги.
Часть 2: Практические задачи (Главы 8-16)
Вторая часть книги посвящена реальным задачам System Design Interview — от URL Shortener до Google Drive.
8. Design a URL Shortener
Классическая задача для System Design Interview — сервис для сокращения ссылок типа bit.ly или tinyurl.
Требования
- 100 million URLs generated per day
- Read:Write ratio = 10:1
- Average URL length = 100 symbols
- Store for 10 years
API
POST /api/shorten— создание короткой ссылкиGET /:shortUrl— редирект на длинный URL
Варианты хеширования
| Подход | Описание | Особенности |
|---|---|---|
| Base62 | [a-zA-Z0-9] | 62⁷ ≈ 3.5 trillion комбинаций |
| MD5/SHA | Hash + обрезка | Возможны коллизии |
| Counter + Base62 | Инкрементный ID | Предсказуемость |
Дополнительные вопросы
- Rate limiting на запросы
- Шардирование базы данных
- Аналитика использования ссылок
9. Design a Web Crawler
Система для парсинга страниц в интернете — основа поисковых движков.
Требования
- 1 миллиард страниц в месяц
- Хранение 5 лет
- Средний размер страницы — 500 KB
- Только HTML (расширяемо)
Компоненты системы
URL Frontier: Politeness & Priority
Prioritizer распределяет URL по очередям с разным приоритетом. Front Queue Selector обеспечивает politeness — запросы к одному домену идут последовательно через один worker, ограничивая нагрузку на внешние сайты.
10. Design a Notification System
Система отправки миллионов push-уведомлений, SMS и email в день.
Архитектура
- Notification API — приём заданий, аутентификация, rate limiting
- Message Queues — отдельные очереди для iOS, Android, SMS, Email
- Workers — обработчики очередей для каждого канала
- 3rd Party Services — APNs, FCM, Twilio, SendGrid
- Analytics Service — отслеживание доставки и метрик
11. Design a News Feed System
Лента новостей как в социальных сетях — классическая задача, подробно разобранная в DDIA Мартина Клеппмана.
Требования
- 10M DAU
- До 5000 друзей
- Посты с текстом, фото, видео
- Сортировка по времени
Fan-out стратегии
- Push — пишем в ленты всех подписчиков
- Pull — собираем ленту при запросе
- Hybrid — комбинация для celebrities
Ключевые компоненты
12. Design a Chat System
Мессенджер с peer-to-peer и групповыми чатами, индикатором онлайна.
Способы получения данных
Polling
Периодический опрос сервера. Просто, но неэффективно.
Long Polling
Запрос висит до появления данных или timeout.
WebSocket ✓
Двусторонний канал. Рекомендуется для чатов.
Компоненты
- Connection API — HTTP для auth и получения chat server
- Chat API — WebSocket для сообщений и heartbeat
- Message Queue → Keeper Worker, Push Notification Worker
- Heartbeat Queue → Online Presence Worker → Presence DB
Stateful Chat Servers
Chat servers хранят активные WebSocket соединения — это делает их stateful. Нужен механизм для роутинга сообщений на правильный сервер.
13. Design Search Autocomplete
Система подсказок для автозаполнения в поисковой строке.
Требования
- 10M DAU
- 10 поисков / пользователь / день
- Топ-5 подсказок по частотности
- Только английский язык
Ключевая структура данных
Позволяет эффективно искать по префиксу и хранить частотность запросов
Архитектура
- Поисковые запросы → Search QueueSearch Queue
- Workers обновляют Trie с частотностьюTrie с частотностью
- Shard Manager определяет нужный шардShard Manager определяет нужный шард
- Autocomplete API возвращает топ-5 подсказокAutocomplete API возвращает топ-5 подсказок
14. Design YouTube
Видеохостинг с фокусом на транскодирование и CDN.
Ключевые аспекты
Параллельная обработка видео в разных форматах и разрешениях
Раздача видео через глобальную сеть CDN
Граф задач для параллельной обработки
Лента рекомендаций и подписок
15. Design Google Drive
Облачное хранилище с синхронизацией файлов между устройствами.
Требования
- 10M DAU
- 10 GB на пользователя
- Upload / Download файлов
- Синхронизация между устройствами
- Sharing с другими пользователями
Ключевые компоненты
16. The Learning Continues
В финальной главе автор делится источниками для дальнейшего изучения.
Рекомендации автора
- Инженерные блоги крупных компаний (Netflix, Uber, Airbnb, Meta)
- Конференции и выступления (Strange Loop, QCon, InfoQ)
- Книга "Designing Data-Intensive Applications" Мартина Клеппмана
- Практика на реальных задачах и mock-интервью
Итоги по книге Alex Xu
"System Design Interview: An Insider's Guide" — отличная отправная точка для подготовки к System Design Interview.
Сильные стороны
- ✓ Чёткий 4-шаговый фреймворк
- ✓ 12 практических задач
- ✓ Понятные диаграммы
- ✓ Back-of-the-envelope estimation
- ✓ Дополнительные вопросы к каждой задаче
Рекомендации
- ⚠ Дополнить DDIA для теории
- ⚠ Изучить Database Internals для БД
- ⚠ Практиковаться на mock-интервью
- ⚠ Читать инженерные блоги