{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:53Z","timestamp":1750308413327,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072214"],"award-info":[{"award-number":["62072214"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"International Cooperation Project of Guangdong Province","award":["2020A0505100040"],"award-info":[{"award-number":["2020A0505100040"]}]},{"name":"Science and Technology Planning Project of Guangzhou","award":["202103000036"],"award-info":[{"award-number":["202103000036"]}]},{"name":"Open Project Program of Wuhan National Laboratory for Optoelectronics","award":["2020WNLOKF006"],"award-info":[{"award-number":["2020WNLOKF006"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2021,11,30]]},"abstract":"<jats:p>\n            Data deduplication techniques construct an index consisting of fingerprint entries to identify and eliminate duplicated copies of repeating data. The bottleneck of disk-based index lookup and data fragmentation caused by eliminating duplicated chunks are two challenging issues in data deduplication. Deduplication-based backup systems generally employ containers storing contiguous chunks together with their fingerprints to preserve data locality for alleviating the two issues, which is still inadequate. To address these two issues, we propose a container utilization based hot fingerprint entry distilling strategy to improve the performance of deduplication-based backup systems. We divide the index into three parts: hot fingerprint entries, fragmented fingerprint entries, and useless fingerprint entries. A container with utilization smaller than a given threshold is called a\n            <jats:italic>sparse container<\/jats:italic>\n            . Fingerprint entries that point to non-sparse containers are hot fingerprint entries. For the remaining fingerprint entries, if a fingerprint entry matches any fingerprint of forthcoming backup chunks, it is classified as a fragmented fingerprint entry. Otherwise, it is classified as a useless fingerprint entry. We observe that hot fingerprint entries account for a small part of the index, whereas the remaining fingerprint entries account for the majority of the index. This intriguing observation inspires us to develop a hot fingerprint entry distilling approach named\n            <jats:italic>HID<\/jats:italic>\n            . HID segregates useless fingerprint entries from the index to improve memory utilization and bypass disk accesses. In addition, HID separates fragmented fingerprint entries to make a deduplication-based backup system directly rewrite fragmented chunks, thereby alleviating adverse fragmentation. Moreover, HID introduces a feature to treat fragmented chunks as unique chunks. This feature compensates for the shortcoming that a Bloom filter cannot directly identify certain duplicated chunks (i.e., the fragmented chunks). To take full advantage of the preceding feature, we propose an evolved HID strategy called\n            <jats:italic>EHID<\/jats:italic>\n            . EHID incorporates a Bloom filter, to which only hot fingerprints are mapped. In doing so, EHID exhibits two salient features: (i) EHID avoids disk accesses to identify unique chunks and the fragmented chunks; (ii) EHID slashes the false positive rate of the integrated Bloom filter. These salient features push EHID into the high-efficiency mode. Our experimental results show our approach reduces the average memory overhead of the index by 34.11% and 25.13% when using the Linux dataset and the FSL dataset, respectively. Furthermore, compared with the state-of-the-art method HAR, EHID boosts the average backup throughput by up to a factor of 2.25 with the Linux dataset, and EHID reduces the average disk I\/O traffic by up to 66.21% when it comes to the FSL dataset. EHID also marginally improves the system's restore performance.\n          <\/jats:p>","DOI":"10.1145\/3459626","type":"journal-article","created":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T01:27:42Z","timestamp":1634434062000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Improving the Performance of Deduplication-Based Backup Systems via Container Utilization Based Hot Fingerprint Entry Distilling"],"prefix":"10.1145","volume":"17","author":[{"given":"Datong","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Computer Science, Jinan University, Guangzhou, Guangdong Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhui","family":"Deng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Jinan University, Guangzhou, Guangdong Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Zhou","sequence":"additional","affiliation":[{"name":"TSYS School of Computer Science, Columbus State University, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yifeng","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Electrical and Computer Engineering, University of Maine, Orono, ME, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao","family":"Qin","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Software Engineering, Auburn University, Alabama, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"FSL. n.d. Traces and Snapshots Public Archive. Retrieved September 13 2021 from http:\/\/tracer.filesystems.org."},{"key":"e_1_3_1_3_2","unstructured":"Kernel.org. n.d. The Linux Kernel Archives. Retrieved September 13 2021 from https:\/\/www.kernel.org."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOT.2009.5366623"},{"key":"e_1_3_1_5_2","volume-title":"Experiencing Data De-duplication: Improving Efficiency and Reducing Capacity Requirements","author":"Biggar Heidi","year":"2007","unstructured":"Heidi Biggar. 2007. Experiencing Data De-duplication: Improving Efficiency and Reducing Capacity Requirements. White Paper. Enterprise Strategy Group."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323311"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/3189759.3189789"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1855840.1855856"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1922649.1922660"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/2643634.2643653"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/2750482.2750507"},{"key":"e_1_3_1_13_2","unstructured":"John Gants. 2010. Digital universe decade\u2014Are you ready? Retrieved September 19 2021 from http:\/\/viewer.media.bitpipe.com\/938044859_264\/1287663101_75\/Digital-Universe.pdf."},{"key":"e_1_3_1_14_2","first-page":"1","article-title":"The digital universe in 2020: Big data, bigger digital shadows, and biggest growth in the Far East","author":"Gantz John","year":"2012","unstructured":"John Gantz and David Reinsel. 2012. The digital universe in 2020: Big data, bigger digital shadows, and biggest growth in the Far East. IDC iView: IDC Analyze the Future 2012 (2012), 1\u201316.","journal-title":"IDC iView: IDC Analyze the Future"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2002181.2002206"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154759"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.187"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2367589.2367600"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837915.1837921"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/2591272.2591292"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1525908.1525917"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2512348"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2485732.2485748"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/502059.502052"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.2011.82"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOTS.2012.32"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362731"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2611778"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/1973333.1973340"},{"key":"e_1_3_1_30_2","article-title":"Fingerprinting by Random Polynomials","author":"Rabin Michael O.","year":"1981","unstructured":"Michael O. Rabin. 1981. Fingerprinting by Random Polynomials. Technical Report. Hebrew University of Jerusalem.","journal-title":"Technical Report."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/2342821.2342845"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/2002181.2002207"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3189759.3189790"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2800763"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/1364813.1364831"},{"key":"e_1_3_1_36_2","volume-title":"Proceedings of the 19th USENIX Conference on File and Storage Technologies","author":"Zou Xiangyu","year":"2021","unstructured":"Xiangyu Zou, Jingsong Yuan, Philip Shilane, Wen Xia, Haijun Zhang, and Wang Xuan. 2021. The dilemma between deduplication and locality: Can both be achieved? In Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST'21)."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459626","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:11Z","timestamp":1750268951000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,11,30]]}},"alternative-id":["10.1145\/3459626"],"URL":"https:\/\/doi.org\/10.1145\/3459626","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}