Corridas por Aplicativo

"Projete um serviço de corridas por aplicativo como o Uber ou a 99: um passageiro pede uma corrida, o sistema encontra um motorista próximo e os dois se veem no mapa até a corrida terminar."

Corridas por aplicativo são o problema clássico geoespacial, de muita escrita e em tempo real. Centenas de milhares de celulares informam sua posição a cada poucos segundos; a maioria dessas escritas é inútil segundos depois, e a única consulta que importa — quais motoristas disponíveis estão perto deste ponto? — precisa responder em milissegundos. Por cima disso há um problema de consistência pequeno mas rígido: um motorista, uma corrida. A entrevista testa se você sabe escolher um índice espacial, manter os dados quentes em memória, particionar o mundo de forma sensata e proteger o único lugar onde a corretude não é negociável.

O BoxOffice encontra os mesmos problemas duas vezes. Sua busca "eventos perto de mim" usa as mesmas ideias de índice geográfico, e todo show de estádio termina com 60 000 fãs saindo de uma vez — um app de corridas vê uma única célula do mapa passar de um punhado de pedidos para milhares em minutos. Essa célula quente é um dos follow-ups abaixo.

1. Esclarecer os requisitos

(roteiro de entrevista)

Requisitos funcionais

1. Motoristas ficam online/offline e, enquanto online, enviam sua localização a cada poucos segundos.
2. O passageiro vê motoristas próximos no mapa, uma estimativa de chegada (ETA) e uma estimativa de preço.
3. O passageiro pede uma corrida; o sistema faz o matching com um motorista, que aceita ou recusa em poucos segundos.
4. Durante a corrida, os dois apps mostram a localização ao vivo; a corrida termina com pagamento e avaliação.
5. Histórico de corridas para passageiros, motoristas e suporte.

Requisitos não funcionais

Fora do escopo (diga explicitamente)

Motor de rotas/mapas (chamamos um), cadastro de motoristas e documentos, detecção de fraude, corridas compartilhadas (pooling) — cite o pooling como extensão.

2. Estimativas de guardanapo (back-of-the-envelope)

# Ride sharing: assumptions (illustrative)
drivers_online = 1_000_000     # at peak, worldwide
update_s       = 4             # driver location interval
loc_b          = 100           # driver id, lat, lon, heading, speed, ts
trips_day      = 20_000_000
peak_factor    = 3
trip_min       = 20            # average trip duration
rider_poll_s   = 2             # rider app refreshes driver position during the trip
cities         = 500

loc_writes     = drivers_online / update_s
ingest_mb_s    = loc_writes * loc_b / 1e6
history_tb_day = loc_writes * 86_400 * loc_b / 1e12
latest_mb      = drivers_online * loc_b / 1e6
trip_rps       = trips_day / 86_400
peak_trip_rps  = trip_rps * peak_factor
active_trips   = trip_rps * trip_min * 60             # Little's Law: L = λ·W
trip_push_rps  = active_trips / rider_poll_s
writes_city    = loc_writes / cities                   # average; big cities are 10-50x this

rows = [
    ("loc_writes", loc_writes, "writes/s"), ("ingest_mb_s", ingest_mb_s, "MB/s"),
    ("history_tb_day", history_tb_day, "TB/day"), ("latest_mb", latest_mb, "MB"),
    ("trip_rps", trip_rps, "req/s"), ("peak_trip_rps", peak_trip_rps, "req/s"),
    ("active_trips", active_trips, "trips"), ("trip_push_rps", trip_push_rps, "msgs/s"),
    ("writes_city", writes_city, "writes/s"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

O que os números dizem:

• 250 mil escritas de localização/s — muito além do que um primário relacional deveria absorver como atualizações de linha. Mas a última posição de cada motorista ocupa só ~100 MB: cabe em memória muitas vezes. ⇒ mantenha a última posição num índice geográfico em memória; envie os pontos brutos por um stream para armazenamento barato.
• O histórico bruto soma ~2 TB/dia se guardado por inteiro ⇒ object storage / data lake, comprimido e possivelmente amostrado, nunca no caminho quente.
• Pedidos de corrida são só ~230/s (~700/s no pico) — o caminho de matching tem pouco volume, mas precisa ser correto.
• A Lei de Little dá ~280 mil corridas em andamento a qualquer momento, cada uma enviando a posição do motorista ao passageiro: ~140 mil mensagens/s de fan-out em tempo real (conexões persistentes, como no caso do chat).
• Dividida por cidade, a taxa de escrita é pequena (~500 escritas/s em média, algumas dezenas de milhares nas maiores metrópoles). ⇒ particione por cidade/região: toda consulta fica local a um shard.

3. API

# Driver app (in practice over a persistent connection: WebSocket / gRPC stream / MQTT)
PUT  /v1/drivers/me/status        {"status": "AVAILABLE|OFFLINE"}                 → 204
PUT  /v1/drivers/me/location      {"lat": -23.5475, "lon": -46.6361, "heading": 90,
                                   "speed": 8.3, "ts": 1767261600123}             → 204
POST /v1/offers/{offerId}/accept                                                  → 200 {rideId}
POST /v1/offers/{offerId}/decline                                                 → 204

# Rider app
GET  /v1/drivers/nearby?lat=…&lon=…&radius=2000                                   → 200 [{driverId, lat, lon, etaS}]
POST /v1/rides  {"pickup": {...}, "dropoff": {...}, "product": "economy"}
     Idempotency-Key: 5b1e…                                                       → 202 {rideId, status: MATCHING, fareEstimate}
GET  /v1/rides/{rideId}                                                           → 200 {status, driver, driverLocation, etaS}
POST /v1/rides/{rideId}/cancel                                                    → 200 {cancellationFee}

• Atualizações de localização são disparar e esquecer: se uma se perde, a próxima chega em 4 s. Sem retentativas, sem confirmação por ponto.
• A criação da corrida é idempotente (Idempotency-Key): um passageiro que toca duas vezes numa rede lenta não pode receber dois carros.

4. Modelo de dados

# Latest positions, one geo set per city (Redis GEO = sorted set of geohash-encoded scores)
GEOADD drivers:sao-paulo -46.6361 -23.5475 driver:42
GEOSEARCH drivers:sao-paulo FROMLONLAT -46.6361 -23.5475 BYRADIUS 2 km ASC COUNT 20

# Driver state (hash), with TTL refreshed by each update: no update for 30 s → stale
driver:42 → { status: AVAILABLE, city: sao-paulo, lat, lon, ts, rideId: null }

CREATE TABLE ride (
    ride_id        UUID PRIMARY KEY,
    city           TEXT        NOT NULL,
    rider_id       BIGINT      NOT NULL,
    driver_id      BIGINT,
    status         TEXT        NOT NULL,   -- MATCHING | ACCEPTED | ARRIVING | IN_PROGRESS | COMPLETED | CANCELLED
    pickup         POINT       NOT NULL,
    dropoff        POINT       NOT NULL,
    fare_cents     INT,
    surge          NUMERIC(3,2),
    idempotency_key TEXT UNIQUE NOT NULL,
    requested_at   TIMESTAMPTZ NOT NULL,
    completed_at   TIMESTAMPTZ
);

-- At most one active ride per driver: the database enforces it
CREATE UNIQUE INDEX one_active_ride_per_driver ON ride (driver_id)
    WHERE status IN ('ACCEPTED', 'ARRIVING', 'IN_PROGRESS');

5. Design de alto nível

flowchart LR
    d([App do motorista]) --> gw["Gateway<br/>conexões persistentes"]
    r([App do passageiro]) --> gw
    gw --> loc["Serviço de localização"]
    loc --> st[["Stream de localizações<br/>particionado por cidade"]]
    st --> geo[("Índice geográfico<br/>últimas posições")]
    st --> hist[("Histórico<br/>object store")]
    st --> surge["Preço dinâmico<br/>oferta/demanda por célula"]
    gw --> ride["Serviço de corridas"]
    ride --> match["Matching / despacho"]
    match --> geo
    match --> eta["ETA / rotas"]
    match -. oferta .-> gw
    ride --> db[("Banco de corridas<br/>SQL")]
    ride --> pay[["Provedor de pagamento"]]
    ride --> notif["Notificações"]

Um pedido de corrida, do toque à oferta aceita:

sequenceDiagram
    autonumber
    participant R as App do passageiro
    participant S as Serviço de corridas
    participant M as Matching
    participant G as Índice geográfico
    participant L as Lock do motorista
    participant D as App do motorista
    R->>S: POST /rides (Idempotency-Key)
    S-->>R: 202 MATCHING
    S->>M: match(corrida, embarque)
    M->>G: GEOSEARCH 2 km, AVAILABLE, 20 mais próximos
    G-->>M: candidatos
    M->>M: ranqueia por ETA nas ruas
    M->>L: trava o motorista 42 para a corrida (NX, 15 s)
    L-->>M: OK
    M->>D: oferta (expira em 15 s)
    D-->>M: aceita
    M->>S: atribui o motorista 42 (update condicional)
    S-->>R: motorista 42, ETA 4 min

6. Aprofundamentos (deep dives)

6.1 Ingerindo localizações: guarde só o que importa

• A última posição é o produto; o rastro é analytics. O serviço de localização valida o ponto (velocidade plausível, fora do oceano), grava o último valor no índice geográfico e o acrescenta ao stream. Nada no caminho quente lê o histórico.
• Agrupe e aglutine. O gateway pode aglutinar atualizações por motorista (se duas chegam na mesma janela de 100 ms, fica a mais nova) e gravar no índice geográfico em lotes com pipelining.
• Frequência adaptativa. Um motorista disponível parado não precisa informar a cada 4 s; um motorista se aproximando do embarque precisa de mais. O app adapta o intervalo à velocidade e ao estado — menos escritas, mais atualidade onde importa.
• Desatualização. Cada estado de motorista tem um TTL renovado pelas atualizações; um celular que fica em silêncio por 30 s sai do conjunto de candidatos automaticamente, sem job de limpeza.
• Particione por cidade. O tópico do stream, o índice geográfico e o banco de corridas são todos particionados por cidade (ou região), então uma consulta em São Paulo nunca toca os shards de Lisboa (particionamento).

6.2 O índice espacial: geohash, quadtree ou H3

Uma B-tree em (lat, lon) não responde "dentro de 2 km" de forma eficiente: ela ordena por uma dimensão de cada vez. Índices espaciais mapeiam o espaço 2-D em células (bancos especializados).

Qual o tamanho de uma célula de geohash? Depende da precisão (caracteres) e da latitude — calculado aqui para São Paulo:

import math

lat = -23.55                       # São Paulo
print("| precision | cell width (km) | cell height (km) |\n|---:|---:|---:|")
for p in range(4, 9):
    bits = 5 * p                   # base32: 5 bits per character
    lon_bits, lat_bits = (bits + 1) // 2, bits // 2
    width = 360 / 2 ** lon_bits * 111.32 * math.cos(math.radians(lat))
    height = 180 / 2 ** lat_bits * 110.57
    print(f"| {p} | {width:.3f} | {height:.3f} |")

A precisão 6 (~1,1 × 0,6 km) é um bom balde para "motoristas a uns dois km". Problema da borda: um passageiro na beirada de uma célula pode estar a 50 m de um motorista na célula vizinha — sempre busque a célula mais suas 8 vizinhas (ou um anel k do H3) e depois filtre pela distância real. Se poucos motoristas forem encontrados, amplie o anel (precisão 5, ou k + 1) até aparecerem candidatos suficientes ou atingir um raio máximo.

6.3 Matching sem atribuição dupla

O momento perigoso: os matchers de dois passageiros escolhem o mesmo motorista mais próximo ao mesmo tempo. A regra um motorista, uma corrida precisa de uma guarda atômica (consenso e locks):

1. Os candidatos vêm do índice geográfico (rápido, um pouco desatualizado — tudo bem).
2. Antes de ofertar, trave o motorista: SET lock:driver:42 <rideId> NX PX 15000 — só um matcher ganha; o lock expira se o motorista ignorar a oferta ou o matcher cair.
3. O motorista aceita → o serviço de corridas atribui com um update condicional (UPDATE ride SET driver_id = 42, status = 'ACCEPTED' WHERE ride_id = $1 AND status = 'MATCHING'), e o índice único parcial garante que o motorista não tem outra corrida ativa — a última linha de defesa durável caso o lock falhe algum dia.
4. O motorista recusa ou a oferta expira → libere o lock e oferte ao próximo candidato.

Matching guloso vs. em lote. O guloso (cada pedido pega seu motorista disponível mais próximo) é simples e rápido. O matching em lote junta pedidos por 1–2 segundos e resolve um problema de atribuição sobre todos (minimizando o tempo total até o embarque), o que é globalmente melhor em áreas densas — um trade-off clássico de latência por eficiência.

6.4 A corrida como máquina de estados

stateDiagram-v2
    [*] --> MATCHING: passageiro pede
    MATCHING --> ACCEPTED: motorista aceita a oferta
    MATCHING --> CANCELLED: sem motorista / passageiro cancela
    ACCEPTED --> ARRIVING: motorista a caminho
    ARRIVING --> IN_PROGRESS: passageiro embarcou
    ARRIVING --> CANCELLED: passageiro não apareceu (taxa)
    IN_PROGRESS --> COMPLETED: desembarque
    COMPLETED --> [*]: pagamento capturado
    CANCELLED --> [*]

• Toda transição é um update condicional sobre o estado atual (idempotente sob retentativas) e emite um evento (stream) para notificações, atualizações de ETA, recibos e analytics.
• Pagamento: autorize uma estimativa quando a corrida é aceita e capture a tarifa final em COMPLETED pelo provedor de pagamento com uma chave de idempotência (veja o caso do sistema de pagamentos).
• Celulares ficam offline no meio da corrida (túneis): a corrida continua no servidor; o app do motorista guarda os pontos de GPS e os envia depois, para a tarifa ser calculada pelo trajeto real.

O preço dinâmico cabe no mesmo pipeline: um job de stream conta os pedidos abertos (demanda) e os motoristas disponíveis (oferta) por célula H3 por minuto e publica um multiplicador por célula, suavizado no espaço e no tempo para os preços não ficarem piscando.

7. Gargalos, modos de falha e trade-offs

Os trade-offs para dizer em voz alta: atualidade vs. custo de escrita (posições a cada 4 s, não a cada segundo), consistência eventual para posições, consistência forte para a atribuição (o índice geográfico pode estar desatualizado; o lock do motorista e a linha da corrida, não), e matching guloso vs. em lote (latência vs. eficiência global).

8. Experimente no playground

O cenário ride-sharing modela atualizações de localização com muita escrita passando por um stream até um índice geográfico, e um caminho de matching que o lê.

Abrir o playground completo

9. Perguntas de follow-up que o entrevistador faz

10. Rubrica de autoavaliação

Relacionados: Particionamento, Bancos especializados, Caso do chat (conexões persistentes), Caso do sistema de pagamentos, Hands-on 6 (transações e locks).

Como se conecta

Quais aulas este caso testa? Cada ramo é uma aula cujas ideias o design usa (azul), com os componentes da paleta em que elas aparecem (verde):

flowchart LR
    CASE(["Ride sharing"]) --> EST["Estimation<br/>location writes, latest position fits in memory"]:::tech
    CASE --> DB["Databases<br/>geohash, quadtree, H3, partition by city"]:::tech
    CASE --> MSG["Messaging<br/>location stream by city"]:::tech
    CASE --> DIS["Distributed<br/>one driver, one ride: atomic guard"]:::tech
    CASE --> CMP["Compute<br/>trip state machine, payment"]:::tech
    CASE --> EDG["Edge<br/>persistent connections"]:::tech
    DB -.-> k1["cache (geo index) · sql"]:::comp
    MSG -.-> k2["stream · objstore"]:::comp
    CMP -.-> k3["payment · notifications"]:::comp
    EDG -.-> k4["mobile · apigw"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Aulas que ele testa: Bancos de dados — especializados · Bancos de dados — particionamento · Mensageria — Kafka · Distribuídos — consenso · Compute — integrações · Caching — Redis (comandos geo) · Hands-on 6. Componentes da paleta: mobile · apigw · stream · cache · sql · objstore · payment · notifications. Cenários: ride-sharing.

Referências

• XU, A.; LAM, S. System Design Interview — An Insider's Guide, vol. 2, cap. 1 "Proximity Service" e cap. 2 "Nearby Friends"¹.
• O índice espacial hierárquico hexagonal do Uber².
• Comandos geoespaciais do Redis (GEOADD, GEOSEARCH)³.
• FINKEL, R.; BENTLEY, J. Quad Trees: A Data Structure for Retrieval on Composite Keys⁴.