Plugin Elasticsearch de recherche spatiales via un R-Tree

Elasticsearch est un logiciel serveur permettant d’indexer puis de rechercher des données. Il met à disposition un moteur de recherche très puissant, qui peut être distribué sur plusieurs noeuds d’un cluster. Il s’adapte correctement aux architectures scalables. Il permet de faire des recherches sur tout type de document quasiment en temps réel. C’est un logiciel libre, écrit en Java et publié en Open Source sous licence Apache, qui s’appuie sur Lucene pour la création d’index. Très simple d’utilisation, il dispose d’une API Rest et communique dans le format JSON. Il existe aussi une API client dans de nombreux langages (Java, Javascript, groovy, .NET, PHP, Perl, Python et Ruby).

Description du mécanisme de plugin ES

Du fait de l’accessibilité de son code, de nombreux développeurs ont commencé à customiser le code d’Elasticsearch souhaitant le rendre plus adéquat à leurs besoins. Elasticsearch a donc rapidement intégré un mécanisme de plugin, permettant à chacun de modifier les fonctionnalités de base du logiciel ou d’en ajouter de nouvelles.

Il existe deux grands types de plugin :

  • Plugin Java : un jar contenant du code à incorporer aux librairies d’Elasticsearch
  • Plugin “Site” : permet d’ajouter des services web, pages html / javascript / CSS

Un plugin peut, bien entendu, mélanger code Java et pages web en une seule archive. De nombreux plugins ont vu le jour au sein de la grande communauté de développeurs qui suit Elasticsearch et certains ont même été intégrés au code source du logiciel (devenant ainsi des plugins officiels).

Elasticsearch permet de customiser les aspects suivants :

  • Extension de l’API Rest.
  • Système de notification de modification des données.
  • Analyse / tokenisation des termes à l’indexation.
  • Découverte de machines via le réseau (Cloud Amazon, S3, Google cloud).
  • Administration et UI.
  • “Mapper” : permet d’ajouter de nouveaux types, structures de données.
  • Scripts : ajout du support pour diffèrents langages de script (javascript, python).
  • Sécurisation des APIs, et des systèmes d’authentification.
  • Système de fichier (Azure, Amazon, Hadoop).
  • “Transport” : mécanisme de communication HTTP.

Description des besoins de recherches spatiales dans le monde de la géomatique

Dans le cadre de la géomatique, le besoin de cataloguer / rechercher des metadonnées spatiales existe depuis de nombreuses années. De plus, la directive INSPIRE, adoptée en 2007, incite les différents partenaires européens à partager et à mettre à disposition les données environnementales. Les SIG (systèmes d’informations géographiques) disposent donc d’un volume de données en constante augmentation.

Pour simplifier et harmoniser en globalité la recherche de données satellites, environnementales et géographiques dans les différents pays et organisations, L’OCG (Open Geospatial Consortium) développe et promouvoit des standards et spécifications ouvertes. Ils garantissent l’interopérabilité des contenus, des services et des échanges.

Le protocole CSW (Catalog Service Web) est un service web de catalogage de métadonnées spatiales, dont le standard est fourni par l’OGC. Il permet de rechercher et lister différentes ressources telles que des données géospatiales, des services web (autres services standardisés par l’OGC), etc. Il diffuse des metadonnées au format XML issues de différentes normes (Dublin Core, ISO 19139, Ebrim, etc.).

Ce standard définit un certain nombre de filtres spatiaux et textuels afin d’effectuer sa recherche dans le système d’information géographique.

Depuis 2008, Geomatys a créé sa propre implementation du CSW, au sein du logiciel Constellation (qui regroupe de nombreux services web standardisés de diffusion de données géographiques). Ce catalogue comprend un index basé sur Lucene, avec une sur-couche géographique qui permet d’ajouter à sa recherche des filtres spatiaux définis par l’OGC.

Suite à l’industrialisation du logiciel Constellation et à son intégration dans un environnement Cloud / Big Data et étant  familier avec Lucene et Elasticsearch sur de nombreux projets, nous avons décidé de migrer notre index CSW sur cette solution. Cela nous a permis de gérer un volume massif de metadonnées tout en gardant de bonnes performances de recherche.

Architecture du plugin

Initialement implémentée pour Lucene, la recherche géographique est effectuée par un R-tree, dans lequel on enregistre une ou plusieurs géométries par métadonnée (ou document au sens Lucene). On insère seulement des enveloppes, dans le cas d’un polygone, on utilise son enveloppe englobante.

Cet arbre est défini dans un CRS (Coordinate Reference System). Chaque géométrie que l’on ajoute dans l’arbre doit être reprojetée, si elle n’est pas déjà exprimée dans le CRS de l’arbre. Concrètement, le R-tree va indexer ou ranger des éléments géographiques selon certains critères mathématiques liés, par exemple, à leur situation géographique, leur taille, volume etc … Ces différents algorithmes, (ou critères mathématiques),  permettent ainsi de retrouver ou rechercher un ou plusieurs éléments parmi un très grand nombre.

Globalement, le fonctionnement consiste durant l’insertion à regrouper les éléments à insérer dans des “boites” qui seront elles même regroupées par “boites” quand elles auront atteint une certaine limite de taille et indéfiniment jusqu’au dernier élément.

Ainsi, pendant une recherche, par de simples intersections de coordonnées successives, nous parcourons l’arbre de “boites” en “boites” afin d’évincer un grand nombre d’éléments et ainsi retrouver ceux qui nous intéressent dans un temps très court.

709px-RTree-Visualization-3D.svg

Le R-tree se compose :

  • D’un fichier binaire contenant l’arbre afin d’éviter la montée en charge de la mémoire et d’assurer la persistance de celui-ci.
  • D’un ou plusieurs fichiers permettant de sérialiser le CRS d’un arbre.

Lorsque l’on recherche les géométries qui intersectent (ou diffèrent d’autres filtres spatiaux), le R-Tree permet de rapidement évincer les résultats qui ne correspondent pas aux filtres.

Ce R-tree s’appuie sur la librairie Apache SIS pour la lecture des CRS.

Le plugin est composé de 4 customisations des APIs Elasticsearch :

  • Un parseur de requête qui reçoit les recherches spatiales des utilisateurs et les traduit en filtre Lucene.
  • Un “Mapper” qui définit  la structure pour un champ géométrique.
  • Un “Analyzer” (geotk-classic) qui spécifie les règles d’indexation et tokenisation des termes (Pour les recherches non spatiales).
  • Un “IndexListener” qui intercepte les insertions/délétions de document afin de mettre a jour le R-tree.

Fonctionnement du plugin

Mécanisme de mise à jour de l’arbre

Tout d’abord, l’utilisateur crée un index puis définit un type de document (structure de données) qui inclut un ou plusieurs champs de type géométrique.

exemple de mapping :

{  "metadata_type": {
       "properties": {
         "title": { "type": "string",  "analyzer": "geotk-classic" },
         "geometry": {"type": "bbox"}
}
}

Ensuite, il insère ces documents contenant les informations et géométries de chaque métadonnée.

{ "title": "box 1",
   "desert": [{
              "crs": "CRS:84",
              "maxx": "-25.0",
              "maxy": "-40.0",
              "minx": "-40.0",
              "miny": "-50.0"
         }]
}

 

Les requêtes d’insertion sont interceptées. Si le document contient un champ géométrique et qu’aucun R-tree n’est présent au sein de l’index, un nouvel arbre est créé avec le CRS de l’objet en question. Sinon, il est ajouté à l’arbre déjà présent (si le CRS de l’arbre est diffèrent de celui de l’objet à insérer, ce dernier est reprojeté vers le CRS de l’arbre).

De même, lors d’une délétion, le plugin vérifie si l’arbre contient le document à détruire, et le retire, si besoin est.

Le R-tree se situe au niveau le plus bas de l’architecture Elasticsearch, c’est-à-dire les indexes Lucene. Un serveur Elasticsearch se constitue de plusieurs noeuds (Nodes) qui se situent sur une ou plusieurs machines. L’ensemble des données est ensuite découpé en plusieurs “Shard” qui sont distribués, répliqués et dispatchés entre les différents noeuds.
Chaque Shard contient une partie des données de chaque index, cette partie correspond à un index Lucene. C’est à cette endroit que se place notre R-tree.

ElasticSearch_RTree_plugin_copy

Un index peut comprendre plusieurs R-tree (si il y a plusieurs champs géométriques). Si aucune des données du Shard ne contient le champ géométrique, le R-tree n’est pas construit.

Lors de la duplication des Shards, le R-tree est dupliqué en même temps que les données.

Mécanisme du filtre spatial

Afin d’effectuer une recherche avec un filtre spatial l’utilisateur fournit :

  • Le type du filtre parmi les suivants :
    • BBOX,
    • INTERSECTS
    • EQUALS
    • CONTAINS
    • DISJOINT
    • TOUCHES
    • WITHIN
    • CROSSES
    • DWITHIN (distance)
    • BEYOND (distance)
    • OVERLAPS
  • Une géométrie (Point, ligne, enveloppe, polygone) avec son CRS
  • le champ sur lequel est appliqué le filtre.

 

exemple filtre BBOX :

{"ogc_filter": {
     "desert": {
      "filter": "BBOX",
         "minx": -20.0,
         "maxx": 20.0,
         "miny": -20.0,
         "maxy": 20.0,
         "CRS": "CRS:84" 
   }
        }
}

exemple filtre distance :

{"ogc_filter": {
     "desert": {
         "filter": "DWITHIN",
         "x": 0.0,
         "y": 0.0,
         "distance": 6000.0,
         "distance_unit": "kilometers",
         "CRS": "CRS:84"
     }
       }
}

Le parseur transforme ensuite la requête en filtre Lucene qui est exécuté sur chaque Shard du serveur. Le R-Tree évince une majorité de résultats et un second filtre est éventuellement appliqué sur les résultats restants (dépend du type de filtre et de géométrie).

Pour conclure, la question du développement d’un nouveau plugin de recherche spatiale s’est posée. Il existe déjà plusieurs plugins et solutions officielles qui traitent de ce cas. Au sein de la communauté Elasticsearch, de nombreux développeurs se sont intéressés à l’indexation spatiale, les dernières versions commencent à compléter les  types de filtres disponibles (INTERSECTS, DISJOINT, WITHIN, CONTAINS et BBOX) et les types de géométries sont quasiment tous présents.

Cependant, il n’y a toujours aucune trace des systèmes de coordonnées, ce qui ne peut s’ignorer quand on travaille dans la géomatique, et qu’on est limité à des géométries en 2 dimensions. Bien que le plugin développé est, dans sa version actuelle, lui aussi en 2D, la prochaine étape est pour nous le multidimensionnel, déjà supporté par le R-Tree.

Laissez un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *