dm-dedup: device-mapper deduplication target

This is a request for comments for Dmdedup.

Dmdedup is a device-mapper deduplication target. Every write coming to the Dmdedup instance is deduplicated against previously written data. For datasets that contain many duplicates scattered across the disk (e.g., collections of virtual machine disk images and backups) deduplication provides a significant amount of space savings.

To quickly identify duplicates, Dmdedup maintains an index of hashes for all written blocks. A block is a user-configurable unit of deduplication with a default block size of 4KB. Dmdedup's index, along with other deduplication metadata, resides on a separate block device, which we refer to as a metadata device. Although the metadata device can be on any block device, e.g., an HDD or its own partition, for higher performance we recommend to use SSD devices to store metadata.

Dmdedup is designed to support pluggable metadata backends. A metadata backend is responsible for storing metadata: LBN-to-PBN and HASH-to-PBN mappings, allocation maps, and reference counters. (LBN: Logical Block Number, PBN: Physical Block Number). Currently we implemented "cowbtree" and "inram" backends. The cowbtree uses device-mapper persistent API to store metadata. The inram backend stores all metadata in RAM as a hash table.

Our preliminary experiments on real traces (FIU traces from
http://iotta.snia.org/tracetypes/3) demonstrate that Dmdedup can even exceed the performance of a disk drive running ext4. The reasons are that (1) deduplication reduces I/O traffic to the data device, and (2) Dmdedup effectively sequentializes random writes to the data device.

Dmdedup is developed by a joint group of researchers from Stony Brook University, Harvey Mudd College, and EMC. See the documentation patch for more details.

Vasily Tarasov (10):
dm-dedup: main data structures
dm-dedup: core deduplication logic
dm-dedup: hash computation
dm-dedup: implementation of the read-on-write procedure
dm-dedup: COW B-tree backend
dm-dedup: inram backend
dm-dedup: Makefile changes
dm-dedup: Kconfig changes
dm-dedup: status function
dm-dedup: documentation

 Documentation/device-mapper/dm-dedup.txt |   51 ++
 drivers/md/Kconfig                       |    8 +
 drivers/md/Makefile                      |    2 +
 drivers/md/dm-dedup-backend.h            |  114 +++++
 drivers/md/dm-dedup-cbt.c                |  724 ++++++++++++++++++++++++++++
 drivers/md/dm-dedup-cbt.h                |   44 ++
 drivers/md/dm-dedup-hash.c               |  148 ++++++
 drivers/md/dm-dedup-hash.h               |   30 ++
 drivers/md/dm-dedup-kvstore.h            |   51 ++
 drivers/md/dm-dedup-ram.c                |  585 +++++++++++++++++++++++
 drivers/md/dm-dedup-ram.h                |   43 ++
 drivers/md/dm-dedup-rw.c                 |  248 ++++++++++
 drivers/md/dm-dedup-rw.h                 |   19 +
 drivers/md/dm-dedup-target.c             |  760 ++++++++++++++++++++++++++++++
 drivers/md/dm-dedup-target.h             |  100 ++++
 15 files changed, 2927 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/device-mapper/dm-dedup.txt
 create mode 100644 drivers/md/dm-dedup-backend.h
 create mode 100644 drivers/md/dm-dedup-cbt.c
 create mode 100644 drivers/md/dm-dedup-cbt.h
 create mode 100644 drivers/md/dm-dedup-hash.c
 create mode 100644 drivers/md/dm-dedup-hash.h
 create mode 100644 drivers/md/dm-dedup-kvstore.h
 create mode 100644 drivers/md/dm-dedup-ram.c
 create mode 100644 drivers/md/dm-dedup-ram.h
 create mode 100644 drivers/md/dm-dedup-rw.c
 create mode 100644 drivers/md/dm-dedup-rw.h
 create mode 100644 drivers/md/dm-dedup-target.c
 create mode 100644 drivers/md/dm-dedup-target.h

Regarding that documentation: shouldn't the on-disk data structures be documented ? Shouldn't it be documented how dm-dedup recovers from a power failure ? Since different storage devices are used for data and meta-data recovery from a power failure is nontrivial. How is it e.g. guaranteed if a data block has been made persistent (e.g. via REQ_FUA) and the refcount is increased for that data block that neither the data nor the metadata for that data block is lost if a power failure occurs ?

Bart.

Yes, you're right, documentation should be more detailed. Alasdair also pointed me to the format they use in cache.txt and verity.txt files. I'll update dedup.txt to comply with that format and include the information about on-disk structures and behavior in case of a power failure. Will send an updated documentation patch in some time.

The short answer to your question is that we use device-mapper's persistent-data library for storing metadata. The library uses COW B-trees to provide atomicity, consistency, and durability. On REQ_FUA we commit transactions. The allocation of data blocks on a data device ensures that no old blocks are overwritten within a transaction. So, during a write operation, data blocks go straight to the disk, but they become visible only after the transaction is committed (i.e., if power fails in the middle of the transaction, one sees the old image of the device).

I'll explain more details in the documentation patch.

Thanks,
Vasily

Seems dm-devel is missing patches 4, 5 and 7. Do you happen to have the entire series staged in a public git tree somewhere?

Interestingly, I can see 4, 5, and 7 in dm-devel's archive:

https://www.redhat.com/archives/dm-devel/2014-April/author.html

In any case, you can pull the patches from:

git://git.fsl.cs.sunysb.edu/linux-dmdedup.git

Branch: rfc-v1.1

Thanks for looking into this.

Vasily

Seems the redhat mail servers have been misbehaving.

OK, thanks.

Hi,

I haven't been able to get to _really_ reviewing dm-dedup. It isn't anything against you guys.. I've just been quite busy with other tasks.

I did start in on dm-dedup a month or so ago by staging a baseline of your work in a branch here:
http://git.kernel.org/cgit/linux/kernel/git/snitzer/linux.git/log/?h=dm-dedup

I found a few things that didn't look right, but they are more DM-specific mechanics and not anything to do with your approach for accomplishing dedup, see the FIXMEs I added to the documentation file in this commit:
http://git.kernel.org/cgit/linux/kernel/git/snitzer/linux.git/commit/?h=dm-dedup&id=fed855928fba624c7a494db7519c37dcc7c9492d

The reconstruct= param isn't needed. In both dm-thinp and dm-cache we use __superblock_all_zeroes to checks if the metadata device's superblock is all zeros. Ideally dm-dedup would do something comparable.

I'm going to be on paternity leave until Sept. 8. It'd be great if Joe and/or Mikulas took some time to review dm-dedup but I'm not sure if they'll be able to. I do hope to be around to respond to emails periodically but my availability is TBD at this point.

When I get back from leave I'll definitely make dm-dedup a priority if others don't beat me to it.

Hi Mike,

Thanks for your initial reviewing steps! Here is what we plan to do:

1) Address your current comments

2) Few people mentioned that our documentation need to be formatted better and be more detailed. We'll address this.

3) There are several things in dm-dedup that we would like to improve. We will work on that to.

4) We will then post dm-dedup v2 patchset and prepare a fresh git branch. It will definitely happen before you're available in September.

5) If Joe and/or Mikulas can take a look at the code meanwhile - that would be great!

Thank you,
Vasily

I'll do it over the next week.

- Joe

Thanks, try to look at how the other DM targets have tables with arguments that have a fixed position (less flexible than name=value but tools like lvm2 benefit from the rigidity).

Yes, it could be more comprehensive. And it would be nice if it were updated to have the same kind of sections/flow that other targets' Documentation/device-mapper/ files have (e.g. cache.txt and thin-provisioning.txt).

But overall the plan sounds great.

mkfs.xfs crash the dm-dedup driver. mkfs.ext4 worked find though for me.

Thanks
Vivek

Vasily,

I recommend you to add tests into dmts
https://github.com/jthornber/device-mapper-test-suite

This testing framework can eliminate such trivial bugs. And the tests become available to other developers are valuable too.
It's written in Ruby and Joe designed carefully. So it's really easy to add tests.

- Akira

@Vivek, thanks, we'll take a look at it.

@Akira, thanks, we'll add dm test-suite to our testbed.

Vasily