Backends cohérents et UX: comment les nouveaux algorithmes aident-ils?


Dans des articles précédents, nous avons expliqué ce qu’est la cohérence, la différence entre une cohérence “forte” et “éventuelle”, et pourquoi cette distinction est plus importante que jamais pour les développeurs d’applications modernes. Nous avons également introduit la notion de «taxe de cohérence»: le temps et les efforts supplémentaires dont une équipe de développement a besoin pour investir si elle choisit un système avec seulement une cohérence éventuelle ou des garanties de cohérence limitées.

Plusieurs bases de données modernes utilisent des algorithmes de pointe pour éliminer le compromis entre cohérence et performances. Bien sûr, nous ne voudrions pas que vous preniez notre parole sans une explication appropriée. Par conséquent, dans cet article final, nous plongeons dans les détails techniques derrière certaines de ces bases de données. En règle générale, la seule source d’informations pour ces détails techniques sont les documents de recherche, donc le but de cet article est d’expliquer ces systèmes en termes plus simples. Parce que ces systèmes sont beaucoup plus complexes en réalité, nous fournirons les liens dans le texte au cas où vous voudriez en savoir plus et aimer lire des articles de recherche.

introduction

Dans les parties 1 et 2 de cette série d’articles, nous avons expliqué comment les bases de données distribuées utilisent différentes répliques pour répartir la charge et / ou servir les utilisateurs dans différentes régions. Pour résumer ici, pour les nouveaux lecteurs, une réplique n’est qu’une duplication de vos données. Et cette duplication peut vivre soit au même endroit pour la redondance, soit dans un autre emplacement pour offrir des latences plus faibles aux utilisateurs de ces emplacements. Avoir plusieurs répliques capables de gérer à la fois les lectures et les écritures présente un avantage considérable, car la base de données devient évolutive et peut offrir une latence plus faible à tous vos utilisateurs, où qu’ils se trouvent. Toutefois, vous ne souhaitez pas que chacune des répliques ait sa propre interprétation des données. Au lieu de petites différences de données entre chaque réplique, vous voulez une interprétation unique des données, qui est souvent appelée une seule source de vérité. Pour y parvenir, vous devez avoir une sorte d’accord sur les modifications des données. Nous avons besoin d’un consensus.

En attente d’un consensus

Chaque base de données distribuée qui vise à être cohérente possède plusieurs répliques qui doivent se mettre d’accord sur le résultat des transactions. Si des mises à jour de données conflictuelles se produisent, ces répliques doivent convenir de la mise à jour effectuée et de celle qui ne le sera pas. C’est ce qu’on appelle le «consensus».

Revenons à notre jeu pour illustrer pourquoi nous avons besoin d’un consensus. Imaginez que le joueur de notre jeu ne dispose que de 3 pièces d’or, mais essaie d’acheter simultanément deux articles différents dans deux magasins différents pour un budget total supérieur aux 3 pièces d’or restantes. Cela implique deux transactions, une pour chaque article / magasin, que nous appelons t1 et t2. Et supposons que les propriétaires des magasins se trouvent à travers le monde les uns des autres, de sorte que les transactions se déroulent sur deux répliques différentes. Si les deux transactions sont acceptées, l’utilisateur pourra acheter plus qu’il ne peut se le permettre. Comment empêcher l’utilisateur de dépenser trop?

Un exemple de deux répliques qui reçoivent chacune une transaction (t1) et (t2). Si nous laissons les deux passer, cela violerait notre règle commerciale selon laquelle les utilisateurs ne peuvent pas dépenser plus que ce qu’ils possèdent. Il est clair que ces répliques doivent décider quelle transaction est autorisée et laquelle doit être bloquée.

Nous savons que ces répliques doivent communiquer pour se mettre d’accord sur le résultat final des deux transactions. Ce que nous ne savons pas, c’est la quantité de communication dont ils ont besoin. Combien de messages doivent aller et venir entre la réplique 1 et la réplique 2 pour convenir de la transaction prioritaire et de celle annulée?

Étant donné que les répliques d’une base de données distribuée sont destinées à desservir des utilisateurs de différentes régions du monde avec une faible latence, elles sont très éloignées par nature. En rapprochant les doublons des données des utilisateurs finaux, ces utilisateurs peuvent lire avec des latences plus faibles. Cependant, lorsque les écritures se produisent, les répliques doivent s’envoyer des messages pour mettre à jour toutes les données dupliquées de manière uniforme – et ces messages peuvent prendre plusieurs dizaines de millisecondes car ils sont bridés par la vitesse de la lumière lorsqu’ils voyagent à travers le monde. Il est clair que nous devons limiter autant que possible le nombre de messages inter-centres de données afin que l’utilisateur final ne reste pas à attendre que ces répliques à travers le monde parviennent à un consensus.

Pendant longtemps, il avait été jugé impossible ou impossible de le faire. Mais aujourd’hui, plusieurs technologies existent pour maintenir le nombre d’aller-retour bas et ramener la latence dans les limites normales.

La distance entre New York et Paris est de 5 839 km. Pour que la lumière voyage de New York à Paris, puis retour, il faudrait 40 millisecondes.

Vitesse théorique vs vitesse réelle

S’il faut un minimum de 40 millisecondes pour voyager entre New York et Paris, un aller-retour prendrait au moins 80 ms. La question la plus importante qui reste est: “De combien d’aller-retour avons-nous besoin pour exécuter des transactions?” La réponse à cette question dépend largement des algorithmes utilisés.

Comment parvenir à un accord?

Il semble que pour parvenir à un consensus sur quelque chose, vous avez besoin d’au moins quatre sauts (ou deux tours de communication): un tour pour faire savoir à chaque réplique que vous êtes sur le point de faire quelque chose, puis un deuxième tour pour exécuter l’action une fois tout le monde convient que cette action peut être exécutée. C’est quelque chose appelé distribué validation en deux phases qui est utilisé par presque toutes les bases de données distribuées. Voyons une analogie. Imaginez que vous deviez convenir avec un groupe de personnes d’une bonne date pour une fête. Cela pourrait ressembler à ceci:

Tout d’abord, Polly demande à tout le monde s’ils peuvent se rendre à une fête lundi; elle sait maintenant que tout le monde pouvez en fait venir à la fête. Ensuite, elle doit faire savoir à tout le monde que la fête volonté en effet lundi, et les gens reconnaissent qu’ils seront là.

Celles-ci sont très similaires aux deux phases de validation en deux phases. Bien sûr, les bases de données ne font pas partie donc les phases ont des fonctions différentes. Dans le cas d’un système distribué, les phases sont appelées:

  • Préparez-vous ou demandez à vous engager: assurez-vous que tout le monde est au courant de la transaction. Au cours de cette phase, les répliques d’une base de données distribuée stockent la requête dans une sorte de liste de tâches (un journal des transactions) sur le disque pour s’assurer qu’elles savent toujours quoi faire si le serveur tombe en panne.
  • Commettre: calculer réellement les résultats et les stocker

Bien sûr, comme toujours, ce n’est jamais aussi simple. Il existe de nombreuses variantes de ces algorithmes. Par exemple, il existe des améliorations des validations en deux phases appelées Paxos et Radeau et même de nombreuses variantes de ceux-ci (multi paxos/paxos rapides/ …). Ces alternatives visent à améliorer les problèmes de disponibilité ou de performance. Pour comprendre les problèmes de disponibilité, imaginez simplement que Polly tombe malade ou que le téléphone d’Amber meurt. Dans le premier cas, elle ne pourrait pas continuer son travail de coordinatrice du parti et dans le second cas, il serait temporairement impossible pour Polly de savoir si Amber est d’accord sur la date du parti. Raft et Paxos améliorent cela en exigeant seulement la majorité de répondre et / ou de sélectionner automatiquement un nouveau coordinateur lorsque le leader ou le coordinateur tombe en panne. Une bonne animation qui montre comment fonctionne Raft peut être trouvée ici.

D’accord sur quoi?

Pouvons-nous conclure que chaque base de données distribuée nécessite alors 2 allers-retours pour écrire / lire des données? Non, la réalité est plus complexe que cela. D’un côté, il existe de nombreuses optimisations possibles et de l’autre, il peut y avoir plusieurs points sur lesquels nous devons nous mettre d’accord.

  • Se mettre d’accord sur l’heure d’une transaction
  • Convenir si les lectures peuvent être exécutées
  • Convenir si les lectures peuvent être exécutées

L’exemple le plus simple qui comporte plusieurs cycles de validation en deux phases est probablement les transactions légères de Cassandra. Ils nécessitent d’abord des accords consensuels sur les lectures, puis un consensus sur les écritures. Si chaque message met 40 ms à voyager, cela signifie que la transaction entière nécessite 320 ms ou plus – en fonction des “verrous” requis, comme nous l’expliquerons plus loin.

C’est assez facile à comprendre, mais il y a quelques problèmes avec la mise en œuvre puisque Cassandra n’a jamais été conçue pour être fortement cohérente. Cela signifie-t-il que les bases de données fortement cohérentes sont encore plus lentes? Pas du tout! Les bases de données distribuées modernes utilisent un mélange de fonctionnalités intéressantes pour obtenir de meilleures performances.

En attente de verrous

Non seulement nous devons attendre que les messages parviennent à un accord, mais presque toutes les bases de données distribuées utiliseront également des «verrous». Les verrous garantissent que les données sur le point d’être modifiées par une transaction ne sont pas modifiées simultanément par une autre transaction. Lorsque les données sont verrouillées, elles ne peuvent pas être modifiées par d’autres transactions, ce qui signifie que ces transactions doivent attendre. La durée d’un tel verrou a donc un impact important sur les performances. Encore une fois, cet impact sur les performances dépend de l’algorithme et des optimisations qui ont été implémentés par la base de données. Certaines bases de données détiennent des verrous plus longtemps que d’autres et certaines bases de données n’utilisent pas du tout de verrous.

Maintenant que nous connaissons suffisamment les bases, plongons-nous dans les algorithmes.

Algorithmes modernes pour le consensus

Nous savons maintenant que le consensus et les verrous sont les principaux goulots d’étranglement que nous devons optimiser. Revenons donc à la question principale de cet article: “Comment les nouvelles technologies réduisent-elles ces latences dans des limites acceptables?” Commençons par le premier de ces algorithmes modernes, qui ont suscité des idées intéressantes pour le reste du monde des bases de données.

2010 – Percolateur

Percolateur est un système interne construit sur Grande table (l’une des premières bases de données NoSQL construites par Google) que Google utilisait pour effectuer des mises à jour incrémentielles de la vitesse d’exploration de la page de leur index de recherche. La première papier on Percolator est sorti en 2010, inspirant la première base de données distribuée qui s’en est inspirée: FoundationDB en 2013. FoundationDB a ensuite été acquise par Apple pour enfin sortir une version stable en 2019, avec la sortie d’un FoundationDB papier.

Bien que Percolator ait permis à Google d’accélérer considérablement l’exploration des pages, il n’a pas été initialement conçu comme une base de données à usage général. Il était plutôt destiné à être un moteur de traitement incrémentiel rapide et évolutif pour prendre en charge l’index de recherche de Google. Comme l’index de recherche devait être évolutif, de nombreux calculs devaient être effectués simultanément sur de nombreuses machines, ce qui nécessitait une base de données distribuée. Comme nous l’avons appris dans les articles précédents, la programmation contre des systèmes distribués qui stockent des données peut être très complexe et exigeait traditionnellement que les développeurs paient une “ taxe de cohérence ” pour programmer un comportement imprévisible des bases de données. Pour éviter de payer une taxe de cohérence aussi élevée, Google a adopté un modèle de cohérence solide lors de la création de Percolator.

Le modèle de cohérence de Percolator ne pourrait exister sans deux ingrédients clés: le contrôle de version et Oracle Timestamp

Ingrédient 1: Versioning

Comme nous l’avons mentionné dans les articles précédents, une forte cohérence nous oblige à convenir d’un ordre global pour nos transactions. La gestion des versions est l’un des éléments qui sera crucial pour bon nombre de ces algorithmes, car il peut être utilisé pour la récupération après défaillance, pour aider à répliquer les données et pour prendre en charge un modèle de cohérence appelé «isolement de capture instantanée».

La gestion des versions aide à la récupération après échec lorsqu’un nœud tombe en panne ou se déconnecte. Lorsque le nœud revient en ligne, grâce aux versions, il peut facilement restaurer son état en commençant par le dernier instantané qu’il a pu enregistrer, puis en relisant les transactions en fonction des versions d’un autre nœud. Tout ce qu’il a à faire est de demander à un autre nœud: “Hé, qu’est-ce qui a changé depuis que je suis parti?” Sans versioning, il faudrait recopier tout les données, ce qui aurait mis à rude épreuve le système.

La récupération après échec est excellente, mais l’avantage le plus important réside dans le fait qu’un tel système de gestion des versions peut être utilisé pour implémenter un modèle de cohérence solide. Si le système de gestion des versions conserve les versions pour chaque modification de données, nous pouvons en fait remonter dans le temps et effectuer des requêtes sur une version antérieure de nos données.

Certains esprits brillants ont découvert que cette capacité d’interrogation historique pouvait être utilisée pour fournir un modèle de cohérence appelé «cohérence des instantanés». L’idée de la cohérence de l’instantané est de choisir une version des données au début de la requête, de travailler avec cette version des données pendant le reste de la requête, puis d’écrire une nouvelle version à la fin de la requête.

Il y a un écueil possible ici: lors de l’exécution d’une telle requête, une autre requête pourrait être l’écriture de données en conflit avec la première requête. Par exemple, si deux requêtes d’écriture commencent par le même instantané d’un compte bancaire avec 1 000 $, elles pourraient toutes deux dépenser l’argent car elles ne voient pas les écritures de l’autre requête. Pour éviter cela, une transaction supplémentaire aura lieu pour voir si les valeurs de l’instantané ont changé avant que l’une des requêtes n’écrive un résultat. Si un conflit est survenu pour modifier la valeur de l’instantané, la transaction est annulée et doit être redémarrée.

Cependant, il reste un problème que Percolator doit résoudre. Les horloges de différentes machines peuvent facilement s’écarter de quelques centaines de millisecondes. Si les données d’une requête sont réparties sur plusieurs machines, comme dans notre exemple initial, vous ne pouvez pas simplement demander aux deux machines de vous fournir des données à un certain horodatage, car elles ont une idée légèrement différente de l’heure actuelle. C’est une question de millisecondes, mais lorsque de nombreuses transactions doivent être traitées, quelques millisecondes suffisent pour passer de données correctes à des données erronées.

La synchronisation de l’heure nous amène au deuxième ingrédient Percolator.

Ingrédient 2: l’Oracle d’horodatage

La solution de Percolator au problème de synchronisation de l’heure est appelée l’horodatage Oracle. Au lieu de laisser chaque nœud dicter son propre temps (qui n’était pas assez précis), Percolator utilise un système central qui expose une API vous fournissant un horodatage. Le nœud sur lequel ce système réside est l’Oracle d’horodatage. Lorsque nous conservons plusieurs versions de nos données, nous avons besoin d’au moins deux horodatages pour chaque requête. Tout d’abord, nous avons besoin d’un horodatage pour interroger un instantané, que nous utiliserons pour lire les données. Ensuite, à la fin de la transaction lorsque nous sommes prêts à écrire, nous avons besoin d’un deuxième horodatage pour baliser la nouvelle version des données. Par conséquent, Percolator présente l’inconvénient d’avoir besoin d’au moins deux appels vers l’horodatage Oracle, ce qui introduit encore plus de latence si l’oracle se trouve dans une autre région des nœuds d’où proviennent les appels. Lorsque Google a proposé sa clé de répartition de base de données, ils ont résolu ce problème.

2012 – Clé

Spanner a été la première base de données distribuée à l’échelle mondiale à offrir une forte cohérence, ce qui signifie essentiellement que vous obtenez des lectures à faible latence sans avoir à vous soucier des erreurs de base de données potentielles. Les développeurs n’ont plus besoin d’investir de travail supplémentaire pour contourner les bogues potentiels causés par une cohérence éventuelle. Le document a été publié en 2012 et il a été rendu public en 2017 sous le nom de Spanner Cloud.

Ingrédient 1: Versioning

Google a créé Spanner après leur expérience avec Percolator. Étant donné que le système de versioning de Percolator s’est avéré efficace, ils l’ont conservé dans la conception de Spanner. Ce système de gestion des versions offrait la possibilité d’effectuer des lectures très rapides (lectures instantanées) si vous vouliez renoncer à la cohérence. Dans ce cas, vous pouvez exécuter des requêtes et donner à Spanner un âge maximal pour les résultats. Par exemple: «Veuillez retourner mon inventaire actuel le plus rapidement possible, mais les données ne peuvent avoir que 15 secondes». Fondamentalement, au lieu d’abandonner la cohérence, vous pouvez désormais choisir pour chaque requête le niveau de cohérence adapté à votre cas d’utilisation.

Ingrédient 2: TrueTime

Pour éliminer les frais supplémentaires pour synchroniser le temps entre les machines, Spanner a abandonné l’horodatage Oracle au profit d’un nouveau concept appelé TrueTime. Au lieu d’avoir un système central qui offre une vue unifiée du temps, TrueTime essaie de réduire la dérive d’horloge entre les machines elles-mêmes. Les ingénieurs de Google ont réussi à limiter la dérive de l’horloge locale en mettant en œuvre un protocole de synchronisation de l’heure basé sur le GPS et les horloges atomiques. Cet algorithme de synchronisation leur a permis de limiter la dérive de l’horloge dans une limite de 7 ms, mais a nécessité un matériel spécifique composé d’une combinaison de la technologie d’horloge atomique et GPS.

Bien sûr, il y a toujours une dérive d’horloge potentielle de 7 ms, ce qui signifie que deux serveurs pourraient toujours interpréter un horodatage comme deux instantanés différents. Ceci est résolu par le troisième ingrédient de Spanner: commit-wait.

Ingrédient 3: Commit-wait

En fait, l’API TrueTime ne renvoie pas un horodatage mais renvoie et un intervalle n dont il est sûr que l’horodatage actuel doit se trouver. Une fois prêt à s’engager, il n’attendra que quelques millisecondes pour faire face à la dérive potentielle appelée «Commit-wait». Cela garantit que l’horodatage qui sera affecté à l’écriture est un horodatage qui est passé sur tous les nœuds. C’est également la raison pour laquelle l’exécution de Spanner sur du matériel standard ne peut pas offrir la même garantie, car la période d’attente devrait être de quelques centaines de millisecondes.

2012 – Calvin

La première papier sur l’algorithme de Calvin a été publié en 2012, à partir de recherches à Yale. Tout comme les approches précédentes, Calvin se compose de plusieurs ingrédients. Bien que le versioning en fasse également partie, le reste de l’approche est radicalement différent, ce qui nécessite quelques ingrédients supplémentaires pour fonctionner: les calculs déterministes et la séparation de la commande du verrouillage. Ce sont des ingrédients que l’on ne trouve généralement pas dans les bases de données à architecture traditionnelle. En modifiant l’architecture et en acceptant que les requêtes doivent être déterministes, Calvin peut réduire le nombre le plus défavorable de messages entre centres de données à deux. Cela réduit considérablement la latence du pire des transactions mondiales et la ramène en dessous de 200 ms ou théoriquement même en dessous de 100 ms. Bien sûr, pour croire que cela est possible, vous voudrez peut-être d’abord savoir comment cela fonctionne, alors examinons l’algorithme.

Ingrédient 1: Versioning

Semblable à Percolator et Spanner, Calvin s’appuie sur des données versionnées. Ces instantanés à Calvin sont principalement utilisés pour garantir la tolérance aux pannes. Chaque nœud stocke différents instantanés qui peuvent être considérés comme des points de contrôle. Un nœud déconnecté qui revient en ligne n’a besoin que de saisir l’horodatage du dernier point de contrôle dont il a été témoin, puis de demander à un autre nœud de l’informer de toutes les transactions intervenues après ce point de contrôle.

Ingrédient 2: calculs déterministes

De nombreux développeurs front-end auront entendu parler de la Orme cadre frontal qui met en œuvre un React Reduxcomme un flux de travail. Elm a une courbe d’apprentissage plus abrupte que les cadres basés sur JavaScript similaires car il vous oblige à apprendre un nouveau langage. Cependant, comme la langue est fonctionnel (pas d’effets secondaires), Elm permet des optimisations impressionnantes. La clé est que les fonctions dans Elm abandonnent les manipulations destructrices pour être déterministes. Vous pouvez exécuter deux fois la même fonction avec la même entrée et cela donnera toujours le même résultat. Parce qu’elles sont déterministes, les requêtes Elm peuvent désormais décider plus efficacement comment mettre à jour les vues.

Semblable à Elm, Calvin a renoncé à quelque chose pour accélérer les calculs. Dans le cas de Calvin, nous pouvons essentiellement dire que le résultat d’une transaction sera le même, qu’elle soit exécutée sur la machine A ou la machine B. Cela peut sembler évident, mais les bases de données ne le garantissent généralement pas. N’oubliez pas que SQL vous permet d’utiliser l’heure actuelle ou autorise ce que l’on appelle des transactions interactives dans lesquelles une entrée utilisateur peut être insérée au milieu d’une transaction, les deux pouvant violer les garanties fournies par Calvin.

Pour réaliser des calculs déterministes, Calvin (1) doit effectuer des calculs tels que l’heure actuelle et les pré-calculer, et (2) ne permet pas les transactions interactives. Les transactions interactives sont des transactions où un utilisateur démarre une transaction, lit certaines données, fournit des entrées utilisateur supplémentaires au milieu, puis effectue enfin des calculs supplémentaires et éventuellement des écritures. Étant donné que l’utilisateur n’est pas prévisible, une telle transaction n’est pas déterministe. En substance, Calvin négocie une commodité mineure (transactions interactives) pour de grandes performances.

Ingrédient 3: Séparez le problème de la commande.

Les bases de données passent beaucoup de temps à négocier des verrous afin de donner l’impression que le système s’exécute dans un ordre spécifique ». Si une commande est tout ce dont vous avez besoin, nous pouvons peut-être séparer le problème de verrouillage du problème de commande. Cela signifie cependant que vos transactions doivent être pures.

– Kyle Kingsbury

Séparer le souci d’ordonner des transactions de l’exécution réelle a été considéré à plusieurs reprises dans le monde des bases de données, mais sans grand succès. Cependant, lorsque vos transactions sont déterministes, il est possible de séparer la commande des calculs. En fait, la combinaison de calculs déterministes et la séparation des commandes du reste de l’algorithme est extrêmement puissante car elle contribue à réduire la durée du verrouillage et diminue considérablement la communication plus lente entre les nœuds distants (communication entre centres de données).

Durée de verrouillage plus courte

Chaque fois que des verrous sont maintenus sur une donnée, cela signifie que les autres requêtes qui utilisent ces données doivent attendre. Par conséquent, un verrouillage plus court entraîne de meilleures performances. Ci-dessous est une image qui montre un aperçu de la procédure de verrouillage dans Calvin par rapport à la façon dont une base de données distribuée traditionnelle pourrait le faire. La plupart des bases de données garderaient un verrou sur les données jusqu’à ce qu’il y ait au moins un consensus sur ce qu’il faut écrire tandis que Calvin ne garderait le verrou que jusqu’à ce que tous les nœuds soient d’accord sur l’ordre. Parce que les calculs sont déterministes et qu’ils ont tous convenu de la commande, chaque nœud calculera séparément et arrivera au même résultat final.

Moins de communication entre les nœuds distants

Outre les avantages de la durée de verrouillage, la séparation de la commande du reste de l’algorithme nécessite également moins de communication. Comme expliqué précédemment avec l’exemple Cassandra, une base de données distribuée nécessite généralement une communication entre centres de données dans de nombreuses phases de leur algorithme. Dans le cas de Calvin, le seul moment où nous devons nous mettre d’accord sur quelque chose est au moment où nous déterminons la commande. Avec le protocole Raft, cela pourrait être fait en deux sauts, ce qui permet d’obtenir des latences inférieures à 100 ms pour les requêtes en lecture-écriture.

Associé au temps de verrouillage réduit, cela permet également un débit exceptionnel. Le Calvin d’origine papier a également fait des expériences qui montrent que cette approche surpasse de manière significative les conceptions de bases de données distribuées traditionnelles sous des charges de travail très conflictuelles. Leurs résultats d’un demi-million de transactions par seconde sur un groupe de machines de base sont compétitifs par rapport aux résultats du record mondial actuel obtenus sur du matériel beaucoup plus haut de gamme.

Fonctionne sur n’importe quel matériel

En plus de cela, Calvin a un autre avantage: il ne nécessite plus matériel spécifique afin d’obtenir de tels résultats. Étant donné que Calvin peut fonctionner sur des machines standard, il peut fonctionner sur n’importe quel fournisseur de cloud.

2014 – Le FaunaDB saveur du consensus

Ingrédient 1: Versioning

FaunaDB a son propre protocole de transaction distribué avec quelques similitudes avec Calvin. Tout comme les anciennes approches, les données de FaunaDB sont également versionnées. Étant donné que la gestion des versions est non seulement utile pour le modèle de cohérence, mais peut également avoir une valeur commerciale, FaunaDB a mis à niveau ce mécanisme en un citoyen de première classe qui peut être utilisé par les utilisateurs finaux. Cette fonctionnalité permet essentiellement des requêtes dans le temps. Les utilisateurs finaux peuvent exécuter une requête sur les données historiques pour répondre à des questions telles que: “Quel aurait été le résultat de cette requête il y a 20 jours?”. Ceci est utile pour récupérer des données qui ont été accidentellement écrasées, auditer les modifications de données ou simplement incorporer le voyage dans le temps dans les fonctionnalités de votre application.

Ingrédient 2 et 3: calculs déterministes et séparation

Comme Calvin, FaunaDB a également des calculs déterministes et sépare le problème de la commande du reste de l’algorithme. Bien qu’il existe des similitudes, le calcul des transactions dans FaunaDB se produit dans une phase différente de Calvin. Lorsque Calvin profite de la nature déterministe pour exécuter la même transaction plusieurs fois une fois que l’ordre est défini, FaunaDB ne calculera qu’une seule fois avant de parvenir à un consensus sur l’ordre des transactions. Ce qui nous amène au quatrième ingrédient.

Ingrédient 4: calcul optimiste

FaunaDB ajoute un quatrième ingrédient que nous avons déjà vu lorsque nous avons parlé de l’isolement de l’instantané: Calculs optimistes au lieu de verrouiller.

FaunaDB ne se verrouillera pas, mais calculera à la place de manière optimiste le résultat de la transaction une fois que dans le nœud où la transaction a été reçue, puis ajoutez le résultat et les valeurs d’entrée d’origine au journal. Là où Calvin aurait enregistré la requête qui doit être exécutée dans le journal des transactions, FaunaDB enregistrera à la fois le résultat du calcul et les valeurs d’entrée d’origine dans le journal. Une fois qu’il y aura consensus sur l’ordre dans lequel les résultats doivent être appliqués, FaunaDB vérifiera si les données d’entrée pour ce calcul ont changé ou non (grâce au versioning). Si les valeurs d’entrée ont changé, la transaction est abandonnée et redémarrée, si elles sont restées les mêmes, les résultats sont appliqués sur tous les nœuds sans aucun calcul supplémentaire.

L’algorithme de FaunaDB présente des avantages similaires à Calvin, mais réduit la quantité de calculs requis dans le cluster.

Conclusion

Dans cette série, nous avons expliqué comment une cohérence élevée peut vous aider à créer des applications sans erreur plus efficacement. Dans ce dernier article, nous avons expliqué comment les idées révolutionnaires peuvent alimenter une nouvelle génération de bases de données distribuées à la fois cohérentes et performantes. Le point à retenir dans les articles précédents était: «La cohérence est importante». Dans cet article final, les plats à emporter sont englobés dans ce qui suit:

Dans un avenir proche, si vous lisez une phrase telle que:

«De nombreuses bases de données NoSQL n’offrent pas d’écritures atomiques pour plusieurs documents et offrent en retour de meilleures performances. Et bien que la cohérence soit une autre grande caractéristique des bases de données SQL, elle empêche la possibilité de faire évoluer une base de données sur plusieurs nœuds, de nombreuses bases de données NoSQL abandonnent la cohérence. » – les plus grands défis du passage à NoSQL

Réalisez que les algorithmes modernes permettent aux bases de données de fournir une cohérence sans centralisation. Dans cet article, nous avons vu quelques exemples d’algorithmes et de bases de données qui le font. Les bases de données qui s’appuient sur ces algorithmes sont une nouvelle génération de bases de données qui ne peuvent plus être décrites par des catégories simples telles que NoSQL, SQL ou même NewSQL.

Avec des bases de données cloud distribuées basées sur Percolator, Spanner, Calvin et le protocole de transaction de FaunaDB, vous pouvez disposer de bases de données distribuées hautement performantes qui offrent des modèles de cohérence plus solides. Cela signifie que vous pouvez créer des applications gourmandes en données qui offrent une faible latence sans avoir à vous soucier des erreurs de données, des performances ou du provisionnement des services. Dans de tels systèmes, la cohérence est transparente et vous n’avez pas à y penser en tant que développeur. La prochaine fois que vous choisissez une base de données, choisissez-en une qui soit cohérente par défaut.

Close Menu