{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:16:35Z","timestamp":1784099795376,"version":"3.55.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"7","license":[{"start":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T00:00:00Z","timestamp":1687392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>Flash-based solid-state drives (SSDs) are a key component in most computer systems, thanks to their ability to support parallel I\/O at sub-millisecond latency and consistently high throughput. At the same time, due to the limitations of the flash media, they perform writes out-of-place, often incurring a high internal overhead which is referred to as write amplification. Minimizing this overhead has been the focus of numerous studies by the systems research community for more than two decades. The abundance of system-level optimizations for reducing SSD write amplification, which is typically based on experimental evaluation, stands in stark contrast to the lack of theoretical algorithmic results in this problem domain. To bridge this gap, we explore the problem of reducing write amplification from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm. In the online setting, we first consider algorithms that have no prior knowledge about the input and show that in this case, the greedy algorithm is optimal. Then, we design an online algorithm that uses predictions about the input. We show that when predictions are relatively accurate, our algorithm significantly improves over the greedy algorithm. 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\/3596205","type":"journal-article","created":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T22:47:22Z","timestamp":1687474042000},"page":"129-137","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Offline and Online Algorithms for SSD Management"],"prefix":"10.1145","volume":"66","author":[{"given":"Tomer","family":"Lange","sequence":"first","affiliation":[{"name":"Technion---Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion---Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gala","family":"Yadgar","sequence":"additional","affiliation":[{"name":"Technion---Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"2010 IEEE Globecom Workshops (2010","author":"Agarwal R.","year":"1846","unstructured":"Agarwal, R., Marrow, M. A closed-form expression for write amplification in NAND flash. In 2010 IEEE Globecom Workshops (2010), IEEE, Miami, FL, USA, 1846--1850."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.07.003"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456727.3463784"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2577384"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.04.014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064187"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138041.1138043"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10--15, 2018, volume 80 of Proceedings of Machine Learning Research","author":"Lykouris T.","year":"2018","unstructured":"Lykouris, T., Vassilvitskii, S. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10--15, 2018, volume 80 of Proceedings of Machine Learning Research (2018), PMLR, Stockholm, Sweden, 3302--3311."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435.037"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1416944.1416949"},{"key":"e_1_2_1_11_1","volume-title":"27th IEEE Symposium on Mass Storage Systems and Technologies (MSST) (2011)","author":"Park D.","unstructured":"Park, D., Du, D.H. Hot data identification for flash-based storage systems using multiple Bloom filters. In 27th IEEE Symposium on Mass Storage Systems and Technologies (MSST) (2011) IEEE, Denver, CO, USA."},{"key":"e_1_2_1_12_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Purohit M.","year":"2018","unstructured":"Purohit, M., Svitkina, Z., Kumar, R. 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\u00e8al, Canada) (2018), Curran Associates, Inc., Montreal, Canada, 9684--9693."},{"key":"e_1_2_1_13_1","volume-title":"MSR Cambridge Traces","author":"Trace Repository","year":"2007","unstructured":"SNIA IOTTA Trace Repository. MSR Cambridge Traces, 2007. http:\/\/iotta.snia.org\/traces\/block-io\/388."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3423137"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825261"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3596205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:57Z","timestamp":1750178157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,22]]},"references-count":16,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1145\/3596205"],"URL":"https:\/\/doi.org\/10.1145\/3596205","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,22]]},"assertion":[{"value":"2023-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}