Redis offre des fonctionnalités géospatiales via les commandes GEO, permettant d'ajouter, de rechercher et de calculer des distances entre des lieux. Cet article explore l'implémentation interne de ces commandes en s'appuyant sur une analyse du code source.

1. Fonctionnement des commandes GEO

Les commandes GEO de Redis, telles que GEOADD, GEODIST et GEORADIUS, s'appuient fondamentalement sur les opérations des ensembles triés (ZSETs). Voici comment elles sont traduites :

• GEOADD : Bien qu'utilisant ZADD en interne, cette commande procède d'abord à l'encodage des coordonnées de longitude et de latitude.
• GEORADIUS : Cette commande calcule d'abord la plage de valeurs Geohash correspondant à la zone cible, puis interroge l'ensemble trié pour trouver les membres se situant dans cette plage.

1.1. Encodage Geohash

Redis utilise l'algorithme Geohash pour convertir les paires de longitude/latitude en un entier de 52 bits, qui sert de 'score' dans l'ensemble trié. Le code source, notamment dans geohash.c, détaille ce processus.

// redis/src/geohash.c
uint64_t geohashEncodeWGS84(double longitude, double latitude, uint8_t step) {
   // La fonction principale d'encodage appelle une fonction plus générique
   // avec des bornes prédéfinies pour la Terre.
   return geohashEncode(/* bounds */ -180, 180, -90, 90, longitude, latitude, step);
}
 

• La longitude est comprise dans l'intervalle [-180, 180].
• La latitude est comprise dans l'intervalle [-90, 90].
• Le paramètre step contrôle la précision de l'encodage Geohash. Redis utilise par défaut 26 bits pour la longitude et 26 bits pour la latitude, résultant en un entier de 52 bits.

1.2. Structure de stockage

Les données GEO sont stockées dans Redis sous la forme d'ensembles triés. Chaque clé GEO correspond à un ensemble trié, où les membres sont les noms des lieux et les scores sont les valeurs Geohash encodées.

ZSET:
   Clé : "villes:geo"
   Membre : "Paris"
   Score : 3866730017297418240 (Entier de 52 bits résultant de l'encodage Geohash)
 

2. Pourquoi la latitude est limitée à 85° ?

Dans l'implémentation Redis GEO, la latitude est restreinte à la plage [-85°, 85°], et non aux [-90°, 90°] théoriques. Plusieurs raisons expliquent cette limitation :

2.1. Problèmes de bordure avec Geohash

L'algorithme Geohash utilise une courbe en Z (ou courbe de remplissage d'espace) pour découper l'espace bidimensionnel en régions et les représenter par des chaînes de caractères (ou des entiers). Près des pôles (latitude proche de ±90°), les variations de longitude peuvent entraîner des changements drastiques dans la valeur Geohash. Cela a pour conséquences :

• Discontinuité du Geohash : Des emplacements géographiquement proches aux pôles peuvent avoir des valeurs Geohash très différentes, ce qui nuit à la propriété de localité de l'algorithme.
• Inefficacité des requêtes : Les requêtes basées sur des plages Geohash (comme avec GEORADIUS) deviennent moins performantes car elles ne peuvent pas représenter efficacement les zones polaires de manière continue.

2.2. Déformations de la projection terrestre

• Dans les régions de haute latitude, la projection de Mercator, couramment utilisée pour représenter la Terre sur une carte plane, introduit des déformations importantes. Les dsitances peuvent être faussées.
• Bien que Redis utilise la formule de Haversine pour calculer les distances sphériques, les erreurs de calcul augmentent considérablement dans les zones de haute latitude en raison des approximations liées à la projection.

2.3. Restrictions dans le code source

Une vérification dans le fichier geo.c de Redis révèle cette contrainte explicite sur la latitude :

// redis/src/geo.c
int decodeGeohash(double bits, double *xy) {
   // ...
   // Vérifie si la latitude calculée dépasse les bornes acceptables.
   if (xy[1] > 85.05112878 || xy[1] < -85.05112878) {
       return 0; // La latitude est hors des limites valides.
   }
   // ...
}
 

La valeur 85.05112878° correspond à la latitude maximale valide dans la projection Web Mercator, calculée comme arctan(sinh(π)). Au-delà de cette latitude, la projection devient mathématiquement instable ou dégénère.

3. Synthèse

L'implémentation GEO de Redis combine ainsi l'efficacité des ensembles triés pour les requêtes avec les propriétés de l'encodage Geohash, tout en introduisant des ajustements ciblés (comme la limitation de latitude) pour garantir la précision et la performance des calculs géospatiaux.