Job 2026 md

title: Конспект источника 4 — репозиторий System Design Primer целиком (структура, решения с расчётами, Anki) source: https://github.com/donnemartin/system-design-primer (клон master, ae9bbd7 «Fix link for UDP vs TCP», сентябрь 2026) author: Donne Martin (ex-AWS); самый звёздный опенсорс-гайд по системному дизайну (~100k+ stars) конспект: подготовлено 2026-09-18, TASK-45.11; состав репо, все разделы README, 8 решений, Anki. Числа и формулировки расчётов — дословная выжимка источника; «что брать» — наши дополнения. Те же разделы глубже: sdp-guide.md (45.7, словарь паттернов) и sdp-appendix-numbers.md (45.6, числа) — здесь не дублируются, стоят ссылки. статус: карта всего репозитория; главный прирост против прежних конспектов — back-of-envelope расчёты всех 8 решений (§5, сводная таблица — ../knowledge-base.md §2.6) и Anki-карточки (§7)


System Design Primer — весь репозиторий

Прежние конспекты этого репо закрывали README-гайд (sdp-guide.md) и Appendix с числами (sdp-appendix-numbers.md). Этот файл — обход репозитория целиком, включая то, что в них не попало: восемь решений с расчётами (главная ценность — эталоны, по которым сверять этап 2 «оценки» наших разборов), шаблон решения, study guide, Anki-колоды, OO-design и честный список недописанных разделов.

1. Состав репозитория (карта)

Путь Что там Наш конспект / использование
README.md 1839 строк: полный гайд (сеть → БД → кэш → асинхронность → связь → безопасность) + Appendix sdp-guide.md (45.7), sdp-appendix-numbers.md (45.6); выжимки — §3 этого файла
solutions/system_design/ 8 решений по 4-шаговому фреймворку + template/ §4–5 здесь; расчёты — KB §2.6; три эталонных разбора — ../classic-designs.md §5–7
solutions/object_oriented_design/ 6 OO-задач (Jupyter-ноутбуки с кодом) §8
resources/flash_cards/ 3 Anki-колоды (.apkg) §7
images/, переводы, generate-epub.sh иллюстрации; переводы zh/ja; скрипт сборки EPUB всего гайда epub можно собрать командой из корня репо — удобно для телефона

2. Study guide: три трека по времени

Прямой ответ репо на вопрос «нужно ли знать всё» — нет: состав вопросов зависит от опыта, позиции и компании; senior'ов спрашивают шире, architects/лидов — ещё шире. Три режима:

Трек Глубина тем Решения
Short breadth: обзор всех тем + несколько разборов some
Medium breadth + some depth many
Long breadth + more depth most

Обязательная база на любом треке: обзор тем, несколько инженерных блогов компаний, несколько real-world архитектур, фреймворк «how to approach». Наше отображение: short ≈ вариант А методички (слот «завтра»), medium ≈ вариант Б, long ≈ вариант В — совпадение полное.

3. README, раздел за разделом (выжимки)

Нумерация — по порядку следования в README. Разделы, закрытые глубокими конспектами, даются тезисно со ссылкой.

3.1 Motivation, Anki, Interactive Coding Challenges

  • Три цели репо: научиться проектировать large-scale системы, учиться у open source community, готовиться к SD-интервью.
  • Anki-колоды — spaced repetition по ключевым концептам; «great for use while on-the-go» (детали и установка — §7).
  • Сестринский репо автора — interactive-coding-challenges (алгоритмы) со своей Coding-колодой: к нашей секции 2 отношения не имеет.

3.2 How to approach a system design interview question (4 шага)

  • Полный разбор каркаса и его сверка с яндексовскими 6 этапами — sdp-guide.md §1. Здесь коротко: (1) use cases/constraints/assumptions, (2) high level design с обоснованием каждого блока, (3) детали core components, (4) scale the design.
  • После шага 1 SDP явно спрашивает у интервьюера: считать ли back-of-envelope — «clarify with your interviewer» (у нас этап 5 по плану всегда, у них — по договорённости).
  • Back-of-the-envelope calculations вынесены в приложение: степени двойки + latency numbers → KB §1–2.

3.3 System design topics: start here

  • Две входные точки для новичков: видео-лекция Harvard (vertical/horizontal scaling, кэш, LB, репликация, партиционирование БД — 6 тем) и серия статей lecloud «Scalability for dummies» (4 части: clones, databases, caches, asynchronism).
  • Логика «start here»: сначала механика масштабирования, затем трейдоффы, затем конкретные компоненты (DNS, CDN, LB). Наш «порядок чтения» из README system-design построен так же.

3.4 Performance vs scalability, Latency vs throughput

  • Performance-проблема — медленно для одного; scalability — быстро для одного, медленно под нагрузкой; масштабируемость = производительность растёт пропорционально ресурсам.
  • Latency — время операции, throughput — операций в секунду; цель — максимальный throughput при приемлемой latency.
  • Подробнее и с речевыми паттернами — sdp-guide.md §2.

3.5 Availability vs consistency (CAP)

  • Сеть ненадёжна → P выбирать нельзя, выбор между C и A; CP — деньги/инвентарь (риск таймаутом), AP — лента/счётчики (риск устаревшим ответом).
  • PACELC в репо нет — брать из DDIA (KB §12), репо не приписывать. Подробно — sdp-guide.md §3.

3.6 Consistency patterns

  • Weak (memcached, VoIP) / Eventual (DNS, email, асинхронная репликация) / Strong (RDBMS, синхронная репликация) — таблица с «после записи чтение…» — sdp-guide.md §3.

3.7 Availability patterns

  • Fail-over: active-passive (heartbeats, простой только на failover) vs active-active (оба пишут, никакой простой); недостатки — рост сложности и «потеря данных-в-полёте» при падении активной ноды.
  • Replication: master-slave (master пишет, слейвы читают/реплицируются), master-master (оба пишут, конфликты и идентификаторы), синхронная vs асинхронная.
  • Availability in numbers: 99.9% = 8.76 ч/год простоя, 99.99% = 52.6 мин, 99.999% = 5.26 мин; формула последовательных/параллельных компонентов — sdp-guide.md §11, KB §1.3.

3.8 Domain name system

  • DNS — «телефонная книга интернета»: домен → IP; каскад резолверов (браузер → ISP → root → TLD → authoritative), всё кэшируется с TTL.
  • Недостатки (дословный список источника): задержка распространения записей из-за TTL, управляемость NS/переносами, DDoS-атаки на DNS.
  • На секции — одной фразой «запись A/CNAME + TTL, за ней CDN» — KB §13.1; ловушки TTL — Shopify-кейс (45.31).

3.9 Content delivery network

  • Push CDN: контент заливается заранее — предсказуемый трафик, «неактуальный» контент лежит впустую; Pull CDN: тянуть по запросу с origin и кэшировать — меньше обслуживания, лишний поход к origin на первом попадании.
  • На секции: статика и медиа — на CDN почти всегда; недостатки — цена, доп. точка отказа, сложность инвалидации — sdp-guide.md §4.

3.10 Load balancer

  • Распределяет трафик между нодами; L4 (по IP/порту, быстрее, «тупее») vs L7 (по содержимому: URL, куки, заголовки — умнее, дороже); active-passive vs active-active; алгоритмы — random, weighted, least connections, latency-based.
  • Горизонтальное масштабирование = добавить нод за LB; недостатки LB — доп. хоп и SPOF, который сам решают HA-парой — sdp-guide.md §4.

3.11 Reverse proxy (web server)

  • Terminates SSL, compression, кэш, статика, rate limiting — «витрина» перед приложением; LB vs reverse proxy: LB нужен при пуле нод, reverse proxy полезен и с одной.
  • Недостатки: при большом числе коннектов становится узким местом (нужен L4 ниже по стеку); sdp-guide.md §4.

3.12 Application layer (микросервисы, discovery)

  • Web server (reverse proxy) отделён от application layer; слои масштабируются независимо; stateless app-слой — условие горизонтального масштабирования.
  • Микросервисы — SOA-вариант: независимое развертывание/масштабирование против роста сложности; service discovery (Consul, Etcd, ZooKeeper) — как ноды находят друг друга — sdp-guide.md §5.

3.13 Database (RDBMS, NoSQL, SQL vs NoSQL)

  • RDBMS + 6 приёмов масштабирования: master-slave, master-master, federation, sharding, denormalization, SQL tuning — каждый со своим disadvantage-списком (sdp-guide.md §6).
  • NoSQL-типы: key-value, document, wide column, graph — по паре строк на каждый с примерами; NoSQL = «в целом»: меньше структуры, больше гибкости схемы и горизонтального масштаба, слабее гарантии.
  • SQL vs NoSQL — развилка секции: реляционные данные, ACID, сложные запросы → SQL; огромный объём, непредсказуемая схема, «данные — не связи» → NoSQL.
  • LSM vs B-tree под этим углом — DDIA (KB §3.1); в репо внутренней механики движков нет.

3.14 Cache

  • Уровни кэша: client → CDN → web server → database → application (внешний vs встроенный); что кэшируем — запросы или объекты.
  • Когда обновлять — четыре стратегии: cache-aside (приложение само, лениво; минус — холодный miss и race на инвалидацию), write-through (пишем в кэш и БД атомарно; медленные записи, данные не теряются), write-behind/write-back (в кэш сразу, в БД отложено; риск потери при падении кэша), refresh-ahead (предиктивное обновление; риск угадать неверно).
  • Недостатки кэша: поддержка двух источников правды, инвалидация — «две сложные проблемы CS», нужна логика устаревания — sdp-guide.md §7, KB §4.

3.15 Asynchronism

  • Медленное — в очередь: message queues (связь компонентов) и task queues (фоновые работы); масштаб через workers.
  • Back pressure: если очередь растёт быстрее обработки — возвращать давление наверх (ошибку, троттлинг), а не копить бесконечно — sdp-guide.md §8, KB §8.

3.16 Communication (HTTP, TCP, UDP, RPC, REST)

  • HTTP — запрос/ответ поверх TCP; TCP — гарантии доставки и порядок (handshake, ретрансмиты), UDP — без гарантий, зато дёшево (DNS, VoIP, стриминг, игры).
  • RPC — «вызов локальной функции как удалённой»: компактно и быстро для внутреннего трафика; REST — контракт HTTP-глаголов + URL: кэшируемость, простота, отладка.
  • Сравнительная таблица RPC vs REST (сложность/согласованность/кэш/порты) — sdp-guide.md §9; наш речевой шаблон: «наружу REST, внутрь RPC/очереди».

3.17 Security

  • Короткий чек-лист (репо честно скромен): шифрование in transit и at rest, валидация/санитизация ввода (SQLi, XSS), минимум привилегий, авторизация-проверки на каждом слое.
  • Подробно — sdp-guide.md §10; платежи и security на секции — KB §13.7.

3.18 Appendix

  • Степени двойки, latency numbers, доп. список вопросов, real world architectures, company architectures, engineering blogs. Полный разбор — sdp-appendix-numbers.md; уроки реальных систем — sdp-guide.md §12.

3.19 Under development (честные дыры репозитория)

  • Три раздела объявлены, но не дописаны: MapReduce (distributed computing), consistent hashing, scatter gather.
  • Практический вывод: не ссылаться на primere по этим темам. Consistent hashing у нас закрыт KB §6 (шардирование) + Alex Xu гл. 5; scatter-gather — Twitter search (§6 этого файла, solutions); MapReduce — через решения mint/sales_rank (§5) и DDIA гл. 10.

4. Шаблон решения (solutions/system_design/template)

  • Скелет для любого нового разбора: Step 1 (use cases + constraints + calculate usage с той же шпаргалкой конверсии), Step 2 (high level: клиент → DNS/CDN → LB → web/app → БД), Step 3 (по каждому use case — поток компонентов + схема данных + API), Step 4 (scale: benchmark → profile → bottlenecks → trade-offs → repeat).
  • Каждое решение заканчивается «Additional talking points» — фиксированным меню: NoSQL, caching, asynchronism/microservices, communications, security, latency numbers, ongoing. Это готовый чек-лист «что ещё проговорить, если осталось время» — совпадает с нашим этапом 6 (KB §11, methodology §3).

5. Восемь решений system_design

Сводная таблица «задача → числа → выводы» — в KB §2.6. Здесь — по решению: скоуп, ключевые компоненты, масштабирование, что взять.

5.1 Pastebin (или Bit.ly)

  • Скоуп: аноним кладёт текст → короткая ссылка (опционально с TTL); читатель открывает ссылку; аналитика просмотров не realtime; удаление просроченного. Out of scope: аккаунты, редактирование, кастомные ссылки.
  • Расчёт: 10 млн пользователей, 10М записей/мес, 100М чтений/мес (10:1 read:write); паста ~1.27 KB (1 KB контент + shortlink 7 B + метаданные) → 12.7 GB/мес, ~450 GB за 3 года, 360 млн ссылок; 4 writes/s, 40 reads/s.
  • Ядро: RDBMS как большая hash-таблица (shortlink → путь) + Object Store (S3) для контента; уникальность shortlink — PK-индекс; генерация: MD5(ip+timestamp) → Base62 → первые 7 символов (62^7 ≈ 3.5 трлн ≥ 360 млн).
  • Аналитика — MapReduce по логам web-серверов в аналитическое хранилище (Redshift/BigQuery); TTL — скан таблицы по expiration.
  • Масштабирование: 40 rps читает memory cache (трафик неравномерный — кэш же гасит пики), реплики закрывают miss; 4 writes/s — один SQL master-slave; если нет — federation/sharding/denormalization/tuning.
  • Эталонный разбор — ../classic-designs.md §5; сходство с URL shortener (§1) и отличие (хранится контент, а не редирект).

5.2 Twitter timeline and search

  • Скоуп: твит (с фанаутом подписчикам: push-уведомления + email), home timeline, user timeline, поиск. Out of scope: firehose, видимость/retweet-настройки, аналитика.
  • Расчёт: 100 млн активных, 500М твитов/день (15 млрд/мес), фанаут в среднем ×10 (150 млрд доставок/мес); твит ~10 KB (8+32+140 B + 10 KB медиа) → 150 TB/мес, 5.4 PB за 3 года; чтения 100k/s, твиты 6k/s, фанаут 60k/s, поиск 4k/s.
  • Ядро: user timeline — SQL; home timeline — пре-вычисленная лента в Memory Cache (Redis-лист: tweet_id+user_id+meta); Fan Out Service при твите пишет в ленты подписчиков — O(n): 1000 подписчиков = 1000 вставок; параллельно — Search Index и Object Store, уведомления через очередь.
  • Чтение home timeline: Timeline Service — O(1) из кэша + multiget в Tweet Info Service и User Info Service — O(n).
  • Масштабирование: селебрити-проблема — фанаут миллионам подписчиков тормозит минуты и ломает порядок @replies; решение — не фанать звёздам, а мерджить их твиты из поиска при чтении, сортировать на выдаче. Гигиена кэша: ~сотни твитов на ленту, только активные пользователи (30 дней), месяц твитов в Tweet Info.
  • Эталонный разбор — ../classic-designs.md §6; сверка с нашей лентой (§2) — pull-гибрид и race на re-ordering.

5.3 Web crawler

  • Скоуп: краулинг списка URL → реверс-индекс слов → титулы/сниппеты; поиск по готовому индексу (наброском). Out of scope: персонализация, page rank, аналитика поиска.
  • Расчёт: 1 млрд ссылок, рефреш ~раз в неделю → 4 млрд ссылок/мес × 500 KB → 2 PB/мес, 72 PB за 3 года; 1600 writes/s, 40k searches/s.
  • Ядро: очередь links_to_crawl (Redis sorted sets — приоритет по популярности) + crawled_links с сигнатурой страницы (против циклов и дублей); Crawler Service в цикле: взять верхний приоритет → проверить сигнатуру → crawl → задачи в очередь Reverse Index Service и Document Service.
  • Дедупликация: URL — MapReduce с частотой 1; контент — сигнатуры + Jaccard/cosine similarity.
  • Свежесть: timestamp последнего краула; рефреш по умолчанию неделя, популярным — чаще; politeness через robots.txt.
  • Не покрыт нашим классическим разбором — кандидат на тренировочный раунд (очередь + дедуп + politeness); компоненты поиска повторяют 5.2 (search cluster).

5.4 Mint.com

  • Скоуп: подключение финансового аккаунта, ежедневная экстракция транзакций, категоризация (ручной override, без авто-перекатегоризации), месячная аналитика, рекомендации бюджета с уведомлениями.
  • Расчёт: 10 млн пользователей, 30 млн аккаунтов, 5 млрд транзакций/мес; транзакция ~50 B → 250 GB/мес, 9 TB за 3 года; 2000 writes/s, 200 reads/s — 10:1 write:read, write-heavy (транзакции капают ежедневно, сайт посещают редко).
  • Ядро: SQL (accounts, transactions, monthly_spending); экстракция — асинхронно через очередь (SQS/RabbitMQ): подключение аккаунта ставит job, воркеры выкачивают и нормализуют транзакции; категоризация — по справочнику 50 тыс. продавцов.
  • Масштабирование: сессии/агрегаты/последние транзакции — в memory cache (cache-aside); monthly_spending — в аналитическое хранилище; в SQL держать только месяц транзакций, хвост — в S3/warehouse; 2000 writes/s «может быть тяжело для одного master-slave» → SQL scaling patterns.
  • Уникальный для наших эталонов ракурс: write-heavy web-сервис + интеграционная асинхронщина — прямая аналогия банковских интеграций (наш опыт Raiffeisen).

5.5 Social network data structures (соцграф)

  • Скоуп: поиск человека + кратчайший путь до него. Граф не влезает на одну машину, рёбра невзвешенные; 100 млн пользователей × 50 друзей = 5 млрд рёбер, 1 млрд поисков/мес → 400 rps.
  • Ядро: BFS по невзвешенному графу; шардирование пользователей по Person Servers + Lookup Service (person_id → сервер); User Graph Service: lookup → friend_ids → BFS, каждый сосед — снова через Lookup Service (сам признаёт потенциал оптимизации).
  • Ограничение упражнения — без графовых БД и GraphQL: «традиционными системами». На секции мы скорее назовём Neo4j/соцграф из §2 и TAO (45.30) — а это решение даёт «наивный» бейзлайн и аргументацию, зачем спец. системы.
  • Сходство с flock-частью нашей ленты (classic-designs §2, соцграф) — кратчайший путь туда не входит; решение — доп. вопрос уровня «а как бы вы искали связи».

5.6 Query cache (key-value store для поиска)

  • Скоуп: кэш результатов поиска — hit и miss; 10 млн пользователей, 10 млрд запросов/мес; запись 270 B (query 50 + title 20 + snippet 200) → 2.7 TB, если хранить все; 4000 rps. Память ограничена — «нужно решить, что выкидывать».
  • Ядро: LRU — hash map + doubly linked list, O(1) на get/set; hit — поднять в голову списка; miss — Reverse Index Service + Document Service → вставить в голову; переполнение — выкинуть хвост. Полный код на Python (QueryApi, Node, LinkedList, Cache).
  • Масштабирование кэша на много машин: hash-маршрутизация запросов по нодам (упомянут hash-based + hop при ребалансировке) — за подробностями к LB/sharding-разделам гайда.
  • Это тот же LRU, что в OO-design (lru_cache) и в нашем KB §4; на секции «кэш с ограничением памяти» — называть LRU + структуру.

5.7 Sales rank by category (Amazon)

  • Скоуп: еженедельные топы товаров по категориям, обновление ежечасно; 10 млн товаров, 1000 категорий; 1 млрд транзакций/мес, 100 млрд чтений/мес (100:1 read:write); транзакция ~40 B → 40 GB/мес, 1.44 TB за 3 года; 400 writes/s, 40k reads/s.
  • Ядро: логи Sales API на S3 → двухшаговый MapReduce: (1) (category, product) → sum(quantity) за неделю; (2) distributed sort — mapper эмитит (category, −qty) → product, shuffle сортирует, reducer — identity. Результат — готовая таблица sales_rank в SQL.
  • Чтение — дёшево: precomputed агрегат; ценой является hourly-батч. Аналитика — по схеме 5.1/5.4 (warehouse).
  • Уникальный ракурс для нас: precomputed read model — то же семейство, что materialized views и наш фанаут ленты; «тяжёлое читаем лениво/пре-вычисленно» — готовая фраза для этапа 4.

5.8 Scaling to millions of users on AWS

  • Скоуп: не сервис, а лестница эволюции архитектуры от 1 пользователя до десятков миллионов; 1 млрд writes/мес, 100 млрд reads/мес (100:1), 1 KB/write → 1 TB/мес, 36 TB за 3 года; 400 writes/s, 40k reads/s.
  • Метод: каждый шаг — benchmark/load test → profile → узкое место → изменение с trade-offs → повторить. «Не прыгать сразу в финальную схему» — цитировать на секции дословно.
  • Ступени: Users+: S3 для статики + MySQL на отдельную машину (RDS) + VPC/приватные сабнеты. Users++: LB (ELB/HAProxy, SSL на LB) + несколько web-серверов по AZ + master-slave failover + отделение web от app слоя + CDN. Users+++: memory cache (частый контент, сессии → stateless → autoscaling) + MySQL read replicas + разделение read/write API. Users++++: autoscaling по метрикам CloudWatch (min/max, время суток или CPU/latency/трафик) + автоматизация DevOps (Chef/Puppet/Ansible) + наблюдаемость (хост/агрегат/логи/внешний пинг/инциденты/Sentry). Users+++++: хвост данных в warehouse (Redshift), кэш масштабируется на 40k reads/s, 400 writes/s «может быть tough» → SQL scaling patterns, NoSQL (DynamoDB), очереди + workers для асинхронных работ (пример: аплоад фото → очередь → worker делает thumbnail).
  • Эталонный разбор — ../classic-designs.md §7; это «скелет этапов 4–6» нашего фреймворка: аргументация «зачем добавляем каждый блок».

6. Anki-карточки (проверено 18.09.2026)

Состав и проверка целостности:

Колода Записей Тип Содержимое
System Design.apkg 42 Basic словарь гайда: термины и трейдоффы (Performance vs scalability, Consistency patterns, …)
System Design Exercises.apkg 8 Basic промпты всех восьми решений — «спроектируй X»
OO Design.apkg 6 Basic промпты OO-задач (deck of cards, call center, hash map, …)

Файлы — валидные Anki APKG (SQLite collection.anki2 + media), проверено распаковкой; поля — HTML-разметка, стандартный тип заметки Basic. Установка: Anki Desktop (apps.ankiweb.net, Win/Mac/Linux, бесплатно) — File → Import или двойной клик по .apkg; AnkiDroid (Android, бесплатно); AnkiMobile (iOS, платный). Синхронизация между устройствами через AnkiWeb (бесплатный аккаунт). CLI-плеера не нужно и нет смысла — механика spaced repetition требует самого Anki.

Рекомендация — ../methodology.md §6.6: до слотов использовать не как «учить с нуля», а как самопроверку словаря (пробежаться по 42 картам = активный recall трейдоффов); полный spaced-repetition режим — после секции.

7. Object-oriented design (6 задач)

  • Задачи (ноутбуки с кодом и диаграммами): hash map, LRU cache, call center, deck of cards, parking lot, online chat.
  • Для нашей секции релевантны первые два: hash map и LRU cache — это же внутренности query cache (5.6) и стандартный доп. вопрос «а что внутри кэша». Остальные — классика OO-раунда, к SD-секции 2 прямого отношения не имеют.
  • Приоритет: низкий; брать только если на секции уйдут в структуру данных кэша.

8. Что взято в нашу базу (карта переноса)

Из репо Куда Задача
Back-of-envelope всех 8 решений ../knowledge-base.md §2.6 — таблица «задача → числа → выводы» 45.11
Pastebin, Twitter timeline+search, scaling AWS ../classic-designs.md §5–7 — подробные разборы как эталоны 45.11
Anki: установка, состав, рекомендация ../methodology.md §6.6 45.11
Каркас 4 шагов, трейдоффы, CAP, паттерны sdp-guide.md (было, 45.7) —
Числа Appendix, список вопросов sdp-appendix-numbers.md (было, 45.6) —
Селебрити-проблема фанаута, LRU-структура, precomputed rank KB §2.6 (выводы) + classic-designs §6/§7 (в разборах) 45.11

Связанные документы

  • sdp-guide.md — глубокий конспект гайда README (45.7)
  • sdp-appendix-numbers.md — Appendix: числа и список вопросов (45.6)
  • ../knowledge-base.md §2.6 — сводная таблица расчётов восьми решений
  • ../classic-designs.md §5–7 — эталонные разборы pastebin, twitter, scaling AWS
  • ../methodology.md §6.6 — Anki-рекомендация