aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAlex Auvolat <alex@adnab.me>2023-01-13 13:16:55 +0100
committerAlex Auvolat <alex@adnab.me>2023-01-13 13:16:55 +0100
commitd44e8366e7b9ab2ad352ecee189231430ee713df (patch)
treeda57f725192227c65d8b32c4a56b30a1e4e3e503
parentcbb522e17942797ea1f0fd972225b6945a775368 (diff)
downloadgarage-d44e8366e7b9ab2ad352ecee189231430ee713df.tar.gz
garage-d44e8366e7b9ab2ad352ecee189231430ee713df.zip
Reorder and add a hard problem
-rw-r--r--doc/talks/2023-01-18-tocatta/talk.pdfbin2488793 -> 2490671 bytes
-rw-r--r--doc/talks/2023-01-18-tocatta/talk.tex61
2 files changed, 37 insertions, 24 deletions
diff --git a/doc/talks/2023-01-18-tocatta/talk.pdf b/doc/talks/2023-01-18-tocatta/talk.pdf
index 6a70fcd7..3d0c8830 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 4c3e4eeb..09250cf1 100644
--- a/doc/talks/2023-01-18-tocatta/talk.tex
+++ b/doc/talks/2023-01-18-tocatta/talk.tex
@@ -509,7 +509,8 @@
\begin{frame}
\frametitle{Consensus vs weak consistency}
\begin{center}
- \textbf{The same objects cannot be implemented in both models.}
+ \textbf{From a theoretical point of view:}\\
+
\end{center}
\vspace{2em}
@@ -519,11 +520,8 @@
\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
-
+ Require \textbf{additionnal assumptions} such as a fault detector or a strong RNG\\
+ (FLP impossibility theorem)
\end{minipage}
\hfill
\begin{minipage}{6.5cm}
@@ -531,19 +529,20 @@
\vspace{1em}
- \textbf{Limited objects such as CRDTs}\\(conflict-free replicated data types)
-
- \vspace{1em}
- Part of the complexity is \textbf{reported to the consumer of the API}\\~
+ Can be implemented in \textbf{any\\asynchronous message passing\\distributed system} with node crashes
\end{minipage}
\hspace{1em}
+
+ \vspace{3em}
+ \begin{center}
+ They represent \textbf{different classes of computational capability}\\
+ \end{center}
\end{frame}
\begin{frame}
\frametitle{Consensus vs weak consistency}
\begin{center}
- \textbf{From a theoretical point of view:}\\
-
+ \textbf{The same objects cannot be implemented in both models.}
\end{center}
\vspace{2em}
@@ -553,7 +552,11 @@
\vspace{1em}
- Require \textbf{additionnal assumptions} such as a fault detector or a strong RNG\\~
+ \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}{6.5cm}
@@ -561,14 +564,12 @@
\vspace{1em}
- Can be implemented in \textbf{any asynchronous message passing distributed system}
+ \textbf{Only CRDTs}\\(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}
- They represent \textbf{different classes of computational capability}
- \end{center}
\end{frame}
\begin{frame}
@@ -608,7 +609,7 @@
$\to$ the API cannot be implemented in a weakly consistent system
\vspace{2em}
\item \textbf{This API can be implemented using only weak primitives}\\
- (e.g. a bunch of atomic registers)\\
+ (e.g. in the asynchronous message passing model with no further assumption)\\
$\to$ the API is strictly weaker than consensus\\
$\to$ we can implement it in Garage!
\end{itemize}
@@ -625,7 +626,10 @@
\item \textbf{Performance issues:}
\vspace{1em}
\begin{itemize}
- \item The leader is a \textbf{bottleneck} for all requests
+ \item Theoretical requirements (RNG, failure detector) translate into \textbf{practical costs}
+ \vspace{1em}
+ \item The leader is a \textbf{bottleneck} for all requests;\\
+ even in leaderless approaches, \textbf{all nodes must process all operations in order}
\vspace{1em}
\item Particularly \textbf{sensitive to higher latency} between nodes
\end{itemize}
@@ -746,10 +750,19 @@
\end{frame}
\begin{frame}
- \frametitle{The hard parts we don't address (yet!)}
+ \frametitle{A hard problem: layout changes}
\begin{itemize}
- \item Maintain consistency changes when nodes assigned to a partition change:\\
- \item TODO
+ \item We rely on quorums $k > n/2$ within each partition:\\
+ $$n=3,~~~~~~~k\ge 2$$
+ \item When rebalancing, the set of nodes responsible for a partition can change:\\
+ $$\{n_A, n_B, n_C\} \to \{n_A, n_D, n_E\}$$
+ \vspace{.01em}
+ \item During the rebalancing, $D$ and $E$ don't yet have the data,\\
+ ~~~~~~~~~~~~~~~~~~~and $B$ and $C$ want to get rid of the data to free up space\\
+ \vspace{.2em}
+ $\to$ quorums only within the new set of nodes don't work\\
+ $\to$ how to coordinate? \textbf{currently, we don't...}
+
\end{itemize}
\end{frame}