Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-16-101. April 2016.
Lianghong Xu*, Andrew Pavlo*, Sudipta Sengupta†, Gregory R. Ganger*
* Carnegie Mellon University
† Microsoft Research
dDedup is a similarity-based deduplication scheme for on-line database management systems (DBMSs). Beyond block-level compression of individual database pages or operation log (oplog) messages, as used in today’s DBMSs, dDedup uses byte-level delta encoding of individual records within the database to achieve greater savings. dDedup’s single-pass encoding method can be integrated into the storage and logging components of a DBMS to provide two benefits: (1) reduced size of data stored on disk beyond what traditional compression schemes provide, and (2) reduced amount of data transmitted over the network for replication services. To evaluate our work, we implemented dDedup in a distributed NoSQL DBMS and analyzed its properties using four real datasets. Our results show that dDedup achieves up to 37X reduction in the storage size and replication traffic of the database on its own and up to 61X reduction when paired with the DBMS’s block-level compression. dDedup provides both benefits with negligible effect on DBMS throughput or client latency (average and tail).
KEYWORDS: Deduplication, Databases, Delta Encoding
FULL TR: pdf