Servir les clusters de cartes 50 fois plus rapidement grâce à une mise en cache plus intelligente

Les composants cartographiques qui comportent des marqueurs de localisation sont courants dans les applications mobiles d'aujourd'hui. Par exemple, l'application Airbnb met en évidence de tels marqueurs, extraits d'un service Web, pour représenter les propriétés disponibles sur une carte.

Pour s'assurer que le volume de données récupérées ne devienne pas ingérable à mesure que le nombre de marqueurs augmente, le serveur regroupe ces marqueurs avant de les envoyer au client. Un cluster cartographique est un marqueur spécialisé dont la position est égale à la position moyenne des marqueurs qu'il subsume. Il est étiqueté avec le nombre de marqueurs qu'il représente.

Néanmoins, les clusters de service peuvent créer des goulots d'étranglement en termes de performances, car un service Web doit récupérer chaque marqueur dans une région géographique donnée à partir de la base de données. Heureusement, ce problème peut être résolu avec une stratégie de mise en cache. Pour mieux comprendre comment concevoir et gérer un cache, examinons un exemple de point de terminaison d'API de carte que j'ai créé pour l'application Playsports.

Un problème de mise à l'échelle et une solution naïve

Dans la carte Playsports, chaque marqueur représente une installation sportive. Le point de terminaison de l'API de la carte doit renvoyer une liste de marqueurs et de groupes de marqueurs, en fonction d'un niveau de zoom et d'un cadre de délimitation.

Si le nombre de marqueurs est suffisamment petit, nous pouvons charger tous les marqueurs dans la zone de délimitation à partir de la base de données, les regrouper si nécessaire et renvoyer les marqueurs et les clusters résultants au client.

Au départ, le nombre maximal de marqueurs dans n'importe quelle zone de délimitation accessible dans Playsports était d'environ 400, ce qui entraînait une vitesse au point final d'environ 0,5 seconde. La mise en œuvre de la solution naïve était suffisante pour ce cas d'utilisation.

Cependant, à mesure que le nombre de marqueurs augmentait, l'inefficacité du mécanisme devenait évidente. Après avoir ajouté environ 10 000 nouveaux marqueurs d'installations sportives, la vitesse du point final a ralenti à environ 4,3 secondes sous certains niveaux de zoom. Ce taux est bien inférieur à la durée d'une seconde qui est généralement considérée comme le délai maximal acceptable pour une action de l'utilisateur dans une application mobile.

Pour mieux comprendre les inefficacités de la solution naïve, analysons-la dans le contexte de la requête marqueur :

1. Dans la base de données, récupérez tous les marqueurs dans la boîte englobante . Pour la plupart des applications, cette étape doit inclure la récupération des détails du marqueur au-delà du positionnement latitude/longitude. Par exemple, les marqueurs d'Airbnb incluent le prix, si l'utilisateur a déjà vu la propriété et s'il l'a marqué comme favori.
2. Sur les marqueurs récupérés, exécutez un algorithme de regroupement de cartes qui intègre le niveau de zoom.
3. Renvoyez les clusters et les marqueurs (détaillés) au client.

À mesure que le nombre de marqueurs augmente, les performances se détériorent aux étapes 1 et 2 :

• Lorsque la boîte englobante est suffisamment grande et que plus de 10 000 marqueurs nécessitent une recherche détaillée via un JOIN, la requête de la base de données ralentit considérablement (de 1 à 2 secondes).
• L'alimentation de 10 000 éléments à l'algorithme de regroupement de cartes prend environ 250 millisecondes supplémentaires.

En supposant une taille de fenêtre constante, lorsqu'une boîte englobante est relativement grande, le niveau de zoom est généralement faible (c'est-à-dire qu'il effectue un zoom arrière important). Sous de faibles niveaux de zoom, les résultats ont tendance à favoriser les clusters pour éviter l'encombrement visuel. Ainsi, le plus grand potentiel d'optimisation réside dans la première étape de la solution, où des milliers de marqueurs individuels sont chargés. Nous n'avons pas besoin de la plupart de ces marqueurs dans le résultat. Nous n'avons besoin que de chacun d'eux pour compter vers un cluster.

Concevoir la solution optimisée

La solution naïve prend beaucoup plus de temps pour effectuer une requête dans le pire des cas : une boîte englobante maximale dans une région dense en marqueurs. En revanche, la solution optimisée ne prendrait que 73 ms, ce qui représente une accélération d'environ 58 fois. D'un niveau élevé, cela ressemble à ceci:

1. La stratégie de mise en cache. Récupérez des marqueurs et des clusters dans une zone de délimitation à partir d'un cache spécifique au niveau de zoom.
2. Détail du marqueur supplémentaire (facultatif). Améliorez les marqueurs avec une charge utile extraite de la base de données.
3. Renvoyer le résultat. Renvoyez les marqueurs et les clusters au client.

La principale complexité réside dans l'architecture du cache (c'est-à-dire la première étape).

Étape 1 : La stratégie de mise en cache

Cette étape principale se compose de six éléments :

La technologie

Redis est une base de données rapide en mémoire qui est couramment utilisée comme cache. Son indexation géospatiale intégrée utilise l'algorithme Geohash pour le stockage et la récupération efficaces des points de latitude-longitude, ce qui est précisément ce dont nous avons besoin pour nos marqueurs.

Un cache pour chaque niveau de zoom

Le degré de regroupement de la carte (si des marqueurs uniques ou des regroupements sont renvoyés) est déterminé par le niveau de zoom transmis au point de terminaison.

• Pour les niveaux de zoom élevés (c'est-à-dire zoom rapproché), le résultat favorisera les marqueurs individuels, sauf dans les régions denses en marqueurs.
• Pour les faibles niveaux de zoom (c'est-à-dire, un zoom arrière important), le résultat favorisera les clusters, sauf dans les régions à marqueurs clairsemés.

Google Maps prend en charge les niveaux de zoom de zéro à un maximum de 20, selon la zone. (Les plages prises en charge par d'autres services de carte sont similaires. Par exemple, Mapbox utilise des niveaux de zoom de zéro à un maximum de 23.) Étant donné que ces niveaux de zoom sont également des valeurs entières, nous pouvons simplement créer un cache séparé pour chaque niveau de zoom.

Pour prendre en charge tous les niveaux de zoom dans Google Maps, à l'exception du niveau zéro, qui est trop éloigné, nous allons créer 20 caches distincts. Chaque cache stockera tous les marqueurs et clusters pour l'ensemble de la carte, regroupés pour le niveau de zoom qu'il représente.

Types de données du cache

Chaque cache stockerait des grappes et des marqueurs individuels. Pour chaque type d'entrée, nous devrons remplir plusieurs champs :

Cependant, Redis permet aux utilisateurs de stocker uniquement l'emplacement, plus une seule chaîne, en tant que valeur dans un ensemble géospatial. Pour contourner cette restriction, nous sérialisons les champs ci-dessus dans une chaîne JSON. Nous utilisons ensuite cette chaîne comme valeur dans Redis. La taille maximale des clés et des valeurs dans Redis est de 512 Mo, ce qui est plus que suffisant pour ce cas d'utilisation.

Remplir les caches

Pour remplir les caches, nous récupérons tous les marqueurs de la base de données. Pour chaque niveau de zoom, nous exécutons l'algorithme de map-clustering. Nous utilisons GEOADD de Redis pour insérer les marqueurs et les clusters résultants dans le cache du niveau de zoom correspondant, et transmettons la latitude et la longitude, ainsi que la chaîne JSON décrite précédemment.

L'exécution de l'algorithme de clustering de cartes sur l'ensemble de la carte à ce stade (plutôt que sur une zone de délimitation de l'utilisateur, à la demande) pourrait théoriquement produire des différences de bord dans le placement des clusters, mais l'expérience utilisateur globale restera la même.

Interroger le cache

Pour une requête entrante, nous transmettons le cadre de délimitation donné à la commande Redis GEOSEARCH , qui interroge le cache du niveau de zoom donné pour récupérer les candidats marqueurs et clusters dans la zone.

Conception d'un plan d'actualisation du cache

Une actualisation du cache à 20 niveaux coûte cher, il est donc préférable d'actualiser aussi rarement que le permettent les exigences de votre projet. Par exemple, l'ajout ou la suppression d'une installation sportive dans Playsports marque uniquement le cache comme obsolète ; une tâche cron horaire rafraîchit ensuite le cache, si nécessaire. Plus d'informations à ce sujet dans la section Obsolescence du cache.

Étape 2 : Détails supplémentaires sur le marqueur (facultatif)

À ce stade, la plupart des applications devront récupérer les détails en fonction des identifiants de marqueurs individuels. Nous pourrions intégrer ce détail aux valeurs JSON sous forme de chaîne dans le cache, mais dans de nombreuses applications, les détails du marqueur sont spécifiques à l'utilisateur. Comme il existe un seul cache partagé pour tous les utilisateurs, il n'est pas possible d'y stocker ces champs supplémentaires.

Notre solution optimisée extrait les identifiants des marqueurs individuels du résultat du cache et récupère leurs détails dans la base de données. Maintenant, nous recherchons uniquement les marqueurs individuels qui restent après le regroupement. Il n'y en aura pas trop lorsque la carte sera agrandie (parce que nous aurons principalement des clusters) ni lors d'un zoom avant (parce que la zone sera petite).

En revanche, la solution naïve recherche tous les marqueurs dans la boîte englobante (et leurs détails) avant le regroupement. Ainsi, cette étape, facultative mais cruciale pour de nombreuses applications, s'exécute désormais beaucoup plus rapidement.

Étape 3 : retour du résultat

Avec les clusters construits et les marqueurs individuels améliorés, nous pouvons maintenant les livrer au client. Mis à part quelques cas marginaux sans conséquence, les données résultantes sont presque identiques à la solution naïve, mais nous sommes en mesure de les fournir beaucoup plus rapidement.

Autres considérations

Examinons maintenant deux facteurs supplémentaires :

Besoins en ressources

Supposons que la carte d'une application contienne N marqueurs au total. Comme il y a jusqu'à 20 niveaux de zoom, nous aurions besoin de stocker au maximum 20 N éléments de cache. En pratique, cependant, le nombre réel d'éléments de cache est souvent beaucoup plus faible en raison du regroupement, en particulier dans les niveaux de zoom inférieurs. En fait, le nombre total d'éléments de cache répartis entre tous les caches de Playsports n'est que d'environ 2N.

De plus, si nous supposons que la longueur d'une valeur de cache (le JSON stringifié) est d'environ 250 caractères (une hypothèse raisonnable, au moins pour Playsports) et que la taille de la chaîne est de 1 octet par caractère, alors la quantité de stockage de cache nécessaire pour le Les valeurs JSON seraient d'environ 2 * N * 250 octets.

À ce chiffre, nous ajoutons les structures de données internes de Redis pour les ensembles triés utilisés par GEOADD . Redis utilise 85 Mo de mémoire pour 1 million de petites paires clé-valeur, nous pouvons donc supposer que les composants internes de Redis représentent moins de 100 octets par élément de cache. Cela signifie que nous pourrions utiliser une instance Redis de 1 Go de RAM pour prendre en charge jusqu'à 1,4 million de marqueurs. Même dans le scénario improbable où les marqueurs seraient répartis uniformément sur toute la carte, ce qui entraînerait un nombre d'éléments de cache proche de 20N, N pourrait encore monter jusqu'à ~140 000. Puisqu'une instance Redis peut gérer plus de 4 milliards de clés (2 ³² , pour être exact), ce n'est pas un facteur limitant.

Obsolescence du cache

Selon le cas d'utilisation, il peut ne pas être suffisant d'actualiser le cache uniquement périodiquement. Dans de tels cas, nous pourrions utiliser une file d'attente de tâches à débit limité. Cela réduirait l'obsolescence du cache, tout en limitant le nombre d'actualisations du cache, et donc la charge sur le système.

Après chaque mise à jour de la base de données, nous mettions en file d'attente une tâche d'actualisation du cache. Cette file d'attente limiterait le nombre de tâches à M par heure. Ce compromis permet des mises à jour plus rapides qu'une heure tout en maintenant une charge relativement faible sur le système (en fonction de M).

Les stratégies de mise en cache l'emportent sur les algorithmes de clustering de cartes

La solution optimisée pour Playsports - plus de 50 fois plus rapide que la solution naïve - a bien fonctionné. Il devrait continuer à bien fonctionner, jusqu'à ce que nous atteignions 1,4 million de marqueurs ou plus de 100 fois les données existantes.

Pour la plupart des demandes de service Web basées sur des cartes, une certaine forme de précalcul est nécessaire pour permettre l'évolutivité. Le type de technologie à utiliser, ainsi que la conception spécifique, dépendraient des besoins de l'entreprise. Les besoins d'obsolescence du cache, l'augmentation des marqueurs et le nombre de marqueurs sont des caractéristiques importantes à prendre en compte lors de la conception d'une solution.

Lectures complémentaires sur le blog Toptal Engineering :

• Enquête sur les meilleurs outils de cartographie en ligne pour les développeurs Web : de la feuille de route à la feuille de route
• Aventures dans la programmation et le développement GPS : un didacticiel géospatial