Как Uber вычисляет расчетное время прибытия при полумиллионе запросов в секунду

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

🔥 Наш Telegram канал о машинном обучении: https://t.me/+RlgPz8ihjxViOGEy

📌 Папка отборных каналов для Python разработчиков – https://t.me/addlist/8vDUwYRGujRmZjFi

Начнем!

У Марии важная встреча через 15 минут.

Она вызывает такси.

Но поездка заняла гораздо больше времени, чем ожидалось.

Поэтому она опоздала и расстроилась.

Как Uber вычисляет расчетное время прибытия при полумиллионе запросов в секунду

О приложении для совместного использования поездок под названием Uber она узнает от коллеги.

Она сразу же устанавливает его и была ошеломлена его точностью.

Расчетное время в пути из пункта А в пункт Б называется ожидаемым временем прибытия (ETA).

Uber рассчитывает расчетное время прибытия по 4 сценариям:

  • Старт: когда водитель вводит пункт назначения в приложении.
  • Диспетчерская: найти машину и забрать пассажира в кратчайшие сроки ожидания
  • Забрать пассажира: найти время, необходимое для того, чтобы забрать пассажира.
  • Время во время поездки: своевременно предоставлять обновления в режиме реального времени, чтобы добраться до места назначения.
Uber ETA Use Cases
Варианты использования ETA

На одну поездку обычно требуется около 1000 запросов ETA.

Однако вычисление расчетного времени прибытия является сложной проблемой. Потому что расстояние между источником и пунктом назначения не является прямой линией.

Вместо этого он состоит из сложных уличных сетей и автомагистралей.

Умные инженеры Uber использовали простые идеи для решения этой сложной проблемы.


Uber ETA

Вот как Uber точно рассчитывает расчетное время прибытия в экстремальных масштабах:

1. Алгоритм маршрутизации

Они представляют физическую карту в виде графа.

Uber ETA; Graph representation of a map
Графическое представление карты

Каждый перекресток дорог моделируется как узел.

При этом каждый сегмент дороги моделируется как направленное ребро.

Таким образом, вычисление ETA превращается в поиск кратчайшего пути в ориентированном взвешенном графе.

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

Но временная сложность алгоритма Дейкстры составляет O(n logn). А n — количество перекрестков дорог или узлов на графике.

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

Поэтому они разделили граф. А затем предварительно вычислил лучший путь внутри каждого раздела.

Uber ETA; Routing algorithms
Разбиение на разделы и предварительное вычисление наилучшего пути в разделах

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

Представьте себе плотный граф, сопоставленный с кругом.

Uber ETA; Partitioning
Поиск лучшего пути путем взаимодействия только с границами разделов

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

Таким образом, временная сложность будет равна площади круга: pi * r^2.

А секционирование и предварительные вычисления делают его более эффективным.

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

Таким образом, временная сложность будет равна периметру круга: 2 * pi * r.

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

2. Информация о дорожном движении

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

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

Uber ETA; Traffic layer
Заполнение весов ребер графика информацией о трафике

Uber используют информацию о трафике для заполнения весов ребер графа. Потому что это делает расчетное время прибытия более точным.

Кроме того, они объединили агрегированную историческую информацию о скорости потока с информацией о скорости движения в реальном времени. Потому что дополнительные данные о движении делают информацию о дорожном движении более точной.

3. Сопоставление карт

Сигналы GPS могут быть зашумленными и неточными особенно когда автомобиль въезжает в туннель.

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

Плохой сигнал GPS снижает точность определения расчетного времени прибытия.

Uber ETA; Map matching
Сопоставление карт

Поэтому они сопоставляют карты, чтобы найти лучшее расчетное время прибытия.

Сопоставление карт осуществляется путем сопоставления необработанных сигналов GPS с реальными сегментами дороги.

Uber ETA; Map matching transformation
Сопоставление сигналов GPS с сегментами дороги

Они используют фильтр Калмана для сопоставления карт. Он принимает сигналы GPS и сопоставляет их с участками дороги.

Представьте себе фильтр Калмана как человека, который делает правильное предположение о местоположении чего-либо. При угадывании учитывается новая и старая информация.

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

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


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

Кроме того, ежедневно совершается более 18 миллионов поездок Uber.

Таким образом, в масштабах Uber неправильное расчетное время прибытия может стоить им убытков в миллиарды долларов США.

Текущий подход позволил им масштабироваться до полумиллиона запросов в секунду.

Как Uber вычисляет расчетное время прибытия при полумиллионе запросов в секунду

Источник

+1
2
+1
11
+1
0
+1
1
+1
0

Ответить

Ваш адрес email не будет опубликован. Обязательные поля помечены *