О чем думать на NALSD собеседовании

в 7:07, , рубрики: Google, it-эмиграция, nalsd, Анализ и проектирование систем, библиотеки, Блог компании Google, высокая производительность, книги нужно читать, многобукофф, работа в google, распределенные системы, собеседование

Я описывал ранее типичное кодинг-интервью. Помимо кодинга почти всегда есть вопрос на проектирование систем. (Large) System Design. В случае собеседований на SRE, это еще более интересный (как по мне) зверь — NALSD. Non-abstract large system design. Главное отличие между SWE и SRE именно в этих буковках “NA”.

О чем думать на NALSD собеседовании - 1 В чем же отличие, и как подготовиться к нему? Давайте разберём на примере. В качестве примера возьмём что-то весьма материальное, что-то такое, что точно никто никогда не спросит на реальном собеседовании (в гугл) :)

Например — давайте спроектируем библиотеку. Для бумажных книг, обычную такую. Весь текст ниже был написан в один присест за примерно час, чтобы примерно показать что можно успеть, и что важно успеть. Так что уж простите за сумбурность, но я так мыслю (а значит, так существую).

NALSD вопрос: Спроектируйте публичную библиотеку.

Сперва, интересуемся о характеристиках нагрузки, либо делаем разумное предположение сами. Раз уж это вопрос о масштабируемой системе, это минимум город миллионник. Стоит подумать о вариантах — одно большое здание, или районные библиотеки плюс хранилище. Как мне кажется, последнее разумнее. Особенно, если не город, а города.

Итак, сфокусируемся на текущий момент на системе одного города (с некоторыми оговорками, мы сможем применить аналогичный механизм уровнем выше для масштабирования на много городов). Итак, город миллионник. Округлим цифры для удобств прикидок — пусть будет 1млн вероятных читателей. Читатели собираются почитать в произвольный момент времени независимо друг от друга. Так что можем прикинуть как простой пуассоновский процесс. Но “на бегу” считать нормально будет сложно, так что сделаем еще один шаг упрощения и возьмём просто, что 1% читателей захотят взять книжку в день. Итого, для дальнейших расчетов примем 10000 взятий книжек в день.

Наша задача — обеспечить возможность выдачи 10000 книг в день (плюс возврата тех же 10000 в какой-либо другой день в будущем, кстати) в городе миллионнике. В этот момент вопрос моно-библиотеки или районных уже отпадает (кстати, чтоб весь миллион был потенциальными читателями, надо чтоб они могли добраться до библиотеки за разумное время, иначе желание взять книгу точно отвалится по таймауту). Итак, нам нужно оценить ёмкость каждой локальной библиотеки. Правильно это делать с учетом плотности населения и достижимости, но поскольку это не сильно влияет на саму систему, для простоты расчетов представим, что мы их размещаем равномерно. Но это всё равно не говорит о том, как мы можем их делить. Очевидно, что поставить 10000 библиотек с одной книгой равномерно по городу не имеет смысла, поэтому надо понять а что же имеет смысл. Уходим на уровень ниже.

Итак, одна библиотека. Чтобы она имела смысл, большая часть пришедших должна найти нужную им книгу. Это означает, что нам потребуется вести учет и прогноз самых популярных запросов и держать эти книги наготове. Затем, нам надо держать в принципе ассортимент. Навскидку, я бы сказал что локальная библиотека должна иметь не меньше 1000 наименований, самые топы из них во множестве экземпляров, топовых больше, хвостовых меньше. Средняя книжка в нашей библиотеке читается от 3 дней до 2 недель (на самом деле, характеристика зависит от книги, потребуется тут отдельный анализ), примем равным в неделе в среднем и двигаемся дальше. То есть взятая книга отсутствует примерно неделю, так что топовых книг надо с запасом на неделю (потом они начнут восстанавливаться от возвратов).

Примем средний коэффициент раздувания в 6. Так что ёмкость хранилища начинается от 6000 книг. Меньше означает что это только маленький топ, который всё равно может в некоторых случаях помочь (например, островок с “сумерками” в супермаркете возле детской игровой комнаты), но мы оставим пока это за пределами.

В “равновесном” состоянии, в день возвращают и берут примерно поровну, плюс-минус разброс, но нам нужна еще возможность принять повышенное число пиковое число возвратов (например, из-за внешней синхронизации типа отпусков или смены моды). Правильно — моделировать. Но здесь и сейчас прикинем как буфер в треть. Итого, поддерживаем 6000 книг доступных к выдаче, плюс место еще на 2000 про запас.

Итак, нам нужен юнит, способный хранить 8000 книг. Ежедневное пополнение очень дорого, значит это на неделю или две. Две недели, 6000 книг, с перекосом в возвратах это примерно на 300 в день. В момент открытия мы можем забить все 8000 книг, чтоб создать начальные 2000 в обороте до первых возвратов. 2000 за 3 дня = около 600 книг в день, плюс буфер = 800 книг в день.

Прикинем пропускную способность и ограничения хранилища. Одна книга занимает в среднем 2 сантиметра линейного пространства, 8000 книг — 160 метров. сворачиваем в 4 раза по вертикали, 40 метров. Разбиваем на ровные 5-метровые стеллажи, получаем 8 стеллажей по 4 полки 5 метров длиной. Один библиотекарь (или робо-библиотекарь) сможет работать с двумя стеллажами, извлечение одной книги потребует до 5 секунд дойти до неё, 5 секунд достать или поставить книгу, 5 секунд обратный ход, итого 15 секунд. 4 библиотекаря обеспечат нас приблизительно 15 книгами в минуту максимум, то есть 900 книг в час из хранилища приблизительно.

Добавляем время на обработку запроса (10с), поиск (5с), внесение в систему приема и выдачи(2с) => 400 книг в час. Значит хранилище в пике может выдавать-принимать 400 книг в час, следовательно 800 книг в день достижимы за 2 рабочих часа.

Теперь считаем другие характеристики: чтобы выдавать 400 книг в час 4 людьми, надо вместить 100 человек в зал ожидания в очередь перед окошком обработки, и чтобы эти люди не создавали толпы на входе-выходе. То есть входная группа должна пропускать 400 человек в час в обе стороны. Выходит, что главным ограничителем будет даже не хранилище, а емкость зала и входной группы.

Значит, можно будет найти оптимальное соотношение хранилища и зала при более точных расчетах.

Итак, с юнитом разобрались, возвращаемся на уровень выше. Мы прикиниули общую нагрузку на библиотеку примерно на 10000 книг в день, один юнит мы посчитали на 800 книг в день, то есть нам надо 12.5 юнитов. При геораспределении по городу, до каждого читателя будут достижимы один-два альтернативных юнита (на границах города) а то и 3-4 (внутри), что позволяет немного сглаживать пики трафика и/или повышенного спроса на конкретные позиции.

Так же мы знаем, что в любой момент любая библиотека может быть закрыта (пожар, сан.инспекция, покраска ручек холодильников или еще что), с ростом числа их, вероятность совпадения выпадения двух из жизни растёт, так что нам надо по запасному юниту на каждые 5-6 юнитов. Итого, 15 юнитов должны обеспечить требуемую производительность, при условии поддержания у них на складах расчетного запаса.

Для поддержания расчетного запаса, нам потребуется обновлять раз в неделю или две (мы выше считали что две) примерно пол-ассортимента для следования за тенденциями и проч. Значит, надо к каждому юниту подвоз и вывоз 4000 книг каждые две недели. При каждом завозе и вывозе, эти самые 4000 книг должны быть извлечены из хранилища и потом положены туда другие. При 400 книг в час, обновление ассортимента будет занимать 10 часов под максимальной нагрузкой. Что, вроде бы, всё еще не так плохо, опять же, при массовой загрузке многие вещи будут проходить быстрее, тем не менее, поддержание ассортимента занимает в 5 раз больше, чем работа с населением.

Средняя книга (2см*20см*30см) это примерно 1.5л, то есть 4000 книг = 6 кубометров. Легко влезет в одну газель. Вес кубометра бумаги 600кг, то есть 6 кубометров это 3.6 тонны. Грузоподъемность газели полторы тонны, так что потребуется три газели. Плюс одна резервная. У нас 15 юнитов, обновление раз в 2 недели, при равномерном распределении мы на пределе, придётся добавить еще газельку.

И это мы не успели продумать, куда и откуда эти газельки возят, так что на схеме появляются склады поставщиков и точки выгрузки потерявших актуальность книг…

Итак, время вышло. Что же такого ненормального в NALSD вопросе? Масштабируемость она обязана быть в любом Large System Design. Главное же — конкретность.

Выше я делал много предположений и допущений, но все последующие оценки базировались на предыдущих. Для чисел я еще постарался привести “как оценить правильно”, впрочем, это очень легко забыть сделать, устаёшь и забываешь. Еще очень легко залипнуть с какой-то цифрой из памяти, без объяснения… Но так как дизайн конкретный, если какое-то из допущений окажется ошибочным, его можно исправить и просто пересчитать последующие.

Как сейчас помню, на своём интервью при прикидках взял IOPS диска в 600, просто потому, что недавно оптимизировал и маялся с одним массивом, где _массив_ выдавал 600 IOPS… Собеседующий слегка удивлённо спросил меня тогда — 600 IOPS на диск? :D

Во время интервью любое из ваших допущений собеседующий может поправить. Или добавить какое-либо ограничение (о котором вы не знали, не подумали, не спросили, или просто обычное изменение ТЗ на лету). При этом, так как вы оперируете исключительно конкретными цифрами, это будет просто тривиальным обновлением чисел.

Если же корректировка допущения вызывает редизайн системы — это уже либо ошибка проектирования, либо же неверная корректировка, либо выход за пределы применимости системы, что тоже не редкая ситуация в реальной жизни. Важно не пропускать такие моменты, и оценивать полученные цифры на реальность как в процессе стадии дизайна, так и при любых корректировках.

Как SRE мы обязаны думать в терминах масштабирования реальных систем в условиях реальных ограничений реального железа. Вполне может существовать прекрасный алгоритм, разменивающий огромные временные затраты на небольшое количество памяти… Но всё равно петабайт оперативки на одно процессорное ядро пока еще не поставишь в реальных условиях. Так что если у нас есть петабайт оперативки, то у нас тысяч десять процессоров как минимум. Или двадцать. Или тридцать. И надо искать оптимум не глобальный, а здесь и сейчас, в данных условиях.

Вам не надо помнить точные цифры, но обязательно иметь некое представление о порядке: те же IOPSы, которых у HDD порядка сотни, а у SSD сотня тысяч. Но достаются эти сотни тысяч вместе с соотношением стоимости терабайта HDD к стоимости терабайта у SSD как один к трем-четырем. И это еще не считая обвязку — место в стойке, блейды под них, порты на свичах и прочие вещи, которые перестают быть копейками когда счет идет на петабайты.

А теперь немного откиньтесь в своём кресле, расслабьтесь, и попытайтесь сконструировать систему поставки свежих куриных яиц по подписке.

Если есть желание поделиться с англоязычными коллегами, есть вариант на английском.

Автор: Anton Fedorov

Источник

* - обязательные к заполнению поля