{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:41:18Z","timestamp":1782834078332,"version":"3.54.5"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T00:00:00Z","timestamp":1699920000000},"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":["ACM Trans. Storage"],"published-print":{"date-parts":[[2023,11,30]]},"abstract":"<jats:p>\n            Most of the data in large-scale storage clusters is erasure coded. At exascale, optimizing erasure codes for low storage overhead, efficient reconstruction, and easy deployment is of critical importance.\n            <jats:italic>Locally recoverable codes (LRCs)<\/jats:italic>\n            have deservedly gained central importance in this field, because they can balance many of these requirements. In our work, we study wide LRCs; LRCs with large number of blocks per stripe and low storage overhead. These codes are a natural next step for practitioners to unlock higher storage savings, but they come with their own challenges. Of particular interest is their\n            <jats:italic>reliability<\/jats:italic>\n            , since wider stripes are prone to more simultaneous failures.\n          <\/jats:p>\n          <jats:p>\n            We conduct a practically minded analysis of several popular and novel LRCs. We find that wide LRC reliability is a subtle phenomenon that is sensitive to several design choices, some of which are overlooked by theoreticians, and others by practitioners. Based on these insights, we construct novel LRCs called\n            <jats:italic>Uniform Cauchy LRCs<\/jats:italic>\n            , which show excellent performance in simulations and a 33% improvement in reliability on unavailability events observed by a wide LRC deployed in a Google storage cluster. We also show that these codes are easy to deploy in a manner that improves their robustness to common maintenance events. Along the way, we also give a remarkably simple and novel construction of distance-optimal LRCs (other constructions are also known), which may be of interest to theory-minded readers.\n          <\/jats:p>","DOI":"10.1145\/3626198","type":"journal-article","created":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T15:42:38Z","timestamp":1696520558000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Practical Design Considerations for Wide Locally Recoverable Codes (LRCs)"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5582-0354","authenticated-orcid":false,"given":"Saurabh","family":"Kadekodi","sequence":"first","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1742-7137","authenticated-orcid":false,"given":"Shashwat","family":"Silas","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5799-0375","authenticated-orcid":false,"given":"David","family":"Clausen","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0913-1459","authenticated-orcid":false,"given":"Arif","family":"Merchant","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11,14]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2800042"},{"key":"e_1_3_2_3_2","unstructured":"Amazon. 2023. Amazon S3 FAQs. Retrieved from https:\/\/aws.amazon.com\/s3\/faqs"},{"key":"e_1_3_2_4_2","unstructured":"Backblaze. 2013\u20132018. Disk Reliability Dataset. Retrieved from https:\/\/www.backblaze.com\/b2\/hard-drive-test-data.html"},{"key":"e_1_3_2_5_2","unstructured":"Backblaze. 2013\u20132018. Erasure coding used by Backblaze. Retrieved from https:\/\/www.backblaze.com\/blog\/reed-solomon\/"},{"key":"e_1_3_2_6_2","volume-title":"IEEE International Symposium on Information Theory (ISIT\u201915)","author":"Balaji S. B.","year":"2015","unstructured":"S. B. Balaji and P. Vijay Kumar. 2015. On partial maximally-recoverable and maximally-recoverable codes. In IEEE International Symposium on Information Theory (ISIT\u201915)."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-022-01020-8"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2700859"},{"key":"e_1_3_2_9_2","unstructured":"Shimrit Ben-Yair. 2020. Updating Google Photos\u2019 storage policy to build for the future. Retrieved from https:\/\/blog.google\/products\/photos\/storage-changes\/"},{"key":"e_1_3_2_10_2","unstructured":"Johannes Bloemer Malik Kalfane Richard Karp Marek Karpinski Michael Luby and David Zuckerman. 1995. An XOR-Based Erasure-Resilient Coding Scheme . University of California Berkeley."},{"key":"e_1_3_2_11_2","unstructured":"Eric Brewer. 2018. Spinning Disks and Their Cloudy Future. Retrieved from https:\/\/www.usenix.org\/node\/194391"},{"key":"e_1_3_2_12_2","volume-title":"Disks for Data Centers","author":"Brewer Eric","year":"2016","unstructured":"Eric Brewer, Lawrence Ying, Lawrence Greenfield, Robert Cypher, and Theodore T\u2019so. 2016. Disks for Data Centers. Technical Report. Google."},{"key":"e_1_3_2_13_2","volume-title":"International Symposium on Network Coding (NetCod\u201913)","author":"Cadambe Viveck","year":"2013","unstructured":"Viveck Cadambe and Arya Mazumdar. 2013. An upper bound on the size of locally recoverable codes. In International Symposium on Network Coding (NetCod\u201913). IEEE."},{"key":"e_1_3_2_14_2","article-title":"A construction of maximally recoverable codes with order-optimal field size","author":"Cai Han","year":"2021","unstructured":"Han Cai, Ying Miao, Moshe Schwartz, and Xiaohu Tang. 2021. A construction of maximally recoverable codes with order-optimal field size. IEEE Trans. Inf. Theor. (2021).","journal-title":"IEEE Trans. Inf. Theor."},{"key":"e_1_3_2_15_2","first-page":"37","volume-title":"USENIX Annual Technical Conference (USENIX ATC 13)","author":"Cidon Asaf","year":"2013","unstructured":"Asaf Cidon, Stephen Rumble, Ryan Stutsman, Sachin Katti, John Ousterhout, and Mendel Rosenblum. 2013. Copysets: Reducing the frequency of data loss in cloud storage. In USENIX Annual Technical Conference (USENIX ATC 13). 37\u201348."},{"key":"e_1_3_2_16_2","volume-title":"USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910)","author":"Ford Daniel","year":"2010","unstructured":"Daniel Ford, Fran\u00e7ois Labelle, Florentina I. Popovici, Murray Stokely, Van-Anh Truong, Luiz Barroso, Carrie Grimes, and Sean Quinlan. 2010. Availability in globally distributed storage systems.. In USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910)."},{"key":"e_1_3_2_17_2","volume-title":"Redundant Disk Arrays: Reliable, Parallel Secondary Storage","author":"Gibson Garth Alan","year":"1991","unstructured":"Garth Alan Gibson. 1991. Redundant Disk Arrays: Reliable, Parallel Secondary Storage. Ph. D. Dissertation. University of California, Berkeley."},{"key":"e_1_3_2_18_2","volume-title":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Gopalan Parikshit","year":"2017","unstructured":"Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, and Sergey Yekhanin. 2017. Maximally recoverable codes for grid-like topologies. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2332338"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2208937"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3176807"},{"key":"e_1_3_2_22_2","volume-title":"Electronic Colloquium on Computational Complexity (ECCC\u201917).","author":"Gopi Sivakanth","year":"2017","unstructured":"Sivakanth Gopi, Venkatesan Guruswami, and Sergey Yekhanin. 2017. On maximally recoverable local reconstruction codes. In Electronic Colloquium on Computational Complexity (ECCC\u201917)."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2990981"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2019.2921540"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3023110"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.23919\/SpringSim.2019.8732912"},{"key":"e_1_3_2_27_2","article-title":"Locally recoverable codes with availability  \\(t\\lt = 2\\)  from fiber products of curves","author":"Haymaker Kathryn","year":"2016","unstructured":"Kathryn Haymaker, Beth Malmskog, and Gretchen Matthews. 2016. Locally recoverable codes with availability \\(t\\lt = 2\\) from fiber products of curves. arXiv preprint arXiv:1612.03841 (2016).","journal-title":"arXiv preprint arXiv:1612.03841"},{"key":"e_1_3_2_28_2","volume-title":"USENIX File and Storage Technologies Conference (FAST\u201921)","author":"Hu Yuchong","year":"2021","unstructured":"Yuchong Hu, Liangfeng Cheng, Qiaori Yao, Patrick P. C. Lee, Weichun Wang, and Wei Chen. 2021. Exploiting combined locality for wide-stripe erasure coding in distributed storage. In USENIX File and Storage Technologies Conference (FAST\u201921)."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2435204.2435207"},{"key":"e_1_3_2_30_2","volume-title":"USENIX Annual Technical Conference (ATC\u201912)","author":"Huang Cheng","year":"2012","unstructured":"Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin. 2012. Erasure coding in windows azure storage. In USENIX Annual Technical Conference (ATC\u201912)."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2901492"},{"key":"e_1_3_2_32_2","volume-title":"DISK-ADAPTIVE REDUNDANCY: Tailoring Data Redundancy to Disk-reliability Heterogeneity in Cluster Storage Systems","author":"Kadekodi Saurabh","year":"2020","unstructured":"Saurabh Kadekodi. 2020. DISK-ADAPTIVE REDUNDANCY: Tailoring Data Redundancy to Disk-reliability Heterogeneity in Cluster Storage Systems. Ph. D. Dissertation. Carnegie Mellon University."},{"key":"e_1_3_2_33_2","volume-title":"USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201922)","author":"Kadekodi Saurabh","year":"2022","unstructured":"Saurabh Kadekodi, Francisco Maturana, Sanjith Athlur, Arif Merchant, K. V. Rashmi, and Gregory R. Ganger. 2022. Tiger: Disk-adaptive redundancy without placement restrictions. In USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201922)."},{"key":"e_1_3_2_34_2","volume-title":"USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920)","author":"Kadekodi Saurabh","year":"2020","unstructured":"Saurabh Kadekodi, Francisco Maturana, Suhas Jayaram Subramanya, Juncheng Yang, K. V. Rashmi, and Gregory R. Ganger. 2020. PACEMAKER: Avoiding HeART attacks in storage clusters with disk-adaptive redundancy. In USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201920)."},{"key":"e_1_3_2_35_2","volume-title":"USENIX File and Storage Technologies Conference (FAST\u201919)","author":"Kadekodi Saurabh","year":"2019","unstructured":"Saurabh Kadekodi, K. V. Rashmi, and Gregory R. Ganger. 2019. Cluster storage systems gotta have HeART: Improving storage efficiency by exploiting disk-reliability heterogeneity. In USENIX File and Storage Technologies Conference (FAST\u201919)."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381832"},{"key":"e_1_3_2_37_2","unstructured":"Yin Li Hao Wang Xuebin Zhang Ning Zheng Shafa Dahandeh and Tong Zhang. 2017. Facilitating magnetic recording technology scaling for data center hard disk drives through filesystem-level transparent local erasure coding. In USENIX File and Storage Technologies Conference in 2017 ."},{"key":"e_1_3_2_38_2","article-title":"New constructions of optimal locally recoverable codes via good polynomials","author":"Liu Jian","year":"2017","unstructured":"Jian Liu, Sihem Mesnager, and Lusheng Chen. 2017. New constructions of optimal locally recoverable codes via good polynomials. IEEE Trans. Inf. Theor. (2017).","journal-title":"IEEE Trans. Inf. Theor."},{"key":"e_1_3_2_39_2","article-title":"Maximally recoverable local reconstruction codes from subspace direct sum systems","author":"Liu Shu","year":"2021","unstructured":"Shu Liu and Chaoping Xing. 2021. Maximally recoverable local reconstruction codes from subspace direct sum systems. arXiv preprint arXiv:2111.03244 (2021).","journal-title":"arXiv preprint arXiv:2111.03244"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2021.3083320"},{"key":"e_1_3_2_41_2","article-title":"Constructions of locally recoverable codes which are optimal","author":"Micheli Giacomo","year":"2019","unstructured":"Giacomo Micheli. 2019. Constructions of locally recoverable codes which are optimal. IEEE Trans. Inf. Theor. (2019).","journal-title":"IEEE Trans. Inf. Theor."},{"key":"e_1_3_2_42_2","first-page":"1","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912)","author":"Nightingale Edmund B.","year":"2012","unstructured":"Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, and Yutaka Suzue. 2012. Flat datacenter storage. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912). 1\u201315."},{"key":"e_1_3_2_43_2","unstructured":"Geoffrey Noer and David Petrie Moulton. 2021. How Cloud Storage Delivers 11 Nines of Durability\u2014and How You Can Help. Retrieved from https:\/\/cloud.google.com\/blog\/products\/storage-data-transfer\/understanding-cloud-storage-11-9s-durability-target"},{"key":"e_1_3_2_44_2","volume-title":"IEEE International Symposium on Information Theory (ISIT\u201912)","author":"Papailiopoulos D. S.","year":"2012","unstructured":"D. S. Papailiopoulos and A. G. Dimakis. 2012. Locally repairable codes. In IEEE International Symposium on Information Theory (ISIT\u201912)."},{"key":"e_1_3_2_45_2","volume-title":"USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201913)","author":"Rashmi K. V.","year":"2013","unstructured":"K. V. Rashmi, Nihar B. Shah, Dikang Gu, Hairong Kuang, Dhruba Borthakur, and Kannan Ramchandran. 2013. A solution to the network challenges of data recovery in erasure-coded distributed storage systems: A study on the Facebook warehouse cluster. In USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201913)."},{"key":"e_1_3_2_46_2","unstructured":"Framing.: Int. Data Corp. 2018 16 The digitization of the world from edge to core"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488339"},{"key":"e_1_3_2_48_2","unstructured":"Seagate. 2018. The Digitization of the World from Edge to Core. Retrieved from https:\/\/www.seagate.com\/files\/www-content\/our-story\/trends\/files\/idc-seagate-dataage-whitepaper.pdf"},{"key":"e_1_3_2_49_2","unstructured":"Mostafa Shahabinejad. 2018. Locally repairable linear block codes for distributed storage systems. Department of Electrical and Computer Engineering at the University of Alberta."},{"key":"e_1_3_2_50_2","volume-title":"IEEE International Symposium on Information Theory (ISIT\u201913)","author":"Silberstein Natalia","year":"2013","unstructured":"Natalia Silberstein, Ankit Singh Rawat, O. Ozan Koyluoglu, and Sriram Vishwanath. 2013. Optimal locally repairable codes via rank-metric codes. In IEEE International Symposium on Information Theory (ISIT\u201913)."},{"key":"e_1_3_2_51_2","volume-title":"IEEE Trans. Inf. Theor.","author":"Tamo Itzhak","year":"2014","unstructured":"Itzhak Tamo and Alexander Barg. 2014. Bounds on locally recoverable codes with multiple recovering sets. In IEEE Trans. Inf. Theor. (2014)"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2321280"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2518663"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2555813"},{"key":"e_1_3_2_55_2","unstructured":"VAST. 2019. Providing Resilience Efficiently. Retrieved from https:\/\/www.usenix.org\/node\/194391"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2020.2998587"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626198","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:57:03Z","timestamp":1750291023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,14]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,11,30]]}},"alternative-id":["10.1145\/3626198"],"URL":"https:\/\/doi.org\/10.1145\/3626198","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,14]]},"assertion":[{"value":"2023-05-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}