Геолокация и Proximity Search
Проектирование системы для поиска ближайших объектов (рестораны, магазины, водители) на основе географических координат.
Шаг 1: Требования
Функциональные требования
- Поиск ближайших объектов в заданном радиусе
- Добавление/обновление/удаление объектов с координатами
- Фильтрация по категории, рейтингу, часам работы
- Real-time обновление позиций (для движущихся объектов)
- Reverse geocoding (координаты -> адрес)
Нефункциональные требования
- Latency поиска < 100ms
- 500K+ бизнесов, 100M+ запросов в день
- Обновление позиции < 30 секунд для real-time объектов
- Высокая доступность (99.99%)
Шаг 2: High-Level архитектура
┌──────────┐ ┌───────────────┐ ┌────────────────────────┐
│ Client │────>│ API Gateway │────>│ Location Service │
│ │ │ │ │ ┌──────────────────┐ │
└──────────┘ └───────────────┘ │ │ Geospatial Index │ │
│ │ (Geohash/R-tree) │ │
│ └────────┬─────────┘ │
└───────────┼────────────┘
│
┌─────────────────────┼──────────────┐
│ │ │
┌──────▼──────┐ ┌─────────▼─────┐ ┌─────▼────────┐
│ PostgreSQL │ │ Redis │ │ Elasticsearch│
│ (PostGIS) │ │ (Real-time │ │ (Full-text │
│ │ │ positions) │ │ + Geo) │
└─────────────┘ └───────────────┘ └──────────────┘
Шаг 3: Geohash
Geohash кодирует 2D координаты (lat, lng) в строку. Чем длиннее строка, тем точнее область.
Geohash precision:
Length 1: ~5000 km
Length 2: ~1250 km
Length 3: ~156 km
Length 4: ~39 km
Length 5: ~5 km
Length 6: ~1.2 km
Length 7: ~150 m
Length 8: ~38 m
<?php
declare(strict_types=1);
final class GeohashEncoder
{
private const BASE32 = '0123456789bcdefghjkmnpqrstuvwxyz';
/**
* Encode latitude/longitude to geohash string
*/
public function encode(float $latitude, float $longitude, int $precision = 6): string
{
$latRange = [-90.0, 90.0];
$lngRange = [-180.0, 180.0];
$hash = '';
$bit = 0;
$ch = 0;
$isLng = true; // Start with longitude
while (strlen($hash) < $precision) {
if ($isLng) {
$mid = ($lngRange[0] + $lngRange[1]) / 2;
if ($longitude >= $mid) {
$ch |= (1 << (4 - $bit));
$lngRange[0] = $mid;
} else {
$lngRange[1] = $mid;
}
} else {
$mid = ($latRange[0] + $latRange[1]) / 2;
if ($latitude >= $mid) {
$ch |= (1 << (4 - $bit));
$latRange[0] = $mid;
} else {
$latRange[1] = $mid;
}
}
$isLng = !$isLng;
$bit++;
if ($bit === 5) {
$hash .= self::BASE32[$ch];
$bit = 0;
$ch = 0;
}
}
return $hash;
}
/**
* Decode geohash to bounding box [lat_min, lat_max, lng_min, lng_max]
*/
public function decode(string $hash): array
{
$latRange = [-90.0, 90.0];
$lngRange = [-180.0, 180.0];
$isLng = true;
for ($i = 0; $i < strlen($hash); $i++) {
$char = $hash[$i];
$value = strpos(self::BASE32, $char);
for ($bit = 4; $bit >= 0; $bit--) {
if ($isLng) {
$mid = ($lngRange[0] + $lngRange[1]) / 2;
if (($value >> $bit) & 1) {
$lngRange[0] = $mid;
} else {
$lngRange[1] = $mid;
}
} else {
$mid = ($latRange[0] + $latRange[1]) / 2;
if (($value >> $bit) & 1) {
$latRange[0] = $mid;
} else {
$latRange[1] = $mid;
}
}
$isLng = !$isLng;
}
}
return [
'lat' => ($latRange[0] + $latRange[1]) / 2,
'lng' => ($lngRange[0] + $lngRange[1]) / 2,
'lat_min' => $latRange[0],
'lat_max' => $latRange[1],
'lng_min' => $lngRange[0],
'lng_max' => $lngRange[1],
];
}
/**
* Get all 8 neighboring geohash cells
*/
public function neighbors(string $hash): array
{
$center = $this->decode($hash);
$lat = $center['lat'];
$lng = $center['lng'];
$latStep = $center['lat_max'] - $center['lat_min'];
$lngStep = $center['lng_max'] - $center['lng_min'];
$precision = strlen($hash);
$neighbors = [];
$directions = [
'n' => [$latStep, 0],
'ne' => [$latStep, $lngStep],
'e' => [0, $lngStep],
'se' => [-$latStep, $lngStep],
's' => [-$latStep, 0],
'sw' => [-$latStep, -$lngStep],
'w' => [0, -$lngStep],
'nw' => [$latStep, -$lngStep],
];
foreach ($directions as $dir => [$dLat, $dLng]) {
$neighbors[$dir] = $this->encode($lat + $dLat, $lng + $dLng, $precision);
}
return $neighbors;
}
}
Proximity Search с Geohash
<?php
declare(strict_types=1);
final class ProximitySearchService
{
public function __construct(
private readonly GeohashEncoder $geohash,
private readonly \Redis $redis,
private readonly \PDO $db,
) {}
/**
* Find nearby places using geohash prefix matching
*/
public function findNearby(
float $lat,
float $lng,
float $radiusKm,
string $category = '',
int $limit = 20,
): array {
// 1. Determine geohash precision based on radius
$precision = $this->radiusToPrecision($radiusKm);
// 2. Get center geohash and neighbors
$centerHash = $this->geohash->encode($lat, $lng, $precision);
$neighbors = $this->geohash->neighbors($centerHash);
$searchHashes = array_merge([$centerHash], array_values($neighbors));
// 3. Get candidates from all cells
$candidates = [];
foreach ($searchHashes as $hash) {
$key = $category
? "geo:{$category}:{$hash}"
: "geo:all:{$hash}";
$members = $this->redis->sMembers($key);
$candidates = array_merge($candidates, $members);
}
// 4. Calculate exact distance and filter
$results = [];
foreach ($candidates as $placeJson) {
$place = json_decode($placeJson, true);
$distance = $this->haversineDistance($lat, $lng, $place['lat'], $place['lng']);
if ($distance <= $radiusKm) {
$results[] = [
'id' => $place['id'],
'name' => $place['name'],
'lat' => $place['lat'],
'lng' => $place['lng'],
'distance_km' => round($distance, 2),
];
}
}
// 5. Sort by distance
usort($results, fn ($a, $b) => $a['distance_km'] <=> $b['distance_km']);
return array_slice($results, 0, $limit);
}
/**
* Index a place for proximity search
*/
public function indexPlace(Place $place): void
{
$precision = 6; // ~1.2 km cells
$hash = $this->geohash->encode($place->lat, $place->lng, $precision);
$data = json_encode([
'id' => $place->id,
'name' => $place->name,
'lat' => $place->lat,
'lng' => $place->lng,
]);
// Index in category-specific and "all" sets
$this->redis->sAdd("geo:all:{$hash}", $data);
$this->redis->sAdd("geo:{$place->category}:{$hash}", $data);
}
/**
* Haversine formula for distance between two coordinates
*/
private function haversineDistance(
float $lat1, float $lng1,
float $lat2, float $lng2,
): float {
$earthRadius = 6371.0; // km
$dLat = deg2rad($lat2 - $lat1);
$dLng = deg2rad($lng2 - $lng1);
$a = sin($dLat / 2) ** 2
+ cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * sin($dLng / 2) ** 2;
$c = 2 * atan2(sqrt($a), sqrt(1 - $a));
return $earthRadius * $c;
}
private function radiusToPrecision(float $radiusKm): int
{
return match (true) {
$radiusKm <= 0.1 => 7, // ~150m
$radiusKm <= 1 => 6, // ~1.2km
$radiusKm <= 5 => 5, // ~5km
$radiusKm <= 40 => 4, // ~39km
default => 3, // ~156km
};
}
}
Альтернатива: Redis GEO
<?php
declare(strict_types=1);
final class RedisGeoService
{
public function __construct(
private readonly \Redis $redis,
) {}
public function addPlace(string $category, string $placeId, float $lat, float $lng): void
{
$this->redis->geoAdd("places:{$category}", $lng, $lat, $placeId);
$this->redis->geoAdd('places:all', $lng, $lat, $placeId);
}
public function findNearby(
string $category,
float $lat,
float $lng,
float $radiusKm,
int $limit = 20,
): array {
$key = $category ? "places:{$category}" : 'places:all';
// GEORADIUS returns sorted by distance
return $this->redis->geoRadius(
$key,
$lng,
$lat,
$radiusKm,
'km',
[
'WITHDIST',
'WITHCOORD',
'COUNT' => $limit,
'ASC',
],
);
}
public function updatePosition(string $placeId, float $lat, float $lng): void
{
$this->redis->geoAdd('places:all', $lng, $lat, $placeId);
}
}
Шаг 4: Сравнение подходов
| Подход | Плюсы | Минусы | Когда использовать |
|---|---|---|---|
| Geohash + Redis | Простой, быстрый | Edge cases на границах | Статичные объекты |
| Redis GEO | Встроенный, точный | Все данные в памяти | < 1M объектов |
| PostGIS | Мощные spatial запросы | Медленнее Redis | Сложные geo-запросы |
| Quadtree | Адаптивный к плотности | Сложная реализация | Неравномерная плотность |
| R-tree | Оптимален для прямоугольников | Сложная реализация | Регионы, полигоны |
Шаг 5: Масштабирование
| Компонент | Стратегия |
|---|---|
| Geo index | Redis Cluster (sharded by geohash prefix) |
| Place data | PostgreSQL + PostGIS |
| Real-time positions | Redis (TTL-based expiry) |
| Search + filter | Elasticsearch с geo_distance |
Возможные вопросы интервьюера
-
Geohash vs Quadtree?
- Geohash: простой, хорошо для кэша, prefix-based
- Quadtree: лучше при неравномерной плотности
- Geohash для большинства случаев
-
Как обрабатывать edge case на границе geohash ячеек?
- Всегда проверять соседние ячейки (8 neighbors)
- Финальная фильтрация по точному расстоянию (Haversine)
-
Как обновлять позицию движущегося объекта?
- Redis GEO с periodic updates (каждые 5-15 секунд)
- Pub/Sub для real-time уведомлений
- TTL для автоматического удаления неактивных
-
Как масштабировать до миллиардов точек?
- Sharding по geohash prefix (региональный)
- Tiered approach: Redis (hot) + DB (all)
- Spatial partitioning