ݺߣ

ݺߣShare a Scribd company logo

Codemotion Milan '22 - Real Time Data - No CRDTs, no party!

•
•
Luigi Fugaro
Luigi Fugaro

Sono ormai anni che i maggiori vendor di piattaforme database parlano di dati in tempo reale, le cosiddette Real Time Data Platform. Ma è veramente solo questione di tempo? Certo che no! Ottenere il dato non è mai stato un problema, gestirne le scritture concorrenti e stabilirne la validità, quello è il vero problema. La tecnologia Conflict-Free Replicated Data Types (CRDT) è la soluzione. In questo talk illustrerò quali sono gli approcci per risolvere i conflitti per database distribuiti, il meccanismo dei CRDT e loro implementazione. Il futuro dei DB è solo Real Time e passa per i CRDT.

1 of 33
Luigi Fugaro Real Time Data No CRDTs, no party!
Nell’IT da oltre 20 anni. Mi sono sempre occupato di programmazione, partendo dal QuickBasic, al Pascal, al Fortran, fino a Java nel 1996 con la prima specifica delle Servlet. La mia esperienza lavorativa comincia nel 1999, come WebMaster. Da lì in poi è stato un susseguirsi di evoluzioni (e involuzioni ho fatto un gestionale in Clipper 5.2) fino ad approdare in Red Hat nel 2012 dove sono stato per oltre 7 anni - esperienza fantastica! Successivamente sono entrato in Datadog, dove ho avuto il piacere di conoscere il mondo del monitoraggio e dell’observability. Nell’estate 2021, la chiamata Redis - tecnologia made in Italy. Redis è quella tecnologia dove le architetture, i dati e le applicazioni gioiscono nello stare insieme! Luigi Fugaro Solutions Architect luigi.fugaro@redis.com
Contesto 1
Data
Big Data
Data Lake
I dati son dati!
Codemotion Milan '22 - Real Time Data - No CRDTs, no party!
Codemotion Milan '22 - Real Time Data - No CRDTs, no party!
Scritture concorrenti 3
Algoritmi noti (WIP) Operational Transformation (OT) (1989-2006) Conflict-Free Replicated Data Types (CRDTs) (2006-now)
|C|I|A|O|_|M|A|M|M|A|!|_ aggiungi “_MAMMA” alla posizione 4 |0|1|2|3|4|5|6|7|8|9|0| |C|I|A|O|!| |C|I|A|O|!|!|_ |0|1|2|3|4|5| |0|1|2|3|4| aggiungi “!” alla posizione 5 aggiungi “!” alla posizione 11 aggiungi “_MAMMA” alla posizione 4 |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1| |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1|
Qualcuno l’ha notato?
CRDTs 4
|C|I|A|O|_|M|A|M|M|A|!|_ aggiungi “_MAMMA” alla posizione 4 |0|1|2|3|4|5|6|7|8|9|0| |C|I|A|O|!| |C|I|A|O|!|!|_ |0|1|2|3|4|5| |0|1|2|3|4| aggiungi “!” alla posizione 5 aggiungi “!” alla posizione 5 aggiungi “_MAMMA” alla posizione 4 |C|I|A|O|_|!|M|A|M|M|A|!| |0|1|2|3|4|5|6|7|8|9|0|1| |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1|
|C|I|A|O|_|M|A|M|M|A|!|_ aggiungi “_MAMMA” alla posizione 4 |0|1|2|3|4|5|6|7|8|9|0| |C|I|A|O|!| |C|I|A|O|!|!|_ |0|1|2|3|4|5| |0|1|2|3|4| aggiungi “!” alla posizione 5 aggiungi “!” alla posizione 5 aggiungi “_MAMMA” alla posizione 4 |C|I|A|O|_|!|M|A|M|M|A|!| |0|1|2|3|4|5|6|7|8|9|0|1| |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1|
Algoritmi basati su CRDTs ● Logoot - Interleaving anomalies ● LSEQ - Interleaving anomalies ● RGA - Interleaving anomalies free, quasi! ● Treedoc - no Interleaving anomalies ● WOOT - no Interleaving anomalies ● Astrong - Interleaving anomalies
Algoritmi basati su CRDTs ● LWW - Last Write Wins ○ Ogni mutazione ha il proprio timestamp unico. La mutazione con il timestamp più alto vince. ● PN-Counters - Positive Negative Counters ○ Somma algebrica degli incrementi, meno, la somma algebrica dei decrementi. ● OR-Set - Oberved Removed-Set ○ Se un elemento è aggiunto e rimosso, l’aggiunta vince sulla cancellazione.
Qualcuno ha notato qualcosa di ambiguo?
Algoritmi basati su CRDTs ● LWW - Last Write Wins ○ Ogni mutazione ha il proprio timestamp unico. La mutazione con il timestamp più alto vince. ● PN-Counters - Positive Negative Counters ○ Somma algebrica degli incrementi, meno, la somma algebrica dei decrementi. ● OR-Set - Oberved Removed-Set ○ Se un elemento è aggiunto e rimosso, l’aggiunta vince sulla cancellazione.
Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Esempio LWW
Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Codice Descrizione 1 Tintoria 2 Spesa 3 Posta Codice Descrizione 1 Spesa 2 Tintoria 3 Posta Codice Descrizione 1 Tintoria 2 Spesa 3 Posta Codice Descrizione 1 Tintoria 2 Spesa 3 Posta LWW Esempio LWW
Sincronizziamo gli orologi ● Gli orologi non sono sincronizzati in un sistema distribuito asincrono! ● Gli eventi devono essere ordinati per poter essere processati in modo deterministico. ● Algoritmi di sincronizzazione del tempo: ○ Cristian’s algorithm ○ Berkley’s algorithm ○ NTP algorithm ● Logical timestamp → Vector Clocks
Vector Clocks R1 R2 R3 (0,0,0) (0,0,0) (0,0,0) (1,0,0) (3,0,0) (2,2,1) (2,3,1) (0,0,2) (4,3,1) (5,3,3) (5,3,1) (2,0,0) (0,0,1) (0,1,1)
Redis CRDTs 5
Redis ed i suoi CRDTs Strings Bitmaps Bit fields Hashes Lists Sets Sorted Sets Geospatial HyperLogLog Streams KEY
Redis ed i suoi CRDTs Strings Bitmaps Bit fields Hashes Lists Sets Sorted Sets Geospatial HyperLogLog Streams KEY JSON Search
Consistenza 4
Modelli di consistenza
Codemotion Milan '22 - Real Time Data - No CRDTs, no party!
Codemotion Milan '22 - Real Time Data - No CRDTs, no party!
Real Time Data No CRDTs, no party!
Grazie! l.fugaro@gmail.com @foogaro @foogaro https:/ /www.linkedin.com/in/luigifugaro/

More Related Content

Codemotion Milan '22 - Real Time Data - No CRDTs, no party!

  • 1. Luigi Fugaro Real Time Data No CRDTs, no party!
  • 2. Nell’IT da oltre 20 anni. Mi sono sempre occupato di programmazione, partendo dal QuickBasic, al Pascal, al Fortran, fino a Java nel 1996 con la prima specifica delle Servlet. La mia esperienza lavorativa comincia nel 1999, come WebMaster. Da lì in poi è stato un susseguirsi di evoluzioni (e involuzioni ho fatto un gestionale in Clipper 5.2) fino ad approdare in Red Hat nel 2012 dove sono stato per oltre 7 anni - esperienza fantastica! Successivamente sono entrato in Datadog, dove ho avuto il piacere di conoscere il mondo del monitoraggio e dell’observability. Nell’estate 2021, la chiamata Redis - tecnologia made in Italy. Redis è quella tecnologia dove le architetture, i dati e le applicazioni gioiscono nello stare insieme! Luigi Fugaro Solutions Architect luigi.fugaro@redis.com
  • 7. I dati son dati!
  • 11. Algoritmi noti (WIP) Operational Transformation (OT) (1989-2006) Conflict-Free Replicated Data Types (CRDTs) (2006-now)
  • 12. |C|I|A|O|_|M|A|M|M|A|!|_ aggiungi “_MAMMA” alla posizione 4 |0|1|2|3|4|5|6|7|8|9|0| |C|I|A|O|!| |C|I|A|O|!|!|_ |0|1|2|3|4|5| |0|1|2|3|4| aggiungi “!” alla posizione 5 aggiungi “!” alla posizione 11 aggiungi “_MAMMA” alla posizione 4 |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1| |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1|
  • 15. |C|I|A|O|_|M|A|M|M|A|!|_ aggiungi “_MAMMA” alla posizione 4 |0|1|2|3|4|5|6|7|8|9|0| |C|I|A|O|!| |C|I|A|O|!|!|_ |0|1|2|3|4|5| |0|1|2|3|4| aggiungi “!” alla posizione 5 aggiungi “!” alla posizione 5 aggiungi “_MAMMA” alla posizione 4 |C|I|A|O|_|!|M|A|M|M|A|!| |0|1|2|3|4|5|6|7|8|9|0|1| |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1|
  • 16. |C|I|A|O|_|M|A|M|M|A|!|_ aggiungi “_MAMMA” alla posizione 4 |0|1|2|3|4|5|6|7|8|9|0| |C|I|A|O|!| |C|I|A|O|!|!|_ |0|1|2|3|4|5| |0|1|2|3|4| aggiungi “!” alla posizione 5 aggiungi “!” alla posizione 5 aggiungi “_MAMMA” alla posizione 4 |C|I|A|O|_|!|M|A|M|M|A|!| |0|1|2|3|4|5|6|7|8|9|0|1| |C|I|A|O|_|M|A|M|M|A|!|!| |0|1|2|3|4|5|6|7|8|9|0|1|
  • 17. Algoritmi basati su CRDTs ● Logoot - Interleaving anomalies ● LSEQ - Interleaving anomalies ● RGA - Interleaving anomalies free, quasi! ● Treedoc - no Interleaving anomalies ● WOOT - no Interleaving anomalies ● Astrong - Interleaving anomalies
  • 18. Algoritmi basati su CRDTs ● LWW - Last Write Wins ○ Ogni mutazione ha il proprio timestamp unico. La mutazione con il timestamp più alto vince. ● PN-Counters - Positive Negative Counters ○ Somma algebrica degli incrementi, meno, la somma algebrica dei decrementi. ● OR-Set - Oberved Removed-Set ○ Se un elemento è aggiunto e rimosso, l’aggiunta vince sulla cancellazione.
  • 19. Qualcuno ha notato qualcosa di ambiguo?
  • 20. Algoritmi basati su CRDTs ● LWW - Last Write Wins ○ Ogni mutazione ha il proprio timestamp unico. La mutazione con il timestamp più alto vince. ● PN-Counters - Positive Negative Counters ○ Somma algebrica degli incrementi, meno, la somma algebrica dei decrementi. ● OR-Set - Oberved Removed-Set ○ Se un elemento è aggiunto e rimosso, l’aggiunta vince sulla cancellazione.
  • 21. Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Esempio LWW
  • 22. Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Codice Descrizione 1 Spesa 2 Posta 3 Tintoria Codice Descrizione 1 Tintoria 2 Spesa 3 Posta Codice Descrizione 1 Spesa 2 Tintoria 3 Posta Codice Descrizione 1 Tintoria 2 Spesa 3 Posta Codice Descrizione 1 Tintoria 2 Spesa 3 Posta LWW Esempio LWW
  • 23. Sincronizziamo gli orologi ● Gli orologi non sono sincronizzati in un sistema distribuito asincrono! ● Gli eventi devono essere ordinati per poter essere processati in modo deterministico. ● Algoritmi di sincronizzazione del tempo: ○ Cristian’s algorithm ○ Berkley’s algorithm ○ NTP algorithm ● Logical timestamp → Vector Clocks
  • 24. Vector Clocks R1 R2 R3 (0,0,0) (0,0,0) (0,0,0) (1,0,0) (3,0,0) (2,2,1) (2,3,1) (0,0,2) (4,3,1) (5,3,3) (5,3,1) (2,0,0) (0,0,1) (0,1,1)
  • 26. Redis ed i suoi CRDTs Strings Bitmaps Bit fields Hashes Lists Sets Sorted Sets Geospatial HyperLogLog Streams KEY
  • 27. Redis ed i suoi CRDTs Strings Bitmaps Bit fields Hashes Lists Sets Sorted Sets Geospatial HyperLogLog Streams KEY JSON Search
  • 32. Real Time Data No CRDTs, no party!