В этом посте описывается, как Uber точно вычисляет расчетное время прибытия при полумиллионе запросов в секунду. Подумайте о том, чтобы поделиться этим постом с кем-то, кто хочет изучать проектирование систем.
🔥 Наш Telegram канал о машинном обучении: https://t.me/+RlgPz8ihjxViOGEy
📌 Папка отборных каналов для Python разработчиков – https://t.me/addlist/8vDUwYRGujRmZjFi
Начнем!
У Марии важная встреча через 15 минут.
Она вызывает такси.
Но поездка заняла гораздо больше времени, чем ожидалось.
Поэтому она опоздала и расстроилась.
О приложении для совместного использования поездок под названием Uber она узнает от коллеги.
Она сразу же устанавливает его и была ошеломлена его точностью.
Расчетное время в пути из пункта А в пункт Б называется ожидаемым временем прибытия (ETA).
Uber рассчитывает расчетное время прибытия по 4 сценариям:
- Старт: когда водитель вводит пункт назначения в приложении.
- Диспетчерская: найти машину и забрать пассажира в кратчайшие сроки ожидания
- Забрать пассажира: найти время, необходимое для того, чтобы забрать пассажира.
- Время во время поездки: своевременно предоставлять обновления в режиме реального времени, чтобы добраться до места назначения.
Варианты использования ETA
На одну поездку обычно требуется около 1000 запросов ETA.
Однако вычисление расчетного времени прибытия является сложной проблемой. Потому что расстояние между источником и пунктом назначения не является прямой линией.
Вместо этого он состоит из сложных уличных сетей и автомагистралей.
Умные инженеры Uber использовали простые идеи для решения этой сложной проблемы.
Uber ETA
Вот как Uber точно рассчитывает расчетное время прибытия в экстремальных масштабах:
1. Алгоритм маршрутизации
Они представляют физическую карту в виде графа.
Графическое представление карты
Каждый перекресток дорог моделируется как узел.
При этом каждый сегмент дороги моделируется как направленное ребро.
Таким образом, вычисление ETA превращается в поиск кратчайшего пути в ориентированном взвешенном графе.
Алгоритм Дейкстры известен тем, что находит кратчайший путь в графе.
Но временная сложность алгоритма Дейкстры составляет O(n logn). А n — количество перекрестков дорог или узлов на графике.
Только в районе залива Сан-Франциско имеется полмиллиона перекрестков дорог. Таким образом, алгоритма Дейкстры недостаточно в масштабах Uber.
Поэтому они разделили граф. А затем предварительно вычислил лучший путь внутри каждого раздела.
Разбиение на разделы и предварительное вычисление наилучшего пути в разделах
Таким образом, взаимодействия с границами разделов графа достаточно, чтобы найти лучший путь.
Представьте себе плотный граф, сопоставленный с кругом.
Поиск лучшего пути путем взаимодействия только с границами разделов
Необходимо пройти каждый узел в круге, чтобы найти лучший путь между двумя точками.
Таким образом, временная сложность будет равна площади круга: pi * r^2.
А секционирование и предварительные вычисления делают его более эффективным.
Становится возможным найти лучший путь, взаимодействуя только с узлами на границе круга.
Таким образом, временная сложность будет равна периметру круга: 2 * pi * r.
Другими словами, временная сложность поиска лучшего пути в районе залива Сан-Франциско снижается с 500 тысяч до 700.
2. Информация о дорожном движении
Необходимо учитывать движение на участках дороги, чтобы найти самый быстрый путь между двумя точками.
В то время как движение транспорта зависит от времени суток, погоды и количества транспортных средств на дороге.
Заполнение весов ребер графика информацией о трафике
Uber используют информацию о трафике для заполнения весов ребер графа. Потому что это делает расчетное время прибытия более точным.
Кроме того, они объединили агрегированную историческую информацию о скорости потока с информацией о скорости движения в реальном времени. Потому что дополнительные данные о движении делают информацию о дорожном движении более точной.
3. Сопоставление карт
Сигналы GPS могут быть зашумленными и неточными особенно когда автомобиль въезжает в туннель.
Также эффект многолучевого распространения может ухудшить сигнал GPS. Эффект многолучевого распространения возникает, когда здания отражают сигнал GPS.
Плохой сигнал GPS снижает точность определения расчетного времени прибытия.
Сопоставление карт
Поэтому они сопоставляют карты, чтобы найти лучшее расчетное время прибытия.
Сопоставление карт осуществляется путем сопоставления необработанных сигналов GPS с реальными сегментами дороги.
Сопоставление сигналов GPS с сегментами дороги
Они используют фильтр Калмана для сопоставления карт. Он принимает сигналы GPS и сопоставляет их с участками дороги.
Представьте себе фильтр Калмана как человека, который делает правильное предположение о местоположении чего-либо. При угадывании учитывается новая и старая информация.
Кроме того, они используют алгоритм Витерби для поиска наиболее вероятных участков дороги. Это подход динамического программирования.
Представьте себе алгоритм Витерби как человека, который находит правильную историю, даже если некоторые слова написаны неправильно. Они делают это, просматривая слова рядом и исправляя ошибки, чтобы история приобрела больше смысла.
Пассажир, скорее всего, избежит будущих поездок, если фактическое время поездки превышает расчетное время прибытия.
Кроме того, ежедневно совершается более 18 миллионов поездок Uber.
Таким образом, в масштабах Uber неправильное расчетное время прибытия может стоить им убытков в миллиарды долларов США.
Текущий подход позволил им масштабироваться до полумиллиона запросов в секунду.