0: Всем привет. Сегодня прохожу 3 заключительное интервью в яндекс системный дизайн или по другому, архитектурная секция для разных вакансий. Это интервью может идти разным по счёту, например, для java разработчика оно идёт 2, а для меня, как для датасаентиста 3, но это не отменяет того факта, что
1: Эта секция общая для всех, и проходить её нужно будет всем. По традиции выражаю благодарность собеседующему за это прекрасное интервью. Не подавайте на меня в суд, пожалуйста. Также скоро на этом канале наберётся 1000 подписчиков или уже набралась? А значит, скоро выйдет видео с интересным анон.
2: Не пропусти, также очень скоро я буду переезжать, поэтому частота выхода роликов может немного нарушиться. Вот, но вы терпите. Давайте теперь перейдём к собеседованию, посмотрим, что же нам приготовил яндекс папарапам. Итак, задача у нас
3: Будет следующее. Нам нужно разработать приложение для поиска 100 ближайших заведений к текущей точке. То есть мы открываем приложение, нажимаем большую кнопку. У нас есть координаты, наши координаты. Вот. И приложение показывает 100 ближайших заведений к нашей координате вроде
4: Задача выглядит простой, тем более ничего программировать не надо. Поэтому сначала я даже не понял, что мне нужно сделать, и долго тупил. Тут наверняка мы должны получить список сначала вообще всех заведений, которые есть. И поэтому мы можем использовать какие-нибудь яндекс карты, например, да, давай не говорить там, условно, яндекс карт.
5: И давай представим, что в нашей системе, да, как-то, каким-то образом завиты заведения с координатами. Ну то есть координаты заведения мы знаем, давайте послушаем заново, что именно от меня хотят, чтобы я это смог нарисовать. Ну вот, ну, в общем, наша цель спроектировать, как бы ты проектировал такой, ну, такую бэкэнд систему, ну, то есть,
6: Рисовать там условно, что есть какие-то там сервера, что они отвечают на запросы там, что есть какие-то там, условно, базы данных и так далее, и так далее. Описать, кто как, с кем работает, вот, и так далее, и так далее. Наверняка нам нужно сначала завести какую-то базу данных, где будут лежать координаты всех.
7: Заведений, которые вообще есть. Я предложил для этого использовать Эскель, а именно посгрес, ну, и попытался что-то нарисовать. Почему постгрис? Ну, в смысле, почему, Эскель, решение хочется, да, больше конкретики. Ну, наверное, потому что я ничего другого не знаю, моя картинка его не убедила, и он попросил
8: Что-то более конкретное. Ну вот представь, что ты делаешь задачу. Тебе же явно этого не будет хватать для того, чтобы сесть и начать там, например, писать код или давать задачи другим. Пример. Собственно, как сам поиск будет происходить, что мы там будем делать всякие в случае всяких отказов нашей системы
9: Тут я предложил заменить эскьюэль базу данных на spark a spark, как работает, и сразу передумал это делать, а может, мы можем просто загрузить все наши точки в датафрейм пандаса и посчитать векторное расстояние до них ну а вот какой критерий, что можем ли мы, например, в питоне?
10: Или не можем, сразу скажу, что про объём данных ты в том числе можешь спросить, вот объём данных у нас будет 100 100000000 заведений, да, у нас вряд ли получится хранить такой большой объём данных в оперативной памяти. А может, мы можем поднять хадуп и через мапредьюс просто считать расстояние мапредьюс это не про там.
11: Все-таки, ну то есть вот у тебя в рантайме приходит запрос, ты же не будешь там пользователя заставлять ждать, пока там наберётся бач, значит нам нужно что-то, куда мы сможем отправлять запрос и быстро получать 100 ближайших точек. Ах, да, забыл, это ведь и есть наша задача. На, давай просто подумаем.
12: Про такую структуру данных, которая бы, ну, там, без использования, там, возможно, там, спарка и так далее. Тут я не совсем понял, что он имеет ввиду, ведь других систем для хранения данных я не знаю, но намекал не на то, где мы будем хранить наши точки. А как мы их будем получать? Ну, давай задачу попроще.
13: Если у нас много точек на плоскости, как нам найти? Ну, у нас есть какой-нибудь, например, квадрат, вот как найти точки, которые входят в этот квадрат. Самое простое, что мы можем сделать, это пройтись циклом по нашим точкам, посчитать расстояние и найти 100 ближайших, да, за сколько это будет работать? Ну, блин, всего 100000000.
14: Может быть пользователи смогут подождать. Думаю, правильнее было бы выделить какие-то кластеры, кандидаты на поиск и искать только в них, а не по всем точкам, какую можно было бы вообще самую тупую кластеризацию такую сделать. Я скорее не про кластеризацию в терминах Эмеля, а вот кластеризацию в терминах прост.
15: Тупого алгоритма, где есть плоскость и квадраты. Например, можно разбить плоскость на сетку. Тогда каждая точка будет относиться к какому-то 1 квадрату. А если у нас такая сетка, если квадратиков даже после сетки стало, было все ещё слишком много, тогда можно сделать такую иерархию.
16: Объединив маленькие квадраты в квадраты побольше, их квадраты ещё больше и так далее, пока у нас не получится 1 большой квадрат. Кстати, я видел что-то похожее на бумажных картах. Так вот, что же все-таки нужно делать дальше? Допустим, у нас есть какая-то область, и мы хотим найти все точки, которые входят в
17: Эту область, используя вот эту нашу иерархическую систему квадратов, делаем мы это так, берём самый большой квадрат и смотрим, какие квадраты в нём пересекаются с нашей областью. Те, которые пересекаются, мы оставляем, которые не пересекаются, выкидываем и для каждого из эти
18: Квадратов, которые пересекаются. Мы повторяем этот процесс, то есть смотрим в них квадраты меньше, которые пересекаются и так далее. Так, итерация. За итерацией мы спустимся до самого нижнего уровня, где лежат наши точки. Так, мы найдём все точки, которые лежат в нашей области.
19: Ну, с какой-то небольшой аппроксимацией квадратами, за сколько такой поиск будет работать, поскольку с каждой итерацией область поиска уменьшается кратно, время будет логарифмическим. Ну, если точки, да, равномерно распределены, то получается логарифмическое, фуух, может быть этого
20: Достаточно для решения? Нет. Вот. Окей, да, теперь вот придумали структуру данных. Она, кстати, называется Куат 3. Попробуйте погуглить, может быть, что-то найдёте. Я ничего не смог найти. Ну и ладно, которая умеет за логарифмическое время решать такую задачу. Давай подумаем, можно ли
21: Нам как-то её использовать, blink. Разве это ещё не все? А, ну да, нам ведь нужно найти 100 ближайших заведений к нашей точке, а не просто точки, которые лежат в какой-то области. Смотри, у нас есть множество точек, вот и мы как-то там научи, построили структуру данных, состоящую
22: Квадратов, который позволяет как-то там быстро искать что-то вот это, это наша структура данных. А дальше у нас в этой структуре данных можно, кажется, сделать запросы, какие точки входят в квадрат икс. Вот квадрат x может быть, кажется произвольным. Ага, тогда ведь можно взять, например, круг радиус.
23: Там 100 метров и найти все квадраты нижнего уровня, которые с ним пересекаются. Тогда все точки, лежащие в этом, в этих квадратах, и будут кандидатами на поиск. Их будет немного. Поэтому мы сможем посчитать расстояние до всех и отобрать 100 ближайших, например,
24: Используя датафрейм, пандасы или что-нибудь ещё, а если мы не найдём достаточно точек, то есть их будет меньше чем 100, то мы просто расширим радиус нашего круга, например, до двухста метров и повторим процесс вот, а radius все-таки у нас радиус чего круга. В общем, давай подумаем, какая проблема с круго.
25: Только область для поиска лучше сделать не круглой, а квадратной. Я не смог понять почему, и спросил у собеседующего ну да, сравнить то, что 2 квадрата пересекаются. Не тоже самое, что сравнить, что квадрат с кругом пересекается, надо думать, но в общем, кажется, у них из за большой комбинации разли.
26: Взаиморасположений могут быть разные приколы, а с квадратами как-то сильно проще. Там по сути отрезки надо просто сравнить. И все. Наконец то мы изобрели алгоритм поиска 100 ближайших заведений к точке. Ура. Кто не понял, посмотрите полную версию, которая находится в описании, может быть, станет
27: Понятней. Вот. Окей. Ну возьмём там какой-то условно радиус, и если там 100 не нашли, то увеличиваем наш радиус квадрата. И, в общем, вот это уже похоже на какую-то программу. Там, например, на питоне, которую можно было бы написать, но все равно эти точки нужно где-то хранить. Поэтому по любому здесь будет
28: Используется какая-то база данных, и я его спросил, почему он сказал в начале, что эскьюэль здесь не подходит. Ну, с базами данных. Я имел ввиду, что вот эскьюэль, то, что вот сейчас мы с тобой описали, это, кажется, не похоже на эскьюэль, но мы при этом это написали через условно питон. Давай подумаем, где нам, собственно, эскьюэль.
29: Нужен, нужен, не нужен и так далее. Да, ведь нам нужно где-то хранить координаты 100000000 заведений и какую-то дополнительную информацию о них, которую мы будем выводить нашим пользователям. Что мы скажем нашим нативным разработчикам приложения, куда им нужно вообще ходить. Они, они же не ходят напрямую в базу данных, не ходят в какой-то бэкен.
30: Вот, а вот что мы им дадим в качестве идентификатора этого бэкенда. У нас должен быть какой-то сервер, куда разрабы будут слать http запросы и где будет крутиться наш алгоритм поиска для того, чтобы делать http запрос нужен какой-то пост нейм, н.
31: Точка нет, условно, как запрос доходит физически до нашего, до нашей линукс тачки, где крутится демон, который принимает запрос. То есть как он понимает, что backend точка нет, надо идти сюда. Я ответил, что backend точка нет, относится к какому-то ip адресу нашего сервера. Ну вот не совсем за бэкэнд точка, нет, на самом
32: Деле может скрываться много разных ip сейчас в твоей схеме получается так, что все запросы принимает только 1 сервер и тут я понял ошибку. Он хотел, чтобы я нарисовал, как схематически происходит маршрутизация запросов, ведь мы поднимаем не 1 инстанс нашей программы, а несколько, чтобы они
33: Могли справляться с нагрузкой, кстати, маршрутизацией занимается программа, которая называется балансировщик, да? А вот ты сказал, что там, например, если машинка загружена, он направляет запрос в другую. Давай подумаем, как вот он будет понимать, вообще загружена, не загружена, балансировщик.
34: Это очень тупая программа, которая просто пингует сервера, и если он отвечает на её запросы, то она отправляет ему пакет. А вот у нас ещё есть база данных. Вот, что мы вообще могли бы хранить в этих базах данных. То есть там, кроме точек, как я уже сказал, мы можем хранить любую дополнительную информацию о заведениях, которые мы выводим.
35: Нашим пользователям, кстати, базы данных тоже нужно реплицировать, но обычно базы данных делают немного Копий, потому что базы данных дорогие, и если Копий программы может быть там 20 и даже 50, то Копий баз данных 2, 3 обычно. А что
36: Вот будем делать. Если у нас условно база данных выходит из строя, я предложил систему, при которой за этим всем наблюдает человек. Если что-то ломается, он просто это чинит вручную или зовёт своих коллег. Такая система может показаться очень примитивной. Но я то знаю, что в яндексе
37: Делают именно так. А вот если бы мы, например, хотели бы пользователи че-нибудь кликают, и мы хотим как-то отправлять это в нашу систему, чтоб потом как-нибудь ещё прикрутить ранжирование, вот на основании этих кликов и всякое такое вот чего бы мы делали, чтобы хранить логи Кель
38: Данных не подойдёт, так как логи это большое количество неструктурированной информации, но зато для этого отлично подходит спарк. Что ж, у нас время подошло, подходит к концу. Ура, друзья, вот такое получилось собеседование. Мне когда-то сайнтисту эта секция показалась сложной, но очень интересной.
39: Мы узнали, как онлайн карты быстро ищут нужные нам заведения. Мы узнали, что такое балансировщик и зачем он нужен. Мы также узнали, какие базы данных, в каких случаях лучше всего использовать. В общем, время. Точно провели. Не зря. Я надеюсь, что вам все понравилось, друзья. Спасибо, что досмотрели.
40: Этот ролик до конца. Если вам понравилось, то ставьте лайки, подписывайтесь и пишите свои комментарии. Мне очень приятно их читать. Полная версия этого ролика, как обычно будет в описании под видео. Также напоминаю, что как только канал наберёт 1000 подписчиков, выйдет видео с очень интересным
41: Объявлением, поэтому