Optimizing file replication using binary comparisons

• US 20050102288A1
• Filed: 11/06/2003
• Published: 05/12/2005
• Est. Priority Date: 11/06/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Hai, Antonoff, Lauren
• Granted Patent: US 7,203,708 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1767 Concurrency control, e.g. optimistic or pessimistic approaches
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Client and server based copies of a file are maintained in synchronicity as changes are made to the file. Data is compared to a previous version known to both the client and server and a highly compressed representation of the differences between the two is generated. These differences, or “diffs”, are then transmitted, and may use extensions to the HTTP (HyperText Transport Protocol) protocol.

Claims

1. A method of maintaining an updated file, comprising:

storing a first copy and a second copy of a base file at a first device;

receiving changes to the first copy at the first device;

determining a first difference between the changed first copy and the second copy;

transmitting the first difference to a server; and

accepting the first difference at the server if the base file at the server is the same as the base file that was stored at the first device, otherwise rejecting the first difference at the server.

2. The method of claim 1, further comprising receiving the first copy of the file at the first device from the server, and making a second copy of the file at the first device, prior to storing the first copy and the second copy of the file at the first device.

3. The method of claim 1, wherein determining the first difference comprises using binary comparisons between the changed first copy and the second copy.

4. The method of claim 1, wherein the first difference is a binary diff.

5. The method of claim 1, wherein if the difference is rejected at the server, then transmitting a second difference from the server to the first device, and applying the second difference to the second copy of the base file stored at the first device.

6. The method of claim 1, further comprising determining if the base file at the server is the same as the base file that was stored on the first device.

7. The method of claim 1, wherein transmitting the first difference comprises utilizing extensions to the HTTP protocol.

8. The method of claim 1, further comprising:

storing a first copy and a second copy of the base file at a second device;

receiving changes to the first copy at the second device;

determining a second difference between the changed first copy and the second copy;

transmitting the second difference to the server; and

accepting the second difference at the server if the base file at the server is the same as the base file that was stored at the second device, otherwise rejecting the second difference at the server.

9. The method of claim 8, further comprising, if rejecting the second difference at the server, then transmitting a third difference to the second client, and applying the third difference to the second copy of the base file stored at the second device.

10. The method of claim 8, further comprising receiving the first copy of the file at the second device from the server, and making a second copy of the file at the second device, prior to storing the first copy and the second copy of the file at the second device.

11. The method of claim 8, wherein determining the second difference comprises using binary comparisons between the changed first copy and the second copy at the second device.

12. The method of claim 8, wherein the second difference is a binary diff.

13. The method of claim 8, further comprising determining if the base file at the server is the same as the base file that was stored on the second device.

14. The method of claim 8, wherein transmitting the second difference comprises utilizing extensions to the HTTP protocol.

15. A computer-readable medium having stored thereon computer-executable instructions for performing a method of maintaining an updated file, comprising:

storing a first copy and a second copy of a base file at a first device;

receiving changes to the first copy at the first device;

determining a first difference between the changed first copy and the second copy;

transmitting the first difference to a server; and

accepting the first difference at the server if the base file at the server is the same as the base file that was stored at the first device, otherwise rejecting the first difference at the server.

16. The computer-readable medium of claim 15, further comprising computer-executable instructions for receiving the first copy of the file at the first device from the server, and making a second copy of the file at the first device, prior to storing the first copy and the second copy of the file at the first device.

17. The computer-readable medium of claim 15, wherein determining the first difference comprises using binary comparisons between the changed first copy and the second copy.

18. The computer-readable medium of claim 15, wherein the first difference is a binary diff.

19. The computer-readable medium of claim 15, further comprising computer-executable instructions for, if the difference is rejected at the server, transmitting a second difference from the server to the first device, and applying the second difference to the second copy of the base file stored at the first device.

20. The computer-readable medium of claim 15, further comprising computer-executable instructions for determining if the base file at the server is the same as the base file that was stored on the first device.

21. The computer-readable medium of claim 15, wherein transmitting the first difference comprises utilizing extensions to the HTTP protocol.

22. The computer-readable medium of claim 15, further comprising computer-executable instructions for:

storing a first copy and a second copy of the base file at a second device;

receiving changes to the first copy at the second device;

determining a second difference between the changed first copy and the second copy;

transmitting the second difference to the server; and

accepting the second difference at the server if the base file at the server is the same as the base file that was stored at the second device, otherwise rejecting the second difference at the server.

23. The computer-readable medium of claim 22, further comprising computer-executable instructions for, if the second difference is rejected at the server, transmitting a third difference to the second client, and applying the third difference to the second copy of the base file stored at the second device.

24. The computer-readable medium of claim 22, further comprising computer-executable instructions for receiving the first copy of the file at the second device from the server, and making a second copy of the file at the second device, prior to storing the first copy and the second copy of the file at the second device.

25. The computer-readable medium of claim 22, wherein determining the second difference comprises using binary comparisons between the changed first copy and the second copy at the second device.

26. The computer-readable medium of claim 22, wherein the second difference is a binary diff.

27. The computer-readable medium of claim 22, further comprising computer-executable instructions for determining if the base file at the server is the same as the base file that was stored on the second device.

28. The computer-readable medium of claim 22, wherein transmitting the second difference comprises utilizing extensions to the HTTP protocol.

29. A system for use in a file synchronization system, comprising:

a storage device for storing a first copy and a second copy of a base file;

an input device for receiving changes to the first copy of the base file; and

a processor for changing the first copy based on the received changes, and determining a difference between the changed first copy and the second copy.

30. The system of claim 29, wherein the difference is a binary difference.

31. The system of claim 29, wherein the base file resides on a server, and further comprising an output device for transmitting the difference to the server.

32. The system of claim 29, wherein the difference is transmitted to the server using extensions to the HTTP protocol.

33. The system of claim 29, further comprising a device for receiving a second difference, wherein the processor applies the second difference to the second copy of the base file to generate a modified second copy, applies the received changes to the modified second copy to generate a third copy, and determines a third difference between the third copy and the modified second copy.

34. The system of claim 33, further comprising an output device for transmitting the third difference to a server.

35. A system for use in a file synchronization system, comprising:

a storage device for storing a base file;

an input device for receiving a difference from a client device; and

a processor for determining if the difference is applicable to the stored base file, and if so, applying the difference to the base file, otherwise indicating to the client device that the difference is rejected.

36. The system of claim 35, wherein the difference is a binary difference.

37. The system of claim 35, wherein the difference is received in the form of extensions to the HTTP protocol.

38. The system of claim 35, wherein if the difference is rejected by the processor, a second difference is retrieved from the storage device and transmitted to the client device via an output device.

39. The system of claim 38, wherein the second difference is received from a second client device.

40. The system of claim 35, wherein the difference is applicable to the stored base file if the base file is the same as a client base file that the client device used to generate to the difference.