  SSDs are currently replacing magnetic disks in many application areas. A
challenge of the underlying flash technology is that data cannot be updated
in-place. A block consisting of many pages must be completely erased before a
single page can be rewritten. This victim block can still contain valid pages
which need to be copied to other blocks before erasure. The objective of
garbage collection strategies is to minimize write amplification induced by
copying valid pages from victim blocks while minimizing the performance
overhead of the victim selection. Victim selection strategies minimizing write
amplification, like the cost-benefit approach, have linear runtime, while the
write amplifications of time-efficient strategies, like the greedy strategy,
significantly reduce the lifetime of SSDs. In this paper, we propose two
strategies which optimize the performance of cost-benefit, while (almost)
preserving its write amplification. Trace-driven simulations for single- and
multi-channel SSDs show that the optimizations help to keep the write
amplification low while improving the runtime by up to 24-times compared to the
original cost-benefit strategy, so that the new strategies can be used in
multi-TByte SSDs.
