Modelling and Managing SSD Write-amplification
\alignauthor Niv Dayan
\affaddr{IT University of Copenhagen
How stable is the performance of your flash-based Solid State Drives (SSDs)? This question is central for database designers and administrators, cloud service providers, and SSD constructors. The answer depends on write-amplification, i.e., garbage collection overhead. More specifically, the answer depends on how write-amplification evolves in time. %It has been shown that write-amplification depends on application workload as well as SSD internals (over-provisioning, space allocation and garbage collection). How then can one model and manage write-amplification, especially when application workloads change? This is the focus of this paper. Managing write-amplification boils down to managing the surplus physical space, called over-provisioned space. Modern SSDs essentially separate the physical space into several partitions, based on the update frequency of the pages they contain, and divide the over-provisioned space among the groups so as to minimize write-amplification. We introduce Wolf, a block manager that allocates over-provisioned space to SSD partitions using a near-optimal closed-form expression, based on the sizes and update frequencies of groups of pages. Our evaluation shows that Wolf is robust to workloads change, with an improvement factor of 2 with respect to the state-of-the-art. We also show that Wolf performs comparably and even slightly better than the state of the art with stable workloads (over 20$\%$ improvement with a TPC-C workload).
00_abstract.tex
\begin{abstract}

How stable is the performance of your flash-based Solid State Drives (SSDs)? This question is central for database designers and administrators, cloud service providers, and SSD constructors. The answer depends on write-amplification, i.e., garbage collection overhead. More specifically, the answer depends on how write-amplification evolves in time. 
%It has been shown that write-amplification depends on application workload as well as SSD internals (over-provisioning, space allocation and garbage collection). 

How then can one model and manage write-amplification, especially when application workloads change? This is the focus of this paper. Managing write-amplification boils down to managing the surplus physical space, called over-provisioned space. Modern SSDs essentially separate the physical space into several partitions, based on the update frequency of the pages they contain, and divide the over-provisioned space among the groups so as to minimize write-amplification. We introduce Wolf, a block manager that allocates over-provisioned space to SSD partitions using a near-optimal closed-form expression, based on the sizes and update frequencies of groups of pages. Our evaluation shows that Wolf is robust to workloads change, with an improvement factor of 2 with respect to the state-of-the-art. We also show that Wolf performs comparably and even slightly better than the state of the art with stable workloads (over 20$\%$ improvement with a TPC-C workload). 

\end{abstract}

01_introduction.tex

\section{Introduction} % (fold)
\label{sec:introduction}

Solid State Drives (SSDs), based on flash chips, are now the secondary storage
of choice for data intensive applications. Database
systems can now rely on high performance SSDs to store log, indexes and data either on servers or in the cloud.
While SSDs provide increasingly high performance out of the box, 
maintaining high throughput and low latency as the utilization of SSDs increases and despite abrupt changes in the workload remains a challenge. 

On flash chips, data is organized into pages, each of which typically comprises tens of kilobytes of data. Pages reside in erase blocks. 
Before a page is updated, the underlying block must be erased. A software layer called the 
Flash Translation Layer (FTL) manages these constraints by updating pages out-of-place. 
To enable out-of-place updates, SSDs are given {\em over-provisioned} space: a portion 
of the physical storage space which is not exposed to applications, but used by the FTL to accommodate 
the before-images of pages. Eventually,  garbage-collection operations are required to reclaim 
space occupied by before-images. Garbage-collection operations migrate live pages from victim blocks
(to be erased) to other blocks. The flash operations generated by the garbage collector interfere
with application IOs. Such interferences cause 
reduced throughput and variable latency. 
For instance, the NTOSort\footnote{\url{http://sortbenchmark.org/NTOSort2013.pdf}},
with top results in the JouleSort
benchmark, exhibits high variability
for the 1TB sort, when the Samsung 840 Pro SSDs are highly utilized.

The extent of this overhead is captured by {\em write-amplification}, which is the ratio between the number of physical writes that occur inside an SSD to the number of logical writes issued by the application. A way to reduce write-amplification is to increase {\em over-provisioning}\footnote{Other ways to
reduce write-amplification include compression and deduplication. Both of these
methods reduce the volume of data that needs to be stored on SSD, at the cost of
increased CPU utilization. They are orthogonal (and can be combined) with our
proposed contribution.}. Both SSD constructors and application designers tune 
over-provisioning to trade storage capacity for performance
(see for example the note on how over-provisioning is used to maximize lifetime and performance for the Samsung 840 Pro SSDs\footnote{\url{http://www.samsung.com/global/business/semi
conductor/minisite/SSD/global/html/about/whitepaper05.html}}).

There is a direct relationship between write-amplification and over-provisioning. A
greater amount of over-provisioned space reduces the average number of live pages per block, and thus the average
number of pages that need to be migrated when a block is garbage-collected. 
%But how precisely, does write-amplification evolve in time when SSD utilization increases and as the workload changes? This is still an open issue and a major concern for experimentation and benchmarking with SSDs~\cite{uflip}.

There is also a relationship between write-amplification and the internals of the FTL. 
It has been shown~\cite{stoica} that a way to reduce write-amplification
is to design a block manager, within the FTL, that writes
hot and cold pages on separate flash blocks, thereby essentially partitioning
the SSD into several groups based on the update frequency of the pages they contain. Designing a block manager
that manages data placement across such SSD partitions is still problematic though: 

\begin{itemize}

\item Existing block managers exhibit pathological behaviors when certain types
of changes in the application workloads occur. In the context of a database 
system, examples of such abrupt changes include offline 
index maintenance (which essentially forces database writes 
to swap back and forth between data pages and index pages), 
checkpointing (where writes switch between log and data pages), 
or external algorithms (that force large volumes of writes to
temporary space). Moreover, in cloud
environments SSDs store various databases with different workload
characteristics subject to abrupt changes in the
workload \cite{spikes}.
We show that when a group of pages abruptly changes
temperature, existing FTLs exhibit an elongated period of exceptionally high
write-amplification as over-provisioned space is slow to move among groups.

\item Existing block managers do not adapt well to realistic workloads like TPC-C. 
The reason is that existing methods make assumptions about the relative temperatures 
of pages in different groups, which may be inaccurate. The allocation of over-provisioned 
space based on such assumptions is sub-optimal. 

\item There is no closed-form method for allocating over-provisioned space to different 
groups. Existing methods are either mathematically  complex or based on hill-climbing algorithms, which are computationally
expensive. 

\end{itemize}

%With the advent of open-channel SSDs~\cite{sdf14}, designing a FTL is no longer a problem for 
%the companies that provide SSD controllers alone. Open-channel SSDs are flash-based SSDs that do not embed a FTL. 
%They directly expose internal flash commands to the host: read and write at the page level,
%and erase at the block level. The FTL is provided by the host. It can be customized to the need
%of a given workload. It is thus now possible for system programmers 
%to write custom block managers, well suited for database workloads. 

In this paper, our contribution is twofold:
\begin{enumerate}
\item We derive a mathematical expression that relates over-provisioning to write-amplification under a uniform workload. 
%We also 	study the evolution of write-amplification over time. We derive a simple procedure for bringing SSDs to a well-defined state before benchmarking them. 	Such a procedure could benefit industry benchmarks. 
\item We introduce a new block manager to address the aforementioned problems, called Wolf, or \textbf{Wo}rkload \textbf{L}eveller for \textbf{F}lash. Wolf is able to detect and quickly adapt to changes in workload by pro-actively reallocating over-provisioned space among the groups based on their changing needs. It adapts better to stable workloads by measuring the update frequencies of	groups instead of making assumptions about them. It uses a novel  near-optimal closed-form expression to allocate over-provisioned space to groups.
\end{enumerate}

The rest of the paper is organized as follows. Section 2 explores related work. 
Section 3 introduces a system model for the
analysis, as well as the simulator we later use. Section 4 simplifies an
existing analysis of the relationship between over-provisioning and write-amplification 
with uniform workload, and analyses the behavior of 
garbage-collection efficiency over time in this context. In section 5,  we introduce
Wolf, a new block manager design that adapts better to realistic workloads,
especially ones that dynamically change over time. 
%HERE
%In particular, we give a 
%closed-form expression for how to assign over-provisioned space to
%different groups based on update frequency in a k-modal workload. 
%END
We describe our evaluation of Wolf in Section 6 and conclude in section 7.

02_relwork.tex

\section{Related Work} % (fold)
\label{sec:related_work}

We discuss existing work focused on modelling write amplification, and managing
it in the context of a FTL design.

\subsection{Modelling Write-Amplification}

There have been many efforts to relate write-amplification and over-provisioning.
Hu et al.~\cite{write-amp} and Agrawal et al.~\cite{closed} developed
probabilistic models for write-amplification, but they do not fit simulation
results well for all values of over-provisioning. Haas et al.~\cite{limit}
proposed a model for write-amplification that is directly fitted from simulation
results. Bux et al.~\cite{bux} developed two complementary theoretical models
for write-amplification, but they do not give a closed-form expression.

In 2012-2013, several papers~\cite{improved, Desnoyers, stoica} gave an equation
that relates over-provisioning to write-amplification in terms of the Lambert w
function. Stoica et al.~\cite{stoica} even simplified this expression into one
that does not rely on the Lambert w function. The model presented in these works
fits simulation results nicely when the workload is stable and has been running
for a while.

In this paper, we derive a simpler closed-form equation that relates over-provisioning 
to write-amplification. 
%We also examine how write-amplification evolves in time and how long it takes it to converge.

%In relation to these works, our contribution is fourfold: 

%\begin{itemize}
%\item In terms of modelling the uniform workload, we derive a new expression that related the ratio between the logical and physical address spaces to the average number of pages migrated per garbage-collection operation on average. It is of interest because it is simpler in form and derivation than the expressions given in \cite{improved, Desnoyers, stoica} which serve the same function. We also show mathematically that our expression is essentially equivalent to the expressions used in \cite{improved, Desnoyers, stoica}. Thus, it is just as accurate.
%\item We study how cleaning efficiency evolves as we reach equilibrium. We give mathematically-grounded rules of thumb for the amount of time it takes to reach equilibrium from different initial states. This is useful to ensure repeatable experiments on SSDs starting from a known state. 
%\item It has been shown that the greedy policy's performance is superior to LRU yet converges to LRU as the We show that when the workload changes, the greedy cleaning policy outperforms the LRU policy significantly. We give a mathematical explanation for this and provide simulation results. 
%\item In terms of a grouped workload, we give the first closed-form expression for how much over-provisioned space to allocate to each group. We show that it is near-optimal well for a vast number of workload configurations, and describe the kinds of workloads under which its accuracy starts to degrade. 
%\end{itemize}

\subsection{Managing Write-Amplification} \label{sec:prev_work_managing}

In the design of the Log-Structured File System \cite{log-fs}, the authors
noticed that when writing a stream of logical random writes sequentially in the
physical address space, one can reduce cleaning costs by physically clustering
together logical addresses with the same update frequency. Several works
utilize this idea for flash in order to minimize write-amplification.

Envy \cite{envy} proposed separating the physical space into equally-sized
groups of erase blocks. Pages are migrated to a hotter or colder group based on
their temperatures with the overall goal of equalizing the groups' cleaning
costs, defined as the average cost of cleaning a block multiplied by the
frequency of cleaning operations. DAC \cite{dac} also partitions the physical
space into equally sized groups, but the migration policies are different. A
page is promoted to a hotter group when it is updated and only if the update
distance to the last update is relatively short. On the other hand, a page is
demoted to a colder group during cleaning. ContainerMarking \cite{container} 
partitions the physical space in finer-grained groups, and promotes pages on 
updates and demotes pages based on a statistical model.

%\cite{adaptive} proposed balancing cold and hot pages across the parallel
%\architecture of the SSD in order to avoid workload imbalances among LUNs.

% \cite{ffs} examined different cleaning policies, including one that combines
% \the goals of wear-levelling and cleaning.
 
Recently, Stoica et al.~\cite{stoica} proposed a scheme, that we denote Frequency-based
Data Placement (FDP) in the rest of the paper, whereby the number and
sizes of groups adapt to the workload. In FDP, cleaning is performed independently in
each group using a least-recently-cleaned (LRU) policy. Several methods are
proposed for allocating over-provisioned space to the different groups in order 
to minimize overall write-amplification, yet no closed-form is given. FDP outperforms 
existing FTL designs theoretically and under realistic workloads.

In this work, we propose Wolf, which improves on FDP~\cite{stoica} in several ways. It
adapts better to realistic workloads since the update frequencies of groups are
continuously measured and adapted. It avoids pathological behabiors that FDP is subject to when application workloads change. It uses a greedy cleaning policy in groups, as we identified
scenarios in which the LRU policy is suboptimal. Finally, it uses a simple
closed-from expression to decide how to allocate over-provisioned space to the
different groups.

%In relation to these works, our contribution is threefold:

%\begin{itemize}
%\item We give a way to map the notion of groups of flexible sizes to a parallel SSD architecture. 
%\item We give a block manager that allows groups to better adapt to changes in the workload.
%\end{itemize}
03_sysmodel.tex

\section{System Model} % (fold)
\label{sec:system_model}

We rely on the following SSD model throughout this paper.
There are $B$ pages in a block, and $K$ blocks
in the SSD. The SSD is partitioned into a number of logical units called LUNs,
on which flash operations can occur in parallel. Several LUNs are connected to
the SSD controller through channels. Communication between the controller and
the LUNs through the channel is serial.

The size of the logical address space in pages is $LBA$, and the number of physical
pages is $PBA$. The amount of pages for over-provisioned 
space is $OP = PBA - LBA$. Over-provisioning is captured by the ratio $LBA/PBA$.  The notations used for the analysis 
are summarized in Table \ref{tab:notations}. 

\begin{table}[t]
\begin{center} 
    \begin{tabular}{ | l | p{6cm} |} 
    \hline
    \textbf{Notation} & \textbf{Description} \\ \hline
    $B$ & Number of pages in a flash block  \\ \hline
    $\delta$ & The fraction of pages in a flash block that are on average migrated in one garbage collection operation \\ \hline
    $LBA$ & Logical address space size in flash pages \\ \hline
    $PBA$ & Physical address space size in flash pages \\ \hline
    $OP$ & The number of over-provisioned flash pages. Note that $OP = PBA - LBA $ \\ \hline
    $K$ & The number of blocks in the SSD. Note that $K = \frac{PBA}{B}$ \\ \hline
    \end{tabular}
\end{center}
\caption{System Model}   
\label{tab:notations}
\end{table}

We assume the FTL uses a page-level mapping scheme to handle out-of-place
updates. This means there are LBA mapping entries, and when a page is updated,
the physical address corresponding to the page's logical address is changed.
The mapping table is either stored in the host's RAM or on flash
memory \cite{dftl}. 
%Such FTLs have been shown to dominate block-mapping schemes such as \cite{fast}.

In our baseline block manager, a page update is written to some non-busy LUN
that has a block with free pages. As the LUN runs out of blocks with free
space, cleaning operations are triggered on it to clear space for new writes.
Garbage-collection works independently for each LUN. It selects a victim,
migrates any live pages to other blocks (which may be on other LUNs), and
finally erases the block. The block is then returned to the pool of free
blocks for that LUN.

The garbage-collection policy within a LUN can be {\em LRU} or {\em greedy}.  The LRU
policy targets the block that was erased the longest time ago. The greedy
policy keeps track of the number of live pages in each block and targets the
block with the least number of live pages. 

We use the SSD simulator EagleTree \cite{EagleTree} to validate analytical
results and evaluate system designs. EagleTree is an open-source and
extensible simulation framework for the entire IO stack running in virtual
time. We used the above-mentioned policies and the default parameters in table
\ref{tab:sim-parameters} for all simulations unless otherwise mentioned\footnote{The default
settings result in an SSD of 16GB. We show throughout the paper that increasing 
SSD capacity (i.e., the number of channels, the number of LUN per channels, the 
number of blocks per LUN or page size) either has no impact on our analysis, or
that it actually amplifies the benefits of our approach. This setting is thus conservative
and it allows us to conduct a thorough exploration of the design space in simulation.}. We
implemented Wolf on top of the existing simulator, 
available on Github\footnote{\url{https://github.com/ClydeProjects/EagleTree}}.

\begin{table}[t]
\begin{center}  
    \begin{tabular}{ | l | p{2,5cm} |} 
    \hline
    \textbf{Parameter} & \textbf{Default Value} \\ \hline
    Channels & 4  \\ \hline
    LUNs per channel & 2  \\ \hline
    Blocks per LUN & 1024 \\ \hline
    Pages per block (B) & 128 \\ \hline
        Page size & 16 KB \\ \hline
    LBA / PBA & $70\%$ \\ \hline
    \end{tabular}
\end{center}
\caption{Default simulation parameters}
\label{tab:sim-parameters} 
\end{table}

% section system_model (end)
04_WAandOP.tex

\section{Write-Amplification} % (fold)
\label{sec:write_amplification_for_uniform_workloads}

We now examine the relationship between over provisioning and write-amplification. 
We focus on a uniformly distributed random workload, where an application write targets any logical address with an equal probability. 

%Write-amplification under the uniform workload eventually converges to an equilibrium state whereby each cleaning operation involves on average the same number of page migrations. Reaching this equilibrium state is key to ensure the reproducibility of experiments involving an SSD. Otherwise, write-amplification may vary during an experiment and make it difficult to control. 

%In~\cite{uflip}, Bouganim et al. discussed the impact of SSD initialization on experimental results. They proposed to write the entire logical address space over with random writes without repetition in order to bring a SSD in a stable state where the effects of write-amplifications are perceived by applications. This was a heuristic and there was no characterization of the state reached at the end of the initialization procedure. We address these shortcomings in the rest of this section.

\subsection{The lifetime of a block}\label{sec:block-lifetime}

As a first step, we model the lifetime of a block. Suppose we have just finished writing a block. 
How many pages G do we expect to remain valid after X application 
writes\footnote{We assume that LBA is much bigger than B, which means the likelihood 
that a page in the block was invalidated before we finished writing the block is negligible. 
Thus, we assume all pages in this block are initially valid.}? 

Since the workload is uniform, the probability that any page update targets some page in the block is $\frac{B}{LBA}$. Thus, the number of page updates before some page is invalidated in B is geometrically distributed with mean $\frac{LBA}{B}$. In other words, $\frac{LBA}{B}$ page updates occur on average before the first page in the block is invalidated. After this event, there are $B-1$ live pages in the block. Analogously, the expected number of page updates before the next page in the block is invalidated is $\frac{LBA}{B-1}$. The third page is invalidated after an expected number of $\frac{LBA}{B-2}$ writes, and so on. The expected number of page updates until there are no live pages in the SSD can be simplified using Euler's approximation for the sum of the harmonic series up to n elements, where $\gamma$ is the Euler-Mascheroni constant.

$$
\frac{LBA}{B} + \frac{LBA}{B-1} + ... + \frac{LBA}{1} = LBA \sum_{i=1}^{B}\frac{1}{i} = LBA ( \ln(B) + \gamma )
$$

More generally, suppose that after X updates there are on average $G$ live pages left in the block. It is easy to see that:
 
\begin{equation} \label{eq1}
\begin{split}
X & = LBA \sum_{i=1}^{B}\frac{1}{i} - LBA \sum_{i=1}^{G}\frac{1}{i} \\
& = LBA ( \ln(B) + \gamma ) - LBA ( \ln(G) + \gamma ) \\
& = LBA \ln(B/G)
\end{split}
\end{equation} 

Expressed in terms of G, we get: 

\begin{equation} \label{eq:how_long_til_equib}
\begin{split}
G = B \cdot e^{-X/LBA}
\end{split}
\end{equation} 

\subsection{Equilibrium}\label{sec:unif_equib}

%HERE
%Write-amplification under the uniform workload eventually converges to an equilibrium state whereby each cleaning operation involves on average the same number of page migrations. 
%END
We now study the relationship between over-provisioning ($LBA/PBA$) and the average fraction of migrations per cleaning operation ($\delta$). 

%The relationship between cleaning efficiency and over-provisioning under equilibrium for the uniform workload has been studied and captured in closed form expressions \cite{closed, Radu, Desnoyers}. However, it turns out that we can use equation \ref{eq1} to derive an alternative expression that is simpler in form and derivation. This is not one of the main contributions of the paper, but it is a useful opportunity to render an existing analysis simpler and more accessible. 

We start by asking a simple question: what is the expected number of cleaning operations throughout the SSD between two times that the same block is cleaned? Under the LRU policy, the number is K by definition. Under the greedy policy, the number is K on average. 

%Let's consider the LRU policy first and then the greedy policy. Consider a block that has just been cleaned and rewritten. By definition of how LRU works, every other block in the SSD will be chosen as a victim of garbage collection before this block is cleaned again. Since there are K blocks in the SSD, K garbage-collection operations happen between two times that the same block is cleaned. The lifetime of a block under the greedy policy is similar. Every block in the system has been written before the block in question, and since the rate of page invalidation across blocks is identical, on average every block in the system will be cleaned before the block of interest will be cleaned again. 

Let us now ask how many application page updates are expected between two times the same block is cleaned. By the assumption of being in equilibrium, each cleaning operation involves $B \cdot \delta$ migrations. Conversely, each cleaning operation clears space for $B \cdot (1 - \delta)$ new application writes. Since K blocks are cleaned on average between two times that the same block is cleaned, and since each of them accommodates for $B \cdot (1 - \delta)$ application writes, then $K \cdot B \cdot (1-\delta)$ page updates occur on average 
%HERE
% j'aime pas ce qui est dessous - style mais bon, j'ai pas trouv� mieux
before two times that the same block is garbage-collected. We substitute this expression for X in equation \ref{eq1}. 
%END

$$
LBA \cdot \ln(\frac{B}{B \cdot \delta}) = K \cdot B \cdot (1-\delta) \\
$$

Plugging in $\frac{PBA}{B}$ for K, simplifying and rearranging, we get: 

\begin{equation} \label{eq:eq_6}
\frac{LBA}{PBA} = \frac{\delta - 1}{\ln(\delta)}
\end{equation} 

We can relate $\delta$ to write-amplification using the equation $WA = 1/(1 - \delta)$. This is a characterization of write-amplification at equilibrium.

Figure \ref{fig:verif} plots equation \ref{eq:eq_6}. In appendix \ref{App:AppendixA}, we show how to express equation \ref{eq:eq_6} in terms of $\delta$. By so doing, we also show that this equation is in fact equivalent to the findings of previous analyses provided in \cite{closed,stoica,Desnoyers}. The interesting part of our analysis is that the derivation and form of the equation are simpler. 

%Obviously, the equilibrium state is based on the system model assumptions from Section 3. The internal logic of traditional SSDs incurs undocumented complexity, that will introduce a discrepancy between actual device state and the equilibrium state we model here. Exploring the performance of a range of actual devices around the predicted equilibrium state is an important topic for future work.

\begin{figure}
\includegraphics[scale=0.25]{overprov-graph.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{ How $LBA / PBA$ affects $\delta$ (left axis) and write amplification (right axis) in equilibrium, assuming a uniform workload. }
\label{fig:verif}
\end{figure}

%\subsubsection{Greedy vs. LRU - may remove this}

%The analysis so far suggests that garbage-collection efficiency is independent of whether we use the greedy or LRU policy. Indeed, \cite{Radu} showed that the difference between these policies is negligible. To verify this, we ran a workload consisting of $50\%$ page writes and $50\%$ page reads on our simulated SSD using each of the policies. The average number of migrations per garbage-collection operation was $59.3$ and $61.1$ for the greedy and LRU policies respectively. Throughput in terms of application IOs was indistinguishable. 
%3255 and 3255 IOs/s for the greedy and LRU policies respectively. 

%While the greedy and LRU policies give the same average number of migrations per garbage-collection operation, the variance of the number of migrations varies dramatically between them as shown in figures \ref{fig:greedy_equib} and \ref{fig:LRU_equib}. In our experiment, the standard deviation number of migrations per cleaning operation were 4.7 and 2.3 for the LRU and greedy policies respectively. An interesting question is if the greater latency variability of the LRU policy leads to more throughput or latency variability for the application. Our experiments show that this is typically not the case. In our experiment, standard deviation for reads and writes with the greedy policy was 5898 and 8744 microseconds respectively, and 5972 and 8954 microseconds for the LRU policy. The greedy policy has slightly less variability, but this can also be accounted for by the fact there are $1.5\%$ less migrations and erases for the greedy policy. 

%\subsection{Reaching Equilibrium}\label{sec:unif_equib}

%\subsubsection{Blank SSD}\label{sec:unif_blank}

%We first  consider a blank SSD on which nothing has so far been written. Suppose we run the uniform  workload on it. We focus on the following question: after how many random application page writes does write-amplification converges to equilibrium? 

%In the last subsection, we saw that the equilibrium rate of write-amplification depends on the ratio between the number of live pages in the SSD and PBA, the total physical capacity. Thus, the time it takes to reach equilibrium can be approximated by the expected number of random writes it takes until the logical address space is fully written. We can approximate this using the classical coupons' collector problem in probability theory.
 
%We just saw that write-amplification depends on $Q / PBA$, where $Q \le LBA$. Let us define L as the number of live pages written on the SSD. When the SSD is blank, L is 0. It grows with every page write to a logical address that has never been written before. For any value of L, (with $L <= LBA$), the probability that the next page update targets a new logical address is $(LBA - L)/LBA$, which on average takes $LBA/(LBA - L)$ application writes. Summing this up for L from 0 to LBA - 1, we get the following\footnote{Again, we use the approximate sum of the harmonic series up to n elements. Note that we omit the Euler-Mascheroni constant for simplicity because we are dealing with approximations and the value of the constant in this case is negligible.}: 

%\begin{equation} \label{eq:equib_blank}
%\sum_{L=0}^{LBA - 1} (LBA/(LBA - L) \approx LBA \cdot %\ln(LBA)
%\end{equation}

%The above formula gives the expected number of application writes until $L = LBA$, at which point write-amplification is stable. However, it is a conservative estimation. At the start, there is an extremely large probability that page writes target new addresses, and this probability gradually decreases as more pages are written. This means most pages are written at the beginning. In practice, a sufficient upper bound on the number of page writes until write-amplification converges is $\frac{LBA \ln(LBA)}{2}$  (after this number of writes, there are on average $LBA - \sqrt{LBA}$ pages written, which is close enough to LBA.) 

%We validated this using EagleTree by applying a uniform workload to a blank SSD with different over-provisioning values and different internal garbage-collection policies. Figure \ref{fig:equilib1} presents the evolution of write-amplification from a blank initial state when random writes are  applied uniformly. This is done for different over-provisioning values (0.7, 0.8 and 0.9) and cleaning policies (greedy, LRU). Write-amplification begins to take place after approximately PBA writes (approximately 1 million in this case). At this point, the amount of free space in the SSD is almost exhausted and  garbage-collection kicks in. The black dots on the figure mark the equilibrium predicted by equation \ref{eq:equib_blank}. They verify that the equation  accurately predicts equilibrium. Note also that the greedy policy slightly outperforms the LRU policy, but the difference is minor. 

%\begin{figure}
%\includegraphics[scale=0.25]{reaching-equilibrium/graph.eps}
%\captionsetup{margin=10pt,font=small,labelfont=bf}
%\caption{The evolution of write-amplification due to random writes from a blank initial state, for different values of $LBA/PBA$ and cleaning policies. The black dots show where equilibrium is predicted to have been reached by equation %\ref{eq:equib_blank} . }
%\label{fig:equilib1}
%\end{figure}

%Assuming that X unique live pages have been written, the probability that an update writes a new page is geometrically distributed with probability $\frac{LBA-X}/{LBA}$, and it takes on average $\frac{LBA}/{LBA-X}$ page updates before it is written. Now, let $E_x$ to the the expected number of writes before there are x live pages in the SSD assuming we start from a blank SSD. It is easy to see that:

%\begin{equation} \label{eq:equib}
%\begin{split}
%E_x & = \frac{LBA}{LBA} + \frac{LBA}{LBA-1} + ... + %\frac{LBA}{LBA-X+1} \\
%& = LBA \sum_{i=X}^{LBA} \frac{1}{i} \\
%& \approx LBA (\ln(LBA) + \gamma)
%\end{split}
%\end{equation} 

%\subsubsection{The logical address is written out}\label{sec:unif_seq}

%Now consider a non-blank SSD in an arbitrary state, the only constraint being that the entire logical address space is fully written. Assuming we then apply the uniform workload, how long does it take to reach equilibrium?

%To reason about this, let's characterize the state of all blocks in equilibrium. In equilibrium, the distribution of remaining live pages in each block is a function of x, where x is the number of writes that has taken place since the block was last rewritten. The most recently rewritten block has a distribution $F(0)$ and the oldest still active block has $F(k(B-GC))$. All other blocks have distributions in-between at intervals of $B-GC$. 

%Now suppose every block is erased once from the time we start applying the uniform workload. 

%If each block is cleaned at least once due to regular garbage-collection from the time we started applying the uniform workload, this turns out to be precisely the state we reach. The amount of writes it takes all blocks to eventually be erased actually varies with the over-provisioning factor, as different amounts of migrations are triggered. An upper bound that works for all over-provisioning values, however, is to just issue a number of random updates equivalent to the physical size of the SSD, that is PBA writes. This is validated in the next subsection. 

%\subsubsection{Full SSD}\label{sec:equib_written}

%We now suppose that the logical space exposed by the SSD is fully written once, either by a sequential write over the entire logical address space or by random writes without repetition. The default block manager from section \ref{sec:system_model} fills up $LBA/B$ blocks with live pages whereas $OP/B$ blocks remain empty. We then apply the uniform workload. How does write-amplification evolve in time, and how long does it take for it to converge?

%In Figure \ref{fig:LRU_greed_equib}, we trace the evolution of write-amplification for the same over-provisioning values and garbage-collection policies than in Figure 2, but with a different initial condition. Now, the SSD is full, while the SSD was blank in Figure 2. The green, blue and red dots in Figure 3 correspond to the number of writes that are necessary to write the the entire logical address space once (obviously the size of the logical address space increases as the ratio between LBA and PBA increases).

%We observe that the behaviors of the greedy and LRU policies in Figure \ref{fig:LRU_greed_equib} are different. The LRU policy entails more migrations and steeper fluctuations. The reason is that the $LBA/B$ blocks that are initially filled have the same expected number of live pages, since they have all undergone the same number of random writes since they were written. Thus, the LRU policy's underlying assumption, that the block written the longest time ago has the fewest number of live pages, does not hold. It is thus less effective than the greedy policy. Previous works compared the LRU and greedy policies only under equilibrium. Here, we observe a situation outside of equilibrium where the greedy policy significantly outperforms the LRU policy. We exploit this later in the design of Wolf. 

%While the equilibrium state is the same in Figure 2 and 3, it takes around 3 times longer to reach it in Figure 2 than in Figure 3. This is a useful observation for experiment tractability, since writing the entire capacity of a large SSD to reach equilibrium for an experiment can take a significant amount of time. We use it in the next sub-section.

%\subsection{SSD Initialization} % (fold)
%\label{sub:ssd_initialization}

%Figure 3 shows that it is not sufficient to write a SSD over with random writes without repetition to bring it to equilibrium as suggested in~\cite{uflip}. To devise a sufficient condition, we need to answer the following question: How many random writes should be applied to a full SSD to reach equilibrium? 

%Expression \ref{eq:equib_written} is a rule of thumb that predicts the number of random writes needed before reaching equilibrium once the SSD's logical address space has been written over exactly once without repetition. It is derived in Appendix 2, where we also provide a mathematical model that accounts for the fluctuations in Figure \ref{fig:LRU_greed_equib}.  

%\begin{equation} \label{eq:equib_written}
%OP + 2 \cdot PBA \cdot (1 - \delta)
%\end{equation}

%\begin{figure}
%\includegraphics[scale=0.25]{equib-unif/graph.eps}
%\captionsetup{margin=10pt,font=small,labelfont=bf}
%\caption{The evolution of write-amplification due to random writes from an initial state where the logical space is sequentially written. This is done for different values of $LBA/PBA$ and cleaning policies. The black dots show where equilibrium is predicted to have been reached by equation \ref{eq:equib_written}. The colored dots indicate where the initializing sequential writes stop and the random writes begin for the lines of the corresponding colors.}
%\label{fig:LRU_greed_equib}
%\end{figure}

%This result gives us a simple means to bring an SSD at equilibrium. First, the SSD should be written over exactly once without repetition (e.g., with sequential writes). Second, equation~\ref{eq:equib_written} gives us the number of random writes that should be applied, from this state, to reach equilibrium. This number depends on the over-provisioning (OP), the size of the physical address space (PBA), and $\delta$ (from Figure~\ref{fig:verif} or Equation~\ref{eq:eq_6}). Such a procedure could become a requirement for SSD initialization in industry benchmarks, e.g., from the TPC or for the sort benchmarks, or in any effort to design reproducible experiments with SSD-based systems.

% subsection ssd_initialization (end)






%A good rule of thumb is that whenever the physical address space is fully written, write-amplification converges after PBA application writes from the time we start applying the uniform workload. The reason is that after PBA random writes every block in the system is very likely to have been cleaned  and overwritten at least once. We do not try to prove this proposition formally, but instead we refer to a verifying simulation result in figure \ref{fig:LRU_greed_equib}. Write-amplification converges after approximately 1 million writes (20 intervals) from when random writes start (the dotted line). This is roughly the size of the physical address space. 

%In the last subsection, we saw that if the logical address is fully written out, it takes at most PBA random application writes to reach equilibrium. This is validated in figure \ref{fig:LRU_greed_equib}, where equilibrium is reached after approximately 1 million writes, the size of the physical address space in pages. We also observe that once equilibrium is reached the average number of migrations per cleaning operation was $59.3$ and $61.1$ for the greedy and LRU policies respectively.

%We notice two additional interesting aspects in figure \ref{fig:LRU_greed_equib}. Before reaching equilibrium, the behaviors of the greedy and LRU policies are different. The LRU policy entails more migrations and steeper fluctuations over time. LRU performs poorly because its heuristic is ineffective at this situation because the active blocks have the same distribution of live pages. Previous works compared the LRU and greedy policies only under equilibrium. Here, we see that under some situations when we are outside of equilibrium, the greedy policy significantly outperforms the LRU policy. We will exploit this later in our design of a workload adaptive block manager. 

%The other interesting aspect in figure \ref{fig:LRU_greed_equib}. Observe that for both policies, there is a fluctuation in cleaning efficiency. We can explain it using our analysis. In equilibrium, we anticipate around 60 migrations per block erase given our default architecture. The peak for the curves, however, occurs after OP writes when garbage-collection kicks. At this point, all candidates for garbage-collection have an equal distribution of live pages. By plugging OP for X in equation \ref{eq:how_long_til_equib}, we see that after OP writes (314572 in this case) there are on average 83.4 live pages per block. Thus, garbage-collection is much worse than during equilibrium. The reason for the subsequent trough is that many more application writes could take place and invalidate pages during the first erase cycle during equilibrium, where $K \cdot B \cdot \delta$ application writes occur in one erase cycle. This is since the first OP writes did not involve any garbage-collection overheads. 




%Suppose the active blocks in the system are in a set called $set_{init}$. These blocks are all completely packed with live pages and have the same distribution of live pages F(0). We suppose all other (free) blocks are in set $set_{equib}$, and that when a block in set $set_{init}$ is cleaned, it moves to set $set_{equib}$. Equilibrium is reached once set $set_{init}$ is empty. 

%In order to compare the LRU and greedy cleaning policies, observe that the distribution of live pages for all the blocks in $set_{init}$ remains the same until the set is empty. Because the distribution of live pages is identical, the block with the minimum number of pages has significantly less valid pages than the average block in $set_{init}$. The greedy policy is able to target this block each time, whereas the LRU policy picks a random block from $set_{init}$. We were unable to quantify the difference analytically, but we ran an experiment comparing the LRU and greedy policies in this scenario until equilibrium is reached. In the simulation, the difference between the number of migrations until reaching equilibrium for the two policies divided by the size of the logical address space for normalization was $6.3\%$. This may not seem like a big difference, but it does illustrate a point that has been neglected in all previous works. The LRU and greedy policy may have nearly indistinguishable performance during equilibrium, but while we are outside equilibrium and there is a group of blocks with an identical distribution of live pages, the greedy policy outperforms the LRU policy. As we will later see, this insight turns out to be important when the workload changes. 

%879819 migrations and 14327 erases took place for the greedy policy whereas 926328 migrations and 14690 erases took place for the LRU policy. 

%Also note that:

%\begin{equation} 
%\begin{split}
%s_1 + s_2 + ... + s_n & = LBA \\
%OP_1 + OP_2 + ... + OP_n & = OP \\
%LBA + OP & = PBA
%\end{split}
%\end{equation} 



05_Wolf.tex
\section{Wolf: Workload Leveller for Flash} \label{sec:wolf}

We have seen how write-amplification is linked to over-provisioning for random writes uniformly distributed across the whole SSD.  Now consider that the logical address space is partitioned into $n$ groups denoted as $g_1, g_2, ... , g_n$, that each group has a different size $s_1, s_2, ... , s_n$ measured in flash pages, and that each group may have a different update frequency $p_x$ defined as the probability that an incoming application update targets a page in group x. 

Previous works \cite{envy, dac, container, stoica} have shown that storing pages with different update frequencies in different groups of physical blocks leads to reduced write-amplification in this context. Existing approaches thus conceptually partition the SSD into n virtual SSDs. 

The problem is then to allocate the over-provisioned space across virtual SSDs in a way that minimizes write amplification. Existing solutions do not always adapt well to realistic workloads, and they exhibit poor performance under certain types of workload changes that are typical of database workloads. In this Section, we introduce Wolf, a block manager designed to deal with these issues. 

But first, let us describe the problems of existing approaches in more detail. We base our study on the block manager from Stoica et al.~\cite{stoica}, that we denote {\em FDP}, which has been shown to dominate the state-of-the-art. The groups in this scheme have a fixed order, and it is assumed that the $i$th group contains hotter pages than the $(i-1)$th group. A page is promoted/demoted to a hotter/colder group on an update/migration if it is deemed too hot/cold relative to the other pages in its group.

Problems arise if the update frequency of a group abruptly changes. The essential problem is that over provisioned space is slow to move among groups, which leads to a potentially long period of suboptimal write-amplification. 

For example, Figure~\ref{fig:mass_migrations_prob} (in Section 6) illustrates a scenario using FDP where we initially have two groups $g_{cold}$ and $g_{hot}$ where $s_{cold} = s_{hot}$, $p_{cold} = 10\%$ and $p_{hot} = 90\%$. At some point, the update frequencies of the groups are abruptly swapped. Pages in $g_{cold}$ are now hot and flow into $g_{hot}$ very quickly as they are updated. On the other hand, pages originally in $g_{hot}$ are now cold, and they reside in blocks that occupy a lot of over-provisioned space. Ideally, these pages should be quickly demoted and compacted into $g_{cold}$ in order to free the underlying over-provisioned space, so that it can now benefit the pages that turned hot. However, there is no mechanism to do this quickly. The over-provisioned space is only freed as the original blocks in $g_{hot}$ are cleaned, and the amount of time this takes depends on the garbage-collection policy. Indeed, in figure~\ref{fig:mass_migrations_prob}, write-amplification after the temperature swap is slow to converge again. 

The question we ask is thus the following: how can we facilitate a speedy reallocation of over-provisioned space among groups in order to minimize overall write-amplification as fast as possible? 

The scheme we propose, Wolf, addresses these concerns. It is able to quickly detect changes in workload and quickly move over-provisioned space among groups in response. A key design principle is that when a change in workload occurs, physical space rather than logical pages (as in existing schemes), should move among groups. Wolf is different from existing schemes in the following ways. 

It continuously records run-time statistics about the sizes and update frequencies of groups. These statistics serve three purposes. (1) They allow adjusting the relative ordering of groups as the workload changes. (2) They allow determining when it is worthwhile creating or merging groups as the workload changes. (3) They serve a reliable input to determine how to reallocate the over-provisioned space among groups as the workload changes. 

Wolf uses a novel near-optimal closed-form method to compute how to allocate over-provisioned space among the groups. Compared to existing methods, the closed-form method constitutes a good compromise between cheapness, accuracy and simplicity. 

Wolf continually identifies groups with excess over-provisioned space relative to the optimum, compacting pages in those groups on fewer physical blocks, and donating the redeemed blocks to groups with a deficit of over-provisioned space. This is achieved through \textit{movement operations}. Within a group, Wolf uses the greedy garbage-collection policy since our analysis showed that it significantly outperforms the LRU policy under certain workload changes.

We first describe the key data structures and skeleton subroutines of Wolf. We then describe its novel aspects in more detail.

%Note that Wolf exploits the parallelism of SSDs and is compatible with existing wear-leveling strategies, as addressed in sections \ref{sec:Garbage-Collection-and-Parallelism} and \ref{sec:wear-leveling} respectively. 

\subsection{Algorithm Outline and Key Data Structures}

Wolf's skeleton is structured around three key subroutines, and the notion of intervals of application writes. The first subroutine handles write operations and updates statistics about each group within an interval. The second subroutine handles the completion of an interval. In this subroutine, updated statistics about groups' sizes and update frequencies are used to (1) re-sort the relative order of group, (2) consider whether or not to create or merge groups, (3) recompute the optimal allocation of over-provisioned space among groups, and (4) consider moving over-provisioned space among groups. The third subroutine handles an erase operation. It assigns a redeemed block to a group with an over-provisioned space deficit, and considers triggering more over-provisioning reallocation operations. We now explain these subroutines in more detail. %The key data structures are in table \ref{tab:wolf_notations}.

%\begin{table}[t]
%\begin{center} 
%    \begin{tabular}{ | l | p{6cm} |} 
%    \hline
%    \textbf{Notation} & \textbf{Description} \\ \hline
%    $BGM$ & blocks to groups mapping \\ \hline
%    $SGV$ & Sorted groups vector \\ \hline
%    $MT$ & Orthogonal mapping table between the logical and physical address spaces \\ \hline
%    $TD$ & Temperature Detector \\ \hline
%    $GROUPS$ & vector of metadata about groups indexed by group id \\ \hline    
%    $h$ & size of an interval, measured in a number of application writes. \\ \hline
%    \end{tabular}
%\end{center}
%\caption{System Model}   
%\label{tab:wolf_notations}
%\end{table}

Listing \ref{lst:writes} shows how writes are handled. When a write arrives, we determine which group it currently belongs to by (1) looking up the corresponding physical address in the usual logical to physical mapping table (orthogonal to Wolf), and then (2) consulting a data structure called the \textit{Blocks to Groups Map (BGM)}, which keeps track of which physical blocks belong to which group. Now that we know the page's current group, we consult a temperature detector module (TD) to determine if the page should remain in its current group or be demoted/promoted to a colder/hotter group. When we have a target group on which to write the page, we find a free page in the group and execute the write. Finally, we update statistics about the sizes of groups and the number of writes targeting the groups per interval. The routine concludes by checking if the target group is nearly out of free pages, in which case garbage-collection is invoked within it. Non-trivial parts of all subroutines are marked in red and described in more details in later sections. 

\lstset{morekeywords={MT,BGM, TD, flash, GROUPS, SGV}}
\lstset{emph={write},emphstyle=\textit}
\lstset{emph={find_target, garbage_collect},emphstyle=\textcolor{red}}

\begin{lstlisting}[frame=single, numbers=left,caption={ handle write},breaklines=true,label={lst:writes},columns=fullflexible]
  input: write
  logi_addr = write.logi_addr
  phys_addr = MT[logi_addr]
  block_id = phys_addr.block_id
  group_id = BGM[block_id]
  curr_group = GROUPS[group_id]
  new_group_id = TD.find_target(group_id, logi_addr) 
  new_group = GROUPS[new_group_id]
  new_phys_addr = new_group.find_free_addr()
  write.new_phys_addr = new_phys_addr
  flash.schedule(write)
  curr_group.size--
  new_group.size++
  if (write is not a garbage-collection operation)
      new_group.interval_writes++
  if (new_group.num_free_pages < B)
      new_group.garbage_collect()
\end{lstlisting}

In principle, the length of an interval, denoted as $h$, captures a trade-off between responsiveness to changes in workload and the computational expense of subroutine \ref{lst:interval}. Fortunately, subroutine \ref{lst:interval} is not expensive since the component that would usually be expensive in it, namely the method for recomputing the allocation of over-provisioned space, is non-iterative and therefore extremely cheap. Thus, we can set $h$ to be small (in our implementation $h = LBA \cdot 0.001$\footnote{The parameters we define in this Section remained fixed throughout the experiments presented in Section 6. In this paper, we do not present a thorough exploration of the performance impact of these tuning parameters. This is a topic for future work.}) 

Let us now describe subroutine \ref{lst:interval}. In lines 2 and 3, each group's update frequency is updated based on the proportion of writes that targeted that group within the interval that finished. Note that $a$ is a constant that controls the weighting of a group's long-run measured update frequency versus the update frequency in the interval that just finished (we set $a$ to $h \cdot 3$). In line 4, the allocation of over-provisioned space for a group is recomputed. 

In line 7, we sort a data structure called the \textit{Sorted Groups Vector (SGV)} based on updated statistics. This data structure maintains the relative order of groups based on the notion of \textbf{hit rate}, which we define for group $g_x$ as $p_x / s_x$, its update frequency over its size. As we will later see, this structure is used by the temperature detector, and by the policy that decides whether to create or merge groups. In lines 8 and 9, we trigger routines that consider creating or merging existing groups, and whether or not to start reallocating over-provisioned space among group.

\lstset{emph={allocate_over_prov, merge_or_create_groups, consider_movement_operations},emphstyle=\textcolor{red}}

\begin{lstlisting}[frame=single, numbers=left,caption={ handle interval completion},breaklines=true,label={lst:interval},columns=fullflexible]
  for (group x in GROUPS) {
     U = group.interval_writes / h
     p_x = p_x * (1 - a) + a * U
     group.over_prov = allocate_over_prov(p_x, s_x)
     group.interval_writes = 0
  }
  SGV = sort_by_hit_rate(GROUPS) 
  merge_or_create_groups()
  consider_movement_operations()
\end{lstlisting}


The last subroutine of Wolf handles erase operations. It identifies the group with the greatest over-provisioning deficiency and assigns the erased block to it. After this, we consider reallocating more over-provisioned space by triggering additional movement operations. 

\begin{lstlisting}[frame=single, numbers=left,caption={ erase},breaklines=true,label={lst:erase},columns=fullflexible]  
  flash.schedule(erase)  
  find group x that maximizes (s_x, OP_x)
  block_id = erase.block_id
  BGM[block_id] = group.id
  consider_movement_operations()
\end{lstlisting}

With Wolf's skeleton in mind, let us reiterate why it adapts better to changes in workload. Firstly, Wolf detects changes in workload through statistics. It is highly responsive to changes in workload since intervals are short. As groups change in update frequency relative to each other, their order is re-sorted, and the allocation of over-provisioned space among them is recomputed and pro-actively adjusted. This is in sharp contrast to existing schemes, whereby the ordering of groups is fixed, and write-amplification is controlled by moving pages among the groups, as opposed to by moving over-provisioned space among them.

An additional advantage of Wolf over existing schemes is that its statistics provide a more accurate input to the over-provisioning allocation strategy. FDP makes assumptions about the update frequencies of the groups based on their relative order, but does not measure them. Thus, Wolf is able to adjust better to a stable workload.

The next sections explain non-trivial parts of Wolf, marked in red in the above subroutines. In section \ref{sec:Dynamic_Group_Management}, we describe the policy for creating and merging groups. In section \ref{sec:Over-provisioning_Redistribution}, we describe the policy for reallocating over-provisioned space among groups using \textit{movement operations}. In section \ref{sec:cleaning_within_groups}, we discuss the garbage-collection policy within groups, and in section \ref{sec:overprob_alloc} we describe the novel closed-form method for a near-optimal allocation of over-provisioned space among groups. Finally, in sections \ref{sec:temp_det}, \ref{sec:Garbage-Collection-and-Parallelism} and \ref{sec:wear-leveling}, we discuss compatibility with orthogonal concerns of temperature detection, parallelism and wear-levelling respectively.

\subsection{Groups Creation And Merging Policies} \label{sec:Dynamic_Group_Management}

%In Wolf, a measure $p_x$ is maintained for every group $g_x$ indicating its update frequency. The accuracy of this measure is important, as it is used as input to the over-provisioning allocation strategy in the previous section. Thus, $p_x$ should be adapted quickly as the workload changes. To do so, we count the fraction of updates targeting group $g_x$ within intervals of updates to the SSD. The length of an interval is a small fraction of the logical address space given by $h \cdot LBA$ (in our implementation $h = 0.001$\footnote{The parameters we define in this Section remained fixed throughout the experiments presented in Section 6. In this paper, we do not present a thorough exploration of the performance impact of these tuning parameters. This is a topic for future work.}). At the end of an interval, the fraction of updates U that targeted group $g_x$ is added to $p_x$ with some weighting controlled by parameter a (in our implementation $a = 3 \cdot h$):

%\begin{equation} \label{eq:time_equib_seq}
%p_x  = p_x \cdot (1 - a) + U \cdot a
%\end{equation}

%Note that the factor $a$ is the proportion of the size of the interval of the logical address space, multiplied by $z$, a constant set to determine how much weight to give the count in the recent interval. The greater it is, the faster $p_x$ adapts to changes in the update frequency of the group, but at the less importance we give to the long-run average, which may be harmful if there are irregularities in the workload over time. We set $z$ to 3 in our implementation. Note also that at the end of each interval, the hit rates of the groups may have changed, so we make a pass over the sorted array and sort it if necessary. 

Let us describe the policy for creating or merging groups invoked in subroutine \ref{lst:interval}. Wolf is initialized with a minimum of two groups. A page that is written for the first time is always assigned to the coldest group. A hotter additional group is created when the following conditions hold: (1) the group with the highest hit rate in SGV must have at least F pages, and (2) the ratio between the hit-rates of the two hottest groups in SGV must be at least Q. Rule 1 is meant to avoid the creation of an excessive number of very small groups, and rule 2 is meant to ensure that the creation of a new group is motivated by a real temperature skew in the workload. 

We set the constant F in rule (1) to be the number of LUNs in the SSD multiplied by the number of pages in a block. Thus, each group has at least one block in each LUN. This ensures natural load balancing across the parallel architecture of the SSD.

An implication of rule (2) is that the hit rate of groups increases exponentially for a stable workload. Indeed, \cite{stoica} showed analytically that the update frequency ratio among pages in the same group may vary by up to 2 without incurring any significant penalty. Thus, we set the constant Q in rule (2) to two. Note that the exponential increase in the hit rates of groups means we can handle very skewed workloads with relatively few groups. 

When a new hot group is created, it takes time for pages to flow into it and for its long-term update frequency $p_x$ to adjust and stabilize. We give it time by fixing its position in the SGV as well as banning the creation or merging of any additional hot group for the next w intervals ($w = 50$ in our implementation). 

If the update frequency of two adjacent groups in SGV diverges and the hotter one is hotter by a factor of more than $Q \cdot 2$, we create a new empty group in the middle, again fixing its location for w intervals to allow it to stabilize. 

If two adjacent groups in SGV converge in terms of hit rate for over $w$ intervals, they are merged. Moreover, if the number of pages in a group drops below F, we merge the group with one of its adjacent groups in SGV. Note that a merge is logical, as it only involves consolidating the metadata about the groups.  

The implication of our groups' creation and merging policy is that when a workload is highly skewed, the number of groups would tend to oscillate. This is indeed what we observe with a TPC-C workload in section \ref{sec:realistic}. 

This policy improves on FDP in the sense that FDP does not have a policy for merging groups, or to control that the creation of a new group is motivated by a genuine skew in the workload as opposed to randomness. Thus, the number of groups in FDP tend to grow over time. 

%We observed that the existence of many groups harms garbage-collection efficiency. In figure \ref{fig:groups_gc}, we ran an experiment where we vary the number of groups from 1 to 100. Each group has an identical update frequency and size. This shows the impact of increasing the number of groups without a change in workload. In average, the spare block is completely free while the current block is half full. The amount of reserved free space cannot be used to store invalid pages, so it effectively decreases the amount of over-provisioning across the SSD by 1.5 blocks per group. As shown, as the number of groups increases, garbage-collection performance becomes poorer because each group claims a small amount of over-provisioned space for its free blocks. The expected line was derived by subtracting 1.5 multiplied by the number of groups from the amount of over-provisioned space, and solving for $\delta$ using equation \ref{eq1}. The lesson from this is that the number of groups is subject to an optimization problem based also on the workload. We mustn’t create more groups than necessary.

%\begin{figure} 
%\includegraphics[scale=0.25]{num-groups-gc/graph.eps}
%\label{fig:verif}
%\caption{ Impact on garbage-collection efficiency as the number of groups increases. In this experiment, groups are identical in terms of size and update frequency. }
%\label{fig:groups_gc}
%\end{figure}

\subsection{Movement Operations}\label{sec:Over-provisioning_Redistribution}

In both subroutines \ref{lst:interval} and \ref{lst:erase}, a procedure is called to consider reallocating physical space among the groups. It work by scanning the metadata for each groups. It identifies groups that have a block-surplus relative to the dictated amount of over-provisioned space the group should have. It then triggers garbage-collection operations within such groups. The redeemed blocks are donated to groups with a block-deficiency relative to the dictated allocation, as shown in subroutine \ref{lst:erase}.

%Let us first introduce a few terms. We say a group has a \textit{block-deficiency} or \textit{block-surplus} if it has too few or too many blocks respectively relative to the amount dictated by the closed-form method of section \ref{sec:overprob_alloc}. We say a group is in equilibrium if it is within Z blocks of the optimal. We set Z to the number of LUNS, so as to allow in principle plus/minus 1 block in each LUN. A group may become block-deficient as its size or update frequency increases.

%As far as the authors are aware, such a mechanism has not been described anywhere before. This is because many existing schemes assume fixed-sized groups, such that only pages can move among groups, but the number of physical blocks per group is always the same. As we saw in the problem definition, when groups have a flexible size, over-provisioned space moves too slowly or not at all if we wait for normal garbage-collectors collect the blocks. There is an urgent need for a more proactive block redistribution policy.

There is an interesting cost-benefit question regarding how greedily to trigger movement operations. On the one hand, movement operations constitute a clear cost in terms of migrations. On the other hand, movement operations are an investment in future performance, as they help reducing the overall write-amplification. Thus, an interesting question is how rapidly to issue movement operations. We investigated different strategies of pacing movement operations, but found that issuing movement operations as greedily as possible with no restrictions always minimized the overall number of migrations. This indicates that the investment in movement operations is always worthwhile.

In contrast to Wolf, in FDP a group may only be donated blocks from the two groups adjacent to it, namely the next colder and next hotter groups. This restricts the adaptivity of the scheme to changes in workload, as a block may need to cross multiple groups to reach its target. In contrast, Wolf has the flexibility of being able to move blocks between any groups.

%within a group to only occur  the pacing of movement operations influences performance by comparing the following 3 policies.

%\begin{enumerate}
%\item \textbf{1/1 Policy}: at most 1 movement operation can be issued for every cleaning operation in a group. 
%\item \textbf{3/1 Policy}: at most 3 movement operations can be issued for every cleaning operation in a group. 
%\item \textbf{$\infty / 1$ Policy}: movement operations are issued as rapidly as possible. 
%\end{enumerate}

%We tested each policy under 3 workloads. In all workloads, there are two groups with update frequencies of $90\%$ and $10\%$. These groups' update frequencies are swapped after $LBA/2$, $LBA$ and $2 LBA$ updates respectively. Thus, blocks must move from one group to the other, and the different policies control the rate of the transfer. Note that when periodicity is $LBA/2$, none of the policies actually has enough time to transfer all blocks before the next swap, so blocks are moved constantly to and fro. In Figure~\ref{fig:redist}, we see that the greedier the policy is, the less migrations take place. This indicates that the savings in garbage-collection that we get by moving blocks more than offset the cost of the movement operations, so the investment is always worthwhile. We use the $\infty / 1$ policy in all subsequent experiments. 

%\begin{figure} 
%\includegraphics[scale=0.25]{redistribution-policy/graph.eps}
%\captionsetup{margin=10pt,font=small,labelfont=bf}
%\caption{ Comparing 3 policies for triggering movement operations.}
%\label{fig:redist}
%\end{figure}

\subsection{Cleaning Policy within a Group}\label{sec:cleaning_within_groups}

A garbage-collection operation is triggered in a group when it has less than B free pages. The question we now address is how to choose a victim block. We compare two policies: LRU and greedy.

Previous work~\cite{stoica} showed that the difference between the greedy and LRU policies in equilibrium is not great (though it does increase slightly for higher values of $LBA / PBA$). As LRU is simpler to implement, state-of-the-art FTLs such as FDP~\cite{stoica} use the LRU policy. However, the heuristic of the LRU policy, namely that the block that was cleaned the longest time ago contains the fewest live pages, may sometimes underperform, particularly due to movement operations, which were introduced in the last section. 

Movement operations pack the pages of groups with block-excess more compactly on fewer blocks. Suppose that many of them occur rapidly in a group relative to the size and update frequency of the group. By the time they are finished, a significant number of blocks in the group will be completely full. In such a scenario, the block that has been least recently erased holds statistically the same number of live pages as the other blocks in the group, so the LRU heuristic fails. 

To demonstrate this, we made a micro-experiment using Wolf whereby the workload is divided into two groups $g_1$ and $g_2$ where $s_1 = s_2$, $p_1 = 100\%$ and $p_2 = 0\%$. Initially, $g_1$ has most of the over-provisioned space and $g_2$ has almost none. We then abruptly swap the groups' update frequencies. Movement operations are issued, rapidly compacting the pages of group 1 into few physical blocks and moving the redeemed blocks to group 2. This creates a vast number of filled blocks with the same number of live pages in group 1. We then swap the update frequencies of the groups again. Cleaning operations are triggered in group 1, but since the blocks in this groups have the same number of live pages, the LRU policy is unable to choose a block with exceptionally few live pages. Write-amplification after the second swap is shown in Figure~\ref{fig:greedy.vs.lru}. Approximately $15\%$ more migrations take place in the LRU policy compared to the greedy policy until write-amplification converges. 
%The model in appendix \ref{App:equib} describes this situation as well.
  
\begin{figure} 
\includegraphics[scale=0.25]{greed-vs-lru.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{The greedy vs. LRU policies}
\label{fig:greedy.vs.lru}
\end{figure}

%In graph  \ref{fig:greedy.vs.lru.90.10} we repeat the same experiment with the same workload except the update frequencies are $90\%$ and $10\%$ respectively. This graph gives more of a birds' eye view over 3 consecutive swaps. Overall, the $5\%$ more migrations took place for the LRU policy, and the greedy and window-greedy policies were approximately equal, with greedy outperforming window-greedy by less than $0.1\%$. Note that even in equilibrium, our simulations as well as the simulations in \cite{stoica} show that greedy involves $1-2\%$ less migrations than LRU per each cleaning operation. 

%\begin{figure} 
%\includegraphics[scale=0.25]{greedy-vs-lru/graph-90-10.eps}
%\caption{ The greedy, window-greedy and LRU policies as we make 3 temperature swaps between two groups. The swaps are instantaneous and marked by the vertical dotted lines. }
%\label{fig:greedy.vs.lru.90.10}
%\end{figure}

%There is another situation where the heuristic of the LRU policy does not perform well. Suppose that the workload is more complex. In particular, suppose that many sets of pages in the SSD share temporal update locality and may abruptly change in temperature. Consider a set of hot pages being written in a hot group and then abruptly turning cold. The LRU policy would eventually target these blocks resulting in inefficient garbage-collection. Instead, Wolf's greedy policy does not touch such these blocks as they contain many live pages. Wolf uses an alternative method for coping with such situations. It detects blocks that survived two consecutive erase cycles in their groups and demotes them and their underlying pages to a colder group. 

Traditionally, the argument used against the greedy policy has been that its computational cost is high, particularly the process of choosing a victim. However, victim selection does not need to consider all blocks in the SSD. It is enough to consider only the blocks in a particular group within a particular LUN. As there are usually tens of LUNs in an SSD, this narrowing of the search allows reducing the cost of victim-selection by an order of magnitude. 

\subsection{Over-Provisioning Allocation} \label{sec:overprob_alloc}

We now describe the closed-form method for determining how to allocate over-provisioned space among groups. Let $OP_x$ be the over-provisioned space given to group x. The total amount of physical space consumed by group x is $(s_x + OP_x)/B$ physical blocks. Let $\delta_x$ be the fraction of pages that need to be migrated per cleaning operation in group x. Using equation \ref{eq:eq_6}, we can relate $s_x$, $OP_x$ and $\delta_x$ for any group x:

\begin{equation} \label{eq:eq_group}
\frac{s_x}{s_x - OP_x} = \frac{\delta_x - 1}{\ln(\delta_x)}
\end{equation} 

Let us denote $WA(s_x, OP_x)$ as the write-amplification of group x, which is a function of the size and over-provisioned space allocated to that group. Overall write-amplification is the sum of the write-amplifications of all groups weighted by their update frequencies. 

\begin{equation} \label{eq:total_write_amp}
\begin{split} 
\text{WA} & = \sum^n_{i=1} p_i \cdot WA(s_i, OP_i) 
\end{split}
\end{equation}

Allocating the over-provisioned space among the groups so as to minimize write amplification is an optimization problem. Although~\cite{stoica, Desnoyers} proposed methods for finding the optimal allocation, no closed-form method was proposed. Moreover, methods explored in these works are either expensive (e.g. relying on iterative optimization algorithms), of questionable accuracy (polynomials of best fit that hold the relative update frequencies of groups as a constant), or of questionable adaptability to workload changes (i.e. they only support movement of blocks between adjacent groups). It is important that the over-provisioned allocation strategy should be both accurate and cheap to compute because it should be invoked frequently, especially with a changing workload. We now present a novel closed-form approach. 

Our key insight is that the optimal allocation of over-provisioned space exists on a plateau defined by a few key points in the optimization space. We find two such points by considering two hypothetical suboptimal policies and then merging their solutions. The first policy assigns over-provisioned space to groups only based on the group's size, and the other assigns over-provisioned space only based on the group's update frequency. We can then approximate the location of the optimum based on these two key points. 

\subsubsection{Considering just Size}

The first policy performs garbage-collection greedily across groups. It always picks as a victim the block with the least number of live pages in the SSD, regardless of which group it belongs to. A redeemed block is allocated randomly to any group that has less than B free pages. 

Let us reason about equilibrium in this kind of system. Suppose there are two groups $g_1$ and $g_2$ with different cleaning efficiencies such that $\delta_1 < \delta_2$. The cleaning policy will only target blocks from group $g_1$ since that's where the cheapest blocks to claim are. However, writes are still taking place in group $g_2$. As $g_2$ runs out of space, some of the blocks garbage-collected from group $g_1$ will flow to group $g_2$. This will increase $\delta_1$ and decrease $\delta_2$, until they equalize. At this point, the blocks from both groups will be just as expensive to garbage-collect. 
%Note that at this equilibrium state, over-provisioning for each group is stable as it is naturally balanced by the cleaning policy, and so write-amplification is also stable. 

This equalization principle holds regardless of the number of groups, their sizes or their update frequencies. Eventually, cleaning efficiency among all groups equalize such that: $\delta_1 = \delta_2 = ... = \delta_n$. This also means that the amount of over-provisioned space in each group reaches a fixed point (it may oscillate, but the cleaning policy will cause it to converge again). So, even though this is an open system, whereby blocks can flow among groups, in equilibrium the amount of over-provisioned space in each group can be assumed to be fixed, and so each group can be analysed as a closed system. 

By equation \ref{eq:eq_group}, the fact that cleaning efficiency for all groups in equilibrium is equal implies that the following holds:

$$
\frac{s_1}{s_1 - OP_1} = \frac{s_2}{s_2 - OP_2} = ... = \frac{s_n}{s_n - OP_n}
$$

It is therefore easy to see that for any group $g_x$: 

$$
\frac{s_x}{s_x - OP_x} = \frac{s_1 + ... + s_n}{s_1 + ... + s_n + OP_1 + ... + OP_n} = \frac{LBA}{PBA}
$$

With some rearranging, the the exact amount of over-provisioned space allocated to group x in equilibrium is the following expression, which only depends on its size. We simplify by letting $V = \left( \frac{PBA}{LBA} - 1 \right)$.

\begin{equation} \label{eq:OP_space_per_group}
OP_x = s_x \cdot \left( \frac{PBA}{LBA} - 1 \right)  = s_x \cdot  V 
\end{equation} 

\subsubsection{Considering just Update Frequency}

The second hypothetical policy we consider assigns over-provisioned space directly based on each group's update frequency. It is solely based on the observation that a group with a higher update frequency should have more over-provisioned space. Thus, the overall over-provisioned space is partitioned to groups based on each group's update frequency, and completely disregarding their sizes. 

\begin{equation} \label{eq:OP_space_per_group_prob}
\begin{split}
OP_x & = p_x \cdot OP \\
& = p_x \cdot \left( V^{-1} + 1 \right) \\
\end{split}
\end{equation} 

Note that this policy directly fixes the amount of over-provisioned space in each group, whereas in the previous one the amount of over-provisioned space per group was determined indirectly through a convergence process. 

\subsubsection{Mixing the expressions} \label{sec:mixing}

Let us now combine the above two policies. Suppose we wish to find a near-optimal allocation of over-provisioned space for the groups. We get two different values from equations \ref{eq:OP_space_per_group} and \ref{eq:OP_space_per_group_prob}. The actual optimum must lay somewhere in-between those values. In fact, it turns out that their average is extremely close to the optimum:

\begin{equation} \label{eq:OP_mixed}
OP_x = \frac{s_x \cdot V + p_x \cdot \left( V^{-1} + 1 \right)}{2}
\end{equation} 

This is shown for several 2-modal workloads in Figure~\ref{fig:2_modal}. The red line shows how the division-point of the over-provisioned space among the groups affects overall write-amplification. The dots along the line give the division-point given by the 3 different policies. 

\begin{figure} 
\includegraphics[scale=0.7]{closed-form.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{ The write-amplification optimization space for several different 2-modal workloads. The fraction from 0 to the blue dot is the amount of over-provisioned space given to group 1, and the rest is given to group 2. The green and black dots corresponds to the point of division based on update frequency or group size alone. The blue dot is their average. }
\label{fig:2_modal}
\end{figure}

We evaluated formula \ref{eq:OP_mixed} through a brute-force exploration of the workload space. We partition the logical address space and update frequency space into Q equally sized chunks of sizes $LBA/Q$ and $1/Q$ respectively. Each group gets at least one chunk of the logical address space and update frequency space. Under these constraints, we test all possible unique workload configurations. We vary the number of groups from 2 to 9. We repeated all experiments for 4 different over-provisioning values, 0.6, 0.7, 0.8 and 0.9. Note that Q controls how skewed the workload can be. The bigger it is, the more extreme the differences between groups in terms of update frequencies and sizes can be. We used two different values of Q, 10 and 20. All in all, our exploration captured a little over a million different workload configurations. % exact number of configurations captured is 1043093

Note that the space of workloads covered in our exploration covers a TPC-C workload. Figure \ref{fig:skew} shows an update histogram of the core data of a TPC-C workload. We see that pages are divided into two clusters in terms of temperature. The hotter cluster's peak is approximately 8 times hotter than the other cluster, and both clusters are similar in size. It is easy to see that the above brute-force approach covers such a workload configuration. We demonstrate this empirically in the evaluation. 

The baseline we used to compare the closed-form method is against is the hill-climbing algorithm similar to the one given in~\cite{stoica}, which always finds the optimum because the optimization space for write-amplification is convex. 

Trends from this analysis are displayed in Figures~\ref{fig:mix_groups} and \ref{fig:mix_over}. Both graphs show the average and maximum percentage differences of our policy from the optimum for the two different values of Q for every workload configuration tried. On average, our policy is below 1\% of the optimal for all the workload configurations. The maximum departures from the optimal are between 2\% (when Q=10) and 9\% (when Q=20). Put differently, the closed-form we propose works well unless for very skewed workloads where a group is either very hot or very cold. 

In order to take such skew into account in practice, we provide special treatment to the coldest group. When the hit rate of the coldest group is less than a certain fraction of the second coldest group, set to $5\%$ in our implementation, we allocate a fixed over-provisioned space to the coldest group, in our implementation $5\%$ of the smallest group's logical size. For the remaining groups we allocate over-provisioned space using the closed-form method. This works in practice well for the TPC-C Workload, whereon a high percentage of the data is extremely cold relative to the rest. 
 
\begin{figure}[t]
\includegraphics[scale=0.25]{boxplot1.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{ The average and maximum percentages off the optimal for all configurations with certain number of groups. In these experiments, $LBA / PBA = 0.7$.  }
 \label{fig:mix_groups}
\end{figure}

\begin{figure}
\includegraphics[scale=0.25]{boxplot2.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{ The average and maximum percentages off the optimal for all configurations with certain values of LBA / PBA. The number of groups is fixed to 5. }
 \label{fig:mix_over}
\end{figure}

\subsection{Temperature Detection} \label{sec:temp_det}

A key component of subroutine \ref{lst:writes} used to handle writes is to determine if the logical page should remain on the same group, or be demoted or promoted. A page should be promoted or demoted only if its update frequency changes relative to the group. Wolf uses one independent temperature detector for each group. If the temperature detector deems a page in group i relatively hotter or colder than its group, it migrates it to groups i+1 or i-1 respectively. 

Temperature detectors are subject to a trade-off between bookkeeping overhead and accuracy, and implementing a detector that strikes a good balance between these aspects is non-trivial. In our implementation, we used a detector inspired from \cite{bloom}. It consists of 2 bloom filters, one active and one passive. When a page is written to a group, its logical address is inserted into the active filter. Each group has independent write intervals, each of which is set to be as long as the number of pages in the group. At the end of an interval, the passive bloom filter is erased, the active one becomes passive, and a new active filter is created. This new bloom filter is initialized with 0.3 as the false probability rate and the projected number of elements is set to the current size of the group. Thus, each page in the SSD needs 5 bits in RAM for both bloom filters, which is not a significant overhead. The filters are used as follows. If the address of a page update exists in both active and passive filters and is an application update, the page is promoted to the next hotter group. If the address is in neither bloom filters and the write is a garbage-collection migration, the page is demoted to the next colder group. Otherwise, the page is updated in its current group. Designing a better temperature detector for Wolf is a topic for future work. 

\subsection{Garbage-Collection and Parallelism} \label{sec:Garbage-Collection-and-Parallelism}

Wolf exploits the SSD's available parallelism and achieves load-balancing by partitioning each group equally among all LUNs. It does so by maintaining free space for every group in every LUN, similarly to~\cite{adaptive}. We introduce the notion of a \textbf{subgroup} to refer to the blocks of given group that are on a particular LUN. Wolf's garbage-collection policy issues a garbage-collection operation in a subgroup as soon as the number of free pages in the subgroup falls below $B$. The manner in which a victim is chosen is described in section \ref{sec:cleaning_within_groups}. In terms of scheduling, a write targeting group $g_x$ is scheduled on some subgroup of $g_x$ that has free space and whose LUN is currently non-busy. During garbage-collection, the pages that are migrated can be written on any subgroup of the target group. 

\subsection{Wear-Levelling} \label{sec:wear-leveling}

The specifics of wear-levelling are orthogonal to the design of Wolf. Dynamic wear-levelling can take place by reassigning old blocks from hot groups to young groups to decelerate their wear, and young blocks from cold groups to hot groups to accelerate their wear. Static wear-levelling can take place in the coldest group to free exceptionally young blocks and assign them to hot groups. 

%To control this experiment and also establish a baseline for later, we assume an oracle temperature detector which knows in advance the update probability of different pages. There are 8 groups, and pages x updates overall goes into group number $x / 20$, and all pages for which $x > 140$ go into the last group. We then calculate the update frequency for each group dynamically as in section \ref{sec:Dynamic_Group_Management}. Surprisingly, the closed-form method outperformed the iterative method with $4\%$ less migrations. The reason for this turned out to be that the iterative method gives very little over-provisioned space to the coldest group, as shown in table \ref{tab:gc_closed_iterative}. This means that every now and then, when this group needs to donate blocks to other groups, many migrations are involved leading to garbage-collection spikes that occur irregularly throughout the trace, as shown in figure \ref{fig:gc_closed_iterative}. This suggests that the theoretical difference between the closed-form and iterative method is arbitrarily small and that it is overshadowed by other factors in a realistic setting. It also indicates that the closed-form method is generally more compatible with Wolf. 

%0-19 -> 1
%20-39 -> 2
%40-59 -> 3
%60-79 -> 4
%80-99 -> 5
%100-119 -> 6
%120-139 -> 7
%140-159 -> 8

%http://www.tablesgenerator.com/
%\begin{table}[h] 
%\begin{center} 
%\begin{tabular}{| p{1cm} | p{1cm} | p{1cm} | p{1.4cm} | p{1.4cm} |}
%\hline
%Group & size   & prob   & \textbf{iterative} & \textbf{closed-form} \\ %\hline
%1     & 66.5\% & 3.9\%  & 25.0\%       & 35.2\%         \\ \hline
%2     & 6.1\%  & 5.0\%  & 8.7\%        & 5.5\%          \\ \hline 
%3     & 1.1\%  & 1.4\%  & 1.8\%        & 1.3\%          \\ \hline
%4     & 0.7\%  & 1.5\%  & 1.4\%        & 1.0\%          \\ \hline
%5     & 5.6\%  & 16.4\% & 13.7\%       & 11.1\%         \\ \hline
%6     & 16.1\% & 55.4\% & 39.3\%       & 35.8\%         \\ \hline
%7     & 3.7\%  & 14.8\% & 9.5\%        & 9.2\%          \\ \hline
%8     & 0.2\%  & 1.6\%  & 0.6\%        & 0.9\%          \\ \hline
%\end{tabular}
%\end{center}
%\caption{The sizes and update frequencies in the experiment, and how %iterative and closed-form methods differ in how much over-provisioned %space they allocate to the different groups.}   
% \label{tab:gc_closed_iterative}
%\end{table}


%\subsubsection{temp detection - to be replaced}

%So far, we assumed an oracle temperature detector that knows the update probability of every page in the SSD. In this section, we perform experiments with with real temperature detector to determine how much performance we lose by 

%The issue of temperature detection is largely orthogonal to this work, and various existing schemes can be adapted to suit our purpose. Like \cite{stoica}, we use two schemes for our evaluation. The first is an oracle that knows the update frequency of every page, as well as any changes to the update frequency. 

%The second algorithm is based on estimating the update distance between two updates to a page. An existing idea is to copy all live pages in a cleaning operation to the same block, packing them and preserving their relative order. Thus, the update distance for different pages in a block can be estimated based on a page's location in a block. The closer a page is to the end of a block, the more recently it has been updated by an application IO. 

%Unfortunately, there are reasons to believe that on a parallel SSD, migrating all pages to the same block may harm performance. Suppose that our SSD does not have a safe battery. In this case, all migration must be finished before a block being cleaned can be erased. This is to avoid a possible loss of data during a power failure. The problem is that if all writes are made to the same new block, they cannot be parallelized across many different channels and LUNs. This may have two adverse effects on performance. Firstly, it takes longer before we can erase the block, and so it takes longer before we free space. This may stall application writes. Secondly, a nice property of writes in page-mapping schemes is that they can flexibly be executed on any LUN. Thus, we can schedule them on LUNs that are currently not targeted by reads so as to improve performance for reads. However, if writes target a specific block, we lose this scheduling flexibility, and so we may harm the performance of reads. It is therefore an open question if an FTL can be designed that preserves locality during garbage-collection without harming performance. This is under current investigation. 

%For now, we use a temperature detection scheme based on bloom filters inspired by , but somewhat simpler. The design uses the notion of write-intervals, each with a length equivalent to the size of the group at the time the interval started. At the start of an interval, we create a bloom filter for the group. We also always maintain the bloom filter from the two last intervals. During an interval, for any logical write that takes place into the group we first make a lookup in all the bloom filters. If the the logical address exists in all of them, we promote the page. Otherwise, we insert the page into the current bloom filter. During garbage-collection, we also probe all bloom filters for every page migrated. If the page is in none of the bloom filters, we demote it to a lower group. 




%\section{Static Data}

%How do we define static data? With relation to the threshold. If data has an update probability such that it is updated less often than pages in the other groups do threshold * (LBA – static), then the data is static. 

%What is the contribution of wear-leveling to write-amplification? Addative. Show that it isn't significant. 

%Depending on the workload, static data may turn dynamic. This is exactly what we get. Suppose we can separate the data into two groups. Suddenly one group needs a lot more blocks. Suppose it gets those blocks through fast redistribution. So initially, it gets blocks from another group. Eventually, there are enough blocks in the group. Then, at last, garbage-collection kicks in within this group. At this point, all blocks have the same distribution of live pages. So Greedy outperforms LRU. 


%\section{Sequential Writes} % (fold)
%\label{sec:seq}

%Let us generalize equation \ref{eq:eq_6} to the case where some %parts of the logical address space are sequentially written and %others are uniformly randomly written. Suppose that the SSD can %defect 



%We observe that the SSD has to make fast proactive decisions. It isn't clear how long it takes it before it can tell if data in a group really changed, or not. How does it know for sure how to trigger the fast redistribution policy? 

%Note also that sometimes the workload is such that temperatures cannot be inferred for pages at all, like any copy-on-write scheme. Log structured file system, or perhaps even a write-optimized b-tree. In such cases, hits to the SSD become extremely important or everything in this paper falls apart. 

%What does it take to implement a system that complies with our system model?
%How to reason about write amplification.
% section impact_on_system_design (end)

06_eval.tex

\section{Evaluation}

Let us evaluate Wolf against the sate-of-the-art. As \cite{stoica}, we rely on simulation for our evaluation. We thus ignore the impact of error correction and bad block management on write-amplification, and the possible RAM limitations of a given SSD model. Rather, we focus on the impact of over-provisioned space utilisation on write-amplification with a simulator that reflects the internal structure of an actual SSD.  We are in contact with a SSD constructor to proceed to a validation of our simulation results. 

The recent scheme in FDP~\cite{stoica} has been shown to dominate existing block managers that strive to separate pages based on their update frequencies to reduce write-amplification, so it will serve as the main frame for comparison. We implemented in EagleTree the data allocation mechanisms from FDP, as described in~\cite{stoica}. We begin the evaluation by assuming an oracle temperature detector that knows the precise update probability of every page. We start by comparing how these schemes adapt to changes in workload. 

% Our implementation of \cite{stoica} differs from that of Wolf only in that in \cite{stoica} the groups have fixed update probabilities. Thus, when a page changes in update probability, it moves to the other group upon update or garbage-collection operation. On the other hand, in Wolf, the update frequencies of groups is adaptive, as described in section \ref{sec:Dynamic_Group_Management}. Since \cite{stoica} did not describe an explicit strategy for how blocks move among groups as groups change in size, our implementation of \cite{stoica} uses the over-provision redistribution method described in section \ref{sec:Over-provisioning_Redistribution}. 

%Under the oracle assumption and a stable workload (the update temperature of pages remains the same), Wolf and \cite{stoica} have the same performance since they use the same method for determining how to allocate over-provisioned space to the different groups. Therefore, the interesting comparison for now is how these schemes adapt to changes in workload. 

\subsection{Frequency Swap} % (fold)
\label{sub:changing_update_frequencies}

In the first experiment, we examine how the schemes adapt to a change in the update frequencies of two groups. Groups 1 and 2 are equally-sized and have update frequencies $10\%$ and $90\%$, and at some point their update frequencies swap. 

Figure \ref{fig:mass_migrations_prob} shows the evolution of write-amplification as a result of a swap with FDP. As described in Section \ref{sec:wolf}, the pages originally in group 2 which turned cold reside on blocks that occupy a significant amount of over-provisioned space, and it takes a considerable amount of time before the garbage-collection algorithm targets them . Thus, write-amplification is high and slow to decrease again. 

In Figure~\ref{fig:mass_migrations_sol}, we see the result of a swap in Wolf. The change in update frequency is quickly detected, and movement operations aggressively take place in group 1 to reallocate over-provisioned space from the now cold group to the now hot group. Equilibrium is restored much more quickly.

We can compare the schemes using a baseline whereby no swap happens. The additional number of migrations for Wolf and FDP respectively relative to the no-swap scenario and divided by PBA is $0.7\%$ and $152.1\%$. In other words, Wolf hardly requires any additional migrations except a short spike, whereas FDP entails an additional total overwriting the SSD 1.5 times over. 

\begin{figure}
\includegraphics[scale=0.25]{groups_gc_mass_migration_problem.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{ How write-amplification evolves in time with FDP as we swap the update frequencies of two groups. The swap occurs at the dotted line. }
\label{fig:mass_migrations_prob}
\end{figure}

\begin{figure} 
\includegraphics[scale=0.25]{groups_gc_mass_migration_solution.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{ How write-amplification evolves in time with Wolf as we swap the update frequencies of two groups. The swap occurs at the dotted line. }
\label{fig:mass_migrations_sol}
\end{figure}

In order to generalize this result, we show the difference in performance between FDP and Wolf when the groups being swapped have different update frequencies. In the experiment, there are 5 groups with ids 0,1,2,3 and 4 that have exponentially increasing update frequencies of around $3.2\%$, $6.4\%$, $12.8\%$, $25.6\%$ and $51.2\%$, such that the sum of the update frequencies adds up to $100\%$. We swap the update frequencies of every pair of groups. We measure the total difference in migrations between FDP and Wolf and normalize it through division by the number of physical pages in the SSD. The bar chart shows that Wolf always outperforms FDP, with up to 2.2x performance improvements. The performance improvement increases with the difference between the groups in terms of update frequency. 

\begin{figure} 
\includegraphics[scale=0.6]{3d.eps}
\caption{ Garbage-collection performance as we swap the update frequencies of two groups after 5 million writes. }
\label{fig:swapping}
\end{figure}
% subsection changing_update_frequencies (end)

\subsection{Realistic Workload} \label{sec:realistic}

In this section, we examine how Wolf behaves under a TPC-C workload. We generated an IO trace of the TPC-C benchmark using Shore-MT and Shore-Kits \cite{kits}. We added print statements into the code in Shore-MT to collect the logical addresses being written to. We used a scaling factor of 48 to match the size of our simulated SSD. The amount of RAM given to the Shote-MT buffer poll was set to  5$\%$ of the size of the data. 
 
%We used a scaling factor of 48, which generated a database in the region of 800,000 logical addresses. 512 RAM 

%We changed the size of flash pages in EagleTree to match the size of a page in Shore-MT at 8 KB, and we increased the number of physical blocks by 1120 per LUN in order to maintain an over-provisioning ratio of $70\%$. 

A challenge of using TPC-C for benchmarking over SSDs is that the size of the database grows. Of every 100 writes on average, 3 are to new addresses. This is a problem as it causes over-provisioning to change throughout an experiment thereby making it difficult to control and interpret. 

What is even more interesting is that the data that is added to the database throughout an experiment, which we coin $\textup{TPC-C}_{\textup{added}}$, has distinctly different workload characteristics than the data written during initialization, which we coin $\textup{TPC-C}_{\textup{init}}$. Figure \ref{fig:skew} shows the update frequency distribution for the logical pages in $\textup{TPC-C}_{\textup{init}}$. The temperature of most pages in $\textup{TPC-C}_{\textup{init}}$ remains stable. Of the pages in $\textup{TPC-C}_{\textup{added}}$, however, $68\%$ are only written once and never updated and the remaining $32\%$ tend to be hot for a short period of time and are then never updated again. Investigating how to cater for these different workload characteristics is the subject of future work. 

\begin{figure} 
\includegraphics[scale=0.25]{skew.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{Update histogram of logical addresses in $\textup{TPC-C}_{\textup{init}}$ that have update frequencies between 1 and 300, which includes $46\%$ of the pages. Of the remaining pages, $54\%$ are never updated and $0.2\%$ are updated more than 300 times. }
\label{fig:skew}
\end{figure}

Here, we just focus on the updates in $\textup{TPC-C}_{\textup{init}}$ (47 million writes to $802816$ addresses). We assume that the updates in $\textup{TPC-C}_{\textup{added}}$ (10 million writes to $1815483$ addresses) are written elsewhere and so we remove them from the workload. Thus, over-provisioning remains constant throughout our experiments, and the workload is stable: the temperature of pages does not significantly change. 

How does Wolf compare to FDP under a TPC-C workload? When investigating this question, we found two factors that play a role: (i) the definition of groups, as their size and update frequency changes (adaptive for Wolf vs. non-adaptive for FDP), and (ii) the allocation of over-provisioned space (closed form for Wolf vs. the iterative method from \cite{Desnoyers, stoica}, which is theoretically optimal if group sizes and update frequencies are defined). In order to separate the influence of each factor, we ran two sets of experiments: first we varied group definition (both for closed form allocation), then we varied allocation strategy (both for adaptive groups).

Figure \ref{fig:iter-vs-closed} shows the results of both experiments. The blue line corresponds to Wolf (flexible group definition, closed form allocation), the red line corresponds to the theoretically optimal iterative method (with flexible group definition), and the green line corresponds to FDP's group definition (with closed form allocation). The red and green line allow us to separate the features of FDP and how they relate to Wolf. The grey line, used as a baseline, illustrates write-amplification over time if all pages are mixed in one group. 

First, our experiment confirms the significant superiority of data allocation schemes that separate pages based on update frequency over the baseline that considers over-provisioned space as a single group.

Second, we observe that the policies corresponding to the red and blue lines perform similarly. The iterative policy involves $0.2\%$ less migrations than the closed-form policy, which suggests that for a realistic workload the theoretical difference between the policies explored in section \ref{sec:mixing} is in fact small. The number of groups in Wolf oscillates between 7 and 9 groups when running TPC-C. The reason for this is the skew of the workload. The last group tends to be so much hotter than the second hottest group, that Wolf continually creates additional hotter groups (according to the policy in \ref{sec:Dynamic_Group_Management}). However, this leads to the middle groups eventually converging in terms of hit rate, and they are thus merged. The creation and merging of groups does not involve any significant penalty. We observed some fluctuations arising in garbage-collection which occur due to surges in movement operations (but smoothed in Figure \ref{fig:iter-vs-closed}  for readability). Flattening such surges is the subject in future work. The mechanism we proposed in Section~\ref{sec:mixing} to handle coldness skew kicks in with the TPC-C workload, as the difference in update frequency between the coldest and second coldest groups is two orders of magnitude greater than the difference in update temperature between any other two adjacent groups. 

Third, we observe that the red and blue lines perform consistently better than the green line (by a approximately $22\%$ in equilibrium). For the red and blue lines, the update frequency of groups is continuously measured and adapted as described in section \ref{sec:Dynamic_Group_Management}. For the green line, we consider that groups have a fixed order, and that the pages in group i are twice as hot as pages in group i-1 and half as hot as pages in group i+1, as described in~\cite{stoica}. 
%We consider a fixed number of groups n. We tried different values of n and chose 7, the one that minimized write-amplification for this workload. 
The workload skew explains the difference between the flexible group management from Wolf, and FDP's group management. The problem comes from FDP's assumption that the hit rate of one group is within a given factor of its adjacent groups. Wolf overcomes this by measuring how many writes actually target each group in each interval. These much more accurate figures of update frequencies allow the over-provisioning allocation mechanism to give different groups an allocation of over-provisioned space that yields slightly lower write-amplification. This shows that Wolf performs slightly better than the state-of-the-art for a realistic stable workload, while it outperforms it significantly when the workload changes. 

\begin{figure} 
\includegraphics[scale=0.25]{tpcc_eval.eps}
\captionsetup{margin=10pt,font=small,labelfont=bf}
\caption{Comparison of two methods for allocating over-provisioned space to different groups. The red pluses and minuses indicate the creation or merging of groups respectively for the closed-form policy. }
\label{fig:iter-vs-closed}
\end{figure}

As far as we are aware, real SSD manufactures today don't implement schemes like FDP or Wolf. On real SSDs, pages with different update frequencies are mixed on the same blocks. Thus, running the experiments in this subsection on a real SSD would result in a much higher overall write-amplification that would resemble the gray line in figure \ref{fig:iter-vs-closed}. We hope that with the recent advent of schemes like FDP and Wolf, more SSD manufactures would indeed begin implementing such schemes. 

07_conclusion.tex

\section{Conclusion} % (fold)
\label{sec:conclusion}

SSD write-amplification is a key aspect of their performance, which depends on (i) how much over-provisioned space is
made available, and (ii) how this over-provisioned space is allocated to different virtual partitions of the SSDs (groups) 
defined by their update frequency. 
%In this paper, we presented an analysis of how write-amplification evolves in time. We presented the characteristics of the equilibrium state for a uniformly random workload, and derive a simple procedure for bringing a SSD to this well-defined state. This procedure should benefit industry benchmarks and any researcher or practitioner interested in evaluating the performance of SSD-based data systems. 
In this paper, we presented Wolf, a FTL block manager, designed to adapt well to abrupt changes in workload and to the skew of realistic workloads such as TPC-C. Future work includes the deployment of Wolf in an open-channel SSD and its evaluation with a larger set of database workloads.

08_appendix.tex

\appendix
\section{Deeper analysis} \label{App:AppendixA}

Through a series of simple manipulations and application of the Lambert W function, we can express equation \ref{eq:eq_6} in terms of $\delta$: 

%\\
%\frac{PBA}{LBA} & = \frac{\ln(\delta)}{\delta - 1} \\
%\frac{PBA}{LBA} \delta - \frac{PBA}{LBA} & = \ln(\delta)

\begin{equation} \label{eq:new_eq_6}
\begin{split}
 \frac{LBA}{PBA} & = \frac{\delta - 1}{\ln(\delta)}  \\ - \frac{PBA}{LBA} & = \ln(\delta) - \frac{PBA}{LBA} \delta  \\
e^{-PBA/LBA} & = e^{\ln(\delta) - \delta(PBA/LBA)} \\
e^{-PBA/LBA} & = \delta e^{-\delta(PBA/LBA)} \\
-\frac{PBA}{LBA} e^{-PBA/LBA} & = -\delta \frac{PBA}{LBA}  e^{-\delta(PBA/LBA)} \\
-\delta \frac{PBA}{LBA} & = W \left( -\frac{PBA}{LBA} e^{-PBA/LBA} \right) \\
\delta & = - \frac{LBA}{PBA} \cdot W \left( -\frac{PBA}{LBA} e^{-PBA/LBA} \right)
\end{split}
\end{equation} 

This is in fact the equation derived through different means in \cite{Desnoyers, stoica, improved}, so these analyses are equivalent. 

%\section{Reaching Equilibrium} \label{App:equib}

%In sections \ref{sec:equib_written} and \ref{sec:cleaning_within_groups} and in particular in figures \ref{fig:greedy.vs.lru} and \ref{fig:LRU_greed_equib}, we saw that in a situation when multiple blocks have the same number of live pages, a few fluctuations occur in write-amplification before it converges. We now try to explain them using a mathematical model. We concentrate on the scenario from section \ref{sec:equib_written}, namely that the logical address space is sequentially written, that writes are random.

%To understand the fluctuations, the first important observation is that at the beginning the SSD's blocks are divided into two sets: the set of full blocks $S_1$ (of size $|s_1| = LBA/B$ blocks) and the set of empty blocks with free space $S_2$ (of size $|s_2| = OP/B$ blocks). The random writes initially fill up the empty blocks in $S_2$. Then, there are no valid blocks with free space, so cleaning begins. The blocks in set $S_1$ were written earlier than the blocks in $s_2$, so on average they contain more invalid pages. Thus, the blocks in $S_1$ are all cleaned. We call this phase 1. Then, the blocks in $S_2$ all have less valid pages on average than the blocks in $S_1$, so they are cleaned, in what we call phase 2. When this is finished, the blocks in $S_1$ are cleaned in phase 3. This goes on. These sets of blocks are cleaned in alternation, but the difference  between them eventually converges. 

%Can we model the evolution of write-amplification fluctuations? It turns out that we can model them using the following system of equations. $f(x)$ is the expected number of invalid pages in a block after $x$ random application writes since the time the block was written. $w(j)$ gives the number of application writes that have taken place in phase j. $g_i^j$ is the number of application writes that have taken place since the the $i$th block that is cleaned during phase j was last written. 

%Phases 1 and 2 are special. Phase 1 begins after OP application writes, so $g^1_0 = OP$. For the $i$th block that is cleaned in phase 1, we simply add the application additional application writes that have taken place so far during phase 1.

%The first block in phase 2 that is cleaned was on average the first block that was written by the random writes. Thus, it has undergone initially OP random writes before phase 1 as the blocks in $s_2$ were being filled, and it also went through the $w(1)$ application writes that took place in phase 1. The $i$th block cleaned in phase 2 takes account of the additional writes that have taken during phase 2, and also subtracts B because only $OP - i \cdot B$ application writes had taken place since the time the $i$th block in the second phase is cleaned. 

%In any other phase j, $g^j_{0}$ is always the number of application writes that have taken place in the previous two phases. For the $i$th block that is cleaned in phase j, we account in $g^j_{i}$ for the application writes that took place during phase j, and subtract the application writes that took place in phase $j-2$ before the block was cleaned, as they had no effect on the current number of live pages in it.

%\begin{equation}
%\begin{split}
%f(x) & = B (1 - e^{-x/LBA})  \\
%w(j) & = \sum_{k=0}^{|s_{j \bmod 2}|} f(g^j_{k})  \\
%g^1_i & = \begin{cases} OP & \mbox{if } i = 0 \\ 	
%g^1_{i-1} + f(g^1_{i-1} ) & \mbox{if } i > 0. \end{cases} \\
%g^2_i & = \begin{cases} OP + w(1) &\mbox{if } i = 0 \\ 	
%g^2_{i-1} + f(g^2_{i-1} ) - B & \mbox{if } i > 0. \end{cases} \\
%g^j_i & = \begin{cases} w(j-1) + w(j-2) &\mbox{if } i = 0 \\ 	
%g^j_{i-1} + f(g^1_{i-1} ) - g^{j-2}_{i-1} & \mbox{if } i > 0. %\end{cases} \\
%\end{split}
%\end{equation}

%\begin{figure}
%\includegraphics[scale=0.25]{equib-unif/model/graph.eps}
%\caption{ Analytical modelling of garbage-collection   }
%\label{fig:equib_model}
%\end{figure}

%We can plot the expected number of migrations for every cleaning operation in order by plotting $B-f(g^j_i)$ for all cleaning operations from phase 1 and onwards. This is shown in figure \ref{fig:equib_model}, which captures the fluctuations we see in figure in the simulation in figure \ref{fig:LRU_greed_equib}. 

%Regarding the time until convergence to equilibrium, we notice that phase 1 involves a rapidly decreasing write-amplification followed by a rapid increase in phase 2. In phase 3, the curve becomes smoother, and by the end of phase 4 equilibrium is reached. The number of physical writes in the first 4 phases is $2 \cdot PBA$. Out of this, we approximate the number of application writes to be $2 \cdot PBA (1 - \delta)$, where $(1 - \delta)$ is the fraction of application writes made in equilibrium over the total number of writes. We then add an additional OP writes to account for the random writes that take place before phase 1. Thus, our approximation for the number of application writes is:

%\begin{equation}
%OP + 2 \cdot PBA \cdot (1 - \delta)
%\end{equation}

main.tex
% BASED ON VLDB12 LATEX SAMPLE
% base\left. \right\lbrace \right\lbrace d on ACM SIGPROC-SP.TEX VERSION 2.7
% Modified by  Gerald Weber <gerald@cs.auckland.ac.nz>
% Removed the requirement to include *bbl file in here. (AhmetSacan, Sep2012)
% Fixed the equation on page 3 to prevent line overflow. (AhmetSacan, Sep2012)\left\rbrace 
\documentclass{vldb}
\usepackage{graphicx,epstopdf}
\usepackage{balance}  % for  \balance command ON LAST PAGE  (only there!)
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{caption}
\setcounter{secnumdepth}{5}
%\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\usepackage{amsmath}
%\newtheorem*{note}{Note}
\usepackage[]{algorithm2e}
\usepackage[toc,page]{appendix}
\usepackage{fancyvrb}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{url}
\usepackage{balance}  % for  \balance command ON LAST PAGE  (only there!)
\usepackage{listings}
\lstset{escapeinside={<@}{@>}}

\begin{document}

% ****************** TITLE ****************************************

\title{Modelling and Managing SSD Write-amplification}

% ****************** AUTHORS **************************************

% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

 \numberofauthors{3} 
 \author{
 \alignauthor Niv Dayan\\
        \affaddr{IT University of Copenhagen}\\
        \affaddr{Copenhagen, Denmark}\\
        \email{nday@itu.dk}
 \alignauthor Luc Bouganim\\
        \affaddr{INRIA Paris-Rocquencourt}\\
       \affaddr{Le Chesnay, France}\\
        \email{Luc.Bouganim@inria.fr}
 \alignauthor Philippe Bonnet\\
        \affaddr{IT University of Copenhagen}\\
        \affaddr{Copenhagen, Denmark}\\
        \email{phbo@itu.dk}
 }


\maketitle
\balance

\input{00_abstract.tex}
\input{01_introduction.tex}
\input{02_relwork.tex}
\input{03_sysmodel.tex}
\input{04_WAandOP.tex}
\input{05_Wolf.tex}
\input{06_eval.tex}
\input{07_conclusion.tex}


% ensure same length columns on last page (might need two sub-sequent latex runs)




% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{bib}  % vldb_sample.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references

\input{08_appendix.tex}

\end{document}

main.bbl
\begin{thebibliography}{10}

\bibitem{closed}
R.~Agarwal and M.~Marrow.
\newblock A closed-form expression for write amplification in nand flash.
\newblock In {\em GLOBECOM Workshops (GC Wkshps)}, pages 1846 -- 1850, 2010.

\bibitem{kits}
A.~Ailamaki, R.~Johnson, I.~Pandis, and P.~T\"{o}z\"{u}n.
\newblock Toward scalable transaction processing: Evolution of shore-mt.
\newblock {\em Proc. VLDB Endow.}, pages 1192--1193, Aug. 2013.

\bibitem{spikes}
P.~Bodik et~al.
\newblock Characterizing, modeling, and generating workload spikes for stateful
  services.
\newblock SoCC, pages 241--252, 2010.

\bibitem{uflip}
L.~Bouganim, B.~Jonsson, and P.~Bonnet.
\newblock {\em uFlip: Understanding Flash IO Patterns}, pages 1--12.
\newblock CIDR. 2009.

\bibitem{bux}
W.~Bux and I.~Iliadis.
\newblock Performance of greedy garbage collection in flash-based solid-state
  drives.
\newblock {\em Perform. Eval.}, pages 1172--1186, Nov. 2010.

\bibitem{adaptive}
L.-P. Chang and T.-W. Kuo.
\newblock An adaptive striping architecture for flash memory storage systems of
  embedded systems.
\newblock RTAS, pages 187--, 2002.

\bibitem{dac}
M.-L. Chiang, P.~C.~H. Lee, and R.-C. Chang.
\newblock Using data clustering to improve cleaning performance for plash
  memory.
\newblock {\em Softw. Pract. Exper.}, pages 267--290, Mar. 1999.

\bibitem{EagleTree}
N.~Dayan, M.~K. Svendsen, M.~Bj{\o}rling, P.~Bonnet, and L.~Bouganim.
\newblock Eagletree: Exploring the design space of ssd-based algorithms.
\newblock {\em Proc. VLDB Endow.}, pages 1290--1293, Aug. 2013.

\bibitem{Desnoyers}
P.~Desnoyers.
\newblock Analytic modeling of ssd write performance.
\newblock In {\em SYSTOR}, pages 12:1--12:10, 2012.

\bibitem{dftl}
A.~Gupta, Y.~Kim, and B.~Urgaonkar.
\newblock Dftl: A flash translation layer employing demand-based selective
  caching of page-level address mappings.
\newblock In {\em ASPLOS}, pages 229--240, 2009.

\bibitem{limit}
R.~Haas and X.~Hu.
\newblock The fundamental limit of flash random write performance:
  Understanding, analysis and performance modelling.
\newblock Technical report, IBM, 2010.

\bibitem{write-amp}
X.-Y. Hu, E.~Eleftheriou, R.~Haas, I.~Iliadis, and R.~Pletka.
\newblock Write amplification analysis in flash-based solid state drives.
\newblock In {\em SYSTOR}, pages 10:1--10:9, 2009.

\bibitem{container}
X.-Y. Hu, R.~Haas, and E.~Evangelos.
\newblock Container marking: Combining data placement, garbage collection and
  wear levelling for flash.
\newblock In {\em Proceedings of the 2011 IEEE 19th Annual International
  Symposium on Modelling, Analysis, and Simulation of Computer and
  Telecommunication Systems}, MASCOTS '11, pages 237--247, 2011.

\bibitem{fast}
S.-W. Lee, W.-K. Choi, and D.-J. Park.
\newblock Fast: An efficient flash translation layer for flash memory.
\newblock In {\em EUC Workshops}, pages 879--887, 2006.

\bibitem{Lee2013}
Y.-S. Lee, S.-H. Kim, J.-S. Kim, J.~Lee, C.~Park, and S.~Maeng.
\newblock {OSSD: A case for object-based solid state drives}.
\newblock {\em 2013 IEEE 29th Symposium on Mass Storage Systems and
  Technologies (MSST)}, pages 1--13, May 2013.

\bibitem{improved}
X.~Luojie and B.~M. Kurkoski.
\newblock An improved analytic expression for write amplification in nand
  flash.
\newblock ICNC, pages 497 -- 501, 2012.

\bibitem{Ouyang2011}
X.~Ouyang, D.~Nellans, R.~Wipfel, D.~Flynn, and D.~Panda.
\newblock {Beyond block I/O: Rethinking traditional storage primitives}.
\newblock In {\em High Performance Computer Architecture (HPCA), 2011 IEEE 17th
  International Symposium on}, pages 301--311. IEEE, 2011.

\bibitem{bloom}
D.~Park and D.~H. Du.
\newblock Hot data identification for flash-based storage systems using
  multiple bloom filters.
\newblock MSST, pages 1--11, 2011.

\bibitem{log-fs}
M.~Rosenblum and J.~K. Ousterhout.
\newblock The design and implementation of a log-structured file system.
\newblock {\em ACM Trans. Comput. Syst.}, pages 26--52, 1992.

\bibitem{stoica}
R.~Stoica and A.~Ailamaki.
\newblock Improving flash write performance by using update frequency.
\newblock {\em Proc. VLDB Endow.}, pages 733--744, July 2013.

\bibitem{envy}
M.~Wu and W.~Zwaenepoel.
\newblock envy: A non-volatile, main memory storage system.
\newblock In {\em ASPLOS VI}, pages 86--97, 1994.

\end{thebibliography}
