comparing multiple copies of terrabytes of data?

[Dan Stromberg]

We will soon have 3 copies, for testing purposes, of what should be about
4.5 terrabytes of data.

Rather than cmp'ing twice, to verify data integrity, I was thinking we
could speed up the comparison a bit, by using a python script that does 3
reads, instead of 4 reads, per disk block - with a sufficiently large
blocksize, of course.

My question then is, does python have a high-level API that would
facilitate this sort of thing, or should I just code something up based on
open and read?

Thanks!

[Istvan Albert]

Dan Stromberg wrote:

Rather than cmp'ing twice, to verify data integrity, I was thinking we
could speed up the comparison a bit, by using a python script that does 3

Use the cmp. So what if you must run it twice ... by the way I
really doubt that you could speed up the process in python
.... you'll probably end up with a much slower version

Istvan.

[Josiah Carlson]

Istvan Albert <ia*****@mailbl ocks.com> wrote:

Dan Stromberg wrote:

Rather than cmp'ing twice, to verify data integrity, I was thinking we
could speed up the comparison a bit, by using a python script that does 3

Use the cmp. So what if you must run it twice ... by the way I
really doubt that you could speed up the process in python
... you'll probably end up with a much slower version

In this case you would be wrong. Comparing data on a processor is
trivial (and would be done using Python's C internals anyways if a
strict string equality is all that matters), but IO is expensive.
Reading Terabytes of data is going to be the bottleneck, so reducing IO
is /the/ optimization that can and should be done.

The code to do so is simple:

def compare_3(fn1, fn2, fn3):
f1, f2, f3 = [open(i, 'rb') for i in (fn1, fn2, fn3)]
b = 2**20 #tune this as necessary
p = -1
good = 1
while f1.tell() < p:
p = f1.tell()
if f1.read(b) == f2.read(b) == f3.read(b):
continue
print "files differ"
good = 0
break
if good and f1.read(1) == f2.read(1) == f3.read(1) == '':
print "files are identical"
f1.close() #I prefer to explicitly close my file handles
f2.close()
f3.close()
Note that it /may/ be faster to first convert the data into arrays
(module array) to get 2, 4 or 8 byte block comparisons.

- Josiah

[Eddie Corns]

Dan Stromberg <st******@dcs.n ac.uci.edu> writes:

We will soon have 3 copies, for testing purposes, of what should be about
4.5 terrabytes of data. Rather than cmp'ing twice, to verify data integrity, I was thinking we
could speed up the comparison a bit, by using a python script that does 3
reads, instead of 4 reads, per disk block - with a sufficiently large
blocksize, of course. My question then is, does python have a high-level API that would
facilitate this sort of thing, or should I just code something up based on
open and read? Thanks!

Taking a checksum of each file and comparing them would probably be much
faster. A quick test with md5 versus cmp gave me a 10 times speedup. Though,
unexpectedly, running 2 md5 processes in parallel was slower than 2 in
sequence - could be the cheap'n'nasty HD in my desktop, normally I'd expect a
gain here as 1 process CPUs while the other is IOing.

Eddie

[Istvan Albert]

Josiah Carlson wrote:

The code to do so is simple:
.... p = -1
good = 1
while f1.tell() < p:
p = f1.tell()
if f1.read(b) == f2.read(b) == f3.read(b):
continue

....

What is slightly amusing is that your *simple*
solution is actually incorrect. You got the
comparison backwards in the while loop.

Other functional deficiency when compared to
the cmp diffs is that you don't know which
file has changed or which byte differs
.... adding that brings about the potential
for another set of bugs. Then someone else comes along
who knows a little less about python and adds
a little feature to the program that actually
silently breaks it ...

Whether or not it is actually faster remains
to be seen. And that was my whole point,
not to don't dismiss cmp to soon, see how it works
test it, then armed with some real numbers one
can make better decisions.

Istvan.

[Josiah Carlson]

Istvan Albert <ia*****@mailbl ocks.com> wrote:

Josiah Carlson wrote:

The code to do so is simple:
...

> p = -1
> good = 1
> while f1.tell() < p:
> p = f1.tell()
> if f1.read(b) == f2.read(b) == f3.read(b):
> continue

...

What is slightly amusing is that your *simple*
solution is actually incorrect. You got the
comparison backwards in the while loop.

My finger slipped.

Other functional deficiency when compared to
the cmp diffs is that you don't know which
file has changed or which byte differs
... adding that brings about the potential
for another set of bugs. Then someone else comes along
who knows a little less about python and adds
a little feature to the program that actually
silently breaks it ...
You are now talking about code maintenance, which is a separate issue
from "how fast can I compare three files", which was originally asked
about.

Whether or not it is actually faster remains
to be seen. And that was my whole point,
not to don't dismiss cmp to soon, see how it works
test it, then armed with some real numbers one
can make better decisions.

Ok. Let me see. I am using the fastest computer in the apartment; my
wife's 2.26 ghz P4 without hyperthreading, with a gig of memory, running
two 40GB ATA-100 drives. I have created 3x1.5gb files on one of the
drives (I don't have 4.5tb free), which should give us a reasonable
measure, if shy by around 3 orders of magnitude in terms of time.

cmp looks to be taking 0-12% processor, so I was correct in my statement
that it is likely disk bound (unless your disks are 8 times faster or
your processor is 1/10 as fast).

Oh, goodness, it is still going. I've been typing this email for over 8
minutes. It sure would be nice if cmp had a progress bar. At least
then I could know if I should kill it now or wait another few minutes.
To hell with it, I'm going to try the Python version.

*make little fix to code to give me a progress bar, time elapsed, and an
expected total time*

cmp: at least 8 1/2 minutes for the first cmp, was not finished, I
killed it. At least 17 minutes in total;
Python: 15 minutes, 3 seconds to finish it all.

Hrm, that is only around 5 megs/second. I think we can do better (even
if it is already better than cmp)...
New algorithm...
def compare_32(fn1, fn2, fn3):
mn = md5.new
st = time.time()
f1, f2, f3 = [open(i, 'rb') for i in (fn1, fn2, fn3)]
b = 2**20 #tune this as necessary
p = -1
good = 1
total = 1.5*2**30
digs = []
m = mn()
while f1.tell() > p:
p = f1.tell()
digs.append(m.u pdate(f1.read(b )).digest())
if not ((p>>20)&7) and p:
a = 100.0*p/total/3
d = time.time()-st
print "%8.1f%% %8.0f\t\r"%(a,1 00*d/a),
m = mn()
for dig in digs:
if dig != m.update(f2.rea d(b)).digest():
print "files 1 and 2 differ before", f2.tell()
good = 0
break
m = mn()
for dig in digs:
if dig != m.update(f3.rea d(b)).digest():
print "files 1 and 2 differ before", f3.tell()
good = 0
break
if good and f1.read(1) == f2.read(1) == f3.read(1) == '':
print "files are identical"
f1.close() #I prefer to explicitly close my file handles
f2.close()
f3.close()
That new one runs in 5 minutes 15 seconds total, because it exploits the
fact that sequential reads are fast. It does use ~20% processor to
compute the md5s, which only makes a difference if your processor is as
fast as a 400mhz P4.

I'd say that Python wins here. Is that concrete enough for you?
- Josiah

[Josiah Carlson]

Josiah Carlson wrote:

for dig in digs:
if dig != m.update(f2.rea d(b)).digest():
print "files 1 and 2 differ before", f2.tell()
good = 0
break
m = mn()
for dig in digs:
if dig != m.update(f3.rea d(b)).digest():
print "files 1 and 2 differ before", f3.tell()

Oops, copy/paste bug. ^^^^^^^
Should be:
print "files 1 and 3 differ before", f3.tell()

- Josiah

[Josiah Carlson]

Josiah Carlson <jc******@uci.e du> wrote:

Obviously this was running old code as the following lines don't work...

digs.append(m.u pdate(f1.read(b )).digest())
if dig != m.update(f2.rea d(b)).digest():
if dig != m.update(f3.rea d(b)).digest():

Those got split up into:
m.update(f1.rea d(b))
digs.append(m.d igest())

m.update(f2.rea d(b))
if dig != m.digest():

m.update(f3.rea d(b))
if dig != m.digest():

respectively. Gah, I don't like mornings.

- Josiah

[Istvan Albert]

Josiah Carlson wrote:

measure, if shy by around 3 orders of magnitude in terms of time. That new one runs in 5 minutes 15 seconds total, because it exploits the

my point was never to say that it is not possible to write
a better way, nor to imply that you could not do it, I simply
said that there is no easy way around this problem.

Your solution while short and nice is not simple, and
requires quite a bit of knowledge to understand
why and how it works.

other topic ... sometimes I have a hard time visualizing how much
a terrabyte of data actually is, this is a good example
for that, even this optimized algorithm would take over three
days to perform a a simple identity check ...

Istvan.

[Josiah Carlson]

Istvan Albert <ia*****@mailbl ocks.com> wrote:

Josiah Carlson wrote:

measure, if shy by around 3 orders of magnitude in terms of time.

That new one runs in 5 minutes 15 seconds total, because it exploits the

my point was never to say that it is not possible to write
a better way, nor to imply that you could not do it, I simply
said that there is no easy way around this problem.

Funny, I thought the implementation I offered was an easy way. No
easier than to use someone else's code, which took all of 5 minutes to
write.

Your solution while short and nice is not simple, and
requires quite a bit of knowledge to understand
why and how it works.
Anyone who has difficulty understanding the algorithm I offered that
used md5 should seriously consider switching hobbies/jobs. The algorithm
is trivial to understand.

other topic ... sometimes I have a hard time visualizing how much
a terrabyte of data actually is, this is a good example
for that, even this optimized algorithm would take over three
days to perform a a simple identity check ...

It would only take that long if you could only get 15 megs/second from
your drives (it was the main boot drive and the files were fragmented).
At multi-tb data sizes, RAID arrays are common, so read speed is
generally much higher, which would then reduce the running time
significantly.

In the case of multiple drives in a non-raid array, splitting up the
process could linearly scale to the limit of the drive and processor(s)
speed.
- Josiah