\documentclass[twocolumn, 10pt, letter]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{inlinebib}
\usepackage{titling}
%\renewcommand{\titlefont}{\begin{center}\small}
\addtolength{\oddsidemargin}{-.3in}
\addtolength{\evensidemargin}{-.3in}
\addtolength{\textwidth}{.4in}
\addtolength{\topmargin}{-.4in}
\addtolength{\textheight}{1.5in}
\title{Efficient Cooperative Caching for YFS}
\author{Raluca Ada Popa and Irene Zhang}
%\date{\today}

\begin{document}
\twocolumn[\begin{center}\LARGE\textbf{\thetitle}\end{center}
\begin{center}\theauthor\end{center}\vspace{10pt}]

\thispagestyle{empty}

\section{Problem Description}
This project solves the problem of the bandwidth bottleneck at the
extent server. In the original YFS implementation, each client asks
the extent server for the data it needs. As the system scales, the
extent server will not be able to handle requests from all the clients
in a timely manner, especially if this data is highly shared. We also
reduce the bottleneck at the lock server.

\section{Design}
The underlying idea of our design is to reduce the load on the extent
server by fetching extents from clients. We use a distributed lock
manager similar to Ivy\footnote{~\cite{li89}}: each client consists of
a lock client and a manager (similar to lock server). Each manager
stores the locks and information on where extents may be found for a
particular set of extent ids. We use a consistent hashing function
\footnote{~\cite{karger97}} to map extent ids to managers and to
balance load. Figure \ref{fig:protocol} illustrates how a client gets
an extent in our system.

\begin{figure}[htp]
  \centering
  \includegraphics[scale=0.5]{protocol.eps}
  \caption{Protocol to acquire a lock and get extent. (1) $C3$ makes
    an acquire request to the manager of the lock, $C2$, as determined
    by the consistent hash function. (2) $C2$ sends a revoke to the
    current owner of the lock, $C1$. (3) $C1$ sends a release to the
    manager, $C2$. (4) The manager sends a grant to $C3$, along with
    information about the last owner of the extent, $C1$. (5) $C3$
    gets the extent from the previous owner of the lock, $C1$.}
  \label{fig:protocol}
\end{figure}

The lock server is now just a metadata server, which tracks the
members in the system. The extent server remains unchanged.

The system transfers locks to a different manager when a client joins
or leaves according to the consistent hashing function. We broadcast
joins and leaves to members in the system. Each time a client cannot
reach another client, it asks for the updated membership at the server
and retries the client.

\section{Implementation}

To implement our system, we rewrote the lock server and lock client so
they can be packaged together and run distributed lock management
using consistent hashing. A new protocol is needed for communicating
with the metadata server. The clients had to be changed to handle
joining and leaving the system (i.e. notifying the metadata server and
broadcasting to the other clients) and the lock servers to handle lock
transfer. We implemented a metadata server, the consistent hashing
library functions and some test code.  Our overall changes are about
$800$ lines of code.

\section{Evaluation}

We evaluated our system using \textit{test lab 4c} and \textit{lock
  tester}. We counted the number of RPC-s at the extent server and
metadata server for the standard YFS (with local extent and lock
caching) and for our cooperatively cached YFS, and found that they are
radically reduced. Table \ref{results} shows our results.

\begin{table}[htp]
  \caption{Number of rpc calls to the extent server, \textit{get}
    and \textit{put}, and the \textit{metadata} server (the lock
    server for YFS) for test lab 4c and lock tester.}
\centering
\vspace{5pt}
\begin{tabular}{ | c | c c  c |   c |}
\hline			
  File  &  & test lab 4c&  & lock tester   \\
 System & get & put & metadata & metadata  \\
\hline
  YFS &392&3&550&42 \\
\hline
  Coop YFS &1&0&9&27\\
\hline  
\end{tabular}
\label{results}
\end{table}

The number of get rpcs are reduced to one in our system because only
the root directory needs to be fetched from the server; all new files
are created in the cooperative cache so no more gets are needed. The
only time puts occur in our system is a flush of the cache when
clients leave. We did not take this into consideration in comparing
our system to YFS because \textit{test lab $4$c} does no flushing. If
we were to consider flushing the data upon leave, the total number of
puts is equal to the total number of extents for both our system and
the original YFS. We implemented periodic flushes at the server (every
$10$s), but they are not triggered in \textit{test lab 4c} because the
period is too long ($10$s). Comparing our metadata server with YFS's
lock server, the metadata server receives a reduced number of rpc-s
because joins, leaves and membership requests are rarer than acquire
and releases.

However, note that \textit{test lab 4c} and \textit{lock tester} test
the system when client membership is static. In a system with churn,
the number of joins and leaves (and thus gets and puts) increase, but
we believe these should still be significantly less than the original
YFS, especially in systems with low churn.


%\bibliography{write-up}{}
%\bibliographystyle{inlinebib}


\end{document}