Проектируем сервис поиска поблизости

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

Требования

Сначала форма, потом хранилище. У сервиса поиска рядом, как Yelp или поиск магазинов, узкий набор функций и очень специфический профиль нагрузки.

• Функциональные: по широте/долготе пользователя и радиусу (или числу «k ближайших») вернуть подходящие места, ранжированные. Сверху накладываются фильтры (категория, открыто-сейчас, рейтинг). Места меняются медленно; координаты кофейни по сути статичны.
• Нефункциональные: read-heavy с большим перевесом — поисков несравнимо больше, чем правок. Низкая задержка для подсказки (десятки миллисекунд). Допустима eventual-свежесть данных о местах; новый ресторан, появившийся с минутной задержкой, приемлем. Доступность важнее строгой консистентности.

Решающее наблюдение — асимметрия чтения/записи. Локации пишутся редко и читаются постоянно, поэтому можно позволить себе один раз построить тяжёлый индекс и амортизировать его на миллионах запросов — противоположность write-heavy задачи живой локации из следующего урока.

Оценки

Пусть 100 млн мест в мире и 200 млн поисков в сутки. Средний QPS поиска — 2×10^8 / ~10^5 с ≈ 2000, и провижиним на пик ~10 000 (обеденные и вечерние всплески). Каждый поиск не должен трогать 100 млн строк; он трогает несколько сотен кандидатов внутри нужных ячеек. Данные о месте малы — скажем, 1 КБ на запись, то есть ~100 ГБ всего, что легко индексируется и в основном кэшируется. Горячий рабочий набор — «центры популярных городов», доля от целого, поэтому кэширование по локации так окупается.

Высокоуровневая схема

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

Гео-индекс-сервис — сердце системы. Всё ниже работает на малом множестве кандидатов, которое даёт поиск по ячейкам, поэтому выбор индекса — центральное решение схемы.

Глубокое погружение

Выбор пространственного индекса

Есть три семейства, которые стоит знать, и правильный ответ зависит от паттерна доступа.

Geohash чередует биты широты и долготы в одну строку, где каждый добавленный символ уточняет локацию в меньший прямоугольник. Его большое достоинство: близкие точки обычно делят префикс, поэтому префиксное сканирование LIKE 'u4pruyd%' по обычному B-дереву находит соседей — без особого типа индекса. Большой изъян: свойство префикса верно лишь обычно: две точки в метре друг от друга могут лечь по разные стороны границы и не делить ни одного символа (классический пример — у экватора и нулевого меридиана). Ячейки geohash также неравномерны по реальной площади, потому что градусы долготы сжимаются к полюсам.

Quadtree рекурсивно делит пространство на четыре квадранта, разбивая ячейку только когда в ней больше некоторого порога точек. Это адаптируется к плотности: плотный Манхэттен получает глубокие мелкие ячейки; пустой океан — одну неглубокую. Эта адаптивность — выигрыш для перекошенных данных, но дерево — это stateful-структура в памяти, которую нужно строить, балансировать и перестраивать при сдвиге данных — больше операционного веса, чем у строкового префикса.

S2 (Google) проецирует сферу на куб и кривой Гильберта даёт каждой ячейке 64-битный ID; H3 (Uber) покрывает планету шестиугольниками. Оба чинят худшие проблемы geohash: ячейки куда ближе к равноплощадным, а ID на разных разрешениях вложены чисто. У шестиугольников H3 есть уникально полезное свойство — каждый сосед равноудалён (у шестиугольника шесть рёберных соседей, все на одном расстоянии), что делает операцию «расширить кольцо поиска» чистой. Это продакшен-выбор на масштабе; цена — зависимость от библиотеки и более крутая кривая входа.

Проблема границы ячейки

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

Решение — запрашивать ячейку и её соседей, а не одну ячейку. На квадратной сетке вы берёте ячейку плюс восемь окружающих (блок 3×3); в H3 — центральную ячейку плюс её kRing соседей под нужный радиус. Затем считаете точные ортодромические расстояния на объединении кандидатов и оставляете лишь тех, кто реально в радиусе. Индекс ячейки — это грубый фильтр, дёшево отбрасывающий те 99,99% мест, что нигде рядом; точная математика расстояний — тонкий фильтр над уцелевшими. Забыть разбиение «грубо-потом-точно» и доверять одной ячейке — каноническая ошибка поиска поблизости.

Узкие места и компромиссы

Первое узкое место — база данных, а не математика индекса, и кэширование по ячейке — рычаг. Так как нагрузка read-heavy, а локации меняются медленно, список кандидатов для данной ячейки стабилен минутами. Кэшируйте по ключу (cell_id, фильтры), и популярная центральная ячейка обслуживает тысячи поисков из памяти между обновлениями. Поэтому асимметрия чтения/записи из раздела требований — вся игра: вы платите за индекс один раз и собираете попадания в кэш вечно.

Второе — перекос плотности. Сетка фиксированного разрешения тратит усилия в океане и переполняется на Таймс-сквер, где одна ячейка может держать десять тысяч мест. Quadtree и переменное разрешение S2/H3 существуют именно для того, чтобы держать число кандидатов на запрос примерно ограниченным, где бы ни стоял пользователь.

Третье — ранжирование против расстояния. Возвращать геометрически ближайшие места — редко то, что хочет продукт; Yelp ранжирует смесью расстояния, рейтинга, популярности и рекламы. Поэтому поиск по ячейкам даёт кандидатов, а финальный порядок — шаг скоринга — и именно его вы кэшируете и тюните, отдельно от геометрии. Держите две заботы врозь: пространственный индекс отвечает «какие места правдоподобно рядом», сервис ранжирования — «в каком порядке их показать».