Data deduplication, though being efficient for redundancy elimination in storage systems, introduces chunk fragmentation which severely decreases restore performance. Rewriting algorithms are proposed to reduce the chunk fragmentation. Typically, the backup software aggregates files into larger “tar” type files for storage. We observe that, in tar type datasets, a large number of Persistent Fragmented Chunks (PFCs) are repeatedly rewritten by state-of-the-art rewriting algorithms in every backup, which severely impacts restore performance. We found that the existence of PFCs is due to the traditional strategy of storing PFCs along with other chunks in the containers to preserve the stream locality, rendering them always stored in the containers with low utilization. We propose DePFC to reduce PFCs. DePFC identifies and removes PFCs from the containers preserving the stream locality, and groups them together, to increase the utilization of containers holding them for the subsequent backup, thus preventing them from being rewritten again. We further propose an FC Buffer to avoid mistaken rewrites of PFCs and grouping PFCs that cause restore cache thrashing together. Experimental results demonstrate that DePFC improves restore performance of state-of-the-art rewriting algorithms by 44.24-89.42 percent, while attaining comparable deduplication efficiency, and FC Buffer further improves restore performance.

Data deduplication, as a proven technology for effective data reduction in backup and archive storage systems, also demonstrates the promise in increasing the logical space capacity of storage caches by removing redundant data. However, our in-depth evaluation of the existing deduplication-aware caching algorithms reveals that they do improve the hit ratios compared to the caching algorithms without deduplication, especially when the cache block size is set to 4KB. But when the block size is larger than 4KB, a clear trend for modern storage systems, their hit ratios are significantly reduced. A slight increase in hit ratios due to deduplicationmay not be able to improve the overall storage performance because of the high overhead created by deduplication. To address this problem, in this paper we propose CDAC, a Content-driven Deduplication-Aware Cache, which focuses on exploiting the blocks' content redundancy and their intensity of content sharing among source addresses in cache management strategies. We have implemented CDAC based on LRU and ARC algorithms, called CDAC-LRU and CDAC-ARC respectively. Our extensive experimental results show that CDACLRU and CDAC-ARC outperform the state-of-the-art deduplication-aware caching algorithms, D-LRU and DARC, by up to 19.49X in read cache hit ratio, with an average of 1.95X under real-world traces when the cache size ranges from 20% to 80% of the working set size and the block size ranges from 4KB to 64 KB.

As promising alternatives in building future main memory systems, emerging non-volatile memory (NVM) technologies can increase memory capacity in a cost-effective and power-efficient way. However, NVM is facing security threats due to its limited write endurance: a malicious adversary can wear out the cells and cause the NVM system to fail quickly. To address this issue, several wear-leveling schemes have been proposed to evenly distribute write traffic in a security-aware manner. In this study, we present a new type of timing attack, remapping timing attack (RTA), based on information leakage from the remapping latency difference in NVM. Our analysis and experimental results show that RTA can cause three of the latest wear-leveling schemes (i.e., region-based start-gap, security refresh, and multi-way wear leveling) to lose their effectiveness in several days (even minutes), causing failure of NVM. To defend against such an attack, we further propose a novel wear-leveling scheme called the ‘security region-based start-gap (security RBSG)’, which is a two-stage strategy using a dynamic Feistel network to enhance the simple start-gap wear leveling with level-adjustable security assurance. The theoretical analysis and evaluation results show that the proposed security RBSG not only performs well when facing traditional malicious attacks, but also better defends against RTA.

Deduplication has been widely used to improve storage efficiency in modern primary and secondary storage systems, yet how deduplication fundamentally affects storage system reliability remains debatable. This paper aims to analyze and compare storage system reliability with and without deduplication in primary workloads using public file system snapshots from two research groups. We first study the redundancy characteristics of the file system snapshots. We then propose a trace-driven, deduplication-aware simulation framework to analyze data loss in both chunk and file levels due to sector errors and whole-disk failures. Compared to without deduplication, our analysis shows that deduplication consistently reduces the damage of sector errors due to intra-file redundancy elimination, but potentially increases the damages of whole-disk failures if the highly referenced chunks are not carefully placed on disk. To improve reliability, we examine a deliberate copy technique that stores and repairs first the most referenced chunks in a small dedicated physical area (e.g., 1 percent of the physical capacity), and demonstrate its effectiveness through our simulation framework.

Chunk-level deduplication, while robust in removing duplicate chunks, introduces chunk fragmentation which decreases restore performance. Rewriting algorithms are proposed to reduce the chunk fragmentation and accelerate the restore speed. Delta compression can remove redundant data between non-duplicate but similar chunks which cannot be eliminated by chunk-level deduplication. Some applications use delta compression as a complement for chunk-level deduplication to attain extra space and bandwidth savings. However, we observe that delta compression introduces a new type of chunk fragmentation stemming from delta compressed chunks whose base chunks are fragmented. We refer to such delta compressed chunks as base-fragmented chunks. We found that this new type of chunk fragmentation has a more severely impact on the restore performance than the chunk fragmentation introduced by chunk-level deduplication and cannot be reduced by existing rewriting algorithms. In order to address the problem due to the base-fragmented chunks, we propose SDC, a scheme that selectively performs delta compression after chunk-level deduplication. The main idea behind SDC is to simulate a restore cache to identify the non-base-fragmented chunks and only perform delta compression for these chunks, thus avoiding the new type of chunk fragmentation. Due to the locality among the backup streams, most of the non-base-fragmented chunks can be detected by the simulated restore cache. Experimental results based on real-world datasets show that SDC improves the restore performance of the delta compressed and deduplicated backup system by 1.93X-7.48X, and achieves 95.5%-97.4% of its compression, while imposing negligible impact on the backup throughput.

Chunk-level deduplication plays an important role in backup storage systems. Existing Content-Defined Chunking (CDC) algorithms, while robust in finding suitable chunk boundaries, face the key challenges of (1) low chunking throughput that renders the chunking stage a serious deduplication performance bottleneck, (2) large chunk size variance that decreases deduplication efficiency, and (3) being unable to find proper chunk boundaries in low-entropy strings and thus failing to deduplicate these strings. To address these challenges, this paper proposes a new CDC algorithm called the Asymmetric Extremum (AE) algorithm. The main idea behind AE is based on the observation that the extreme value in an asymmetric local range is not likely to be replaced by a new extreme value in dealing with the boundaries-shifting problem. As a result, AE has higher chunking throughput, smaller chunk size variance than the existing CDC algorithms, and is able to find proper chunk boundaries in low-entropy strings. The experimental results based on realworld datasets show that AE improves the throughput performance of the state-of-the-art CDC algorithms by more than 2.3×, which is fast enough to remove the chunking-throughput performance bottleneck of deduplication, and accelerates the system throughput by more than 50 percent, while achieving comparable deduplication efficiency.

Erasure codes are widely used in modern distributed storage systems to prevent data loss and server failures. Regenerating codes are a class of erasure codes that trade storage efficiency and computation for repair bandwidth reduction. However, their nonunified coding parameters and huge computational overhead prohibit their applications. Hence, we first propose a family of General Functional Regenerating (GFR) codes with uncoded repair, balancing storage efficiency and repair bandwidth with general parameters. The GFR codes take advantage of a heuristic repair algorithm, which makes efforts to employ as little repair bandwidth as possible to repair a single failure. Second, we also present a scheduled shift multiplication (SSM) algorithm, which accelerates the matrix product over the Galois field by scheduling the order of coding operations, so encoding and repairing of GFR codes can be executed by fast bitwise shifting and exclusive-OR. Compared to the traditional table-lookup multiplication algorithm, our SSM algorithm gains 1.2 to 2 X speedup in our experimental evaluations, with little effect on the repair success rate.

Data compression is widely used in storage systems to reduce redundant data and thus save storage space. One challenge facing the traditional compression approaches is the limitation of compression windows size, which fails to reduce redundancy globally. In this paper, we present DEC, a Deduplication-Enhanced Compression approach that effectively combines deduplication and traditional compressors to increase compression ratio and efficiency. Specifically, we make full use of deduplication to (1) accelerate data reduction by fast but global deduplication and (2) exploit data locality to compress similar chunks by clustering the data chunks which are adjacent to the same duplicate chunks. Our experimental results of a DEC prototype based on real-world datasets show that DEC increases the compression ratio by 20% to 71% and speeds up the compression throughput by 17%~183% compared to traditional compressors, without sacrificing the decompression throughput by leveraging deduplication in traditional compression approaches.

As an emerging memory technology to build the future main memory systems, Phase Change Memory (PCM) can increase memory capacity in a cost-effective and power-efficient way. However, PCM is facing security threats for its limited write endurance: a malicious adversary could wear out the cells and cause the whole PCM system to fail within a short period of time. To address this issue, several wear-leveling schemes have been proposed to evenly distribute write traffic in a security-aware manner. In this work, we present a new type of timing attacknamed Remapping Timing Attack (RTA), based on the asymmetry in write time of PCM. Our analysis and experimental results show that the new revealed RTA can make two state-of-the-art wear-leveling schemes (Region Based Start-Gap and Security Refresh) lose effectiveness, failing PCM with these two techniques in several days (even minutes). In order to defend such attack, we further propose a novel wear-leveling scheme called Security Region Based Start-Gap (Security RBSG), which employs a two-stage strategy and uses a dynamic Feistel Network to enhance the simple Start-Gap wear leveling with level-adjustable security assurance. The theoretical analysis and evaluation results show that the proposed Security RBSG is the most robust wear-leveling methodology so far, which not only better defends the new RTA, but also performs well on the traditional malicious attacks, i.e., Repeated Address Attack and Birthday Paradox Attack.

Data deduplication, an efficient approach to data reduction, has gained increasing attention and popularity in large-scale storage systems due to the explosive growth of digital data. It eliminates redundant data at the file or subfile level and identifies duplicate content by its cryptographically secure hash signature (i.e., collision-resistant fingerprint), which is shown to be much more computationally efficient than the traditional compression approaches in large-scale storage systems. In this paper, we first review the background and key features of data deduplication, then summarize and classify the state-of-the-art research in data deduplication according to the key workflow of the data deduplication process. The summary and taxonomy of the state of the art on deduplication help identify and understand the most important design considerations for data deduplication systems. In addition, we discuss the main applications and industry trend of data deduplication, and provide a list of the publicly available sources for deduplication research and studies. Finally, we outline the open problems and future research directions facing deduplication-based storage systems.

In backup systems, the chunks of each backup are physically scattered after deduplication, which causes a challenging fragmentation problem. We observe that the fragmentation comes into sparse and out-of-order containers. The sparse container decreases restore performance and garbage collection efficiency, while the out-of-order container decreases restore performance if the restore cache is small. In order to reduce the fragmentation, we propose History-Aware Rewriting algorithm (HAR) and Cache-Aware Filter (CAF). HAR exploits historical information in backup systems to accurately identify and reduce sparse containers, and CAF exploits restore cache knowledge to identify the out-of-order containers that hurt restore performance. CAF efficiently complements HAR in datasets where out-of-order containers are dominant. To reduce the metadata overhead of the garbage collection, we further propose a Container-Marker Algorithm (CMA) to identify valid containers instead of valid chunks. Our extensive experimental results from real-world datasets show HAR significantly improves the restore performance by 2.84-175.36 × at a cost of only rewriting 0.5-2.03 percent data.

Erasure codes are widely used in modern distributed storage systems to prevent data loss and server failures. Regenerating codes are a class of erasure codes that trades storage efficiency and computation for repair bandwidth reduction. However, their non-unified coding parameters and huge computation overhead prohibit their applications. Hence, we first propose a family of Functional Regenerating Codes (FRCs) with uncoded repair, balancing storage efficiency and repair bandwidth with general parameters. FRCs take advantage of a heuristic repair algorithm, which makes efforts to employ as little repair bandwidth as possible. Second, we optimize encoding by constructing the generator matrix with a bitmatrix, so encoding of FRCs can be executed by fast bitwise XORs. Further, we also optimize repairing with the Scheduled Shift Multiplication (SSM) algorithm, which accelerates the matrix product over the Galois field during repair. Compared to the traditional table-lookup multiplication algorithm, our SSM algorithm gains 1.2~2X speed-up.

Data deduplication, a space-efficient and bandwidth-saving technology, plays an important role in bandwidth-efficient data transmission in various data-intensive network and cloud applications. Rabin-based and MAXP-based Content-Defined Chunking (CDC) algorithms, while robust in finding suitable cut-points for chunk-level redundancy elimination, face the key challenges of (1) low chunking throughput that renders the chunking stage the deduplication performance bottleneck and (2) large chunk-size variance that decreases deduplication efficiency. To address these challenges, this paper proposes a new CDC algorithm called the Asymmetric Extremum (AE) algorithm. The main idea behind AE is based on the observation that the extreme value in an asymmetric local range is not likely to be replaced by a new extreme value in dealing with the boundaries-shift problem, which motivates AE's use of asymmetric (rather than symmetric as in MAXP) local range to identify cut-points and simultaneously achieve high chunking throughput and low chunk-size variance. As a result, AE simultaneously addresses the problems of low chunking throughput in MAXP and Rabin and high chunk-size variance in Rabin. The experimental results based on four real-world datasets show that AE improves the throughput performance of the state-of-the-art CDC algorithms by 3x while attaining comparable or higher deduplication efficiency.

Nowadays, many customers and enterprises backup their data to cloud storage that performs deduplication to save storage space and network bandwidth. Hence, how to perform secure deduplication becomes a critical challenge for cloud storage. According to our analysis, the state-of-the-art secure deduplication methods are not suitable for cross-user finegrained data deduplication. They either suffer brute-force attacks that can recover files falling into a known set, or incur large computation (time) overheads. Moreover, existing approaches of convergent key management incur large space overheads because of the huge number of chunks shared among users. Our observation that cross-user redundant data are mainly from the duplicate files, motivates us to propose an efficient secure deduplication scheme SecDep. SecDep employs User-Aware Convergent Encryption (UACE) and Multi-Level Key management (MLK) approaches. (1) UACE combines cross-user file-level and inside-user chunk-level deduplication, and exploits different secure policies among and inside users to minimize the computation overheads. Specifically, both of file-level and chunk-level deduplication use variants of Convergent Encryption (CE) to resist brute-force attacks. The major difference is that the file-level CE keys are generated by using a server-aided method to ensure security of cross-user deduplication, while the chunk-level keys are generated by using a user-aided method with lower computation overheads. (2) To reduce key space overheads, MLK uses file-level key to encrypt chunk-level keys so that the key space will not increase with the number of sharing users. Furthermore, MLK splits the file-level keys into share-level keys and distributes them to multiple key servers to ensure security and reliability of file-level keys. Our security analysis demonstrates that SecDep ensures data confidentiality and key security. Our experiment results based on several large real-world datasets show that SecDep is more time-efficient and key-space-efficient than the state-of-the-art secure deduplication approaches.

Data deduplication, an efficient space reduction method, has gained increasing attention and popularity in data-intensive storage systems. Most existing state-of-the-art deduplication methods remove redundant data at either the file level or the chunk level, which incurs unavoidable and significant overheads in time (due to chunking and fingerprinting). These overheads can degrade the write performance to an unacceptable level in a data storage system. In this paper, we propose P-Dedupe, a fast and scalable deduplication system. The main idea behind P-Dedupe is to fully compose pipelined and parallel computations of data deduplication by effectively exploiting the idle resources of modern computer systems with multi-core and many-core processor architectures. Our experimental evaluation of the P-Dedupe prototype based on real-world datasets shows that P-Dedupe speeds up the deduplication write throughput by a factor of 2~4 through pipelining deduplication and parallelizing hash calculation and achieves 80%~250% of the performance of a conventional storage system without data deduplication.