Space Savings and Design Considerations in Variable Length Deduplication

cover.gifGiridhar Appaji Nag Yasa and P.C. Nagesh.

In this paper, we describe and evaluate a hybrid of a variable length and block based deduplication that is hierarchical in nature.

Explosion of data growth and duplication of data in enterprises has led to the deployment of a variety of deduplication technologies. However not all deduplication technologies serve the needs of every workload. Most prior research in deduplication concentrates on fixed block size (or variable block size at a fixed block boundary) deduplication which provides sub-optimal space efficiency in workloads where the duplicate data is not block aligned. Workloads also differ in the nature of operations and their priorities thereby affecting the choice of the right flavor of deduplication. Object workloads for instance, hold multiple versions of archived documents that have a high degree of duplicate data. They are also write-once read-many in nature and follow a whole object GET, PUT and DELETE model and would be better served by a deduplication strategy that takes care of nonblack aligned changes to data.

In this paper, we describe and evaluate a hybrid of a variable length and block based deduplication that is hierarchical in nature. We are motivated by the following insights from real world data: (a) object workload applications do not do in-place modification of data and hence new versions of objects are written again as a whole (b) significant amount of data among different versions of the same object is shareable but the changes are usually not block aligned. While the second point is the basis for variable length technique, both the above insights motivate our hierarchical deduplication strategy.

We show through experiments with production data-sets from enterprise environments that this provides up to twice the space savings compared to a fixed block deduplication.

In ACM SIGOPS Operating Systems Review, Vol. 46, No. 3, December 2012, pp. 57-64

Resources

Variable_length-dedup_Giridhar.pdf