From f5a7bc37365e8e593359db114a4e44f8e8c65207 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Thu, 12 Jan 2023 17:17:13 +0100 Subject: Add 12 lattice diagrams to explain CRDTs and quorums --- doc/talks/2023-01-18-tocatta/Makefile | 12 + doc/talks/2023-01-18-tocatta/assets/lattice1.svg | 433 ++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice2.svg | 514 +++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice3.svg | 515 +++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice4.svg | 525 ++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice5.svg | 536 ++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice6.svg | 553 +++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice7.svg | 581 ++++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice8.svg | 587 ++++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/lattice9.svg | 587 ++++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/latticeA.svg | 587 ++++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/latticeB.svg | 598 +++++++++++++++++++++++ doc/talks/2023-01-18-tocatta/assets/latticeC.svg | 598 +++++++++++++++++++++++ doc/talks/2023-01-18-tocatta/talk.pdf | Bin 2594434 -> 2643346 bytes doc/talks/2023-01-18-tocatta/talk.tex | 43 +- 15 files changed, 6658 insertions(+), 11 deletions(-) create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice1.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice2.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice3.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice4.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice5.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice6.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice7.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice8.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/lattice9.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/latticeA.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/latticeB.svg create mode 100644 doc/talks/2023-01-18-tocatta/assets/latticeC.svg (limited to 'doc/talks') diff --git a/doc/talks/2023-01-18-tocatta/Makefile b/doc/talks/2023-01-18-tocatta/Makefile index 4a967d24..a1f76e15 100644 --- a/doc/talks/2023-01-18-tocatta/Makefile +++ b/doc/talks/2023-01-18-tocatta/Makefile @@ -4,6 +4,18 @@ ASSETS=assets/consistent_hashing_1.pdf \ assets/consistent_hashing_4.pdf \ assets/garage_tables.pdf \ assets/consensus.pdf_tex \ + assets/lattice1.pdf_tex \ + assets/lattice2.pdf_tex \ + assets/lattice3.pdf_tex \ + assets/lattice4.pdf_tex \ + assets/lattice5.pdf_tex \ + assets/lattice6.pdf_tex \ + assets/lattice7.pdf_tex \ + assets/lattice8.pdf_tex \ + assets/lattice9.pdf_tex \ + assets/latticeA.pdf_tex \ + assets/latticeB.pdf_tex \ + assets/latticeC.pdf_tex \ assets/deuxfleurs.pdf talk.pdf: talk.tex $(ASSETS) diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice1.svg b/doc/talks/2023-01-18-tocatta/assets/lattice1.svg new file mode 100644 index 00000000..8bfa5aa7 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice1.svg @@ -0,0 +1,433 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice2.svg b/doc/talks/2023-01-18-tocatta/assets/lattice2.svg new file mode 100644 index 00000000..adcd92cb --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice2.svg @@ -0,0 +1,514 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\not\sqsupseteq \{a\}$ + $\not\sqsupseteq \{a\}$ + $\not\sqsupseteq \{a\}$ + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice3.svg b/doc/talks/2023-01-18-tocatta/assets/lattice3.svg new file mode 100644 index 00000000..640dc468 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice3.svg @@ -0,0 +1,515 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + $\not\sqsupseteq \{a\}$ + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice4.svg b/doc/talks/2023-01-18-tocatta/assets/lattice4.svg new file mode 100644 index 00000000..b2a99e28 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice4.svg @@ -0,0 +1,525 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + return OK + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice5.svg b/doc/talks/2023-01-18-tocatta/assets/lattice5.svg new file mode 100644 index 00000000..bc6b7195 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice5.svg @@ -0,0 +1,536 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $read()$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + return OK + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice6.svg b/doc/talks/2023-01-18-tocatta/assets/lattice6.svg new file mode 100644 index 00000000..176b1715 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice6.svg @@ -0,0 +1,553 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $read()$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + + $\to \{\}$ + return OK + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice7.svg b/doc/talks/2023-01-18-tocatta/assets/lattice7.svg new file mode 100644 index 00000000..7ce8bda8 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice7.svg @@ -0,0 +1,581 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $read()$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + + $\to \{\}$ + return OK + return $\{\}\sqcup\{a\}=\{a\}$ + + $\to \{a\}$ + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice8.svg b/doc/talks/2023-01-18-tocatta/assets/lattice8.svg new file mode 100644 index 00000000..3bada791 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice8.svg @@ -0,0 +1,587 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + return OK + + + + $write(\{b\})$: + $\not\sqsupseteq \{b\}$ + $\not\sqsupseteq \{b\}$ + $\not\sqsupseteq \{b\}$ + + diff --git a/doc/talks/2023-01-18-tocatta/assets/lattice9.svg b/doc/talks/2023-01-18-tocatta/assets/lattice9.svg new file mode 100644 index 00000000..8b3c6585 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/lattice9.svg @@ -0,0 +1,587 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\not\sqsupseteq \{a\}$ + return OK + + + + $write(\{b\})$: + $\not\sqsupseteq \{b\}$ + $\not\sqsupseteq \{b\}$ + $\sqsupseteq \{b\} \to$ OK + + diff --git a/doc/talks/2023-01-18-tocatta/assets/latticeA.svg b/doc/talks/2023-01-18-tocatta/assets/latticeA.svg new file mode 100644 index 00000000..400ccff8 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/latticeA.svg @@ -0,0 +1,587 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\}$ + return OK + + + + $write(\{b\})$: + $\not\sqsupseteq \{b\}$ + $\not\sqsupseteq \{b\}$ + $\sqsupseteq \{b\} \to$ OK + + diff --git a/doc/talks/2023-01-18-tocatta/assets/latticeB.svg b/doc/talks/2023-01-18-tocatta/assets/latticeB.svg new file mode 100644 index 00000000..06725d75 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/latticeB.svg @@ -0,0 +1,598 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\}$ + return OK + return OK + + + + $write(\{b\})$: + $\not\sqsupseteq \{b\}$ + $\sqsupseteq \{b\} \to$ OK + $\sqsupseteq \{b\} \to$ OK + + diff --git a/doc/talks/2023-01-18-tocatta/assets/latticeC.svg b/doc/talks/2023-01-18-tocatta/assets/latticeC.svg new file mode 100644 index 00000000..c815af94 --- /dev/null +++ b/doc/talks/2023-01-18-tocatta/assets/latticeC.svg @@ -0,0 +1,598 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + $\{\}$ + $\{a,b,c\}$ + + $\{a\}$ + $\{b\}$ + $\{c\}$ + + + $\{a,c\}$ + $\{a,b\}$ + $\{b,c\}$ + + + + + + + + + + + + + + + + + + + + $write(\{a\})$: + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\} \to$ OK + $\sqsupseteq \{a\}$ + return OK + return OK + + + + $write(\{b\})$: + $\sqsupseteq \{b\}$ + $\sqsupseteq \{b\} \to$ OK + $\sqsupseteq \{b\} \to$ OK + + diff --git a/doc/talks/2023-01-18-tocatta/talk.pdf b/doc/talks/2023-01-18-tocatta/talk.pdf index ba9bde3d..02f605e8 100644 Binary files a/doc/talks/2023-01-18-tocatta/talk.pdf and b/doc/talks/2023-01-18-tocatta/talk.pdf differ diff --git a/doc/talks/2023-01-18-tocatta/talk.tex b/doc/talks/2023-01-18-tocatta/talk.tex index ac9b4077..e789f597 100644 --- a/doc/talks/2023-01-18-tocatta/talk.tex +++ b/doc/talks/2023-01-18-tocatta/talk.tex @@ -494,8 +494,7 @@ \item \textbf{Linearizability} of all operations\\ (strongest consistency guarantee) \vspace{1em} - \item \textbf{Replicated state machines} that can implement - any sequential specification + \item Any sequential specification can be implemented as a \textbf{replicated state machine} \vspace{1em} \item \textbf{Costly}, the leader is a bottleneck; leader elections on failure take time @@ -515,7 +514,7 @@ \item \textbf{Operations have to commute}, i.e.~we can only implement CRDTs \vspace{1em} - \item \textbf{Fast}, no node is a bottleneck;\\ + \item \textbf{Fast}, no single bottleneck;\\ works the same with offline nodes \end{itemize} } \end{minipage} @@ -530,27 +529,29 @@ \vspace{2em} \hspace{1em} - \begin{minipage}{7cm} + \begin{minipage}{6.5cm} \underline{Consensus-based systems:} \vspace{1em} \textbf{Any sequential specification}\\~ + + \vspace{1em} + \textbf{Easier to program for}: just write your program as if it were sequential on a single machine + \end{minipage} \hfill - \begin{minipage}{7cm} + \begin{minipage}{6.5cm} \underline{Weakly consistent systems:} \vspace{1em} \textbf{CRDTs only}\\(conflict-free replicated data types) + + \vspace{1em} + Part of the complexity is \textbf{reported to the consumer of the API}\\~ \end{minipage} \hspace{1em} - - \vspace{3em} - \begin{center} - Part of the complexity is \textbf{reported to the consumer of the API} - \end{center} \end{frame} \begin{frame} @@ -663,7 +664,27 @@ \end{frame} \begin{frame} - \frametitle{Impact on performances} + \frametitle{Understanding CRDTs and quorums} + \begin{figure} + \centering + \def\svgwidth{.8\textwidth} + \only<1>{\import{assets/}{lattice1.pdf_tex}}% + \only<2>{\import{assets/}{lattice2.pdf_tex}}% + \only<3>{\import{assets/}{lattice3.pdf_tex}}% + \only<4>{\import{assets/}{lattice4.pdf_tex}}% + \only<5>{\import{assets/}{lattice5.pdf_tex}}% + \only<6>{\import{assets/}{lattice6.pdf_tex}}% + \only<7>{\import{assets/}{lattice7.pdf_tex}}% + \only<8>{\import{assets/}{lattice8.pdf_tex}}% + \only<9>{\import{assets/}{lattice9.pdf_tex}}% + \only<10>{\import{assets/}{latticeA.pdf_tex}}% + \only<11>{\import{assets/}{latticeB.pdf_tex}}% + \only<12>{\import{assets/}{latticeC.pdf_tex}}% + \end{figure} +\end{frame} + +\begin{frame} + \frametitle{Performance gains in practice} \begin{center} \includegraphics[width=.8\linewidth]{assets/endpoint-latency-dc.png} \end{center} -- cgit v1.2.3