Programma Lezione 76 di 148 · Limiti strani
Limiti strani

Prima offline

Perché è importante "Invia tutta la lista, vince l'ultima scrittura" funziona finché due dispositivi non modificano mentre sono offline. Allora le modifiche di una persona spariscono in silenzio, e nessuno sa dire dove siano finite.

L'app della lista della spesa di una famiglia deve funzionare nel seminterrato di un supermercato senza segnale. Ogni dispositivo tiene un registro di ciò che ha fatto. Quando i dispositivi si riconnettono, i due registri vengono uniti in un'unica lista. Entrambi i registri iniziano con la stessa storia condivisa (tutto ciò che era stato sincronizzato prima di andare offline), poi ognuno ha le proprie modifiche.

Registro delle operazioni: una registrazione dei cambiamenti fatti (aggiungi questo, togli quello), invece di una copia del risultato. I registri si possono unire; le copie possono solo sovrascrivere.

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

Scrivi merge(log_a, log_b) e restituisci la lista ordinata degli articoli della lista della spesa unita (ogni articolo una volta). Un registro è una lista di operazioni: ("add", item, tag), dove ogni aggiunta ha un'etichetta unica, e ("remove", item, tags), dove tags elenca le aggiunte di quell'articolo che il dispositivo poteva vedere quando l'ha tolto.

Limiti. Nessuna modifica può andare persa: un articolo è nella lista se almeno una delle sue aggiunte non è mai stata tolta. Una rimozione annulla solo le etichette che elenca, quindi un'aggiunta fatta dall'altro dispositivo mentre era offline sopravvive. Entrambi i registri possono contenere le stesse operazioni condivise (contale una volta). merge(a, b) deve essere uguale a merge(b, a).

Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione

Questo esercizio si apre presto

Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.