Quand utiliser une base de données CRDT

Roshan Kumar est chef de produit senior chez Redis Labs.

Contrer la cohérence et la disponibilité telles que décrites par le théorème CAP a été un grand défi pour les architectes d'applications géo-distribuées. La partition réseau est inévitable. La latence élevée entre les centres de données entraîne toujours une certaine déconnexion entre les centres de données pendant une courte période. Ainsi, les architectures traditionnelles pour les applications géo-distribuées sont conçues soit pour renoncer à la cohérence des données, soit pour nuire à la disponibilité.

Malheureusement, vous ne pouvez pas vous permettre de sacrifier la disponibilité des applications utilisateur interactives. Ces derniers temps, les architectes ont pris une photo de cohérence et ont adopté le modèle de cohérence éventuelle. Dans ce modèle, les applications dépendent du système de gestion de base de données pour fusionner toutes les copies locales des données pour les rendre finalement cohérentes.

Tout semble bon avec le modèle de cohérence éventuel jusqu'à ce qu'il y ait des conflits de données. Quelques modèles de cohérence éventuels promettent de meilleurs efforts pour résoudre les conflits, mais ne garantissent pas une cohérence forte. La bonne nouvelle est que les modèles construits autour de types de données répliquées sans conflit (CRDT) offrent une forte cohérence à terme.

Les CRDT atteignent une forte cohérence à terme grâce à un ensemble prédéterminé de règles et de sémantiques de résolution des conflits. Les applications construites sur des bases de données CRDT doivent être conçues pour prendre en charge la sémantique de résolution des conflits. Dans cet article, nous allons explorer comment concevoir, développer et tester des applications géo-distribuées à l'aide d'une base de données CRDT. Nous examinerons également quatre exemples de cas d'utilisation: compteurs, mise en cache distribuée, sessions partagées et ingestion de données multirégionales.

Mon employeur, Redis Labs, a récemment annoncé la prise en charge de CRDT dans Redis Enterprise, avec des types de données répliquées sans conflit rejoignant le riche portefeuille de structures de données: chaînes, hachages, listes, ensembles, ensembles triés, Bitfields, Geo, Hyperloglog et Streams. notre produit de base de données. Cependant, la discussion suivante s'applique non seulement à Redis Enterprise, mais à toutes les bases de données CRDT.

Bases de données pour applications géo-distribuées

Pour les applications géo-distribuées, il est courant d'exécuter des services en local pour les clients. Cela réduit le trafic réseau et la latence provoquée par l'aller-retour. Dans de nombreux cas, les architectes conçoivent les services pour se connecter à une base de données locale. Vient ensuite la question de savoir comment maintenir des données cohérentes dans toutes les bases de données. Une option consiste à gérer cela au niveau de l'application. Vous pouvez écrire un processus de travail périodique qui synchronisera toutes les bases de données. Ou vous pouvez compter sur une base de données qui synchronisera les données entre les bases de données.

Pour le reste de l'article, nous supposons que vous opterez pour la deuxième option: laissez la base de données faire le travail. Comme le montre la figure 1 ci-dessous, votre application géo-distribuée exécute des services dans plusieurs régions, chaque service se connectant à une base de données locale. Le système de gestion de base de données sous-jacent synchronise les données entre les bases de données déployées dans les régions.

Redis Labs

Modèles de cohérence des données

Un modèle de cohérence est un contrat entre la base de données distribuée et l'application qui définit le degré de propreté des données entre les opérations d'écriture et de lecture.

Par exemple, dans un modèle de cohérence forte, la base de données garantit que les applications liront toujours la dernière écriture. Avec une cohérence séquentielle, la base de données garantit que l'ordre des données que vous lisez est cohérent avec l'ordre dans lequel elles ont été écrites dans la base de données. Dans l'éventuel modèle de cohérence, la base de données distribuée promet de synchroniser et de consolider les données entre les répliques de base de données en arrière-plan. Par conséquent, si vous écrivez vos données dans un réplica de base de données et que vous les lisez à partir d'un autre, il est possible que vous ne lisiez pas la dernière copie des données.

Forte cohérence

La validation en deux phases est une technique courante pour atteindre une forte cohérence. Ici, pour chaque opération d'écriture (ajout, mise à jour, suppression) sur un nœud de base de données local, le nœud de base de données propage les modifications à tous les nœuds de base de données et attend que tous les nœuds acquittent. Le nœud local envoie alors un commit à tous les nœuds et attend un autre accusé de réception. L'application ne pourra lire les données qu'après le deuxième commit. La base de données distribuée ne sera pas disponible pour les opérations d'écriture lorsque le réseau se déconnecte entre les bases de données.

Cohérence éventuelle

Le principal avantage de l'éventuel modèle de cohérence est que la base de données sera à votre disposition pour effectuer des opérations d'écriture même lorsque la connectivité réseau entre les répliques de base de données distribuées tombe en panne. En général, ce modèle évite le temps d'aller-retour engendré par une validation en deux phases, et prend donc en charge beaucoup plus d'opérations d'écriture par seconde que les autres modèles. Un problème que la cohérence éventuelle doit résoudre est celui des conflits - écritures simultanées sur le même élément à deux emplacements différents. En fonction de la manière dont elles évitent ou résolvent les conflits, les bases de données éventuellement cohérentes sont classées dans les catégories suivantes:

  1. Le dernier écrivain gagne (LWW).  Dans cette stratégie, les bases de données distribuées reposent sur la synchronisation d'horodatage entre les serveurs. Les bases de données échangent l'horodatage de chaque opération d'écriture avec les données elles-mêmes. En cas de conflit, l'opération d'écriture avec le dernier horodatage l'emporte.

    L'inconvénient de cette technique est qu'elle suppose que toutes les horloges du système sont synchronisées. En pratique, il est difficile et coûteux de synchroniser toutes les horloges du système.

  2. Cohérence éventuelle basée sur le quorum: cette technique est similaire à la validation en deux phases. Cependant, la base de données locale n'attend pas l'accusé de réception de toutes les bases de données; il attend juste l'accusé de réception de la majorité des bases de données. La reconnaissance de la majorité établit un quorum. En cas de conflit, l'opération d'écriture qui a établi le quorum l'emporte.

    D'un autre côté, cette technique ajoute une latence du réseau aux opérations d'écriture, ce qui rend l'application moins évolutive. En outre, la base de données locale ne sera pas disponible pour les écritures si elle est isolée des autres répliques de base de données de la topologie.

  3. Réplication de fusion: dans cette approche traditionnelle, courante parmi les bases de données relationnelles, un agent de fusion centralisé fusionne toutes les données. Cette méthode offre également une certaine flexibilité dans la mise en œuvre de vos propres règles de résolution des conflits.

    La réplication de fusion est trop lente pour prendre en charge des applications engageantes en temps réel. Il a également un point de défaillance unique. Comme cette méthode ne prend pas en charge les règles prédéfinies pour la résolution des conflits, elle conduit souvent à des implémentations boguées pour la résolution des conflits.

  4. Type de données répliquées sans conflit (CRDT): vous en apprendrez plus sur les CRDT dans les prochaines sections. En un mot, les bases de données CRDT prennent en charge les types de données et les opérations qui offrent une cohérence éventuelle sans conflit. Les bases de données CRDT sont disponibles même lorsque les répliques de base de données distribuées ne peuvent pas échanger les données. Ils fournissent toujours une latence locale aux opérations de lecture et d'écriture.

    Limites? Tous les cas d'utilisation de bases de données ne bénéficient pas des CRDT. En outre, la sémantique de résolution des conflits pour les bases de données CRDT est prédéfinie et ne peut pas être remplacée.

Que sont les CRDT?

Les CRDT sont des types de données spéciaux qui font converger les données de toutes les répliques de base de données. Les CRDT populaires sont les compteurs G (compteurs de croissance uniquement), les compteurs PN (compteurs positifs-négatifs), les registres, les ensembles G (ensembles de croissance uniquement), les ensembles 2P (ensembles à deux phases), les ensembles OR ( Observer-supprimer des ensembles), etc. En coulisse, ils s'appuient sur les propriétés mathématiques suivantes pour faire converger les données:

  1. Propriété commutative: a ☆ b = b ☆ a
  2. Propriété associative: a ☆ (b ☆ c) = (a ☆ b) ☆ c
  3. Idempotence:  a ☆ a = a

Un compteur G est un parfait exemple de CRDT opérationnel qui fusionne les opérations. Ici, a + b = b + a et a + (b + c) = (a + b) + c. Les répliques échangent uniquement les mises à jour (ajouts) entre elles. Le CRDT fusionnera les mises à jour en les additionnant. Un G-set, par exemple, applique l'idempotence ({a, b, c} U {c} = {a, b, c}) pour fusionner tous les éléments. L'idempotence évite la duplication des éléments ajoutés à une structure de données lorsqu'ils voyagent et convergent via des chemins différents.

Types de données CRDT et leur sémantique de résolution des conflits

Structures de données sans conflit: compteurs G, compteurs PN, jeux G

Toutes ces structures de données sont conçues sans conflit. Les tableaux ci-dessous montrent comment les données sont synchronisées entre les répliques de base de données.

Redis Labs Redis Labs

Les compteurs G et PN sont populaires pour des cas d'utilisation tels que l'interrogation globale, le nombre de flux, le suivi d'activité, etc. Les G-sets sont largement utilisés pour implémenter la technologie blockchain. Les bitcoins, par exemple, utilisent des entrées de blockchain ajoutées uniquement.

Registres: chaînes, hachages

Les registres ne sont pas sans conflit par nature. Ils suivent généralement les politiques de LWW ou de résolution des conflits basée sur le quorum. La figure 4 montre un exemple de la façon dont un registre résout le conflit en suivant la politique LWW.

Redis Labs

Les registres sont principalement utilisés pour stocker les données de mise en cache et de session, les informations de profil utilisateur, le catalogue de produits, etc.

Ensembles 2P

Les ensembles à deux phases conservent deux ensembles de G-sets: l'un pour les éléments ajoutés et l'autre pour les éléments supprimés. Les répliques échangent les ajouts de G-set lorsqu'ils se synchronisent. Un conflit survient lorsque le même élément est trouvé dans les deux ensembles. Dans certaines bases de données CRDT telles que Redis Enterprise, cela est géré par la stratégie «Ajouter l'emporte sur la suppression».

Redis Labs

L'ensemble 2P est une bonne structure de données pour stocker des données de session partagées telles que des paniers d'achat, un document partagé ou une feuille de calcul.

Comment concevoir une application pour utiliser une base de données CRDT

La connexion de votre application à une base de données CRDT n'est pas différente de la connexion de votre application à une autre base de données. Cependant, en raison des éventuelles stratégies de cohérence, votre application doit suivre un certain ensemble de règles pour offrir une expérience utilisateur cohérente. Trois clés: 

  1. Rendez votre application sans état. Une application sans état est généralement pilotée par API. Chaque appel à une API entraîne la reconstruction du message complet à partir de zéro. Cela garantit que vous tirez toujours une copie propre des données à tout moment. La faible latence locale offerte par une base de données CRDT rend la reconstruction des messages plus rapide et plus facile. 

  2. Sélectionnez le bon CRDT qui correspond à votre cas d'utilisation. Le compteur est le plus simple des CRDT. Il peut être appliqué pour des cas d'utilisation tels que le vote global, le suivi des sessions actives, le comptage, etc. Cependant, si vous souhaitez fusionner l'état des objets distribués, vous devez également prendre en compte d'autres structures de données. Par exemple, pour une application qui permet aux utilisateurs de modifier un document partagé, vous souhaiterez peut-être conserver non seulement les modifications, mais également l'ordre dans lequel elles ont été effectuées. Dans ce cas, enregistrer les modifications dans une liste basée sur CRDT ou une structure de données de file d'attente serait une meilleure solution que de les stocker dans un registre. Il est également important que vous compreniez la sémantique de résolution des conflits appliquée par les CRDT et que votre solution soit conforme aux règles.
  3. CRDT n'est pas une solution universelle. Bien que CRDT soit en effet un excellent outil pour de nombreux cas d'utilisation, il peut ne pas être le meilleur pour tous les cas d'utilisation (transactions ACID, par exemple). Les bases de données CRDT s'adaptent généralement bien à l'architecture de microservices où vous disposez d'une base de données dédiée pour chaque microservice.

Le principal avantage ici est que votre application doit se concentrer sur la logique et déléguer la gestion des données et la complexité de la synchronisation à la base de données sous-jacente.

Tester des applications avec une base de données multi-maître distribuée

Pour accélérer la mise sur le marché, nous vous recommandons de disposer d'une configuration de développement, de test, de préparation et de production cohérente. Entre autres choses, cela signifie que votre configuration de développement et de test doit avoir un modèle miniaturisé de votre base de données distribuée. Vérifiez si votre base de données CRDT est disponible en tant que conteneur Docker ou appareil virtuel. Déployez vos réplicas de base de données sur différents sous-réseaux afin de pouvoir simuler la configuration de cluster connecté et déconnecté.

Tester des applications avec une base de données multimaître distribuée peut sembler complexe. Mais la plupart du temps, vous ne testerez que la cohérence des données et la disponibilité des applications dans deux situations: lorsque les bases de données distribuées sont connectées et lorsqu'il y a une partition réseau entre les bases de données.

En configurant une base de données distribuée à trois nœuds dans votre environnement de développement, vous pouvez couvrir (et même automatiser) la plupart des scénarios de test dans les tests unitaires. Voici les instructions de base pour tester vos applications: