Как Uber Обрабатывает Миллионы Поездок: Архитектурный Разбор Системы Геолокации и Диспетчеризации

Система Uber обрабатывает более 20 миллионов поездок ежедневно в 10 000+ городах по всему миру. Пиковая нагрузка достигает 50 000 запросов в секунду при задержке менее 100 мс. В этой статье мы детально разберем архитектурные решения, позволяющие обрабатывать миллионы одновременных геолокационных обновлений и обеспечивать оптимальную диспетчеризацию в реальном времени.

Архитектурный обзор системы

Система геолокации в реальном времени

Uber обрабатывает более 2 миллионов обновлений местоположения в секунду от водителей и пассажиров. Основные требования:

• Задержка обновления: < 5 секунд
• Точность позиционирования: 5-10 метров
• Доступность: 99.99%
• Глобальное покрытие: 70+ стран

// Архитектура Location Service на Go
package main

import (
    "context"
    "sync"
    "time"
    "github.com/go-redis/redis/v8"
)

type LocationUpdate struct {
    UserID    string    `json:"user_id"`
    Latitude  float64   `json:"latitude"`
    Longitude float64   `json:"longitude"`
    Bearing   float64   `json:"bearing"` // Направление движения
    Speed     float64   `json:"speed"`   // Скорость км/ч
    Timestamp time.Time `json:"timestamp"`
    Accuracy  float64   `json:"accuracy"` // Точность в метрах
}

type LocationService struct {
    redisClient *redis.ClusterClient
    geofence    GeofenceService
    mu          sync.RWMutex
    locations   map[string]LocationUpdate // In-memory кэш
}

func (ls *LocationService) UpdateLocation(ctx context.Context, update LocationUpdate) error {
    // Валидация координат
    if !ls.isValidCoordinate(update.Latitude, update.Longitude) {
        return ErrInvalidCoordinates
    }
    
    // Обновление in-memory кэша
    ls.mu.Lock()
    ls.locations[update.UserID] = update
    ls.mu.Unlock()
    
    // Асинхронное сохранение в Redis
    go ls.persistToRedis(ctx, update)
    
    // Проверка геозон
    go ls.checkGeofences(ctx, update)
    
    return nil
}

func (ls *LocationService) persistToRedis(ctx context.Context, update LocationUpdate) {
    key := fmt.Sprintf("location:%s", update.UserID)
    
    // GEOADD для пространственных запросов
    err := ls.redisClient.GeoAdd(ctx, "drivers:locations", 
        &redis.GeoLocation{
            Name:      update.UserID,
            Longitude: update.Longitude,
            Latitude:  update.Latitude,
        },
    ).Err()
    
    if err != nil {
        log.Error("Failed to update Redis GEO", err)
        return
    }
    
    // Сохранение полных данных
    data, _ := json.Marshal(update)
    ls.redisClient.SetEX(ctx, key, data, 30*time.Second)
}

func (ls *LocationService) GetNearbyDrivers(ctx context.Context, lat, lng float64, radius float64) ([]Driver, error) {
    // Поиск водителей в радиусе с использованием Redis GEO
    results, err := ls.redisClient.GeoRadius(ctx, "drivers:locations", 
        lng, lat, &redis.GeoRadiusQuery{
            Radius:      radius, // в км
            Unit:        "km",
            WithDist:    true,
            WithCoord:   true,
            WithGeoHash: true,
            Sort:        "ASC",
        },
    ).Result()
    
    if err != nil {
        return nil, err
    }
    
    var drivers []Driver
    for _, result := range results {
        // Получение детальной информации о водителе
        driverData, err := ls.redisClient.Get(ctx, fmt.Sprintf("location:%s", result.Name)).Result()
        if err == nil {
            var driver Driver
            json.Unmarshal([]byte(driverData), &driver)
            drivers = append(drivers, driver)
        }
    }
    
    return drivers, nil
}

// Оптимизированная структура для хранения геоданных
type SpatialIndex struct {
    quadTree   *QuadTree
    redis      *redis.Client
    cellSize   float64 // Размер ячейки сетки
    grid       map[string][]string // grid_cell -> [user_ids]
}

func (si *SpatialIndex) AddLocation(userID string, lat, lng float64) {
    cellKey := si.getGridCell(lat, lng)
    
    si.mu.Lock()
    si.grid[cellKey] = append(si.grid[cellKey], userID)
    si.mu.Unlock()
    
    // Обновление QuadTree для точного поиска
    si.quadTree.Insert(userID, lat, lng)
}

Алгоритм диспетчеризации и matching

// Алгоритм matching в Dispatch Service
package dispatch

type DispatchRequest struct {
    RiderID       string
    PickupLat     float64
    PickupLng     float64
    DropoffLat    float64
    DropoffLng    float64
    VehicleType   string
    PaymentMethod string
}

type DriverCandidate struct {
    DriverID     string
    ETA          time.Duration // Время до пассажира
    Distance     float64       // Расстояние в км
    Rating       float64
    VehicleType  string
    CurrentRides int           // Текущие поездки
}

type DispatchService struct {
    locationService *LocationService
    pricingService  *PricingService
    mapService      *MapService
    matchingAlgo    MatchingAlgorithm
}

func (ds *DispatchService) FindDriver(ctx context.Context, req DispatchRequest) (*DriverCandidate, error) {
    // Поиск кандидатов в радиусе 5 км
    candidates, err := ds.findDriverCandidates(ctx, req.PickupLat, req.PickupLng, 5.0)
    if err != nil {
        return nil, err
    }
    
    // Фильтрация по типу транспортного средства
    filteredCandidates := ds.filterByVehicleType(candidates, req.VehicleType)
    
    if len(filteredCandidates) == 0 {
        // Расширяем радиус поиска
        candidates, _ = ds.findDriverCandidates(ctx, req.PickupLat, req.PickupLng, 10.0)
        filteredCandidates = ds.filterByVehicleType(candidates, req.VehicleType)
    }
    
    // Расчет ETA для каждого кандидата
    for i := range filteredCandidates {
        eta, err := ds.mapService.CalculateETA(
            filteredCandidates[i].LastLat,
            filteredCandidates[i].LastLng,
            req.PickupLat,
            req.PickupLng,
        )
        if err == nil {
            filteredCandidates[i].ETA = eta
        }
    }
    
    // Выбор оптимального водителя
    bestDriver := ds.matchingAlgo.SelectBestDriver(filteredCandidates, req)
    
    return bestDriver, nil
}

// Усовершенствованный алгоритм выбора водителя
type AdvancedMatchingAlgorithm struct {
    config MatchingConfig
}

func (ama *AdvancedMatchingAlgorithm) SelectBestDriver(candidates []DriverCandidate, req DispatchRequest) *DriverCandidate {
    var bestScore float64 = -1
    var bestDriver *DriverCandidate
    
    for i := range candidates {
        score := ama.calculateDriverScore(candidates[i], req)
        
        if score > bestScore {
            bestScore = score
            bestDriver = &candidates[i]
        }
    }
    
    return bestDriver
}

func (ama *AdvancedMatchingAlgorithm) calculateDriverScore(driver DriverCandidate, req DispatchRequest) float64 {
    var score float64
    
    // Время подъезда (60% веса)
    etaScore := math.Max(0, 1-float64(driver.ETA)/ama.config.MaxETA)
    score += etaScore * 0.6
    
    // Рейтинг водителя (20% веса)
    ratingScore := driver.Rating / 5.0
    score += ratingScore * 0.2
    
    // Баланс нагрузки (10% веса)
    loadScore := math.Max(0, 1-float64(driver.CurrentRides)/ama.config.MaxConcurrentRides)
    score += loadScore * 0.1
    
    // Приемлемость поездки (10% веса)
    acceptanceScore := ama.calculateAcceptanceProbability(driver.DriverID, req)
    score += acceptanceScore * 0.1
    
    return score
}

Оптимизация производительности и масштабирования

Сравнение стратегий шардирования

// Реализация геошардирования
type GeoShardManager struct {
    shards map[string]*Shard // city_region -> Shard
    locator *ServiceLocator
}

func (gsm *GeoShardManager) GetShardForLocation(lat, lng float64) *Shard {
    cityRegion := gsm.locateCityRegion(lat, lng)
    return gsm.shards[cityRegion]
}

func (gsm *GeoShardManager) locateCityRegion(lat, lng float64) string {
    // Использование геокодирования для определения города/региона
    // Например: "sf_downtown", "nyc_manhattan"
    return gsm.locator.GetRegion(lat, lng)
}

// Конфигурация Redis Cluster с геошардированием
const redisConfig = {
    clusters: {
        'na-west': [
            {host: 'redis-na-west-1', port: 6379},
            {host: 'redis-na-west-2', port: 6380}
        ],
        'na-east': [
            {host: 'redis-na-east-1', port: 6379},
            {host: 'redis-na-east-2', port: 6380}
        ],
        'eu-central': [
            {host: 'redis-eu-central-1', port: 6379},
            {host: 'redis-eu-central-2', port: 6380}
        ]
    },
    routing: {
        'san_francisco': 'na-west',
        'new_york': 'na-east',
        'berlin': 'eu-central'
    }
};

Система расчета маршрутов и ETA

// Сервис расчета маршрутов с кэшированием
type RouteService struct {
    externalProviders []ExternalMapProvider
    internalEngine    *ValhallaEngine
    cache             *RouteCache
    metrics           *MetricsCollector
}

func (rs *RouteService) CalculateRoute(origin, destination Location, options RouteOptions) (*Route, error) {
    cacheKey := rs.generateCacheKey(origin, destination, options)
    
    // Попытка получить из кэша
    if cachedRoute, found := rs.cache.Get(cacheKey); found {
        rs.metrics.Increment("route_cache_hit")
        return cachedRoute, nil
    }
    
    rs.metrics.Increment("route_cache_miss")
    
    // Параллельный запрос к нескольким провайдерам
    var wg sync.WaitGroup
    results := make(chan *Route, len(rs.externalProviders)+1)
    
    // Запрос к внутреннему движку
    wg.Add(1)
    go func() {
        defer wg.Done()
        if route, err := rs.internalEngine.CalculateRoute(origin, destination, options); err == nil {
            results <- route
        }
    }()
    
    // Запросы к внешним провайдерам
    for _, provider := range rs.externalProviders {
        wg.Add(1)
        go func(p ExternalMapProvider) {
            defer wg.Done()
            if route, err := p.CalculateRoute(origin, destination, options); err == nil {
                results <- route
            }
        }(provider)
    }
    
    // Сбор результатов
    go func() {
        wg.Wait()
        close(results)
    }()
    
    // Выбор лучшего маршрута
    var bestRoute *Route
    for route := range results {
        if bestRoute == nil || route.Duration < bestRoute.Duration {
            bestRoute = route
        }
    }
    
    if bestRoute != nil {
        rs.cache.Set(cacheKey, bestRoute, 5*time.Minute)
    }
    
    return bestRoute, nil
}

// Адаптивный ETA с учетом трафика
type TrafficAwareETA struct {
    historicalData *HistoricalData
    realTimeTraffic *RealTimeTraffic
    weatherService *WeatherService
}

func (eta *TrafficAwareETA) CalculateETA(route *Route, startTime time.Time) time.Duration {
    baseETA := route.Duration
    
    // Корректировка на основе исторических данных
    hourOfDay := startTime.Hour()
    dayOfWeek := startTime.Weekday()
    trafficFactor := eta.historicalData.GetTrafficFactor(route, hourOfDay, dayOfWeek)
    
    // Корректировка на основе текущего трафика
    currentTraffic := eta.realTimeTraffic.GetTrafficConditions(route)
    trafficFactor *= currentTraffic
    
    // Корректировка на погоду
    weatherImpact := eta.weatherService.GetWeatherImpact(route)
    trafficFactor *= weatherImpact
    
    adjustedETA := time.Duration(float64(baseETA) * trafficFactor)
    
    return adjustedETA
}

Мониторинг и observability

// Комплексная система мониторинга
type DispatchMetrics struct {
    requests           prometheus.Counter
    requestDuration    prometheus.Histogram
    matchingTime       prometheus.Histogram
    driverResponseTime prometheus.Histogram
    errorRate          prometheus.Gauge
    activeDrivers      prometheus.Gauge
    activeRiders       prometheus.Gauge
}

func (dm *DispatchMetrics) RecordMatching(requestType string, duration time.Duration, success bool) {
    dm.requests.WithLabelValues(requestType).Inc()
    dm.requestDuration.WithLabelValues(requestType).Observe(duration.Seconds())
    
    if !success {
        dm.errorRate.WithLabelValues(requestType).Inc()
    }
}

// Распределенная трассировка
func InstrumentDispatch(ctx context.Context, req DispatchRequest) (*DriverCandidate, error) {
    span, ctx := opentracing.StartSpanFromContext(ctx, "dispatch.find_driver")
    defer span.Finish()
    
    span.SetTag("rider_id", req.RiderID)
    span.SetTag("pickup_lat", req.PickupLat)
    span.SetTag("pickup_lng", req.PickupLng)
    span.SetTag("vehicle_type", req.VehicleType)
    
    // Логирование ключевых этапов
    span.LogKV("event", "search_started", "radius_km", 5.0)
    
    candidates, err := findDriverCandidates(ctx, req.PickupLat, req.PickupLng, 5.0)
    if err != nil {
        span.SetTag("error", true)
        span.LogKV("error_message", err.Error())
        return nil, err
    }
    
    span.LogKV("event", "candidates_found", "count", len(candidates))
    
    // ... остальная логика
    
    return bestDriver, nil
}

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

Ключевые архитектурные решения и lessons learned

• Микросегментация сервисов: Разделение location, dispatch, pricing для независимого масштабирования
• Геошардирование: Оптимизация задержки через локализацию данных
• Многоуровневое кэширование: In-memory + Redis + CDN для разных типов данных
• Асинхронная обработка: Non-blocking операции для критического пути
• Circuit breakers: Защита от каскадных отказов при интеграции с внешними API
• Event-driven архитектура: Kafka для асинхронной обработки событий

Система Uber продолжает эволюционировать, обрабатывая растущие объемы данных и повышая точность диспетчеризации. Ключевой фактор успеха - способность балансировать между производительностью, надежностью и стоимостью, обеспечивая бесперебойный сервис для миллионов пользователей по всему миру.