Messages in this thread | | | Date | Thu, 16 Oct 2003 16:04:48 -0700 | From | jw schultz <> | Subject | Re: Transparent compression in the FS |
| |
On Thu, Oct 16, 2003 at 11:49:27AM -0600, Val Henson wrote: > 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)
Several months ago we encountered the hash collision problem with rsync. This brought about a fair amount of discussion regarding the likelihood of false positives with the result of some code changes. I am not educationally equipped to offer mathematical proofs myself but i can highlight the salient points. If you wish more detail you can look it up in the list archives.
1. Internal collision: The smaller the hash size to data size ratio the greater the likelihood of false positives. A poor quality hash adversely affects this but no matter how good the hash is it remains true.
2. External collision: The smaller hash size to unit count ratio the greater liklihood of false positives. To put it in the extreme: if you have 10,000 blocks you are almost guaranteed to get false positives on a 16 bit hash. This is similar to filling the namespace. It is external collision that was killing rsync on iso images.
Because each hash algorithm has different pathologies multiple hashes are generally better than one but their effective aggregate bit count is less than the sum of the separate bit counts.
The idea of this sort of block level hashing to allow sharing of identical blocks seems attractive but i wouldn't trust any design that did not accept as given that there would be false positives. This means that a write would have to not only hash the block but then if there is a collision do a compare of the raw data. Then you have to add the overhead of having lists of blocks that match a hash value and reference counts for each block itself. Further, every block write would then need to include, at minimum, relinking facilities on the hash lists and hash entry allocations plus the inode block list being updated. Finally in the case of COW due to refcount!=0 you would have to do a block allocation, even when simply overwriting which could cause ENOSPACE when an application was simply rewriting an already allocated block or inside mmap.
-- ________________________________________________________________ J.W. Schultz Pegasystems Technologies email address: jw@pegasys.ws
Remember Cernan and Schmitt - 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/
| |