Ride-sharing Matching — geolocalização, tempo real e consistência

Em 2014, o Uber tinha um problema chamado internamente de "phantom cars". Motoristas apareciam no mapa do app do passageiro, mas quando o passageiro solicitava a corrida, nenhum motorista estava disponível — o mapa mostrava uma realidade que já não existia. A causa era a diferença entre o modelo de dados do sistema de localização e a realidade física: carros em movimento, conectividade intermitente, e atualizações de GPS que chegavam com atraso ou fora de ordem. O sistema de localização não refletia "onde o carro está agora" mas "onde o carro estava quando a última atualização chegou" — uma distinção crítica quando o carro se move a 60 km/h.

O sistema de matching de um ride-sharing combina três classes de problemas que raramente aparecem juntos em outros sistemas: indexação espacial de dados que mudam continuamente (a localização de cada motorista muda a cada 4 segundos), coordenação distribuída para evitar que dois passageiros reservem o mesmo motorista simultaneamente, e comunicação bidirecional em tempo real entre dois tipos de clientes móveis (motorista e passageiro) através de uma infraestrutura de servidores stateful.

Requisitos e estimation

Requisitos funcionais:

• Motorista: atualizar localização em tempo real, receber solicitações de corrida, aceitar/recusar
• Passageiro: ver motoristas disponíveis no mapa, solicitar corrida, acompanhar o motorista em tempo real
• Sistema: fazer matching motorista-passageiro em <5s, gerenciar o ciclo de vida da corrida

# Estimation
# Motoristas ativos globalmente no pico: 5M (dos 10M cadastrados)
# Passageiros ativos no pico: 20M

# Location updates:
# 5M motoristas × 1 update a cada 4s = 1.250.000 writes/s
# Cada update: driver_id + lat + lng + timestamp = ~50 bytes
# Throughput: 1.25M × 50B = 62.5 MB/s de writes de localização

# Matching requests:
# Suposição: 10M corridas/dia → ~116 corridas/s → pico ~350/s
# Cada matching: busca de motoristas próximos + oferta + aceite

# Real-time tracking durante corridas:
# 2M corridas simultâneas no pico × 1 update/s de posição = 2M reads/s
# (passageiro acompanhando motorista no mapa durante a corrida)

# Conclusão crítica:
# O gargalo do sistema não é matching (350/s — trivial)
# É a atualização de localização: 1.25M writes/s em um store espacial

O problema de indexação espacial

A query fundamental do sistema é: "dado que um passageiro está em (lat, lng), quais motoristas disponíveis estão dentro de X km?" Essa é uma busca por proximidade num espaço bidimensional contínuo — um problema que banco de dados relacionacionais resolvem mal sem extensões especializadas.

-- Abordagem ingênua: bounding box
SELECT driver_id, lat, lng
FROM drivers_available
WHERE lat BETWEEN :lat - 0.045 AND :lat + 0.045  -- ~5km em latitude
  AND lng BETWEEN :lng - 0.055 AND :lng + 0.055  -- ~5km em longitude (varia com lat)
ORDER BY (lat - :lat)^2 + (lng - :lng)^2  -- distância euclidiana aproximada
LIMIT 20;

-- Problemas:
-- 1. Full table scan se não há índice adequado
-- 2. Índices B-tree numa coluna não ajudam para queries em duas colunas simultaneamente
-- 3. Com 5M drivers ativos e 1.25M updates/s: índice fica sob write pressure constante
-- 4. Distância euclidiana em lat/lng ignora a curvatura da Terra (imprecisa em distâncias >10km)

-- Alternativa: PostGIS (extensão espacial do PostgreSQL)
-- Usa índice GiST (R-tree) otimizado para dados espaciais
SELECT driver_id,
       ST_Distance(location::geography, ST_MakePoint(:lng, :lat)::geography) AS dist_meters
FROM drivers_available
WHERE ST_DWithin(location::geography, ST_MakePoint(:lng, :lat)::geography, 5000) -- 5km
ORDER BY dist_meters
LIMIT 20;

-- PostGIS funciona bem para queries ocasionais, mas
-- 1.25M writes/s invalidam o índice GiST continuamente → performance degrada sob carga

Geohash — indexação espacial com strings

Geohash é uma técnica de discretização do espaço geográfico: o mundo é dividido recursivamente em células retangulares, e cada célula recebe uma string identificadora. Strings com o mesmo prefixo representam células adjacentes — o que transforma busca espacial em busca por prefixo de string, uma operação que bancos de dados e sistemas de cache conhecem muito bem.

# Como geohash funciona:
# 1. Dividir o mundo em 32 células com um caractere (base32):
#    Longitude: [-180, 0) → bit 0 | [0, 180] → bit 1
#    Latitude:  [-90,  0) → bit 0 | [0,  90] → bit 1
#    ... intercalar bits de longitude e latitude ...
#    Codificar em base32 (0-9 + b-z exceto a, i, l, o)

# Precisão por número de caracteres:
# 1 char:  ±2500km   (5000×5000 km)  — um por continente
# 4 chars: ±20km     (40×20 km)      — nível de cidade
# 6 chars: ±610m     (1.2×0.6 km)    — bairro
# 7 chars: ±76m      (150×75 m)      — quadra
# 8 chars: ±19m      (40×20 m)       — edifício
# 9 chars: ±2.4m                     — precisão de GPS

import geohash2  # Python library

# Motorista em São Paulo (Av. Paulista)
driver_lat, driver_lng = -23.5613, -46.6561
gh = geohash2.encode(driver_lat, driver_lng, precision=7)
# → "6gyf4rr" (precisão de ~75m, suficiente para ride-sharing)

# Passageiro a 500m de distância
passenger_lat, passenger_lng = -23.5567, -46.6584
passenger_gh = geohash2.encode(passenger_lat, passenger_lng, precision=7)
# → "6gyf4rr" (mesma célula!) ou "6gyf4rq" (célula adjacente)

# A propriedade crítica:
# Mesma célula geohash = geograficamente próximos (quase sempre)
# Mas: pontos próximos podem ter geohashes diferentes se estão em lados opostos
# de uma fronteira de célula → solução: buscar a célula central + 8 células vizinhas

As 9 células do geohash

# O problema da fronteira de célula:
# Dois pontos separados por 10m podem estar em células geohash diferentes
# se estão em lados opostos da fronteira da célula.

# Solução: buscar sempre a célula do passageiro + 8 células vizinhas

neighbors = geohash2.neighbors("6gyf4rr")
# → ["6gyf4rx", "6gyf4rw", "6gyf4rq", "6gyf4rm", "6gyf4rp",
#    "6gyf4r8", "6gyf4r9", "6gyf4rd"]  # 8 vizinhos + célula central

search_cells = [passenger_gh] + neighbors  # 9 células ao total

# No Redis: para cada célula, buscar drivers disponíveis
# SMEMBERS drivers:6gyf4rr → {driver_id_1, driver_id_2, ...}
# SMEMBERS drivers:6gyf4rx → {driver_id_5, driver_id_8, ...}
# ...
# União de todos os 9 sets → candidatos para matching
# Filtrar por distância real (haversine) para remover falsos positivos nas bordas

Redis GEO — a solução de produção

Redis tem comandos GEO nativos desde a versão 3.2 (2016), baseados em geohash e implementados sobre Sorted Set. Eles resolvem exatamente o problema de busca por proximidade com performance de Redis:

# Estrutura de dados: Redis Sorted Set
# Score = geohash de 52 bits (representação interna do Redis GEO)
# Member = driver_id

# Ao receber update de localização do motorista:
GEOADD drivers_available -46.6561 -23.5613 "driver:12345"
# Complexidade: O(log N) onde N é o número de motoristas no set
# Throughput: Redis processa ~100k GEOADD/s por thread

# Ao buscar motoristas próximos ao passageiro:
GEOSEARCH drivers_available
  FROMLONLAT -46.6584 -23.5567  # posição do passageiro
  BYRADIUS 5 km
  ASC                           # ordenado por distância
  COUNT 20                      # top 20 mais próximos
  WITHCOORD                     # retornar coordenadas
  WITHDIST                      # retornar distância em km

# Resultado:
# [
#   ["driver:12345", 0.42, [-46.6561, -23.5613]],  # 420m de distância
#   ["driver:67890", 1.13, [-46.6623, -23.5501]],  # 1.13km
#   ...
# ]

# Remover motorista quando ele aceita uma corrida (não mais disponível):
ZREM drivers_available "driver:12345"

# Verificar posição de um motorista específico (durante a corrida):
GEOPOS drivers_on_trip "driver:12345"

Sharding do Redis GEO para 1.25M updates/s

# 1.25M GEOADD/s está acima do que um único Redis node aguenta.
# Sharding por região geográfica (geohash de 1-2 chars = país/continente):

# Shard mapping (geohash prefix → Redis instance):
SHARD_MAP = {
    "6g": "redis-sa-east",        # América do Sul
    "9q": "redis-us-west",        # EUA Costa Oeste
    "dr": "redis-us-east",        # EUA Costa Leste
    "u0": "redis-eu-west",        # Europa Ocidental
    "w3": "redis-ap-southeast",   # Ásia Sudeste
    # ...
}

def get_shard(lat, lng):
    gh_prefix = geohash2.encode(lat, lng, precision=2)
    return SHARD_MAP.get(gh_prefix, "redis-default")

# Na prática, com 5M motoristas ativos distribuídos globalmente:
# ~500k por região → 500k ÷ 4s = 125k updates/s por shard
# Um Redis node aguenta 100k ops/s → 2 nodes por região por segurança

# Busca de motoristas: sempre no shard da região do passageiro
# (corridas cross-região são raras e tratadas com routing especial)

O matching service — pontuação e oferta

# Fluxo de matching ao receber solicitação de corrida:
def match_passenger(passenger_id, passenger_lat, passenger_lng, vehicle_type):
    # 1. Buscar candidatos próximos (Redis GEO)
    candidates = redis.geosearch(
        f"drivers_available:{get_shard(passenger_lat, passenger_lng)}",
        fromlonlat=(passenger_lng, passenger_lat),
        byradius=5,  # km
        unit="km",
        count=50,    # top 50 candidatos antes de filtrar
        sort="ASC",
        withdist=True, withcoord=True
    )

    # 2. Filtrar por tipo de veículo e rating mínimo
    eligible = []
    for driver_id, distance_km, (lng, lat) in candidates:
        driver = driver_service.get(driver_id)
        if driver.vehicle_type != vehicle_type: continue
        if driver.rating < 4.5: continue
        eligible.append((driver_id, distance_km, driver))

    if not eligible:
        return no_drivers_available()

    # 3. Calcular score para cada candidato
    def score(driver_id, distance_km, driver):
        eta_seconds = routing_service.get_eta(driver.lat, driver.lng,
                                              passenger_lat, passenger_lng)
        return (
            0.5 * (1 / (eta_seconds + 1)) +   # ETA: quanto menor, melhor
            0.3 * (driver.rating / 5.0) +      # Rating normalizado
            0.2 * (driver.acceptance_rate)     # Taxa de aceite do motorista
        )

    ranked = sorted(eligible,
                    key=lambda x: score(x[0], x[1], x[2]),
                    reverse=True)

    # 4. Oferecer para motoristas em ordem de score até aceite
    for driver_id, distance_km, driver in ranked:
        result = offer_to_driver(driver_id, passenger_id, timeout_seconds=15)
        if result == "ACCEPTED":
            return create_trip(driver_id, passenger_id)
        # Se DECLINED ou TIMEOUT: tentar próximo

A race condition — dois passageiros, um motorista

O problema de consistência mais crítico do sistema: se dois passageiros A e B estão próximos e o motorista D é o melhor match para ambos, ambos os matching services vão selecionar D simultaneamente. O motorista recebe duas solicitações e aceita uma — qual dos dois passageiros fica sem carro?

# Solução: distributed lock com Redis SET NX (Set if Not eXists)

def offer_to_driver(driver_id, passenger_id, timeout_seconds=15):
    lock_key = f"driver_lock:{driver_id}"

    # Tentativa atômica de adquirir o lock
    # NX = só seta se a chave não existir
    # EX = TTL em segundos (release automático se o processo morrer)
    acquired = redis.set(
        lock_key,
        passenger_id,     # valor = quem adquiriu o lock
        nx=True,          # only if not exists
        ex=timeout_seconds + 5  # TTL = timeout do motorista + buffer
    )

    if not acquired:
        # Driver já está sendo oferecido para outro passageiro
        # Quem tem o lock pode verificar: GET driver_lock:{driver_id}
        # → retorna o passenger_id que tem o lock
        return "DRIVER_BUSY"

    try:
        # Lock adquirido: enviar notificação para o motorista via WebSocket
        websocket_gateway.send(driver_id, {
            "type": "TRIP_REQUEST",
            "passenger_id": passenger_id,
            "pickup_location": passenger_location,
            "expires_at": time.now() + timeout_seconds
        })

        # Aguardar resposta do motorista (com timeout)
        response = wait_for_driver_response(driver_id, timeout=timeout_seconds)

        if response == "ACCEPTED":
            return "ACCEPTED"
        else:
            return "DECLINED"  # ou TIMEOUT

    finally:
        # Liberar o lock SEMPRE — mesmo em exceção
        # Usar Lua script para garantir atomicidade: só deletar se eu sou o dono
        lua_script = """
        if redis.call("get", KEYS[1]) == ARGV[1] then
            return redis.call("del", KEYS[1])
        else
            return 0
        end
        """
        redis.eval(lua_script, 1, lock_key, passenger_id)

O script Lua garante que apenas o detentor original do lock pode liberá-lo — evitando o cenário onde o lock expira durante o processamento, outro passageiro adquire o lock, e então o primeiro libera o lock do segundo.

Trip state machine

# Estados de uma corrida e transições válidas:

STATES = {
    "MATCHING":           ["DRIVER_EN_ROUTE", "CANCELLED"],
    "DRIVER_EN_ROUTE":    ["DRIVER_ARRIVED", "CANCELLED"],
    "DRIVER_ARRIVED":     ["TRIP_STARTED", "CANCELLED"],
    "TRIP_STARTED":       ["TRIP_COMPLETED", "CANCELLED"],
    "TRIP_COMPLETED":     [],  # terminal
    "CANCELLED":          [],  # terminal
}

def transition_trip_state(trip_id, new_state, actor_id):
    trip = redis.hgetall(f"trip:{trip_id}")
    current_state = trip["state"]

    if new_state not in STATES[current_state]:
        raise InvalidTransition(f"{current_state} → {new_state} não permitido")

    # Transição atômica com Lua script (evita race condition de duas transições simultâneas)
    lua_script = """
    local current = redis.call("hget", KEYS[1], "state")
    if current ~= ARGV[1] then
        return redis.error_reply("STATE_CHANGED: expected " .. ARGV[1] .. " got " .. current)
    end
    redis.call("hset", KEYS[1], "state", ARGV[2])
    redis.call("hset", KEYS[1], "updated_at", ARGV[3])
    return "OK"
    """
    redis.eval(lua_script, 1,
               f"trip:{trip_id}",
               current_state, new_state, str(time.now()))

    # Persistir no banco para durabilidade (async, fora do caminho crítico)
    db_write_queue.publish({
        "trip_id": trip_id,
        "new_state": new_state,
        "actor_id": actor_id,
        "timestamp": time.now()
    })

    # Notificar ambas as partes via WebSocket
    notify_trip_participants(trip_id, new_state)

WebSocket com pub/sub — comunicação em tempo real

Tanto motoristas quanto passageiros precisam de comunicação bidirecional em tempo real. HTTP polling é inadequado (latência alta, desperdício de banda). WebSocket mantém uma conexão TCP persistente — mas cria um problema de roteamento: como o matching service (running on server A) envia uma mensagem para um motorista conectado via WebSocket no server B?

# Problema:
# Driver D está conectado ao WebSocket server WS-2
# Matching service está rodando no App server AS-1
# AS-1 precisa enviar uma mensagem para D, mas não tem a conexão de D

# Solução: pub/sub via Redis

# Ao conectar o motorista D ao WebSocket server WS-2:
redis.set(f"driver_ws:{driver_id}", "ws-server-2")  # routing table
# WS-2 subscreve no canal do motorista:
redis.subscribe(f"channel:driver:{driver_id}")

# Quando matching service quer enviar mensagem para D:
redis.publish(
    f"channel:driver:{driver_id}",
    json.dumps({"type": "TRIP_REQUEST", "passenger_id": "P123", ...})
)

# Redis entrega a mensagem para todos os subscribers do canal
# WS-2 é o subscriber → WS-2 encontra a conexão WebSocket de D → envia

# Tracking de localização durante a corrida (passageiro acompanha motorista):
# Driver D envia atualização de GPS via WebSocket para WS-2
# WS-2 publica no canal da corrida:
redis.publish(f"channel:trip:{trip_id}:location",
              json.dumps({"lat": driver_lat, "lng": driver_lng}))
# Passenger app (em qualquer WS server) é subscriber desse canal
# → recebe a atualização e atualiza o pin no mapa

Escalando WebSocket servers

# WebSocket servers são stateful (cada conexão é persistente)
# → não podem ser escalados com round-robin simples no load balancer

# Sticky sessions: o load balancer sempre roteia o mesmo cliente para o mesmo WS server
# Implementação: cookie de sessão ou hash do IP

# Mas: se o WS server cai, as conexões morrem
# Solução no client: reconnect automático com exponential backoff
# Na reconexão: o client pode cair em qualquer WS server (round-robin)
# → o novo WS server subscreve nos canais relevantes para o cliente

# Healthcheck: motoristas enviam heartbeat a cada 30s
# Se o server não recebe heartbeat de um motorista em 60s:
# → marcar motorista como offline no Location Service
# → remover do pool de motoristas disponíveis
# → o cliente vai reconectar automaticamente

Surge pricing — demanda vs oferta por zona

# Surge é calculado por zona geográfica (geohash de precisão 4-5 chars)
# A cada 30 segundos, para cada zona ativa:

def calculate_surge(zone_geohash):
    # Motoristas disponíveis na zona (e zonas adjacentes)
    available_drivers = count_available_drivers(zone_geohash)

    # Solicitações de corrida nos últimos 5 minutos
    recent_requests = redis.zcount(
        f"requests:{zone_geohash}",
        time.now() - 300,  # 5 minutos atrás
        time.now()
    )

    if available_drivers == 0:
        return MAX_SURGE_MULTIPLIER  # 4.0x

    demand_ratio = recent_requests / available_drivers

    # Mapeamento demand_ratio → surge multiplier
    if demand_ratio < 0.5:   return 1.0   # sem surge
    elif demand_ratio < 1.0: return 1.2
    elif demand_ratio < 1.5: return 1.5
    elif demand_ratio < 2.0: return 2.0
    else:                    return min(demand_ratio, 4.0)

# Armazenar no Redis com TTL de 60s (atualizado a cada 30s)
redis.setex(f"surge:{zone_geohash}", 60, surge_multiplier)

# Ao mostrar preço para o passageiro:
passenger_zone = geohash2.encode(lat, lng, precision=5)
surge = float(redis.get(f"surge:{passenger_zone}") or 1.0)
estimated_price = base_price * surge

ETA — tempo estimado de chegada

# ETA é necessário em dois momentos:
# 1. Antes do matching: para scoring dos motoristas candidatos
# 2. Durante a corrida: mostrado ao passageiro enquanto espera

# Problema: calcular ETA real (considerando tráfego e rotas) é caro
# Google Maps Platform API: ~$5/1000 requests
# Com 350 matchings/s × 20 candidatos = 7.000 ETAs/s → ~$1M/dia sem cache

# Solução: caching de ETA por par (origin_geohash, dest_geohash)
# Origin = posição do motorista (geohash 6 chars = ~600m)
# Dest = posição do passageiro (geohash 6 chars)

def get_eta(driver_lat, driver_lng, passenger_lat, passenger_lng):
    origin_gh = geohash2.encode(driver_lat, driver_lng, precision=6)
    dest_gh   = geohash2.encode(passenger_lat, passenger_lng, precision=6)
    cache_key = f"eta:{origin_gh}:{dest_gh}"

    cached_eta = redis.get(cache_key)
    if cached_eta:
        return int(cached_eta)

    # Cache miss: chamar routing service (interno ou Google Maps)
    eta_seconds = routing_service.get_eta(
        (driver_lat, driver_lng),
        (passenger_lat, passenger_lng)
    )
    # Cachear por 2 minutos (tráfego muda; precisão de geohash absorve movimentos pequenos)
    redis.setex(cache_key, 120, eta_seconds)
    return eta_seconds

# Para scoring durante o matching, uma estimativa baseada em distância euclidiana
# com um fator de "tortuosidade" de rodovia é suficiente:
def estimate_eta_fast(distance_km, city_speed_factor=1.4):
    # speed_factor > 1: rotas reais são mais longas que linha reta
    avg_speed_kmh = 30  # velocidade média em área urbana
    return (distance_km * city_speed_factor / avg_speed_kmh) * 3600  # segundos

Arquitetura completa

Driver App → WebSocket Gateway (sticky session)
                  ↓ GPS update (a cada 4s)
            Location Service
                  ↓ GEOADD
            Redis Cluster (shardado por região)
            ["drivers_available:us-east", "drivers_available:eu-west", ...]

Passenger App → API Gateway → Matching Service
                                    ↓ GEOSEARCH (busca candidatos)
                              Redis Cluster (Location)
                                    ↓ scoring + oferta
                              PUBLISH channel:driver:{id}
                                    ↓ Redis Pub/Sub
                              WebSocket Gateway (servidor do motorista)
                                    ↓ WebSocket
                              Driver App (exibe solicitação de corrida)

                              ↓ driver aceita
                              SET driver_lock:{id} NX (distributed lock)
                              Trip Service → cria trip no Redis + queue para DB
                              PUBLISH channel:trip:{id}:state → ambas as partes

Durante a corrida:
Driver App → WebSocket Gateway → PUBLISH channel:trip:{id}:location
           → Passenger App (qualquer WS Gateway via Redis Pub/Sub)

Persistência:
  Redis → source of truth para estado em tempo real (trips, locations)
  PostgreSQL → dados históricos (trips concluídas, ratings, pagamentos)
  Kafka → eventos de transição de estado (audit trail, analytics)

Decisões de engenharia

Perguntas de entrevista

SETEX driver_active:{driver_id} 10 "1"  # TTL de 10s
GEOADD drivers_available lng lat driver_id

def can_add_passenger(trip, new_passenger):
    # Rota atual: driver → pickup_A → destination_A
    # Nova rota candidata: driver → pickup_new → pickup_A → dest_A → dest_new
    # (ou outra ordem dependendo das coordenadas)

    # Calcular tempo adicional para passageiro A (atual):
    detour_seconds = routing_service.get_route_time(
        [driver_position, new_passenger.pickup, passenger_a.pickup, passenger_a.destination]
    ) - routing_service.get_route_time(
        [driver_position, passenger_a.pickup, passenger_a.destination]
    )

    # Aceitar se o desvio for menor que threshold (ex: 5 minutos)
    return detour_seconds < 300

Exercícios práticos