Системный дизайн сервиса поиска мест рядом: geohash, quadtree и кеширование

Как спроектировать поиск мест рядом вроде Yelp или 2ГИС на system design интервью: оценка нагрузки, geohash и quadtree, поиск по соседним ячейкам, кеширование, реплики и шардирование.

13 мин чтениясистемный дизайн · геоданные · кеширование · python

Коротко

ВопросРешение в этом разборе
Профиль нагрузкичтение на порядки чаще записи: тысячи поисков в секунду против десятков правок
Геоиндексgeohash в обычном B-tree индексе или quadtree в памяти; оба помещаются на одну машину
Поисксвоя ячейка + 8 соседей → фильтр по точному расстоянию → ранжирование → top K
Хранение местреляционная база, шардирование по place_id, реплики на чтение
Кешячейка → список id мест; карточка места → отдельный ключ
Свежестьновое место появляется в поиске через минуты, а не мгновенно, и это нормально

«Найдите рестораны в радиусе километра» — одна из самых популярных задач на секции системного дизайна. Она похожа на сервис такси, но устроена почти наоборот. У такси точки двигаются и обновляются сотни тысяч раз в секунду. У каталога мест точки стоят на месте: кафе не переезжает каждые четыре секунды. Зато поиск запускают постоянно, и он должен отвечать за десятки миллисекунд.

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

Общий порядок секции описан в статье про подходы к проектированию систем. Идём по нему.

Шаг 1. Требования

ВопросОтвет интервьюераЧто это меняет
Что ищет пользователь?места рядом с точкой в заданном радиусегеопоиск — ядро системы
Какие радиусы?от 500 м до 20 кминдекс должен работать на разных масштабах
Фильтры?категория, «открыто сейчас»фильтрация после геопоиска или внутри него
Владелец может добавить место?да, и править егопуть записи есть, но редкий
Как быстро правка видна в поиске?достаточно до конца дняможно перестраивать индекс пачками
Отзывы, фото, бронирование?вне рамоктолько поиск и карточка места

Нефункциональные требования:

  • Задержка поиска — десятки миллисекунд на p99 без учёта сети.
  • Высокая доступность чтения: если поиск лёг, приложение бесполезно. Запись может деградировать.
  • Данные о местах не теряются. Владелец, который завёл карточку, должен её увидеть, пусть и не сразу в поиске.

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

Шаг 2. Оценка нагрузки

dau = 100_000_000 # активных пользователей в день searches_per_user = 5 # поисков в день places = 200_000_000 # мест в базе place_bytes = 1_000 # название, адрес, категории, часы работы, рейтинг qps = dau * searches_per_user / 86_400 print(f"поиск: {qps:,.0f} QPS в среднем, {qps * 3:,.0f} в пик") print(f"данные мест: {places * place_bytes / 1e12:.1f} ТБ") # Геоиндекс: только id и координаты index_entry = 8 + 8 + 8 # id, lat, lon print(f"геоиндекс: {places * index_entry / 1e9:.1f} ГБ") writes_per_day = 1_000_000 # новых мест и правок в сутки print(f"записей: {writes_per_day / 86_400:.0f} в секунду")
поиск: 5,787 QPS в среднем, 17,361 в пик данные мест: 0.2 ТБ геоиндекс: 4.8 ГБ записей: 12 в секунду

Что из этого следует:

  1. Геоиндекс целиком помещается в память одной машины. 5 ГБ — немного. Шардировать индекс по географии не обязательно: проще держать полную копию на каждом сервере поиска и масштабироваться репликами.
  2. 17 тыс. QPS в пик — много для одного сервера с базой, но легко для десятка stateless-серверов поиска за балансировщиком.
  3. 12 записей в секунду — смешная нагрузка. Путь записи можно сделать простым и надёжным.
  4. Данные мест — сотни гигабайт. Помещаются в одну базу, но для запаса и отказоустойчивости их удобно шардировать.

Подробнее о таких прикидках — в статье об оценке нагрузки на салфетке.

Шаг 3. API

GET /v1/search/nearby?lat=55.75&lon=37.62&radius=1000&category=cafe&limit=20&cursor=... -> {places: [{id, name, lat, lon, distance_m, rating}], next_cursor} GET /v1/places/{id} карточка места POST /v1/places владелец добавляет место PUT /v1/places/{id} правка

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

Пагинация по курсору, а не по offset: при offset=200 серверу придётся заново найти и отсортировать первые 200 мест.

Шаг 4. Архитектура верхнего уровня

┌──► Search Service (×N, stateless) ──► Geo Index (в памяти) ──┐ Клиент ──► LB ──────┤ │ │ │ └──► Cache (Redis): ячейка → id, id → карточка │ │ └──► Place Service ──► Places DB (primary) ──► реплики ◄──────┘ │ └──► CDC / очередь ──► перестройка индекса
  • Search Service отвечает на «что рядом». Без состояния, масштабируется добавлением копий. Каждая держит в памяти полный геоиндекс или ходит в общий.
  • Place Service обслуживает карточки и правки. Пишет в primary, читает с реплик.
  • Places DB — реляционная база с местами. Схема простая, транзакции нужны только на запись.
  • Перестройка индекса забирает изменения из базы (через CDC или очередь) и обновляет индекс пачкой раз в несколько минут.

Балансировку и реплики подробно разбирают статьи про балансировку нагрузки и шардирование и репликацию.

Шаг 5. Геоиндекс

Наивное решение — WHERE lat BETWEEN ? AND ? AND lon BETWEEN ? AND ?. Обычный B-tree индекс по (lat, lon) сузит поиск только по первой колонке: найдёт полосу широт вокруг всей планеты и отфильтрует долготу перебором. Два отдельных индекса дадут два огромных множества, которые придётся пересекать. Почему так, рассказано в статье про индексы.

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

Geohash

Мир делится пополам по долготе, потом по широте, потом снова по долготе и так далее. Каждое деление — один бит: 1, если точка в правой (верхней) половине. Пять бит кодируются одним символом base32. Чем длиннее строка, тем меньше ячейка.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz" def geohash_encode(lat, lon, precision=6): lat_lo, lat_hi = -90.0, 90.0 lon_lo, lon_hi = -180.0, 180.0 bits, bit_count, even = 0, 0, True result = [] while len(result) < precision: if even: # чётные биты — долгота mid = (lon_lo + lon_hi) / 2 if lon >= mid: bits = bits * 2 + 1 lon_lo = mid else: bits = bits * 2 lon_hi = mid else: # нечётные — широта mid = (lat_lo + lat_hi) / 2 if lat >= mid: bits = bits * 2 + 1 lat_lo = mid else: bits = bits * 2 lat_hi = mid even = not even bit_count += 1 if bit_count == 5: # 5 бит -> один символ base32 result.append(BASE32[bits]) bits, bit_count = 0, 0 return "".join(result) print(geohash_encode(55.7539, 37.6208)) # ucfv0j — Красная площадь print(geohash_encode(55.7547, 37.6215)) # ucfv0j — ГУМ, та же ячейка

Главное свойство: общий префикс означает общую ячейку. Все места внутри ucfv0 начинаются с ucfv0, а значит, в отсортированном индексе лежат подряд. Поиск по ячейке — это WHERE geohash LIKE 'ucfv0%', то есть диапазон в обычном B-tree.

Размеры ячеек на экваторе (ближе к полюсам они сужаются по долготе):

ДлинаЯчейкаДля какого радиуса
439 × 19,5 км20 км
54,9 × 4,9 км2–5 км
61,2 × 0,6 км500 м – 1 км
7153 × 153 мдо 150 м

Подвох с границами. Обратное неверно: близкие точки не обязательно имеют общий префикс.

# Два кафе в 25 метрах друг от друга, но по разные стороны границы ячейки print(geohash_encode(55.75, 37.6171), geohash_encode(55.75, 37.6175)) # ucftpu ucfv0h

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

Поиск по ячейке и соседям

Ниже рабочая модель: отсортированный список ключей играет роль B-tree индекса в базе, а поиск по префиксу — это два бинарных поиска. Используем geohash_encode из примера выше.

import bisect import math def geohash_bbox(code): lat_lo, lat_hi, lon_lo, lon_hi = -90.0, 90.0, -180.0, 180.0 even = True for ch in code: val = BASE32.index(ch) for shift in range(4, -1, -1): bit = (val >> shift) & 1 if even: mid = (lon_lo + lon_hi) / 2 lon_lo, lon_hi = (mid, lon_hi) if bit else (lon_lo, mid) else: mid = (lat_lo + lat_hi) / 2 lat_lo, lat_hi = (mid, lat_hi) if bit else (lat_lo, mid) even = not even return lat_lo, lat_hi, lon_lo, lon_hi def cell_with_neighbors(code): """Ячейка и 8 соседей: сдвигаем центр на ширину/высоту ячейки.""" lat_lo, lat_hi, lon_lo, lon_hi = geohash_bbox(code) lat_c, lon_c = (lat_lo + lat_hi) / 2, (lon_lo + lon_hi) / 2 d_lat, d_lon = lat_hi - lat_lo, lon_hi - lon_lo cells = set() for dy in (-1, 0, 1): for dx in (-1, 0, 1): lon = (lon_c + dx * d_lon + 540) % 360 - 180 # перескок через 180-й меридиан lat = max(-89.999, min(89.999, lat_c + dy * d_lat)) cells.add(geohash_encode(lat, lon, len(code))) return cells def haversine_m(lat1, lon1, lat2, lon2): r = 6_371_000 p1, p2 = math.radians(lat1), math.radians(lat2) dp, dl = p2 - p1, math.radians(lon2 - lon1) a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2 return 2 * r * math.asin(math.sqrt(a)) class GeohashIndex: def __init__(self, places, precision=6): # Отсортированный список (geohash, id) — как B-tree индекс в базе self.precision = precision self.coords = {pid: (lat, lon) for pid, lat, lon in places} self.keys = sorted( (geohash_encode(lat, lon, 12), pid) for pid, lat, lon in places ) def _prefix_scan(self, prefix): # Все ключи, начинающиеся с prefix, лежат подряд: два бинарных поиска lo = bisect.bisect_left(self.keys, (prefix,)) hi = bisect.bisect_left(self.keys, (prefix + "~",)) return [pid for _, pid in self.keys[lo:hi]] def nearby(self, lat, lon, radius_m, limit=10): center = geohash_encode(lat, lon, self.precision) candidates = [] for cell in cell_with_neighbors(center): candidates.extend(self._prefix_scan(cell)) found = [] for pid in candidates: d = haversine_m(lat, lon, *self.coords[pid]) if d <= radius_m: found.append((round(d), pid)) return sorted(found)[:limit] places = [ ("cafe-a", 55.7500, 37.6171), ("cafe-b", 55.7500, 37.6175), # 25 м от cafe-a, но в соседней ячейке ("bar-c", 55.7520, 37.6200), ("museum", 55.7600, 37.6400), # ~1,7 км ("spb", 59.9343, 30.3351), # другой город ] idx = GeohashIndex(places, precision=6) print(idx.nearby(55.7500, 37.6172, radius_m=500)) # [(6, 'cafe-a'), (19, 'cafe-b'), (283, 'bar-c')]

Три этапа — это и есть весь поиск: кандидаты из 9 ячеек → точное расстояние → сортировка и top K. Ячейки дают грубый, но дешёвый фильтр; формула гаверсинуса отсекает углы квадрата, которые не попадают в круг. Для больших K вместо полной сортировки берут кучу размера K, как в задаче про top K элементов.

Точность подбирают по радиусу: ячейка должна быть не меньше радиуса, тогда 9 ячеек гарантированно покрывают круг. Если результатов мало (пригород, ночь, редкая категория), повторяем запрос на уровень грубее.

# Точность geohash -> примерная ширина ячейки в метрах на широте Москвы CELL_WIDTH_M = {4: 22_000, 5: 2_700, 6: 690, 7: 86} def nearby_at_least(index, lat, lon, k, max_radius_m=20_000): """Расширяем поиск, пока не наберём k мест или не упрёмся в предел.""" for precision in (7, 6, 5, 4): index.precision = precision radius = min(CELL_WIDTH_M[precision], max_radius_m) found = index.nearby(lat, lon, radius, limit=k) if len(found) >= k: return found return found print(nearby_at_least(idx, 55.7500, 37.6172, k=4)) # [(6, 'cafe-a'), (19, 'cafe-b'), (283, 'bar-c'), (1809, 'museum')]

В реальной базе geohash — просто колонка с индексом:

CREATE TABLE places ( id BIGINT PRIMARY KEY, name TEXT NOT NULL, category TEXT NOT NULL, lat DOUBLE PRECISION NOT NULL, lon DOUBLE PRECISION NOT NULL, geohash VARCHAR(12) NOT NULL ); CREATE INDEX places_geohash ON places (geohash text_pattern_ops); -- кандидаты из 9 ячеек; точное расстояние досчитывает сервис SELECT id, lat, lon FROM places WHERE geohash LIKE 'ucftpu%' OR geohash LIKE 'ucfv0h%' -- ... ещё 7 ячеек

Если в стеке есть PostGIS, на собеседовании стоит упомянуть, что ST_DWithin с GiST-индексом решает ту же задачу из коробки. В Redis есть команды GEOADD и GEOSEARCH: внутри это отсортированное множество, где score — 52-битный geohash. Но интервьюер обычно хочет услышать, как это устроено, а не название готового продукта.

Quadtree

Geohash делит мир на ячейки одинакового размера на каждом уровне. Это неудобно: в центре Москвы в ячейке длины 6 сотни заведений, а в тайге — ноль. Quadtree подстраивается под плотность: узел делится на четыре квадранта, только когда в нём больше заданного числа мест. Подробно структура разобрана в отдельной статье про quadtree, здесь — минимальная версия под нашу задачу.

class QuadTree: CAPACITY = 100 # максимум мест в листе, потом делим на 4 def __init__(self, lat_lo, lat_hi, lon_lo, lon_hi, depth=0): self.box = (lat_lo, lat_hi, lon_lo, lon_hi) self.depth = depth self.points = [] # (lat, lon, id) — только в листьях self.children = None def insert(self, lat, lon, pid): if self.children is not None: self._child_for(lat, lon).insert(lat, lon, pid) return self.points.append((lat, lon, pid)) if len(self.points) > self.CAPACITY and self.depth < 24: self._split() def _split(self): lat_lo, lat_hi, lon_lo, lon_hi = self.box lat_m, lon_m = (lat_lo + lat_hi) / 2, (lon_lo + lon_hi) / 2 d = self.depth + 1 self.children = [ QuadTree(lat_lo, lat_m, lon_lo, lon_m, d), # юго-запад QuadTree(lat_lo, lat_m, lon_m, lon_hi, d), # юго-восток QuadTree(lat_m, lat_hi, lon_lo, lon_m, d), # северо-запад QuadTree(lat_m, lat_hi, lon_m, lon_hi, d), # северо-восток ] for lat, lon, pid in self.points: self._child_for(lat, lon).insert(lat, lon, pid) self.points = [] def _child_for(self, lat, lon): lat_lo, lat_hi, lon_lo, lon_hi = self.box north = lat >= (lat_lo + lat_hi) / 2 east = lon >= (lon_lo + lon_hi) / 2 return self.children[north * 2 + east] def query(self, lat_lo, lat_hi, lon_lo, lon_hi, out): b = self.box if lat_hi < b[0] or lat_lo > b[1] or lon_hi < b[2] or lon_lo > b[3]: return out # прямоугольник запроса не пересекает узел if self.children is None: for lat, lon, pid in self.points: if lat_lo <= lat <= lat_hi and lon_lo <= lon <= lon_hi: out.append(pid) return out for child in self.children: child.query(lat_lo, lat_hi, lon_lo, lon_hi, out) return out

На тесте из 50 тыс. точек (90% в «городе», 10% равномерно по миру) дерево получилось из 1075 листьев глубиной до 15, а запрос по прямоугольнику совпал с полным перебором. Для 200 млн мест при 100 местах на лист это около 2 млн листьев и те же ~5 ГБ на точки.

Чем quadtree отличается от geohash на практике:

КритерийGeohashQuadtree
Где живётколонка в базе, обычный B-tree индексструктура в памяти сервиса
Неравномерная плотностьфиксированные ячейки, выбор точностидерево само мельчит плотные районы
Обновлениявставка строки, индекс обновит базанужна синхронизация между копиями в памяти
Старт сервисамгновенныйпостроение дерева из 200 млн точек — минуты
Сложность реализациинизкаясредняя: деление, удаление, слияние узлов

Хорошая позиция на интервью: начать с geohash как с простого и достаточного решения, а quadtree предложить, если интервьюер спросит про неравномерную плотность или K ближайших без фиксированного радиуса. Ещё стоит упомянуть Google S2 и Uber H3 — иерархические сетки на сфере, которые решают проблемы geohash с искажениями у полюсов; подробнее о них — в разборе сервиса такси.

Как обновлять quadtree

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

  • Перестройка по расписанию. Раз в N минут новый экземпляр строит дерево из снимка базы, прогревается и встаёт в балансировщик вместо старого. Простой и надёжный путь, требования на свежесть позволяют.
  • Инкрементальные обновления. Каждая копия подписана на поток изменений из базы и вставляет/удаляет точки на лету. Быстрее, но нужна блокировка или copy-on-write для узлов, которые одновременно читаются.

Важно не забыть про холодный старт: сервер, который строит дерево, не должен получать трафик. Для этого его отдают балансировщику только после прохождения readiness-проверки.

Шаг 6. Кеширование

При 17 тыс. QPS и данных, которые меняются раз в несколько минут, кеш — главный рычаг. Но наивный ключ lat,lon,radius бесполезен: координаты пользователей почти никогда не совпадают до шестого знака, и попаданий не будет.

Кешировать надо то, что повторяется:

КлючЗначениеTTL / инвалидация
cell:<geohash>список id мест в ячейкеминуты; сброс при правке места в ячейке
place:<id>карточка местачасы; сброс при правке
cell:<geohash>:<category>id мест категории в ячейкекак у ячейки

Поиск превращается в 9 чтений cell:* (одним MGET), локальный подсчёт расстояний и MGET карточек для top K. Популярные ячейки — центры городов — почти всегда в кеше. Стратегии записи и инвалидации подробно разобраны в статье про стратегии кеширования.

Ещё один слой — клиент и CDN. Ответ «что рядом с ячейкой ucfv0j» одинаков для всех пользователей в этой ячейке, если клиент округляет запрос до ячейки. Такой ответ можно кешировать на CDN на минуту, и значительная часть трафика вообще не дойдёт до серверов. Плата — чуть менее точная сортировка по расстоянию, которую клиент может досчитать сам.

Шаг 7. База и масштабирование

  • Места шардируются по place_id (например, через консистентное хеширование). Запрос карточки всегда идёт по id, так что поиск по шардам не нужен.
  • Геоиндекс не шардируется: 5 ГБ на копию — нормально. Масштабируем поиск количеством копий.
  • Если индекс перестанет помещаться (добавили отзывы с геометками, миллиарды объектов), шардируем по географии: регион или префикс geohash → шард. Тогда запрос у границы региона идёт в два шарда, а горячие регионы вроде Москвы придётся делить мельче.
  • Реплики на чтение у базы мест: карточки читаются в сотни раз чаще, чем правятся. Задержка репликации в секунды не страшна.

Шаг 8. Фильтры и ранжирование

Пользователь ищет не «всё рядом», а «открытые кофейни рядом с рейтингом выше 4». Два подхода:

  1. Геопоиск, затем фильтр. Берём кандидатов из ячеек, отсекаем по категории и часам работы. Просто, но если категория редкая, после фильтра останется мало, и придётся расширять радиус.
  2. Категория в ключе индекса. Отдельные индексы (category, geohash) или кеш cell:<geohash>:<category>. Быстро для частых категорий, но индексов становится много.

На практике совмещают: популярные категории — в ключе, остальное — фильтром. Финальное ранжирование учитывает не только расстояние, но и рейтинг, популярность, персонализацию. На интервью достаточно сказать, что ранжирование — отдельный сервис, который получает сотню кандидатов и возвращает top 20.

Узкие места и вопросы вглубь

  • «А если пользователь двигается?» Клиент повторяет поиск при смещении больше чем на половину ячейки, а не на каждый шаг GPS.
  • «Как найти K ближайших без радиуса?» Расширение радиуса по уровням geohash, как выше, или обход quadtree с приоритетной очередью по расстоянию до узла.
  • «Что у полюсов и на 180-м меридиане?» Ячейки geohash там сильно искажаются, а соседи «перескакивают» через границу. Код выше учитывает переход через меридиан; у полюсов мест мало, и проблему обычно признают, не решая. S2 и H3 этих проблем лишены.
  • «Владелец переместил место, а в кеше старая ячейка?» При правке инвалидируем и старую, и новую ячейку.

Типичные ошибки

  • Поиск только в своей ячейке. Места через дорогу, но за границей ячейки, пропадают. Всегда 9 ячеек.
  • Кеш по сырым координатам. Ноль попаданий. Кешируют ячейки и карточки.
  • Шардирование геоиндекса там, где он помещается в память. Лишняя сложность и запросы в несколько шардов без выигрыша.
  • Расстояние по евклидовой формуле в градусах. Градус долготы в Москве — около 63 км, а градус широты — 111 км. Нужна формула гаверсинуса или хотя бы поправка на косинус широты.
  • Сразу Elasticsearch / PostGIS без объяснения. Название инструмента — не дизайн. Сначала покажите, как работает индекс, потом скажите, какой продукт его реализует.
  • Одинаковые требования к записи и чтению. Строгая консистентность поиска здесь не нужна, и попытка её обеспечить усложнит всё остальное.

Как рассказывать на собеседовании

  1. Требования и прикидка — 5–7 минут. Главная фраза: «чтение доминирует, индекс помещается в память».
  2. API и схема верхнего уровня — 5 минут.
  3. Геоиндекс — основная часть, 15 минут: почему не BETWEEN, geohash, проблема границ и 9 ячеек, quadtree как альтернатива, сравнение.
  4. Кеширование и масштабирование — 10 минут.
  5. Остаток — вопросы вглубь: фильтры, K ближайших, обновление индекса.

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

Потренироваться в спокойной обстановке

Все задачи