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

Привет! Меня зовут Серёжа Синягин, я старший разработчик в Яндекс Еде и пишу на C++. В этой статье расскажу о задаче, с которой столкнулся в работе: как мы определяем, какие рестораны доступны пользователю для заказа. По пути заглянем во внутреннюю кухню, обсудим библиотеку H3 от Uber и разберём, как устроены R‑деревья и как мы используем их у себя.

Внутренняя кухня: как Яндекс Еда определяет доступность ресторана

Вы когда‑нибудь замечали, что стоимость или время доставки из одного и того же ресторана зависит от того, где вы находитесь в городе? Так и есть, и это не случайность. Всё дело в зонах доставки.

Зона доставки — это площадь, очерченная ломаной линией (полигон). И чтобы ресторан был доступен для заказа, в неё должны попадать координаты пользователя. У одного ресторана может быть сразу несколько таких зон. Они различаются геометрией, площадью и даже типом. И от того, в какую зону попал пользователь, может зависеть и стоимость, и время доставки.

Важно понимать, что зоны доставки в Яндекс Еде строятся по изохронам — областям, до границ которых время доставки примерно одинаково. Представьте себе: если Петя и Вася находятся в разных частях города, но в пределах одной зоны, значит, курьер доедет до обоих примерно за одно и то же время. Так и формируются границы зон — не по расстоянию, а по времени доставки.

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

При этом у одного ресторана может быть несколько зон: ближняя (на схеме — фиолетовая) и дальняя (зелёная). Чем дальше пользователь от ресторана, тем выше может быть стоимость и дольше время доставки. Это одна из причин, почему условия доставки могут различаться в зависимости от точки на карте.

Теперь обсудим, как всё это работает на практике. Допустим, Вася открывает приложение Яндекс Еда. Его координаты отправляются на бэкенд. Первый шаг: из всех ~500 000 ресторанов, доступных в системе, мы отбираем только те, которые вообще способны доставить заказ в его район. В центре Москвы это примерно 10 000 ресторанов. Следом запускаются дополнительные фильтры: например, проверка по расписанию — чтобы исключить те, что сейчас закрыты.

Сегодня мы сосредоточимся на одном ключевом этапе: как из полумиллиона ресторанов выбрать те, что доставляют именно Васе. Назовём этот механизм геопоиском, а выполняется он структурой данных — геоиндексом.

Как работает геопоиск и какие требования мы предъявляем к геоиндексу

Чтобы поиск по географии работал стабильно и быстро, геоиндекс в Яндекс Еде должен соответствовать сразу нескольким требованиям:

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

2. Быстрый геопоиск. Геопоиск — блокирующая операция во многих сценариях: от построения поисковой выдачи до отображения ресторанов в приложении. Поэтому он должен работать быстро — около 50 мс в 99-м перцентиле.

3. Экономное хранение. Сейчас в системе около 500 000 ресторанов и 3 млн зон доставки. В среднем на один ресторан приходится примерно шесть зон. Значит, геоиндекс должен эффективно использовать память и не иметь больших накладных расходов.

Один из первых вариантов, который приходит в голову при работе с географией, — это Geohash. Он кодирует координаты в строку, длина которой определяет точность. Чем строка длиннее, тем мельче «клетка» на координатной сетке. Простая и понятная идея.

Но для наших задач Geohash не подошёл. Его сложно применить к зонам доставки с произвольной геометрией: слишком неудобно совмещать строки‑коды с полигонами нетривиальной формы.

Вместо Geohash мы рассматривали два других инструмента:

• библиотеку H3 от Uber;

• структуру данных R‑деревья.

Разберёмся с каждым подробнее. Начнём с H3.

Что такое H3 и как он работает

H3 — это географическая система индексации, разработанная Uber. Она разбивает всю поверхность Земли на сетку из гексагонов (шестиугольников) и 12 обязательных пентагонов (пятиугольников). Эти 12 пентагонов нужны, чтобы корректно «замостить» шаровую поверхность без пробелов.

Каждому гексагону (и пентагону) присваивается уникальный идентификатор. Uber предоставляет библиотеку с быстрым API, которая позволяет сопоставить координаты определённому гексагон.

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

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

На примере Москвы это выглядит так: крупные (красные) гексагоны — с низким разрешением и большой площадью, мелкие (чёрные) — с высоким разрешением и более точной географией.

Как мы пытались применить H3 — и почему не вышло

Идея была простая и, на первый взгляд, рабочая: мы планировали разбивать всю географию на гексагоны определённого разрешения. Когда пользователь отправляет координаты, мы с помощью H3 быстро устанавливаем, в какой гексагон он попадает. Затем достаём из этого гексагона все зоны доставки, проверяем, какие из них действительно покрывают координату, — и формируем ресторанную выдачу.

Пример. У нас есть ресторан с фиолетовой зоной доставки, и она попадает в несколько гексагонов. Если пользователь (например, Петя) оказался в нужном гексагоне, мы находим его по ID, извлекаем из него нужную зону — и, если координаты попадают в полигон, ресторан отображается в выдаче.

Всё звучит логично. Алгоритм простой, библиотека быстрая. Казалось бы, идеальное решение, но на практике всё вышло не так гладко.

Напомню три ключевых требования к геоиндексу:

1. Быстрое обновление при изменении зон доставки.

2. Низкие тайминги поиска (вплоть до 50 мс в p99).

3. Разумный объём хранимых данных.

С последними двумя всё действительно хорошо:

• H3 даёт очень быстрый поиск за счёт эффективного API;

• память используется экономно, без лишнего overhead.

А вот с первым требованием — обновлением геоиндекса — начались проблемы. И причина — в особенностях иерархии H3.

В H3 каждый гексагон‑родитель может быть разбит на несколько гексагонов‑потомков. На схеме ниже видно: крупный красный гексагон (с низким разрешением) покрывает большую площадь, а внутри него расположены меньшие, синие, гексагоны.

Но здесь возникает важная проблема: площадь родителя не равна объединённой площади потомков. Из‑за этого появляются «дыры» — области, которые покрывает родитель, но не покрывают его потомки. Это разрушает возможность построить полноценную древовидную структуру, где можно эффективно спускаться от корня к листам и собирать нужные зоны.

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

Кому подойдёт Н3 

Несмотря на то что H3 нам не подошёл, это удобный, практичный и эффективный инструмент, который подходит для решения многих задач хранения и поиска геоданных. Например:

• для кластеризации геоданных;

• геоаналитики;

• любых задач, где геометрия зон не задана извне, а задаётся разработчиком.

Если вы можете заранее принять, что зоны доставки — это именно гексагоны, H3 вполне подойдёт. Но в Яндекс Еде алгоритм формирования зон доставки по изохронам не позволяет прийти к форме гексагонов, и их геометрия может быть самой причудливой — полигоны произвольной формы. Мы не можем подогнать их под сетку H3.

Поэтому мы перешли к следующему варианту — R‑деревьям.

Что такое R-деревья и почему они больше подошли для нашей задачи

В отличие от H3, R‑деревья оперируют не гексагонами, а прямоугольниками. Вся география делится на узлы — иерархическая структура.

• Листовые узлы содержат сами геообъекты, в нашем случае зоны доставки.

• Узлы ветвления (не листовые) группируют прямоугольники и позволяют строить иерархию.

Иерархия здесь строгая. Это означает, что площадь родителя всегда полностью покрывает площади всех потомков. Именно этого нам и не хватало в H3.

Ещё одна техническая деталь: при построении дерева можно задавать, сколько потомков максимум может быть у каждого внутреннего узла. Прямоугольники могут пересекаться между собой, и это нормальное поведение для R‑дерева.

Представим: у нас есть четыре зоны доставки в Москве. Для наглядности примера построим R‑дерево с числом потомков, равным двум.

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

Представим R‑дерево, построенное для четырёх зон доставки.

• Корень — узел A1.

• У него два потомка — B1 и B2, в которых уже хранятся зоны.

Теперь хотим добавить пятую зону доставки — она чуть южнее. Что происходит:

• Расширяем прямоугольник A1, чтобы он покрывал новую зону.

• Спускаемся в B1, так как именно туда должна попасть зона. Но B1 слишком мал, его тоже нужно расширить.

• Однако у B1 уже максимум потомков (напомним, мы ограничили их числом 2). Поэтому он расщепляется на два новых узла — C1 и C2. Зоны распределяются между ними.

В итоге получаем новое R‑дерево, которое удовлетворяет всем нашим ограничениям и в котором новая зона учтена.

Алгоритм поиска простой и эффективный:

1. На вход поступают координаты пользователя.

2. Мы проходим по всем прямоугольникам, в которые попадают эти координаты.

3. Спускаемся в листовые узлы.

4. Из узлов достаём зоны доставки и проверяем, какие реально покрывают координату (с учётом точной геометрии, не только прямоугольника).

5. Оставляем только подходящие зоны — это и есть финальный список.

В худшем случае алгоритм работает за O(N), если прямоугольники сильно пересекаются. Но в реальности таких ситуаций почти не бывает и алгоритм в среднем работает за O(logN).

Пример: поиск зоны для пользователя 

На схеме у нас всё то же дерево: корень A1, у него B1 и B2, у B1 — C1 и C2.

Допустим, пользователь оказался в районе жёлтого кружочка. Алгоритм работает так:

• Проверяем A1 → пользователь внутри.

• Проверяем потомков: в B2 не попадает, в B1 — да. Идём дальше.

• Внутри B1 → попадает в C2.

• В C2 лежат вторая и пятая зоны доставки. Из них только вторая покрывает координаты — её и возвращаем.

Если бы пользователь оказался на пересечении прямоугольников, пришлось бы проверить оба: и B1, и B2. Это предусмотрено алгоритмом.

По итогам экспериментов стало ясно: R‑дерево отлично подходит в качестве геоиндекса в Яндекс Еде. Оно позволяет быстро искать, легко обновлять и адекватно масштабируется.

Но на этом мы не остановились. Под капотом есть несколько дополнительных оптимизаций, которые ещё сильнее ускоряют работу.

Дополнительные оптимизации R-дерева

Оптимизация 1: разделение индексов для ресторанов и ритейла

В Яндекс Еде есть не только рестораны, но и ритейл (магазины, аптеки и т. д.). В некоторых пользовательских сценариях нужно получить выдачу только по ресторанам или только по ритейлу.

Чтобы не тратить ресурсы на лишние проверки, мы разделили геоиндексы: один для ресторанов, другой для ритейла. Это позволило ускорить геопоиск. Если требуется найти заведения и ресторанов и ритейла, поиск по двум индексам ведётся асинхронно.

Оптимизация 2: отдельный индекс для самовывоза

В Яндекс Еде можно не только заказывать доставку, но и забирать заказ самостоятельно. Этот сценарий покрывается зонами самовывоза, и они могут быть огромными — в десятки раз больше зон обычной доставки.

Если хранить самовывоз вместе с доставкой, большие полигоны замедляют поиск. Поэтому мы выделили отдельный индекс для самовывозных зон. Получилось компактно — всего ~60 000 элементов — и быстро.

Оптимизация 3: оптимальный размер узлов

В процессе нагрузочного тестирования мы подобрали оптимальное число потомков для каждого узла в R‑дереве. Лучший результат — при числе потомков, равном восьми. Именно это значение мы используем на проде.

На слайдах выше я показывал примеры с R‑деревьями, где у узлов было по два потомка, — это просто для наглядности. В реальности мы используем восемь.

Подводя итоги

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

И теперь мы можем вернуться к исходным требованиям — посмотреть, насколько они выполняются на практике.

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

Низкие тайминги геопоиска. Целью было около 50 мс в p99. Геопоиск работает за 45 мс в p99 и за 35 мс в p95. Получилось даже быстрее, чем планировали.

Объём хранимых данных. План: покрыть ~500 000 ресторанов и 3 млн зон доставки. Факт: индекс занимает 10 ГБ и полностью помещается в оперативной памяти, что, конечно, ускоряет доступ к данным.

Как время отклика зависит от региона. Время геопоиска зависит от плотности ресторанов:

• Центр Москвы: ~10 000 ресторанов → геопоиск занимает 30–40 мс.

• Меньшие города: ~2000 ресторанов → геопоиск укладывается в 5–10 мс.

Если вы работаете с похожими задачами, советуем присмотреться к R‑деревьям: они просты в применении, масштабируются и дают отличные результаты.

Если хотите углубиться в тему H3, советую посмотреть доклад авторов системы — очень подробный, технически насыщенный и отлично объясняет логику этой библиотеки.

А если у вас появились вопросы или захотите обсудить тему — пишите комментарии, буду рад пообщаться. Спасибо, что дочитали до конца!