Mock-собеседование по System Design от Team Lead из Ozon

[@Magomedrasul7]

Что если упадет хранилище заготовленных ссылок 200кк ? Если это inMemory хранилище, то при рестарте оно восполнится снова этими же заготовками или же будут новые заготовки ? 🤔

[@alekseyeject940]

Тут задача минут на 30 максимум, просто кандидат рассуждая, очень часто идет по неверному пути или придумывает избыточные сценарии. Во-первых, долго пытался вогнать учет юзеров в контур системы, хотя там user_id максимум нужен только на post для аналитики. Во-вторых, не услышал, что с дублями long url. В-третьих, было требование в возможности создания "осмысленных" short url,например, для рекламных кампаний, а это круто может поменять систему. В-четвертых, в комментах уже сказали по поводу запросов: 10ярдов на чтение в месяц ОХ как неравномерно будет распределено. Они вполне реально могут приходить все только по пятницам с 4х до 6ти вечера и будет весело смотреть как они упрутся в канал в 1мб/с и в rate limit (хотя до него тупо не дойдет). Кандидат видно, что знает технологии и какие-то паттерны и больше похоже,что это хочет показать, а не решить задачу. Удивительно, что кафку с оркестрацией не захотел вкорячить. В любом случае, спасибо за интервью: почти помогло избавиться от синдрома самозванца.

[@dmitryzolotarev1532]

Сколько смотрю собесы по сисдизу, еще ни один человек в тайминг 50 минут не уложился, даже если мок-интервью внутри одной компании. И по rps постоянно невнятки. Кто говорит DAU, кто DAU/86400. Мало кто задает вопрос про распределение внутри дня. Я так и не понял, как правильно.

[@covrom]

для начала надо было выбрать архитектуру и ее обосновать. без этого путь от баз к редису выглядит попыткой заткнуть дыры выбранной архитектуры (shared database)

[@НиколайБондаренко-е5я]

Если абстрагироваться от необходимости шардирования. В качестве ключа для шарда может быть первый символ короткой ссылки? Или 62 шарда это много?

[@НиколайБондаренко-е5я]

Ну или верхний регистр + нижний регистр одной буквы в шарде 26 шардов + все цифры допустим еще + 10

[@oo_ilin]

@@НиколайБондаренко-е5я в данной задаче кажется избыточно иметь 62 шарда, но опять же если бы это был сервис гугла и он сокращал ссылки для их ресурсов где бешенная посещаемость, то почему бы и нет. Но именно по символу не оочень хорошая идея, так как ссылку можно переименовать и тогда придется её перевозить, а это не очень

[@timur2887]

Любопытно узнать, как можно достигнуть времени ответа на запрос в 1мс, если на такие короткие тайминги может оказать огромное влияние протокол передачи данных и сетевая загрузка

[@textyre]

Во-первых это абстрактная задача, во-вторых обычно идет речь о том, что твой сервис (код) выполняет работу за 1 мс. Понятно, что латенси из-за всего интернета выше.

[@cubgrad]

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

[@kozhurkin]

неверно же посчитал пропускную способность 40 wRps x 300 байт = 12,000 байт/сек = 0.094 Мбит/сек

[@dragvs]

Основное это кандидат волнуется и торопится. Без API переходит к шардированию. Хотя говорит что SQL DB тут норм справляется. Дальше появляется кэш. Архитектура усложняется на глазах, но не звучит обоснований. Дальше distributed locks появляются, кандидат закопался в знакомых терминах.

[@feolius]

Если честно, то не совсем понятно, чем так плоха хэш функция для обеспечения уникальности ссылки в шардах. Допустим у нас N шардов, и есть хэш функция, которая на любую шорт ссылку возвращает число от 0 до N - 1, т.о. определяя индекс шарда. На POST запросе мы рандомно генерим ссылку, считаем от нее хэш. Идем в нужный шард и проверяем занята ли ссылка. Кажется, что при такой длине шорт ссылки (8 символов) вероятность коллизий крайне мала (62^8 возможных вариантов). Если все же сгенерили случайно уже используемую ссылку, штош, придется еще раз сгенерить, пока не сгенерим свободную. Таким видится алгоритм. Возможно я что-то упускаю или неправильно понял проблему.

[@artemkashipov9865]

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

[@feolius]

@@artemkashipov9865 да, я согласен, что интервьюер на это правильно указал. просто я не совсем понял, почему идею с хэшем так сразу отбросили в пользу куда более сложного и менее надежного решения. но наверное, легко об этом говорить, когда интервьюируют не тебя)

[@timur2887]

​@@artemkashipov9865 в предложенной системе производительность записи ссылок рискует упереться в узкое горлышко - в ожидания сервисов POST снятий блокировки в сервисе генерации ссылок

[@wsxpocxeafx]

1:10 Что такое Эс Ай И (SIE)?

[@ДинарГарипов-ж3о]

Скорее всего системный аналитик

[@timur2887]

Systems Integration Engineer - системный инженер по интеграции. Это специалист, занимающийся проектированием, разработкой и управлением сложными системами. По сути сеньор бэкендер обладает функциями такого вот отдельного инженера)

[@pacifistrush680]

@@timur2887 а есть такой специальный чел? Архитектор что ль? Ну тогда чел очень слаб на эту позицию, жаль компанию где он работает

[@noone7796]

26 букв, + верхний регистр + числа в 8 символах это 62^8 возможных уникальных значений. разве вероятность коллизии высокая?

[@oo_ilin]

В вашем варианте словарь хороший и коллизий в принципе нет если генерировать ключ последовательно. Речь шла о другом. Что если взять какой-нибудь алгоритм хеширования, например MD5, то у него длина 32 символа, а сами символы это всего лишь шестнадцатиричная система: 0-9A-F. Так как наша задача сделать короткую ссылку, то если мы от md5 отрежим 8 символов, то будет очень высокая вероятность коллизии. Ну и в интервью я подталкивал Сашу на то что 8 символов это очень большое число уникальных значений и ключ можно сократить до 6 или 7 символов.

[@aleksandr_t]

@@oo_ilinКажется для того, чтобы ответить на этот вопрос, стоило понять какие конкретно символы у нас есть (алфавит), допустим если алфавит 72 (26 uppercase/lowercase, 10 цифр и 10 спец символов), то нам нужно как раз таки 6 символов (log72(10^10), 10^10 - потому что у меня получилось 12 * 10^9 ссылок за 10 лет, что примерно равно 10^10). Ну и блочный CRC как раз таки идеально подходит под эту задачу. Вообще задача хоть и тривиальная на первый взгляд, но может проверить глубокие знания и даже умение считать

[@suhanoves]

@@oo_ilin в данном случае MD5 можно перегнать в Base64 и отрезать 8 символов уже от него. Коллизия будет ничтожной

[@timur2887]

@@suhanoves с чего вы взяли, что будет ничтожной?)))

[@Nemesis-b4c]

Хороший кандидат , что вы докопались . Надо понимать сперва на что эти собеседования нацелены, и ух-ты ух-ты первое это понять как человек думает , что знает и как строит гипотезы и их защищает или отвергает. И уже в далеко Не первую очередь это прототип абсолютно рабочей и униыерсальной системы... А то тут я смотрю умников собралось вагон и маленькая тележка.

[@instl1117]

Крутое интервью, много интересных моментов, мне кажется «кандидат» отлично справился

[@dragvs]

На что влияет расчет хранилища здесь? Ок, 4 ТБ всего, для Postgres это вообще не проблема где по сути безлимитные таблицы. Зачем шарды? Если делать шарды то зачем страдать на SQL БД?

[@iteospace]

Высокая доступность

[@dragvs]

@@iteospace скорее нет, для HA можно реплики использовать. Шардировние требуется для распределения нагрузки при условии что вы уперлись вертикально. 4 ТБ вертикально это вообще копейки. Надо показывать что условная Постгря упрется по памяти/CPU/сети, а иначе шарды вам не нужны особо. И при шардировании проще тогда Монгу какую-нибудь взять, что чаще всего и является решением в TinyURL.

[@dragvs]

@@iteospace и собственно Монга это терабайты данных еще до шардов, т.е. с шардами можно в принципе забыть про ограничение на обьем данных, это бесполезный расчет, нужен скорее для FinOps/бюджетирования.

[@iteospace]

@@dragvs почему бы просто не взять распределеную NoSql\New Sql типа Apache Cassandra\CocroachDb

[@dragvs]

@@iteospaceвсе три являются NoSQL и масштабируются. Как бы вы сами выбирали? Я бы добавил ScyllaDB чтобы просто уже в космос перфоманс отправить. И еще можно смело выпилить кэш за апп-серверами, ничего не дает с учетом что современные БД идут со своими мэмкэшами.

[@ITV-ITV-]

Я бы не смог продолжать серьёзную беседу после фразы: "опыт на кончиках пальцев" 🤣 Понимаю, что это про идиому "at your fingertips", но это характеризует гарантированную доступность чего-то, а не про практический опыт. К тому же, это уже лет 10 не buzzword.

[@snow.dealer]

А в чем вы схемки рисуете?

[@ДмитрийБогданов-г4э]

Excalidraw

[@SergeiWPopov]

playback x1.5 save your time :)

[@ko22012]

x2

[@alterpub2]

X4

[@userresus]

Мне кажется, в БД с прегенерёнными ссылками можно сделать проще - просто отдавать ссылку по запросу и сразу её забывать. Если не пригодилась, ничего страшного, это же пул ссылок

[@afterglow392]

тебе кажется, по условию ссылки нужно хранить 10 лет и записывать по ним статистику

[@yauhenibut-husaim5822]

@@afterglow392 прегенерированные ссылки могут быть сохранены в очереди с высокой доступностью; воркер генерирует ссылку и перед добавлением ее в очередь проводится проверка наличия дубликата в базе данных; следующий алгоритм будет таков: инстанс берет следующую следующее сообщение из очереди типа AWS SQS, извлекает ссылки из соощения, отмечает сообщение в очереди как обработанное и записывает в базу данных ассоциацию между короткой и длинной ссылкой; при таком подходе коллизии записи исключены. таким образом это решает проблему записи, а аналитика и чтение - это другие аспекты. можно пойти дальше и в момент герации ссылки позволить вокреру рассчитывать партишен, для которого предназначена данная ссылка. Но это уже другая история со своими бенефитами и проблемами.

[@qwerty2536]

@@yauhenibut-husaim5822Прикольное решение. А как воркер будет определять, с какой скоростью ему надо продьюсить ссылки? Что если будет всплеск нагрузки и очередь опустеет?

[@qwerty2536]

@@yauhenibut-husaim5822 А проще наверное использовать что-то такое en.wikipedia.org/wiki/Snowflake_ID

[@IQ-120]

44:00 херня какая то... Без предметной области и понятной нагрузки - можно долго тыкать пальцем в небо... !

[@oo_ilin]

согласен сисдиз секция не предназначена для реального проектирования.Такие системы проектируют неделями, а то и месяцами что бы они были production ready. Но за то можно показать свой кругозор и продать себя как специалиста

[@IQ-120]

@oo_ilin вчера узнал, что Пушкин был двоечником :) и настоятельно рекомендую посмотреть фильм, старенький - путеводитель по галактике!

[@oo_ilin]

@@IQ-120 Действительно, в свидетельстве об окончании Царскосельского лицея у Пушкина есть двойки и даже колы и нули! Но во времена учебы великого поэта эти оценки соответствовали другим характеристикам: 2 - «хорошо», 1 - «весьма хорошо». А вот 0 означал «превосходно» - такую оценку Пушкин имел по Российской и Французской словесности, а также по фехтованию.

[@IQ-120]

@@oo_ilin ну, круто же :)

[@IQ-120]

@@oo_ilin Ухты, титул звонкий! Не думал, что с поднебесной - челяди кто то отвечать будет... :)

[@leonkonig5131]

Очень крутой кандидат, кроме самого системного дизайна явно где то учился грамотно говорить и отвечать, действует как психолог -архитектор

[@artemkashipov9865]

хотелось бы увидеть поподробнее как ссылка выбирается и как по ней определяется в какую шарду мы идем, вопрос распределения равномерного опять же и про аналитику, можно было проговорить, что данные там тоже устаревают и допустим ссылка созданная такая 15 лет назад и 7 лет назад это две разные? и надо по итогу записывать еще время создания туда, этой ссылки, чтобы можно было уже агрегировать в дальнейшем для анализа но мужик конечно круто отвечал, очень приятно говорит в целом, не зря в токио сидит)

[@dirty0dozen]

мужик не круто отвечал. Шардировать по первому символу короткой ссылки. 4 шарда, символов 26+26+10=62 символа. Делим 62 на 4, получаем первые 16 символов, отсортированных по таблице ASCII в первый шард, вторые 16 во второй и т.п. А мужик просто повторяет за интервьюером

[@dirty0dozen]

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

[@dirty0dozen]

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

[@insanebeaver3060]

Consistent hashing по идее решает оба ваших вопроса. Шард выбирается по short_url, так мы сразу понимаем какой шарф для конкретной ссылки выбрать. Вопрос масштабирования при таком подходе довольно просто решается добавлением новых шардов и перелоцированием данных.

[@dirty0dozen]

@@insanebeaver3060 в изначальной задаче такой проблемы не ставилось. Так-то можно и рандеву хеширование сделать

[@noone7796]

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

[@oo_ilin]

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

[@artemkashipov9865]

​@@oo_ilin я не соглашусь тут. если ссылка была создана под очень популярного человека на рекламу. он выставляет эту ссылку и все по ней начинают ходить. потом также с другим человеком и так далее(эти ссылки случайно попали в один шард). получается может быть такая ситуация, что все будут очень мощно долбить лишь один шард. шардирование не помогло получается, плохо) но я думаю тут благодаря кешированию будет все ок

[@sergeyz4591]

Я фронтендер и, стало быть, в систем дизайне понимаю больше))

[@tertiumorganum5665]

чел, айдишник тебе зачем? чо за конвульсии, хеш, не хеш, прегенеренные ссылки, лок, сук, еще джойнов добавь😂

[@timur2887]

а кто будет прогревать датацентры долгими зимами? только вот такие распределенные системы генерации ссылок чуть покороче, чем были)

[@darkreaper8798]

По мне слабоват кандидат.

[@tertiumorganum5665]

да так себе кандидат, слишком закопался в счет. что это за 6 байт на дату и 10 на ид? ох уж эти питонисты, куда им в хайлоад задача идеоматическая для таких собесрв, странно что он ее на изусть не знает

[@4cast2]

он ещё и в фаанг собрался, хотя может там сейчас таких берут на ура...