System Design с Валерием Бабушкиным | Выпуск 3 | Собеседование | karpov.courses

Транскрипция видео:

• жень привет это я рад тебя видеть мы как бы мог подумать в 2017 году когда мы вместе тащили осенью к рванут ирвинга что окажемся на двух стульях но оба нормальный будем с тобой обсуждать следующую историю расскажи тебя уже здесь спросили кто ты за na'vi тоже в 1 кто ты ну прямо сейчас я тимлид в команде машинного обучения в компания экспресс россия мы занимаемся матч янгом товаров то есть ищем наши товары которые есть на нашей площадке и находим такие же товары на площадках конкурентов вот непонятная монкада вариантов валик ну

  00:00:03 - 00:01:24

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

  00:00:44 - 00:01:51

• камере то есть ты не участвовал вместе со мной ильёй но и сам это было очень рисовать соревнования я там было по моему в топе лидер барда один и все остальные были в пятером да да в итоге на каком месте ты оказался тут опять на первый саммит и влетел в топ 3 пункт к ней было написано хорошо мы ты уже знаешь сегодня будем делать человек опытный system design тебе достается самая на мой взгляд сложная задача одна я сам сложно задач но я причем догадываюсь ты знаешь как ведет потому что эта структура данных

  00:01:17 - 00:02:25

• задачу час от который висит игорю игорь привет за дизайне губер то есть это kolber сервис в котором люди вызывают такси садятся на него то есть нужно понимать где находится водитель при этом водитель может передвигаться где находится пользователь но пользователь может передвигаться на зачастую ну же из какое-то фиксированной точки вызывает он садится машинок он на них приезжает куда-то и заканчивается эта поездка есть пока водитель везет он недоступен для новых заказов а может быть и доступен в

  00:01:51 - 00:02:59

• конце сервис работает по всему миру нагрузка высокая допустим пусть у нас будет он этот 500 пользователей и 5 миллионов водитель за дизайн пожалуйста нам систему но данное первое что сразу стоит заметить что в отличие от многих наверно других систем которые там какой-нибудь делаем какой-нибудь сервис twitter там youtube или еще что то то есть у нас сервис не глобальный в том смысле что когда мы пишем пост мы выпишем всем когда мы хотим как будто написать сообщение что ядрами мы пишем любому человеку в любой

  00:02:26 - 00:03:53

• точке мира здесь же у нас основная особенно задача состоит в том что поиск водителя это локальность с точки зрения как дела локальная задачу то есть нам нужно найти водителя чтобы совершить поездку в каком-то месте естественно водитель должен именно из какой-то вот этой выборки водителей которые не очень далеко то есть нам не хочется ждать целый час водители сейчас бы там желтуха штук он отвез нас там десять минут я не поесть после этой записи вот спицын давайте поговорим сначала на требование к этой задачи которые мы

  00:03:09 - 00:04:17

• хотим там рисовать до начала мы опишем функциональные требования что мы как пользователь мы умеем делать плюс здесь еще интересно что у нас пользователь на самом деле пользователь сервиса делятся на 2 категории потому что водители это тоже пользователь вот здесь у нас есть сервис с точки зрения пользователя есть сервис точки зрения водителя плюс сервис еще раз у нас разделен на скажем так real-time часть и но оффлайн то есть мы совершаем какую-то поездку в режиме реального времени и затем уже потом

  00:03:42 - 00:04:40

• можем как-то отдельно послужить информацию то есть у нас будут две такие крупные части 300 которые происходят здесь и сейчас чтобы создать поездку отследить поездку завершить и затем уже сложить от какое-то for место поэтому опишем сначала функциональные требования что как пользователь как водитель мы можем делать с точки зрения пользователя пользователя которые именно пешеход будем считать значит первое что мы можем делать это указать то есть зайти в приложениям посмотреть сколько этом есть ли какие-то машины

  00:04:12 - 00:05:29

• поблизости вбить какой-то адрес куда мы хотим поехать и затем начать поездку то есть первое вбить сбить порезку куда мы хотим наехать там второе найти водителя ну и затем у нас уже будет совершается поездка плюс там можно какой нибудь править информацию то есть условный профиль назову это например карты оплата менять что там ещё есть в яндексе там даже рейтинг сейчас есть и и пью райан творить 49 с копейками обычно так наверно из функциональные для пешехода боли меня все если что же тут а потом вспомним для водителя

  00:04:50 - 00:06:10

• остается на водитель что он из пользователь совершает более такой разово действо водитель же он выходит из на смену и на смене он принимает заказывать то он может выйти на смену потом насколько понимаем этом прилетает такое уведомление что вот такой это заказ он может его принять или отклонить и по моему из за это штрафуют потом помоги деньгами к ментам социальным рейтингу принять повестку затем естественно происходит поездка в конце поездки статей пользователей водителями мама трейдинг поставить в

  00:05:53 - 00:06:55

• конце там высвечиваются здесь тоже где то есть три с половиной ребенка после вот ну естественно на этом пск завершается он может вернуться либо на пункт 2 принять еще какой-то следующий заказ либо он может завершить мин на это с точки зрения мина функциональных требований какие функции наш сервис предоставляет пешеходам и водителям тем мы опишем не функциональные требования к зуб казалось бы причем здесь nrt нам как пешеходам не хочется ждать по 20 минут когда на получится машина то есть хочется найти водителя поблизости

  00:06:43 - 00:08:07

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

  00:07:47 - 00:09:08

• строки для нервы заказывай поблизости у него не ждать недолго у него простая недолгий не хочется сидеть просто ношению но и доступность тоже как бы на него то есть если нам недоступно такси манометра поедем освободителю недоступным для xeon без денег будет сидеть у него с точки зрения не функциональных требований то есть и поездка там но это уже с точки зрения гео-локации наверно поиск совершается более-менее по оптимальному шутеру чтоб они жаловались что денег тратим много то есть оптимальность

  00:08:28 - 00:09:28

• еще одно требование наверно которая бы выдвинул на котором даже яндекс такси не соответствует эту прозрачность вот почему если я проверил такси и обулся и она стала стоить 2 раза дороже хотелось бы объяснить это как-то ну я напишу это со звездочкой при этом если мы скажем водителя что что-то слишком дорого мы от них соответствующую историю в обратную сторону наверняка будем слушать в собственные через поездки но остается с точки зрения требований теперь давайте проговорим про наше эстимейт и того сколько все это место

  00:09:13 - 00:10:22

• занимает какие прочность то что ты проговорил у нас есть сколько там 5 0 5 миллионов пользователь родитель миллионов и 500 миллионов пешеходов понятно циклы здесь можно обсуждать может быть 301 в целом понятно что uber это как любой taxi service is помимо то что я посетил какую-то локальности в костре нет мы там вызываем заказ и нам нужен водитель который через 5 мы приедем понятно что мы скользящие будем ехать в рамках москвы там если мы здесь заказ возьмем и но и евро цена там не знаю такси в краснодар мы знаем вот

  00:09:52 - 00:11:03

• поэтому все равно здесь ещё будет такая как бы первый уровень условно локальности это то что все равно сервис работает в каждом городе свой то есть когда мы подключаемся то есть мы сейчас только у них московском яндекс такси начинаю выбирать то есть мы можем в принципе вот это вот вещь сразу разбить то есть какой такой глобальный лот бенстер как который еще прям нашим клиентском приложении нас определяют что мы еще в таком-то городе и такси нам нужно искать исходя здесь например если мы возьмем

  00:10:34 - 00:11:28

• крупную москву например то есть у нас есть 10 миллионов пешеходов и на миллион водители 500000 сколько их но здесь соотношение было один к ста ну значит будет столько водителей по поездкам мы будем считать что каждые 10 совершает поездку в конкретный день то есть есть один миллион или the fathers напишем но в целом там одну две три поездки то есть поездок принципе столько же ежедневно будет происходить но и вводить водителей до или актив ты достоин с у нас это будет и знаю но водителю почти все время

  00:11:01 - 00:12:21

• работают на этом 50к да и для этих driver's будем считать это так это совершается если один миллион в день как у нас там сто тысяч секунд значит каждую конкретную секунду а у нас еще поездка длится сколько то в среднем там допустим 1 час москве когда все стоит то есть у нас есть 24 часа у нас один миллион поездок распадаются на 25 это получается 40000 одновременных поездок у нас поездок одновременно и поисков поездок тогда если на 100000 секунд миллион поездок еще мы секунд там 10 в среднем у нас получается сейчас

  00:11:46 - 00:13:08

• секунду действенно времен на 10 секунд они занимают то есть то грубы 1 100 г рыбы инициируется стон 100 новых 100 каких на поиск водителю до что не значит поездка естественно происходит столько из них потом одновременно работают течение там правильно так и ставлю 10 каире персик and is the connection of не что то есть мы как бы 10 секунд еще здесь кайри персиком потому что у нас один миллион доу и 100000 секунд это у нас миллион поездок но мы можем накинуть там условно его задал он и кажется какой то есть имеет

  00:12:36 - 00:14:09

• припяти 100 миллионах всеобщего нет это я в рамках как даже самого крупного города тоже перу в целом мы можем перейти на потом на суммарную просто дам новый принцип целом там в 550 раз поможет умножить будет получим суммарную так наверно это по требованием по то есть это по трафику смысле трафика именно количество пользователей соединение прочего вот мы потом наверно оценим сколько нам еще хранитель уже информации про пользователей про водителей потом складывать поездки куда-нибудь базу данных я думаю частную перейдем к

  00:13:38 - 00:14:59

• какому-то вск уровнем и понимание как сервисом же работает будет а схемам потом еще дополнительные оценки уже по исходя из того что мы вообще будем хранить и записывать значит у нас есть 2 категория пользователей у нас есть пешеход есть водитель сказать на они каждую смотрят своя какой такой клиентов рейтинг приложения описанных он даже это разное то есть это драйвер сервис я пока без там логин серов и прочего дерево нет рядом ниц и и для сцены и как я уже сказал у нас получается у системы будет разбиваться на две части

  00:14:26 - 00:15:49

• то есть как пешеход мы инициируем поездку мы хотим естественно это просто будет происходить водитель он и инициирует поиск ему находится то есть мы решаем какие страны задачу матч инга мы смачиваем водителя и пешехода и затем нам нужен какой-то сервис который будет поддерживать эту поездку во время того как она происходит водитель и пешеход как-то обмениваются их приложения информацией у нас есть какое-то там про промежуточный сервис который будет обмениваться с ними этой данные плюс у нас есть про пешеходы и про

  00:15:18 - 00:16:26

• водителя у нас есть там базу данных собственно с этим профилем и всем прочим то есть где то там они в целом могут быть вообще разные не пересекаться может быть одна база данных вот затем то есть мы инициируем сервис есть какой-то connection сервис в которой собственницы рует между ними общение затем эта поездка происходит после как поездка заканчивается она складывается куда-то же как произошедшая поездкой плюс мы должны хандрить этом оплаты вот эти все истории то есть connection сервис он скорее

  00:15:52 - 00:17:00

• всего когда ты поймешь что поездка завершилась не может ли до конца доехали бы раньше закрыли после этого он должен в какой-нибудь там роиться сервер собственно тот который будет ходить что вот там поездка завершилась и как ты ее нужно спорить для удобного масштабирования до капли нга разных вещей нашей системе я бы ввёл сразу system design какую-то вещь типа шины ивентах например ту же кафку чтобы можно было такие события складывать 12 разные по части системы потом реагировали на то или иное действует она

  00:16:32 - 00:17:37

• началась поездка значит он конечно сервис давай что-то выделяет ресурсы еще закончилась поездка значит нам нужно снять деньги из пользователя там накинуть танки тачки водителю вывести водители опять встроенное или снять отказался то есть наверное тот райт сервис он скидывает информацию какую-то кафку либо да можно настройках сообщений ну да мы с альбац брокер connection сервер сказать эту шину на этой шине у нас сидит сервис который видит что нам поездка заканчивалась или началась так естественно

  00:17:08 - 00:18:26

• сейчас подумаю какие еще крупные такие на кино пили уже потом помимо баз данных для пользователя баз данных для водителя у нас должен быть еще собственно чем uber будет опять же отличаться от других систем у нас должен быть специальный белый локейшн сервис который собственно пай-мальчик такое пользователь рядом что такое они не рядом для нас должен быть какой-то отдельный dial-up гиа backend конечно зову с которым нам нужно общаться то есть для пользователя connection сервис должен через гигабайт понять какие водителя

  00:17:47 - 00:19:08

• можно считать то то что они рядом для водителя нужно понять как бы чтобы он записался что он здесь и где пользование да и чтоб ему потом показали где где где пользователь то есть какие-то из принципе это принимать это интересно значит пока наверное какие-то крупные куски потом накину наверно про вот эту из интересная часть двое про него подробнее это как решать задачу найти кого-то кто у нас есть рядом есть разные структуры данных для этого в целом они похожи наверное такая более академично я простая для понимания записи есть такая

  00:18:29 - 00:19:40

• штука называется quadtree какие еще есть гексагональная отвожу брать библиотека h3 с которой собственно позволяет на гексагональной карте там все разбиение поиски делать просто точки зрения простого простого разработчика квартире понятен тем что у тебя из иксы и игреки просто координаты для эти каждый квадратик можешь победить о ну давайте чуть подробнее расскажем отсутствие у нас есть грубо говоря карта мира понятно что она там для когда мы находимся яндекс такси москва у нас есть кусок то московской

  00:19:05 - 00:20:16

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

  00:19:40 - 00:20:44

• от плотности то есть если мы где-то в центре рядом скорейшего желательно там несколько кварталов если мы там не знаю хотим уехать из красногорска то значит там можно взять машину 10 метров по мкаду на приедет к нам приедет нас заберет поэтому нам желательно для поиска мы можем чем мельче мы разбиваем тем более точно мы выбираем вот это вот понимание рядом при этом если мы разобьем просто всю карту слишком мелко нам пранк слишком много данные чтобы хранить вот эти вот все все все мелкие квадратики индексы да поэтому

  00:20:12 - 00:21:21

• нам желательно адаптировать например что в каждом квадратики там было сколько-то ним небольшим сколько-то водителей вот и в зависимости от необходимости можем побить чуть сильнее 100 где наоборот или или или какие-то укрупнить если там танец мероприятие или пробка там прошла и уже не так важно поэтому мы можем адаптировать эту структуру то есть у нас есть какое-то и не шил разбиением для наших квадратиков затем если мы видим что у нас какие-то квадрат и выдают большей плотностью то мы можем разбить

  00:20:47 - 00:21:43

• их на еще на 4 часть идет вопрос не то есть я пай пользователь нахожусь где в каком-то квадранте как сервис знает каком квадранте у нас есть приложение яндекс и которая использует gps поэтому у нас есть как бы в эти планки как выглядит запрос к базе данных с точки зрения пользователя то есть мы сообщаем связать идет вон тут ходим как бы в в этот гигант начинаем один нам свой сервис какой-то клайн fighting он зачем идет в г в бэг-энд что понять где мы находимся или затем найти машину и эти машины будут какой-то больше крупной

  00:21:15 - 00:22:27

• структуре находиться вот в эти как 1 к 3 то есть мы сообщаем lucky john кличут он нам нас маппет в какой-то большой квадрат затем мы сообщаем у нас еще пол во время поиску то потеряется радиус так же как в приложение напрямую даже как карта отделяется чтобы это проиллюстрировать то есть мы сначала ищем у нас есть какой-то там радиус там дельта окрестность мы находим те куб куб квадро деревья точнее кадра клеточки которые мы задели затем нас может быть попасть какие-то крупные куски какие-то мелкие если мы

  00:21:51 - 00:23:01

• хотим радиус уточнить то есть мы видим что мы вот этот вот задели вроде бы давайте начнем подробнее мы вобьем еще на четыре части смотрим затем в какую из более мелких частей мы попали и тем самым мы как бы находимся все квадратики там как которые заполняют наш радиус поиска и при этом это наша система так как у нас есть довер сервис который сообщает что в каком месте у нас есть активные водители мы понимаем и начинаем прошивать то есть у нас и так есть connection сервис который работает из водитель из

  00:22:26 - 00:23:36

• пешеходам и с водителями и он начинает водителям присылать им сетей что-то в зависимости от их приоритета их рейтинга и прочие плюс там накидывать стоимость если водитель и перестают отвечать самым накидывается общая там базовая стоимость для всех поездок средстве на какой-то водитель он тыкать что данная часть хорошо поездку и после этого устанавливается connection сервисом сообщает пользователю что до водитель согласился и поиск начинается дальше у нас может быть общение напрямую пир toupper между

  00:23:01 - 00:24:07

• приложением пользователей водитель например я хочу изменить адресе это вбиваю водитель то там сразу приходит они там через какие-то промежуточные сервиса то есть это в этом нет необходимости то есть мы как бы между собой разруливает текущую поездку когда оно закончится уже это там сообщается в эту ширину поездок и там хоть раз сервис поездок уже определит что там происходило поэтому скорее всего здесь есть то есть помог an action service есть какой-нибудь отдельный под сервис там для winter в абсолют sockets хендлер то есть это

  00:23:34 - 00:24:35

• штука которая позволяет нам как раз между приложением между над приложениями через посредника сохранять постоянно какую-то связь между собой чтобы мы видели что там добавил адрес пользователь водитель сразу это приходил он сразу маршрут изменила не ждал пока там пока весь сервис обработать довольно долго этот запросам может уже поворот пропустили нужный вот соответственно такая структура нам позволяет адаптироваться к частоте после понятно что если мы дошли до клетки в которой по всего три водителя моим всем

  00:24:05 - 00:25:07

• трем уже скинни мыслим там очень много водителей и мы и там вот в этом квадрате много мы задеваем этот квадратик ему меньше водителей tank top 500 мы сдается начинаем делить этот квадратик попадаем в более мелкие и вы забираем уже только нужных водитель чтоб не опрашивает он все тысяч в радиусе 10 километров вот поэтому если когда там ситуации разгрузится к ночью дело близится водители становятся меньше мы начинаем укрупнять эти квадраты обратно в нашей структуре и постоянно пересчитываю над стана в таком постоянном и мы их держим

  00:24:37 - 00:25:45

• сколько на память давайте посчитаем что ни будь то есть треть функциональные не функциями требования принципе помнить так на давайте возьмем например какой нибудь квадро дерево для москвы сколько бы она могла занимать у нас есть москва можем запасом взять например что у нас по ширине по высоте там будет сколько ни 40 километров этот квадрат 40 на 40 километров мы его разбиваем страстно для разбиения у нас получается чтобы уйти на один уровень глубже нам нужно 2 бита то есть и потом нолики книжка 0 книжка по высоте и ширине и

  00:25:11 - 00:26:42

• затем то есть каждый раз когда мы укрупняются за каждый шаг мы добавляем плюс четыре бита чтобы сохранить именно нашу конкретную позицию либо можно чуть-чуть изменить то есть нельзя взять запасом чтобы еще отдельно описать ситуацию не нырять дальше на каждом уровне у нас становится в четыре раза больше мест где бить на 4 бита или нет вот и нарисовал сейчас у тебя ты потратил два бита здесь два бита здесь здесь уже получилось четыре квадранта и в каждом из них снова нужно по четыре бита правильно я сейчас

  00:26:01 - 00:27:13

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

  00:26:36 - 00:27:44

• вот в этой системе теллера естественно каждый раз когда мы получаем на выбит мы уточняем в два раза то есть у нас было 40 километров до 140 тысяч метров каждый раз мы уменьшаем это в 2 раза точность получается сколько нам 250 это будет 1024 наверное чуть по точнее хочется еще нормально ну или 40 путей 40 метров соответственно это делим на 2 в 10 получается 40 метров точностью на самом для именно поиск нормальными на позиционирование где стою это не очень вот два в 10 но если запасом взять там добавлять какой-нибудь дополнительный

  00:27:11 - 00:28:32

• бит что точнее не надо либо можно запасным поддаваться ответить что что нет я просто хочу понимать как не кодировать что я просто остаюсь на эту муру женю 2 десятых 220 это огромная разница в тысяч раз love 12 мало и за пределы москвы выехал все-таки получаешь и 212 и позволить увеличить 40 километров до 160 ну да получается у нас эти 2 в двенадцатой то есть мы храним как бы руки и даже запасом два байта gepai то ли беда но 2 в двенадцатой это искал здесь начало 2 2 бита или не два байта это 2 12 у него точно поместится плюс еще

  00:27:54 - 00:29:27

• какая-нибудь там инфа по я потому что игры все нужно 2 бита чтобы разбудить а сейчас ты горишь два байта до обито чтобы каждый шаг сделан когда то есть нам всего на 12 шагов и все вся весь наш маршрут занимает дома все весьма сильно полная наша позиция совета на эту позицию должны сохранять для всех водителей всех пешеходов чтобы не стесняться у нас получается даже если взять вот эту всю нашу церковную систему нас получает 5 мегабайт 10 мегабайт нас занимают водители и один гигабайт занимает позиция для

  00:28:45 - 00:30:03

• пешеходов а как поиск фазе структуре происходит какая у него сложность получается каждого latitude ломтики правильно дамы получается то есть у нас есть дерево у нас фактический поиск пойдет как раз по деле у нас есть каждый раз четыре варианта куда пойти дальше мы понимаем что так у нас радиус такой то это примерно как задачи похоже получается просто на 2-мерное но в целом она похожа на одномерную задачу как как найти все числа в бинарном дереве поиска из нужного диапазона вот получается мы каждый раз отрезаем что

  00:29:29 - 00:30:46

• если у нас какая-то ветка идет в большее число чем у нас наибольшее или наоброт из нас минимум больше чем наш максимум поиска или максимум дереве больше минимум то есть мы как бы обрезаем такой весь вес у нас получается что где-то мы идем глубже где где-то мы идем меньше но по факту 12 операций предельно но да то есть но сложность это гонителями танк на и время но в целом да тазик сложной все-таки от глубину а дерево в целом получается что поиск и быстро но эту штуку нужно постоянно на бы на обновлять то есть мы

  00:30:11 - 00:31:16

• каждый раз там водителя говорите онлайн идём-идём-идём добавляем понимаем что у нас в этом листе уже на хочешь к много водитель начинаем его добить пополам либо наоборот водитель говорит я все на катался на сегодня видим что в листе осталось мало значит укрепляем она наоборот но ты такое дерево на динамически менять глубину получается ну в зависимости от того как поиски начинается заканчивается так хочется наверное побольше теперь вот сюда сюда чистили кидать вас на хэширование как-то можем здесь или не

  00:30:44 - 00:31:50

• имеется я почему спрашиваю 12 операций это принципе не так чтобы много в этой 12 раз больше чем одна операция мы можем сделать это наверно оптимизацию как в случае задача по по деревьям 5 же английского манчестер то есть понять в какой у нас общие региону двух вершин ты снова про также можем за 10 запросов секунду правда то есть если я знаю что у меня уже был запрос в это в этот лист в в течение каких-то последних пяти секунд может быть не выдать то же самое выродка у меня все покинули все водители а то про

  00:31:17 - 00:32:32

• это немножко про другое процесс начал говорить ни одной а мой вопрос простой 12 операций можно провести но лоб лоб скажем 12 мы посчитали нас но ведь одна операция это в 12 раз быстрее чем 12 можно ли как-то сделать здесь одну операцию я щас просто другую штуку говорил то есть как понять что водитель и пешеход попадают не делают этот полный полный поиск то есть мы можем выбрать из всех водителей только и тех у которых то есть когда мы кодируем вот этим вот двумя байтами позицию только тех у которых префиксов падает между собой так

  00:31:58 - 00:33:09

• решается задача лист команд сестер в дереве если мы бинар на закодируем все наши пути лево право и так далее то у нас сделали ну да то у нас у двух вершин общая вершина будет иметь код к общей префикс плюсы 0 и вот здесь надо как-то похоже может быть история мы понимаем для нас есть пешеход у нас с радиус поездки поэтому нам нужно просто все водители с нужным префиксом зависимости от радиус радиус увеличивается префикс укорачивается водитель становится отвечать больше на это все это как [музыка]

  00:32:36 - 00:33:39

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

  00:33:07 - 00:34:24

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

  00:33:46 - 00:34:47

• принципе легко это понять то есть у нас либо квадрат соседней в той же разбивки либо квадрат будет соседней там из какого-то уровня разбивки то есть мы поднимемся на сколько это и опустимся на другой то и соседних квадратов то есть чтобы не идти по всему дереву не 12 операции скорее все это будет там 1 2 см и сокрытием как бы не не лагай она просто будет фактически константа скорее вся в среднем по больнице да самым можем main тренить как бы позиции наших водителей паку от дерева ну это пока все давайте

  00:34:16 - 00:35:18

• вернемся к в общем нашего сервиса что еще какие нам частью нужны ты сказал что 20 мегабайт это занимает но это занимает именно индекса а ведь мы еще в листе хотим записать перемыто get в отдельным будем писать кто кто в этом и сейчас находится то есть для каждого листа хранить сет яичника в тех кто там сейчас в нем сидит как если я запросил вот я пользователь я упал в лист между нужной кто там находится еще правильно нужно из водителей а как я этого на если мы нигде не записали правильно сейчас я пока просто про ну да

  00:34:47 - 00:36:07

• окей напишу то есть нам надо знать [музыка] так страстно сервис будет поддерживать вот это как раз вот так я нарисую как раз это квадро наше дерево с базы данных чем она будет частично ссылаться на вот вот этот вот и на вот это вот чтобы водители каких-то пыли идиш ники но будем считать что у нас там у пользователя и у водителя есть какой нибудь типа int64 хищник не стану для драйвера для страны и в нашем собственно этом дерево то есть помимо того как мы делаем запрос именно к вере когда пользователь приходит и

  00:35:30 - 00:37:08

• попадаете в клеточку в этой клеточки нам нужно собственно записывать сохранить сет из тех водителей которые там находятся вот если у нас причем это динамическое то есть словно все водители они будут как раз размещены по всей этой таблички и для то есть суммарное количество элементов всех цветов во всем куда берию это будет просто количество водителей которые существуют на лекторы онлайн хотя бы на получать сценическая 4 то есть вот у нас восемь байт на сколько у нас тут сто сто тысяч пять минут всего было здесь

  00:36:46 - 00:38:01

• 5 миллионов получается 40 40 мегабайт будет хранить информацию для куда дерево то вам наверное сел бы в памяти между и даже пользователи пусть они добавят причем опять же мы это глобально для всех посчитали а мы говорю что ходим локаль именно дату сможем использовать армию помада дителей вся вся эта штука это просто россии написанными история но по факту внутри которая позволяет посчитать в квадранте ii всегда квадрант радовать а потом еще какая-то ассоциация где структура данных уже какой гридо той

  00:37:32 - 00:38:38

• стану листе у нас хранится постоянно водители плюс водитель говорит заканчивать мы удаляем из сета или когда он за границу пересекает нужно из одного предложения друг и только что мы сейчас обсудили как раз все отлично вот так да то есть нас 50 сервис драйве сервисе так ван хельсинг и это приложение у нас есть как бы какая-то db для собственной информации по переходу по информации есть база данных табличка персонал тыкать информация по водителю для этого скорее всего можем что-то использовать кнопкой бы простоя типа майский этом

  00:38:06 - 00:39:12

• какой-то обычные дмс продолжение которое нам бесплатно дает как бы и сид теорема выполнение значение интерес и 10 свои сложные ряда выполняется вот в целом как бы это нам хорошо то есть мы это мы заменяем профиль ничего не теряем как бы все все условия на плюс но поездок будет много происходить их как бы нужно тоже куда-то складывать что потом производить аналитику но в целом хранить информацию по поездка из пока поездка происходит мы общаемся с к нашим сервисом и записываем у нас должна быть отдельно наверное

  00:38:39 - 00:39:45

• более доступной база данных текущих поездок что подписывать там какой-то маршрут запоминать что сейчас происходит если вдруг поиск прервется потому что то страшное случится на узнаем какой водители с каким пешеходам куда ехал что с ним происходило с нас искать табличка с текущим поездка есть табличка отдельная на отдельно базу с история поездок которые мы используем для после последующие аналитики для текущей таблички наверное можно поддерживать какой-нибудь оля радист с какой-то мере сторож который бы позволял быстро

  00:39:12 - 00:40:08

• общаться быстро обновлять данные принципы всю историю может сохранить какой-нибудь список из патентов стоим стоим память чем-то таким но в принципе вроде с лист или легко можно складывать по у нас когда генерируется поездка создается новый ключ для поездки у неё свойство какой водитель какой пешеход и какой у них маршрут своим с темпами что-то информация в принципе немного потому чуть подробнее описать вот настраивать сервис который общается с нашим высоким менеджером который общается с водителями драйверами он

  00:39:40 - 00:40:46

• записываю в какой-то и номер старик radisson ну да условный родис снята какие-то текущие поездки плюс по 100 как поездка завершается у нас отравить сервис положит в историю но будем считать что это либо там кассандра любишь bass то есть там просто много очень данных либо клик house тоже можно записывать у него до дало ночную важную до коллаж на базу данных в целом как бы считается что там либо ибо если бы кассандра зависит этого если вас hadoop на самом деле в той же сегодня уже упоминал спасаться теореме и кассандре

  00:40:12 - 00:41:21

• лишь бы и супом по разным веткам одна из них выбирает consist in сиди там и там другая наоборот там даже закаленных дефолтные настройки про сразу но да ну либо можно их просто адаптировать но в целом дату словно условные кассандрой она станет ходу по которой эти все чаще и чаще случается да хоть я слышал я в одной конторе переходит на ходу в одной конторе из миф о том что когда-то все таки перейдут так history затем когда мы и вот в эту history опять же . да мы записываем то что мы кладем она еще у нас на самолет

  00:40:47 - 00:42:00

• вот так вот выглядит у нас все вся шина через который мы общения правка сервис пишет что вот поиска завершилась либо поездка началась и мы ее как-то хэндом через наш текущая данный либо поиска завершилась положили сюда плюс когда поиска завершилась надо деньги чтобы забрать конева пользователей цель для этого кстати мы опять вспоминаем что она же rdbms и поэтому у нас как бы есть выполняется оказали когда есть денежки как бы это сразу начатое сид и нам надо нам нужно было решено как базу данных которые это

  00:41:25 - 00:42:30

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

  00:41:58 - 00:43:03

• плюс если у нас есть кассандра также может быть у нас есть какие-нибудь доказательства которых мы нанимали и у них скорее все-таки есть какой-то божественный hadoop для того чтобы радикулит аналитику там устанавливается розы родственники выдать его цены безумные придумывать как бы формула для их подсчитывая на основе истории поездок и прочего поэтому мы можем из кафки сразу писать еще куда то здесь может какой-то части ходу по будем считать частью ходу пока он еще может быть парк streaming например в который в

  00:42:30 - 00:43:35

• режиме онлайн чат какой-то анализ проводят что вот на деньги цены поднять что здесь слишком много поездок стала но и в целом месяц как бы ходу кластер то есть х tf слот записывается та же история поездок с кассандрой как бы с более прямым доступом без вот этой всей игры hadoop вычислениями и так далее по ходу контекстами подключение прикрас контекста и прочее у тебя часов нет а я то знаю что одна минута осталась что мы сделали плохо on давай тогда есть одна минута в целом про redundancy доступность вот это все прочее во-первых

  00:43:04 - 00:44:12

• между нашим сервисами клайн facing up у нас всегда есть контент был интер который во первых у нас то что скала из глобальный лот бензин приносит в москве нам нужно в московской через сервис эти с мужа и про парте церовани из любого или самом начале то есть целом нас конь может быть 2 уровне лот beyonce то есть именно сначала ротик куда в нужную этом подсветку в какой местный географически затем уже лот балансы которые стреляют нагрузку можем выбирать зависимости там от того где больше соединений как как

  00:43:41 - 00:44:38

• который там быстрее отвечает где там были какие-то файлы нет и так далее целом между любыми двумя сервисами для максимального как разделение их чтобы каждый из них можно выбирать независимо мы отдельно выставляем лот bouncer и не каждый из них независимо масштабируем в зависимости от того какую нам нагрузку нужно держать для relation баз данных нам нужно иметь как минимум не только как main копию но и оффлайн как бы реплики которые можно было поднять вместо них если что плюс для увеличения readonly нагрузки нам

  00:44:10 - 00:45:14

• нужно добавить больше копий именно readonly копий плюс можем воспользоваться правилом 2086 20 процентов нагрузки как бы вас данных гинер у этого средства нагрузки мы можем исходя из этого поставить перед ним еще тоже это редис каши для ну кассандра соответственно мы выбираем количество там тоже реплики и сортирования просто до плюс для собственного bouncer еще может использовать определить кому нам нужно пойти чтоб мы все время ходили в одно и то же место и какую-то поддерживали вот эти вот соединение прочим можем использовать как

  00:44:42 - 00:45:54

• бы fishing при этом применять кости стенах чтобы приходили все время в одно и то же место из этого и балансире хранит соответственно диапазон дат если там часть отваливается мы используем на качественно чтобы сейчас сервисов отвалилась не стучался к группе перекос нагрузки в какой-то один из наших сервисах так ну стандарт для базы нам нужно резонансе больше копий для доступности и быстрой скорости чтения лот был инсульт перед каждым сервисом каждый сервис независимо масштабируется кафка соответственно тоже там worker и

  00:45:18 - 00:46:20

• масштабируется в зависимости от нагрузки и quot три последние осталось его как мори догнать просто добавляем кучу копии храним то есть у нас есть мини сервису которым собственно только одна штука может вертеться танцоров куберы делаем много кодов есть один из них отвалился тут же переключились на другой как можно посчитали информацию находиться немного то есть это просто дамп нам делать принципе не надо ну то есть какой то просто сервис на головы у нас всегда есть какое-то количество пота в которых которые его поддерживают офиса

  00:45:49 - 00:46:53

• жизнь спасибо большое мне очень понравилось спасибо собственно ну я бы поставил х или стран ха я пожал 1 когда вы поставил эту оценку на этих интервью два момента про которые нужно один момент это мы забыли но потом вспомнили с подсказкой что в код 3 нужно еще учитывать и айдишники но этот индастриал обсудили именно как найти враги шарманку же побежали не учли это потому что у нас от этого могло сильно поменяться благо айдишники немного места занимали но если бы они занимались словно не 40 мегабайт

  00:46:21 - 00:47:28

• и 400 гигабайт уже было бы возможно другое решение и паст момент который часто забывают о нужно сайт и он очень простой мониторинг мониторинг сервиса то есть бордель grafana либо равен графа ну следим за такими то метриками gps перцентиле все такая полировка так все отлично какие базы данных asset как redundancy делать а вот три сожалению тайминг в голове не держалась на это тяжело том что обычно когда ты проводишь свои часы с модели с что-либо в углу в три ноты откровенно говоря около укладывался то есть ты про все

  00:46:54 - 00:48:12

• рассказал покрыла 3-дан дэнси написал функциональные требования на функционирование кажется мы чуть больше уже не потратили чем нужно было то есть например уже можно было сказать так значит про рейтинге проще не говорим вот борьба за базовый функционал уж на это ушло на минут наверно 78 тусит хороший подход ну вот я бы на 3 функционал функционально устраивайте мы функциональность у меня бы устроило честно говорят на на третьем потому что мы видишь мы все равно не нашли не дошли даже до рейтинга то есть мы дальше

  00:47:35 - 00:48:27

• скажем мы можем накручивать сюда ну она даст как бы накидывать свечей который тебя прямо сейчас приходят голову на потому церовани хватит время папа всем пунктами дара годится каждый зале хочу покрыть из моего опыта фейсбуке но обычно у тебя тоже был опыт фейсбуке положительный они таки не значит кафка так system design спрашивает а я нет никакого кафка вид что такое кафка message broker все понимаю но я в свою защиту писал на слайдах именно прим просто whirlwind босую а еще там же теперь лучше не

  00:48:01 - 00:49:09

• говорить про мастерски но это пропарим праймари секунды доложны были все те говорят masters life уверяю по прежнему крайне редко но мне нечего сок добавить то есть никакого разбора я не вижу смысла здесь делать понять что дальше можно углубляться как ranking тоже туда праве парк stream но эта вещь весьма лет а вот эту сторону добавляем еще одну стрелочку нагружено эрнольд system design нужно еще нужно квадратик собственно ты сказал основное упущенные квадрате график хана и куча куча стрелы к из него

  00:48:35 - 00:49:45

• таскать есть графа нам и оттуда кидаем неважно чем не очень понравилось у меня вопросов нет здесь вопрос что-то обсудить я думаю что вы забыли вопрос где мы будем есть стоит спасибо 7

  00:49:10 - 00:49:41