diff options
Diffstat (limited to 'usenix2019.tex')
| -rw-r--r-- | usenix2019.tex | 324 |
1 files changed, 324 insertions, 0 deletions
diff --git a/usenix2019.tex b/usenix2019.tex new file mode 100644 index 0000000..34557a4 --- /dev/null +++ b/usenix2019.tex @@ -0,0 +1,324 @@ +% TEMPLATE for Usenix papers, specifically to meet requirements of +% USENIX '05 +% originally a template for producing IEEE-format articles using LaTeX. +% written by Matthew Ward, CS Department, Worcester Polytechnic Institute. +% adapted by David Beazley for his excellent SWIG paper in Proceedings, +% Tcl 96 +% turned into a smartass generic template by De Clarke, with thanks to +% both the above pioneers +% use at your own risk. Complaints to /dev/null. +% make it two column with no page numbering, default is 10 point + +% Munged by Fred Douglis <douglis@research.att.com> 10/97 to separate +% the .sty file from the LaTeX source template, so that people can +% more easily include the .sty file into an existing document. Also +% changed to more closely follow the style guidelines as represented +% by the Word sample file. + +% Note that since 2010, USENIX does not require endnotes. If you want +% foot of page notes, don't include the endnotes package in the +% usepackage command, below. + +% This version uses the latex2e styles, not the very ancient 2.09 stuff. +\documentclass[letterpaper,twocolumn,10pt]{article} +% \usepackage{usenix2019,epsfig,endnotes} +\usepackage{usenix2019,epsfig} + +\begin{document} + +%don't want date printed +\date{} + +%make title bold and 14 pt font (Latex default is non-bold, 16 pt) +\title{\Large \bf bcachefs : A next generation filesystem } + +%for single author (just remove % characters) +\author{ +{\rm Kent Overstreet}\\ +\and +{\rm Second Name}\\ +Second Institution +% copy the following lines to add more authors +% \and +% {\rm Name}\\ +%Name Institution +} % end author + +\maketitle + +% Use the following at camera-ready time to suppress page numbers. +% Comment it out when you first submit the paper for review. +\thispagestyle{empty} + + +\subsection*{Abstract} + +bcachefs is a new b-tree based, CoW local POSIX filesystem for Linux. Here we +describe the background, status, and an overview of the key design elements. + +\section{Introduction} + +\subsection{What is bcachefs?} + +bcachefs is a full featured POSIX filesystem, with a featureset aimed at +competing with ZFS, btrfs and xfs. Existing features include: + +\begin{itemize} + \item Copy on Write + \item Full data checksumming + \item Compression + \item Encryption (AEAD style encryption using ChaCha20 and Poly1305) + \item Multi-device + \item Replication + \item Online grow/shrink and add/remove of devices, and a completely + flexible data layout + \item Tiering/caching (both writethrough and writeback; IO stack is in + fact policy driven now) +\end{itemize} +Upcoming features: +\begin{itemize} + \item Erasure coding (Reed-Solomon, with ability to add others) + \item Snapshotting +\end{itemize} + +\subsection{Status} + +bcachefs is in outside use by a small community of early adopters and testers, +and likely soon in a production capacity as well. Upstreaming is hopefully +imminent as there are no blockers left on the bcachefs side. + +\section{What makes bcachefs interesting?} + +\begin{itemize} + \item The design is a major departure from existing filesystems. In + particular it is constructed more as a layer on top of a generic + key-value store, with much more consistent handling of metadata + and on disk data structures. + \item This simplification is possible because we have a very + sophisticated and scalable b-tree implementation, which has been + under development for nearly 10 years now, inherited from + bcache. +\end{itemize} + +\section{bcachefs design novelties} + +\begin{itemize} + \item Auxiliary search tree for searching within a btree node + +\end{itemize} + + + +\section{bcachefs design fetaures} + +\subsection{Filesystem as RDBMS} + +In bcachefs, all metadata is organized into a small number of "btree" - +effectively tables: + +\begin{itemize} + \item Inodes table + \item Extents table + \item Dirents table + \item Xattrs table + \item etc. +\end{itemize} + +This is a major departure from most existing filesystems, where most data +structures hang off of the inodes. This isn't an unreasonable way to do things - +it's an effective way to shard most data structures and historically, those data +structures weren't particularly scalable so you really wanted that sharding +(i.e. block based filesystems that used the double/triple indirect block +scheme). + +But bcachefs's history meant that we started out with a btree implementation +scalable enough that we no longer needed that sharding - bcache uses a single +btree for indexing every cached extent, regardless of the number of volumes +being cached (and a cached volume in bcache is equivalent to a file in +bcachefs). + +This means we have a single unified, iterator based API for manipulating +essentially all filesystem data (everything not stored in the superblock), and +that metadata is all in a single flat namespace. + +This is a huge win for the complexity of the filesystem code itself. Rename, for +example, is just a couple of operations on keys in the dirents btree, done +atomically in a single update operation - drastically simpler than most other +filesystems. + +Even better, we don't need complex logging to make high level filesystem +operations like create, link and rename atomic. Instead, they make heavy use of +the btree's ability to use multiple iterators simultaneously, and then the final +update is done by passing a list of (iterator, new key) pairs to the btree +update path - for atomicity, all that is required is that the btree update path +use the same journal reservation for all the updates to be done. + +This make journalling and in particular journal replay drastically simpler than +on other contemporary filesystems. + + + + + + +A paragraph of text goes here. Lots of text. Plenty of interesting +text. \\ + +% More fascinating text. Features\endnote{Remember to use endnotes, not footnotes!} galore, plethora of promises.\\ + +\section{This is Another Section} + +Some embedded literal typset code might +look like the following : + +{\tt \small +\begin{verbatim} +int wrap_fact(ClientData clientData, + Tcl_Interp *interp, + int argc, char *argv[]) { + int result; + int arg0; + if (argc != 2) { + interp->result = "wrong # args"; + return TCL_ERROR; + } + arg0 = atoi(argv[1]); + result = fact(arg0); + sprintf(interp->result,"%d",result); + return TCL_OK; +} +\end{verbatim} +} + +Now we're going to cite somebody. Watch for the cite tag. +Here it comes~\cite{Chaum1981,Diffie1976}. The tilde character (\~{}) +in the source means a non-breaking space. This way, your reference will +always be attached to the word that preceded it, instead of going to the +next line. + +\section{This Section has SubSections} +\subsection{First SubSection} + +Here's a typical figure reference. The figure is centered at the +top of the column. It's scaled. It's explicitly placed. You'll +have to tweak the numbers to get what you want.\\ + +% you can also use the wonderful epsfig package... +\begin{figure}[t] +\begin{center} +\begin{picture}(300,150)(0,200) +\put(-15,-30){\special{psfile = fig1.ps hscale = 50 vscale = 50}} +\end{picture}\\ +\end{center} +\caption{Wonderful Flowchart} +\end{figure} + +This text came after the figure, so we'll casually refer to Figure 1 +as we go on our merry way. + +\subsection{New Subsection} + +It can get tricky typesetting Tcl and C code in LaTeX because they share +a lot of mystical feelings about certain magic characters. You +will have to do a lot of escaping to typeset curly braces and percent +signs, for example, like this: +``The {\tt \%module} directive +sets the name of the initialization function. This is optional, but is +recommended if building a Tcl 7.5 module. +Everything inside the {\tt \%\{, \%\}} +block is copied directly into the output. allowing the inclusion of +header files and additional C code." \\ + +Sometimes you want to really call attention to a piece of text. You +can center it in the column like this: +\begin{center} +{\tt \_1008e614\_Vector\_p} +\end{center} +and people will really notice it.\\ + +\noindent +The noindent at the start of this paragraph makes it clear that it's +a continuation of the preceding text, not a new para in its own right. + + +Now this is an ingenious way to get a forced space. +{\tt Real~$*$} and {\tt double~$*$} are equivalent. + +Now here is another way to call attention to a line of code, but instead +of centering it, we noindent and bold it.\\ + +\noindent +{\bf \tt size\_t : fread ptr size nobj stream } \\ + +And here we have made an indented para like a definition tag (dt) +in HTML. You don't need a surrounding list macro pair. +\begin{itemize} +\item[] {\tt fread} reads from {\tt stream} into the array {\tt ptr} at +most {\tt nobj} objects of size {\tt size}. {\tt fread} returns +the number of objects read. +\end{itemize} +This concludes the definitions tag. + +\subsection{How to Build Your Paper} + +You have to run {\tt latex} once to prepare your references for +munging. Then run {\tt bibtex} to build your bibliography metadata. +Then run {\tt latex} twice to ensure all references have been resolved. +If your source file is called {\tt usenixTemplate.tex} and your {\tt + bibtex} file is called {\tt usenixTemplate.bib}, here's what you do: +{\tt \small +\begin{verbatim} +latex usenixTemplate +bibtex usenixTemplate +latex usenixTemplate +latex usenixTemplate +\end{verbatim} +} + + +\subsection{Last SubSection} + +Well, it's getting boring isn't it. This is the last subsection +before we wrap it up. + +\section{Acknowledgments} + +A polite author always includes acknowledgments. Thank everyone, +especially those who funded the work. + +\section{Availability} + +It's great when this section says that MyWonderfulApp is free software, +available via anonymous FTP from + +\begin{center} +{\tt ftp.site.dom/pub/myname/Wonderful}\\ +\end{center} + +Also, it's even greater when you can write that information is also +available on the Wonderful homepage at + +\begin{center} +{\tt http://www.site.dom/\~{}myname/SWIG} +\end{center} + +Now we get serious and fill in those references. Remember you will +have to run latex twice on the document in order to resolve those +cite tags you met earlier. This is where they get resolved. +We've preserved some real ones in addition to the template-speak. +After the bibliography you are DONE. + +{\footnotesize \bibliographystyle{acm} +\bibliography{../common/bibliography}} + + +% \theendnotes + +\end{document} + + + + + + + |