short-paper

On the Optimality of Greedy Garbage Collection for SSDs

Authors:

Yudong Yang,

Vishal Misra,

Dan RubensteinAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 43, Issue 2

Pages 63 - 65

https://doi.org/10.1145/2825236.2825261

Published: 16 September 2015 Publication History

Get Access

Abstract

Solid state drives have been widely applied in modern computer systems. The lifetime of the SSD depends heavily on the efficiency of the implementation of the garbage collection (GC) algorithm that reclaims previously used pages. In this paper, we present the first detailed proof that the greedy GC algorithm has the optimal performance (minimized write amplification) for memoryless workloads.

References

[1]

W. Bux and I. Iliadis. Performance of greedy garbage collection in flash-based solid-state drives. Performance Evaluation, 67(11):1172--1186, 2010.

Digital Library

Google Scholar

[2]

F. Chen, D. A. Koufaty, and X. Zhang. Understanding intrinsic characteristics and system implications of flash memory based solid state drives. In ACM SIGMETRICS Performance Evaluation Review, volume 37, pages 181--192. ACM, 2009.

Digital Library

Google Scholar

[3]

P. Desnoyers. Analytic modeling of ssd write performance. In Proceedings of the 5th Annual International Systems and Storage Conference, page 12. ACM, 2012.

Digital Library

Google Scholar

[4]

X. Haas and X. Hu. The fundamental limit of flash random write performance: Understanding, analysis and performance modelling. Technical report, IBM Research Report, 2010/3/31, 2010.

Google Scholar

[5]

X.-Y. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka. Write amplification analysis in flash-based solid state drives. In Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, page 10. ACM, 2009.

Digital Library

Google Scholar

[6]

Y. Li, P. P. Lee, and J. Lui. Stochastic modeling of large-scale solid-state storage systems: analysis, design tradeoffs and optimization. In Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems, pages 179--190. ACM, 2013.

Digital Library

Google Scholar

[7]

W.-H. Lin and L.-P. Chang. Dual greedy: Adaptive garbage collection for page-mapping solid-state disks. In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2012, pages 117--122. IEEE, 2012.

Digital Library

Google Scholar

[8]

B. Van Houdt. A mean field model for a class of garbage collection algorithms in flash-based solid state drives. In ACM SIGMETRICS Performance Evaluation Review, volume 41, pages 191--202. ACM, 2013.

Digital Library

Google Scholar

[9]

B. Van Houdt. Performance of garbage collection algorithms for flash-based solid state drives with hot/cold data. Performance Evaluation, 70(10):692--703, 2013.

Digital Library

Google Scholar

Cited By

View all

Gu YLiu LWu CLi JGuo M(2024)Ada-WL: An Adaptive Wear-Leveling Aware Data Migration Approach for Flexible SSD Array Scaling in ClustersIEEE Transactions on Computers10.1109/TC.2024.339849373:8(1967-1982)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TC.2024.3398493
Luo LYu DLv YShi L(2023)Critical Data Backup with Hybrid Flash-Based Consumer DevicesACM Transactions on Architecture and Code Optimization10.1145/363152921:1(1-23)Online publication date: 6-Nov-2023
https://dl.acm.org/doi/10.1145/3631529
Lange TNaor JYadgar G(2023)Offline and Online Algorithms for SSD ManagementCommunications of the ACM10.1145/359620566:7(129-137)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3596205
Show More Cited By

Recommendations

Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Garbage collection hints
HiPEAC'05: Proceedings of the First international conference on High Performance Embedded Architectures and Compilers

This paper shows that Appel-style garbage collectors often make suboptimal decisions both in terms of when and how to collect. We argue that garbage collection should be done when the amount of live bytes is low (in order to minimize the collection cost)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 43, Issue 2

September 2015

79 pages

ISSN:0163-5999

DOI:10.1145/2825236

Editor:
Giuliano Casale
Imperial College London, London

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2015

Published in SIGMETRICS Volume 43, Issue 2

Check for updates

Qualifiers

Short-paper

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
217
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)3

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gu YLiu LWu CLi JGuo M(2024)Ada-WL: An Adaptive Wear-Leveling Aware Data Migration Approach for Flexible SSD Array Scaling in ClustersIEEE Transactions on Computers10.1109/TC.2024.339849373:8(1967-1982)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TC.2024.3398493
Luo LYu DLv YShi L(2023)Critical Data Backup with Hybrid Flash-Based Consumer DevicesACM Transactions on Architecture and Code Optimization10.1145/363152921:1(1-23)Online publication date: 6-Nov-2023
https://dl.acm.org/doi/10.1145/3631529
Lange TNaor JYadgar G(2023)Offline and Online Algorithms for SSD ManagementCommunications of the ACM10.1145/359620566:7(129-137)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1145/3596205
Van Houdt B(2023)On the Cost of Near-Perfect Wear Leveling in Flash-Based SSDsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/35768558:1-2(1-22)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1145/3576855
Lv YShi LLi QGao CSong YLuo LZhang Y(2023)MGC: Multiple-Gray-Code for 3D NAND Flash based High-Density SSDs2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10070946(122-136)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10070946
Doekemeijer KTehrany NChandrasekaran BBjørling MTrivedi A(2023)Performance Characterization of NVMe Flash Devices with Zoned Namespaces (ZNS)2023 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER52292.2023.00018(118-131)Online publication date: 31-Oct-2023
https://doi.org/10.1109/CLUSTER52292.2023.00018
Jiao ZBhimani JKim BAnwar ASkourtis DKannan SMa X(2022)Wear leveling in SSDs considered harmfulProceedings of the 14th ACM Workshop on Hot Topics in Storage and File Systems10.1145/3538643.3539750(72-78)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3538643.3539750
Althaus EBerenbrink PBrinkmann ASteiner R(2022)On the Optimality of the Greedy Garbage Collection Strategy for SSDs2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS54860.2022.00017(78-88)Online publication date: Jul-2022
https://doi.org/10.1109/ICDCS54860.2022.00017
Cheng WLuo MZeng LWang YBrinkmann A(2022)Lifespan-based garbage collection to improve SSD's reliability and performanceJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.02.006164:C(28-39)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.jpdc.2022.02.006
Liu YWang HZhou KLi CWu R(2022)A survey on AI for storageCCF Transactions on High Performance Computing10.1007/s42514-022-00101-34:3(233-264)Online publication date: 23-May-2022
https://doi.org/10.1007/s42514-022-00101-3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Age-based garbage collection

Age-based garbage collection

Garbage collection hints