К летней Олимпиаде 2016 года в Рио-де-Жанейро Яндекс подготовил сразу несколько проектов. В том числе — «Карту болельщика». Вы могли отметить свой город на карте, которая отображалась на главной странице Яндекса. Чем больше отметок от жителей города мы получали, тем ярче горел его огонёк.
На одном из Я.Субботников руководитель группы интерфейсов главной страницы Яндекса Иван Карев объяснил, как создавалась эта карта.
— Меня зовут Иван Карев. В Яндексе я делаю главную страницу и разные спецпроекты. Хочу рассказать об одном из них. Это такая история из жизни разработчиков — о том, какая еще бывает работа.
Спецпроекты на Яндексе, может, вы видели. Можно зайти на главную страницу, нажать на логотип, у вас потом в полном экране что-нибудь откроется и будет красиво показываться. Они работают на десктопах, тачах, планшетах по-разному, может что-то сразу показываться. Они специфические. Кто-то видел спецпроект для карты Олимпиады в Рио? А кто-то видел спецпроект про Гагарина? Не очень много. Рассказ будет примерно про это.
Летом прошлого года к нам пришли и сказали, что мы хотим сделать в поддержку нашей сборной карту, где люди, которые заходят на Яндекс, могли бы как-то отправить лучи поддержки. И там должна быть какая-то интерактивная карта, где видно, кто и сколько проголосовал, и чтобы каждый человек мог своим голосом поделиться.
Про нее ничего не было понятно, это был концепт. О нем было известно, что он должен быть красивым, что бы в это слово ни вкладывалось. Кроме того, он должен был отображать реальные данные людей — можно было сделать по-другому, но мы хотели сделать хорошо. И он должен был работать на десктопах, тачах, планшетах, разных девайсах. Возможно, даже с разной логикой.
Первый вопрос был в том, что мы не знаем, что мы хотим сделать. Должно быть красиво, должна быть карта с поддержкой. Обычно, когда приносят макет, вы смотрите, примерно оцениваете функциональность и думаете, как это можно сделать. А здесь наоборот: к нам пришли дизайнеры и сказали: «А что вы можете сделать?». Мы сказали: «Если вы хотите это — можно так». Мы бросали мячик туда-обратно, долго смотрели разные демки, показывали, что мы умеем, что можно сделать быстро, что не быстро. Общались, спрашивали, за какое-то время договорились.
Что мы могли предложить дизайнерам в качестве реализации? У нас есть всякие картографические движки. Яндекс.Карты — вообще движок про карты. Есть движки, где что-то можно рисовать на карте. Их очень много, я привел Carto, потому что у нас он кем-то был упомянут и рассматривался.
Либо есть просто JS-библиотеки, где можно вручную рисовать все, что хочешь. Принципиально svg/canvas — в зависимости от дизайна можно было выбрать либо то, либо другое. Есть куча готовых решений, куча демок. Мы примерно отсматривали, что можно было взять. Шла довольно интересная работа, но к сожалению, было не очень много времени, приходилось укладываться.
Что в итоге получили? Был такой концепт. Вот карта, она вроде бы плоская, на ней есть кружочки разного размера и прозрачности. Тут можно с помощью разных вещей это реализовывать.
Потом был такой концепт. На движке Carto реализована карта болельщиков футбольного клуба «Реал Мадрид», показывающая, как они голосуют в Твиттере. Тоже плоская карта, здесь сильно больше точек, какие-то градиенты с прозрачностью. Вроде похоже на canvas, может, svg, пока тоже не очень понятно.
Пошли смотреть, что есть у нас на Яндекс.Картах. В них есть модуль Heatmap, даже была такая демка собрана, тоже карта с подложкой, на ней много точек, они разного цвета. Что-то, кажется, тоже можно из этого попробовать сделать.
Потом был такой дизайн. Здесь точек гораздо больше, у них какая-то прозрачность. Это тоже на уровне концепта было.
Даже такую штуку нашли, прикольная демка из уроков Proper GL (название может быть неточным — прим. ред.), где можно взять настоящую Землю со всякими текстурами, красивыми шейдерами, она круто вращается. Тоже хотелось, очень красиво. Всем очень нравилось, но мы всех убеждали, что нет, это мы так показали, но делать так не будем — далеко не все компьютеры могут вообще это выдержать, тяжелая штука.
В итоге родился примерно такой макет, один из таких концептов. Плоская карта, где есть специальная раскрашенная подложка и есть бурление в виде точек, они разноцветные, переливающиеся друг в друга. В тот момент пришло понимание, что перед нами скорее уже не svg, а canvas.
От карт тут то, что текущая точка нахождения человека привязывалась к этой карте. Показано, где ты, а где кто-то еще.
В итоге мы решили делать это на Яндекс.Картах, используя модуль Heatmap. Мэпа, уже тогда готовая в демках такого, конечно, не умела делать, но мы с разработчиками пообщались и поняли, что это возможно. Стали пилить дальше.
Вот начало. Нам надо было сделать подложку.
На самом деле это творческое занятие. Подложка тоже бывает разная. Здесь она плоская, всего двух цветов. Россия выделена одним цветом. Есть территориальные границы государств в Яндекс.Картах, есть модуль регионов, который рисует эту подложку в виде svg. Там можно выбрать степень детализации, в зависимости от нее svg будет весить больше или меньше. При этом она довольно долго рисуется, и каждый раз ее загружать было довольно странно, если учесть, что подложка одна и та же. Плюс мы решили, что нужны не все подряд уровни зумов, а только какие-то верхние. Так что мы внезапно сделали то ж самое, но только на тайлах. Карта России серого цвета на черном фоне.
Можно взять модуль полигонов, модуль регионов, сделать большой скриншот, и через простой Image Magic разрезать все на тайлики, которые будут точно так же отображаться.
Самый интересный вопрос был с данными. Нам нужно было принимать голоса людей. Нам очень хотелось их показывать в реальном времени — чтобы общее количество точек, которые нажимают люди, с течением времени изменялось, чтобы был виден прогресс, было видно, что что-то происходит.
Может, я и параноик, но вот первый вопрос, который пришел мне в голову: если нам отдать наружу какую-то штуку, которая умеет принимать координаты и по ним что-то рисовать, то примерно через полчаса у нас будет поперек всей карты какое-нибудь слово «Привет» написанное с помощью геокоординат. Это легко делается. И такая мысль засела, и хотелось сделать все так, чтобы у нас не было необходимости вручную отсматривать все, что на этой карте происходит. Поэтому возник и вопрос, как сделать модерацию, причем времени было не очень много. Конечно, не хотелось заново что-то поднимать и отслеживать по ночам, что там происходит. Тяжело было.
Еще нам хотелось, чтобы внешний вид карты был прогнозируемый и понятный. Нужна была возможность прикидывать, что там вообще может быть. Люди могут голосовать в разных местах, но нам бы примерно понимать, в каких и как это будет выглядеть.
В итоге после каких-то обдумываний у нас появилась следующая архитектура. Мы решили взять большой список точек, назвали его белым списком. Речь идет про те места, где люди в принципе могут голосовать. Мы будем включать только какие-то точки. Вопрос только один — как их взять. Естественно, их должно быть много, но мы ничего другого не включаем. Каждый клик по карте ищет ближайшую точку из белого списка, и какой-то счетчик увеличивается. Была большая база со всеми возможными координатами точек. Мы увеличивали счетчики и, чтобы рисовать на карте, показывали это в простой логарифмической шкале. Так что некие накрутки и перепады были не видны.
Вопрос, как сделать белый список точек. У нас же люди на главную страницу и так заходят — давайте посмотрим на эти заходы и из них возьмем те геолокации и координации, которые есть в перечисленных запросах.
Есть два типа координат. Координаты первого типа вычисляются по IP с привязкой городов. Мы можем взять все заходы, координаты, выбрать какой-то уровень, например всё до уровня города, а дальше у каждого города по его названию и ID взять соответствующие ему географические координаты, геокодировать их и получить список заранее. Он не очень большой. У нас городов в России и округе не миллионы, а тысячи, десятки тысяч.
Второе — самое интересное. Требовалось брать реальные координаты от пользователей. То, что у человека разрешено как геолокация. Можно попробовать эти данные собрать, как-то структурировать и сгруппировать. При кликах, когда человек говорил, что хочет поддержать сборную, мы спрашивали в телефоне геолокацию — на мобилке она почти везде есть — и запросы отправлялись уже с правильным местоположением. Она уже относительно точная, и происходить это могло где угодно: в чистом поле, вдоль дорог, на дачах.
Вот то, что мы получили по геокодированию. Если кто-то помнит географию и может примерно оценить, где заканчивается Россия, то она заканчивается ровно там, где начинаются желтые точки. На самом деле здесь подсвечена Европа. Так получилось, что в России плотность городов поменьше, чем в Европе. Здесь мы брали координаты с точностью до города. И у всех точек радиус единичный. Получается, в России голосовать негде, а какие-то люди в Европе и в Турции — мы там внезапно тоже есть — они как будто начнут составлять большую часть нашего электората. Не очень правильная картина. Поэтому все надежды были на то, что координаты нам дадут что-то хорошее.
Так мы получали координаты по географической сетке. Есть координаты, мы их округляем до какого-нибудь знака после запятой — можем брать сетку в один градус, в полградуса, в одну десятую градуса. Перед вами простой код на MapReduce, который координаты в кластера складывает. В этом его прелесть. Сколько бы у вас ни было координат, можно с помощью простых параллельных вычислений их все сгруппировать и получить. У вас есть квадрат, вы все квадраты сжимаете в один уголок, и количество точек в этом уголочке растет в зависимости от того, сколько точек было в этом квадрате. Получается сетка. Вопрос в том, какой шаг для сетки вы берете. Можно брать с точностью до градуса, до одной десятой градуса и т. д.
Чем точнее координаты вы получаете, тем больше у вас точек.
Получилось нечто похожее на то, что есть в России. Здесь видно облако точек где-то в центральной части, в районе Москвы, Подмосковья. Сочи очень длинное. И дальше по Сибири, Питер и немножко Европа. Уже больше похоже на правду.
Эта картинка получена путем кластеризации по одному градусу. Точек получается очень много, и все точки сразу нельзя отобразить на карте. Решили выбрать какой-то порог. Отрезали так, чтобы суммарное число оставшихся точек было порядка 5000.
Мы потеряли довольно много информации, просто отбросив некое количество точек, у которых по одному-два значения в яркости.
Если взять больше точек, получится следующая картинка.
Здесь с помощью Heatmap нарисована карта. Группировка та же самая, но отображено уже 50 тыс. точек. Видно, что картинка получается более живая, в ней много всего, вот все наши люди, вот они ровно по всей России. Все здорово — кроме двух проблем. В первую очередь, у нас 50 тыс. точек. Не каждый браузер справится с такой нагрузкой, и получив такую красивую картинку, отдавать ее всем мы бы не стали. Плюс это какое-то приличное число данных, передаваемое по сети.
Второе. Картинка получена методом кластеризации по сетке, и эта сетка видна. Мы от нее не избавимся никак. Мы можем уменьшать эту сетку, но тогда точек будет еще больше. Получается нерешаемая дилемма. Понятно, чт в чистом виде эта штука использоваться не может.
В итоге пришли к другой схеме. Мы использовали не один подход, а их комбинацию, кластеризацию. Взяли большое количество точек, порядка миллиарда. Это просто заходы на главную страницу, откуда мы взяли только координаты. Там нет ничего. Нам нужны были просто факты заходов в штуках.
Дальше применили кластеризацию по сетке, получили из миллиардов всего лишь сотни тысяч. Можно было больше или меньше, не принципиально. Дальше их надо было сгруппировать в кластера с помощью какого-то хитрого алгоритма. Есть целая теория, кластеризация, не буду подробно рассказывать. Есть алгоритмы, которые позволяют по массивам точек с координатами выделить их кластера, центры кластеров. Но у них много разных ограничений, они не готовы переварить слишком большое количество точек. Такое можно сделать с помощью локальных данных, а не распределенными вычислениями. Под распределенные штуки эти алгоритмы не найти, а делать их заново тоже не хотелось. Поэтому выбрали тот, который смог это сделать: MiniBatchKMeans. Это метод ближайших соседей с доработками, позволяющий на сотнях тысяч точек за вменяемое время добиться кластеризации до какого-то количества, которое мы в принципе можем показать на клиенте. Мы выбрали около 10 тыс. точек.
Здесь уже видно, что мы получили картину, в которой при любом зуме нет никаких следов сетки. Они сгруппированы по кластерам, но уже без перечисленных недостатков. Здесь довольно мало точек, и получается довольно интересная картинка. Так в итоге и решили делать.
В итоге мы получили сначала список из координат, а затем, объединив его со списком из городов, общую большую картинку. Вот отличия. Это все возможные точки, где человек в принципе мог голосовать. Мы рассчитывали, что люди, которые будут голосовать с главной страницы Яндекса, и так на ней находятся. Мы просто взяли длительный период времени и все возможные варианты перебрали. Вряд ли там бы появился кто-то новый. Были даже в самом Рио, в Америке, в Австралии. Просто их было мало. По крайней мере, все единичные точки мы получили в белом списке, а дальше вопрос состоял в том, как люди будут голосовать.
Следующая задача — сделать так, чтобы точки красиво отображались на карте. Heatmap для этого напрямую не предназначен. Он для других вещей — чтобы показывать тепловые карты. Там вес точек влияет на цвет. Нам нужно было чуть-чуть другое. Плюс нам хотелось делать точки больше и меньше в зависимости от их веса. Еще к нам поступило огромное количество пожеланий от дизайнеров про то, как это должно выглядеть с точки зрения градиентов, переливания цветов. На самом деле это не решалось никакими настройками Heatmap. Мы просто взяли сырые исходники и пошли их править. Ушло несколько дней, чтобы въехать, разобраться, поменять все что можно, переписать, закомментировать, переписать обратно с разными сайд-эффектами под разные браузеры. Не буду рассказывать. Если кому-нибудь интересно, я привел ссылку на исходники. Из больших вещей мы сделали только то, что кисть, которая рисует сам градиент, увеличивалась в зависимости от веса. Плюс градиент был с немного другими настройками.
В итоге получилась чуть-чуть другая картинка. Раньше точки были одинакового размера, а сейчас стали чуть ярче, у них меняется радиус, есть переливание из белого в желтый — в общем, дизайнеров это устроило.
Для запуска нам нужно было убедиться, что карта действительно может работать у людей. Методом научного тыка мы попробовали ее на разном количестве девайсов, в основном на планшетах, потому что там были основные проблемы, ну и на десктопах. Вывели какое-то примерное приближение, что на десктопах можно показывать не больше 5000 точек, на планшетах — не больше 3000, а на тачах — не больше 1000. Примерно таким был план, он давал приемлемый результат. Понятно, что план не самый лучший, но он работал, и не было особенного запаса что-то с ним делать.
Нам было важно, чтобы карта работала у всех, чтобы можно было делать какие-то деградации в зависимости от текущей загруженности страницы. Но мы так делать не стали.
Мы постоянно про это вспоминали. Проблема была особенно заметна на тачах, на телефонах. Смысл в том, что карта сразу показывалась на странице, не за кликом. Люди, проскроллив буквально один или два экрана, видели карту, и получалось, что они видели ее довольно часто, в каждый свой заход. И если бы там был большой лаг, а он там был, то они бы видели пустое место. Потом бы загружались картинки с фоном, потом сами точки, потом модуль карт, потом точки рисовали бы Heatmap. В общем, очень много времени. Плюс этих точек было не очень много, и картинка там получалась довольно куцая.
Единственное, что мы придумали: фильтровать данные, как-то ранжировать их в том месте, где мы их готовим. У нас существовала большая база, раз в десять минут мы готовили из нее JSON с точками, где были голоса. Тем, где были данные, мы могли что-то сделать. Проблема состояла в том, что код был написан на Perl. У нас бэкенд пишут на Perl, а в нашем случае речь шла про Heatmap на JS на клиенте. Как-то совсем не стыковалось, пока один из наших коллег за одну ночь не переписал Heatmap на Perl. Придя один раз с утра, мы с удивлением обнаружили, что у нас уже есть готовый вариант. Понадобился денек-другой, чтобы его отполировать, настроить обновление, закачку, раскатывание по серверам.
Мы получили возможность генерить на сервере тайлики срзау с картинками. У нас появились картинки, которые мы могли отдавать на тачи. В них мы могли отдавать любое количество точек, и мало того — мы могли их отдавать даже без API Карт. Нам достаточно было отрисовать, условно, всего шесть карт и спозиционировать относительно них текущую координату. Математика не очень сложная. Можно было выдрать кусочек карт, скопипастить и сделать это. По сути, мы убрали два лишних шага: с загрузкой большого количества данных и с работой какого-то из скриптов на телефоне.
Еще это дало нам точно такой же тайл, только растянутый на весь экран. Когда загружалась карта на десктопе, мы показывали фон, потом загружали данные, API Карт, рисовали Heatmap. В общем, было довольно долго и некрасиво. Вместо этого мы взяли просто нулевой тайл, растянули его под размер карты. Он был какой-то размазанный, но когда подгружалась карта, она как будто делала изображение чуть более резким, там все появлялось, и переход получался более плавным, более дружелюбным для пользователя.
Вроде бы мы все проблемы решили: с десктопом, с тачами, все круто.
Была еще одна история. В доме болельщиков в Рио висело две плазмы, где все смотрели. Там были наши голоса. Говорили, что спортсмены очень радовались, что их поддерживают. Там были совершенно разные города: неизвестные, малые и большие. Для ее отрисовки была отдельная версия. Возникала проблема: у двух телевизоров разные разрешения, DPI и т. д. Пришлось туда отдать карту, которая в GET-параметры принимает настройки, и можно было на месте подвигать размеры шрифтов, все что угодно, чтобы она там рисовалась. Потому что мы сидели здесь, а ребята были в Рио с разницей в восемь часов, что очень неудобно. Мы дали инструкции, они всё сделали.
Что получилось? В итоге запустили карту ночью накануне. Со страхом, но запустили, и она постепенно начала жить своей жизнью. Мы в нее залили примерно 1000 точек без голосов — просто чтобы было какое-то начальное состояние. Дальше люди потихоньку начали голосовать. Вначале темп был примерно 20 тыс. голосов в час, и так 3–5 дней. Потом постепенно снижалось, и к концу Олимпиады было порядка 2 млн голосов, сколько-то лайков в соцсетях. Мы с ней больше ничего не делали, она работала и все. Была процедура перегенерации раз в 10 минут. Она раскладывала, а мы ничего не делали, только смотрели. Успех.
Демку с глобусом мы все-таки сделали. Это произошло гораздо позже и чисто ради эксперимента. Взяли наш тайл, спроецировали его в нужную проекцию, натянули на глобус WebGL, и оно тоже завелось. При желании можно было и его включить, но он получился довольно тяжелым, мы его делали так, для себя. Для развлечения.
Автор: Леонид Клюев
