[lkml]   [2003]   [Oct]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: Transparent compression in the FS
    Val Henson wrote:
    > 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."

    I'm curious if anyone has done any work on using multiple different
    checksums? For example, the cost of checksumming a single block with
    multiple algorithms (sha1+md5+crc32 for a crazy example), and storing
    each checksum (instead of just one sha1 sum), may be faster than reading
    the block off of disk to compare it with the incoming block. OTOH,
    there is still a mathematical possibility (however-more-remote) of a

    With these sorts of schemes, from basic compare-by-hash to one that
    actually checks the data for a collission, you take a hit no matter what
    when writing, but reading is still full-speed-ahead. (if anyone is
    curious, Plan9's venti uses a multi-GB "write buffer", to mitigate the
    effect of the checksumming on throughput)

    So it's easy to tweak the writing algorithms pretty much any which way,
    as long as the outcome is a unique tag for each block. Hash collisions
    between two files, for example, could be resolved easily by making each
    unique tag "$sha1_hash $n", where $n is the unique number
    differentiating two blocks with the same SHA1 hash.


    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:58    [W:0.021 / U:9.208 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site