Online Deduplication for Databases

ACM SIGMOD International Conference on Management of Data, May 14-19, 2017.

Lianghong Xu, Andrew Pavlo, Sudipta Sengupta*, Gregory R. Ganger

Carnegie Mellon University
*Micrososft Research


dbDedup 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, dbDedup uses byte-level delta encoding of individual records within the database to achieve greater savings. dbDedup’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 dbDedup in a distributed NoSQL DBMS and analyzed its properties using four real datasets. Our results show that dbDedup 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 blocklevel compression. dbDedup provides both benefits with negligible effect on DBMS throughput or client latency (average and tail).





© 2017. Last updated 9 February, 2017