Checksum for multi-gigabyte filesystem images ?
I'm currently looking for a (very) fast way to (more or less reliably) checksum multi-gigabyte filesystem images (namely VMFS), to validate that my somehow compressed image files, once expanded, are still accurate to what the original image used to be. One of the main features of the image files is that they are sparse files, so you'd get bonus points with checksum algorithms that allow fast addition of a huge amount of zeroes.
So far, I've considered Adler-32, Fletcher-32, though I'm unsure how they would accurately detect the kind of bogus output I could get, and also "md5 of md5" or "sha-1 of sha-1" (i.e. calculate the md5 or sha-1 sum of the concatenation of the md5 or sha-1 sums of blocks of some size, where you can pre-calculate the md5 or sha-1 sums for blocks full of zeroes).
Dear lazyweb, do you have any better ideas, before I start looking more seriously at the ideas above?
2009-08-26 23:34:38+0900
Both comments and pings are currently closed.
2009-08-27 00:18:57+0900
I’ve never used rsync in anger, but was browsing through tridge’s PhD thesis on it a few days ago – it seems to have a pretty optimal method for working out whether or not a file of arbitrary size is worth resyncing. Worth a look? Or not?
2009-08-27 03:21:47+0900
You might consider whether a real checksum like sha1 really runs much slower than the ones you’ve mentioned, and whether you can check for a run of zeroes much more easily than you can checksum them; once you’ve read them off disk, you’ve pretty much already lost, so unless you can get information from the kernel on the sparse regions of the files…
2009-08-27 03:31:00+0900
Also, take a look at Skein.
2009-08-27 07:12:04+0900
As previously said, you may want to measure first.
(to see what performance you have wrt. the performance you would like to have).
Some compression tools probably include checksuming, so you may not need checksuming in addition to somehow compression.
If you have the hardware pbzip2 can be fast (that is, the limitation should become the disks, not the cpu).
If you need to be extra careful, you may also want to consider checksuming the files inside the filesystem, rather than the filesystem image (probably not since you want “more or less reliably”).
The time measurements should probably be compared to the time to read the filesystem image or to compress and read the compressed filesystem image.
2009-08-27 07:18:11+0900
Steve Parker: IIRC, rsync does checksums by blocks, and I don’t think it needs to aggregate them.
Anonymous: Reading http://www.schneier.com/skein.html, skein doesn’t sound faster than sha-1. Also, a stripped down version of adler-32 as currently in zlib (I can take some shortcuts due to knowing the block size) is twice as fast as Linus’s sha-1 on an old core duo. And that’s without optimizing the case where I know I have n zero bytes to add, which I do, either because I already need to test that as part of the “compression” process, or I already know I have a bunch of zeroes to write in the “uncompression” process.
Also, on the same old machine, reading from a sparse file is roughly as fast as adler-32 if I read it by blocks of 512 bytes, and 4 times faster by blocks of 16 kB (tested with dd).
2009-08-27 07:24:17+0900
Anonymous: sadly, standard compression tools are very sparse file unaware at uncompression phase and are slow as hell. Compression is also very slow if you want efficient compression. The tool which I need the checksum for is some kind of content aware compression tool, specialized for the filesystem images I need to compress. That’s why I’m looking for some kind of checksum: I want to be sure I don’t break my images, especially considering they are supposed to then be used as automated test cases for vmfs-tools.
2009-08-27 18:55:45+0900
MD6 has some modes specifically designed for multicore processing, and as others have pointed out, Skein probably can do the same. I’m pretty sure you could just calculate the sub-checksum of a zero block once and then reuse that.
Adler32 is fast and reasonably good (at least since you don’t have very short strings), although it’s of course only 32 bits. I’m pretty sure you could write an Adler32 that lets you insert a long string of zeros very efficiently (ie. constant time).
CRC32 is a bit slower, but generally better. Like Adler32 it’s not cryptographic, though, but you don’t sound like you care about that.
You might want to consider at what point speed really matters. An optimized Adler32 implementation can reach several gigabytes per second, and your hard disks are probably slower than that.
/* Steinar */
2009-08-28 06:13:44+0900
If you’re lucky enough to have Xeon 55xx or i7 cpus (nehalem based) in your systems, you could consider using hardware-assisted crc32c. I’ve benchmarked it at about 20x faster than pure software crc32c, doing around 6-8GB/ses. Of course, this will only help if you’re CPU bound and not IO bound