System Design Interview – An Insider's Guide
[!Warning] Дисклеймер - это не то, чтобы выдержка. Просто небольшой пересказ книги. Важно, что её не надо просто читать. Лучший способ использование этой книги следующий:
- открываете главу-задачку, которая заинтересовала
- рисуете свою схему сервиса
- сравнивайте ответ из книги со своей схемой текстом
Первая глава была о всех простых способах масштабирования веб сервиса - начиная с горизонтального масштабирование stateless сервисов за лоад балансерами, и заканчивая гео роутингом по нескольким ДЦ. Так же были рассмотрены случаи, когда добавлять кеши и noSQL базы данных для масштабирования, а для SQL горизонтальное масштабирование через репликацию и шардинг.
Вторая глава была про быструю оценку решений на основе известных решений и допущений. Обычно речь идёт о том, что нам даны входные числа вида MAU, основного количество пользователей и прочего, а мы их можем перевести в RPS и data volume. Предлагается в рамках этих вычислений использовать только округления до 10, всегда использовать меры вычисления (не 5, а 5 мегабайт), и писать свои допущения, которых не было в задачке.
В третьей главе говорилось о том, что надо успеть за часовой процесс интверью. Он включает в себя четыре шага: уточнение задачи, предложение высокоуровневого дизайна, уточнение важных элементов и обощение решение с потенциальными проблемами.
В чётвёртой главе рассматривалось проектирование rate limiter. Основное обсуждение шло вокруг выбора алгоритма решения задачи, нежели чем ради построения инфраструктуры вокруг. Для инфы просто сделали middleware + redis.
В пятой главе рассматривается разработка [[consistent hashing]]. Это подход для распределения данных по нескольким сервера. В качестве примеров было использование: модуль, кольцевое хеширование, виртуальные ноды. Основная проблема в таком подходе находиться на уровне решардирования.
В шестой главе разбиралась разработка key-value database. Поговорили про то что на одном сервере это сделать тривиально, а вот в случае распределённой системы мы сталкиваемся с [[CAP теорема]]. Для создания отказоустойчивой и консистеной распределённой системы мы должны воспользоваться консистентным хеширование с выбранным кворумом по записи и репликации. Для разрулирование реплик придётся добавить версионирование ключей. Для полного ответа на вопрос что происходит в такой системе необходимо отдельно рассмотреть read и write path.
В седьмой главе рассматривалась проблема генерации уникального ID в распределённой системе. Для решения этой проблемы можно использовать автоинкремент с пропусками, uuid, централизованный сервер автоинкремента, а так же есть спецификация snowflake. Она даёт лексиграфическую сортировку и размер в 64 бита, при этом с ограничениями по пропускной способности.
В восьмой главе идёт задачка про дизайн сокращателя ссылок. Для этого можно использовать два подхода: один с генерацией случайной последовательности из 7 символов, второй генерацией base62 на основе уникального идентификатора. Для редиректов стоит воткнуть кеш.
В 10 главе рассказывалось как сделать единый сервис нотификаций для большой компании.
В 12 главе было про построение чата. И мне кажется, что там наконец-то прочитал хорошую разницу между polling и long polling. В polling запросы к серверу идут с частотой раз в N времени, а в long polling этот N устанавливается серверов и коннект висит. Дальнейшее развитие - это websockets, где надо держать stateful ноды для коннекта. Необходимо в рамках задачи рассмотреть флоу между 1-1 сообщениями и групповыми. Для них будет различаться флоу по тому как идёт запись и рассылка сообщений. Дополнительная функциональность - это рассмотрение online не online. А дальше уже вопрос про e2ee, media files, load time & error handling.
В 13 главе идёт речь о разработке autocomplete сервиса. Она говорит о том, чтобы вернуть top k популярных запросов при пользовательском вводе текста. Для этого предлагается использовать один из типов tree structure, а именно [[trie]]. Обновлять такую структуру на каждый пользовательской запрос стоит дорого. поэтому необходимо чтобы был разделён write path. Он будет состоят из ~~клик ~~search стрима в виде логов, которые потом аггрегирует и периодически обновляют. Интересной штукой было, что надо ещё добавить фильтрацию всяких негативных терминов и это проще делать на лету.
Цитаты
- 202401091644: tips for back-of-the-envelope estimation
- 202401101549: dos and donts for system design interview
- 202401101550: ask-assume-propose
- 202401101551: right questions to ask on system design interview
- 202401181238: problems - techinques mapping
Задачи
- #task Обработать все выдержки из книги в рамках Zettels ⏳ 2024-02-26 ✅ 2024-02-27
- #task Написать выдержку из книги ⏳ 2024-02-28 ✅ 2024-02-27
- #task Доработать свои заметки на основе идей из книг