Servir clústeres de mapas 50 veces más rápido con un almacenamiento en caché más inteligente

Los componentes de mapas que cuentan con marcadores de ubicación son comunes en las aplicaciones móviles de hoy. Por ejemplo, la aplicación de Airbnb destaca dichos marcadores, obtenidos de un servicio web, para representar las propiedades disponibles en un mapa.

Para garantizar que el volumen de datos obtenidos no se vuelva inmanejable a medida que aumenta la cantidad de marcadores, el servidor agrupa esos marcadores antes de enviarlos al cliente. Un grupo de mapas es un marcador especializado cuya posición es igual a la posición promedio de los marcadores que subsume. Está etiquetado con el número de marcadores que representa.

Aún así, los clústeres de servicio pueden crear cuellos de botella en el rendimiento porque un servicio web debe recuperar todos los marcadores dentro de una región geográfica determinada de la base de datos. Afortunadamente, este problema se puede resolver con una estrategia de almacenamiento en caché. Para entender mejor cómo diseñar y mantener un caché, veamos un punto final de API de mapa de ejemplo que creé para la aplicación Playsports.

Un problema de escala y una solución ingenua

En el mapa de Playsports, cada marcador representa una instalación deportiva. El extremo de la API del mapa debe devolver una lista de marcadores y grupos de marcadores, dado un nivel de zoom y un cuadro delimitador.

Si el número de marcadores es lo suficientemente pequeño, podemos cargar todos los marcadores en el cuadro delimitador de la base de datos, agruparlos según sea necesario y devolver los marcadores y grupos resultantes al cliente.

Al principio, la cantidad máxima de marcadores en cualquier cuadro delimitador accesible en Playsports era de ~400, lo que resultaba en una velocidad de punto final de ~0,5 segundos. La implementación de la solución ingenua fue suficiente para este caso de uso.

Sin embargo, a medida que crecía el número de marcadores, la ineficiencia del mecanismo se hizo evidente. Después de agregar aproximadamente 10 000 nuevos marcadores de instalaciones deportivas, la velocidad del punto final se redujo a aproximadamente 4,3 segundos con algunos niveles de zoom. Esta tasa está muy por debajo de la duración de un segundo que generalmente se considera como el retraso máximo aceptable para una acción del usuario en una aplicación móvil.

Para comprender mejor las ineficiencias de la solución ingenua, analicémosla en el contexto de la consulta del marcador:

1. De la base de datos, recupere todos los marcadores en el cuadro delimitador . Para la mayoría de las aplicaciones, este paso debe incluir la obtención de detalles del marcador más allá del posicionamiento de latitud/longitud. Por ejemplo, los marcadores de Airbnb incluyen el precio, si el usuario ya ha visto la propiedad y si la ha marcado como favorita.
2. En los marcadores recuperados, ejecute un algoritmo de agrupamiento de mapas que incorpore el nivel de zoom.
3. Devuelve grupos y marcadores (detallados) al cliente.

A medida que aumenta el número de marcadores, el rendimiento se deteriora en los pasos 1 y 2:

• Cuando el cuadro delimitador es lo suficientemente grande y más de 10 000 marcadores requieren una búsqueda detallada a través de JOIN, la consulta de la base de datos se ralentiza drásticamente (de 1 a 2 segundos).
• Introducir 10 000 elementos en el algoritmo de agrupamiento de mapas lleva otros ~250 milisegundos.

Suponiendo un tamaño de ventana constante, cuando un cuadro delimitador es relativamente grande, el nivel de zoom suele ser bajo (es decir, se aleja demasiado). Con niveles de zoom bajos, los resultados tienden a favorecer los grupos para evitar la aglomeración visual. Por lo tanto, el mayor potencial de optimización se encuentra en el primer paso de la solución, donde se cargan miles de marcadores individuales. No necesitamos la mayoría de estos marcadores en el resultado. Solo necesitamos que cada uno de ellos cuente para un grupo.

Arquitectura de la solución optimizada

La solución ingenua tarda mucho más en completar una consulta en el peor de los casos: un cuadro delimitador máximo en una región densa en marcadores. Por el contrario, la solución optimizada tardaría solo 73 ms, lo que representa una aceleración de ~58x. Desde un nivel alto, se ve así:

1. La estrategia de almacenamiento en caché. Recupere marcadores y grupos en un cuadro delimitador desde una memoria caché específica del nivel de zoom.
2. Detalle de marcador adicional (opcional). Mejora los marcadores con una carga extraída de la base de datos.
3. Devolviendo el Resultado. Devuelve marcadores y clústeres al cliente.

La principal complejidad radica en la arquitectura de la memoria caché (es decir, el primer paso).

Paso 1: la estrategia de almacenamiento en caché

Este paso principal consta de seis componentes:

Tecnología

Redis es una base de datos en memoria rápida que se usa comúnmente como caché. Su indexación geoespacial integrada utiliza el algoritmo Geohash para el almacenamiento y la recuperación eficientes de puntos de latitud y longitud, que es precisamente lo que necesitamos para nuestros marcadores.

Un caché para cada nivel de zoom

El grado de agrupación de mapas (ya sea que se devuelvan marcadores individuales o grupos) está determinado por el nivel de zoom pasado al punto final.

• Para niveles altos de zoom (es decir, acercamiento), el resultado favorecerá a los marcadores individuales, excepto en las regiones densas de marcadores.
• Para niveles de zoom bajos (es decir, alejado mucho), el resultado favorecerá a los grupos, excepto en las regiones con pocos marcadores.

Google Maps admite niveles de zoom desde cero hasta un máximo de 20, según el área. (Los rangos admitidos por otros servicios de mapas son similares. Por ejemplo, Mapbox usa niveles de zoom desde cero hasta un máximo de 23). Dado que estos niveles de zoom también son valores enteros, simplemente podemos crear un caché separado para cada nivel de zoom.

Para admitir todos los niveles de zoom en Google Maps, excepto el nivel cero, que está demasiado alejado, crearemos 20 cachés distintos. Cada caché almacenará todos los marcadores y grupos para todo el mapa, como agrupados para el nivel de zoom que representa.

Tipos de datos de caché

Cada caché almacenaría grupos y marcadores individuales. Para cualquier tipo de entrada, necesitaremos completar varios campos:

Sin embargo, Redis permite a los usuarios almacenar solo la ubicación, además de una sola cadena, como valor en un conjunto geoespacial. Para sortear esta restricción, serializamos los campos anteriores en una cadena JSON. Luego usamos esta cadena como el valor en Redis. El tamaño máximo de claves y valores en Redis es de 512 MB, que es más que suficiente para este caso de uso.

Llenar los cachés

Para llenar los cachés, recuperamos todos los marcadores de la base de datos. Para cada nivel de zoom, ejecutamos el algoritmo de agrupamiento de mapas. Usamos GEOADD de Redis para insertar los marcadores y grupos resultantes en la memoria caché del nivel de zoom correspondiente y pasar la latitud y la longitud, además de la cadena JSON descrita anteriormente.

Ejecutar el algoritmo de agrupamiento de mapas en todo el mapa en esta etapa (en lugar de en un cuadro delimitador del usuario, a pedido) podría producir teóricamente algunas diferencias de borde en la ubicación del agrupamiento, pero la experiencia general del usuario seguirá siendo la misma.

Consultando el caché

Para una solicitud entrante, pasamos el cuadro delimitador dado al comando GEOSEARCH de Redis, que consulta la memoria caché del nivel de zoom dado para recuperar marcadores y grupos candidatos en el área.

Diseño de un plan de actualización de caché

Una actualización de caché de 20 niveles es costosa, por lo que es mejor actualizar con la menor frecuencia que lo permitan los requisitos de su proyecto. Por ejemplo, la adición o eliminación de una instalación deportiva en Playsports solo marca el caché como obsoleto; un trabajo cron por hora luego actualiza el caché, si es necesario. Más sobre esto en la sección Caché obsoleta.

Paso 2: Detalle de marcador adicional (opcional)

En este punto, la mayoría de las aplicaciones necesitarán obtener detalles en función de los identificadores de marcadores individuales. Podríamos hacer que este detalle forme parte de los valores JSON en cadena en la memoria caché, pero en muchas aplicaciones, los detalles del marcador son específicos del usuario. Dado que hay un único caché compartido para todos los usuarios, no es posible almacenar estos campos adicionales allí.

Nuestra solución optimizada toma los ID de los marcadores individuales del resultado del caché y obtiene sus detalles de la base de datos. Ahora solo estamos buscando los marcadores individuales que quedan después de la agrupación. No habrá demasiados de estos cuando el mapa se aleje (porque tendremos principalmente grupos) ni cuando se acerque (porque el área será pequeña).

Por el contrario, la solución ingenua busca todos los marcadores en el cuadro delimitador (y sus detalles) antes de agruparlos. Por lo tanto, este paso, opcional, pero crucial para muchas aplicaciones, ahora se ejecuta mucho más rápido.

Paso 3: Devolver el resultado

Con los grupos construidos y los marcadores individuales mejorados, ahora podemos entregarlos al cliente. Aparte de algunos casos extremos intrascendentes, los datos resultantes son casi idénticos a la solución ingenua, pero podemos entregarlos mucho más rápido.

Consideraciones adicionales

Ahora veamos dos factores adicionales:

Necesidades de recursos

Supongamos que el mapa de una aplicación contiene N marcadores en total. Como hay hasta 20 niveles de zoom, necesitaríamos almacenar, como máximo, 20N elementos de caché. Sin embargo, en la práctica, el número real de elementos de caché suele ser mucho menor debido a la agrupación, especialmente en los niveles de zoom más bajos. De hecho, la cantidad total de elementos de caché distribuidos entre todos los cachés de Playsports es solo ~2N.

Además, si asumimos que la longitud de un valor de caché (el JSON en cadena) es de ~250 caracteres (una suposición razonable, al menos para Playsports) y el tamaño de la cadena es de 1 byte por carácter, entonces la cantidad de almacenamiento en caché necesaria para el Los valores JSON serían aproximadamente 2 * N * 250 bytes.

A esta figura le agregamos las estructuras de datos internas de Redis para los conjuntos ordenados utilizados por GEOADD . Redis usa 85 MB de memoria para 1 millón de pares clave-valor pequeños, por lo que podemos suponer que las partes internas de Redis representan menos de 100 bytes por elemento de caché. Eso significa que podríamos usar una instancia de Redis de 1 GB de RAM para admitir hasta 1,4 millones de marcadores. Incluso en el escenario improbable de que los marcadores se distribuyan uniformemente por todo el mapa, lo que daría como resultado que la cantidad de elementos del caché se acerque a 20N, N aún podría aumentar a ~140,000. Dado que una instancia de Redis puede manejar más de 4 mil millones de claves (2 ³² , para ser exactos), este no es un factor limitante.

Caché obsoleto

Según el caso de uso, puede que no sea suficiente actualizar la memoria caché solo periódicamente. En tales casos, podríamos usar una cola de tareas de velocidad limitada. Reduciría la obsolescencia de la caché, al mismo tiempo que limitaría la cantidad de actualizaciones de caché y, por lo tanto, la carga en el sistema.

Después de cada actualización de la base de datos, pondríamos en cola un trabajo de actualización de caché. Esta cola limitaría el número de tareas a M por hora. Este compromiso permite actualizaciones más rápidas que cada hora mientras mantiene una carga relativamente baja en el sistema (dependiendo de M).

Las estrategias de almacenamiento en caché superan los algoritmos de agrupamiento de mapas

La solución optimizada para Playsports, más de 50 veces más rápida que la solución ingenua, ha funcionado bien. Debería seguir funcionando bien, hasta que lleguemos a 1,4 millones de marcadores o más de 100 veces los datos existentes.

Para la mayoría de las solicitudes de servicios web basados ​​en mapas, se necesita algún tipo de cálculo previo para permitir la escalabilidad. El tipo de tecnología a utilizar, así como el diseño específico, dependerán de los requerimientos del negocio. Las necesidades de obsolescencia de la memoria caché, el aumento de marcadores y la cantidad de marcadores son características importantes que se deben tener en cuenta al diseñar una solución.

Lecturas adicionales en el blog de ingeniería de Toptal:

• Encuesta de las mejores herramientas de creación de mapas en línea para desarrolladores web: la hoja de ruta para la hoja de ruta
• Aventuras en la programación y el desarrollo de GPS: un tutorial geoespacial