Maps.me. Как упаковать мир в телефон

Всем привет! Меня зовут Самат Галимов, и это подкаст «Запуск завтра». Как технический директор я пытаюсь разобраться, как устроены сложные и интересные штуки. Я зову профессионалов, с которыми можно поговорить простым человеческим языком. Дорогие друзья, ставьте нам, пожалуйста, звездочки в приложении Apple Podcasts и пишите комментарии. Это поможет найти подкаст новым слушателям. Для нас это очень важно. Сегодня я буду говорить о картах в мобильном телефоне. Сегодня эту технологию легко не заметить, потому что приложения карт есть у всех крупных производителей, у Apple, Google, Яндекса, у каждого. При этом гость нашего подкаста Юрий Мельничек 10 лет назад с командой ребят из Беларуси сделал то, чего не умели делать ни одни мобильные карты. Он смог запихнуть карты в память мобильного телефона так, что они работали без интернета. Сегодня я хочу разобраться. как поместить карты внутрь мобильного телефона и как сделать так, чтобы они работали без интернета. Это подкаст студии «Либо/Либо», и мы его делаем вместе с сервисом онлайн-образования «Яндекс.Практикум». У «Практикума» есть курсы по разработке, по анализу данных и по английскому языку. Если вы хотите освоить цифровую профессию, переходите на сайт «Яндекс.Практикум» и учитесь. А еще, если вы хотите вспомнить курсы школьной математики, а точнее самые базовые вещи, вроде того, как складывать дроби или как быстро считать в уме, ссылку положу в описании к этому эпизоду. Переходите на специальный математический тренажер, который сделал «Практикум», и можете освежить эти знания.

Всем привет, меня зовут Юра Мельничек, я программист из Беларуси. Когда-то вместе с товарищами сделал приложение Maps.me, потом его купила компания Mail.Ru Group и сделала open source, потом мы делали с другими уже друзьями компанию, которая занималась нейронными сетями, и ее в итоге купил Google Research. И теперь я в вырученные деньги инвестирую в различные Machine Learning стартапы.

Офигеть! То есть я сейчас вот созваниваюсь с человеком, который придумал Maps.me.

Я бы не атрибутировал на 100% себе придумал Maps.me, но вот, короче, когда я пришел с идеей Maps.me к одному из своих кофаундеров, он сказал, слушай, Юра, вот у меня были вообще очень-очень похожие идеи, прям очень сильно резонирует, вот, потом мы… еще пришли к паре куфаундеров, и вот так все началось. Так что мне кажется, что это скорее мысли, тенденции, они витают в воздухе, и вот я их уловил тогда на заре, когда только появился iPhone.

Ты помнишь вообще 2011 год? Как тебе пришла эта идея в голову?

В 2011 году в СМИ уже появилась первая версия, а была еще работа над ней. В какой-то момент я ушел в отпуск, и набросали с друзьями прототип. Это даже было не приложение. И эта история у нас называлась OMIM. И до сих пор репозиторий называется OMIM. И это такая у нас внутренняя шутка, потому что OMIM значил «One month in Minsk». Вот мы собрались на один месяц в Минске, и все к этому относились, что это мы собрались на такой хакатон. Никто тогда не знал, что месячный хакатон «Один месяц в Минске» закончится годами разработки.

Почему вы после этого месяца поняли, что надо увольняться с работы и начинать этим заниматься? Что там произошло в этом месяце?

Я тогда работал еще в гугле, и было несколько проблем с гугл мэпсами. Одна из них была в том, что Беларусь тогда была представлена только двумя дорогами и государственной границей, а я сам из Беларуси, мне хотелось, чтобы для Беларуси была красивая карта, вот всё такое. А вторая вещь, вот как я тогда по тем временам про это думал, что вот карта мне нужна, когда я вот иду где-то, где я, скорее всего, никогда не был, и там может быть что угодно. Например, там может не быть интернета. Поэтому было бы круто, чтобы карта была как бумажная карта, которую, если что, всегда можно достать и с ней свериться. Мы взяли очень-очень маленький кусочек Минска, где есть железнодорожный вокзал, дорога, здания, то есть где были такие очень разнообразные объекты, супермаленький кусочек вокруг центрального вокзала, и мы сделали какой-то очень маленький прототип, который его начал рисовать. Сделав этот прототип, мы поняли, что, блин, можно сделать приложение, его можно рисовать с телефона. Просто тогда идея MapsMe оказалась немножко безумием. что все рисуют карты на серверах, и уже на телефон приходит просто картинка, как фотография, просто картинка карты.

То есть вся информация хранится на сервере Google или Яндекса, а приложение – это просто показывает тебе информацию, которую получил по интернету.

Да, это такой браузер картинок. Если мы просматриваем карту, то карта из данных рисуется на серверах, а в самом приложении мы просто просматриваем картинки. Когда мы делаем поиск по карте, мы пишем запрос, этот запрос отправляется на сервер. На самом деле на которые там друг с другом работают, обмениваются информацией. они там находят лучшие результаты и возвращают назад. Тогда была такая модель, а все это делать на супер-супер маленьком, медленно маломощном телефоне казалось безумием. И в этом смысле Maps.me попала в контртренд и оказалась права. У Питера Тиля (Peter Thiel), что если вы считаете, что весь мир или большинство мира ошибаются, а вот вы правы, и вдруг оказывается, что это действительно так, то это хорошее основание, чтобы из этого построить стартап-бизнес.

И заработать кучу денег.

И мы решили увольняться с работы и нормально собираться.

Юра говорит о том, что в те годы и Яндекс, и Google хранили данные о мире на своих серверах и обрабатывали их там, а на телефон прислали только готовые картинки, карт, фотографии. И Юра же своими друзьями решил сделать невозможное и хранить, и обрабатывать карты прямо на телефоне. хочу с тобой поговорить про основу. Вот я достаю телефон, открываю там Яндекс карты, Google карты или то же самое Maps.me и вижу, где я нахожусь и что есть рядом. Откуда берется эта информация?

У Google берется из их источников данных, у Яндекса из их источников данных, у Maps.me из OpenStreetMap. Обычно, что делают поставщики карт, обычно они покупают данные от очень-очень многих провайдеров, объединяют, как-то склеивают, сшивают их вместе.

А у них они откуда берутся, у других провайдеров, у поставщиков карт?

Я сейчас не уверен на 100%, но мне кажется, что какие-то поставщики выросли из каких-то государственных картографий, Как развивался этот рынок, были какие-то ребята, которые как-то агрегировали в себе карты до появления вот этих вот интернет-карт массовых. Они продавали по тому, кому нужно, тому и продавали вот эти данные. Некоторые города, сейчас это все более и более часто, но вот на момент появления Maps.me это была достаточно редкая история, что некоторые города считают, что карта города должна быть в паблик-домейн, то есть она должна быть в общем доступе, и любой человек может воспользоваться этими данными.

Прикольно.

Зачастую в последние годы группные карты стали сами собирать свои данные. Сейчас, наверное, модно это делать из машин, которые снимают съемку street view, то есть снимают панорамные карты улицы, и оттуда распознаванием, компьютерным зрением можно вытащить название магазинов. Есть концепция, допустим, как у DoubleGIS, 2GIS. У них есть прям огромная армия людей, которые ходят руками и редактируют карту, заходят в бизнес, разговаривают с бизнесами, и заодно продают услуги DoubleGIS. И есть OpenStreetMap. Это такая, как Википедия, но в мире карт. Это сообщество, где люди, энтузиасты, вот мы все вместе рисуем карту мира, где мы живем. Ну как бы вообще в целом знание мира, в котором мы находимся, оно не должно принадлежать какому-то человеку или какой-то компании. Это очень важный аспект вот с точки зрения цивилизации, чтобы это знание было доступно всем. Вот как Википедия про то, чтобы знание, как устроен наш мир и что в нем было раньше, было общедоступным. Вот также OpenStreetMap – это знание про то, какой наш мир, где что находится, чтобы оно было общедоступным. И мне кажется, что это чрезвычайно важно.

Ты много рассказывал о OpenStreetMap. Можешь немножко рассказать, насколько это большое сообщество, как оно функционирует, сколько там людей? Можешь немножко про OpenStreetMap рассказать?

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

Это по всему миру или только в каких-то странах сообщества?

Сообщество глобальное, но я думаю, уверен, что можно посмотреть разрез по странам тоже.

Ну, я имею в виду, это не какая-то локальная только русская или только американская история.

Нет, это глобальная история.

Как ты придумал взять данные именно OpenStreetMap для Maps.me?

Ну, мне это было очевидно, потому что на них Беларусь детально нарисована. А потом оказалось, что не только Беларусь. Но, с другой стороны, мы, когда начинали работать над Maps.me, мы посмотрели, что по плотности географической информации Беларусь уступала только Японии.

Ничего себе!

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

Офигеть! Круто! Юра, а как берется… вот просто открываю карту, и там прямоугольнички здания. Вот эти прямоугольнички откуда они появляются? Кто их рисует руками? Или они не руками рисуются?

Их рисуют энтузиасты. Если говорить про именно прямоугольнички зданий, то большая часть из них появилась за счет того, что Microsoft и Yahoo, и, возможно, уже какие-то другие провайдеры спутниковых снимков, Они сказали, ребят, вот мы вообще очень верим в концепцию OpenStreetMap, поэтому берите наши спутниковые снимки и по ним рисуйте карты. Соответственно, контур здания сейчас зачастую просто появляется из спутниковых данных. В редких случаях, когда нет спутниковых снимков в той местности, человек может прийти с телефоном, GPS в телефонах очень точный, можно просто узнать координаты углов зданий.

То есть буквально обойти ногами здание и записать координаты?

Можно сделать так. Его не надо обходить, можно просто координаты углов записать. Зачастую, если есть какая-то подоснова, например, есть дороги и есть пешеходный переход, то можно примерно спозиционировать углы здания и здания примерно спозиционировать относительно той карты, которая уже есть. Есть еще один суперинтересный юзкейс, про который могу рассказать. Это когда происходит какое-то бедствие, например, ураган или, допустим, землетрясение, и получается, что огромное количество домов разрушено, и большой спрос в работе спасателей. Зачастую происходит следующая штука. Компании, которые владеют спутниками, они ближайший пролет спутника фотографируют эти места и выкладывают спутниковые фотографии высокого разрешения в общий доступ. После этого OpenStreetMap Humanitarian Team, команда специально создающаяся для этих вопросов, они быстро-быстро-быстро строят карту и фактически зачастую через сутки у спасателей есть уже супер детальное, супер актуальное.

Типа тропиночки все, и вот вообще все-все-все.

Тропиночки, разрушения, бедствия, завалы. И потом, когда вот это происходит, в таких местах обычно дальше вырастает OpenStreetMap Community, и дальше уже поддерживать детальную карту таких мест становится проще, чем как бы создавать с нуля, и вот как бы так запускается сообщество. Такое иногда бывает.

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

Самый простой маршрут, скорее, это пешеходный маршрут. Вообще, мы когда запускали навигацию, у нас была такая концепция, первой мы делали вертолетную навигацию.

Ты просто от точки в точку, да?

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

Почему пешеходные маршруты? Почему они проще, чем автомобильные?

Потому что они на маленькое расстояние.

А, вот, теперь понятно. Потому что я вряд ли буду ходить пешком из Москвы в Берлин.

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

А построение маршрутов— это задача, в которой нужно обработать огромный массив данных. Чем длиннее этот маршрут, тем данных больше. Google и Яндексу очень просто. Какие бы огромные данные ни были, они все равно поместятся на их бесконечно большие сервера, серверные фермы. Юре же нужно было совершить все эти операции внутри телефона, поэтому понятно, что проще начать с коротких маршрутов, пешеходных, а не с длинных автомобильных. Слушай, а он считал все маршруты прямо на телефоне, да? Не запрашивал никаких данных из сервера?

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

Расскажи, пожалуйста, как подготавливаются. У меня первая гипотеза— это про то, что направление дорог нужно знать. Типа, в какую сторону можно ехать, в какую сторону нельзя. Это про это или что-то более сложное?

Ну, в какую сторону ехать можно, в какую нельзя— это как бы важно и для отрисовки карты, потому что вот если посмотреть на карту... Стрелочки надо рисовать. Да, стрелочки надо рисовать. То есть вот как раз-таки все такого рода вещи, они есть и так в карте. Есть очень много разных интересных подходов к построению навигации автомобильной, к прокладыванию маршрутов. Нашим ограничением было, мы хотели, чтобы это работало очень быстро и занимало мало мест. И для этого есть такой подход, условно говоря, когда берется граф дороги, то есть берутся все связи между всеми точками на дороге, И из этого всего выделяются те маршруты, которые... Там происходит достаточно хитрая трансформация этого графа, которая больше всего, вот если так образно поговорить, похожа на то, что выделяются быстрые дороги, супербыстрые дороги, там, автострады, и тогда дальше, образно говоря, маршрут строится, как сначала строится маршрут по автострадам, потом по, условно, городским дорогам, потом по маленьким улочкам. Это такое метафорическое описание, на самом деле, очень формального алгоритма, который не использует классификацию дорог официальную, а вот в ходе обработки данных он сам, в зависимости от скоростных режимов на дорогах, и взаимного расположения с другими дорогами, он сам У тебя

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

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

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

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

на сервере, чтобы это все посчитать, построить схему?

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

Подожди, но на телефоне их точно нет.

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

Вот. Вау. И ты типа прямо блок загружаешь в оперативную память, и потом с этим блоком можешь быстро работать?

Ну да, типа того, где на внутреннем уровне там есть кэш.

Задача поиска кратчайшего маршрута— это вообще классическая задача компьютерных наук. То есть люди 50 лет пытаются ее оптимально решить. Дело в том, что идеального алгоритма (точного алгоритма), который бы идеально решал эту задачу, не существует. Существуют различные приемчики, которые позволяют решить ее достаточно хорошо. Так вот, проблема в том, что на таких объемах данных искать кратчайший маршрут— это Очень-очень-очень дорогая операция. Тебе для этого нужны сервера с огромными объемами оперативной памяти, с большими жесткими дисками, с мощными процессорами. А телефон— это штучка, в которой мало памяти, да еще и батарейка есть, то есть нужно энергии мало тратить. А чем больше работает процессор, тем больше энергии он тратит. В общем, Юрий применил довольно хитрую математику, алгоритмистику для того, чтобы сначала найти вообще хороший алгоритм поиска кратчайшего пути. А дальше применил супер крутые хаки, именно уже программистские штучки, которые позволили этот алгоритм еще и сжать и сделать их энергоэффективным.

Ну и в целом это не что-то уникальное для нас про построение маршрутов. Это вот все MapsMe. Вот все MapsMe, оно очень сильно про сжатие данных. Очень-очень-очень сильно про сжатие данных. Причем не абы какое сжатие данных, а сжатие данных так, чтобы, во-первых, было то, что программисты называют random access. Когда я пакую файлы zip-ом или rar-ом, или другим архиватором, мне, чтобы один файлик вытащить, мне нужно распаковать обычно весь архив. Некоторые архиваторы дают опцию распаковывать файлики независимо.

Но всё равно в фоне они обычно под капотом всё равно всё распаковывают.

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

То есть Maps.me нужно было решить три задачи одновременно. Во-первых, нужно было очень сильно сжать данные. Это, в принципе, нормальная задача, вы наверняка сами сжимали файлы zip. Вторая проблема уже сложнее. Вы когда создаете архив, потом его распаковываете целиком, все файлы из него вынимаете. Maps.me же нужно было научиться вытаскивать только один файл из середины архива. Это гораздо сложнее. Третья проблема еще сложнее. Нужно было делать все это внутри памяти мобильного телефона. А память мобильного телефона очень-очень медленная. Слушай, это три требования, которые противоречат друг другу. Сделать такое невозможно.

На самом деле не так уж они и противоречат. Мы когда начали это делать, потом оказалось, что есть такая целая область математики, информатики, которая по-английски называется succinct data structures. Это условно структуры данных, которые изначально сжаты. и которая лишь чуть больше теоретического минимума, необходимого для представления той информации, которая сжата. И это как бы доказывается. И более того, там есть своя алгебра операций, и из этой своей алгебры операций оказывается, что там запросы, например, на поиск, они переписываются вот в алгебру этих операций. Есть библиотеки, которые... позволяют сжимать, разжимать и выполнять вот эти операции из алгебры операций. И это вообще оказалась целая очень красивая область математики, которую почему-то мало кто знает.

Я тут маме должен пояснить. Обычно, когда мы говорим о программировании, мы обсуждаем, типа, как кнопочку поставить и сделать так, чтобы 300 программистов друг другу на ноги не заступали, когда они спрогаивают. А Юра впервые, наверное, в этом подкасте рассказывает о таком красивом программировании, умном. Пользуясь словом алгебра операций, это вообще математика. Это про то, что у тебя есть так называемые пространства специальные, и в них ты вводишь специальные правила. То есть это прямо такое чертоги разума. Обалдеть.

Да, и удивительно, что это вообще абсолютно новая на тот момент была область, то есть ей не было и 10 лет. Вот что такое 10 лет для математики?

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

Могу, если интересно, рассказать в формате для мамы про что это.

Расскажи, пожалуйста.

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

Это поиск, наверное, и добавление.

Скажем так, изначально эти структуры, они только для чтения. То есть весь процесс происходит следующим образом. Maps.me скачивает гигантский файл, который представляет все данные для всей планеты. Maps.me не как приложение, а как вот…

Сервис.

Как сервис, да. Мы периодически его скачивали.

Слушай, сколько он весит? Сотни гигабайт? Десятки гигабайт?

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

Вылавливать то, что тебе надо.

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

Очень красиво.

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

Вопрос родился из того, что сказал, что есть базовые операции. Какие базовые операции?

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

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

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

но при этом вы хорошо понимали математику под капотом.

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

Хотя земля вообще-то шар, тебе нужно шар разложить в плоскости, и это типа не так просто, как может показаться.

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

Как нарезать квадратную карту на ленту так, чтобы по ним было удобно перемещаться? Вверх и вниз, например, не только влево-вправо.

Удобство— это последнее, о чем мы думали.

Окей, я перефразирую слово «удобно». Вообще возможно.

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

О, блин, это совершенно нетривиально.

Обычно делается так, обычно строится так называемая заполняющая плоскость двухмерная кривая. Вот можно погуглить безумно красивые картинки кривой Гильберта.

Как она называется еще раз?

Есть кривая Гильберта, которую мы не использовали. и есть кривая Z-curve называется, кривая Z.

Я открыл сейчас картинку, господи, как это красиво. Это про то, как рисуя карандашиком линию одну непрерывную, закрасить.

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

Когда мы берем телевизор или экран монитора, то у нас вот эта двухмерная наша картинка, она построчна. Типа строка и в ней все столбцы, потом следующая строка, следующая, следующая. В Maps.me так делать нельзя, потому что тебе нужно, чтобы вот если это представить как длинную ленту, получится, что два пикселя, которые сверху и снизу на двух разных строках, но на одном столбце, они получатся очень далеко друг от друга на этой ленте, если это все разложить в ленту. Нужно, чтобы они были близко.

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

потому что сжатие работает только если у тебя есть смысл в этих данных, структура есть какая-то, типа что кучкуются данные вместе.

Да, и в целом то, как работает сжатие в Maps, можно представить как то, что есть какая-то модель, которая всегда предсказывает, что будет дальше, и мы никогда не храним, что будет дальше, мы всегда храним разницу между тем, что мы предсказали, и тем, что было на самом деле.

Офигенно круто!

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

Ага, и ты не смог бы просто их быстро вытащить даже для того, чтобы нарисовать.

Да, построчная развёртка, просто нам бы столько чтений с флешки было, что мы бы не успели данные нарисовать, даже если бы объём их был нам не важен.

Охренеть! Юра, когда я планировал записать этот эпизод, я думал, что все будет очень просто. Типа, где мы берем данные, как мы их рисуем, как на этом деньги зарабатывать. Мы сейчас говорим о теоретических ограничениях того, как сильно можно сжать данные. То есть мы приближаемся вообще к каким-то физическим пределам мира. Охренеть! И все это для того, чтобы у нас карты работали. Слушай, как вы придумали, как вы до этого догадались вообще, что для того, чтобы сделать карту, нужна вот такая математика? Вы делали сначала в лоб, и потом, что ничего не получается? Или вы сразу знали, что это такая сложная задача?

Я работал в очень похожей области в Минске в компании Credo Dialog. После этого я работал в Гугле в поиске по карте. При этом у меня был 20-процентный проект по сжатию данных.

В Гугле есть такая штука, что 20% времени раньше программисты могли тратить на те проекты, которые им нравятся. У Google Mail так появился Gmail.

Да, и вот мой менеджер, не мог мой 20-процентный проект закрыть, но он меня всегда убеждал, Юра, Юра, что ты делаешь? Нашим сервисом пользуется миллиард людей. Какое сжатие данных? Ты вот делаешь небольшое изменение в качестве поиска, миллиарду человек становится лучше. Зачем тебе 20% тратить на свое сжатие данных? Давай, вот.

Но у него не было власти просто закрыть проект, поэтому ты продолжал заниматься сжатием.

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

Они сэкономили миллионы долларов просто.

И это примерно было как раз когда я... Прям незадолго до того, как я уволился из Google и пошел делать Maps.me.

Очень-очень интересно. Разговор с Юрой мы записали год назад. Мы очень много раз редактировали этот эпизод. Дело в том, что именно исходник этого разговора был тестовым заданием для младшего редактора нашего подкаста. Редактор подкаста Юля прослушала, мне кажется, 40 версий этого эпизода. Надеюсь, что результат вам понравился. Когда я задумывал этот эпизод, я собирался поговорить с Юрой про деньги. Как зарабатывать деньги на картах? Они же все бесплатные. Почему Юра продал свою компанию Mail.ru? К чему это привело? И вообще, чем он сейчас занимается? В результате, когда мы начали разговор, стало понятно, что технологии в картах гораздо более сложные, чем я себе это представлял, и гораздо более интересные. И мы проговорили про них огромное количество времени, и вот вы сейчас это все прослушали. Про деньги мы, конечно, с Юрой потом тоже поговорили. Дальше перед редакторами стала очень трудная задача. Как сделать из вот этого длинного разговора один емкий эпизод «Запуск завтра», в котором есть и про технологии, и про бизнес, как у нас обычно? Мы решили в этот раз провести эксперимент. Вместо того, чтобы попытаться умести все это в наш обычный эпизод, мы выпустим разговор про бизнес с Юрой завтра в нашем канале «Запуск плюс плюс». Доступ к нему стоит денег. Вы можете подписаться либо в приложении Apple Podcast, если у вас последняя версия iOS, либо на нашей странице в Patreon. Ссылка на Patreon есть в описании к этому эпизоду. Подключайтесь и слушайте. Разговор не менее интересный, чем сегодняшний про технологии. Давай подведем итог, во-первых, тому, о чем мы разговаривали. Я правильно понимаю, что когда ты делал Maps.me, было три задачи. Первая— это взять данные, вы их взяли готовые в OpenStreetMap. Вторая— нужно было их сжать супер-супер сильно. А третья— нужно было их красиво отрисовать.

Да, это очень-очень хорошее краткое описание. Я не готов ответить, какая часть была самая сложная, но точно для меня лично самая интересная была про то, как эти данные сжать.

У нас ещё есть один вопрос, который мы задаём всем гостям. Что ты читаешь в интернете? Ну, не обязательно читаешь, может, слушаешь или смотришь.

Из каких-то профессиональных штук. Мне очень нравится канал Denis Sexy IT, который про компьютерное зрение. Я очень люблю компьютер, компьютерное зрение. Ещё несколько других таких нишевых каналов, «Гонзо-обзоры ML статей» мне нравятся. И «Loss function porn». Но это ML-каналы, которые я читаю.

Хорошо, ссылку на них положу в описании эпизода.