Re: [ANNOUNCE] Btrfs: a copy on write, snapshotting FS

Ph. Marek
2007-06-20T09:18:19Z

On Mittwoch, 20. Juni 2007, Vladislav Bolkhovitin wrote:
> Philipp Matthias Hahn wrote:
> >>>>I would also suggest one more feature: support for block level
> >>>>de-duplication. I mean:
> So, seems ever for file based de-duplication some support from the FS,
> including some kind of ability for different inodes point to the same
> data blocks to store the meta-data, would be needed anyway.
The easy way is to have the inode point to a (shared, reference counted) data
storage, which lists the data - then inodes can share the data, but have
different meta-data.

Ever since I read about filesystems using the files' hash as addressing
mechanism (per some Linus mail on LKML, about 10 years ago) and manber hashes
(http://citeseer.ist.psu.edu/manber94finding.html) I'm thinking about various
ways to use both in a filesystem.

Manber-Hashes allow to split data into similar chunks, which could be
addresses per some cryptographic checksum, and used by several files.

*But*: The boundaries are not at power-of-2 addresses, so the data for
read()/mmap() would have to be rebuild somehow. (Would eg. be necessary
anyway if the data block itself is stored compressed).

The other question I'm still pondering ... File sizes vary very much. If I
have a large project, eg. the kernel, with many thousand files of some 10 kB,
some data could be shared - GPL licenses in files, #include lists, and some
others.
If I have some other data, with files of several hundred megabytes, sharing
gets more interesting ... but what should the right block size (for manber
hashes) be? If it's small, we have to concatenate a lot of blocks to
reconstruct data - if it's big, we might lose many chances for sharing.

And getting good performance, when blocks in the middle of a file have to be
re-splitted, might be a bit of a problem, too ...

Regards,

Phil