Google Maps (tiles, rotas, ETA)

01 · CONTEXTO E REQUISITOS

O que um serviço de mapas precisa fazer

Um serviço de mapas faz três coisas bem diferentes: desenha o mapa na tela, calcula a rota entre dois pontos e estima quanto tempo ela leva. Cada uma tem carga, dados e tolerância a dado velho próprios, e por isso o desenho costuma se separar em três caminhos independentes, em vez de um serviço único. Esse é o primeiro passo de qualquer levantamento de requisitos.

Os requisitos funcionais são ver o mapa com zoom e arrasto, pedir uma rota entre origem e destino e receber uma estimativa de tempo que reflita o trânsito. Entre os não funcionais, três mandam: o mapa precisa aparecer rápido mesmo em rede lenta, a rota deve sair em poucos instantes e o serviço deve continuar disponível mesmo quando o dado de trânsito estiver atrasado.

02 · O MAPA EM PEDAÇOS

Tiles: nunca baixe o mapa inteiro

O aparelho nunca baixa o mapa todo: pede só os pedaços (tiles) que cabem na tela. No esquema aberto do OpenStreetMap, cada tile é uma imagem PNG de 256 por 256 pixels, endereçada por zoom, coluna e linha.

Nesse esquema o zoom vai de 0 (afastado) a 18 (aproximado). No zoom 0 um único tile cobre o mundo todo, e a cada nível o número de tiles por lado dobra, de modo que o mesmo lugar é coberto por tiles cada vez mais numerosos e detalhados.

Como o tile depende só de zoom, coluna e linha, a resposta é igual para todo mundo e muda raramente. Isso a torna ideal para pré-gerar, guardar em armazenamento de objetos e servir por uma CDN: boa parte dos pedidos pode ser atendida na borda, sem tocar nos servidores de origem.

1. O aparelho calcula, pela posição e pelo zoom, quais tiles cobrem a tela e pede cada um pelo endereço zoom, coluna e linha.

2. O pedido chega primeiro à CDN. Se ela já tem o tile, responde ali mesmo, sem incomodar os servidores de origem.

3. Se a CDN não tem o tile, encaminha o pedido ao serviço de tiles.

4. O serviço busca o tile pronto no armazenamento, sem desenhar nada na hora.

5. O tile volta ao aparelho e a CDN guarda uma cópia para os próximos pedidos da região.

6. Fora do caminho do usuário, o gerador relê os dados do mapa quando eles mudam e regrava só os tiles afetados.

Há duas formas de entregar um tile. Na vetorial, o servidor devolve dados recortados nos limites do tile em vez de uma imagem pré-renderizada, e só se transfere o que está na janela e no zoom atuais.

03 · ROTAS NO GRAFO DE ESTRADAS

Caminho mínimo em escala de país

Para calcular rotas, a malha viária vira um grafo: cruzamentos são vértices, trechos de via são arestas e o peso de cada aresta é o tempo de percorrê-la.

O caminho mínimo pode sair do algoritmo de Dijkstra, mas redes viárias têm dezenas de milhões de vértices, o que torna impraticável rodá-lo do zero a cada pedido.

A saída é pré-processar. As contraction hierarchies criam atalhos numa fase prévia, que pulam vértices pouco importantes, e se apoiam no fato de que redes viárias são muito hierárquicas. Como a malha muda pouco, o pré-cálculo pode levar de segundos a horas e ser feito uma vez; depois, muitas consultas são respondidas em microssegundos cada.

O grafo de um país ou do mundo não cabe numa máquina. Uma escolha comum é particioná-lo por região, mantendo cada partição perto de quem a consulta; rotas que cruzam a fronteira de uma região precisam consultar as partições vizinhas, e é aí que o desenho exige mais cuidado.

1. O aparelho envia origem e destino; o gateway encaminha o pedido ao serviço de rotas.

2. O serviço de rotas pede ao serviço de localização que ligue cada ponto ao vértice de estrada mais próximo.

3. Com os vértices, ele carrega as partições do grafo que cobrem a região entre origem e destino.

4. A busca usa os atalhos pré-calculados para pular trechos de pouca importância e chegar rápido ao caminho mínimo.

5. A rota volta ao aparelho como uma lista de trechos para desenhar sobre o mapa.

6. Fora do caminho do usuário, o pré-processamento recalcula os atalhos quando a malha viária muda.

Achar o vértice mais próximo de um ponto pede um índice espacial. O geohash é uma opção simples: quanto maior o prefixo comum entre dois códigos, mais próximos estão os pontos.

O inverso, porém, não vale: dois pontos muito próximos podem ter prefixo curto ou nenhum, e isso acontece, por exemplo, em lados opostos do meridiano de 180 graus. Uma forma de contornar é consultar também os quadrados vizinhos, o que o Solr faz com uma lista de prefixos.

04 · TRÂNSITO E ETA

Estimar o tempo de viagem

O Google Maps analisa dados de trânsito ao vivo dos trechos de via do mundo todo e usa aprendizado de máquina para combinar o trânsito atual com padrões históricos. Só o histórico não basta, porque o horário exato do pico varia bastante de dia para dia e de mês para mês.

Num desenho de entrevista, a fonte usual do trânsito ao vivo são as posições anônimas enviadas pelos aparelhos. Elas chegam em fluxo alto e contínuo, então entram numa fila de mensagens e um consumidor as agrega, num pipeline de dados, em velocidade atual por trecho de via.

1. O aparelho envia sua posição de tempos em tempos; o gateway a entrega ao serviço de ingestão.

2. A ingestão valida a posição e a coloca na fila, sem esperar o cálculo de trânsito.

3. O agregador consome a fila, calcula a velocidade atual de cada trecho e grava o resultado.

4. Quando o usuário pede a ETA de uma rota, o gateway aciona o serviço de ETA.

5. O serviço lê o trânsito atual e o histórico dos trechos da rota e entrega tudo ao modelo de previsão.

6. A soma dos tempos previstos dos trechos volta ao aparelho como a ETA da rota.

Em 2020, a DeepMind descreveu como dividiu a malha em Supersegments, trechos adjacentes que concentram volume de tráfego. O sistema tem um analisador de rotas, que processa terabytes de informação de tráfego para construí-los, e uma rede neural em grafo que prevê o tempo de viagem de cada um.

No grafo do modelo, cada trecho é um nó e as arestas ligam trechos consecutivos na mesma via ou conectados por um cruzamento. Isso permite ao modelo olhar vias adjacentes, porque um congestionamento numa rua lateral pode afetar uma via maior.

O resultado foi medido: segundo a DeepMind, as ETAs já eram precisas em mais de 97% das viagens, e o trabalho com redes neurais em grafo melhorou a precisão das ETAs em tempo real em até 50% em algumas cidades.

05 · DECISÕES E TRADE-OFFS

Três caminhos, três perfis

Juntando as partes, cada caminho tem uma tolerância diferente a dado velho, e é isso que justifica separá-los. O mapa-base muda devagar e aguenta cache longo; a malha viária muda pouco e aguenta pré-cálculo; o trânsito muda o tempo todo e exige um fluxo próprio.

Essa separação também isola falhas: um atraso no pipeline de trânsito deixa a ETA menos precisa, mas não derruba o mapa nem o cálculo de rotas, o que combina com a prioridade de disponibilidade definida nos requisitos.