• BLOG

  • Modélisation d'un arbre avec Django et PostgreSQL (FR)

    Tue 27 November 2018 Dan Lousqui

    Share on: Twitter - Facebook - Google+

    python tree

    Au cas où vous ne le saviez déjà pas, Seald permet de chiffrer des documents. L'une utilisation classique de l'application est de chiffrer un fichier dans un répertoire partagé. Cependant, une fois chiffré, si un utilisateur a besoin de transférer le fichier à une nouvelle personne, elle risque de le déchiffrer et d'envoyer le fichier initialement protégé de façon non sécurisée. C'est pour cela que nous avons développé une nouvelle fonctionnalité : la possibilité de transférer un document chiffré.

    (TLDR: Si ce qui vous intéresse est directement le modèle choisi pour implémenter un arbre avec l'ORM Django et une base de données Postgres, directement aller au Résultat)

    Cela pose pas mal de problématiques, notamment, qui a le droit d'avoir accès aux événements journalisés et qui a le droit de révoquer l'accès à un fichier ? Pour répondre à cela, nous avons mis en place un système d'arborescence, où un utilisateur à tous les droits sur ses enfants.

    Par exemple, si Alice chiffre un fichier pour Bob et Charly, et que Charly le transfert Dylan, alors :

    • Alice aura tous les droits sur tout le monde ;
    • Bob n'aura de droits sur personne ;
    • Charly aura des droits uniquement sur Dylan ;
    • Dylan n'aura de droits sur personne.

    tree

    Il s'agit d'un modèle d'arbre. Le but de cet article sera de montrer les choix d'implémentation que nous avons eu pour réaliser cela avec Python et PostgreSQL via l'ORM de Django.

    Base et contexte

    De base, un document chiffré avec Seald est représenté dans la base de données avec le modèle Django suivant :

    class Document(model.Model):
        id = models.UUIDField(primary_key=True, default=uuid.uuid4)
        owner = models.ForeignKey("SealdUser", on_delete=models.CASCADE)
        created = models.DateTimeField(auto_now_add=True)
    

    Nous voulons créer un nouveau modèle, tel que pour chaque destinataire d'un message, l'instance de ce modèle existe, permettant de savoir sur qui le destinataire à des droits, et qui a des droits sur lui :

    class DocumentAccessRight(model.Model):
        user = models.ForeignKey("SealdUser", on_delete=models.CASCADE)
        document = models.ForeignKey("Document", on_delete=models.CASCADE)
        # Todo: Ajouter des champs
    
        def get_children(self):
            # Todo: implémenter
            raise NotImplementedError
    
        def get_parents(self):
            # Todo: implémenter
            raise NotImplementedError
    

    Ainsi, pour reprendre l'exemple précédent, si Alice veut révoquer un accès à Bob, il suffit de vérifier que Alice soit parent de Bob dans l'arborescence des DocumentAccessRight.

    Maintenant... comment implémenter cela ?

    Approche simpliste

    Une première façon de faire, assez naïve, est simplement d'ajouter un champ parent à la classe, qui ferait le lien entre les enfants et les parents :

    from django.db import models
    
    class DocumentAccessRight(model.Model):
        user = models.ForeignKey("SealdUser", on_delete=models.CASCADE)
        document = models.ForeignKey("Document", on_delete=models.CASCADE)
        parent = models.ForeignKey(
            "DocumentAccessRight",
            on_delete=models.CASCADE,
            related_name="first_children",
            null=True
        )
    

    On peut prendre pour convention que le parent d'un owner d'un document est None. Ainsi, l'implémentation des fonctions peut être la suivante:

    from django.db import models
    
    class DocumentAccessRight(model.Model):
        ...
    
        def get_children(self):
            all_children = []
            for first_child in self.first_children.all():
                all_children.append(first_child)
                all_children.extend(first_child.get_children())
            return all_children
    
        def get_parents(self):
            parents = []
            current_parent=self.parent
            while current_parent is not None:
                parents.append(current_parent)
                current_parent = current_parent.parent
            raise NotImplementedError
    

    Cette implémentation est la première à laquelle on pense. Elle a le mérite de fonctionner et d'être très faible en stockage (uniquement l'id du parent dans un enfant).

    Cependant, il y a un seul soucis : on ne stocke que les enfants directs ou le parent direct en base de données, et le lanqage SQL ne permet pas d'écrire des requêtes récursives.

    Ainsi, dans notre exemple entre Alice, Bob, Charly et Dylan, pour récupérer les parents de Dylan, il faudra exécuter quatre requêtes SQL (une pour chaque noeud). Bien sûr, ces requêtes sont automatiquement exécutées par l'ORM, mais imaginons un cas avec de nombreux destinataires (à l'échelle d'une entreprise par exemple), la solution n'est clairement pas viable.

    De même, pour récupérer les parents d'un utilisateur, il faudra autant de requête qu'il y a de parent.

    Approche vue ailleurs

    De façon plus intelligente, certains bibliothèques Django implémentent un modèle d'arbre. Pour cela, elles ajoutent un champ path représentant le chemin (un peu à la façon d'un fichier sur son filesystem) à partir des parents.

    Ainsi, les recherches de hiérarchie s'effectuent de la façon suivante :

    • La recherche des parents est triviale : c'est les éléments du chemin ;
    • La recherche des enfants est également simple : il suffit de rechercher tous les éléments donc le chemin contient son identifiant (l'élément au chemin /foo/bar/baz est forcément un enfant de /foo/ et de /bar/).

    On peut donc implémenter cette approche de la façon suivante:

    from django.db import models
    
    class DocumentAccessRight(model.Model):
        user = models.ForeignKey("SealdUser", on_delete=models.CASCADE)
        document = models.ForeignKey("Document", on_delete=models.CASCADE)
        parent = models.ForeignKey(
            "DocumentAccessRight",
            on_delete=models.CASCADE,
            related_name="first_children",
            null=True
        )
        path = models.TextField()
    
        def save(self, *args, **kwargs):
            # Automatiquement générer le path à partir du parent
            if self.path is None:
                self.path = "" if self.parent is None else self.parent.path
                self.path += f"/{self.user.id}"
            super().save(*args, **kwargs)
    
        def get_children(self):
            children_id = [
                documentaccessright.user_id
                for documentaccessright in DocumentAccessRight.models.filter(
                    parent__contains=f"/{self.user_id}/"
                )
            }
            return children_id
    
        def get_parents(self):
            parents_id = self.path.split("/")[1:-1]  # 0 is empty, last is self
            return parents_id
    

    Cette version donne exactement les mêmes fonctionnalités que la précédente mais l'avantage de fonctionner en une seule requête SQL, et sans besoin de fonctions récursives.

    Elle a cependant quelques défauts:

    • On stocke le path dans un champ de type Text, de taille indéfinie (impossible à indexer) ;
    • On fait des recherches de type contains qui se traduisent en SQL en LIKE '%foo%', ce qui est très peu performant ;
    • Si jamais on veut déplacer un élément dans l'arbre (par exemple dire que Charly devient le fils direct de Bob), il faut modifier le path tous les fils de l'élément déplacé.

    (Note: Concernant ce dernier point, cela ne nous concerne pas dans le use-case de Seald, il n'est donc pas traité dans cet article)

    Approche optimisée

    (NDLA: à partir de là, il s'agit de ma propre implémentation. Je ne sais pas s'il s'agit d'un pattern classique, ou s'il y a de très mauvaises retombés quelque part, si c'est le cas n'hésitez pas à m'en faire part en commentaire)

    L'approche à partir d'un path semble bonne. Cependant, en vue des inconvénients précédemment mentionnées, il est sûrement possible d'améliorer le modèle. Pour cela, il ne faut plus utiliser un TextField pour stocker le path, mais une structure plus appropriée.

    Pour reprendre l'exemple précédent, les path sont les suivants :

    • Alice : /Alice
    • Bob : /Alice/Bob
    • Charly : /Alice/Charly
    • Dylan : /Alice/Charly/Dylan

    PostgreSQL propose un type de champ propre (n'existant ni sur SqlLite / MySQL / MariaDB) : l'Arrays. Ce type de champ est également accessible via l'ORM de Django via l'ArrayField.

    Ainsi, le path pourrait être représenté par les tableaux suivants :

    • Alice : [Alice]
    • Bob : [Alice, Bob]
    • Charly : [Alice, Charly]
    • Dylan : [Alice, Charly, Dylan]

    Et ainsi, la recherche des enfants d'un élément ne se fait plus par un LIKE %foo%, mais par la vérification qu'un élément du path est présent. Mieux encore, pour trouver les enfants de Charly, il suffirait de vérifier tous les éléments dont Charly est présent dans le path, mais on peut encore optimiser la recherche, car on sait que si Charly est présent dans le path, il sera forcément en 2ème position, il n'est donc pas nécessaire de vérifier tout le path.

    Résultat

    L'implémentation de cette version peut se faire ainsi:

    from django.contrib.postgres.fields import ArrayField
    from django.db import models
    
    class DocumentAccessRight(model.Model):
        user = models.ForeignKey("SealdUser", on_delete=models.CASCADE)
        document = models.ForeignKey("Document", on_delete=models.CASCADE)
        parent = models.ForeignKey(
            "DocumentAccessRight",
            on_delete=models.CASCADE,
            null=True
        )
        path = ArrayField(models.IntegerField())  # A changer selon le type d'index
    
        def save(self, *args, **kwargs):
            # Automatiquement générer le path à partir du parent
            if self.path is None:
                self.path = [] if self.parent is None else self.parent.path
                self.path.append(self.user.id)
            super().save(*args, **kwargs)
    
        def get_children(self):
            query = {f"path__{len(self.path) - 1}": self.user_id}  # Ex: {"path__2": 12}
            children_id = [
                i
                for i in MessageAccess.objects.filter(**query).values("user")
            ]
            return children_id
    
        def get_parents(self):
            parents_id = self.path
            return parents_id
    

    Cette implementation reprend tous les avantages de la précédente, à la différence que la recherche des enfants d'un noeud se traduit par une comparaison d'égalité sur un élément indexable en base, améliorant considérablement les performances de la requête.

    Il reste quand même quelques notes négatives :

    • On utilise des tableaux pour stocker TOUT le path ; dans un contexte où un objet serait "profond" dans l'arbre, cela peut avoir un impact sur l'espace de stockage ;
    • Le déplacement d'un objet dans l'arboressence peut être très complexe et n'est pas du tout géré par l'implémentation.

    Cependant, ces deux points sont clairement assumés en vu du contexte de leur utilisation, ce qui n'est pas forcément le cas de tous les use cases.

  • Comments