Валера, спасибо огромное за видео! Систем дизайн с опытными ребятами очень увлекательно смотреть. Что-то понятно, чему-то можно научиться. Видно, что Евгений натренирован в подобных собесах, даже по времени практически уложился. А я правильно понял, что Quadtree и весь этот GeoBackend описывает эффективный способ расчета географического расстояния, которое совсем не равно расстоянию по автодорогам? Можно ли было бы в данном случае сказать что-то вроде:"Я не уверен, какой наилучший способ найти ближайших водителей. Кажется, что географическое расстояние не совсем подходит, потому что дороги есть не везде. Плюс время пути по одним дорогам больше, чем по другим. Возможно, имело бы смысл выбрать 10 ближайших водителей, а дальше с помощью google maps API или чего-то подобного посчитать время пути, выбрать одного или несколько ближайших водителей, и им отправить уведомление"? Достаточно ли это хороший ответ? И еще вопрос: какой именно мониторинг нужно было упомянуть? Мониторинг системы на ошибки? Метрики, вроде времени поиска заказов и прочего? Что-то еще?
Да, Uber в свое время тратил довольно много денег за вызов API Гугл Карт для расчета времени прибытия. Как только есть географически близкие точки - дальше их можно отранжировать по времени прибытия Мониторинги в первую очередь здоровья сервиса, 99 перцентиль времени запроса, процент ошибок и тп
Очень круто получилось! С точки зрения обучения такие видео более релевантные, чем когда приглашают новичков и они пытаются пук пук пук все готово сделать, мы же в унике не проходим как какой-тоизвестный ученый пытался в юношестве что-то делать, мы проходим уже плоды его работ. Тут уже чётко запоминаешь поинты на которые стоит обратить внимание.
Хочется верить, что для обучения именно прохождению самих интервью в скором времени появятся отдельные материалы. Цель же этой серии в моем понимании не столько научить их проходить, сколько дать понимание, насколько разный может быть результат в заивисимости от подготовки как общей, так и к этому формату в частности, и что в целом к такому формату лучше готовиться.
Что будет если пошеход находится возле границы самого большого квадрата смежной с другим таким квадратом? Мы получим при поиске водителей только с одной стороны от пешехода (в его квадрате) и не получим остальных водителей из соседнего большого квадрата даже если они ближе к пешеходу?
А quadtree будет хранится в памяти и дублироваться во всех поднятых подах "го сервисов" или как это будет работать? Как будет происходить уведомление о пересчитывании quadtree при смене коодинат водителя, допустим, раз в 15-30 секунд?
Спасибо, очень круто, особенно что не очередной youtube/twitter..., по такси моков хороших не найти, только описание после подготовки. По требованиям получился монолог, это норма, или нужно на каждое предположение спрашивать? Например те же рейтинги, если бы Евгений уточнил делать это или нет, это был бы плюс или кандидат должен сам понимать какой функционал успеет задизайнить? Или более того нфт, где могут быть какие то особые требования, вероятно надо уточнять хотим ли мы прозрачность цен а не предлагать от себя. Еще часто вижу противоречия у разных блогеров, одни говорят что после каждого шага надо переспрашивать туда ли движемся, другие говорят наоборот, если что то не так, тебя перебьют. Тут вопросов от Евгения не было, так получилось или советуете что так лучше?
28:03 Как-то не закрыли этот вопрос, по поводу «запасного» бита. А вот если подумать, то одного бита будет недостаточно, т.к представим что у нас всего 10 битов в распоряжении, чтобы закодировать уточняющий адрес: 00|01|11|00|00 И тут уже непонятно, либо все число является адресом(00|01|11|00|00) Либо лишь та часть, после которой идут нули(00|01|11) Тут есть несколько решений: 1. Изменить способ хранения адреса, например если мы уточнили следующим образом(верхний левый квадрат -> нижний левый квадрат: 00|11|00|00|00, то вместо того чтобы хранить таким образом, будем хранить лишь числовой номер этой комбинации - т.к наше искомое число - 4(т.к самый последний номер с первой четвёрки) 2. Ну выделить отдельные 3 бита, которые будут фактически указывать на то, до какой двойки бит следует считывать данный адрес(до 1/2/3/4/5 двойки бит) Например в нашем случаем всё это дело выглядело бы след. образом: 00|01|11|00|00 010 Т.е указывает смотреть до 3-й двойки бит(начинаем отсчёт с нуля, чтобы его значение тоже использовать)
В той части действительно была проблема со способом указания, что глубже идти не надо, но как-то заговорились. Самым простым было бы использовать больше бит на 1 уровень, использовать троичное кодирование, или закодировать вообще все комбинации, как вы правильно предложили, но не просто пронумеровать их, т.к. слишком "тяжелым" может быть номер, а применять разные длины кодов в зависимости от популярности, что-то типа арифмитического сжатия по сути.
По поводу GeoApp, 2 байта на позицию пользователя, поскольку 40КМ диаметр мск. При предложенной архитектуре на каждый город будет своя такая структура?
вопрос по поводу connection-service в случае, когда клиент_x_ водитель могли держать связь. 1) если я правильно понимаю, для такого высоко-нагруженного приложение будет невероятно дорого обходиться ресурс открытия/держания сокет-соединения для КАЖДОГО активного отношения клиент-водитель. 2) как технически разрешается решение, где на load-balancer/api-gateway с constant hashing (для распределения на правильный инстанс) нужно с открытого сокета слать ответы? я имею ввиду вопрос, где клиент шлёт HTTP, а затем ему нужно будет в режиме Socket соединения получать ответы (в обход всех сложных механизмов с constant hashing) спасибо за отличный мастер класс @Evgeny Nizhibitsky :)
@@ValeriiBabushkin предположим у нас tomcat (блокирующий веб-сервер), у которого ограниченное кол-во потоков. Каждое сокет-соединение жрет по 1 потоку на отношение клиент_х_водитель, для поддержки такого функционала придётся скейлить много серверов с поддержкой сокетов, не так ли? [я говорю об открытом сокет-соединении]
Спасибо за видео. Самое интересное из трех видео серии. Собеседуемый парень оч. крутой. Верно ли я понял, что на каждом шаге мы рассчитываем центр квадрата для определения того, какому из четырех квадратов принадлежат искомые координаты (пешехода). Т.е. при глубине в 12, у нас будет 12 вычислений, чтобы получить "адрес" квадрата, по которому мы уже получим множество айдишников водителей? Т.е. для экономии занимаемого места дерева, координаты каждого угла каждого квадрата мы в дереве не храним?
Все эти вычисления легко сделать прямо на стороне клиентского приложения, и тогда клиент при общении с сервером уже будет оперировать в терминах бинарных адресов в дереве сразу. Для «оптимизации» и на стороне клиента эту информацию можно кешировать и обновлять только последние биты адреса, т.к. пешеход не будет телепортироваться обычно, хотя на клиенте такой оптимизацией заниматься скорее бессмысленно.
Оператор-джан, в таком непростом случае все же выбирай целую голову спикера, а не ровный фон. Фиг с ним. Мы слушаем ЧТО говорят умные люди, а не как выглядит фон))
Интересно, что вы обсудили 10 QPS на поиск в QuadTree, но совсем не обсудили как обновляются в нем данные. Например, если 100k онлайн водителей будут каждую секунду слать свою позицию, и ее нужно будет обновлять в QuadTree, то "просто сервис на го" уже вряд ли такое выдержит. Понятно, что можно слать не раз в секунду, а реже, но все равно, во время заказа такси, пользователь хочет увидеть, что машина к нему плавно едет, а не магически становится ближе раз в минуту. В любом случае кажется запросов на запись в эту систему будет значительно больше чем на чтение, и стоит подумать как это обрабатывать.
1. Все 100k RPS не нужно давать на все инстансы сервиса сразу, можно шардирование сделать с привязкой к геолокации, условно 1k RPS давать на Мытищинский «сервис на го», и 3k RPS на инстанс для Хамовников, а между ними иногда синкаться, тогда не нужна сиюсекундная консистентноть между всеми сервисами, ведь такси из Мытищ в Хамовники не телепортируется быстро. 2. «Плавность передвижения» осуществляется частично за счёт предсказания движения, а не большого RPS - так же навигатор будет некоторое время считать, что вы едете по предлагаемому маршруту, хотя уже свернули по своей воле куда-то ещё. 3. Во время поиска передвижение обычно вообще не показывается, только периодически увеличивается радиус опроса, поэтому обновлять и не надо.
@@ValeriiBabushkin про обновление мы обсуждали точно, что нужно сделать количество операций, линейно зависящее от глубины,т.е. фактически константные несколько десятков удалений и записей, т.к. машина обычно успевает только в соседний квадрат переехать, а значит задеты максимум 2 записи на каждом уровне дерева.
Quadtree тут скорее пример как не надо делать на собеседовании. Человек погрузился в детали реализации, без необходимости (чем было обосновано это погружение? я не услышал). Ну и по факту отдельная структура нафиг не нужна, БД умеют делать пространственные запросы, стоят сами quadtree индексы. Сделать запрос в БД водителей, выбрать свободных водителей в таком то радиусе ерунда для БД. Мы же обычно не изобретаем велосипед с другими индекасами, не изобретаем свои БД, без необходимости? Должно быть серьезное обоснование зачем нам изобретать велосипед на этапе поверхностного дизайна.
Этот лев чистый тигр
умение планировать место на доске тоже надо оценивать
Мастер-класс по расчетам в уме ) Респект!
Крутой чувак, показал мастер класс как надо! Мотивирует)
Забурился в функционал, но очень интересно! Спасибо за урок!
Очень крутое интервью. Захватывающее. Спасибо команде за выпуск.
Валера, спасибо огромное за видео! Систем дизайн с опытными ребятами очень увлекательно смотреть. Что-то понятно, чему-то можно научиться. Видно, что Евгений натренирован в подобных собесах, даже по времени практически уложился.
А я правильно понял, что Quadtree и весь этот GeoBackend описывает эффективный способ расчета географического расстояния, которое совсем не равно расстоянию по автодорогам? Можно ли было бы в данном случае сказать что-то вроде:"Я не уверен, какой наилучший способ найти ближайших водителей. Кажется, что географическое расстояние не совсем подходит, потому что дороги есть не везде. Плюс время пути по одним дорогам больше, чем по другим. Возможно, имело бы смысл выбрать 10 ближайших водителей, а дальше с помощью google maps API или чего-то подобного посчитать время пути, выбрать одного или несколько ближайших водителей, и им отправить уведомление"? Достаточно ли это хороший ответ?
И еще вопрос: какой именно мониторинг нужно было упомянуть? Мониторинг системы на ошибки? Метрики, вроде времени поиска заказов и прочего? Что-то еще?
Да, Uber в свое время тратил довольно много денег за вызов API Гугл Карт для расчета времени прибытия. Как только есть географически близкие точки - дальше их можно отранжировать по времени прибытия
Мониторинги в первую очередь здоровья сервиса, 99 перцентиль времени запроса, процент ошибок и тп
Очень круто получилось! С точки зрения обучения такие видео более релевантные, чем когда приглашают новичков и они пытаются пук пук пук все готово сделать, мы же в унике не проходим как какой-тоизвестный ученый пытался в юношестве что-то делать, мы проходим уже плоды его работ. Тут уже чётко запоминаешь поинты на которые стоит обратить внимание.
Хочется верить, что для обучения именно прохождению самих интервью в скором времени появятся отдельные материалы. Цель же этой серии в моем понимании не столько научить их проходить, сколько дать понимание, насколько разный может быть результат в заивисимости от подготовки как общей, так и к этому формату в частности, и что в целом к такому формату лучше готовиться.
Валера крутой выпуск спасибо. Когда будет выпуск про то как банку такую накачать?
зачем мне конкуренты
@@ValeriiBabushkin банки - зачет! муж такие же хочет! но мучает вопрос: ты можешь сам себе спину почесать?
Ля, кайфы смотреть интервью по систем дизайн.
крутой выпуск! нравится! будет еще? жду!!!!
Что будет если пошеход находится возле границы самого большого квадрата смежной с другим таким квадратом? Мы получим при поиске водителей только с одной стороны от пешехода (в его квадрате) и не получим остальных водителей из соседнего большого квадрата даже если они ближе к пешеходу?
А quadtree будет хранится в памяти и дублироваться во всех поднятых подах "го сервисов" или как это будет работать? Как будет происходить уведомление о пересчитывании quadtree при смене коодинат водителя, допустим, раз в 15-30 секунд?
Спасибо, очень круто, особенно что не очередной youtube/twitter..., по такси моков хороших не найти, только описание после подготовки.
По требованиям получился монолог, это норма, или нужно на каждое предположение спрашивать? Например те же рейтинги, если бы Евгений уточнил делать это или нет, это был бы плюс или кандидат должен сам понимать какой функционал успеет задизайнить? Или более того нфт, где могут быть какие то особые требования, вероятно надо уточнять хотим ли мы прозрачность цен а не предлагать от себя.
Еще часто вижу противоречия у разных блогеров, одни говорят что после каждого шага надо переспрашивать туда ли движемся, другие говорят наоборот, если что то не так, тебя перебьют. Тут вопросов от Евгения не было, так получилось или советуете что так лучше?
Про ценообразование как то совсем мельком упомянули, казалось бы довольно важная часть и для пешехода и водителя, и для бизнеса
Ценообразование это уже скорее ML System Design.
Было упомянуто, что неплохо бы его сделать прозрачным в отличие от известных примеров.
Женя жесткий
28:03
Как-то не закрыли этот вопрос, по поводу «запасного» бита.
А вот если подумать, то одного бита будет недостаточно, т.к представим что у нас всего 10 битов в распоряжении, чтобы закодировать уточняющий адрес:
00|01|11|00|00
И тут уже непонятно, либо все число является адресом(00|01|11|00|00)
Либо лишь та часть, после которой идут нули(00|01|11)
Тут есть несколько решений:
1. Изменить способ хранения адреса, например если мы уточнили следующим образом(верхний левый квадрат -> нижний левый квадрат: 00|11|00|00|00, то вместо того чтобы хранить таким образом, будем хранить лишь числовой номер этой комбинации - т.к наше искомое число - 4(т.к самый последний номер с первой четвёрки)
2. Ну выделить отдельные 3 бита, которые будут фактически указывать на то, до какой двойки бит следует считывать данный адрес(до 1/2/3/4/5 двойки бит)
Например в нашем случаем всё это дело выглядело бы след. образом:
00|01|11|00|00 010
Т.е указывает смотреть до 3-й двойки бит(начинаем отсчёт с нуля, чтобы его значение тоже использовать)
В той части действительно была проблема со способом указания, что глубже идти не надо, но как-то заговорились. Самым простым было бы использовать больше бит на 1 уровень, использовать троичное кодирование, или закодировать вообще все комбинации, как вы правильно предложили, но не просто пронумеровать их, т.к. слишком "тяжелым" может быть номер, а применять разные длины кодов в зависимости от популярности, что-то типа арифмитического сжатия по сути.
По поводу GeoApp, 2 байта на позицию пользователя, поскольку 40КМ диаметр мск. При предложенной архитектуре на каждый город будет своя такая структура?
вопрос по поводу connection-service в случае, когда клиент_x_ водитель могли держать связь.
1) если я правильно понимаю, для такого высоко-нагруженного приложение будет невероятно дорого обходиться ресурс открытия/держания сокет-соединения для КАЖДОГО активного отношения клиент-водитель.
2) как технически разрешается решение, где на load-balancer/api-gateway с constant hashing (для распределения на правильный инстанс) нужно с открытого сокета слать ответы?
я имею ввиду вопрос, где клиент шлёт HTTP, а затем ему нужно будет в режиме Socket соединения получать ответы (в обход всех сложных механизмов с constant hashing)
спасибо за отличный мастер класс @Evgeny Nizhibitsky :)
Один сервер легко держит десятки тысяч соединений, кажется здесь нет проблемы
@@ValeriiBabushkin предположим у нас tomcat (блокирующий веб-сервер), у которого ограниченное кол-во потоков. Каждое сокет-соединение жрет по 1 потоку на отношение клиент_х_водитель, для поддержки такого функционала придётся скейлить много серверов с поддержкой сокетов, не так ли?
[я говорю об открытом сокет-соединении]
29:24, а почему это правда, у нас же у водителей из
общего квадрата все "верхние" квадраты общие и их не нужно хранить для
каждого, разве не так?
Спасибо за видео. Самое интересное из трех видео серии. Собеседуемый парень оч. крутой.
Верно ли я понял, что на каждом шаге мы рассчитываем центр квадрата для определения того, какому из четырех квадратов принадлежат искомые координаты (пешехода). Т.е. при глубине в 12, у нас будет 12 вычислений, чтобы получить "адрес" квадрата, по которому мы уже получим множество айдишников водителей?
Т.е. для экономии занимаемого места дерева, координаты каждого угла каждого квадрата мы в дереве не храним?
Все эти вычисления легко сделать прямо на стороне клиентского приложения, и тогда клиент при общении с сервером уже будет оперировать в терминах бинарных адресов в дереве сразу.
Для «оптимизации» и на стороне клиента эту информацию можно кешировать и обновлять только последние биты адреса, т.к. пешеход не будет телепортироваться обычно, хотя на клиенте такой оптимизацией заниматься скорее бессмысленно.
13:31 откуда 100к секунд?
Оператор-джан, в таком непростом случае все же выбирай целую голову спикера, а не ровный фон. Фиг с ним. Мы слушаем ЧТО говорят умные люди, а не как выглядит фон))
Запишите меня на System design курс пожалуйста, можно прям в первый поток
Круто, интересно, что в систем дизайне никак не затрагивают тему безопасности данных, защиты и т.п.
да, кстати, почему?
Интересно, что вы обсудили 10 QPS на поиск в QuadTree, но совсем не обсудили как обновляются в нем данные. Например, если 100k онлайн водителей будут каждую секунду слать свою позицию, и ее нужно будет обновлять в QuadTree, то "просто сервис на го" уже вряд ли такое выдержит. Понятно, что можно слать не раз в секунду, а реже, но все равно, во время заказа такси, пользователь хочет увидеть, что машина к нему плавно едет, а не магически становится ближе раз в минуту.
В любом случае кажется запросов на запись в эту систему будет значительно больше чем на чтение, и стоит подумать как это обрабатывать.
@Evgeny Nizhibitsky мне почему то кажется что мы обсуждали такое, ты не помнишь?
"машина к нему плавно едет"
это уже после мэтчинга, там можно p2p слать координаты
а для самого мэтчинга можно и реже обновлять
1. Все 100k RPS не нужно давать на все инстансы сервиса сразу, можно шардирование сделать с привязкой к геолокации, условно 1k RPS давать на Мытищинский «сервис на го», и 3k RPS на инстанс для Хамовников, а между ними иногда синкаться, тогда не нужна сиюсекундная консистентноть между всеми сервисами, ведь такси из Мытищ в Хамовники не телепортируется быстро.
2. «Плавность передвижения» осуществляется частично за счёт предсказания движения, а не большого RPS - так же навигатор будет некоторое время считать, что вы едете по предлагаемому маршруту, хотя уже свернули по своей воле куда-то ещё.
3. Во время поиска передвижение обычно вообще не показывается, только периодически увеличивается радиус опроса, поэтому обновлять и не надо.
@@ValeriiBabushkin про обновление мы обсуждали точно, что нужно сделать количество операций, линейно зависящее от глубины,т.е. фактически константные несколько десятков удалений и записей, т.к. машина обычно успевает только в соседний квадрат переехать, а значит задеты максимум 2 записи на каждом уровне дерева.
Quadtree тут скорее пример как не надо делать на собеседовании. Человек погрузился в детали реализации, без необходимости (чем было обосновано это погружение? я не услышал). Ну и по факту отдельная структура нафиг не нужна, БД умеют делать пространственные запросы, стоят сами quadtree индексы. Сделать запрос в БД водителей, выбрать свободных водителей в таком то радиусе ерунда для БД.
Мы же обычно не изобретаем велосипед с другими индекасами, не изобретаем свои БД, без необходимости? Должно быть серьезное обоснование зачем нам изобретать велосипед на этапе поверхностного дизайна.
позерство, скорее всего. мол, я знаю, что это, и как оно работает
по-моему очень глупая затея не говорить про мастер-слейв. Это из разряда "не говорить про папа-мама, используя родитель1-родитель2",
"есть графана" - без графана вы про фана...
ладно сойдет за обе стороны - хотя по виду тихий ужас - "карго культ" - оба господина об этом.