Re: Thinking aloud.

Hi,

comparing the checksums of 2 pages is only an indication whether the 
pages are likely to be the same or not. That's because the page size is 
much bigger than the size of the checksum (e.g. 4 kB vs. 8 B). 
Therefore, there are many more possible pages than possible checksums 
(e.g. 256^4096 vs. 256^8), and hence, many different pages will give the 
very same checksum.

Thus, you can't be 100% sure whether 2 pages are identical unless you 
compare the whole page (or you chose a checksum that is 4kB large, which 
is pointless).

However, using sophisticated and reasonably large checksums gets you 
very close to 100%, which might be sufficient. Some P2P networks use a 
that approach: every block of a few MB gets a 16B checksum. If you found 
a block on the net matching the checksum you're looking for, chances are 
good it's the one you're looking for. Chances that 2 blocks have the 
same checksum by pure coincidence are <10^-40.

However, given that we talk about important data and we probably have 
some spare CPU time, I think you might wanna be 100% sure instead of 
just 99.9999999999999...%, and thus you have to go through every byte of 
the page before being sure you can drop the page. To keep you from doing 
that for every page, that's what the checksumming is for. Since this in 
turn takes lots of CPU time, you might do an even quicker checksum 
first. I don't know how many steps make sense here. Each one would keep 
you from wasting too much time on the next step, but takes time itself, 
and increases the code size.

An algorithm might look like:
for ( all pages ) {
step 1. compare 4 bytes (*)
	if they don't match, go to WRITE
	otherwise continue with the next step
step 2. do a quick checksum on 100 bytes (*),
	if they don't match, go to WRITE
	otherwise continue with the next step
step 3. (optional:) a more sophisticated checksum (e.g. SHA1),
	if they don't match, go to WRITE
	otherwise continue with the next step
step 4. a thorough comparison of the 2 pages
	if they don't match, go to WRITE
	otherwise drop the page (i.e. don't write the page)
	and continue with the next one
WRITE: write new page
}

(*) When comparing a few bytes out of a whole page, don't pick the first 
few, cause it might be those that didn't change. Ideally you'd randomly 
pick a few bytes, but I suspect "random" is too expensive. So, instead, 
just pick an even distribution.
As an example: If you have to chose 4 bytes and the page size is 4kB, 
take bytes number 1, 1025, 2049, 3073.

Good luck and best regards

Martin


On 25/10/2012 11:07, Nigel Cunningham wrote:
> Hi.
>
> On 10/23/2012 07:05 PM, Martin Fahr wrote:
>> Hi Nigel,
>>
>> as for the checksums, I wouldn't even bother checksumming the whole
>> page. Checksumming only every 100th byte within the page might be
>> sufficient to give you a good idea whether the page is likely to have
>> changed or not. Obviously, this would not speed up a
>> memory-bandwidth-limited checksum, but saves some CPU cycles and energy.
> Will your data be safe if the checksumming decides the pages are the
> same when they're not (because the 100th bytes matched but ones in
> between didn't) and the changed page isn't written to disk as a result?
> It's better to checksum the whole page.
>> Do you have an idea of how many pages "typically" don't get touched in
>> between two hibernation cycles? I am aware that there's no such thing
>> as typical system or a typical hibernation cycle, yet I suspect it
>> would be good to know very roughly how much improvement could be
>> expected.
> I don't, but that's part of what I'm hoping to find out.
>
> I've started on it today, and so far have a new module that's
> calculating the SHA1 for every page that's written to disk. At the
> moment that's all it's doing, but it already gives useful info:
>
> Booting to init S, my SSD writes a small image at approx 1300MB/s
> without the module enabled and 380MB/s with it. If that's at all
> representative of a 'real' image, we're going to want to see a
> significant portion of the image being the same if speed is going to be
> comparable. Then again, if you're writing a smaller image and getting
> less wear and tear on your drive, perhaps the tradeoff will be worth it.
>
> Next step is to implement recording the checksums and then comparing
> them. That will take longer to do - I know how I'm going to do it, but I
> have other tasks to get on with first.
>> If you didn't plan to do so already, it might be worthwhile to run a
>> simple test on a few systems to find out more. Maybe comparing the
>> uncompressed, unencrypted images from two subsequent hibernation
>> cycles (written to two separate files or partitions on the disk) would
>> do the job?
> Perhaps, but I think just getting on with heading toward implementing
> and seeing what the numbers reveal as we go could be a better way - at
> least that way no effort is wasted if it does prove to be worthwhile.
>> Finally, your work has always been very much appreciated by me. I have
>> to agree with Pedro very much though. Mainline integration of TOI
>> seems to be the most important missing feature and would allow a few
>> million more users to appreciate your work.
> Thanks :)
> _______________________________________________
> TuxOnIce-devel mailing list
> [email protected]
> http://lists.tuxonice.net/listinfo/tuxonice-devel
>