Title
A mean field model for a class of garbage collection algorithms in flash-based solid state drives A mean field model for a class of garbage collection algorithms in flash-based solid state drives
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Basel ,
Subject
Economics
Mathematics
Computer. Automation
Source (journal)
Queueing systems. - Basel
Volume/pages
77(2014) :2 , p. 149-176
ISSN
0257-0130
ISI
000336038000003
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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 of GC algorithms. Apart from the Random GC algorithm, class includes two novel GC algorithms: the -Choices GC algorithm, that selects blocks uniformly at random and erases the block containing the least number of valid pages among the 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 blocks). We further show that the -Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small values, e.g., , 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 per block is large (e.g., for b >= 64).
E-info
https://repository.uantwerpen.be/docman/iruaauth/66b503/1a77701.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000336038000003&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000336038000003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle