  A log structured store uses a single write I/O for a number of diverse and
non-contiguous pages within a large buffer instead of using a write I/O for
each page separately. This requires that pages be relocated on every write,
because pages are never updated in place. Instead, pages are dynamically
remapped on every write. Log structuring was invented for and used initially in
file systems. Today, a form of log structuring is used in SSD controllers
because an SSD requires the erasure of a large block of pages before flash
storage can be reused. No update-in-place requires that the storage for
out-of-date pages be reclaimed (garbage collected or "cleaned"). We analyze
cleaning performance and introduce a cleaning strategy that uses a new way to
prioritize the order in which stale pages are garbage collected. Our cleaning
strategy approximates an "optimal cleaning strategy". Simulation studies
confirm the results of the analysis. This strategy is a significant improvement
over previous cleaning strategies.
