Réplication et cohérence des données

La réplication des données maintient plusieurs copies des données pour assurer la disponibilité et améliorer les performances, tandis que les protocoles de cohérence régissent la manière dont les lectures et les écritures sont réconciliées entre ces copies.

Definition

La réplication des données maintient des copies d'un élément de données sur plusieurs nœuds ; un modèle de cohérence spécifie les garanties concernant les valeurs que les lectures peuvent retourner, compte tenu de l'historique des écritures, allant de la cohérence forte (chaque lecture voit la dernière écriture) à la cohérence éventuelle (les répliques convergent si les mises à jour cessent).

Scope

Ce sujet aborde les stratégies de réplication (primaire-secondaire, multi-maître, quorum), les protocoles de lecture/écriture basés sur le quorum et leurs exigences d'intersection, l'anti-entropie et le 'gossip' pour la convergence éventuelle, la détection des conflits avec les vecteurs de version et les types de données répliqués sans conflit (CRDTs), ainsi que le spectre de la cohérence, de la linéarisable à l'éventuelle. Il traite de l'équivalent au niveau des données de la réplication d'automates.

Core questions

• Comment les tailles de quorum pour les lectures et les écritures garantissent-elles que les lectures observent la dernière écriture ?
• Comment les répliques convergent-elles sous cohérence éventuelle, et comment les conflits sont-ils résolus ?
• Quel niveau de cohérence une application devrait-elle choisir compte tenu de ses besoins en latence et en disponibilité ?

Key theories

Consensus par quorum pour les données répliquées

En attribuant des votes aux répliques et en exigeant des quorums de lecture et d'écriture dont la somme des tailles est supérieure au total, chaque quorum de lecture intersecte le dernier quorum d'écriture, garantissant ainsi que les lectures observent des données à jour.

Cohérence éventuelle et anti-entropie

Les magasins hautement disponibles acceptent les écritures sur n'importe quelle réplique et se réconcilient de manière asynchrone via le 'gossip' et les vecteurs de version, garantissant seulement que les répliques convergent lorsque les mises à jour cessent, comme l'illustre la conception de Dynamo.

Types de données répliqués sans conflit

Les CRDTs sont des types de données dont les opérations sont conçues pour commuter ou dont les états forment un semi-treillis de jointure, de sorte que les mises à jour concurrentes fusionnent de manière déterministe sans coordination, offrant une cohérence éventuelle forte.

Clinical relevance

Ces techniques définissent les garanties des systèmes de stockage réels : les protocoles de quorum sous-tendent les magasins clé-valeur fortement cohérents, tandis que la cohérence éventuelle et les CRDTs alimentent les magasins hautement disponibles, les paniers d'achat et les éditeurs collaboratifs où la disponibilité prime sur l'accord immédiat.

History

Le schéma de vote pondéré de Gifford en 1979 a établi la réplication par quorum ; l'article Dynamo d'Amazon en 2007 a popularisé la cohérence éventuelle hautement disponible ; et la formalisation des CRDTs en 2011 a fourni une base de principes pour une convergence sans coordination, façonnant la conception moderne des données répliquées.

Debates

Quel niveau de cohérence les données répliquées devraient-elles fournir par défaut ?

La cohérence forte facilite le développement d'applications mais limite la disponibilité et ajoute de la latence, tandis que la cohérence éventuelle maximise la disponibilité au prix de l'exposition à une divergence temporaire ; les quorums ajustables et les CRDTs sont des tentatives pour permettre aux applications de choisir par opération.

Key figures

• David Gifford
• Werner Vogels
• Marc Shapiro
• Andrew S. Tanenbaum

Seminal works

• gifford1979
• decandia2007
• shapiro2011

Frequently asked questions

Comment les quorums de lecture et d'écriture garantissent-ils des lectures à jour ?

Si une écriture doit atteindre W répliques et qu'une lecture doit consulter R répliques, et que R plus W dépasse le nombre total de répliques, alors tout quorum de lecture chevauche le quorum d'écriture le plus récent dans au moins une réplique, de sorte que la lecture peut observer la dernière valeur.