Самый эффективный сервис Unwinding Uber

Несколько недель назад Uber опубликовал статью, в которой подробно описал, как они построили свой самый высокий запрос в секунду с помощью Go. Статья довольно короткая и ее необходимо прочитать, чтобы понять мотивацию этой публикации. В последнее время я выполнял некоторые геопространственные работы на Голанге и надеялся, что Uber представит несколько проницательных подходов к работе с геоданными в Go. То, что я обнаружил, не оправдало моих ожиданий, мягко говоря ...

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

Вместо индексации геозон с помощью R-дерева или сложного S2 мы выбрали более простой маршрут, основываясь на наблюдении, что бизнес-модель Uber ориентирована на город; бизнес-правила и геозоны, используемые для их определения, обычно связаны с городом. Это позволяет нам организовать геозоны в двухуровневую иерархию, где первый уровень - это городские геозоны (геозоны, определяющие границы города), а второй уровень - это геозоны внутри каждого города.

Если бы вы попросили кого-то решить проблему геозон, кто никогда не сталкивался с пространственными алгоритмами, вероятно, они бы это придумали. Раскрасьте меня разочарованием, что инженеры компании стоимостью 50 миллиардов долларов, основной бизнес которой сосредоточен на поиске вещей на Земле, которые находятся поблизости, предпочли проигнорировать стандартные решения без конкретной причины, за исключением того, что это слишком сложно. Это особенно обидно, учитывая, что прошлым летом Uber купил часть инженерных разработок Bing Maps, базирующихся в Колорадо. Раньше я работал в команде Bing Maps Streetside, которую приобрел Uber, и я точно знаю, что в этих командах довольно много людей, которые кое-что знают о пространственном индексировании. Один из моих вопросов на собеседовании заключался даже в том, как узнать, какие фотографии в Instagram с геотегами изображают Эйфелеву башню.

Помимо предубеждений, я с уважением отношусь к тому, что Uber установил конкретное требование к распределению задержки, чтобы обслуживать 99% всех запросов менее чем за 100 миллисекунд, и использовал это в качестве своей метрики успеха. Если их удалось добиться с помощью метода грубой силы, то похвалы в порядке. Мое отношение к доставке похвалы изменилось по мере того, как я читал статью дальше.

«Хотя идиоматический способ Go - синхронизировать одновременное чтение / запись с горутинами и каналами, мы были обеспокоены негативными последствиями для производительности».

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

Анализ сложности времени геозон

Начните с анализа временной сложности возможных решений. Для этого не нужно писать код, достаточно провести небольшое исследование и продемонстрировать неэффективность подхода Uber. Даже если вы не знакомы с анализом Big-O, надеюсь, он все же прояснит суть.

Первое, что нам нужно сделать, это стоимость проверки точки в многоугольнике (я люблю называть ее запросом включения многоугольника). Статья в Википедии хорошо разбирается в двух общих алгоритмах, используемых для включения многоугольников; Лучей и число намотки. Оба алгоритма должны сравнивать точку запроса с каждой вершиной многоугольника, поэтому их эффективность зависит от количества вершин. Если мы разберем проблему, используя модель Uber, ориентированную на города, мы получим несколько переменных, которые сможем использовать для нашего анализа.

q := Point Query
C := Number of cities
V := Number of vertices that define a city boundary
n := Number of fence polygons in a city
v := Number of vertices in a fence polygon 

Здесь я обрисую несколько алгоритмов, цитируемых в статье, и посмотрю, как они складываются.

Грубая сила

Я буду опираться на описание алгоритма грубой силы, которое дает Uber.

… Пройти через все геозоны и выполнить проверку точки в полигоне с использованием алгоритма, такого как алгоритм преобразования лучей.

В нашей структуре это означает прохождение каждого города C, затем каждого многоугольника ограждения n, и, наконец, сравнение точки запроса с каждой вершиной в многоугольнике v .

Brute() -> O(Cnv)

Расширенная грубая сила

Uber дополнил подход грубой силы, сначала проверив, в каком городе находится точка, а затем перешел через заборы в этом отдельном городе. Это эффективно сокращает пространство поиска на порядок количества городов, имеющихся в данных. Стоимость сравнения точки запроса с каждой точкой на границе города по-прежнему необходимо учитывать. При таком двухэтапном подходе мы получаем следующее:

Uber() -> O(CV) + O(nv)

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

RTree

Структура данных r-tree основана на b-дереве со специальным определением последовательности для многомерных объектов. Последовательность определяется путем сравнения минимального ограничивающего прямоугольника (MBR) объекта с MBR другого объекта и определения того, полностью ли он его содержит. В двумерном случае геозоны MBR представляет собой простую ограничивающую рамку (bbox), определяемую координатами минимума и максимума. Проверка того, содержит ли bbox другого объекта, - это постоянная операция по утверждению, что минимальная координата меньше, а максимальная больше, чем bbox другого объекта по обеим осям. В статье в Википедии есть подробное объяснение, но вот наглядное пособие по дереву и его ограничивающим рамкам объектов.

Если реализовать это самостоятельно кажется несостоятельным, быстрый поиск дает несколько чистых реализаций Go. Пакет rtreego имеет большую часть возможностей, но должен быть немного специализирован для 2-х измерений и имеет пару дополнительных mallocs, которые можно устранить.

Завершение нашего анализа r-дерева оставляет нам работу по поиску r-дерева, для которого ограничивающие прямоугольники многоугольника содержат точку, а затем выполнение запроса включения многоугольника для каждого из них. Средняя временная сложность поиска в r-дереве составляет O (logMn), где M - определяемая пользователем константа максимального числа дочерних узлов, которое может иметь узел.

M := Maximum number of children
Rtree() -> O(logM(Cn)) + O(v)

QuadTree

Квадродерево - это специализация общего kd-дерева для двумерного индексирования. Обычно вы берете плоскую проекцию области поиска и делите ее на части, которые мы будем называть ячейками. Затем вы рекурсивно делите каждую из этих ячеек на четверти, пока не достигнете определенной максимальной глубины, на которой будут находиться листья дерева. Если мы возьмем меркаторную проекцию Земли и пометим каждую из ячеек, добавив идентификатор к родительской метке, мы сможем использовать структуру квадродерева для создания системы листов быстрого геопространственного поиска, как это делает / делает Bing Maps. Bing Maps называет метки ячеек QuadKeys, и они напрямую переводятся в фрагменты карты. Вот хороший обзор того, как они созданы.

S2

Почему я вообще говорю о квадродереве? Что ж, сложный алгоритм S2, упомянутый в статье, является всего лишь реализацией квадродерева! Основное различие между системой листов Bing Maps и S2 заключается в том, что проекция S2 выполняется посредством кубического отображения сферы Земли, так что каждая ячейка имеет одинаковую площадь поверхности. Ячейки также расположены с использованием кривой распределения пространства для сохранения пространственной локальности в метке ячейки. Вот пост с более глубоким объяснением. S2 написан на C ++ и имеет привязки для разных языков. Одна из замечательных особенностей Go - это простой процесс сборки и создание единого статически связанного двоичного файла. Введение привязок C ++ лишило бы этих преимуществ. К счастью для нас, в golang / geo есть чистая реализация Go. По общему признанию, он неполный и в нем отсутствует реализация s2.Region для s2.Polygon, поэтому s2.RegionCoverer нельзя использовать из коробки, но ядро ​​есть. Вот два примера плоских обложек на разных уровнях и RegionCoverer, который генерирует многоуровневые обложки.

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

T := Features with cell label
QTree() -> O(T) + O(v)

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

Сравнение

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

q := Point Query
C := Number of cities
V := Number of vertices that define a city boundary
n := Number of fence polygons in a city
v := Number of vertices in a fence polygon
Brute() -> O(Cnv)              
Uber()  -> O(CV) + O(nv)       
Rtree() -> O(logM(Cn)) + O(v)  
Qtree() -> O(T) + O(v)       

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

Оценка

В исходном сообщении говорилось, что разложение набора функций на города сократило пространство поиска с десятков тысяч до сотен. Затем мы можем сделать вывод, что у них есть сотни городов для поиска. Количество точек, образующих границу города, может существенно различаться. Я видел, что определение Манхэттена варьируется от тысячи до шести тысяч. Предположим, они выбирают простые определения или делают некоторые собственные упрощения многоугольников, такие как Дуглас-Пойкер (несмотря на то, что никогда не упоминают об этом), и говорят, что граница города в среднем составляет 100 баллов.

Сколько полигонов ограждений будет в каждом городе? Исходя из той же логики, что и для числа городов, и зная, что в Нью-Йорке 167 районов, 100 снова кажется правильным порядком величины. Глядя на вершины забора, можно увидеть, что такие районы, как Вильямсбург в Бруклине, имеют несколько сотен точек, но определяемые пользователем многоугольники почти наверняка имеют простые формы из нескольких точек. Давайте предположим и снова остановимся на 100 для нашего параметра v. Учитывая, что v - это сам запрос включения многоугольника, и каждый алгоритм должен это делать, меня меньше беспокоит его правильность. Я думаю, что мы, по крайней мере, в правильном порядке.

C := 100 // cities
V := 100 // vertices in city
n := 100 // polygons in city
v := 100 // vertices in polygon
M := 50  // rtree parameter
T := 4   // polygons per cell
Brute() -> 1   * 10^6
Uber()  -> 2   * 10^4
Rtree() -> 2.3 * 10^2
Qtree() -> 4   * 10^2

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

Мыслить внутри коробки

Проницательный читатель, возможно, заметил, что есть простое изменение в алгоритме Uber, которое мы могли бы внести, чтобы резко повысить его эффективность. Мы могли бы использовать ограничивающие прямоугольники, чтобы избежать многих дорогостоящих запросов «точка в многоугольнике» так же, как это делает алгоритм Rtree. Они никогда не ссылаются на использование ограничивающих рамок в посте, поэтому я могу только предположить, что они ими не воспользовались. Поиск методом грубой силы по всем ограждениям с проверкой ограничивающего прямоугольника более эффективен, чем алгоритм Uber. Применение флажка ограничивающего прямоугольника к их алгоритму дает нам тот же порядок величины, что и пространственные индексы.

BruteBox() -> O(Cn) + O(v)              -> 1 * 10^4
UberBox()  -> O(C) + O(V) + O(n) + O(v) -> 4 * 10^2

Это ощутимое изменение, которое они могли бы внести в свои системы сегодня. Если они начали с нуля, им все равно следует придерживаться пространственных алгоритмов для обеспечения их гибкости и избегать управления границей города с отображениями многоугольников. Несмотря на то, что мы имеем дело с сусликами, а не со змеями, дзен «плоский лучше, чем вложенный» по-прежнему звучит правдоподобно.

Бенчмаркинг алгоритмов геозон

Все еще не уверены? Я реализовал каждый из алгоритмов, смоделировал проблему геозон и сравнил результаты. Чтобы рассеять сложность библиотеки S2, я также реализовал отсутствующий интерфейс S2.Region для типа s2.Loop. Петля - это простой замкнутый многоугольник в терминологии S2. На реализацию потребовался час.

Для простоты сравнения я создал интерфейс GeoFence для реализации каждого алгоритма.

type GeoFence interface {
    Add(f *geo.Feature)
    Get(c geo.Coordinate) []*geo.Feature
}

Я загрузил материалы переписи населения Нью-Йорка 2010 г. и спросил, в каком урочище в то время находился музей Уитни. Я посчитал каждый город Нью-Йорка как город для алгоритма Uber. Я переименовал его в алгоритм City, чтобы никого не позорить. Код тестирования выглядел примерно так:

func BenchmarkFence(b *testing.B) {
    fence := geofence.NewFence()
    for _, tract := range tracts {
        fence.Add(tract) 
    }
    b.ResetTimer()
    for n := 0; n < b.N; n++ {  
        result = fence.Get(museums["old whitney"])
    }
}

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

На данный момент доказательства выглядят довольно убедительно, но, возможно, вы все еще настроены скептически. Я смоделировал набор данных Uber, используя твиты с геотегами в качестве прокси для запросов на поездку и текущие местоположения автобусов MTA вместо местоположения автомобилей. Поиск этих автобусов и твитов по 2123 участкам переписи населения Нью-Йорка по пяти районам должен дать некоторое сходство с фактическими потоками данных Uber. Сравнительный анализ с помощью wrk одной капли Digital Ocean из другой в той же частной сети показал, что использование пространственного индекса увеличивает пропускную способность более чем на 166% по сравнению с алгоритмом city. Для контрольной выборки конечная точка, обслуживающая короткую строку, обслуживала в среднем 10930 запросов в секунду.

Эти цифры могут показаться ничтожными по сравнению с указанной в статье Uber пропускной способностью 170 тыс. Запросов в секунду. Однако, учитывая, что этот тест является одноядерным, их кластер состоит из 40 узлов и, исходя из предположения, что кластер состоит из 16 ядерных процессоров, мы торгуем в соотношении 1: 640. Если мы применим это соотношение к разнице в производительности, мы получим разницу в пропускной способности в миллионы запросов.

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

Очевидно, что большая часть работы в семействе ограждений методом перебора выполняется при поиске, в то время как пространственные индексы сериализуют больше данных и отвечают на дополнительные запросы. Мы могли бы сократить расходы на сериализацию, приняв сетевой протокол, такой как protobuf или msgpack без схемы. У Uber есть запись в блоге о том, что они выбрали для сериализации. Я уверен, что есть еще много настроек, которые можно сделать на обработчиках и на сервере.

Репо geofence-profiling содержит данные, использованные в этом эксперименте, особенности проведения сравнительного анализа и более подробные результаты, такие как графики pprof и таблицы задержек.

Обмотка его обратно

Мне ясно, что команда Uber недооценила эту проблему. Продуманное проектирование этой услуги могло бы сократить количество узлов на порядок и сэкономить сотни тысяч долларов каждый год. Для компании, стоимость которой превышает ВВП штата Делавэр, это может звучать жалко, но, на мой взгляд, зарплаты нескольких инженеров и нескольких хороших инженеров могут иметь большое значение. Может быть, даже больше, чем несколько дополнительных Mercedes-Benz S-классов, которые они могли бы добавить к своему автопарку из денег, которые они могли бы сэкономить ...

Надеюсь, вам понравился мой небольшой эксперимент так же, как и мне. Далее следует библиотека gofence. Он включает в себя установочный скрипт, который выберет правильный двоичный файл для вашей архитектуры, так что вы можете начать встраивать точечные объекты geojson в свои собственные полигоны уже сегодня.

Прощай!

Спасибо Чампа Ло за иллюстрацию. Это было круто.