Все лампочки горели зелёным

Сегодня днём настоящий роутинг-движок впервые построил нам поездку на автобусе: маршрут 06-2, 2071 секунда от двери до двери против 2585 пешком. Восемь с половиной минут выигрыша. Не разгром, но это автобус, и взялся он из расписания, которое мы написали сами.

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

Зачем роутинг-движок

Четвёртая часть закончилась тем, что поиск пути переехал в память Worker: граф из остановок и рёбер плюс цикл, который перечисляет пути максимум с двумя пересадками. Работает. Но он сначала находит пути, а расписание спрашивает потом. Кандидатов он набирает, считая остановки и пересадки, затем смотрит, когда по ним уходят автобусы, и сортирует по общему времени вместе с ожиданием. Путь, которого нет среди кандидатов, выиграть не может, как бы скоро ни уходил его автобус.

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

Такой у нас уже есть. Valhalla — открытый роутинг-движок, и с прошлого ноября она считает пешие части наших маршрутов. Крутится она на маленькой виртуалке, которая у нас и так была, — на той же машине, что рисует тайлы карты из второй части. Общественный транспорт Valhalla тоже умеет. Надо только скормить ей GTFS.

Расписание, которого никто не публикует

GTFS — это формат, в котором транспортные компании публикуют расписания: zip с CSV-файлами. stops.txt говорит, где остановки, а routes.txt перечисляет маршруты. В trips.txt одна строка на каждый рейс автобуса, stop_times.txt говорит, когда рейс проходит каждую остановку, а calendar.txt — по каким дням. shapes.txt рисует дорогу, по которой едет автобус. Его читает любой роутинг-движок. Для Торревьехи, насколько мы знаем, его никто не публикует.

Но у нас есть всё, из чего GTFS-фид состоит. Нарисованная руками сеть из первой части даёт остановки, маршруты и их форму. Шаблоны расписаний («от C/ Mayor в 07:30, каждые 30 минут, до 20:01, по будням») дают отправления. А трюк из первой части — время отправления плюс секунды от каждой остановки до следующей — даёт каждое прибытие. stop_times.txt — это та самая арифметика, расписанная для каждого отправления и каждой остановки. Слегка упрощённо:

for (const dep of departures) {
  const vec = vectors.get(`${dep.line}:${dep.from}`) // seconds from each stop to the next
  let t = dep.departure_time * 60
  for (let i = 0; i < vec.length; i++) {
    t += vec[i] // vec[0] is 0 for the first stop
    stopTimes.push({
      trip_id: tripId,
      stop_id: lineStations[fromIdx + i],
      arrival_time: formatTime(t),
      departure_time: formatTime(t),
      stop_sequence: i + 1,
    })
  }
}

Это чистый JavaScript внутри Worker плюс маленькая библиотека для zip. Как сказано в шапке файла, «ничему здесь не нужны ни бинарник, ни контейнер, ни раннер GitHub Actions».

Первую версию я написал 6 марта. Каждый будний день в 04:20 UTC Worker собирает фид и загружает его в R2, но только если изменился его хеш. Через десять минут cron на виртуалке должен был сверить хеш, скачать zip, если он новый, распаковать его для Valhalla и перезапустить её. Фид закрыт токеном: остановки, маршруты и их форма — это данные, которые мы собирали руками.

В том же коммите у Worker появилась функция, которая спрашивает у Valhalla маршрут на автобусе и пешком.

Её никто не вызывал.

Приложение продолжало обращаться к поиску по графу из четвёртой части, а фид продолжал уходить каждое утро буднего дня — ну или пытался. Сегодня мы переключили поиск пути на Valhalla и начали выяснять, что же мы всё это время публиковали.

Все лампочки горели зелёным

Вот что стояло между фидом и автобусом в приложении.

Первая проблема хотя бы выглядела как поломка. Собрать фид — значит развернуть каждое отправление в рейс, а каждый рейс — в строку на каждую остановку, потом всё это заархивировать, и всё это должно было уложиться в один запуск Worker. Когда не укладывалось, запуск умирал на полпути, никто не записывал, чем он закончился, и в нашем списке джоб он становился «осиротевшим». В R2 оставалось то, что записал последний удачный запуск. Теперь эта джоба — durable Workflow в Cloudflare из пяти шагов, и у каждого шага свой свежий бюджет.

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

Одно пустое число выкидывает все автобусы. Читалка GTFS в Valhalla разбирает числа сразу, и одна пустая координата в shapes.txt роняет std::stod:

[ERROR] Couldn't find a required file for feed cuando: stod while adding item from shapes.txt
[ERROR] Couldn't find any usable GTFS feeds.

На этом сборка не заканчивается. Valhalla едет дальше без транспорта и строит совершенно нормальный граф, в котором нет ни одного автобуса. А пустая координата в нашем shapes.txt была не одна. Больше половины строк выглядели вот так:

guardamar-hospital,,,1

Каждое ребро хранит дорогу, по которой идёт, в виде списка точек, и у наших рёбер эти точки записаны в двух кодировках: парами [lat, lng] и объектами {latitude, longitude}. Обе законные, обе встречаются сплошь и рядом, и карта в приложении читает обе. Сборщик фида читал только объекты, а пары записывал как пустоту. Лучшее тут — объявление типа в самом сборщике: в комментарии к нему сказано, что в колонке лежат пары [lat, lng]. Комментарий был прав насчёт половины строк, а код — насчёт другой половины.

Zip — тоже фид. Образ ищет фиды в /gtfs_feeds — этот путь зашит в его скрипты — и хочет, чтобы каждый был распакован в отдельную папку. Скрипт, который мы закоммитили в марте, распаковывал фид туда как положено, а потом оставлял рядом сам zip. Всё остальное в этой папке считается отдельным фидом и валит загрузку.

Перезапуск ничего не подхватывает. Valhalla у нас работает из её Docker-образа valhalla-scripted, который настраивается переменными окружения, и они значат не то, что написано. build_transit=True строит транспорт, только если транспортных тайлов ещё нет. build_tar=True собирает архив тайлов, только если архива ещё нет. А сервис отдаёт именно этот архив, а не свежие тайлы рядом с ним. Из скриптов самого образа:

# configure_valhalla.sh: transit builds only if the directory is missing or empty
if [[ "${build_transit}" == "Force" ]] || (! [[ -d ${TRANSIT_DIR} ]] && [[ "${build_transit}" == "True" ]]) || ...

# docker-entrypoint.sh: the archive is built only if it does not already exist
if ([[ "${build_tar_local}" == "True" && ! -f $TILE_TAR ]]) || [[ "${build_tar_local}" == "Force" ]]; then

Наш скрипт синхронизации заканчивался перезапуском под комментарием «Restart Valhalla to rebuild with new transit data». Когда транспортные тайлы уже есть, перезапуск ничего такого не пересобирает. Новый фид лежит на диске, а отвечает старый граф.

Очевидное решение — ловушка. Образ понимает ещё и Force, который пересобирает всё каждый раз. Но окружение контейнера фиксируется при его создании, а наш настроен подниматься сам. Создай его один раз с Force — и каждая перезагрузка виртуалки стирает тайлы и минут двадцать собирает их заново, менялся фид или нет. В compose-файле, который мы закоммитили в марте, был включён родственник этого переключателя — force_rebuild=True. Он пересобирает весь дорожный граф при каждом старте и всё равно не трогает уже существующие транспортные тайлы: двадцать минут пересборки всего, кроме единственного, что поменялось.

Работает наоборот: оставить переменные в True и перед пересозданием контейнера удалить транспортные тайлы и архив. Тогда True строит ровно тогда, когда есть что строить. Пересборка занимает от десяти до двадцати пяти минут на четырёх потоках для выгрузки OpenStreetMap размером около 46 МБ.

Календарь истекает молча. calendar.txt говорит, по каким дням ходит каждый сервис, между датой начала и датой конца. Наш покрывает отправления, которые мы сгенерировали, — примерно на шесть недель вперёд. Фид, у которого дата конца прошла, собирается без единой ошибки и никого никуда не везёт. Фид, который мы опубликовали сегодня, перестанет строить маршруты 13 сентября, если до этого его не сменит новый.

Пешая прогулка — это 200. Когда у Valhalla нет автобусов или ни один не помогает, запрос маршрута на автобусе не падает. Она отвечает пешим маршрутом и HTTP 200 — ровно как при успехе. Функция, которую я написал в марте, проверяла ровно одно: res.ok. Если бы её кто-то вызвал, она положила бы пешую прогулку в список автобусных маршрутов, и прогулка выглядела бы нормально.

Подключаем

Исправление фида влили в пять. К четверти седьмого поиск пути в приложении уже шёл через Valhalla. Что Worker делает с ответом:

• Спрашивает не один раз. Valhalla возвращает один маршрут на запрос, а приложение показывает несколько на выбор. Поэтому Worker спрашивает до трёх раз и каждый раз исключает маршруты, которые уже использовали предыдущие ответы. Если ответ всё равно приходит тот же, он останавливается.
• Узнаёт свои id. Valhalla возвращает id из нашего фида, завёрнутые в свои: cuando_06-2 для маршрута, cuando_c-argonauto_transit_station для остановки. Сними обёртку — и это те самые id, которые приложение уже знает, так что в приложении не пришлось менять ни строчки.
• Никогда не смотрит на название. Короткое название маршрута 06-2 — «06», и у маршрута в обратную сторону оно тоже «06». Ищи маршруты по названию — и получишь правильный номер в неправильную сторону.
• Отправляет местное время. Время отправления Valhalla понимает как местное время на часах, потому что время в stop_times.txt местное. Отправь UTC — и в августе получишь автобусы двухчасовой давности.
• Считает прогулку отсутствием ответа. Ответ без единого автобуса считается как «ничего не нашлось». Ещё каждый маршрут и каждая остановка в ответе сверяются с базой, так что тайлы, собранные из старого датасета, всплывают предупреждением в логах, а не маршрутом без названия в приложении.

Одна настройка в Worker возвращает поиск пути на граф из четвёртой части. Без релиза приложения и без ревью в сторах.

Потом мы посмотрели на карту

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

Теряли их четыре отдельных бага. Каждый был молчаливым по построению: там, где должно было быть предупреждение, стояли continue или filter:

• Опять две кодировки, на этот раз в коде, который рисует форму поездки. Ребро, записанное парами, давало ноль точек.
• Парсер id, который съедал id. В старых строках лежит голый id остановки, в новых — полное имя ресурса, и запрос отрезал имя после /stations/ вот так: substr(x, instr(x, '/stations/') + length('/stations/')). На голом id instr возвращает 0, так что отрезать начинали с десятого символа самого id: c-argonauto превращался в to, а c-perseo, который короче, — вообще в пустую строку. Ни то ни другое ни с чем не совпадает.
• Ребро выбиралось по наименьшему id. Между двумя одними и теми же остановками разные маршруты могут ехать разными дорогами. Запрос брал первое попавшееся ребро, чьё бы оно ни было.
• Кольцевые маршруты. Фид искал рёбра маршрута по остановке, от которой они отходят. Кольцевой маршрут проходит одну остановку дважды, так что от неё отходят два ребра. Фид оставлял одно и использовал его оба раза: линия уходила по одной ветке, возвращалась, рисовала её ещё раз, а другую ветку — ту, на которой была остановка, — не рисовала вообще.

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

Вместе с исправлением появились две джобы, которые проверяют геометрию; их запускают руками после правок сети. Та, что важна здесь, читает из R2 опубликованный zip, так что проверяет ровно те байты, которые ест Valhalla, а не свежую сборку, которая может от них отличаться. Главная её проверка ловит любую остановку дальше 120 метров от линии, нарисованной для её рейса. Порог взят из баг-репорта: в хорошем случае остановки отстояли от линии максимум на 41 метр, а сломанные промахивались на 313, 435 и 843.

День навигации

Сегодня в навигацию и геометрию под ней ушло двенадцать пулл-реквестов — с без четверти три дня до двадцати минут одиннадцатого вечера. Три из них чинили поиск в памяти из четвёртой части, у которого хватало своих проблем. Один добавил норвежский в подсказки маршрута, а шведский — в подписи, которые мы пишем сами: в городе, где живёт столько скандинавов, и то и другое стоило сделать давным-давно. (Белорусского в Valhalla нет вообще, так что белорусским читателям подсказки приходят по-русски.)

Урок, который я из этого выношу, — про сигналы. Каждая наша проверка спрашивала, отработало ли что-то: джоба, загрузка, контейнер, HTTP-запрос. Ни одна не спрашивала, выходит ли на другом конце автобус. Каждый раз, когда контейнер отвечал, он был здоров. Просто автобусов в нём не было.

Что дальше

• Проба. Каждое утро спрашивать у Valhalla поездку, в которой обязан быть автобус, и громко падать, если его нет. Сейчас «синхронизация прошла» значит, что началась пересборка, а она после этого идёт ещё до двадцати пяти минут.
• Более поздние отправления. Valhalla отвечает на вопрос «как лучше доехать, если выйти прямо сейчас?», а спросить про следующий автобус приложение пока не может.
• Сами данные. У новых джоб для нас есть список, и он не короткий.