Reducing Data Fragmentation in Data Deduplication Systems via Partial Repetition and Coding
Yun-Han Li, Jin Sima, Ilan Shomorony and Olgica Milenkovic · 2024
Read Reducing Data Fragmentation in Data Deduplication Systems via Partial Repetition and Coding by Yun-Han Li, Jin Sima, Ilan Shomorony and Olgica Milenkovic (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01407.txt.
Description
Abstract Data deduplication, one of the key features of modern Big Data storage devices, is the process of removing replicas of data chunks stored by different users. Despite the importance of deduplication, several drawbacks of the method, such as storage robustness and file fragmentation, have not been previously analyzed from a theoretical point of view.
Catalog record
| CREATOR | Yun-Han Li, Jin Sima, Ilan Shomorony and Olgica Milenkovic |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 119 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01407
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reducing Data Fragmentation in Data Deduplication Systems via Partial Repetition and Coding Yun-Han Li, Jin Sima, Ilan Shomorony and Olgica Milenkovic Abstract Data deduplication, one of the key features of modern Big Data storage devices, is the process of removing replicas of data chunks stored by different users. Despite the importance of deduplication, several drawbacks of the method, such as storage robustness and file fragmentation, have not been previously analyzed from a theoretical point of view. Storage robustness pertains to ensuring that deduplicated data can be used to reconstruct the original files without service disruptions and data loss. Fragmentation pertains to the problems of placing deduplicated data chunks of different user files in a proximity-preserving linear order, since neighboring chunks of the same file may be stored in sectors far apart on the server. This work proposes a new theoretical model for data fragmentation and introduces novel graph- and coding-theoretic approaches for reducing fragmentation via limited duplication (repetition coding) and coded deduplication (e.g., linear coding). In addition to alleviating issues with fragmentation, limited duplication and coded deduplication can also serve the dual purpose of increasing the robusteness of the system design. The contributions of our work are three-fold. First, we describe a new model for file structures in the form of self-avoiding (simple) paths in specialized graphs. Second, we introduce several new metrics for measuring the fragmentation level in deduplication systems on graph-structured files, including the stretch metric that captures the worst-case “spread” of adjacent data chunks within a file when deduplicated and placed on the server; and, the jump metric that captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. For the stretch metric, we establish a connection between the level of fragmentation and the bandwidth of the file-graph. In particular, we derive lower and upper bounds on degree of fragmentation and describe instances of the problem where repetition and coding reduce fragmentation. The key ideas behind our approach are graph folding and information-theoretic arguments coupled with graph algorithms such as matching. For the jump metric, we provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. Third, we describe how controlled repetition and coded redundancy added after deduplication can ensure valuable trade-offs between the storage volume and the degree of fragmentation. I Introduction Data deduplication is a data management technique employed in modern large-scale data storage systems to increase storage efficiency by removing content replicas of different users [ 1 , 2 , 3 , 4 ] . For example, cloud storage providers such as Microsoft and Dropbox, as well as intelligent data infrastructure companies such as NetApp, actively support deduplication schemes in their storage systems. A typical deduplication algorithm first splits the input files into smaller data subunits, referred to as “chunks” [ 5 , 6 , 7 ] , then removes duplicate data chunks and proceeds to place the chunks on servers. For duplicate chunk identification, one typically uses hash values [ 5 , 6 , 7 ] . The chunk placement is based either on some predetermined protocol or the order of arrival of new chunks. After deduplication, each file is stored in ‘compressed’ form, involving a set of pointers explaining how to assemble it (e.g., a set of hash values pointing to the actual locations of the data chunks and labels indicating their order). During the file restoration phase, the server uses the compressed description to recreate files by retrieving chunks guided by the pointers. The trade-off between the chunk size and the length of the assembly instruction under various chunking strategies is an important practical system compression feature, addressed in [ 5 ] . Since the volume of the assembly instruction data is usually negligible compared to the actual user data, this consideration is irrelevant for protocol-level analyses of deduplication. Although deduplication algorithms provide significant storage savings, they introduce a number of readout issues, including data fragmentation [ 8 ] and data instability [ 9 , 10 ] . Data fragmentation arises due to storing information chunks of a single file at multiple potentially distal locations, which slows down data retrieval and potentially creates problems with accessing large volumes of secondary, unwanted interspersing data. Deduplication instability, on the other hand, refers to the vulnerability to data loss (i.e., lack of robustness) of the file system when only one replica of each chunk is maintained. These problems are partly mitigated in practice by using caches and specialized chunk placements [ 11 ] , as well as ‘incomplete deduplication’ protocols, where not all redundant chunks are removed but only a portion of them, dictated by their popularity [ 1 , 2 ] . Despite the widespread use of deduplication and the many practical implementations of the method, little is known about the theoretical performance limits of such systems with regards to data fragmentation. Prior work [ 4 ] provided a mathematical analysis of the influence of deduplication on distributed storage codes, while [ 5 ] initiated an information-theoretic study of deduplication as a form of compression. Some other works [ 7 , 6 ] focused on examining the influence of errors on chunking and deduplication. None of these contributions considered fragmentation problems or issues associated with partial deduplication and file retrieval robustness. Here, we initiate the first analytical study of the trade-off between storage redundancy and file fragmentation. The key features supporting our analysis are: a) A new model for files that share chunks in terms of self-avoiding (simple) paths/walks in what we call a chunk or file graph . In particular, we model the data as being either generated by a sparse Hamiltonian-path graph in which nodes represent chunks and nodes on connected paths correspond to files to be stored; or, as hierarchical structures whose chunks are organized on a tree. The Hamiltonian path requirement is used to both model a natural linear ordering of concatenated files and to simplify challenging analyses. Similarly, tree models are used to capture chunk organizations in omnipresent hierarchical data; b) Several new metrics for measuring the level of fragmentation, including a worst-case metric which examines the maximum stretch of allotted locations of adjacent data chunks (i.e., the stretch metric ) and a metric that captures the worst-case number of times the location on a server needs to be changed to retrieve a file (i.e., the jump metric ). Average-case metrics, although formally defined in this work will be examined elsewhere. Our main contributions are bounds on the worst-case fragmentation metrics and algorithms for chunk placements that produce provably good fragmentation results. Most importantly, we examine these key features of deduplication systems for the case of completely deduplicated files (for which the solution involves optimization over permutations, i.e., over the symmetric group), partially deduplicated files with data chunk repetitions (repetition-coded deduplication) and coded deduplication , in which the stored chunks may represent linear (or, in general nonlinear) combinations of systematic user chunks. The outlined analysis involves information-theoretic arguments but also strongly relies on results in graph theory pertaining to the graph bandwith and related concepts [ 12 ] , as well as matchings in graphs. In the former