System design-інтерв’ю: карта

На system design-інтерв’ю вам дають одне розпливчасте речення — скажімо, «зроби скорочувач посилань» — і 45 хвилин на таймері. Єдиної правильної відповіді тут немає: готуватися важко, а потонути в деталях ще легше.

Цей постер збирає всю картину на одному аркуші: що оцінює інтерв’юер, як розпланувати час, які числа тримати під рукою, дев’ять родин питань і вісім патернів за ними. Усі розрахунки спираються на один наскрізний приклад. А як ці 45 хвилин виглядають з обох боків столу, розповідає стаття Як проходить system design-інтерв’ю.

trishchuk.com / learn
Інфографіка

System design-інтерв’ю

Про що питають, як розбити 45 хвилин, які числа тримати в голові та жменька патернів, на яких усе тримається.

КлієнтБалансувальникAPI-сервериКешЧергаБаза данихВоркериКлієнтБалансувальникAPI-сервериЧергаБаза данихКешВоркери
Схема, яку ви малюватимете майже в кожній відповіді. Рожева лінія — це шлях читання; починайте розрахунки саме з нього.

Що оцінює інтерв’юер

П’ять сигналів. Схема — лише спосіб їх показати.

  • Уточнення вимог

    Питаєте, що будуємо, для кого і в якому масштабі, ще до першого блоку на схемі.

  • Компроміси

    Прямо називаєте ціну кожного рішення: що виграєте і чим за це платите.

  • Оцінка

    Оцінюєте масштаб у порядках величин, і вже самі числа підказують форму системи.

  • Глибина

    Докладно розбираєте один-два компоненти замість перелічувати десяток назв.

  • Комунікація

    Міркуєте вголос, ловите підказки й самі ведете розмову, не чекаючи навідних питань.

Як розподілити сорок п’ять хвилин

Послідовність важливіша за секундомір.

  1. 1

    Вимоги 5 хв

    Основні функції, нефункціональні цілі (затримка, доступність, узгодженість) і те, що свідомо лишаєте за дужками.

  2. 2

    Оцінка 5 хв

    QPS на читання й запис, обсяг сховища, трафік — навантаження, яке система має витримати.

  3. 3

    API і модель даних 7 хв

    Кілька ендпоїнтів і головні сутності разом із тим, як до них звертатимуться.

  4. 4

    Високорівнева схема 10 хв

    Клієнт, балансувальник, сервіси, кеш, база, черга — і проведіть схемою один реальний запит.

  5. 5

    Глибоке занурення 13 хв

    Найскладніший вузол — його часто обирає сам інтерв’юер: схема даних, шардинг, кешування чи узгодженість.

  6. 6

    Вузькі місця і відмови 5 хв

    Що впаде першим, гарячі ключі, єдині точки відмови, моніторинг і за що ви взялися б далі.

Числа, які варто знати

Дві хвилини арифметики зазвичай вирішують, якою буде система.

Оцінка сервісу

10 млн активних користувачів щодня, на кожного припадає 20 читань і 2 записи. Один запис займає 500 Б, відповідь — 2 кБ, дані зберігаємо 5 років.

ВеличинаРозрахунокРезультат
Читань на день10 млн × 20200 млн
Середній QPS читання200 млн ÷ 86 4002,3 тис.
Піковий QPS читання× 36,9 тис.
Записів на день10 млн × 220 млн
Середній QPS запису20 млн ÷ 86 400231
Піковий QPS запису× 3694
Сховище за 5 років20 млн × 500 Б × 365 × 518,3 ТБ
Трафік читання2,3 тис./с × 2 кБ4,63 МБ/с
Кеш для гарячих 20%, верхня межа20% × 200 млн × 2 кБ80 ГБ

Пік беремо як 3× від середнього, а 86 400 секунд подумки округлюємо до «приблизно 10⁵». Тут усе ясно: одна база витримає записи, а кеш — читання.

Драбина затримок

  1. Звернення до L1-кешу1 нс1 с
  2. Звернення до оперативної пам’яті100 нс1,67 хв
  3. Випадкове читання з SSD100 мкс1,16 дн
  4. Запит туди й назад у межах дата-центру500 мкс5,79 дн
  5. Позиціювання диска (seek)10 мс116 дн
  6. Запит туди й назад через океан150 мс4,76 р.

Порядки величин за Dean (2009), округлені й оновлені під SSD. Це орієнтири, а не бенчмарки: головне — у скільки разів відрізняються рядки.

Доступність і дозволений простій

ЦільЗа рікЗа місяць
99%3,65 дн7,3 год
99,9%8,76 год43,8 хв
99,99%52,6 хв4,38 хв
99,999%5,26 хв26,3 с

Кожна додаткова дев’ятка ріже дозволений простій удесятеро — і різко підвищує ціну розробки й підтримки. Питайте одразу, скільки дев’яток продукту справді потрібно.

Питання складаються в родини

Опануйте родину — і нове питання стане просто варіацією.

Пошук за ключем і сховища

Скорочувач посилань, Pastebin, key-value-сховище, Dropbox

Генерація ID, хешування, шардинг, кешування під читання.

Стрічки й соцмережі

Стрічка Twitter, Instagram, стрічка новин

Fan-out під час запису чи читання, ранжування, акаунти-знаменитості.

Повідомлення й реальний час

Чат, сповіщення, спільне редагування

Постійні з’єднання, порядок, гарантії доставки, статус онлайн.

Медіа

YouTube, Netflix, обмін фото

Об’єктне сховище, конвеєри транскодування, CDN, завантаження з докачуванням.

Геолокація

Uber, пошук поруч, карти

Індекси geohash чи quadtree, рухомі об’єкти, зіставлення (matching).

Інфраструктурні примітиви

Rate limiter, генератор ID, черга повідомлень, планувальник задач, вебкраулер, розподілене блокування

Питають про сам компонент: алгоритми, сценарії відмов, міф про exactly-once.

Транзакції

Бронювання квитків, платежі, готелі, склад

Подвійне бронювання, ідемпотентність, saga, сильна узгодженість там, де йдеться про гроші.

Аналітика

Підрахунок кліків реклами, top-K, лідерборд

Потокова обробка, вікна, наближений підрахунок, запізнілі дані.

ML system design (рекомендації, ранжування, антифрод) — окрема історія. В основі все те саме, але всередині з’являється модель: ознаки, навчальні дані, затримка інференсу й зворотний зв’язок.

Патерни, на яких тримаються питання

Ці вісім ідей трапляються майже на кожній співбесіді.

ПатернЩо розв’язуєІнструментиЯку ціну платите
Fan-out під час запису чи читанняЗатримка стрічки проти вартості записуInbox на кожного підписника, злиття під час читання, гібридМноження записів (write amplification) або повільне читання
ШардингОднієї машини замалоConsistent hashing, hash- чи range-партиціїРебалансування, гарячі ключі, запити між шардами
КешуванняЧасті читання перевантажують базуCache-aside, write-through, TTL, CDNЗастарілі дані, інвалідація, stampede
РеплікаціяДоступність і масштаб читанняLeader-follower, кворум, multi-leaderЛаг реплікації, конфлікти
Черги й потокиСплески трафіку чи довгі задачіЧерга повідомлень, лог, воркери, retry з backoffПорядок, дублікати, складність супроводу
ІдемпотентністьПовторний запит не має спрацювати двічіКлюч ідемпотентності, таблиця дедуплікаціїСтан, який треба зберігати й чистити
Вибір узгодженостіКоректність чи доступність під час відмовиСильна, eventual, read-your-writesЗатримка й доступність (CAP, PACELC)
Імовірнісні структуриТочний підрахунок з’їдає забагато пам’ятіBloom filter, HyperLogLog, count-min sketchКонтрольований рівень помилки

Fan-out: скільки коштує кожен варіант

Push розкладає пост у стрічку кожного підписника — скільки підписників, стільки й записів:

  1. Друг 200200 записів за один пост
  2. Популярний акаунт 10 тис.10 тис. записів за один пост
  3. Знаменитість 10 млн10 млн записів за один пост

Pull перекладає роботу на читання й на ходу зводить стрічки всіх, на кого ви підписані: близько 300 рядків, якщо стежите за 300 людьми.

Push копійчаний для 200 підписників і руйнівний для 10 мільйонів. У pull усе навпаки: дешевий запис, важке читання. Реальні системи поєднують обидва підходи: push для звичайних акаунтів, pull для знаменитостей.

Робіть

  • Спершу питайте. Дві хвилини запитань заощаджують десять хвилин переробок.
  • Називайте ціну. Кажіть прямо: «Беру X і свідомо приймаю Y».
  • Проведіть один запит. Пройдіться схемою для читання й запису від початку до кінця.
  • Спирайтесь на числа. Кожен блок на схемі мають виправдовувати QPS і обсяг даних.

Уникайте

  • Жонглювання назвами: кидати Kafka чи Cassandra без пояснення, навіщо вони тут.
  • Ігнорування збоїв: інтерв’юер неодмінно спитає: «А якщо цей вузол упаде?».
  • Суперечок із підказками: ними інтерв’юер показує, що хоче побачити.
  • Поверховості: десять блоків на дошці, і жодної деталі всередині.

Тренуйтесь

  • Ставте таймер: одна задача, 45 хвилин і міркування вголос.
  • Малюйте з пам’яті базову схему кожної родини, доки рука не робитиме це сама.
  • Перераховуйте оцінки з нуля, а не завчайте готові відповіді.
  • Розбирайте задачі в парі з колегою. Уміння пояснювати важить не менше за саму архітектуру.
Тарас Тріщук Структура за типовою практикою співбесід; кожне число пораховано на цій сторінці trishchuk.com/learn

Звідки це взято