{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:13:28Z","timestamp":1784099608787,"version":"3.55.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T00:00:00Z","timestamp":1748304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2025,5,27]]},"abstract":"<jats:p>Recently, flash-based solid state drives (SSDs) have become a primary storage solution due to their advantages over hard-disk drives. Nonetheless, SSD management presents unique challenges. First, SSDs update data by writing a new copy to a clean slot, rather than overwriting old data. Second, SSDs support cleaning of entire blocks, while slots cannot be cleaned individually. Third, when cleaning a block, any valid data it stores must first be rewritten to another location, which adversely affects the SSD endurance and throughput.<\/jats:p>\n          <jats:p>\n            In this work, we address the\n            <jats:italic toggle=\"yes\">SSD management<\/jats:italic>\n            problem, where the objective is to minimize the number of rewrites in SSDs. We approach the problem from a theoretical perspective, analyzing algorithms in a worst-case fashion. Motivated by recent advances in machine learning, we consider a\n            <jats:italic toggle=\"yes\">learning-augmented<\/jats:italic>\n            setting where the algorithm has access to a predictive\n            <jats:italic toggle=\"yes\">oracle,<\/jats:italic>\n            with performance guarantees expressed as a function of the\n            <jats:italic toggle=\"yes\">error<\/jats:italic>\n            in the oracle's output.\n          <\/jats:p>\n          <jats:p>\n            Our main contribution is\n            <jats:italic toggle=\"yes\">Gladiator,<\/jats:italic>\n            a novel online algorithm that optimally leverages predictions to enhance the performance of SSDs. Compared to prior work, Gladiator requires no additional non-volatile memory and is less sensitive to prediction errors. We further demonstrate the effectiveness of Gladiator under reasonable assumptions on the input distribution, and extend it to an extremely efficient offline algorithm. Empirical results confirm its superiority over state-of-the-art practical solutions across diverse SSD workloads.\n          <\/jats:p>","DOI":"10.1145\/3727122","type":"journal-article","created":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T09:43:35Z","timestamp":1749030215000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimal SSD Management with Predictions"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5503-3914","authenticated-orcid":false,"given":"Tomer","family":"Lange","sequence":"first","affiliation":[{"name":"Computer Science Dept., Technion - Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4234-9466","authenticated-orcid":false,"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Computer Science Dept., Technion - Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2701-0260","authenticated-orcid":false,"given":"Gala","family":"Yadgar","sequence":"additional","affiliation":[{"name":"Computer Science Dept., Technion - Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1404014.1404019"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS54860.2022.00017"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568018"},{"key":"e_1_2_1_4_1","volume-title":"International Conference on Machine Learning. PMLR, 969--983","author":"Antoniadis Antonios","year":"2023","unstructured":"Antonios Antoniadis, Christian Coester, Marek Eli\u00e1s, Adam Polak, and Bertrand Simon. 2023a. Mixing predictions for online metric algorithms. In International Conference on Machine Learning. PMLR, 969--983."},{"key":"e_1_2_1_5_1","volume-title":"Online metric algorithms with untrusted predictions. ACM transactions on algorithms","author":"Antoniadis Antonios","year":"2023","unstructured":"Antonios Antoniadis, Christian Coester, Marek Eli\u00e1\u0161, Adam Polak, and Bertrand Simon. 2023b. Online metric algorithms with untrusted predictions. ACM transactions on algorithms, Vol. 19, 2 (2023), 1--34."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_7_1","volume-title":"Strategy-proof scheduling with predictions. arXiv preprint arXiv:2209.04058","author":"Balkanski Eric","year":"2022","unstructured":"Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. 2022. Strategy-proof scheduling with predictions. arXiv preprint arXiv:2209.04058 (2022)."},{"key":"e_1_2_1_8_1","first-page":"732","article-title":"Wear leveling of static areas in flash memory","volume":"6","author":"Ban Amir","year":"2004","unstructured":"Amir Ban. 2004. Wear leveling of static areas in flash memory. US Patent 6,732,221.","journal-title":"US Patent"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings 14","author":"Ben-Aroya Avraham","year":"2006","unstructured":"Avraham Ben-Aroya and Sivan Toledo. 2006. Competitive analysis of flash-memory algorithms. In Algorithms--ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006. Proceedings 14. Springer, 100--111."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38906-1_10"},{"key":"e_1_2_1_11_1","volume-title":"2021 USENIX Annual Technical Conference (USENIX ATC 21)","author":"Bj\u00f8rling Matias","year":"2021","unstructured":"Matias Bj\u00f8rling, Abutalib Aghayev, Hans Holmberg, Aravind Ramesh, Damien Le Moal, Gregory R. Ganger, and George Amvrosiadis. 2021. ZNS: avoiding the block interface tax for flash-based SSDs. In 2021 USENIX Annual Technical Conference (USENIX ATC 21)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38906-1_14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.07.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.2011358"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456727.3463784"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.134"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199903)29:3<267::AID-SPE233>3.0.CO;2-T"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.67"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2577384"},{"key":"e_1_2_1_21_1","volume-title":"Faster matchings via learned duals. Advances in neural information processing systems","author":"Dinitz Michael","year":"2021","unstructured":"Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. 2021. Faster matchings via learned duals. Advances in neural information processing systems, Vol. 34 (2021), 10393--10406."},{"key":"e_1_2_1_22_1","volume-title":"Nicole Megow, and Jens Schl\u00f6ter.","author":"Erlebach Thomas","year":"2022","unstructured":"Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schl\u00f6ter. 2022. Learning-augmented query policies for minimum spanning tree with uncertainty. arXiv preprint arXiv:2206.15201 (2022)."},{"key":"e_1_2_1_23_1","volume-title":"FIFO. In 12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20)","author":"Eytan Ohad","year":"2020","unstructured":"Ohad Eytan, Danny Harnik, Effi Ofer, Roy Friedman, and Ronen Kat. 2020. It's Time to Revisit LRU vs. FIFO. In 12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM53939.2023.10229044"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508244.1508271"},{"key":"e_1_2_1_26_1","volume-title":"14th USENIX Conference on File and Storage Technologies (FAST 16)","author":"Hao Mingzhe","unstructured":"Mingzhe Hao, Gokul Soundararajan, Deepak Kenchammana-Hosekote, Andrew A. Chien, and Haryadi S. Gunawi. 2016. The tail at store: a revelation from millions of hours of disk and SSD deployments. In 14th USENIX Conference on File and Storage Technologies (FAST 16)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064187"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the USENIX","author":"Hitz Dave","year":"1994","unstructured":"Dave Hitz, James Lau, and Michael Malcolm. 1994. File system design for an NFS file server appliance. In Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference (San Francisco, California). USENIX Association, USA."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138041.1138043"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.09.005"},{"key":"e_1_2_1_31_1","volume-title":"FusionRAID: Achieving Consistent Low Latency for Commodity SSD Arrays. In 19th USENIX Conference on File and Storage Technologies (FAST 21)","author":"Jiang Tianyang","year":"2021","unstructured":"Tianyang Jiang, Guangyan Zhang, Zican Huang, Xiaosong Ma, Junyu Wei, Zhiyue Li, and Weimin Zheng. 2021. FusionRAID: Achieving Consistent Low Latency for Commodity SSD Arrays. In 19th USENIX Conference on File and Storage Technologies (FAST 21)."},{"key":"e_1_2_1_32_1","first-page":"14555","article-title":"Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model","volume":"35","author":"Jin Billy","year":"2022","unstructured":"Billy Jin and Will Ma. 2022. Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. Advances in Neural Information Processing Systems, Vol. 35 (2022), 14555--14567.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289881.1289911"},{"key":"e_1_2_1_34_1","volume-title":"Practical Erase Suspension for Modern Low-latency SSDs. In 2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Kim Shine","unstructured":"Shine Kim, Jonghyun Bae, Hakbeom Jang, Wenjing Jin, Jeonghun Gong, Seungyeon Lee, Tae Jun Ham, and Jae W. Lee. 2019. Practical Erase Suspension for Modern Low-latency SSDs. In 2019 USENIX Annual Technical Conference (USENIX ATC 19)."},{"key":"e_1_2_1_35_1","unstructured":"Kingston. 2024. DC600M Series 2.5'' SATA Enterprise SSD Datasheet. https:\/\/www.kingston.com\/datasheets\/sedc600m_en.pdf Accessed: 2025-01--22."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319647.3325829"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491045"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.28"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3596205"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.114"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447579"},{"key":"e_1_2_1_42_1","volume-title":"20th USENIX Conference on File and Storage Technologies (FAST 22)","author":"Maneas Stathis","year":"2022","unstructured":"Stathis Maneas, Kaveh Mahdaviani, Tim Emami, and Bianca Schroeder. 2022. Operational characteristics of SSDs in enterprise storage systems: a large-scale field study. In 20th USENIX Conference on File and Storage Technologies (FAST 22). 165--180."},{"key":"e_1_2_1_43_1","unstructured":"Albert W Marshall Ingram Olkin and Barry C Arnold. 1979. Inequalities: theory of majorization and its applications. (1979)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528087"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2011.5937225"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1416944.1416949"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2210256"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2011.5937216"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.112"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/146941.146943"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3596204"},{"key":"e_1_2_1_52_1","unstructured":"SNIA IOTTA Trace Repository. 2007. MSR Cambridge Traces. http:\/\/iotta.snia.org\/traces\/block-io\/388."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536372"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494232.2465543"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2013.08.010"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316781.3317929"},{"key":"e_1_2_1_57_1","volume-title":"Virtual Conference.","author":"Wei Alexander","year":"2020","unstructured":"Alexander Wei. 2020. Better and simpler learning-augmented online caching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, August 17--19, 2020, Virtual Conference."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3423137"},{"key":"e_1_2_1_59_1","volume-title":"Tiny-Tail Flash: Near-Perfect Elimination of Garbage Collection Tail Latencies in NAND SSDs. In 15th USENIX Conference on File and Storage Technologies (FAST 17)","author":"Yan Shiqin","unstructured":"Shiqin Yan, Huaicheng Li, Mingzhe Hao, Michael Hao Tong, Swaminathan Sundararaman, Andrew A. Chien, and Haryadi S. Gunawi. 2017. Tiny-Tail Flash: Near-Perfect Elimination of Garbage Collection Tail Latencies in NAND SSDs. In 15th USENIX Conference on File and Storage Technologies (FAST 17)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/3357062.3357089"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825261"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2014.6855534"}],"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\/3727122","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:30:45Z","timestamp":1755898245000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,27]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,5,27]]}},"alternative-id":["10.1145\/3727122"],"URL":"https:\/\/doi.org\/10.1145\/3727122","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,27]]},"assertion":[{"value":"2025-06-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}