Hi all<br><br>If soneone asked me, I would answer than verification is necessary and using weaker and small hash is fine.<br>Storing the block with it's hash, marked "non deduplicated" is fine, just dedup it later with a background process when filesystems has some idle iops to spend on it, and mark it "deduplicated" when done.<br>
I've the feeling that tux3 design is neat to do such a thing (multiple trees, just add one to the forest).<br><br>By the way, may the force be with you all, you're doind such a great job here !<br>Let me also know if you need french localization I'm spend my spare time on it !<br>
<br>Michael B.<br><br><div class="gmail_quote">On Wed, Feb 25, 2009 at 1:53 PM, Philipp Marek <span dir="ltr"><<a href="mailto:philipp.marek@emerion.com">philipp.marek@emerion.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">On Mittwoch, 25. Februar 2009, Christensen Stefan wrote:<br>
</div><div class="Ih2E3d">> > -----Original Message-----<br>
> > From: Philipp Marek [mailto:<a href="mailto:philipp.marek@emerion.com">philipp.marek@emerion.com</a>]<br>
> > Sent: Wednesday, February 25, 2009 12:31 PM<br>
> > That's the question ... if it's "cryptographically secure",<br>
> > it means (AFAIU) that it's "hard" to get collisions ... but<br>
> > it's not impossible.<br>
> > Really, it's *guaranteed* that on a large-enough filesystem<br>
> > (some TB, anyone?) you'll get two blocks with the same hash value.<br>
><br>
> With a 512bit hash value from SHA-2(which is considdered<br>
> collision-resistant), you'll probably get a collision roughly<br>
> after 2**256 blocks you hash(Birthday paradox). This equates to<br>
> an extremely large filesystem(2**218 PiB). By using SHA-1(which has<br>
> Some problems, besides is limited size), you'll get a collision<br>
> After about 2**80 blocks. 2**80 blocks is still a very large<br>
> filesystem(2**42 PiB).<br>
</div>Yes, I know. Thank you for calculating ;-)<br>
<div class="Ih2E3d"><br>
> > Therefore I asked whether the risk is acceptable ... there<br>
> > has been some filesystem (I think that was more than 10 years<br>
> > ago, didn't find a link) that tried deduplication by some<br>
> > hash - but got shot down, because without<br>
> > *verification* that the data is identical you might<br>
> > *silently* shoot yourself (and all others) in the foot.<br>
><br>
> By using a large enough hash-value there shouldn't be a problem.<br>
> But it might be a filesystem-option.<br>
</div>My point is - either there *is* verification (then the hash function itself<br>
doesn't matter that much), or there is *none*.<br>
In the latter case you risk trashing your data.<br>
<br>
As the amount of data stored will only grow, there's an increasing risk of<br>
collisions.<br>
<br>
And, if you use a 512 bit hash for 4096*8 bits of data, you have 1/64th of<br>
your storage wasted for the data index alone.<br>
<div class="Ih2E3d"><br>
> > Ok.<br>
> > But if verification is needed anyway, then something *much*<br>
> > simpler (and<br>
> > *much* faster) would be ok, too.<br>
><br>
> Any hash-function that you'll use have a much shorter calculation<br>
> time than any access to rotating media. Even SSD's are slower than<br>
> what a mainstream CPU can calculate secure hashes from.<br>
</div>The calculation itself, yes.<br>
But if you're getting 1MB of data, and have to tell some hardware to do 256<br>
individual SHA2 calculations of 4kB each, you'll have some latency.<br>
<br>
If that's a simple calculation in the CPU, then you can already ask the SSD<br>
for the first (expected) data block after hashing the first 4kB.<br>
<br>
Maybe it's better via extra hardware - I don't know.<br>
I just think that<br>
- a *big* hash, for collision-resistance, takes too much space; and<br>
- a smaller hash has probably collisions in our lifetime.<br>
So take some ASIC or GPU, and use that for a *simple* hash calculation; but<br>
*verify* the block, to make sure that nothing bad happens.<br>
<br>
<br>
Regards,<br>
<br>
Phil<br>
<div><div></div><div class="Wj3C7c"><br>
<br>
_______________________________________________<br>
Tux3 mailing list<br>
<a href="mailto:Tux3@tux3.org">Tux3@tux3.org</a><br>
<a href="http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3" target="_blank">http://mailman.tux3.org/cgi-bin/mailman/listinfo/tux3</a><br>
</div></div></blockquote></div><br>