Analysis of the d-choices garbage collection algorithm with memory in flash-based SSDs

Garbage collection algorithms have a profound impact on the performance and life span of flash-based solid state drives. Recently, the $d$-choices garbage collection algorithm was shown to provide an excellent tradeoff between simplicity and performance \cite{vanhoudt31}. In this paper, we introduce the $d$-choices garbage collection algorithm with memory and analyze its write performance using both synthetic and real life workloads. The synthetic workloads consist of uniform random writes and the write amplification is analyzed by means of a mean field model. For the trace-based workloads we rely on simulation experiments and consider systems using either a single or a double write frontier. Apart from studying the impact of adding memory to the $d$-choices garbage collection algorithm, the paper also presents the first trace-based evidence that the double write frontier is very effective in reducing the write amplification in the presence of hot and cold data.