aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAlex Auvolat <alex@adnab.me>2023-01-12 17:39:12 +0100
committerAlex Auvolat <alex@adnab.me>2023-01-12 17:39:12 +0100
commit1f5e3aaf8e704ae35a1ccea0f923ce92d4f9ed73 (patch)
treeac2e7b4560f421c542574781711ebb87e43cddef
parentf5a7bc37365e8e593359db114a4e44f8e8c65207 (diff)
downloadgarage-1f5e3aaf8e704ae35a1ccea0f923ce92d4f9ed73.tar.gz
garage-1f5e3aaf8e704ae35a1ccea0f923ce92d4f9ed73.zip
Add explanations about quorums
-rw-r--r--doc/talks/2023-01-18-tocatta/assets/aerogramme_components1.drawio.pdfbin31966 -> 0 bytes
-rw-r--r--doc/talks/2023-01-18-tocatta/assets/aerogramme_components2.drawio.pdfbin31688 -> 0 bytes
-rw-r--r--doc/talks/2023-01-18-tocatta/assets/aerogramme_datatype.drawio.pdfbin31073 -> 0 bytes
-rw-r--r--doc/talks/2023-01-18-tocatta/assets/aerogramme_keys.drawio.pdfbin25145 -> 0 bytes
-rw-r--r--doc/talks/2023-01-18-tocatta/talk.pdfbin2643346 -> 2494390 bytes
-rw-r--r--doc/talks/2023-01-18-tocatta/talk.tex91
6 files changed, 65 insertions, 26 deletions
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
--- a/doc/talks/2023-01-18-tocatta/assets/aerogramme_components1.drawio.pdf
+++ /dev/null
Binary files 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
--- a/doc/talks/2023-01-18-tocatta/assets/aerogramme_components2.drawio.pdf
+++ /dev/null
Binary files 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
--- a/doc/talks/2023-01-18-tocatta/assets/aerogramme_datatype.drawio.pdf
+++ /dev/null
Binary files 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
--- a/doc/talks/2023-01-18-tocatta/assets/aerogramme_keys.drawio.pdf
+++ /dev/null
Binary files 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
--- a/doc/talks/2023-01-18-tocatta/talk.pdf
+++ b/doc/talks/2023-01-18-tocatta/talk.pdf
Binary files 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}
@@ -729,24 +786,6 @@
\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}
\item Design a data model suited to K2V\\