[[!tag python rsync]]
This weekend, I was hacking Obnam, my backup program, adding support for using the rsync algorithm for backing up only the changed parts of modified files. I was reminded once again how beautiful rsync is. There also seems to be very few implementations of it in pure Python, which is a shame, since all the C implementations get bogged down in memory management and other trivia.
So I thought I'd whip up a very simplistic version of it just in case someone finds it useful. Code is in bzr at http://code.liw.fi/obsync/bzr/trunk/, and crucial parts are excerpted below.
A note on the implementation: I've aimed at simplicity, not speed. I've
opted to use zlib.adler32
for the weak checksum rather than the rolling
checksum from the original paper: the rolling checksum was fairly slow to
compute in pure Python, so it seemed just as good to use the library function.
The code in the bzr branch also includes a main program to allow a UI slightly similar to the rdiff program, and a shell script to verify that the code actually works, for at least one test case.
(I'm not providing an explanation of how rsync works: I'm throwing out this blog entry in a few minutes' break. Read the paper, or Wikipedia, or ask me to explain in a later blog entry if you're lazy.)
block_size = 4096
def signature(f):
while True:
block_data = f.read(block_size)
if not block_data:
break
yield (zlib.adler32(block_data), hashlib.md5(block_data).digest())
class RsyncLookupTable(object):
def __init__(self, checksums):
self.dict = {}
for block_number, c in enumerate(checksums):
weak, strong = c
if weak not in self.dict:
self.dict[weak] = dict()
self.dict[weak][strong] = block_number
def __getitem__(self, block_data):
weak = zlib.adler32(block_data)
subdict = self.dict.get(weak)
if subdict:
strong = hashlib.md5(block_data).digest()
return subdict.get(strong)
return None
def delta(sigs, f):
table = RsyncLookupTable(sigs)
block_data = f.read(block_size)
while block_data:
block_number = table[block_data]
if block_number:
yield (block_number * block_size, len(block_data))
block_data = f.read(block_size)
else:
yield block_data[0]
block_data = block_data[1:] + f.read(1)
def patch(outputf, deltas, old_file):
for x in deltas:
if type(x) == str:
outputf.write(x)
else:
offset, length = x
old_file.seek(offset)
outputf.write(old_file.read(length))