Привет. Это мой первый пост в блоге на английском языке, и я расскажу вам, как мы создали простое хранилище в памяти для анимированных автомобилей. Мы показываем анимированные автомобили на главном экране приложения «Намба Такси для клиентов». Этот пост о пройденном пути и алгоритмах, а не о Go.

Начало

История начинается в 2015 году с дипломной работы нашего мобильного разработчика. Тема работы - «Приложение водителя для службы такси». В приложении он анимировал машину. Выглядело это так.

Мы думали. Почему бы не использовать это на экране, если клиент может отслеживать местонахождение водителя. И нашей первой проблемой было отсутствие данных. Мы получаем новое местоположение водителя каждые 15 секунд. Мы не можем просто уменьшить интервал обновления, потому что, когда мобильное приложение водителя отправляет нам данные, оно получает текущий заказ, следующий заказ и наличие открытых предупреждений. Оповещение работает как кнопка SOS. Когда водитель нажимает на нее, другие водители спешат ему на помощь. А когда мы уменьшаем интервал обновления, мы можем получить больше трафика в наши системы. Мы не были уверены, что справимся с этим.

Первые шаги

Наша первая попытка была простой и глупой:

  1. Сделайте запрос и сохраните координаты.
  2. Сделайте еще один запрос и оживите машину.

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

В качестве решения проблемы мы использовали OpenStreetMap Routing Machine (OSRM) для построения маршрутов и улучшили наш алгоритм. У нас такой же тайм-аут.

  1. Делаем запрос.
  2. Сохранить координаты.
  3. Отправьте сохраненные координаты на бэкэнд.
  4. Построить маршрут через OSRM.
  5. Верните его в клиентское приложение и оживите маркер.

Вроде сейчас работает, но мы столкнулись с другой проблемой с дорогами с односторонним движением.

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

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

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

  1. Первым делом был калькулятор стоимости поездки. Все расчеты были на стороне водителя. В этом случае мы экономим ресурсы сервера, потому что не отправляем бесполезные запросы. С другой стороны, у нас всего одна точка доверия. Это мобильное приложение для водителя. Поэтому нам нужно продублировать данные и сохранить их на стороне сервера.
  2. Кроме того, мы поняли, что 1 трек за 15 секунд - это так мало, и многие клиенты не видят новую функцию, потому что автомобиль начинает движение через 15 секунд после открытия экрана. Я знаю не так много людей, которые могут 15 секунд смотреть на экран, на котором ничего не происходит.
  3. Более того, у нас много проблем с GPS-модулем на стороне водителя. Проблемы с GPS связаны с устройством водителя.
  4. Наконец, мы хотели, чтобы на главном экране появлялись анимированные автомобили.

Теперь нам нужно решить несколько проблем:

  1. Начни собирать больше треков с водителей
  2. Показывать анимированные автомобили на главном экране
  3. Сохранить промежуточную стоимость поездки на стороне сервера
  4. Сохранить мобильные данные
  5. Собирать каждый трек за одну секунду

Хочу сказать несколько слов о сохранении мобильных данных. Нам это нужно, потому что у нас в стране очень дешевая квитанция на такси. Мы используем такси как общественный транспорт. Например, добраться из одного конца города в другой можно всего за 2 евро. Это как метро в Париже. К тому же стоимость мобильного интернета слишком высока. Если мы будем экономить 100 байт в секунду, то в масштабе компании мы сэкономим 2000 $.

Какие данные в треке?

  1. Местоположение водителя (широта, долгота)
  2. Сеанс драйвера, который мы даем при входе в систему
  3. Информация о заказе (OrderID и стоимость поездки)

Мы решили, что одна дорожка должна быть меньше 100 байт. И мы начали искать транспортный протокол, чтобы решить эту проблему.

Как видите, мы наблюдали за несколькими протоколами:

  1. HTTP
  2. WebSockets
  3. TCP
  4. UDP

И для нас идеальным вариантом был UDP, потому что:

  1. Отправляем только дейтаграммы
  2. Нам не нужны гарантии
  3. Минимализм
  4. Сохраните много данных
  5. У нас всего 20 байт накладных расходов
  6. Не заблокирован в мобильных сетях в нашей стране

Что касается сериализации данных, мы наблюдали за:

  1. JSON
  2. MsgPack
  3. Протобуф

Мы выбрали буферы протоколов, потому что они очень эффективны при работе с небольшим объемом данных.

И, как видите, ближайший конкурент тяжелее вдвое.

Что у нас в целом?

  1. У нас 42 байта полезной нагрузки
  2. + 20 байт заголовков IP
  3. = 62 байта на дорожку.
  4. ВЫГОДА.

Но когда мы получаем данные, нам также нужно их хранить, верно?

Хранилище данных

Нам нужно хранить эти данные:

  1. Сеанс водителя для идентификации водителя
  2. Номер кабины для поиска мобильного приложения клиента
  3. Идентификатор заказа и стоимость поездки для сохранения данных о поездке из мобильного приложения водителя на сервере
  4. Последнее место для поиска
  5. N последних точек для построения маршрута

Подержанные склады

  1. Percona - для хранения всех данных. У нас хранятся водители, заказы, тарифы и все остальное.
  2. Redis как хранилище ключей и значений для кэширования.
  3. Elasticsearch для геокодирования

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

Мы наблюдали за двумя геоиндексами:

  1. KD-дерево
  2. R-дерево.

У нас были требования к геоиндексу:

  1. Нам нужно найти N ближайших точек.
  2. Нам нужно сбалансированное дерево, чтобы обеспечить лучший поиск в худшем сценарии.

KD-дерево

А KD-дерево нам не подходит, потому что оно несбалансированное и может искать только одну ближайшую точку. Мы можем реализовать k-ближайших соседей над kd-tree, но мы не будем изобретать велосипед, потому что R-tree уже решает эту проблему.

R-дерево

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

Вы можете получить его для языка программирования Go. Https://github.com/dhconnelly/rtreego.

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

  1. Мы храним все данные в памяти.
  2. Мы используем R-tree для поиска ближайших драйверов.
  3. Также мы используем две карты для хранения водителей и выполняем поиск по номеру кабины или по сеансу.

Окончательный алгоритм.

Вот окончательный алгоритм на бэкэнде:

  1. Получать данные по UDP
  2. Попробуйте достать драйвер из хранилища
  3. Если не существует - скачать драйвер из redis
  4. Проверить и подтвердить данные
  5. Установить драйвер в хранилище
  6. Если не существует - инициализировать LRU
  7. Обновить r-tree

Конечные точки HTTP

Мы внедрили эти конечные точки для интеграции в наши системы.

  1. Вернуть ближайших водителей
  2. Удалить водителя из хранилища (по номеру кабины или сеансу)
  3. Получить информацию о поездке
  4. Получить информацию о драйвере

Вывод:

В завершение хочу подвести такие выводы, которые мы использовали в нашей бэкэнд-системе:

  1. UDP + Protobuf для экономии данных
  2. Хранение в памяти
  3. R-дерево для ближайших водителей
  4. Кэш LRU для хранения последних местоположений
  5. OSRM для сопоставления карт и построения маршрутов

В качестве примера вы можете посмотреть на https://github.com/maddevsio/openfreecabs. Это слишком просто, но в нем реализовано множество функций, описанных в статье.