Uber: indexação geoespacial

01 · CONTEXTO

O problema: analisar o mapa em células

Um marketplace de corridas precisa responder perguntas sobre regiões, não sobre pontos isolados: quanta demanda e quanta oferta existem aqui? Para isso, latitude e longitude brutas não bastam; é preciso uma forma de transformar o mapa em células com identificador, que possam ser contadas, comparadas e agrupadas. Em entrevista, comece por levantar requisitos: qual a precisão necessária, que tipo de vizinhança importa e se a região precisa ser vista em escalas diferentes (bairro, cidade).

A resposta da Uber foi criar o H3. A motivação declarada no blog de engenharia é combinar os benefícios de uma grade global hexagonal com um sistema de indexação hierárquico. Ou seja, o H3 é uma grade de hexágonos com hierarquia de resoluções, e não um índice baseado em quadrados. A Uber usa o H3 como o sistema de grade para análise e otimização em seus marketplaces.

02 · POR QUE HEXÁGONOS

A forma da célula muda a análise

Segundo a Uber, usar o hexágono como forma da célula é crítico para o H3. A razão central é a vizinhança: no hexágono existe uma única distância entre o centro da célula e o centro de cada vizinha, enquanto no quadrado há duas distâncias e no triângulo, três. Em grades quadradas, a análise exige conjuntos distintos de coeficientes, porque vizinhas laterais e diagonais não são equivalentes.

Na prática, essa uniformidade simplifica operações como suavizar valores entre células vizinhas ou analisar gradientes: o resultado não depende de a vizinha estar de lado ou na diagonal. É isso que faz sentido para estimar, por exemplo, como a demanda se espalha de uma região para a seguinte.

03 · HIERARQUIA

Resoluções e a aproximação entre pai e filho

O H3 oferece dezesseis resoluções. A cada resolução mais fina, as células têm um sétimo da área das células da resolução anterior, mais grossa. Assim, o mesmo ponto pode ser descrito de forma grosseira (cidade) ou detalhada (quarteirão), apenas trocando a resolução.

Há uma ressalva importante: as células mais finas estão apenas aproximadamente contidas na célula pai, porque hexágonos não se subdividem exatamente em hexágonos menores. Em contrapartida, o identificador de uma célula filha pode ser truncado para encontrar a célula ancestral em resolução mais grossa, o que torna barato subir na hierarquia. Ao projetar, trate o agrupamento por pai como aproximação e não como partição exata.

1. O cliente envia a posição de um ponto no mapa; o sistema precisa agrupá-lo em uma célula antes de qualquer análise regional.

2. O serviço de indexação converte a posição em um identificador de célula hexagonal na resolução pedida.

3. O identificador truncado dá a célula ancestral em resolução mais grossa; o agregado dessa célula é lido do cache, sabendo que o agrupamento por pai é apenas aproximado.

04 · NO MARKETPLACE

Preço dinâmico por célula

A própria Uber descreve o uso mais conhecido: o preço dinâmico é calculado medindo oferta e demanda em hexágonos de cada cidade atendida. O H3 permite analisar informação geográfica para definir preços dinâmicos e tomar outras decisões em escala de cidade.

Como arquitetura, o padrão é: eventos de posição de passageiros e motoristas chegam por uma fila de mensagens, são agregados por célula e alimentam um serviço de preço lido a cada solicitação. Como a chave natural é a célula, os contadores se distribuem bem entre nós, e o desenho conversa com análise em tempo real e com a escolha de uma boa chave de particionamento. Este desenho é uma interpretação didática; o blog da Uber não detalha a infraestrutura.

1. Passageiros e motoristas enviam posições e pedidos pela borda do sistema.

2. Os eventos de posição entram numa fila, desacoplando a ingestão da agregação.

3. Um consumidor converte cada posição em célula hexagonal e atualiza oferta e demanda daquela célula no armazenamento rápido.

4. O serviço de preço lê a relação entre oferta e demanda da célula para definir o preço dinâmico naquela região.

5. Se o armazenamento de agregados cai, o preço da região fica sem dado atual e é preciso decidir entre usar o último valor conhecido ou um valor padrão.