Messages in this thread | | | Date | Thu, 16 Oct 2003 11:49:27 -0600 | From | Val Henson <> | Subject | Re: 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/
| |