From 1f5e3aaf8e704ae35a1ccea0f923ce92d4f9ed73 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Thu, 12 Jan 2023 17:39:12 +0100 Subject: Add explanations about quorums --- .../assets/aerogramme_components1.drawio.pdf | Bin 31966 -> 0 bytes .../assets/aerogramme_components2.drawio.pdf | Bin 31688 -> 0 bytes .../assets/aerogramme_datatype.drawio.pdf | Bin 31073 -> 0 bytes .../assets/aerogramme_keys.drawio.pdf | Bin 25145 -> 0 bytes doc/talks/2023-01-18-tocatta/talk.pdf | Bin 2643346 -> 2494390 bytes doc/talks/2023-01-18-tocatta/talk.tex | 91 +++++++++++++++------ 6 files changed, 65 insertions(+), 26 deletions(-) delete mode 100644 doc/talks/2023-01-18-tocatta/assets/aerogramme_components1.drawio.pdf delete mode 100644 doc/talks/2023-01-18-tocatta/assets/aerogramme_components2.drawio.pdf delete mode 100644 doc/talks/2023-01-18-tocatta/assets/aerogramme_datatype.drawio.pdf delete mode 100644 doc/talks/2023-01-18-tocatta/assets/aerogramme_keys.drawio.pdf diff --git a/doc/talks/2023-01-18-tocatta/assets/aerogramme_components1.drawio.pdf b/doc/talks/2023-01-18-tocatta/assets/aerogramme_components1.drawio.pdf deleted file mode 100644 index 71a90f26..00000000 Binary files a/doc/talks/2023-01-18-tocatta/assets/aerogramme_components1.drawio.pdf and /dev/null differ diff --git a/doc/talks/2023-01-18-tocatta/assets/aerogramme_components2.drawio.pdf b/doc/talks/2023-01-18-tocatta/assets/aerogramme_components2.drawio.pdf deleted file mode 100644 index 87e42eed..00000000 Binary files a/doc/talks/2023-01-18-tocatta/assets/aerogramme_components2.drawio.pdf and /dev/null differ diff --git a/doc/talks/2023-01-18-tocatta/assets/aerogramme_datatype.drawio.pdf b/doc/talks/2023-01-18-tocatta/assets/aerogramme_datatype.drawio.pdf deleted file mode 100644 index 0606e059..00000000 Binary files a/doc/talks/2023-01-18-tocatta/assets/aerogramme_datatype.drawio.pdf and /dev/null differ diff --git a/doc/talks/2023-01-18-tocatta/assets/aerogramme_keys.drawio.pdf b/doc/talks/2023-01-18-tocatta/assets/aerogramme_keys.drawio.pdf deleted file mode 100644 index 8fea81c7..00000000 Binary files a/doc/talks/2023-01-18-tocatta/assets/aerogramme_keys.drawio.pdf and /dev/null differ diff --git a/doc/talks/2023-01-18-tocatta/talk.pdf b/doc/talks/2023-01-18-tocatta/talk.pdf index 02f605e8..e4acf75e 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 e789f597..db6d26ef 100644 --- a/doc/talks/2023-01-18-tocatta/talk.tex +++ b/doc/talks/2023-01-18-tocatta/talk.tex @@ -684,20 +684,77 @@ \end{frame} \begin{frame} - \frametitle{Performance gains in practice} - \begin{center} - \includegraphics[width=.8\linewidth]{assets/endpoint-latency-dc.png} - \end{center} + \frametitle{Read-after-write consistency:} + \textbf{Property:} If node $A$ did an operation $write(x)$ and received an OK response,\\ + \hspace{2cm} and node $B$ starts an operation $read()$ after $A$ received OK,\\ + \hspace{2cm} then $B$ will read a value $x' \sqsupseteq x$. + + \vspace{1em} + + \hspace{1em} + \begin{minipage}{6.8cm} + \textbf{Algorithm $write(x)$:} + \begin{enumerate} + \item Broadcast $write(x)$ to all nodes + \item Wait for $k > n/2$ nodes to reply OK + \item Return OK + \end{enumerate} + \end{minipage} + \hfill + \begin{minipage}{6.8cm} + \vspace{1em} + \textbf{Algorithm $read()$:} + \begin{enumerate} + \item Broadcast $read()$ to all nodes + \item Wait for $k > n/2$ nodes to reply\\ + with values $x_1, \dots, x_k$ + \item Return $x_1 \sqcup \dots \sqcup x_k$ + \end{enumerate} + \end{minipage} + \hspace{1em} + + \vspace{2em} + \textbf{Why does it work?} There is at least one node at the intersection between the two sets of nodes that replied to each request, that ``saw'' $x$ before the $read()$ started ($x_i \sqsupseteq x$). +\end{frame} + +\begin{frame} + \frametitle{Monotonical read consistency:} + \textbf{Property:} If node $A$ did an operation $read()$ and received $x$ as a response,\\ + \hspace{2cm} and node $B$ starts an operation $read()$ after $A$ received $x$,\\ + \hspace{2cm} then $B$ will read a value $x' \sqsupseteq x$. + + \vspace{1em} + + \textbf{Algorithm $read()$:} + \begin{enumerate} + \item Broadcast $read()$ to all nodes + \item Wait for $k > n/2$ nodes to reply with values $x_1, \dots, x_k$ + \item If $x_i \ne x_j$ for some nodes $i$ and $j$,\\ + \hspace{1cm}then call $write(x_1 \sqcup \dots \sqcup x_k)$ and wait for OK from $k' > n/2$ nodes + \item Return $x_1 \sqcup \dots \sqcup x_k$ + \end{enumerate} + + \vspace{1em} + This makes reads slower in some cases, and is \textbf{not implemented in Garage}. \end{frame} +\begin{frame} + \frametitle{Performance gains in practice} + \begin{center} + \includegraphics[width=.8\linewidth]{assets/endpoint-latency-dc.png} + \end{center} +\end{frame} \begin{frame} - \frametitle{An ever-increasing compatibility list} - \begin{center} - \includegraphics[width=.7\linewidth]{assets/compatibility.png} - \end{center} + \frametitle{The hard parts we don't address (yet!)} + \begin{itemize} + \item Maintain consistency changes when nodes assigned to a partition change:\\ + \item TODO + \end{itemize} \end{frame} +\section{Going further than the S3 API} + \begin{frame} \frametitle{Further plans for Garage} \begin{center} @@ -728,24 +785,6 @@ \end{center} \end{frame} -\begin{frame} - \frametitle{Aerogramme data model} - \begin{center} - \only<1>{\includegraphics[width=.4\linewidth]{assets/aerogramme_datatype.drawio.pdf}}% - \only<2->{\includegraphics[width=.9\linewidth]{assets/aerogramme_keys.drawio.pdf}\vspace{1em}}% - \end{center} - \visible<3->{Aerogramme encrypts all stored values for privacy\\ - (Garage server administrators can't read your mail)} -\end{frame} - -\begin{frame} - \frametitle{Different deployment scenarios} - \begin{center} - \only<1>{\includegraphics[width=.9\linewidth]{assets/aerogramme_components1.drawio.pdf}}% - \only<2>{\includegraphics[width=.9\linewidth]{assets/aerogramme_components2.drawio.pdf}}% - \end{center} -\end{frame} - \begin{frame} \frametitle{A new model for building resilient software} \begin{itemize} -- cgit v1.2.3