{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:45:55Z","timestamp":1792799155235,"version":"4.5.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T00:00:00Z","timestamp":1726272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Basic Research Program for Young Students (Doctoral Students) of the National Natural Science Foundation of China","award":["623B2037"],"award-info":[{"award-number":["623B2037"]}],"id":[{"id":"https:\/\/ror.org\/01h0zpd94","id-type":"ROR","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFB1003305"],"award-info":[{"award-number":["2018YFB1003305"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Key Laboratory of Information Storage System Ministry of Education of China"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>More and more storage systems use erasure code to tolerate faults. It takes pieces of data blocks as input and encodes a small number of parity blocks as output, where these blocks form a stripe. When reconsidering the recovery problem in the multi-stripe level and heterogeneous network clusters, quickly generating an efficient multi-stripe recovery solution that reduces recovery time remains a challenging and time-consuming task. Previous works either use a greedy algorithm that may fall into the local optimal and have low recovery performance or a meta-heuristic algorithm with a long running time and low solution generation efficiency.<\/jats:p>\n                  <jats:p>\n                    In this article, we propose a\n                    <jats:italic>Stripe-schedule Aware Repair<\/jats:italic>\n                    (SARepair) technique for multi-stripe recovery in heterogeneous erasure-coded clusters based on Reed\u2013Solomon code. By carefully examining the metadata of blocks, SARepair intelligently adjusts the recovery solution for each stripe and obtains another multi-stripe solution with less recovery time in a computationally efficient manner. It then tolerates worse solutions to overcome the local optimal and uses a rollback mechanism to adjust search regions to reduce recovery time further. Moreover, instead of reading blocks sequentially from each node, SARepair also selectively schedules the reading order for each block to reduce the memory overhead. We extend SARepair to address the full-node recovery and adapt to the LRC code. We prototype SARepair and show via both simulations and Amazon EC2 experiments that the recovery performance can be improved by up to 59.97% over a state-of-the-art recovery approach while keeping running time and memory overhead low.\n                  <\/jats:p>","DOI":"10.1145\/3664926","type":"journal-article","created":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T07:08:42Z","timestamp":1715584122000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Stripe-schedule Aware Repair in Erasure-coded Clusters with Heterogeneous Star Networks"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0869-3038","authenticated-orcid":false,"given":"Hai","family":"Zhou","sequence":"first","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics, Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4674-6006","authenticated-orcid":false,"given":"Dan","family":"Feng","sequence":"additional","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics, Huazhong University of Science and Techonolgy, wuhan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,14]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Amazon. 2022. Amazon EC2. Retrieved from https:\/\/aws.amazon.com\/"},{"key":"e_1_3_2_3_2","unstructured":"Apache. 2020. Apache Hadoop 3.1.4. Retrieved from https:\/\/hadoop.apache.org\/docs\/r3.1.4\/"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3337821.3337831"},{"key":"e_1_3_2_5_2","unstructured":"ceph. 2014. Erasure coding in ceph. Retrieved from https:\/\/ceph.com\/planet\/erasure-coding-in-ceph\/"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486021"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2054295"},{"key":"e_1_3_2_8_2","unstructured":"eecs. 2014. Jerasure. Retrieved from http:\/\/web.eecs.utk.edu"},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the 9th 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 Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910)."},{"key":"e_1_3_2_10_2","first-page":"225","volume-title":"Proceedings of the International Symposium on Reliable Distributed Systems (SRDS\u201920)","author":"Fu Yingxun","year":"2020","unstructured":"Yingxun Fu, Xun Liu, Jiwu Shu, Zhirong Shen, Shiye Zhang, Jun Wu, Jianyong Duan, and Li Ma. 2020. Device and placement aware framework to optimize single failure recoveries and reads for erasure coded storage system with heterogeneous storage devices. In Proceedings of the International Symposium on Reliable Distributed Systems (SRDS\u201920). IEEE, 225\u2013235."},{"key":"e_1_3_2_11_2","first-page":"136","volume-title":"Proceedings of the IEEE 33rd International Symposium on Reliable Distributed Systems","author":"Fu Yingxun","year":"2014","unstructured":"Yingxun Fu, Jiwu Shu, and Xianghong Luo. 2014. A stack-based single disk failure recovery scheme for erasure coded storage systems. In Proceedings of the IEEE 33rd International Symposium on Reliable Distributed Systems. IEEE, 136\u2013145."},{"key":"e_1_3_2_12_2","unstructured":"Google. 2021. Google Datacenters. Retrieved from http:\/\/www.google.com\/about\/datacenters\/"},{"key":"e_1_3_2_13_2","unstructured":"HDFS. 2021. HDFS Erasure Coding. Retrieved from https:\/\/hadoop.apache.org"},{"key":"e_1_3_2_14_2","first-page":"233","volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies (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 Proceedings of the USENIX Conference on File and Storage Technologies (FAST\u201921). 233\u2013248."},{"issue":"4","key":"e_1_3_2_15_2","article-title":"Optimal repair layering for erasure-coded data centers: From theory to practice","volume":"13","author":"Hu Yuchong","year":"2017","unstructured":"Yuchong Hu, Xiaolu Li, Mi Zhang, Patrick P. C. Lee, Xiaoyang Zhang, Pan Zhou, and Dan Feng. 2017. Optimal repair layering for erasure-coded data centers: From theory to practice. ACM Trans. Stor. 13, 4 (2017).","journal-title":"ACM Trans. Stor."},{"key":"e_1_3_2_16_2","first-page":"15","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX 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 Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201912). 15\u201326."},{"key":"e_1_3_2_17_2","first-page":"567","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Li Runhui","year":"2017","unstructured":"Runhui Li, Xiaolu Li, Patrick P. C. Lee, and Qun Huang. 2017. Repair pipelining for \\(\\lbrace\\) Erasure-Coded \\(\\rbrace\\) storage. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201917). 567\u2013579."},{"key":"e_1_3_2_18_2","first-page":"545","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201919)","author":"Li Zhipeng","year":"2019","unstructured":"Zhipeng Li, Min Lv, Yinlong Xu, Yongkun Li, and Liangliang Xu. 2019. D3: Deterministic data distribution for efficient data reconstruction in erasure-coded distributed storage systems. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201919). IEEE, 545\u2013556."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11277-017-4711-4"},{"key":"e_1_3_2_20_2","first-page":"641","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201921)","author":"Lin Shiyao","year":"2021","unstructured":"Shiyao Lin, Guowen Gong, Zhirong Shen, Patrick P. C. Lee, and Jiwu Shu. 2021. Boosting \\(\\lbrace\\) Full-Node \\(\\rbrace\\) repair in \\(\\lbrace\\) Erasure-Coded \\(\\rbrace\\) Storage. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201921). 641\u2013655."},{"key":"e_1_3_2_21_2","unstructured":"Linux. 2022. iperf. Retrieved from https:\/\/github.com\/esnet\/iperf"},{"key":"e_1_3_2_22_2","unstructured":"Linux man. 2023. Linux TC. Retrieved from https:\/\/linux.die.net\/man\/8\/tc"},{"key":"e_1_3_2_23_2","first-page":"1","volume-title":"Proceedings of the 11th European Conference on Computer Systems","author":"Mitra Subrata","year":"2016","unstructured":"Subrata Mitra, Rajesh Panta, Moo-Ryong Ra, and Saurabh Bagchi. 2016. Partial-parallel-repair (ppr) a distributed technique for repairing erasure coded storage. In Proceedings of the 11th European Conference on Computer Systems. 1\u201316."},{"key":"e_1_3_2_24_2","first-page":"181","volume-title":"Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools","author":"Mubeen Saad","year":"2010","unstructured":"Saad Mubeen and Shashi Kumar. 2010. Designing efficient source routing for mesh topology network on chip platforms. In Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools. IEEE, 181\u2013188."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536234"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1145\/3477132.3483558","volume-title":"Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles","author":"Shan Yingdi","year":"2021","unstructured":"Yingdi Shan, Kang Chen, Tuoyu Gong, Lidong Zhou, Tai Zhou, and Yongwei Wu. 2021. Geometric partitioning: Explore the boundary of optimal erasure code repair. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. 457\u2013471."},{"key":"e_1_3_2_28_2","first-page":"556","volume-title":"Proceedings of the 49th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN\u201919)","author":"Shen Zhirong","year":"2019","unstructured":"Zhirong Shen, Xiaolu Li, and Patrick P. C. Lee. 2019. Fast predictive repair in erasure-coded storage. In Proceedings of the 49th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN\u201919). IEEE, 556\u2013567."},{"key":"e_1_3_2_29_2","first-page":"42","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201920)","author":"Shen Zhirong","year":"2020","unstructured":"Zhirong Shen, Jiwu Shu, Zhijie Huang, and Yingxun Fu. 2020. ClusterSR: Cluster-aware scattered repair in erasure-coded storage. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201920). IEEE, 42\u201351."},{"key":"e_1_3_2_30_2","first-page":"323","volume-title":"Proceedings of the 46th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN\u201916)","author":"Shen Zhirong","year":"2016","unstructured":"Zhirong Shen, Jiwu Shu, and Patrick P. C. Lee. 2016. Reconsidering single failure recovery in clustered file systems. In Proceedings of the 46th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN\u201916). IEEE, 323\u2013334."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2611354.2611370"},{"key":"e_1_3_2_32_2","first-page":"993","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201919)","author":"Wang Zhufan","year":"2019","unstructured":"Zhufan Wang, Guangyan Zhang, Yang Wang, Qinglin Yang, and Jiaji Zhu. 2019. Dayu: Fast and low-interference data recovery in very-large storage systems. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201919). 993\u20131008."},{"key":"e_1_3_2_33_2","first-page":"736","volume-title":"IEEE IEEE Conference on Computer Communications (INFOCOM\u201920)","author":"Xu Liangliang","year":"2020","unstructured":"Liangliang Xu, Min Lv, Zhipeng Li, Cheng Li, and Yinlong Xu. 2020. PDL: A data layout towards fast failure recovery for erasure-coded distributed storage systems. In IEEE IEEE Conference on Computer Communications (INFOCOM\u201920). IEEE, 736\u2013745."},{"issue":"10","key":"e_1_3_2_34_2","first-page":"2386","article-title":"SelectiveEC: Towards balanced recovery load on erasure-coded storage systems","volume":"33","author":"Xu Liangliang","year":"2021","unstructured":"Liangliang Xu, Min Lyu, Qiliang Li, Lingjiang Xie, Cheng Li, and Yinlong Xu. 2021. SelectiveEC: Towards balanced recovery load on erasure-coded storage systems. IEEE Trans. Parallel Distrib. Syst. 33, 10 (2021), 2386\u20132400.","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"e_1_3_2_35_2","first-page":"614","volume-title":"Proceedings of the IEEE 42nd International Conference on Distributed Computing Systems (ICDCS\u201922)","author":"Yao Qiaori","year":"2022","unstructured":"Qiaori Yao, Yuchong Hu, Xinyuan Tu, Patrick PC Lee, Dan Feng, Xia Zhu, Xiaoyang Zhang, Zhen Yao, and Wenjia Wei. 2022. PivotRepair: Fast pipelined repair for erasure-coded hot storage. In Proceedings of the IEEE 42nd International Conference on Distributed Computing Systems (ICDCS\u201922). IEEE, 614\u2013624."},{"issue":"1","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1109\/TC.2013.210","article-title":"Accelerate rdp raid-6 scaling by reducing disk i\/os and xor operations","volume":"64","author":"Zhang Guangyan","year":"2013","unstructured":"Guangyan Zhang, Keqin Li, Jingzhe Wang, and Weimin Zheng. 2013. Accelerate rdp raid-6 scaling by reducing disk i\/os and xor operations. IEEE Trans. Comput. 64, 1 (2013), 32\u201344.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","DOI":"10.1109\/TPDS.2023.3282180","article-title":"Boosting erasure-coded multi-stripe repair in rack architecture and heterogeneous clusters: Design and analysis","author":"Zhou Hai","year":"2023","unstructured":"Hai Zhou and Dan Feng. 2023. Boosting erasure-coded multi-stripe repair in rack architecture and heterogeneous clusters: Design and analysis. IEEE Trans. Parallel Distrib. Syst. (2023).","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3153061"},{"key":"e_1_3_2_39_2","first-page":"664","volume-title":"Proceedings of the IEEE 40th International Conference on Computer Design (ICCD\u201922)","author":"Zhou Hai","year":"2022","unstructured":"Hai Zhou, Dan Feng, and Yuchong Hu. 2022. A stripe-schedule aware repair technique in the heterogeneous network for erasure-coded clusters. In Proceedings of the IEEE 40th International Conference on Computer Design (ICCD\u201922). IEEE, 664\u2013671."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Hai Zhou Dan Feng and Yuchong Hu. 2023. MDTUpdate: A multi-block double tree update technique in heterogeneous erasure-coded clusters. IEEE Transactions on Computers 72 10 (2023) 2808\u20132821.","DOI":"10.1109\/TC.2023.3271064"},{"key":"e_1_3_2_41_2","first-page":"1","volume-title":"Proceedings of the IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN\u201912)","author":"Zhu Yunfeng","year":"2012","unstructured":"Yunfeng Zhu, Patrick P. C. Lee, Liping Xiang, Yinlong Xu, and Lingling Gao. 2012. A cost-based heterogeneous recovery scheme for distributed storage systems with RAID-6 codes. In Proceedings of the IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN\u201912). IEEE, 1\u201312."},{"issue":"8","key":"e_1_3_2_42_2","first-page":"2145","article-title":"Boosting degraded reads in heterogeneous erasure-coded storage systems","volume":"64","author":"Zhu Yunfeng","year":"2014","unstructured":"Yunfeng Zhu, Jian Lin, Patrick P. C. Lee, and Yinlong Xu. 2014. Boosting degraded reads in heterogeneous erasure-coded storage systems. IEEE Trans. Comput. 64, 8 (2014), 2145\u20132157.","journal-title":"IEEE Trans. Comput."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3664926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:03:47Z","timestamp":1750277027000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3664926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,14]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3664926"],"URL":"https:\/\/doi.org\/10.1145\/3664926","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,14]]},"assertion":[{"value":"2024-01-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}