Привет, из-за последних событий решил поделиться материалами по собеседованиям в зарубежные компании, которые сам собирал последние несколько лет. Описанное ниже - смесь из личного опыта, историй на различных форумах, и анекдотов собранных через знакомых - поехали.

Что такое L6

Внутри FAANG-подобных компаний существует система уровней, от которых зависят обязанности и зарплата. В разных компаниях уровни могут называть немного по разному, но мы возьмем за стандарт Google. Уровни для программистов начинаются с L3, все что ниже - для не программистких должностей. L3 - это джун, L4 - мидл, L5 - сеньор, L6 - этакий тимлид. Выше уровни тоже есть, но попасть туда без достижений в индустрии невозможно. А вот расколоть L6, просто отлично подготовившись к собеседованию, можно. Сколько там получают люди - можно посмотреть на levels.fyi.

Вступление

Что такое System Design Interview? Стоит понимать, что все FAANG компании оперируют в масштабах всего земного шара. При решении большинства задач нужно учитывать, что пользоваться вашими сервисами будут десятки и сотни миллионов людей, поэтому и интервью заточены под вопросы масштабирования. Банальные задачи, а-ля хранить а что пользователь лайкнул, превращаются в планирование распределенное системы, прикидывание необходимых мощностей, размеров диска, состояния гонки. System Design Interview проверяет умение кандидата оперировать дизайном подобных систем на высоком уровне, умением прикидывать API, различные сервисы на бэкенде, способы хранения данных. Даже если вы никогда не работали с дизайном систему для большой пропускной способности, подготовиться и узнать про все это довольно просто. Точнее, шаги простые, но чтобы пройти их - нужно много терпения и усидчивости.

System Design Interview длится 45 минут, иногда их может быть несколько. Целью не является действительно уметь делать руками все нижеизложенные вещи, но за эти полтора часа уметь раскладывать сложную систему на отдельные компоненты, оперируя глубокими знаниями о возможностях различных систем и баз данных - и не важно, если вы никогда не применяли эти знания на практике. System Design интервью может уходить глубоко в детали, но про них нужно только рассказать ртом.

В зависимости от того, насколько глубоко вы последуете этому плану, подготовка может занять от 3 до 12 месяцев. На 3 месяцах вы вероятнее получите Л4, на 9+ месяцах - Л6. Не нужно быть гением, просто трудолюбивым человеком и знать английский. Не позволяйте никому говорить вам что вы не можете зайти на сеньор позиции в FAANG - все в ваших руках. Важны мотивация, фокус и следование плану.

Все материалы лучше читать и слушать на английском, чтобы оперировать корректными терминами на самом интервью и не потерять часть информации в переводе.

Материалы

Откуда начать? “Высоконагруженные приложения” Мартина Клеппмана. У этой книги низкий порог входа, и она заполнит абсолютно все теоретические пробелы. Читайте ее медленно. Не нужно пропускать секции или делать вид что поняли. Если чего-то не понимаете - остановитесь, посмотрите на референсы, погуглите термины. В этой книге нет вообще ничего бесполезного, от корки до корки. Основательно понять эту книгу - половина работы. Часть 1 очень полезна для умения выбирать правильные базы данных. Часть 2 развеет страхи на тему шардирования и выбора механизмов репликации. Часть 3 расскажет как склеить большую систему вместе из маленьких частей - главное понять разделение Системы записей и производных данных.

Когда вы закончите с “Высоконагруженными приложениями”, вы должны уметь проснуться посреди ночи и объяснить как LSTM базы данных используют красно-черные деревья для сортировки лога в памяти и зачем они это делают.

Дальше - нужно пройти курс “Grokking the system design interview”. Там есть бесполезные уроки, но тем не менее, нужно запомнить мельчайшие детали большинства решений. Детали могут быть более важны чем картина в целом. Дизайните typeahead suggestions? Должны рассказать про экспоненциальное скользящее среднее для взвешивания результатов выдачи.

Видео. Посмотрите видео с ютюб каналов InfoQ и @scale о реальных системах. Посмотрите видео от Nathan Bronson про Tao, Caches и т.д. Посмотрите видео Nishtala про memcache в Фейсбуке. Посмотрите Kulkarni про Facebook Live. Посмотрите Susheel Aroskar про Zuul Push.

Главное не пропускать секции которые не понимаете. Например, в последнем видео про Zuul Push упоминается Apache Netty - прочитайте про него, поймите что это такое. Пойдите глубже, поймите epoll и его красно-черные деревья. Пойдите еще глубже и поймите TIMED-WAIT трюк в TCP, который сохраняет соединения вебсокетов. Или вот: он упоминает, что лоуд балансеры не могут справиться с вебсокетами - почему? Разберитесь! Чем глубже вы можете уходить на интервью, тем более высокий уровень вам могут дать. L6 - это про глубину. Если во время дизайна вы нарисуете на доске один большой квадрат с припиской “Server” вместо многих компонентов - пойдете джуном.

Дальше - книжка Site Reliability Engineering от Гугла. Даже если вы не будете девопсом или сисадмином, в этой книжке есть глава про Non-Abstract Large System Design. Нужно понять ее и запомнить чуть ли не наизусть. Особенно часть про оценки размеров, ресурсов, времени.

Ограничения

Если вы не можете быстро прикидывать примерный размер данных, скорости вычислений, количества машин - получить L6 никогда не получится. Как это сделать? Практикуйте возведение в степени 10, как это описывается в NALSD главе книжки от Гугла. Попрактикуйтесь со случайными числами. Всегда тащите единицы измерения с собой и уменьшайте их при делении и умножении.

Наприме, помните, что Кассандре нужно +-30% свободного места для сжатия (вы же прочитали про LSTM в первой части “Высоконагруженных приложений?”). Также помните, что только +-85% диска можно использовать для базы данных - остальное съесть ОС. 3-5% дисков умирает каждый год, учтите это, не забудьте умножить на фактор репликации, и помните что Кассандра начинает тормозить на дисках больше 2 террабайт.

Прочувствуйте чем может быть ограничена ваша система. Может быть диском (дампы логов)? Может быть CPU (кодирока лайв трансляций)? Или все-таки память (выдача ленты в социальной сети)? Как только вы начнете чувствовать это, вы сможете дизайнить сервисы с разными техниками масштабирования. Поэтому вам нужны числа, не чтобы блистать свой математикой, но найти чем ограничена ваша система и как ее масштабировать на основе этих вычислений.

Приблизительные расчеты

Вы можете подумать - зачем вообще на System Design считать какие-то числа. Только затем, чтобы прикинуть количество машин, дисков и т.д. Или чтобы понять, может ли что-то вместиться на одну машину или нет, в основном в память. Часто это сразу очевидно, но 10 секунд примерных расчетов должны это подтвердить.

Например: как раздавать ленты миллиона людей эффективно? Ну, сколько постов нужно отдавать сходу каждому человеку? Допустим 10. Если мы будем сохранять только ID (допустим 8 байтов), можно хранить их все в redis.

8 байт/пост * 10 пост/лента = 80 байт/лента
1 миллион лент * 80 байт/лента = 10^61080 = 8*10^7 байт
80 миллионов байт означает 80 мегабайт - легко помещается в память.

Это был простой пример, но заметьте важный момент - всегда тащите единицы измерений с собой: байт/пост, пост/лента. И второе - всегда используйте степени десятки чтобы не упустить нужный ноль.

Пример из реальной жизни:

8-байтный ID на пост 800 постов в ленте 500 миллионов лент Фактор репликации 3

800 пост/лента * 8 байт/пост = 8 * 10^2 * 8 байт/лента= 64 * 10^2 байт/лента
500 миллионов лент * 64 * 10^2 байт/лента = 5 * 10^2 * 10^6 * 64 * 10^2 байт = 5*64 * 10^(2+6+2) байт = 300 * 10^10 байт = 3 * 10^12 байт = 3ТБ

3ТБ * 3 (репликация) = +- 10 ТБ. Прикинув что на каждой машине 64 ГБ памяти, из которых можно пользоваться только 50, получается 10 / 50 = 2 * 10^3 = 2000 машин.

Главное не забывать протаскивать с собой единицы измерения, иначе можно запутаться посреди формулы. Этот сервис ограничен по памяти.

Посмотрите Raffi Krikorian's Timelines at Scale на InfoQ чтобы увидеть эти расчеты в деле.

Обычно, у вас получится несколько сервисов с разными механизмами масштабирования. Проведите ваши расчеты рано чтобы прочувствовать какие будут ограничения, и заранее спланировать масштабирование.

Вот пример сервиса, ограниченного по QPS. Вам говорят, что вам нужно логгировать 100 миллиардов событий в день. Кажется, что это много, но давайте переведем это в секунды, чтобы убедиться.

100 * 10^9 событий/день / 86400 секунд/день (можно округлить до ближайшего удобного числа - 86000) 10^11 / (8*10^4) событий в секунду = 1/8 * (10^7) событий/сек = 10/8 миллионов QPS = 1.2 миллиона QPS

Чтобы прикинуть количество машин, необходимых для этого сервиса, возьмите какое-нибудь удобное число, которое похоже на то, сколько может выдержать одна машина, и поделите.

Можете почитать datastax capacity planning, чтобы посмотреть числа для Кассандры и других баз данных.

Вот некоторые числа, которые обычно можно использовать без доказательств в своих вычислениях.

Сжать 1КБ с Zippy - 0.003 мс
Послать 1КБ по 1Gbps сети - 0.01 мс
Прочитать 4МБ последовательной памяти - 1 мс
Прочитать 4МБ с SSD - 20 мс
Прочитать 4МБ с HDD - 80 мс
1 disk seek - 10 мс
Раундтрип внутри датацентра - 150 мс
Пропускная способность внутри датацентра - +-100Gbps
Видео - 10MB/minute
Сервер может иметь 100-150GB свободной для использования памяти
Кассандра утилизируется лучше всего с 1-2ТБ / ноду
1Gb/s → 125MB/s
Кластер Кассандры может выдерживать 10-15000 запросов на ноду и растет линейно от количества нод.
720р видео - 1.5Mbps
340р видео - 150Kbps

Заключение

Помимо System Design Interview есть так же поведенческое и на программирование. Эти интервью намного проще и их гайд не покрывает, и структуированных материалов по ним достаточно, но при желании могу рассказать в другом посте.