We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A mean field model for a class of garbage collection algorithms in flash-based solid state drives.
- Authors
Van Houdt, Benny
- Abstract
Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $$\mathcal {C}$$ of GC algorithms. Apart from the Random GC algorithm, class $$\mathcal {C}$$ includes two novel GC algorithms: the $$d$$ - Choices GC algorithm, that selects $$d$$ blocks uniformly at random and erases the block containing the least number of valid pages among the $$d$$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $$N=50{,}000$$ blocks). We further show that the $$d$$ - Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $$d$$ values, e.g., $$d = 10$$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $$b$$ per block is large (e.g., for $$b \ge 64$$ ).
- Subjects
MEAN field theory; GARBAGE collection (Computer science); COMPUTER algorithms; COMPUTER storage devices; COMPUTER scheduling
- Publication
Queueing Systems, 2014, Vol 77, Issue 2, p149
- ISSN
0257-0130
- Publication type
Article
- DOI
10.1007/s11134-014-9403-0