Types de données répliquées sans conflit (CRDT) vs Paxos ou Raft

Je pense que ce gars sait de quoi il parle:

Blog

Vidéo -

Conclusion sur les systèmes distribués

Les CRDT et les Paxo ont des objectifs différents et sont utilisés selon différents scénarios. Ils ont en commun d'aider les programmeurs à gérer la concurrence / réplication. Les CRDT sont des types de données que des mises à jour simultanées asume auront lieu. Paxos est un protocole qui applique qu'ils ne le feront pas, en appliquant un ordre total sur eux. Nous allons voir cela plus en détail.

Disons que nous avons un ensemble répliqué qui est répliqué à deux endroits différents.

L'utilisation de Paxos garantit que les Écritures l'ensemble sera exécuté par chaque réplique dans le même ordre. Plus généralement, Il garantit que toutes les répliques S'accordent sur l'évolution de l'état de l'ensemble.

Si vous avez, par exemple, user1 effectuant update1 à replica1, ajoutant l'élément 1 à l'ensemble répliqué alors que simultanément user2 effectue update2, ajoutant element2 à replica2, Paxos fera en sorte que les répliques conviennent d'un ordre donné pour ces mises à jour, ou éventuellement d'accord sur le choix de l'une des la deuxième, selon la façon dont vous l'utilisez et ce que vous voulez atteindre. Si le résultat de Paxos est, disons, que update1 vient avant update2, chaque réplique mettra à jour l'ensemble dans cet ordre. En conséquence, les utilisateurs qui lisent l'ensemble en même temps que ces mises à jour peuvent observer, quel que soit l'endroit (à quel réplica) ils lisent, seuls les états suivants de l'ensemble (en supposant que l'ensemble était vide au début):

{} (jeu vide)

{element1}

{element1, element2}

De plus, ces états ne peuvent être vus que dans cet ordre, ce qui signifie qu'une fois que l'état de l'ensemble est {element1, element2} (à chaque réplique), aucune lecture ultérieure ne retournera {} ou {element1}.

Côté positif: Cet ensemble est simple à raisonner, car il équivaut à un ensemble qui n'est pas répliqué.

Côté négatif: Indisponibilité: si les répliques ne peuvent pas se parler (partition réseau), votre ensemble ne peut pas être mis à jour, car il ne peut y avoir aucun accord. Faible performances, latence élevée: L'accord exige que les répliques se synchronisent avant de répondre au client. Cela entraîne une latence proportionnelle à la latence entre les répliques.

Les CRDT ont des garanties plus faibles. Un ensemble CRDT n'est pas équivalent à un ensemble séquentiel à copie unique. Il asume qu'il n'y a pas d'accord ou de commande totale sur la façon dont les répliques sont mises à jour.

CRDTs garantit que si les deux répliques de l'ensemble ont vu les mêmes mises à jour (quel que soit l'ordre dans lequel ils voient ensuite, ils présenteront le même état; les répliques convergeront.

Dans notre exemple de deux utilisateurs effectuant des mises à jour simultanément, un système qui n'exécute pas Paxos pour commander des opérations sur l'ensemble (cela se produit, par exemple, sous une cohérence éventuelle ou causale), permettra à replica1 d'ajouter element1 tandis que replica2 ajoute element2

Ainsi, l'État à replica1 sera: {element1}

Et l'état à replica2 sera: {element2}

À ce stade, les répliques diverger. Plus tard, lorsque les répliques se synchroniseront, elles échangeront leurs mises à jour, affichant finalement cet état:

État à replica1 sera: {element1, element2}

L'État à replica2 sera: {element2, element1}

À ce stade, les répliques ont convergé.

Les utilisateurs qui lisent l'ensemble en même temps que ces mises à jour peuvent observer, en fonction de l'endroit (à quel réplica) ils lisent, les états suivants de l'ensemble (en supposant que l'ensemble était vide au debut):

{} (jeu vide)

{element1} (s'ils lisent à partir de replica1)

{element2} (s'ils lisent à partir de replica2)

{element1, element2}

{element2, element1}

Côté négatif: cet ensemble est difficile à raisonner, car il montre des États qui ne pourraient pas se produire dans un ensemble séquentiel. Dans notre exemple, nous n'avons observé que le cas de deux additions simultanées à un ensemble, ce qui est simple. Les ajouts et les suppressions simultanés sont plus complexes il y en a beaucoup types de données avec différents problèmes:

Une étude complète des types de données répliquées convergentes et commutatives

Côté positif: Haute disponibilité: Si les répliques ne peuvent pas se parler (partition réseau), votre ensemble peut être mis à jour. Les répliques se synchronisent lorsqu'elles se connectent. Haute performance, faible latence: les répliques répondent immédiatement aux clients et se synchronisent en arrière-plan, après avoir répondu au client.

Il y a un défaut avec L'exemple CRDT Treedoc. Chaque nœud nécessite un disambiguator pour le cas où deux systèmes s'insèrent en même temps avec la même clé.

Après cela, il n'est plus possible pour les systèmes d'insérer entre les entrées qui ont des clés identiques mais des désambiguïstes différents, car cela nécessite que le système insère une autre clé identique mais contrôle l'ordre des désambiguïstes. Les désambiguïstes ne sont pas denses, ce n'est donc pas toujours possible. Si l' les désambiguïstes étaient encore un autre arbre, vous résolvez un problème mais vous avez besoin d'un autre mécanisme de résolution des conflits plus en profondeur ... etc.

Ce problème non mentionné, plus le fait que vous devez faire un commit en deux phases pour ranger les méta-données me fait penser que les CRDT sont encore en cours.

Il y a plusieurs métriques que nous avons:

• débit (CRDT et Paxos sont les mêmes car toutes les requêtes sont répliquées sur toutes les répliques à la fin, peu importe CRDT ou Paxos);
• latence (CRDT est meilleur que Paxos car il écrit sur un plus petit nombre de répliques);
• fiabilité (CRDT est plus faible que Paxos car il écrit sur un plus petit nombre de répliques (plus petit que majority), ce qui peut entraîner une perte d'état);
• cohérence (CRDT est plus faible que Paxos car il permet des Écritures simultanées sans point de synchronisation (fondamentalement pas de répliques qui se chevauchent), tandis que les Écritures Paxos nécessitent toujours une réplique qui se chevauchent pour faire la sérialisation).

Ma suggestion est que nous devrions utiliser Paxos lorsque les répliques ne sont pas loin les unes des autres (par exemple, dans un centre de données), et utiliser CRDT lorsque le partitionnement du réseau est normal (par exemple, Mobile déconnecté).

Commentaire à une réponse de @btilly:

La question dans le sujet est liée à différents modèles de cohérence et donc à des modèles de conception:

• CRDT se rapporte à la famille d'algorithmesconsistance éventuelle ,
• Paxos famille d'algorithmes se rapporte à la forte cohérence / Linerizability (synchronisation client-Serveur,),
• RAFT est équivalent {[7] } aux PAXOS d'une manière algorithmique et cohérente, mais il est considéré comme plus facile de mettre.

CRDT et Paxos sont des choses très différentes et l'utilisation doit être décidée en fonction de vos exigences d'architecture. Je crois que la meilleure façon de le gérer est d'examiner les cas d'utilisation où ces algorithmes ont été appliqués avec succès.

Modèles D'utilisation:

CRDT peut être utilisé pour la synchronisation des données entre les clients (c'est-à-dire les appareils mobiles) et les serveurs, l'édition collaborative en temps réel, la synchronisation des valeurs dans les implémentations dist-db et tous les autres cas où la cohérence éventuelle est fin.

PAXOS principalement utilisé dans les systèmes propriétaires supportant l'infrastructure des systèmes (C'est-à-dire Chubby), ou pour implémenter la synchronisation dans les systèmes de base de données distribués comme BigTable, Datastore,Spinnaker, Spanner et etc.

RAFT est plus populaire dans les projets D'infrastructure OSS comme ETCD, Consul,...

(ne me souviens pas de ce que CockroachDB et TiDB sont basés sur)

Il y a aussi un BFT, mais il est moins utilisé.

P. S. PAXOS != ZooKeeper. ZooKeeper utilise un algorithme différent appelé ZAB et n'est pas une machine d'état répliquée, mais une machine d'instantanés répliqués avec un seul écrivain et un modèle de lecture détendu. Chubby de Google basé sur Paxos, mais son propriétaire.

P. S. S. Il est intéressant de voir comment PAXOS évolue toutes ces années. Au cours des 20 dernières années, de nombreuses variantes ont été inventées pour gérer diverses optimisations de cas de périphérie, de tailles de quorum et de reconfiguration de cluster.

Chaque fois que cela est approprié. Cependant, PaxOS n'est pas si mauvais que son débit est généralement le même qu'avec CRDT, sans parler du fait que la fiabilité est beaucoup plus élevée (CRDT peut entraîner une perte d'état), et sa latence n'est pas si mauvaise non plus car elle ne nécessite qu'une majorité des répliques réponses au lieu de toutes.