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

Ric Wheeler
2009-05-04T14:45:46Z

On 05/04/2009 10:39 AM, Tomasz Chmielewski wrote:
> Ric Wheeler schrieb:
>
>> One thing in the above scheme that would be really interesting for
>> all possible hash functions is maintaining good stats on hash
>> collisions, effectiveness of the hash, etc. There has been a lot of
>> press about MD5 hash collisions for example - it would be really neat
>> to be able to track real world data on those,
>
> See here ("The hashing function"):
>
> http://backuppc.sourceforge.net/faq/BackupPC.html#some_design_issues
>
> It's not "real world data", but it gives some overview which applies
> here.
>
>

I have lots of first hand "real world" data from 5 years at EMC in the
Centera group where we used various types of hashes to do single
instancing at the file level, but those are unfortunately not public :-)
Note that other parts of EMC do dedup at the block level (Avamar most
notably).

The key to doing dedup at scale is answering a bunch of questions:

(1) Block level or file level dedup?
(2) Inband dedup (during a write) or background dedup?
(3) How reliably can you protect the pool of blocks? How reliably
can you protect the database that maps hashes to blocks?
(4) Can you give users who are somewhat jaded confidence in your
solution (this is where stats come in very handy!)
(5) In the end, dedup is basically a data compression trick - how
effective is it (including the costs of the metadata, etc) compared to
less complex schemes? What does it costs in CPU, DRAM and impact on the
foreground workload?

Dedup is a very active area in the storage world, but you need to be
extremely robust in the face of failure since a single block failure
could (worst case!) lose all stored data in the pool :-)

Regards,

Ric