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

["Ph. Marek" <philipp.marek@bmlv.gv.at>]

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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/