Re: Data Deduplication with the help of an online filesystem check

[Thomas Glanzmann <thomas@glanzmann.de>]

Hello Chris,

> Right now the blocksize can only be the same as the page size.  For
> this external dedup program you have in mind, you could use any
> multiple of the page size.

perfect. Exactly what I need.

> Three days is probably not quite enough ;)  I'd honestly prefer the
> dedup happen entirely in the kernel in a setup similar to the
> compression code.

I see. I think that it wouldn't scale because than all the checksums
need to be stored in memory or at least in an efficient b*tree. For a
1 Tbyte filesystem with 4 kbyte blocks that would mean more 5 G (!)
(assuming a 16 kbyte checksum and 4 byte block identifier and that
leaves out the b*tree overhead for fast searching) of memory.

> But, that would use _lots_ of CPU, so an offline dedup is probably a
> good feature even if we have transparent dedup.

I think that is the right way to go.

> Wire up a userland database that stores checksums and points to
> file, offset tuples

exactly. And if there is a way to retrieve the already calculated
checksums from kernel land, than it would be possible to implement a
,,systemcall'' that gives the kernel a hint of a possible duplicated
block (like providing a list of lists of blocks to the kernel that might
be duplicated because they have the same checksum). Than the kernel code
could dedup the block after byte-byte comparing it.

> Make the ioctl to replace a given file extent if and only if the file
> contents match a given checksum over a range of bytes.  The ioctl should
> be able to optionally do a byte compare of the src and destination pages
> to make 100% sure the data is really the same.

Exactly.

> Make another ioctl to report on which parts of a file have changed
> since a given transaction. This will greatly reduce the time spent
> scanning for new blocks.

That would be perfect. Even better would be a systemcall that reports
all the blocks that have been touched since a specific transaction. Like
a bitmap that sets a ,,1'' for every block that has been touched.

> It isn't painfully hard, but you're looking at about 3 weeks total
> time.

I see, so no quick hack to get it going.

        Thomas