Programme Leçon 76 sur 148 · Des limites étranges
Des limites étranges

Hors ligne d'abord

Pourquoi c'est important « Envoie toute la liste, la dernière écriture gagne » marche jusqu'à ce que deux appareils modifient hors ligne. Alors les modifications d'une personne disparaissent en silence, et personne ne peut dire où elles sont passées.

Une appli de liste de courses familiale doit marcher dans un sous-sol de supermarché sans réseau. Chaque appareil garde un journal de ce qu'il a fait. Quand les appareils se reconnectent, les deux journaux sont fusionnés en une seule liste. Les deux journaux commencent par le même historique partagé (tout ce qui était synchronisé avant qu'ils passent hors ligne), puis chacun a ses propres modifications.

Journal d'opérations : un enregistrement des changements faits (ajouter ceci, retirer cela), plutôt qu'une copie du résultat. Les journaux peuvent être fusionnés ; les copies ne peuvent que s'écraser.

("add", "milk", "p7")             # tag p7 is unique to this add
("remove", "milk", ["p7", "s2"])  # removes exactly the adds this device had seen
À ton tour

Écris merge(log_a, log_b) et renvoie la liste triée des articles de la liste de courses fusionnée (chaque article une fois). Un journal est une liste d'opérations : ("add", item, tag), où chaque ajout a une étiquette unique, et ("remove", item, tags), où tags liste les ajouts de cet article que l'appareil pouvait voir quand il l'a retiré.

Limites. Aucune modification ne doit être perdue : un article est sur la liste si au moins un de ses ajouts n'a jamais été retiré. Un retrait n'annule que les étiquettes qu'il liste, donc un ajout fait par l'autre appareil pendant qu'il était hors ligne survit. Les deux journaux peuvent contenir les mêmes opérations partagées (compte-les une fois). merge(a, b) doit être égal à merge(b, a).

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.