Системный дизайн сервиса поиска мест рядом: geohash, quadtree и кеширование
Как спроектировать поиск мест рядом вроде Yelp или 2ГИС на system design интервью: оценка нагрузки, geohash и quadtree, поиск по соседним ячейкам, кеширование, реплики и шардирование.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Профиль нагрузки | чтение на порядки чаще записи: тысячи поисков в секунду против десятков правок |
| Геоиндекс | 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 в секунду
Что из этого следует:
- Геоиндекс целиком помещается в память одной машины. 5 ГБ — немного. Шардировать индекс по географии не обязательно: проще держать полную копию на каждом сервере поиска и масштабироваться репликами.
- 17 тыс. QPS в пик — много для одного сервера с базой, но легко для десятка stateless-серверов поиска за балансировщиком.
- 12 записей в секунду — смешная нагрузка. Путь записи можно сделать простым и надёжным.
- Данные мест — сотни гигабайт. Помещаются в одну базу, но для запаса и отказоустойчивости их удобно шардировать.
Подробнее о таких прикидках — в статье об оценке нагрузки на салфетке.
Шаг 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.
Размеры ячеек на экваторе (ближе к полюсам они сужаются по долготе):
| Длина | Ячейка | Для какого радиуса |
|---|---|---|
| 4 | 39 × 19,5 км | 20 км |
| 5 | 4,9 × 4,9 км | 2–5 км |
| 6 | 1,2 × 0,6 км | 500 м – 1 км |
| 7 | 153 × 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 на практике:
| Критерий | Geohash | Quadtree |
|---|---|---|
| Где живёт | колонка в базе, обычный 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». Два подхода:
- Геопоиск, затем фильтр. Берём кандидатов из ячеек, отсекаем по категории и часам работы. Просто, но если категория редкая, после фильтра останется мало, и придётся расширять радиус.
- Категория в ключе индекса. Отдельные индексы
(category, geohash)или кешcell:<geohash>:<category>. Быстро для частых категорий, но индексов становится много.
На практике совмещают: популярные категории — в ключе, остальное — фильтром. Финальное ранжирование учитывает не только расстояние, но и рейтинг, популярность, персонализацию. На интервью достаточно сказать, что ранжирование — отдельный сервис, который получает сотню кандидатов и возвращает top 20.
Узкие места и вопросы вглубь
- «А если пользователь двигается?» Клиент повторяет поиск при смещении больше чем на половину ячейки, а не на каждый шаг GPS.
- «Как найти K ближайших без радиуса?» Расширение радиуса по уровням geohash, как выше, или обход quadtree с приоритетной очередью по расстоянию до узла.
- «Что у полюсов и на 180-м меридиане?» Ячейки geohash там сильно искажаются, а соседи «перескакивают» через границу. Код выше учитывает переход через меридиан; у полюсов мест мало, и проблему обычно признают, не решая. S2 и H3 этих проблем лишены.
- «Владелец переместил место, а в кеше старая ячейка?» При правке инвалидируем и старую, и новую ячейку.
Типичные ошибки
- Поиск только в своей ячейке. Места через дорогу, но за границей ячейки, пропадают. Всегда 9 ячеек.
- Кеш по сырым координатам. Ноль попаданий. Кешируют ячейки и карточки.
- Шардирование геоиндекса там, где он помещается в память. Лишняя сложность и запросы в несколько шардов без выигрыша.
- Расстояние по евклидовой формуле в градусах. Градус долготы в Москве — около 63 км, а градус широты — 111 км. Нужна формула гаверсинуса или хотя бы поправка на косинус широты.
- Сразу Elasticsearch / PostGIS без объяснения. Название инструмента — не дизайн. Сначала покажите, как работает индекс, потом скажите, какой продукт его реализует.
- Одинаковые требования к записи и чтению. Строгая консистентность поиска здесь не нужна, и попытка её обеспечить усложнит всё остальное.
Как рассказывать на собеседовании
- Требования и прикидка — 5–7 минут. Главная фраза: «чтение доминирует, индекс помещается в память».
- API и схема верхнего уровня — 5 минут.
- Геоиндекс — основная часть, 15 минут: почему не
BETWEEN, geohash, проблема границ и 9 ячеек, quadtree как альтернатива, сравнение. - Кеширование и масштабирование — 10 минут.
- Остаток — вопросы вглубь: фильтры, K ближайших, обновление индекса.
Если на этом этапе вы уверенно рассуждаете о префиксах и границах ячеек, интервьюер почти наверняка спросит что-то вроде сервиса такси или доставки — там те же идеи, но точки двигаются. Для разминки перед секцией полезно освежить бинарный поиск: поиск по префиксу geohash — это ровно он.