Preuves de réplication
Cette page énonce les propriétés sur lesquelles repose le protocole de réplication des documents et explique pourquoi chacune tient. Elle couvre l’état par document de barrel_live (apps/barrel_docdb/src/barrel_live.erl) et les règles qui l’entourent. Lisez-la quand vous modifiez la fusion, la façon dont une écriture choisit ce qu’elle remplace, la résolution automatique, l’éviction ou le chemin de mise à niveau. Le contrôle exécutable est barrel_live_SUITE ; chaque section nomme les tests qui l’exercent.
Modèle
Un token est (HLC, writer), ordonné par HLC puis par writer. Le writer d’une écriture utilisateur est l’identifiant d’écrivain de la base, émis à chaque ouverture. Le writer d’une résolution automatique est auto:<hash>.
Un état S a trois parties :
live: les versions courantes, chacune avec un indicateur de suppression, un vecteurvv(pour les anciens pairs) et, pour une résolution automatique, sonbaseet le hash de sonresult.obs: par writer, la plus haute HLC de ce writer que cet état a traitée. Seules les écritures du writer lui-même l’augmentent.cloud: les tokens exacts que cet état a vus (versions d’anciens pairs, résolutions automatiques, versions évincées et converties).
seen(S, t) est vrai quand t est dans cloud, ou quand obs[writer(t)] >= hlc(t).
Invariant I1. Tout token live est vu.
Invariant I2 (clôture). Si obs[w] >= h, tout token du writer w de HLC au plus h qui a jamais été écrit a été traité par S : il est live dans S, ou une écriture dont l’effet a atteint S l’a remplacé.
I2 tient parce que :
- Un seul processus writer écrit toutes les versions d’une base (vérifié à l’exécution :
alloc_hlc/1échoue en dehors de lui). - Les HLC d’un writer croissent strictement, et chaque écriture prend un token supérieur à tous les tokens live et à la marque propre du writer (
author/4vérifie les deux). - Un identifiant de writer ne sert qu’à une seule ouverture : un crash ou une copie restaurée ne peut donc pas écrire sous un identifiant dont il a perdu les versions antérieures.
- Seule l’écriture propre du writer augmente
obs[w]. Les arrivées d’anciens pairs, la conversion et les résolutions automatiques ajoutent seulement des tokens exacts àcloud.
La règle 4 est celle que le contre-exemple de relais de la troisième revue cassait (un ancien pair qui relayait a2 augmentait obs[a] et avalait a1). Elle est fixée par relayed_version_keeps_sibling et conversion_keeps_unseen_sibling, dont les contrôles négatifs augmentent la marque et perdent l’écriture.
T1. La fusion est un demi-treillis supérieur
merge/2 garde une version que les deux côtés détiennent, ou une version que l’autre côté n’a jamais vue ; les contextes se joignent par union (cloud) et par maximum point à point (obs) ; les informations d’un token détenu des deux côtés se joignent point à point (vv au maximum, base par union, une base absente valant le minimum).
C’est la jointure DotFun du cadre des CRDT causaux avec des valeurs en treillis (Almeida, Shoker, Baquero 2018, section 7.4). Ses lois tiennent sur les états dont les contextes sont causalement cohérents, ce que donnent I1 et I2. Les écarts par rapport à l’article sont que les dots sont des tokens HLC compactés par I2 plutôt que par contiguïté de compteur, et que cloud ne se compacte jamais ; aucun des deux ne change les équations ensemblistes.
Contrôle : join_laws_on_reachable_states vérifie la commutativité, l’idempotence et l’associativité sur 373 438 triplets d’états issus d’une même exécution (un token ne nomme une seule écriture qu’au sein d’une exécution).
T2. Clôture
Argumentée ci-dessus (I2). Contrôle : les deux scénarios de relais et de conversion avec leurs contrôles négatifs, et chaque exécution de recherche (une clôture cassée se manifeste par une écriture perdue).
T3. Un document qui existe a toujours une version live
Prenez le token le plus haut p dans live(A) ∪ live(B), par exemple p ∈ live(A). La fusion ne supprime p que si p est vu par B et n’y est pas live. Quelque chose dans l’historique de B l’a retiré, et les seules suppressions possibles sont :
- une écriture utilisateur, dont le token est au-dessus de tout token live, donc au-dessus de
p; - une résolution automatique, dont le token est au-dessus de tout ce qu’elle remplace (HLC = la plus haute de sa base plus la taille de la base, donc strictement au-dessus de toute entrée, autres résolutions comprises) ;
- l’éviction, qui ne retire jamais la version gagnante, donc une version au-dessus de
pétait live.
Dans chaque cas, un token au-dessus de p était live dans B, et par le même argument appliqué à ce token, un token au-dessus de p est encore live dans B. Cela contredit le fait que p soit le plus haut. Les arrivées d’anciens pairs et la conversion ne retirent rien.
Contrôle : empty est vérifié dans chaque exécution de recherche ; auto_sorts_above_replaced fixe la règle + size of base, et son contrôle négatif (+ 1) classe une résolution en dessous de ce qu’elle a remplacé.
T4. Convergence
Une fois les écritures arrêtées, la fusion sur un ensemble connexe de chemins de réplication atteint la jointure de tous les états (T1). Avec un résolveur, chaque résolution couvre strictement plus d’écritures originales que toute version automatique qu’elle remplace (T10) : les étapes de résolution sont donc en nombre fini et le point fixe est atteint. L’éviction retire des versions mais est déterministe sur l’état, elle ne casse donc pas la convergence.
Contrôle : diverge et stuck dans chaque exécution de recherche, qui amène toutes les paires à un point fixe.
T5. Une écriture ne retire que ce qu’elle a observé
replaces/3 renvoie, par ordre de priorité :
- l’ensemble observé explicite, intersecté avec
live; - quand la version gagnante est une suppression, toutes les suppressions live, après vérification de
Revs’il est fourni (la lecture a montré un document supprimé, qui a observé toutes les suppressions) ; - sinon
[Rev], et seulement siRevest la version gagnante.
author/4 retire exactement cette liste.
Exceptions :
- l’éviction ;
- l’appel de compatibilité
resolve_conflict(Db, Id, BaseRev, Resolution), qui remplace toutes les versions courantes et peut retirer une version arrivée après la lecture.
Contrôle : edit_rules.
T6. Un stub fusionne comme le document supprimé
Un stub stocke les mêmes live, obs et cloud, et ne laisse tomber que les corps, l’historique et les entrées d’index, qui ne font pas partie de l’état. digest/1 et merge/2 ne lisent que l’état, ils ne peuvent donc pas distinguer les deux. (Les stubs arrivent avec l’état du document ; la propriété y tient par construction.)
T7. Purge désactivée : une version remplacée ne revient jamais
Un token remplacé est vu par la réplique qui l’a remplacé. L’ensemble vu ne fait que croître : la fusion unit les contextes, les écritures et les évictions y ajoutent, et la conversion n’a lieu qu’une fois par document. Une fusion ne garde jamais un token que l’autre côté a vu et retiré, et l’arrivée d’un token déjà vu depuis un ancien pair est ignorée. Donc dès qu’une réplique remplace t, toute réplique qui fusionne ensuite avec elle, directement ou par d’autres, retire t et ne l’admet plus jamais, quels que soient le délai, la duplication ou le réordonnancement des états.
Un crash qui annule des écritures non synchronisées peut perdre un remplacement en même temps que l’écriture qui l’a produit. Ce remplacement n’a atteint personne : personne n’a donc vu t remplacé. S’il a atteint un pair, la fusion suivante retire t à nouveau.
Contrôle : resurrected dans chaque exécution de recherche (livraisons tardives d’états passés comprises) ; pre_upgrade_delete_stays_deleted et son contrôle négatif (pas d’amorçage de conversion).
T8. Purge activée
T7 tient pour tout ce qui est plus récent que tombstone_purge_after. Une réplique, une sauvegarde, un état stocké ou un message plus ancien que ce délai peut faire revenir un document purgé. C’est le relâchement documenté, comme le gc_grace_seconds de Cassandra ; il n’y a rien de plus à prouver.
T9. Filtres
Un état sans version live passe tous les filtres ; sinon, il passe quand un corps live correspond. Une réplique reçoit chaque document correspondant et chaque suppression qui ne laisse aucune version live, pour un document qu’elle détient, à condition qu’un chemin de tâches de réplication transporte le document. Comme le contexte est par document, ne pas recevoir un document ne le marque jamais comme vu : un changement de filtre ne peut donc pas faire sauter à une réplique un document qui lui correspond plus tard (le nouveau périmètre est rejoué depuis le début). Vérifié dans les modèles Python de la conception simplifiée ; le contrôle Erlang gagnera des cas de filtre quand passes/2 arrivera.
T10. Résolution automatique
La base d’une résolution est l’union des bases de ses entrées (une écriture utilisateur se couvre elle-même). Son token est calculé à partir de la base et du résultat.
- Une fonction donne une version. Une fonction indépendante de l’ordre donne le même résultat pour la même base : chaque réplique qui résout les mêmes écritures originales, quel que soit le regroupement, écrit donc le même token.
- Elle termine. L’arrêt sans remplacement interdit de remplacer une version automatique de même base et de résultat différent. Une version automatique n’est donc remplacée que par une version couvrant strictement plus d’écritures originales, ou par elle-même. Les bases sont des sous-ensembles d’un ensemble fini d’écritures.
- Elle ne vide jamais un document : T3, avec la règle
+ size of base. - Elle ne perd aucune écriture utilisateur : une résolution ne remplace que les versions live qu’on lui a données, qu’elle couvre toutes.
- Des fonctions différentes sur des répliques différentes terminent toujours, ne vident jamais le document et ne perdent aucune écriture, mais le résultat qui survit dépend de l’ordre de synchronisation. C’est une erreur de configuration, documentée comme telle.
Contrôle :
overlapping_auto_one_version; son contrôle négatif (une résolution nommée par l’horloge propre du résolveur) laisse deux versions ;different_functions_never_empty; son contrôle négatif (pas d’arrêt) vide le document ;search_resolver.
Ce que le contrôle couvre et ne couvre pas
barrel_live_SUITE exécute des recherches exhaustives bornées sur un document : une ligne de trois répliques et un triangle, jusqu’à trois écritures utilisateur (modification, modification avec ensemble observé, suppression), une rotation de writer, la livraison tardive d’états passés, et le résolveur activé ou non. Chaque recherche va jusqu’au bout dans ses bornes. search_negative_control montre que la recherche détecte une fusion qui ignore le contexte.
Non couvert ici :
- plusieurs documents, l’éviction dans la recherche et les anciens pairs dans la recherche (ils sont couverts par des scénarios dirigés) ;
- les filtres, les stubs et la purge, qui arrivent plus tard ;
- le décalage d’horloge et la vivacité sous écritures continues.
Les vérifications mécanisées se trouvent dans proofs/ (voir son README) : TLC explore chaque état atteignable de trois répliques, crashs avec annulation et résolution automatique compris ; Ivy prouve la clôture (T2), T5 et T7 comme invariants inductifs pour un nombre quelconque de répliques et de writers ; Lean prouve les lois de jointure (T1), T7 pour une fusion et T6. Chacun a des contrôles négatifs qui doivent échouer.