lkml.org 
[lkml]   [2003]   [Oct]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Transparent compression in the FS
On Thu, Oct 16, 2003 at 10:29:30AM -0700, Larry McVoy wrote:
> On Wed, Oct 15, 2003 at 11:13:27AM -0400, Jeff Garzik wrote:
> > Josh and others should take a look at Plan9's venti file storage method
> > -- archival storage is a series of unordered blocks, all of which are
> > indexed by the sha1 hash of their contents. This magically coalesces
> > all duplicate blocks by its very nature, including the loooooong runs of
> > zeroes that you'll find in many filesystems. I bet savings on "all
> > bytes in this block are zero" are worth a bunch right there.
>
> The only problem with this is that you can get false positives. Val Hensen
> recently wrote a paper about this. It's really unlikely that you get false
> positives but it can happen and it has happened in the field.

To be fair, I talked to someone who claims that Venti now checks for
hash collisions on writes, but that's not what the original paper
describes and I haven't confirmed it.

The compare-by-hash paper is only 6 pages long, at least take the time
to read it before you start using compare-by-hash:

http://www.usenix.org/events/hotos03/tech/henson.html

Abstract:

"Recent research has produced a new and perhaps dangerous technique
for uniquely identifying blocks that I will call
compare-by-hash. Using this technique, we decide whether two blocks
are identical to each other by comparing their hash values, using a
collision-resistant hash such as SHA-1. If the hash values match,
we assume the blocks are identical without further ado. Users of
compare-by-hash argue that this assumption is warranted because the
chance of a hash collision between any two randomly generated blocks
is estimated to be many orders of magnitude smaller than the chance
of many kinds of hardware errors. Further analysis shows that this
approach is not as risk-free as it seems at first glance."

-VAL (not subscribed to l-k ATM)
-
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/

\
 
 \ /
  Last update: 2005-03-22 13:58    [from the cache]
©2003-2011 Jasper Spaans