{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:50:00Z","timestamp":1775782200755,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"US-Israel BSF","award":["2018352"],"award-info":[{"award-number":["2018352"]}]},{"name":"ISF","award":["2233\/19 (2027511)"],"award-info":[{"award-number":["2233\/19 (2027511)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,12,14]]},"abstract":"<jats:p>Flash-based solid state drives (SSDs) have gained a central role in the infrastructure of large-scale datacenters, as well as in commodity servers and personal devices. The main limitation of flash media is its inability to support update-in-place: after data has been written to a physical location, it has to be erased before new data can be written to it. Moreover, SSDs support read and write operations in granularity of pages, while erasures are performed on entire blocks, which often contain hundreds of pages. When erasing a block, any valid data it stores must be rewritten to a clean location. As an SSD eventually wears out with progressing number of erasures, the efficiency of the management algorithm has a significant impact on its endurance. In this paper we first formally define the SSD management problem. We then explore this problem from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm that, given any input, performs a negligible number of rewrites (relative to the input length). We also discuss the hardness of the offline problem. In the online setting, we first consider algorithms that have no prior knowledge about the input. We prove that no deterministic algorithm outperforms the greedy algorithm in this setting, and discuss the possible benefit of randomization. We then augment our model, assuming that each request for a page arrives with a prediction of the next time the page is updated. We design an online algorithm that uses such predictions, and show that its performance improves as the prediction error decreases. We also show that the performance of our algorithm is never worse than that guaranteed by the greedy algorithm, even when the prediction error is large. We complement our theoretical findings with an empirical evaluation of our algorithms, comparing them with the state-of-the-art scheme. The results confirm that our algorithms exhibit an improved performance for a wide range of input traces.<\/jats:p>","DOI":"10.1145\/3491045","type":"journal-article","created":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T18:32:19Z","timestamp":1639593139000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Offline and Online Algorithms for SSD Management"],"prefix":"10.1145","volume":"5","author":[{"given":"Tomer","family":"Lange","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gala","family":"Yadgar","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"2010 IEEE Globecom Workshops . 1846--1850","author":"Agarwal R.","unstructured":"R. Agarwal and M. Marrow. 2010. A closed-form expression for write amplification in NAND Flash. In 2010 IEEE Globecom Workshops . 1846--1850."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461818"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921669"},{"key":"e_1_2_1_4_1","unstructured":"Matias Bj\u00f8rling. 2019. New NVMe Specification Defines Zoned Namespaces (ZNS) as Go-To Industry Technology Acceleration Library. https:\/\/nvmexpress.org\/new-nvmetm-specification-defines-zoned-namespaces-zns-as-go-to-industry-technology\/. Accessed: 2021--1--21."},{"key":"e_1_2_1_6_1","volume-title":"IBM Research - Zurich","author":"Bux Werner","year":"2009","unstructured":"Werner Bux. 2009. Performance Evaluation of the Write Operation In Flash-Based Solid-State Drives . IBM Res. rep. RZ 3757, IBM Research - Zurich (2009), 1--29."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.07.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/291069.291036"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456727.3463784"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.67"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301635"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301633"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2577384"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.04.014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196--6774(91)90041-V"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064187"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138041.1138043"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1534530.1534544"},{"key":"e_1_2_1_19_1","unstructured":"X.-Y. Hu and R. Haas. 2010. The fundamental limit of flash random write performance: Understanding analysis and performance modelling . IBM Res. rep. RZ 3771 IBM Research - Zurich (2010) 1--19."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.09.005"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2014.51"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508148.2485957"},{"key":"e_1_2_1_23_1","volume-title":"The Multi-streamed Solid-State Drive. In 6th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage) .","author":"Kang Jeong-Uk","year":"2014","unstructured":"Jeong-Uk Kang, Jeeseok Hyun, Hyunjoo Maeng, and Sangyeun Cho. 2014. The Multi-streamed Solid-State Drive. In 6th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage) ."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854333"},{"key":"e_1_2_1_25_1","volume-title":"Fully Automatic Stream Management for Multi-Streamed SSDs Using Program Contexts. In 17th USENIX Conference on File and Storage Technologies (FAST) .","author":"Kim Taejin","year":"2019","unstructured":"Taejin Kim, Duwon Hong, Sangwook Shane Hahn, Myoungjun Chun, Sungjin Lee, Jooyoung Hwang, Jongyoul Lee, and Jihong Kim. 2019. Fully Automatic Stream Management for Multi-Streamed SSDs Using Program Contexts. In 17th USENIX Conference on File and Storage Technologies (FAST) ."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings 38th Annual Symposium on Foundations of Computer Science. 353--362","author":"Kleinberg J.","unstructured":"J. Kleinberg, R. Motwani, P. Raghavan, and S. Venkatasubramanian. 1997. Storage management for evolving databases. In Proceedings 38th Annual Symposium on Foundations of Computer Science. 353--362."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319647.3325829"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2008.4771793"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCNC.2012.6167472"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\"a ssan","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive Caching with Machine Learned Advice. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\"a ssan, Stockholm, Sweden, July 10--15, 2018 (Proceedings of Machine Learning Research, Vol. 80). PMLR , 3302--3311."},{"key":"e_1_2_1_31_1","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Sergei Vassilvitskii. 2020. Algorithms with Predictions. In Beyond the Worst-Case Analysis of Algorithms, Tim Roughgarden (Ed.). Cambridge University Press, 646--662."},{"key":"e_1_2_1_32_1","first-page":"1","volume-title":"Austin Donnelly, and Antony Rowstron","author":"Narayanan Dushyanth","year":"2008","unstructured":"Dushyanth Narayanan, Austin Donnelly, and Antony Rowstron. 2008. Write Off-loading: Practical Power Management for Enterprise Storage. Trans. Storage , Vol. 4, 3, Article 10 (Nov. 2008), bibinfonumpages10:1--10:23 pages."},{"key":"e_1_2_1_33_1","volume-title":"27th IEEE Symposium on Mass Storage Systems and Technologies (MSST) .","author":"Park Dongchul","unstructured":"Dongchul Park and David H.C. Du. 2011. Hot data identification for flash-based storage systems using multiple Bloom filters. In 27th IEEE Symposium on Mass Storage Systems and Technologies (MSST) ."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/565816.503283"},{"key":"e_1_2_1_35_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving Online Algorithms via ML Predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3--8, 2018, Montr\u00e9 al, Canada . 9684--9693."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.30"},{"key":"e_1_2_1_37_1","volume-title":"FStream: Managing Flash Streams in the File System. In 16th USENIX Conference on File and Storage Technologies (FAST) .","author":"Rho Eunhee","year":"2018","unstructured":"Eunhee Rho, Kanchan Joshi, Seung-Uk Shin, Nitesh Jagadeesh Shetty, Jooyoung Hwang, Sangyeun Cho, Daniel DG Lee, and Jaeheon Jeong. 2018. FStream: Managing Flash Streams in the File System. In 16th USENIX Conference on File and Storage Technologies (FAST) ."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_39_1","unstructured":"SNIA IOTTA Trace Repository. 2007. MSR Cambridge Traces. http:\/\/iotta.snia.org\/traces\/block-io\/388 ."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536372"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-014--9403-0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.08.003"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277332.3277352"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2015.7282824"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3423137"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177886"},{"key":"e_1_2_1_47_1","volume-title":"Reducing Garbage Collection Overhead in SSD Based on Workload Prediction. In 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage) .","author":"Yang Pan","year":"2019","unstructured":"Pan Yang, Ni Xue, Yuqi Zhang, Yangxu Zhou, Li Sun, Wenwen Chen, Zhonggang Chen, Wei Xia, Junke Li, and Kihyoun Kwon. 2019. Reducing Garbage Collection Overhead in SSD Based on Workload Prediction. In 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage) ."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825261"},{"key":"e_1_2_1_49_1","volume-title":"18th Annual Symposium on Foundations of Computer Science (sfcs","author":"Chi-Chin Yao Andrew","year":"1977","unstructured":"Andrew Chi-Chin Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). 222--227."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:06Z","timestamp":1750195506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,14]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,12,14]]}},"alternative-id":["10.1145\/3491045"],"URL":"https:\/\/doi.org\/10.1145\/3491045","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,14]]},"assertion":[{"value":"2021-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}