Efficiently Reclaiming Space in a Log Structured Store

The cost of executing I/O and the maximum number of I/Os that are provided in a system is important for both system cost and performance. Log structured file systems (LFS) [23, 24] were introduced both to reduce the cost of I/O and to increase the number of blocks that could be written by exploiting batching. An LFS writes batches of diverse pages to secondary storage using large buffers. Further, because the buffer must be written to contiguous secondary storage, LFS’s unit of reclaimed storage is a buffer size area on secondary storage. (In a RAID setting [21], the large buffer is striped across an array of disks.)

An SSD controller, in implementing its flash translation layer (FTL) [2], needs also to reclaim large storage units. It writes pages to SSD storage within an erase block, which is the unit of erasure for flash storage. Pages must be erased between writes, so the unit of reclaimed storage is the erase block. How efficiently it does this helps to determine how many IOPS and cost/IOPS that it can provide.

So for both LFS and FTL, the unit of reclaimed storage (which we refer to subsequently as a “segment”) must be an area that contains a number of pages. However, it is the pages themselves that are the unit of obsolescence. That is, an update to a page replaces the page’s prior version, while the rest of its containing segment is unchanged by the update. Several updates can, of course, make other pages in the segment obsolete as well. This leads to segments that have a “checkerboard” pattern of over-written (and hence obsolete) pages and pages that continue to represent the current content of their respective pages. Figure 1 illustrates this.

Whether it is an LFS or an SSD’s FTL, neither do update-in-place, and both require that out-of-date versions of pages be garbage collected (called “cleaning” in [23]). Without cleaning, secondary storage fills up with partially overwritten segments, i.e. segments in which some of the pages are current versions and some are obsolete (empty of current versions) and hence garbage. And importantly, new storage for writes needs to be acquired in segment size units to ensure the system’s ability to continue writing new versions of pages to storage.

Obviously, it would be great if we could find a segment in which all pages have been over-written and are hence empty. Then we could simply select this segment for re-use, and erase it if it is a flash erase block. But this is incredibly unlikely as we are usually dealing with segments capable of storing a few hundred pages or more. So we have to deal with segments that have a checkerboard of current and empty pages. The strategy to do this entails writing the still current pages to a new segment. Once these pages are written elsewhere (somewhat as if they were being updated by users), all pages in the segment are then empty. This cleaning process has emptied the pages that were current when cleaning began for the segment. Figure 1 shows how segments become increasingly dirty, and how cleaning moves the still current pages to another segment so that there are no remaining current versions of pages in the original segment.

How efficiently we can perform cleaning is an important factor in how well these systems perform. This cost is measured in the number of page moves required to perform cleaning, which is the number of pages that still contain current data. There are two reasons why this “efficiency” matters.

1. 1.

   The number of page moves is directly related to the execution cost of garbage collection. Execution cycles spent on cleaning are cycles that are unavailable for tasks more directly related to user I/O operations.

2. 2.

   For SSDs, the number of page moves is related to what is called “write amplification” [3]. This is a measure of how many writes result from a single page user write. The larger the write amplification, the more wear on the flash memory, which is limited in the number of writes that it can provide.

The remainder of the paper is organized as follows.

• •

  Section 2 starts by providing an algebraic derivation of cleaning cost, originally derived in [23]. Following that is a derivation of simple round robin, age-based cleaning costs, previously derived in [15, 4, 7, 8]. This age based cleaning analysis is used later.

• •

  Section 3 contains one of the significant contributions of this work. We present an analysis demonstrating that a skewed data and update distribution with hot and cold data of different sizes can be exploited to reduce cleaning cost. While this is known [23], our new analysis convincingly demonstrates this and provides a lower bound on cleaning cost for various skews.

• •

  How to order segments for cleaning so as to produce the lowest cost is the subject of Section 4. Here we introduce the major contribution of the paper, the “optimal” approach to choosing the order of cleaning among the in-use segments. This analysis produces a formula that can be evaluated to determine the cleaning order for segments that are in-use.

• •

  The analysis of the prior section needs to be converted into an executable cleaning program. This is described in Section 5 and is another contribution of the paper.

• •

  Our cleaning simulation is described in Section 6. This, our last contribution, demonstrates that our cleaning order produces the lowest cost cleaning of the major competing strategies.

• •

  The last two sections contain related work and a short discussion.

We want to know how many I/O accesses, including those for cleaning, are required to write a segment of new pages to the disk. This will be a function of how empty segments are when cleaned, as once used segments fill the allotted storage, space for new data must be reclaimed from previously written segments.

Let $E$ denote the fraction of a segment that is empty. The reading of a segment for cleaning produces $E*S$ empty pages, where $S$ is the number of pages per segment. In order to write $S$ page frames of new data, $1/E$ segments must be cleaned, i.e. read. Further, for each segment read, $(1-E)*S$ pages must be written to move these still alive pages to a different segment. Finally, the cleaned segment, now completely available, must be written with the $S$ new pages. Thus, the total I/O cost of writing that segment, which we denote as $Cost_{seg}$ is

$$Cost_{seg}=\frac{1}{E}reads+\frac{1}{E}(1-E)writes+1=\frac{2}{E}$$

(1)

Also of importance is the write amplification $Wamp$, which is the number of buffer writes performed compared with the number of buffer writes that the user herself performs. In the $Cost_{seg}$ formula in 1, this is the second term on the right. Thus,

$$Wamp=\frac{1}{E}(1-E)$$

(2)

We report our simulation results in Section 6 where our graphs are in terms of $Wamp$.

$E$ is affected by the fraction of the disk used to store current versions of user data. We call this fraction the fill factor, $F$. The apparent size of the disk for users is $F$ times the real physical size of the disk. Cleaning efficiency depends strongly on $F$. The lower $F$ is, the higher the amount of empty space we are likely to find when cleaning segments. In particular, we can find segments for which $E\geq(1-F)$, as $(1-F)$ is the average amount of empty space over the entire disk when users have completely filled their storage allocation. We should, on average, be able to find larger values of $E$ in segments we clean by careful choice of segments. For example, with a fill factor $F=.8$, on average $E\geq.2$, leading to $IO/seg\leq 10$. Hence, in this case, once segment size exceeds $10$ pages, an LFS performs fewer writes per page than a conventional block-at-a-time system.

We want to order the cleaning of segments so as to minimize $Cost_{seg}$. Given equation 1, it is clear that this cost is minimized when we maximize the average value for $E$ at the time a segment is cleaned. Section 4 concerns how we prioritize (order) the segments for cleaning, and the impact of that priority ordering on the average $E$ that we see when cleaning segments.

A particularly simple cleaning priority is to always clean the oldest segment, i.e. the one that was written the longest time in the past. This means that we first clean the segment with the largest $age$. It is more convenient for subsequent discussion to think of this as cleaning first the segment with the smallest value of $1/age$. Age-based cleaning leads to a very simple implementation where segments can be organized in a circular buffer. The segment written at the earliest time is the one to be cleaned next.

A uniform distribution analysis using age based cleaning priority gives a worst case bound on cleaning efficiency which is more accurate than simply using the fill factor $F$. A similar analysis was done earlier [7]. The disk is assumed to be full, i.e. up to its fill factor $F$. Each page is assumed equally likely to be updated, i.e. have the same probability of update. That is, the update frequency for all pages is $U_{pf}=1$. (Note that regardless of update distribution, where $U_{pf}$ may be greater for some pages than for others, average $(U_{pf})=1$ over the entire disk is normalized to $1$.)

Let $P$ be the number of pages of the user visible disk. Let N be the number of page writes between the time that a segment is written and when it is cleaned. Then $E$ is the probability that a page written subsequently “collides” with a page in the segment. That is

$$E=1-(\frac{P-1}{P})^{N}$$

(3)

We are given P. The difficulty is in determining the value for $N$ since $N$ depends upon write cost, i.e. how efficient cleaning is. The physical disk contains $P/F$ pages, and hence $(P/F)/S$ physical segments. For age based priority, we will have written all the physical segments (less one) before cleaning a segment. Each of those segments will have $E*S$ pages available for writing new data. Hence,

$$N=\frac{(P/F)}{S}ES=\frac{PE}{F}$$

Then, we have

$$E=1-(\frac{P-1}{P})^{P\frac{E}{F}}$$

The above equation is recursive, but a fixpoint can be found numerically. Once $P$ is sufficiently large, e.g. greater than 30, this result depends almost entirely on the value of $F$. In fact, in the limit, as $P$ goes to infinity,

$$E=1-(\frac{1}{e})^{\frac{E}{F}}$$

(4)

because

$$\lim_{P\rightarrow\infty}(\frac{P-1}{P})^{P}=\frac{1}{e}$$

The results for some values for $F$ are presented in Table 1.

This table, all columns except MDC-opt¹¹1MDC-opt is the simulation result for the minimum declining cost (MDC) algorithm proposed later in the paper. This column can be ignored for now. derived from Equation 4, suggests that modest increases of slack space, i.e., $(1-F)$, have a very substantial positive effect on cleaning efficiency. This impact declines as the fraction of slack space increases. As $1-F$ increases, it is increasingly probable that a page will have more than one out-of-date version. These versions are already empty, so another update of their page does not increase the emptiness of their containing segment. A fill factor in the range of $.70$ to $.9$ has high effectiveness, with $E$ in the range of about $.2$ to $.5$ and cost in the range of $10$ to $3.9$.

It is unusual for updates to be uniformly distributed over all the data. In this section, we show that update rate differences can be exploited to reduce cleaning costs. Our analysis for this is artificial, and the way we set things up is all but impossible to realize “in real life”. But this analysis shows the potential if we are able to treat data with different update rates differently.

Assume that we have two different sets of pages, each with uniformly distributed updates, but with the number of pages and update frequencies different for each set. Our analysis goal is to show that if we manage each of these sets of pages completely separately in their own spaces, the write cost for the two sets can be made less than the write cost for the union of the two sets, with uniformly distributed updates. A similar analysis was done in [26]. We hold constant the total page set size and slack space fraction. But we allocate the slack space where it is most useful in reducing write cost. We assume age based cleaning for each set and will use the results of the preceding analysis, as captured in Table 1 to determine $E$.

The total cost for managing the two sets of data separately is the weighted cost for the two sets. Let $D_{i}$ be the fraction of total data size in set $i$, and $U_{i}$ be the relative frequency of updates in set $i$. Then weighted average cost for updates is

$$Cost_{Total}=\sum_{i=1}^{2}Cost_{i}*U_{i}$$

We need to relate cost to $F$, rather than simply to $E$ because we want our result to be a function of how we divide the “slack” space between the two sets. For this we use $E=R*(1-F)$, where $R$ is simply the ratio we observe between $E$ and $(1-F)$. We have computed $R$ in Table 1. Thus, our cost becomes

$$Cost=\frac{2}{E}\approx\frac{2}{R*(1-F)}$$

and total cost for our two separate sets of pages becomes

$$Cost_{Total}=\sum_{i=1}^{2}{\frac{2}{R_{i}*(1-F_{i})}*U_{i}}$$

We want to determine, for a given overall fill factor $F$, how to divide the slack space $(1-F)$ so as to minimize the combined cleaning cost of our two data sets with differing update frequencies. We divide total space into two parts, each part devoted to managing either data set $1$ or data set $2$. $F=D_{1}+D_{2}$ and slack space $(1-F)=S_{1}+S_{2}$. See Figure 2.

We are interested in dividing slack space so we set $S_{i}=(1-F)*g_{i}$ where $g_{1}+g_{2}=1$. Then we have

$$F_{i}=\frac{D_{i}}{D_{i}+S_{i}}=\frac{F*Dist_{i}}{(1-F)*g_{i}+F*Dist_{i}}$$

where $Dist_{i}=D_{i}/(D_{1}+D_{2})$. We are normalizing our distribution and our computation here. For example, if we are dealing with an $80:20$ data distribution where $80\%$ of updates go to $20\%$ of the data, then $Dist_{1}=0.8$ and $Dist_{2}=0.2$.

Plugging $F_{i}$ back into our cost equation yields

$$Cost_{i}=\frac{2}{E_{i}}=\frac{2}{R_{i}}*(1+\frac{F*Dist_{i}}{(1-F)*g_{i}})*U_{i}$$

We want to find the minimum for $Cost_{total}$, so we take the derivative of cost and set it to zero. We want cost in terms of a single variable $g_{1}$, so we replace $g_{2}$ by $1-g_{1}$. We now make an important simplification- i.e. we assume that $R_{i}$ are constant. This is not true, but is a useful simplification as $R_{i}$ does not vary greatly. We hold update rate $U_{i}$, $F$, and $Dist_{i}$ constant. The total cost equation is then, abstractly, of the form

$$Cost_{Total}=A\frac{1}{g_{1}}+B\frac{1}{(1-g_{1})}$$

where all quantities in $A$ and $B$ as constants. This form permits us to easily see how to compute $d(Cost_{Total})/d(g_{1})$.

$$\frac{d(Cost_{Total})}{d(g_{1})}=-A\frac{1}{(g_{1})^{2}}+B\frac{1}{(1-g_{1})^{2}}=0$$

Replacing $A$ and $B$ by their update frequency and size and replacing $(1-g_{1})$ with $g_{2}$ results in

$$(\frac{2*U_{1}}{R_{1}})*(\frac{F*Dist_{1}}{1-F})(\frac{2}{g_{1}^{2}})=(\frac{2*U_{2}}{R_{2}})*(\frac{F*Dist_{2}}{1-F})(\frac{2}{g_{2}^{2}})$$

We will solve the above equation for $g_{1}/g_{2}$. But we will simplify the equation for a special set of distributions so that we can clearly see a pattern in managing hot and cold data separately. The special set of distributions and update frequencies is the very frequently used $m:1-m$, where $m\%$ of the updates go to $1-m\%$ of the data. An example of this is the 80:20, where 80% of the updates go to 20% of the data. For these special distributions, $U_{1}*Dist_{1}=U_{2}*Dist_{2}$. Canceling out these quantities as well as $F$ and $(1-F)$ yield

$$\frac{g_{1}}{g_{2}}=(\frac{R_{2}}{R_{1}})^{\frac{1}{2}}$$

Importantly, slack space division is not related to the size of data being accommodated.

Simplifying things even more, we note that $(R_{2}/R_{1})^{1/2})\approx 1$, so that, for these distributions, $g_{1}\approx g_{2}$ and hence we simply share the slack space equally. But remember, this approximation applies only to our special set of distributions.

We can now capture what would be the minimum cost for our two distributions, based on using the derived way above of sharing the slack space equally between hot and cold data. This is a very large, multi-parameter space. So we restrict ourselves to using a fill factor for the SSD of $.8$, and hence the slack space is $.2$. Dividing slack space equally has a differential impact on the fill factors for hot and cold data, with the hot data having a lower fill factor than the cold data. Said differently, we wait for hot segments to be emptier than cold segments. Thus, when update rates differ, we should not necessarily clean the emptiest segment first.

In Table 2, we show the resulting minimum cost values for a number of distributions that are commonly used to evaluate performance. While we found the minimum cost to be achieved by splitting the slack space equally, the cost does not change very much over a range of space divisions. We include in Table 2 columns showing costs when the space is divided by giving hot data 60% and cold data 40%, and the reverse. This produces only very modest changes in cost, with cost values slightly higher than the minimum.

What we have shown here is that, if we can take into account the hot and cold data distribution, that we can clean more efficiently than if we have uniformly distributed updating. This leads us, in the next section, to how we might efficiently clean data to exploit this opportunity.

Section 2 demonstrated how well we can do assuming a uniform distribution of page writes and a circular buffer. But as demonstrated in Section 3, we can do better if there is a non-uniform distribution of page writes as we can then effectively give more of the slack space to the hot data, improving overall cleaning efficiency even as we reduce cleaning efficiency for cold data. To exploit this, we need to separate hot data and cold data by clustering data into segments based on its update rate.

We exploit a concept that we call declining cost to establish cleaning priority among segments with differing update rates. If cleaning cost per page of a segment can be expected to decline greatly over some time period if we are willing to wait, then we should wait. Instead, we should clean a segment from which we expect very little decline in per page cleaning cost. Indeed, we should clean the segment from which we expect the smallest decrease in cleaning cost, so long as we can reclaim some space.

The segment cleaning cost is related to the number of empty page frames in the segments. From Equation 1 we know that the cleaning cost per page frame declines as more page frames become empty due to update activity.

The general problem is to determine the optimal processing order for items whose processing costs decline with time. We assume that object $i$ has processing cost $c_{i}(t_{n})$ at time $t_{n}$. We further assume that the rate of change in cost of processing is constant, i.e., ${dc_{i}(t)}/{dt}$ is a constant. This is not true for cleaning segments, but over a modest interval, it is a useful approximation.

Thus, at $t_{0}$, $i$’s cost to clean is $c_{i}(t_{0})$. Then for any time $t_{i}$, the cost of cleaning object i is given by

$$c_{i}(t_{i})\approx c_{i}(t_{0})+\frac{dc_{i}(t_{0})}{dt}(t_{i}-t_{0})$$

The total cost of processing a collection of $k$ objects, in some particular order is

$$Cost_{Total}=\sum_{i=1}^{k}c_{i}(t_{i})\approx\sum_{i=1}^{k}c_{i}(t_{0})+\sum_{i=1}^{k}\frac{dc_{i}(t_{0})}{dt}(t_{i}-t_{0})$$

The derivative $\frac{dc(t)}{dt}$ will be negative for segment cleaning. It eases the discussion to talk about cost decline, which is captured by $-\frac{dc(t)}{dt}$. Thus, we rewrite $Cost_{Total}$ as

$$Cost_{Total}\approx\sum_{i=1}^{k}c_{i}(t_{0})-\sum_{i=1}^{k}-\frac{dc_{i}(t_{0})}{dt}(t_{i}-t_{0})$$

$Cost_{Total}$ is minimized when the second sum on the right hand side is maximized. We want to show that this is true when the largest cost declines are multiplied by the largest time intervals.

Maximality Lemma: Given two sets of positive numbers X and Y, with $||X||=||Y||$,

$$\sum_{i=1}^{k}x_{i}y_{i}$$

is maximized when $X=\{x_{i}\}$ and $Y=\{y_{i}\}$ are both ordered in the same way, i.e., $x_{i}\geq x_{j}$ iff $y_{i}\geq y_{j}$.

Proof: See the “Maximality Lemma” in the appendix.

Hence, it is best to process the objects experiencing the largest rates of cost decline last, and conversely, to process first the objects with the smallest rates of decline. The intuition here is that it pays to wait for the large cost declines, and to process objects whose costs won’t decline much more first.

The preceding result will apply only approximately as the rate of decline in cleaning cost per page is not constant. Thus, this is a first order approximation. We need to differentiate the cost per segment function. As before, $E$ denotes the fraction of the segment page frames that are empty. Further, $U_{pf}$ denotes the frequency of updates to pages in the segment. Recall that the cost of writing a segment is:

$$Cost=\frac{2}{E}=2E^{-1}$$

and hence that cost decline is

$$\frac{d(Cost)}{du}=(\frac{-2}{E^{2}})(\frac{dE}{du})$$

We measure time not in clock time but in update count, where the “clock” has one ”tick” per update. We will refer to ”time” subsequently, but it should be understood that our clock is an update counter. Rate of change with respect to updates is unaffected by variations in system load, outages, etc. In particular, update frequency differences would be reduced by a system outage were we to use clock time, since that would add outage time to age computations, which would reduce the ratio between update frequencies.

We need to determine the value for $dE/du$. To get the rate at which $E$ is changing in a segment, we need to multiply the number of non-empty pages by the segment update frequency. Let $U_{pf}$ denote the update frequency per page. The update frequency per segment is then the number of current pages times $U_{pf}$. Then,

$$\frac{dE}{du}\;\alpha\;\ (1-E)U_{pf}\Delta_{E}$$

where $\Delta_{E}$ is the change in E produced by one update. Hence

$$\frac{d(Cost)}{du}\;\alpha\;\frac{-2(1-E)}{E^{2}}U_{pf}\Delta_{E}$$

The big picture of our cleaning approach, like earlier efforts, is to separate pages into segments based on update frequency. To do this, we need a simple way to estimate update frequency. Keeping extensive statistics on page updates is expensive. So, similar to [23], we use some form of “age” as an approximate (and highly uncertain) estimate of a page’s update frequency.

We want to know what fraction of updates are updates for a given segment. This will determine update frequency as a function of overall update rate. We define $u_{now}$ as the current update count, $u_{p1}$ as the time of the ultimate (last) segment update,and $u_{p2}$ as the time of the penultimate (next to last) update.

We have found that using $u_{now}-u_{p1}$ as the update period (inverse of update frequency) is very inaccurate. Instead, we want to take a sample of two intervals instead of one as the the average interval between updates for a segment. Then, for our segment of interest,

$$U_{pf}=\frac{2}{u_{now}-u_{p2}}$$

That is, there are two updates to our segment over an update interval of $u_{now}-u_{p2}$.

It is possible to extend this to include a larger interval containing more updates, e.g.

$$U_{pf}=\frac{n}{u_{now}-u_{pn}}$$

but $U_{pf}$ may change, and we want to track these changes, so we should not average over too many updates. Subsequently, we average $U_{pf}$ over two update intervals. Then our estimated cost decline function is

$$-\frac{d(Cost)}{du}\;\alpha\;\frac{2(1-E)}{E^{2}}*\frac{2}{u_{now}-u_{p2}}*\Delta_{E}$$

$\Delta_{E}$ is the change in emptiness $E$ produced by an update to a page in the segment. For a fixed size page, this change in $E$ is $1/P$ where $P$ is the number of pages in the segment. This yields a minimum cost decline function

$$-\frac{d(Cost)}{du}\;\alpha\;\frac{2(1-E)}{E^{2}}*\frac{2}{u_{now}-u_{p2}}*\frac{1}{P}$$

Since $1/P$ is a constant, it does not impact the cleaning order of segments.

The situation is more complicated when pages can be of variable size. Assume that a segment is $B$ bytes long. What is the impact of an update to page P on emptiness. It is something like $Size_{P}/B$. But what do we use for $Size_{P}$? Since we do not know the next page to be updated, we cannot know its size. However, we can approximate the size by computing the average size of the remaining pages that have not yet been updated. This is a value for $\Delta_{E}$ averaged over the remaining valid pages of the segment.

Let $C$ be the number of pages that have not yet been updated. Further let $A$ be the amount of available free space in our segment of size $B$. Then, the average size of the remaining un-updated pages is $(B-A)/C$. This yields a more general form for declining cost of

$$-\frac{d(Cost)}{du}\;\alpha\;\frac{2(1-E)}{E^{2}}*\frac{2}{u_{now}-u_{p2}}*\frac{(B-A)/C}{B}$$

Subsection 4.3 discussed how to estimate update frequency. However, if we know that updates are uniform, then $U_{pf}=c$, i.e. constant. Taking this into account, with declining cost, we have for our minimum declining cost (MDC)

$$\textrm{Priority[MDC]}\;\alpha\;\frac{2(1-E)}{E^{2}}*\Delta_{E}$$

We define Priority[greedy] as ordering segments for cleaning based on how much empty space they have. Essentially, “greedy” cleans the segment with the highest value of $E$ first, which is the lowest value of $1/E$ when defining high priority by low number as we have been doing. Greedy priority is what age based cleaning yields when applied to a uniform distribution. That is, cleaning the oldest first will have the same result as cleaning the emptiest first because, at least with high probability, the oldest segment is also the emptiest.

For a uniform update distribution, Priority[MDC] orders the segments for cleaning in exactly the same order as Priority[greedy]. This is seen by noting that

$$\frac{1-E}{E^{2}}=\frac{1}{E}(\frac{1}{E}-1)$$

The factor $(1/E)-1)$ is ordered in the same way as $(1/E)$. Both of these factors are positive. Thus their product is ordered as $(1/E)$. Hence, for a uniform distribution, Priority[MDC] $\alpha$ Priority[greedy].

As we have seen in Section 3, cleaning performance is improved when we can separate data by update frequency, i.e. separate hot from cold data. Thus, we try to group together pages from segments as much as possible by their values for $u_{p2}$. Since $u_{p2}$ is maintained in our segment summary information, or is assigned to each newly updated page, we have the information needed for doing this. Thus, when assigning pages to segments, we first sort the collection of pages by their value of $u_{p2}$. This is similar to what the Berkeley paper [23] proposed, though their technique used $u_{p1}$ instead of $u_{p2}$. Sorting permits us to cluster pages by $u_{p2}$ when assigning the pages to new segments, both for user and GC writes. Thus, it is a technique for separating pages into segments by update frequency.

Note that the sorted ordering of page moves to new segments may be slightly different from the minimum declining cost order. However, minimum declining cost order determines the set of candidate segments to clean. The sorting by $u_{p2}$ is within this candidate set.

We first used synthetic workloads to evaluate various cleaning algorithms, where page writes were generated following predefined distributions as discussed below. For each experiment, we wrote 10TB data, which is 100 times the size of the simulated log-structured system, so that the write amplification stabilized. Throughout this evaluation, we focus on the following two questions: First, what is the effectiveness of each optimization used in the proposed MDC algorithm? Second, how well the proposed MDC algorithm performs compared to other cleaning algorithms? In the remainder of this section, we answer these two questions through our evaluation.

To evaluate the cleaning algorithms on a somewhat more realistic workload, we carried out experiments using the I/O traces collected from running the TPC-C benchmark on a B⁺-tree-based storage engine. The buffer cache size was set at 4GB. We varied the fill factor from 0.5 to 0.8, which corresponds to TPC-C scale factors 350 to 560. It should be noted that the storage size under the TPC-C benchmark increases over time. Thus, for each scale factor setting, we first loaded the TPC-C tables and ran the TPC-C benchmark until the fill factor increased by 0.1. After collecting the I/O traces, we replayed them using the simulator to evaluate the cleaning algorithms. The write amplification was measured during running phase, which contains about 250GB writes.

Figure 6 shows the resulting write amplifications on the TPC-C traces. In general, the TPC-C traces also contain hot pages and cold pages, and its skewness is close to 80-20 [26]. Thus, both the age-based and greedy algorithm do not work well, which is consistent with the results under the synthetic workloads. By pre-analyzing page update frequencies, both multi-log-opt and MDC-opt achieve much lower write amplifications. Moreover, MDC-opt further reduces the write amplification compared to multi-log-opt.

Without knowing page update frequencies in advance, both multi-log and MDC perform worse than their optimal alternatives. Specifically, we saw that multi-log performs even slightly worse than the cost-benefit algorithm. One reason is that multi-log initially places all pages into one log and adjusts the number of logs as the system runs. Thus, its cleaning cost decreases over time but requires many writes before converging. However, the number of pages written in this experiment is much smaller than the previous experiment with synthetic workloads.

The TPC-C workload also has a shifting pattern where hot pages become cold over time [26]. Since both algorithms use past update timestamps to estimate page update frequencies, this shifting pattern reduces the accuracy of the estimation. Even so, MDC has a much lower write amplification compared to other cleaning algorithms under all fill factors.

In addition to FTL in SSD controllers, log structured stores have been widely used in various data management components and systems. Examples include key-value stores [11, 12], NoSQL systems [1, 25], in-memory stores [19, 20], log structured variants of B⁺-trees [13, 22], and the key-value separation design [5, 14, 16] for LSM-trees [17, 18]. In these systems, cleaning is often the new bottleneck because of the expensive write amplification incurred by the cleaning process. By minimizing the cleaning cost for log-structured stores, the proposed MDC algorithm will be able to further improve the performance of these systems.

The original LFS work [23] recognized the relationship between age and update rate. They also recognized that low update rate (old) segments should be cleaned at a lower value of $E$ than the more active update rate (young) segments. To capture this, they proposed a heuristic-based cleaning approach, called cost-benefit, that cleans cold segments more aggressively. However, as we have seen in Section 6, the cost-benefit algorithm still fails to minimize the cleaning cost. The LFS design and its cost-benefit algorithm has been adopted and refined by subsequent research [6, 9, 10, 27]. However, these cleaning algorithms are mainly based on heuristics, which fail to minimize the overall cleaning cost [26].

Desnoyers [8] proposed an analytical model to divide pages into a hot pool and a cold pool, which is similar to our discussion in Section 3. In contrast, our MDC algorithm does not predefine the number of page groups. It instead sorts pages to group pages with similar update frequencies together and selects the cleaning segments globally to minimize the overall cleaning cost. Stoica and Ailamaki [26] proposed a multi-log approach to minimize the cleaning overhead, which is the state-of-the-art cleaning algorithm. Its key idea is to separate pages into multiple logs so that pages within each log have similar update frequencies. When writing to a log $L$ causes the system to be nearly full, the algorithm selects a local-optimal log to clean from $L$ and its two neighbors. However, the multi-log approach has a few drawbacks, as shown in our evaluation. First, it requires a lot of page writes to converge to its optimal state. Moreover, it may not achieve the minimum cleaning cost, as its selects cleaning segments locally. The proposed MDC algorithm addresses these two problems and further reduces the cleaning cost.

Simulations can give you results that may be difficult or impossible to fully confirm. However, when analysis can be applied to the same conditions as were used for a simulation, we want to be able to confirm that the results produced from simulations agree with those produced by analysis. We have done this for the results from conditions that we were able to analyze.

Uniform Distribution:

From Table 1, we can compare column E, our analysis results (for age based cleaning, which is optimal for uniform distribution, and column MDC-opt, the results produced by simulation using MDC. These columns agree to two significant digits. Figure 5a graphs the simulation results, and shows that MDC produces the lowest costs among the cleaning methods we compare.

Hot:Cold Separation:

From Table 2 we can compare our analysis of minimum cost cleaning for distributions divided between hot and cold data in the MinCost with our simulation under the same conditions using MDC, the MDC-opt column. Again, the results are in agreement to at least two significant digits, a confirmation that MDC achieves the best possible results under the admittedly contrived conditions. Figure 3 shows that MDC achieves the optimal results and has lower cleaning costs than the other methods.

The above agreement between analysis and simulation reinforce the confidence we can place in our overall results, including those under more general experimental conditions which we were unable to analyze. These confirmations strongly suggests that it will be very difficult to improve on MDC.

Cleaning efficiency is critical to the efficiency of any log structured store, whether it be a software system such as a log structured file system [23] or a “firmware” system in an SSD controller’s FTL. For an FTL, there is the additional incentive to reduce the write amplification so as to reduce flash storage wear. Our approach described here is intuitive, and produces results when we simulated its use that matched optimal results derived via our analysis. While it may be possible to improve the details of the approach, there is only limited room for subsequent improvements if update frequency changes only slowly. However, knowledge of workload may make it possible to better predict update frequency changes, and knowing update frequency, as shown in our simulations, can often improve results further.