Sirva clusters de mapas 50x mais rápido usando um cache mais inteligente

Componentes de mapa que apresentam marcadores de localização são comuns em aplicativos móveis hoje. Por exemplo, o aplicativo do Airbnb destaca esses marcadores, obtidos de um serviço da web, para representar propriedades disponíveis em um mapa.

Para garantir que o volume de dados buscados não se torne incontrolável à medida que o número de marcadores aumenta, o servidor agrupa esses marcadores antes de enviá-los ao cliente. Um cluster de mapa é um marcador especializado cuja posição é igual à posição média dos marcadores que ele inclui. É rotulado com o número de marcadores que representa.

Ainda assim, servir clusters pode criar gargalos de desempenho porque um serviço da Web deve recuperar todos os marcadores em uma determinada região geográfica do banco de dados. Felizmente, esse problema pode ser resolvido com uma estratégia de armazenamento em cache. Para entender melhor como projetar e manter um cache, vejamos um exemplo de endpoint de API de mapa que criei para o aplicativo Playsports.

Um problema de dimensionamento e uma solução ingênua

No mapa Playsports, cada marcador representa uma instalação esportiva. O endpoint da API do mapa precisa retornar uma lista de marcadores e clusters de marcadores, dado um nível de zoom e uma caixa delimitadora.

Se o número de marcadores for pequeno o suficiente, podemos carregar todos os marcadores na caixa delimitadora do banco de dados, agrupar conforme necessário e retornar os marcadores e clusters resultantes ao cliente.

No início, o número máximo de marcadores em qualquer caixa delimitadora alcançável no Playsports era de ~400, resultando em uma velocidade final de ~0,5 segundos. A implementação da solução ingênua foi suficiente para este caso de uso.

À medida que o número de marcadores cresceu, no entanto, a ineficiência do mecanismo tornou-se óbvia. Depois que adicionamos cerca de 10.000 novos marcadores de instalações esportivas, a velocidade do endpoint diminuiu para cerca de 4,3 segundos em alguns níveis de zoom. Essa taxa está muito abaixo da duração de um segundo que geralmente é considerada o atraso máximo aceitável para uma ação do usuário em um aplicativo móvel.

Para entender melhor as ineficiências da solução ingênua, vamos analisá-la no contexto da consulta do marcador:

1. No banco de dados, recupere todos os marcadores na caixa delimitadora . Para a maioria dos aplicativos, esta etapa precisa incluir a busca de detalhes do marcador além do posicionamento de latitude/longitude. Por exemplo, os marcadores do Airbnb incluem o preço, se o usuário já visualizou a propriedade e se a marcou como favorita.
2. Nos marcadores recuperados, execute um algoritmo de agrupamento de mapas que incorpore o nível de zoom.
3. Retorne clusters e marcadores (detalhados) para o cliente.

À medida que o número de marcadores aumenta, o desempenho se deteriora nas etapas 1 e 2:

• Quando a caixa delimitadora é grande o suficiente e quando mais de 10.000 marcadores exigem uma pesquisa de detalhes por meio de um JOIN, a consulta do banco de dados diminui drasticamente (em 1 a 2 segundos).
• Alimentar 10.000 itens para o algoritmo de agrupamento de mapas leva mais ~250 milissegundos.

Assumindo um tamanho de janela constante, quando uma caixa delimitadora é relativamente grande, o nível de zoom geralmente é baixo (ou seja, muito reduzido). Sob baixos níveis de zoom, os resultados tendem a favorecer os agrupamentos para evitar aglomeração visual. Assim, o maior potencial de otimização está na primeira etapa da solução, onde milhares de marcadores individuais são carregados. Não precisamos da maioria desses marcadores no resultado. Só precisamos que cada um deles conte para um cluster.

Arquitetando a solução otimizada

A solução ingênua leva muito mais tempo para concluir uma consulta de pior caso: uma caixa delimitadora máxima em uma região densa de marcadores. Em contraste, a solução otimizada levaria apenas 73 ms, representando uma aceleração de ~58x. De um nível alto, fica assim:

1. A Estratégia de Cache. Recupere marcadores e clusters em uma caixa delimitadora de um cache específico do nível de zoom.
2. Detalhe do marcador adicional (opcional). Aprimore os marcadores com uma carga útil obtida do banco de dados.
3. Retornando o Resultado. Retorne marcadores e clusters para o cliente.

A principal complexidade está na arquitetura do cache (ou seja, o primeiro passo).

Etapa 1: a estratégia de armazenamento em cache

Esta etapa principal consiste em seis componentes:

Tecnologia

O Redis é um banco de dados rápido na memória que é comumente usado como cache. Sua indexação geoespacial integrada usa o algoritmo Geohash para armazenamento e recuperação eficientes de pontos de latitude-longitude, que é exatamente o que precisamos para nossos marcadores.

Um cache para cada nível de zoom

O grau de agrupamento de mapas (se marcadores únicos ou agrupamentos são retornados) é determinado pelo nível de zoom passado para o ponto de extremidade.

• Para níveis de zoom altos (ou seja, com zoom de perto), o resultado favorecerá marcadores individuais, exceto em regiões densas de marcadores.
• Para níveis de zoom baixos (ou seja, com muito zoom), o resultado favorecerá os clusters, exceto em regiões com marcadores esparsos.

O Google Maps suporta níveis de zoom de zero a um máximo de 20, dependendo da área. (Os intervalos suportados por outros serviços de mapa são semelhantes. Por exemplo, o Mapbox usa níveis de zoom de zero a um máximo de 23.) Como esses níveis de zoom também são valores inteiros, podemos simplesmente criar um cache separado para cada nível de zoom.

Para oferecer suporte a todos os níveis de zoom no Google Maps, exceto o nível zero, que é muito reduzido, criaremos 20 caches distintos. Cada cache armazenará todos os marcadores e clusters para todo o mapa, conforme clusterizado para o nível de zoom que representa.

Tipos de dados de cache

Cada cache armazenaria clusters e marcadores individuais. Para qualquer tipo de entrada, precisaremos preencher vários campos:

No entanto, o Redis permite que os usuários armazenem apenas a localização, mais uma única string, como o valor em um conjunto geoespacial. Para contornar essa restrição, serializamos os campos acima em uma string JSON. Em seguida, usamos essa string como o valor no Redis. O tamanho máximo de chaves e valores no Redis é 512 MB, o que é mais que suficiente para este caso de uso.

Preenchendo os caches

Para preencher os caches, recuperamos todos os marcadores do banco de dados. Para cada nível de zoom, executamos o algoritmo de agrupamento de mapas. Usamos o GEOADD do Redis para inserir os marcadores e clusters resultantes no cache do nível de zoom correspondente e passar a latitude e a longitude, além da string JSON descrita anteriormente.

A execução do algoritmo de agrupamento de mapas em todo o mapa neste estágio (em vez de em uma caixa delimitadora do usuário, sob demanda) pode teoricamente produzir algumas diferenças de borda no posicionamento do cluster, mas a experiência geral do usuário permanecerá a mesma.

Consultando o cache

Para uma solicitação de entrada, passamos a caixa delimitadora fornecida para o comando Redis GEOSEARCH , que consulta o cache do nível de zoom fornecido para recuperar candidatos de marcador e cluster na área.

Projetando um plano de atualização de cache

Uma atualização de cache de 20 níveis é cara, portanto, é melhor atualizar com a menor frequência que os requisitos do projeto permitirem. Por exemplo, a adição ou remoção de uma instalação desportiva no Playsports apenas marca a cache como obsoleta; um cron job por hora atualiza o cache, se necessário. Mais sobre isso na seção Cache Staleness.

Etapa 2: detalhes adicionais do marcador (opcional)

Neste ponto, a maioria dos aplicativos precisará buscar detalhes com base em IDs de marcadores individuais. Poderíamos tornar esse detalhe parte dos valores JSON stringificados no cache, mas em muitos aplicativos, os detalhes do marcador são específicos do usuário. Como há um único cache compartilhado para todos os usuários, não é possível armazenar esses campos adicionais lá.

Nossa solução otimizada pega os IDs dos marcadores individuais do resultado do cache e busca seus detalhes no banco de dados. Agora estamos procurando apenas os marcadores individuais que sobraram após o agrupamento. Não haverá muitos deles quando o mapa for reduzido (porque teremos principalmente clusters) nem quando ampliado (porque a área será pequena).

Em contraste, a solução ingênua procura todos os marcadores na caixa delimitadora (e seus detalhes) antes de agrupar. Assim, esta etapa – opcional, mas para muitos aplicativos, crucial – agora é executada muito mais rapidamente.

Etapa 3: retornando o resultado

Com os clusters construídos e os marcadores individuais aprimorados, agora podemos entregá-los ao cliente. Com exceção de alguns casos extremos inconsequentes, os dados resultantes são quase idênticos à solução ingênua, mas podemos fornecê-los muito mais rapidamente.

Considerações Adicionais

Agora vamos analisar dois fatores adicionais:

Necessidades de recursos

Vamos supor que o mapa de um aplicativo contém um total de N marcadores. Como existem até 20 níveis de zoom, precisaríamos armazenar, no máximo, 20N de itens de cache. Na prática, no entanto, o número real de itens de cache geralmente é muito menor devido ao agrupamento, especialmente nos níveis de zoom mais baixos. Na verdade, o número total de itens de cache distribuídos entre todos os caches do Playsports é de apenas ~2N.

Além disso, se assumirmos que o comprimento de um valor de cache (o JSON com string) é de ~250 caracteres (uma suposição razoável, pelo menos para Playsports) e o tamanho da string é de 1 byte por caractere, então a quantidade de armazenamento em cache necessária para o Os valores JSON seriam aproximadamente 2 * N * 250 bytes.

A esta figura adicionamos as estruturas de dados internas do Redis para os conjuntos ordenados usados ​​pelo GEOADD . O Redis usa 85 MB de memória para 1 milhão de pequenos pares de valores-chave, portanto, podemos supor que os internos do Redis representam menos de 100 bytes por item de cache. Isso significa que podemos usar uma instância Redis de 1 GB-RAM para dar suporte a até 1,4 milhão de marcadores. Mesmo no cenário improvável de os marcadores estarem espalhados uniformemente por todo o mapa, resultando em um número de itens de cache próximo de 20N, N ainda pode chegar a ~140.000. Como uma instância do Redis pode lidar com mais de 4 bilhões de chaves (2 ³² , para ser exato), isso não é um fator limitante.

Inatividade do cache

Dependendo do caso de uso, pode não ser suficiente atualizar o cache apenas periodicamente. Nesses casos, poderíamos usar uma fila de tarefas com taxa limitada. Isso reduziria a obsolescência do cache, enquanto ainda limitava o número de atualizações de cache e, portanto, a carga no sistema.

Após cada atualização de banco de dados, enfileiraríamos um trabalho de atualização de cache. Essa fila limitaria o número de tarefas a M por hora. Esse compromisso permite atualizações mais rápidas do que de hora em hora, mantendo uma carga relativamente baixa no sistema (dependendo de M).

As estratégias de armazenamento em cache superam os algoritmos de agrupamento de mapas

A solução otimizada para Playsports – mais de 50 vezes mais rápida que a solução ingênua – funcionou bem. Deve continuar funcionando bem, até atingirmos 1,4 milhão de marcadores ou mais de 100 vezes os dados existentes.

Para a maioria das solicitações de serviço da Web baseadas em mapa, é necessária alguma forma de pré-cálculo para permitir a escalabilidade. O tipo de tecnologia a ser utilizada, bem como o design específico, dependeria dos requisitos do negócio. As necessidades de obsolescência do cache, aumento de marcadores e o número de marcadores são características importantes a serem consideradas ao projetar uma solução.

Leitura adicional no Blog da Toptal Engineering:

• Pesquisa das melhores ferramentas de mapeamento online para desenvolvedores da Web: o roteiro para o roteiro
• Aventuras na programação e desenvolvimento de GPS: um tutorial geoespacial