Rsync
rsync is a utility for efficiently transferring and synchronizing files between a computer and a storage drive and across networked computers by comparing the modification times and sizes of files.
The rsync utility uses an algorithm invented by Australian computer programmer Andrew Tridgell for efficiently transmitting a structure (such as a file) across a communications link when the receiving computer already has a similar, but not identical, version of the same structure.
The recipient splits its copy of the file into chunks and computes two checksums for each chunk: the MD5 hash, and a weaker but easier to compute ‘rolling checksum’. It sends these checksums to the sender.
The sender computes the checksum for each rolling section in its version of the file having the same size as the chunks used by the recipient’s. While the recipient calculates the checksum only for chunks starting at full multiples of the chunk size, the sender calculates the checksum for all sections starting at any address. If any such rolling checksum calculated by the sender matches a checksum calculated by the recipient, then this section is a candidate for not transmitting the content of the section, but only the location in the recipient’s file instead. In this case, the sender uses the more computationally expensive MD5 hash to verify that the sender’s section and recipient’s chunk are equal. Note that the section in the sender may not be at the same start address as the chunk at the recipient. This allows efficient transmission of files which differ by insertions and deletions. The sender then sends the recipient those parts of its file that did not match, along with information on where to merge existing blocks into the recipient’s version. This makes the copies identical.
Created from: Algorithms to know before system design interviews 202211231052
uid: 202211231059 tags: #distributed-systems #software-engineering #algorithms