A mean field model for a class of garbage collection algorithms in flash-based solid state drives.
Saved in:
| Title: | A mean field model for a class of garbage collection algorithms in flash-based solid state drives. |
|---|---|
| Authors: | Van Houdt, Benny1 benny.vanhoudt@ua.ac.be |
| Source: | Queueing Systems. Jun2014, Vol. 77 Issue 2, p149-176. 28p. |
| Subjects: | Mean field theory, Garbage collection (Computer science), Algorithms, Computer storage devices, Computer scheduling |
| 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$$ ). [ABSTRACT FROM AUTHOR] |
| Copyright of Queueing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 95993864 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A mean field model for a class of garbage collection algorithms in flash-based solid state drives. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Van+Houdt%2C+Benny%22">Van Houdt, Benny</searchLink><relatesTo>1</relatesTo><i> benny.vanhoudt@ua.ac.be</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Queueing+Systems%22">Queueing Systems</searchLink>. Jun2014, Vol. 77 Issue 2, p149-176. 28p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Mean+field+theory%22">Mean field theory</searchLink><br /><searchLink fieldCode="DE" term="%22Garbage+collection+%28Computer+science%29%22">Garbage collection (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+storage+devices%22">Computer storage devices</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+scheduling%22">Computer scheduling</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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$$ ). [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Queueing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=95993864 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s11134-014-9403-0 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 28 StartPage: 149 Subjects: – SubjectFull: Mean field theory Type: general – SubjectFull: Garbage collection (Computer science) Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Computer storage devices Type: general – SubjectFull: Computer scheduling Type: general Titles: – TitleFull: A mean field model for a class of garbage collection algorithms in flash-based solid state drives. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Van Houdt, Benny IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun2014 Type: published Y: 2014 Identifiers: – Type: issn-print Value: 02570130 Numbering: – Type: volume Value: 77 – Type: issue Value: 2 Titles: – TitleFull: Queueing Systems Type: main |
| ResultId | 1 |
