From 0eb0c6de1dd7e9838074a1466f844d06b9cac271 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Wed, 22 Jun 2022 16:31:34 +0200 Subject: checkpoint --- doc/talks/2022-06-23-stack/assets/aerogramme.png | Bin 0 -> 118210 bytes doc/talks/2022-06-23-stack/assets/aerogramme.svg | 445 +++++++++++++++++++++ .../2022-06-23-stack/assets/location-aware.png | Bin 58996 -> 99269 bytes doc/talks/2022-06-23-stack/assets/quentin.jpg | Bin 0 -> 39221 bytes doc/talks/2022-06-23-stack/assets/slideB1.png | Bin 0 -> 86886 bytes doc/talks/2022-06-23-stack/assets/slideB2.png | Bin 0 -> 83399 bytes doc/talks/2022-06-23-stack/assets/slideB3.png | Bin 0 -> 82581 bytes doc/talks/2022-06-23-stack/assets/slidesB.svg | 445 +++++++++++++++++++++ doc/talks/2022-06-23-stack/talk.pdf | 4 +- doc/talks/2022-06-23-stack/talk.tex | 188 ++++++--- 10 files changed, 1023 insertions(+), 59 deletions(-) create mode 100644 doc/talks/2022-06-23-stack/assets/aerogramme.png create mode 100644 doc/talks/2022-06-23-stack/assets/aerogramme.svg create mode 100644 doc/talks/2022-06-23-stack/assets/quentin.jpg create mode 100644 doc/talks/2022-06-23-stack/assets/slideB1.png create mode 100644 doc/talks/2022-06-23-stack/assets/slideB2.png create mode 100644 doc/talks/2022-06-23-stack/assets/slideB3.png create mode 100644 doc/talks/2022-06-23-stack/assets/slidesB.svg diff --git a/doc/talks/2022-06-23-stack/assets/aerogramme.png b/doc/talks/2022-06-23-stack/assets/aerogramme.png new file mode 100644 index 00000000..2e46b5a1 Binary files /dev/null and b/doc/talks/2022-06-23-stack/assets/aerogramme.png differ diff --git a/doc/talks/2022-06-23-stack/assets/aerogramme.svg b/doc/talks/2022-06-23-stack/assets/aerogramme.svg new file mode 100644 index 00000000..cf4b00d6 --- /dev/null +++ b/doc/talks/2022-06-23-stack/assets/aerogramme.svg @@ -0,0 +1,445 @@ + + + +User-facing applicationDatabase*K2VObject storage*(not really a database)Custom user-facing application diff --git a/doc/talks/2022-06-23-stack/assets/location-aware.png b/doc/talks/2022-06-23-stack/assets/location-aware.png index 8b55f253..f5966865 100644 Binary files a/doc/talks/2022-06-23-stack/assets/location-aware.png and b/doc/talks/2022-06-23-stack/assets/location-aware.png differ diff --git a/doc/talks/2022-06-23-stack/assets/quentin.jpg b/doc/talks/2022-06-23-stack/assets/quentin.jpg new file mode 100644 index 00000000..d9a7b1e7 Binary files /dev/null and b/doc/talks/2022-06-23-stack/assets/quentin.jpg differ diff --git a/doc/talks/2022-06-23-stack/assets/slideB1.png b/doc/talks/2022-06-23-stack/assets/slideB1.png new file mode 100644 index 00000000..3eb5d2a1 Binary files /dev/null and b/doc/talks/2022-06-23-stack/assets/slideB1.png differ diff --git a/doc/talks/2022-06-23-stack/assets/slideB2.png b/doc/talks/2022-06-23-stack/assets/slideB2.png new file mode 100644 index 00000000..a881a796 Binary files /dev/null and b/doc/talks/2022-06-23-stack/assets/slideB2.png differ diff --git a/doc/talks/2022-06-23-stack/assets/slideB3.png b/doc/talks/2022-06-23-stack/assets/slideB3.png new file mode 100644 index 00000000..830709d2 Binary files /dev/null and b/doc/talks/2022-06-23-stack/assets/slideB3.png differ diff --git a/doc/talks/2022-06-23-stack/assets/slidesB.svg b/doc/talks/2022-06-23-stack/assets/slidesB.svg new file mode 100644 index 00000000..cf4b00d6 --- /dev/null +++ b/doc/talks/2022-06-23-stack/assets/slidesB.svg @@ -0,0 +1,445 @@ + + + +User-facing applicationDatabase*K2VObject storage*(not really a database)Custom user-facing application diff --git a/doc/talks/2022-06-23-stack/talk.pdf b/doc/talks/2022-06-23-stack/talk.pdf index 048de5dd..bbed3083 100644 --- a/doc/talks/2022-06-23-stack/talk.pdf +++ b/doc/talks/2022-06-23-stack/talk.pdf @@ -1,3 +1,3 @@ version https://git-lfs.github.com/spec/v1 -oid sha256:165fed1968c12fcac02f0735d5ea79e7953feddd0ed71ba77b4e7cbc121f6640 -size 1867699 +oid sha256:ba56e1c3545179cc757cdcb3c15989da24bb400a6d293b5bf252cdc408504976 +size 2237526 diff --git a/doc/talks/2022-06-23-stack/talk.tex b/doc/talks/2022-06-23-stack/talk.tex index a0ffed14..b9e034d4 100644 --- a/doc/talks/2022-06-23-stack/talk.tex +++ b/doc/talks/2022-06-23-stack/talk.tex @@ -9,6 +9,9 @@ \usetheme{boxes} \usepackage{graphicx} %\useoutertheme[footline=authortitle,subsection=false]{miniframes} +%\useoutertheme[footline=authorinstitute,subsection=false]{miniframes} +\useoutertheme{infolines} +\setbeamertemplate{headline}{} \beamertemplatenavigationsymbolsempty @@ -72,9 +75,9 @@ \end{frame} \begin{frame} - \frametitle{How to be resilient (the hard way)} + \frametitle{How to make a \underline{stable} system} - Entreprise-grade systems typically employ: + Enterprise-grade systems typically employ: \vspace{1em} \begin{itemize} \item RAID @@ -88,7 +91,7 @@ \end{frame} \begin{frame} - \frametitle{How to be resilient (the \underline{\textbf{cheap}} way)} + \frametitle{How to make a \underline{resilient} system} \only<1,4-5>{ Instead, we use: @@ -189,92 +192,137 @@ \end{frame} \begin{frame} - \frametitle{What makes Garage different?} - \textbf{Coordination-free:} - \vspace{2em} - \begin{itemize} - \item No Raft or Paxos - \vspace{1em} - \item Internal data types are CRDTs - \vspace{1em} - \item All nodes are equivalent (no master/leader/index node) - \end{itemize} - \vspace{2em} - $\to$ less sensitive to higher latencies between nodes -\end{frame} - -\begin{frame} - \frametitle{Storing and retrieving files} + \frametitle{Garage is \emph{location-aware}} \begin{center} - \only<1>{\includegraphics[width=.5\linewidth]{assets/garage2a.drawio.pdf}}% - \only<2>{\includegraphics[width=.5\linewidth]{assets/garage2b.drawio.pdf}}% + \includegraphics[width=\linewidth]{assets/location-aware.png} \end{center} + \vspace{2em} + Garage replicates data on different zones when possible \end{frame} \begin{frame} - \frametitle{What makes Garage different?} + \frametitle{Garage is \emph{location-aware}} \begin{center} - \includegraphics[width=.9\linewidth]{assets/endpoint-latency-dc.png} + \includegraphics[width=.8\linewidth]{assets/map.png} \end{center} \end{frame} \begin{frame} - \frametitle{What makes Garage different?} - \textbf{Consistency model:} - \vspace{2em} + \frametitle{How to spread files over different cluster nodes?} + \textbf{Consistent hashing (DynamoDB):} + \vspace{1em} + + \begin{center} + \only<1>{\includegraphics[width=.45\columnwidth]{assets/consistent_hashing_1.pdf}}% + \only<2>{\includegraphics[width=.45\columnwidth]{assets/consistent_hashing_2.pdf}}% + \only<3>{\includegraphics[width=.45\columnwidth]{assets/consistent_hashing_3.pdf}}% + \only<4>{\includegraphics[width=.45\columnwidth]{assets/consistent_hashing_4.pdf}}% + \end{center} +\end{frame} + +\begin{frame} + \frametitle{How to spread files over different cluster nodes?} + \textbf{Issues with consistent hashing:} + \vspace{1em} \begin{itemize} - \item Not ACID (not required by S3 spec) / not linearizable + \item Doesn't dispatch data based on geographical location of nodes \vspace{1em} - \item \textbf{Read-after-write consistency}\\ - {\footnotesize (stronger than eventual consistency)} + \item<2-> Geographically aware adaptation, try 1:\\ + data quantities not well balanced between nodes + \vspace{1em} + \item<3-> Geographically aware adaptation, try 2:\\ + too many reshuffles when adding/removing nodes \end{itemize} \end{frame} \begin{frame} - \frametitle{What makes Garage different?} - \textbf{Location-aware:} - \vspace{2em} + \frametitle{How to spread files over different cluster nodes?} + \textbf{Garage's method: build an index table} + \vspace{1em} + + Realization: we can actually precompute an optimal solution + \vspace{1em} + + \visible<2->{ \begin{center} - \includegraphics[width=\linewidth]{assets/location-aware.png} + \begin{tabular}{|l|l|l|l|} + \hline + \textbf{Partition} & \textbf{Node 1} & \textbf{Node 2} & \textbf{Node 3} \\ + \hline + \hline + Partition 0 & Io (jupiter) & Drosera (atuin) & Courgette (neptune) \\ + \hline + Partition 1 & Datura (atuin) & Courgette (neptune) & Io (jupiter) \\ + \hline + Partition 2 & Io(jupiter) & Celeri (neptune) & Drosera (atuin) \\ + \hline + \hspace{1em}$\vdots$ & \hspace{1em}$\vdots$ & \hspace{1em}$\vdots$ & \hspace{1em}$\vdots$ \\ + \hline + Partition 255 & Concombre (neptune) & Io (jupiter) & Drosera (atuin) \\ + \hline + \end{tabular} \end{center} - \vspace{2em} - Garage replicates data on different zones when possible + } + \vspace{1em} + \visible<3->{ + The index table is built centrally using an optimal* algorithm,\\ + then propagated to all nodes\\ + \hfill\footnotesize *not yet optimal but will be soon + } \end{frame} \begin{frame} - \frametitle{What makes Garage different?} - \begin{center} - \includegraphics[width=.8\linewidth]{assets/map.png} - \end{center} + \frametitle{Storing and retrieving files} + \begin{center} + \only<1>{\includegraphics[width=.45\linewidth]{assets/garage2a.drawio.pdf}}% + \only<2>{\includegraphics[width=.45\linewidth]{assets/garage2b.drawio.pdf}}% + \end{center} \end{frame} +\begin{frame} + \frametitle{Garage's internal data structures} + \centering + \includegraphics[width=.75\columnwidth]{assets/garage_tables.pdf} +\end{frame} \begin{frame} \frametitle{Garage's architecture} \begin{center} - \includegraphics[width=.5\linewidth]{assets/garage.drawio.pdf} + \includegraphics[width=.35\linewidth]{assets/garage.drawio.pdf} \end{center} \end{frame} \begin{frame} - \frametitle{Consistent Hashing (DynamoDB)} - \textbf{How to spred files over different cluster nodes?} - \vspace{1em} - - \centering + \frametitle{Garage is \emph{coordination-free}:} + \begin{itemize} + \item No Raft or Paxos + \vspace{1em} + \item Internal data types are CRDTs + \vspace{1em} + \item All nodes are equivalent (no master/leader/index node) + \end{itemize} + \vspace{2em} + $\to$ less sensitive to higher latencies between nodes +\end{frame} - \only<1>{\includegraphics[width=.55\columnwidth]{assets/consistent_hashing_1.pdf}}% - \only<2>{\includegraphics[width=.55\columnwidth]{assets/consistent_hashing_2.pdf}}% - \only<3>{\includegraphics[width=.55\columnwidth]{assets/consistent_hashing_3.pdf}}% - \only<4>{\includegraphics[width=.55\columnwidth]{assets/consistent_hashing_4.pdf}}% +\begin{frame} + \frametitle{Impact on performances} + \begin{center} + \includegraphics[width=.8\linewidth]{assets/endpoint-latency-dc.png} + \end{center} \end{frame} \begin{frame} - \frametitle{Garage data structures: 3 levels of consistent hashing} - \centering - \includegraphics[width=.85\columnwidth]{assets/garage_tables.pdf} + \frametitle{Consistency model} + \begin{itemize} + \item Not ACID (not required by S3 spec) / not linearizable + \vspace{1em} + \item \textbf{Read-after-write consistency}\\ + {\footnotesize (stronger than eventual consistency)} + \end{itemize} \end{frame} + \begin{frame} \frametitle{An ever-increasing compatibility list} \begin{center} @@ -282,6 +330,36 @@ \end{center} \end{frame} +\begin{frame} + \frametitle{Further plans for Garage} + \begin{center} + \only<1>{\includegraphics[width=.8\linewidth]{assets/slideB1.png}}% + \only<2>{\includegraphics[width=.8\linewidth]{assets/slideB2.png}}% + \only<3>{\includegraphics[width=.8\linewidth]{assets/slideB3.png}}% + \end{center} +\end{frame} + +\begin{frame} + \frametitle{K2V Design} + \begin{itemize} + \item A new, custom, minimal API + \vspace{1em} + \item<2-> Exposes the partitoning mechanism of Garage\\ + K2V = partition key / sort key / value (like Dynamo) + \vspace{1em} + \item<3-> Coordination-free, CRDT-friendly (inspired by Riak)\\ + \vspace{1em} + \item<4-> Cryptography-friendly: values are binary blobs + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Application: an e-mail storage server} + \begin{center} + \only<1>{\includegraphics[width=.9\linewidth]{assets/aerogramme.png}}% + \end{center} +\end{frame} + \begin{frame} \frametitle{Get Garage now!} \begin{center} @@ -296,10 +374,6 @@ \end{center} \end{frame} -\begin{frame} - \frametitle{Demo time!} -\end{frame} - \end{document} -%% vim: set ts=4 sw=4 tw=0 noet spelllang=fr : +%% vim: set ts=4 sw=4 tw=0 noet spelllang=en : -- cgit v1.2.3