Тут задача минут на 30 максимум, просто кандидат рассуждая, очень часто идет по неверному пути или придумывает избыточные сценарии. Во-первых, долго пытался вогнать учет юзеров в контур системы, хотя там user_id максимум нужен только на post для аналитики. Во-вторых, не услышал, что с дублями long url. В-третьих, было требование в возможности создания "осмысленных" short url,например, для рекламных кампаний, а это круто может поменять систему. В-четвертых, в комментах уже сказали по поводу запросов: 10ярдов на чтение в месяц ОХ как неравномерно будет распределено. Они вполне реально могут приходить все только по пятницам с 4х до 6ти вечера и будет весело смотреть как они упрутся в канал в 1мб/с и в rate limit (хотя до него тупо не дойдет). Кандидат видно, что знает технологии и какие-то паттерны и больше похоже,что это хочет показать, а не решить задачу. Удивительно, что кафку с оркестрацией не захотел вкорячить. В любом случае, спасибо за интервью: почти помогло избавиться от синдрома самозванца.
Что если упадет хранилище заготовленных ссылок 200кк ? Если это inMemory хранилище, то при рестарте оно восполнится снова этими же заготовками или же будут новые заготовки ? 🤔
Основное это кандидат волнуется и торопится. Без API переходит к шардированию. Хотя говорит что SQL DB тут норм справляется. Дальше появляется кэш. Архитектура усложняется на глазах, но не звучит обоснований. Дальше distributed locks появляются, кандидат закопался в знакомых терминах.
для начала надо было выбрать архитектуру и ее обосновать. без этого путь от баз к редису выглядит попыткой заткнуть дыры выбранной архитектуры (shared database)
Любопытно узнать, как можно достигнуть времени ответа на запрос в 1мс, если на такие короткие тайминги может оказать огромное влияние протокол передачи данных и сетевая загрузка
Во-первых это абстрактная задача, во-вторых обычно идет речь о том, что твой сервис (код) выполняет работу за 1 мс. Понятно, что латенси из-за всего интернета выше.
Сколько смотрю собесы по сисдизу, еще ни один человек в тайминг 50 минут не уложился, даже если мок-интервью внутри одной компании. И по rps постоянно невнятки. Кто говорит DAU, кто DAU/86400. Мало кто задает вопрос про распределение внутри дня. Я так и не понял, как правильно.
Я бы не смог продолжать серьёзную беседу после фразы: "опыт на кончиках пальцев" 🤣 Понимаю, что это про идиому "at your fingertips", но это характеризует гарантированную доступность чего-то, а не про практический опыт. К тому же, это уже лет 10 не buzzword.
Если честно, то не совсем понятно, чем так плоха хэш функция для обеспечения уникальности ссылки в шардах. Допустим у нас N шардов, и есть хэш функция, которая на любую шорт ссылку возвращает число от 0 до N - 1, т.о. определяя индекс шарда. На POST запросе мы рандомно генерим ссылку, считаем от нее хэш. Идем в нужный шард и проверяем занята ли ссылка. Кажется, что при такой длине шорт ссылки (8 символов) вероятность коллизий крайне мала (62^8 возможных вариантов). Если все же сгенерили случайно уже используемую ссылку, штош, придется еще раз сгенерить, пока не сгенерим свободную. Таким видится алгоритм. Возможно я что-то упускаю или неправильно понял проблему.
вообще правильно, но я как понял замечание интервьювера. у тебя есть хеш функция, которая распределяет равномерно множество А на Б, а ты по сути берешь подмножество А и отображаешь на Б и затем еще обрезаешь (берешь префикс), то есть отображаешь на подмножество Б. В этом случае хеш функция может не гарантировать равномерности распределения, то есть потенциально есть шанс напороться на более частые коллизии, чем прописано в самой хеш функции. Ну вот решение мужика мне не очень тоже понравилось, он просто сказал что будет отдельный сервис с технологией, но как конкретно все там будет крутиться и считаться не объяснил
@@artemkashipov9865 да, я согласен, что интервьюер на это правильно указал. просто я не совсем понял, почему идею с хэшем так сразу отбросили в пользу куда более сложного и менее надежного решения. но наверное, легко об этом говорить, когда интервьюируют не тебя)
@@artemkashipov9865 в предложенной системе производительность записи ссылок рискует упереться в узкое горлышко - в ожидания сервисов POST снятий блокировки в сервисе генерации ссылок
Хороший кандидат , что вы докопались . Надо понимать сперва на что эти собеседования нацелены, и ух-ты ух-ты первое это понять как человек думает , что знает и как строит гипотезы и их защищает или отвергает. И уже в далеко Не первую очередь это прототип абсолютно рабочей и униыерсальной системы... А то тут я смотрю умников собралось вагон и маленькая тележка.
Мне кажется, в БД с прегенерёнными ссылками можно сделать проще - просто отдавать ссылку по запросу и сразу её забывать. Если не пригодилась, ничего страшного, это же пул ссылок
@@afterglow392 прегенерированные ссылки могут быть сохранены в очереди с высокой доступностью; воркер генерирует ссылку и перед добавлением ее в очередь проводится проверка наличия дубликата в базе данных; следующий алгоритм будет таков: инстанс берет следующую следующее сообщение из очереди типа AWS SQS, извлекает ссылки из соощения, отмечает сообщение в очереди как обработанное и записывает в базу данных ассоциацию между короткой и длинной ссылкой; при таком подходе коллизии записи исключены. таким образом это решает проблему записи, а аналитика и чтение - это другие аспекты. можно пойти дальше и в момент герации ссылки позволить вокреру рассчитывать партишен, для которого предназначена данная ссылка. Но это уже другая история со своими бенефитами и проблемами.
@@yauhenibut-husaim5822Прикольное решение. А как воркер будет определять, с какой скоростью ему надо продьюсить ссылки? Что если будет всплеск нагрузки и очередь опустеет?
Systems Integration Engineer - системный инженер по интеграции. Это специалист, занимающийся проектированием, разработкой и управлением сложными системами. По сути сеньор бэкендер обладает функциями такого вот отдельного инженера)
В вашем варианте словарь хороший и коллизий в принципе нет если генерировать ключ последовательно. Речь шла о другом. Что если взять какой-нибудь алгоритм хеширования, например MD5, то у него длина 32 символа, а сами символы это всего лишь шестнадцатиричная система: 0-9A-F. Так как наша задача сделать короткую ссылку, то если мы от md5 отрежим 8 символов, то будет очень высокая вероятность коллизии. Ну и в интервью я подталкивал Сашу на то что 8 символов это очень большое число уникальных значений и ключ можно сократить до 6 или 7 символов.
@@oo_ilinКажется для того, чтобы ответить на этот вопрос, стоило понять какие конкретно символы у нас есть (алфавит), допустим если алфавит 72 (26 uppercase/lowercase, 10 цифр и 10 спец символов), то нам нужно как раз таки 6 символов (log72(10^10), 10^10 - потому что у меня получилось 12 * 10^9 ссылок за 10 лет, что примерно равно 10^10). Ну и блочный CRC как раз таки идеально подходит под эту задачу. Вообще задача хоть и тривиальная на первый взгляд, но может проверить глубокие знания и даже умение считать
На что влияет расчет хранилища здесь? Ок, 4 ТБ всего, для Postgres это вообще не проблема где по сути безлимитные таблицы. Зачем шарды? Если делать шарды то зачем страдать на SQL БД?
@@iteospace скорее нет, для HA можно реплики использовать. Шардировние требуется для распределения нагрузки при условии что вы уперлись вертикально. 4 ТБ вертикально это вообще копейки. Надо показывать что условная Постгря упрется по памяти/CPU/сети, а иначе шарды вам не нужны особо. И при шардировании проще тогда Монгу какую-нибудь взять, что чаще всего и является решением в TinyURL.
@@iteospace и собственно Монга это терабайты данных еще до шардов, т.е. с шардами можно в принципе забыть про ограничение на обьем данных, это бесполезный расчет, нужен скорее для FinOps/бюджетирования.
@@iteospaceвсе три являются NoSQL и масштабируются. Как бы вы сами выбирали? Я бы добавил ScyllaDB чтобы просто уже в космос перфоманс отправить. И еще можно смело выпилить кэш за апп-серверами, ничего не дает с учетом что современные БД идут со своими мэмкэшами.
Почему тут не модет быть проблема селебрити? Кто-то популярный создал ссылку и разметил ее у себя в соц. сетях, на эту одну ссылку будет очень много запросов на чтение. Кажеться интервьюируемый правильно задал вопрос.
Потому что проблема селебрити в том что один человек может иметь много связей. Например много подписчиков и проблема оповестить всех о выходе нового поста. Тут ты делаешь ровно один адрес и никого не уведомляешь. Тут проблема высокого трафика, а это уже другая история.
@@oo_ilin я не соглашусь тут. если ссылка была создана под очень популярного человека на рекламу. он выставляет эту ссылку и все по ней начинают ходить. потом также с другим человеком и так далее(эти ссылки случайно попали в один шард). получается может быть такая ситуация, что все будут очень мощно долбить лишь один шард. шардирование не помогло получается, плохо) но я думаю тут благодаря кешированию будет все ок
хотелось бы увидеть поподробнее как ссылка выбирается и как по ней определяется в какую шарду мы идем, вопрос распределения равномерного опять же и про аналитику, можно было проговорить, что данные там тоже устаревают и допустим ссылка созданная такая 15 лет назад и 7 лет назад это две разные? и надо по итогу записывать еще время создания туда, этой ссылки, чтобы можно было уже агрегировать в дальнейшем для анализа но мужик конечно круто отвечал, очень приятно говорит в целом, не зря в токио сидит)
мужик не круто отвечал. Шардировать по первому символу короткой ссылки. 4 шарда, символов 26+26+10=62 символа. Делим 62 на 4, получаем первые 16 символов, отсортированных по таблице ASCII в первый шард, вторые 16 во второй и т.п. А мужик просто повторяет за интервьюером
а вообще, система сферический конь в вакууме, как будто у нас с момента создания этого сервиса нагрузка сразу на 100%. Для начала вообще можно бы было все сильно упростить, а уже потом с ростом нагрузки заниматься оптимизацией. Вдруг вообще наш сокращатель никому нафиг не нужен будет, а мы тут всю инфраструктуру подняли, кучу бабла заплатили.
Consistent hashing по идее решает оба ваших вопроса. Шард выбирается по short_url, так мы сразу понимаем какой шарф для конкретной ссылки выбрать. Вопрос масштабирования при таком подходе довольно просто решается добавлением новых шардов и перелоцированием данных.
да так себе кандидат, слишком закопался в счет. что это за 6 байт на дату и 10 на ид? ох уж эти питонисты, куда им в хайлоад задача идеоматическая для таких собесрв, странно что он ее на изусть не знает
Тут задача минут на 30 максимум, просто кандидат рассуждая, очень часто идет по неверному пути или придумывает избыточные сценарии. Во-первых, долго пытался вогнать учет юзеров в контур системы, хотя там user_id максимум нужен только на post для аналитики. Во-вторых, не услышал, что с дублями long url. В-третьих, было требование в возможности создания "осмысленных" short url,например, для рекламных кампаний, а это круто может поменять систему. В-четвертых, в комментах уже сказали по поводу запросов: 10ярдов на чтение в месяц ОХ как неравномерно будет распределено. Они вполне реально могут приходить все только по пятницам с 4х до 6ти вечера и будет весело смотреть как они упрутся в канал в 1мб/с и в rate limit (хотя до него тупо не дойдет). Кандидат видно, что знает технологии и какие-то паттерны и больше похоже,что это хочет показать, а не решить задачу. Удивительно, что кафку с оркестрацией не захотел вкорячить. В любом случае, спасибо за интервью: почти помогло избавиться от синдрома самозванца.
Что если упадет хранилище заготовленных ссылок 200кк ?
Если это inMemory хранилище, то при рестарте оно восполнится снова этими же заготовками или же будут новые заготовки ? 🤔
Основное это кандидат волнуется и торопится. Без API переходит к шардированию. Хотя говорит что SQL DB тут норм справляется. Дальше появляется кэш. Архитектура усложняется на глазах, но не звучит обоснований. Дальше distributed locks появляются, кандидат закопался в знакомых терминах.
неверно же посчитал пропускную способность
40 wRps x 300 байт = 12,000 байт/сек = 0.094 Мбит/сек
для начала надо было выбрать архитектуру и ее обосновать. без этого путь от баз к редису выглядит попыткой заткнуть дыры выбранной архитектуры (shared database)
Любопытно узнать, как можно достигнуть времени ответа на запрос в 1мс, если на такие короткие тайминги может оказать огромное влияние протокол передачи данных и сетевая загрузка
Во-первых это абстрактная задача, во-вторых обычно идет речь о том, что твой сервис (код) выполняет работу за 1 мс. Понятно, что латенси из-за всего интернета выше.
Там в трейсинге учитывается только время ответа сервера, сетевые издержки не считаем
Сколько смотрю собесы по сисдизу, еще ни один человек в тайминг 50 минут не уложился, даже если мок-интервью внутри одной компании. И по rps постоянно невнятки. Кто говорит DAU, кто DAU/86400. Мало кто задает вопрос про распределение внутри дня. Я так и не понял, как правильно.
Я бы не смог продолжать серьёзную беседу после фразы: "опыт на кончиках пальцев" 🤣
Понимаю, что это про идиому "at your fingertips", но это характеризует гарантированную доступность чего-то, а не про практический опыт. К тому же, это уже лет 10 не buzzword.
playback x1.5 save your time :)
x2
Если честно, то не совсем понятно, чем так плоха хэш функция для обеспечения уникальности ссылки в шардах. Допустим у нас N шардов, и есть хэш функция, которая на любую шорт ссылку возвращает число от 0 до N - 1, т.о. определяя индекс шарда. На POST запросе мы рандомно генерим ссылку, считаем от нее хэш. Идем в нужный шард и проверяем занята ли ссылка. Кажется, что при такой длине шорт ссылки (8 символов) вероятность коллизий крайне мала (62^8 возможных вариантов). Если все же сгенерили случайно уже используемую ссылку, штош, придется еще раз сгенерить, пока не сгенерим свободную. Таким видится алгоритм. Возможно я что-то упускаю или неправильно понял проблему.
вообще правильно, но я как понял замечание интервьювера. у тебя есть хеш функция, которая распределяет равномерно множество А на Б, а ты по сути берешь подмножество А и отображаешь на Б и затем еще обрезаешь (берешь префикс), то есть отображаешь на подмножество Б. В этом случае хеш функция может не гарантировать равномерности распределения, то есть потенциально есть шанс напороться на более частые коллизии, чем прописано в самой хеш функции.
Ну вот решение мужика мне не очень тоже понравилось, он просто сказал что будет отдельный сервис с технологией, но как конкретно все там будет крутиться и считаться не объяснил
@@artemkashipov9865 да, я согласен, что интервьюер на это правильно указал. просто я не совсем понял, почему идею с хэшем так сразу отбросили в пользу куда более сложного и менее надежного решения. но наверное, легко об этом говорить, когда интервьюируют не тебя)
@@artemkashipov9865 в предложенной системе производительность записи ссылок рискует упереться в узкое горлышко - в ожидания сервисов POST снятий блокировки в сервисе генерации ссылок
Крутое интервью, много интересных моментов, мне кажется «кандидат» отлично справился
Хороший кандидат , что вы докопались .
Надо понимать сперва на что эти собеседования нацелены, и ух-ты ух-ты первое это понять как человек думает , что знает и как строит гипотезы и их защищает или отвергает. И уже в далеко Не первую очередь это прототип абсолютно рабочей и униыерсальной системы... А то тут я смотрю умников собралось вагон и маленькая тележка.
Очень крутой кандидат, кроме самого системного дизайна явно где то учился грамотно говорить и отвечать, действует как психолог -архитектор
Мне кажется, в БД с прегенерёнными ссылками можно сделать проще - просто отдавать ссылку по запросу и сразу её забывать. Если не пригодилась, ничего страшного, это же пул ссылок
тебе кажется, по условию ссылки нужно хранить 10 лет и записывать по ним статистику
@@afterglow392 прегенерированные ссылки могут быть сохранены в очереди с высокой доступностью; воркер генерирует ссылку и перед добавлением ее в очередь проводится проверка наличия дубликата в базе данных; следующий алгоритм будет таков: инстанс берет следующую следующее сообщение из очереди типа AWS SQS, извлекает ссылки из соощения, отмечает сообщение в очереди как обработанное и записывает в базу данных ассоциацию между короткой и длинной ссылкой; при таком подходе коллизии записи исключены.
таким образом это решает проблему записи, а аналитика и чтение - это другие аспекты.
можно пойти дальше и в момент герации ссылки позволить вокреру рассчитывать партишен, для которого предназначена данная ссылка. Но это уже другая история со своими бенефитами и проблемами.
@@yauhenibut-husaim5822Прикольное решение. А как воркер будет определять, с какой скоростью ему надо продьюсить ссылки? Что если будет всплеск нагрузки и очередь опустеет?
@@yauhenibut-husaim5822 А проще наверное использовать что-то такое en.wikipedia.org/wiki/Snowflake_ID
1:10 Что такое Эс Ай И (SIE)?
Скорее всего системный аналитик
Systems Integration Engineer - системный инженер по интеграции. Это специалист, занимающийся проектированием, разработкой и управлением сложными системами. По сути сеньор бэкендер обладает функциями такого вот отдельного инженера)
@@timur2887 а есть такой специальный чел? Архитектор что ль? Ну тогда чел очень слаб на эту позицию, жаль компанию где он работает
26 букв, + верхний регистр + числа в 8 символах это 62^8 возможных уникальных значений. разве вероятность коллизии высокая?
В вашем варианте словарь хороший и коллизий в принципе нет если генерировать ключ последовательно. Речь шла о другом. Что если взять какой-нибудь алгоритм хеширования, например MD5, то у него длина 32 символа, а сами символы это всего лишь шестнадцатиричная система: 0-9A-F. Так как наша задача сделать короткую ссылку, то если мы от md5 отрежим 8 символов, то будет очень высокая вероятность коллизии. Ну и в интервью я подталкивал Сашу на то что 8 символов это очень большое число уникальных значений и ключ можно сократить до 6 или 7 символов.
@@oo_ilinКажется для того, чтобы ответить на этот вопрос, стоило понять какие конкретно символы у нас есть (алфавит), допустим если алфавит 72 (26 uppercase/lowercase, 10 цифр и 10 спец символов), то нам нужно как раз таки 6 символов (log72(10^10), 10^10 - потому что у меня получилось 12 * 10^9 ссылок за 10 лет, что примерно равно 10^10). Ну и блочный CRC как раз таки идеально подходит под эту задачу. Вообще задача хоть и тривиальная на первый взгляд, но может проверить глубокие знания и даже умение считать
@@oo_ilin в данном случае MD5 можно перегнать в Base64 и отрезать 8 символов уже от него. Коллизия будет ничтожной
@@suhanoves с чего вы взяли, что будет ничтожной?)))
На что влияет расчет хранилища здесь? Ок, 4 ТБ всего, для Postgres это вообще не проблема где по сути безлимитные таблицы. Зачем шарды? Если делать шарды то зачем страдать на SQL БД?
Высокая доступность
@@iteospace скорее нет, для HA можно реплики использовать. Шардировние требуется для распределения нагрузки при условии что вы уперлись вертикально. 4 ТБ вертикально это вообще копейки. Надо показывать что условная Постгря упрется по памяти/CPU/сети, а иначе шарды вам не нужны особо. И при шардировании проще тогда Монгу какую-нибудь взять, что чаще всего и является решением в TinyURL.
@@iteospace и собственно Монга это терабайты данных еще до шардов, т.е. с шардами можно в принципе забыть про ограничение на обьем данных, это бесполезный расчет, нужен скорее для FinOps/бюджетирования.
@@dragvs почему бы просто не взять распределеную NoSql\New Sql типа Apache Cassandra\CocroachDb
@@iteospaceвсе три являются NoSQL и масштабируются. Как бы вы сами выбирали? Я бы добавил ScyllaDB чтобы просто уже в космос перфоманс отправить. И еще можно смело выпилить кэш за апп-серверами, ничего не дает с учетом что современные БД идут со своими мэмкэшами.
А в чем вы схемки рисуете?
Excalidraw
Почему тут не модет быть проблема селебрити? Кто-то популярный создал ссылку и разметил ее у себя в соц. сетях, на эту одну ссылку будет очень много запросов на чтение. Кажеться интервьюируемый правильно задал вопрос.
Потому что проблема селебрити в том что один человек может иметь много связей. Например много подписчиков и проблема оповестить всех о выходе нового поста. Тут ты делаешь ровно один адрес и никого не уведомляешь. Тут проблема высокого трафика, а это уже другая история.
@@oo_ilin я не соглашусь тут. если ссылка была создана под очень популярного человека на рекламу. он выставляет эту ссылку и все по ней начинают ходить. потом также с другим человеком и так далее(эти ссылки случайно попали в один шард). получается может быть такая ситуация, что все будут очень мощно долбить лишь один шард. шардирование не помогло получается, плохо)
но я думаю тут благодаря кешированию будет все ок
44:00 херня какая то... Без предметной области и понятной нагрузки - можно долго тыкать пальцем в небо... !
Я фронтендер и, стало быть, в систем дизайне понимаю больше))
хотелось бы увидеть поподробнее как ссылка выбирается и как по ней определяется в какую шарду мы идем, вопрос распределения равномерного опять же
и про аналитику, можно было проговорить, что данные там тоже устаревают и допустим ссылка созданная такая 15 лет назад и 7 лет назад это две разные? и надо по итогу записывать еще время создания туда, этой ссылки, чтобы можно было уже агрегировать в дальнейшем для анализа
но мужик конечно круто отвечал, очень приятно говорит в целом, не зря в токио сидит)
мужик не круто отвечал. Шардировать по первому символу короткой ссылки. 4 шарда, символов 26+26+10=62 символа. Делим 62 на 4, получаем первые 16 символов, отсортированных по таблице ASCII в первый шард, вторые 16 во второй и т.п. А мужик просто повторяет за интервьюером
теоретически, т.к. ссылка будет генериться рандомно, распределяться по первому символу ссылки будут по шардам равномерно.
а вообще, система сферический конь в вакууме, как будто у нас с момента создания этого сервиса нагрузка сразу на 100%. Для начала вообще можно бы было все сильно упростить, а уже потом с ростом нагрузки заниматься оптимизацией. Вдруг вообще наш сокращатель никому нафиг не нужен будет, а мы тут всю инфраструктуру подняли, кучу бабла заплатили.
Consistent hashing по идее решает оба ваших вопроса. Шард выбирается по short_url, так мы сразу понимаем какой шарф для конкретной ссылки выбрать. Вопрос масштабирования при таком подходе довольно просто решается добавлением новых шардов и перелоцированием данных.
@@insanebeaver3060 в изначальной задаче такой проблемы не ставилось. Так-то можно и рандеву хеширование сделать
чел, айдишник тебе зачем? чо за конвульсии, хеш, не хеш, прегенеренные ссылки, лок, сук, еще джойнов добавь😂
а кто будет прогревать датацентры долгими зимами? только вот такие распределенные системы генерации ссылок чуть покороче, чем были)
По мне слабоват кандидат.
да так себе кандидат, слишком закопался в счет. что это за 6 байт на дату и 10 на ид? ох уж эти питонисты, куда им в хайлоад
задача идеоматическая для таких собесрв, странно что он ее на изусть не знает
он ещё и в фаанг собрался, хотя может там сейчас таких берут на ура...