Optimizing file replication using binary comparisons

• US 7,203,708 B2
• Filed: 11/06/2003
• Issued: 04/10/2007
• 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
• Primary Examiner(s): Alam; Shahid
• Assistant Examiner(s): Fleurantin; Jean Bolte
• Application Number:
  US10/702,863
• Publication Number:
  US 20050102288A1
• Time in Patent Office: 1,251 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 715/500.1, 715/513, 709/217, 709/219, 709248-250, 711/168
• 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 and at a second device;

receiving a first set of changes to the first copy at the first device and a second set of changes to the first copy at the second device;

determining a first difference between the changed first copy and the second copy at the first device, and a second difference between the changed first copy and the second copy at the second device;

transmitting the first difference and the second difference to a server;

receiving the first difference or the second difference first in time at the server;

accepting the difference received first in time at the server if the base file at the server is the same as the base file that was stored at the device associated with the difference received first in time, otherwise rejecting the difference at the server;

rejecting the difference received second in time at the server; and

transmitting a third difference from the server to the device associated with the difference received second in time, and applying the third difference to the second copy of the base file stored at the device.

2. The method of claim 1, further comprising receiving the first copy of the base file at the first device from the server, and making the second copy of the base file at the first device, prior to storing the first copy and the second copy of the base 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 an additional difference from the server to the first device, and applying the additional difference to the second copy of the base file stored at the device associated with the difference received first in time.

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 receiving the first copy of the base file at the second device from the server, and making the second copy of the base file at the second device, prior to storing the first copy and the second copy of the base file at the second device.

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

10. The method of claim 1, wherein the second difference is a binary diff.

11. 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 second device.

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

13. 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 and at a second device;

receiving a first set of changes to the first copy at the first device and a second set of changes to the first copy at the second device;

determining a first difference between the changed first copy and the second copy at the first device, and a second difference between the changed first copy and the second copy at the second device;

transmitting the first difference and the second difference to a server;

receiving the first difference or the second difference first in time at the server;

accepting the difference received first in time at the server if the base file at the server is the same as the base file that was stored at the device associated with the difference received first in time, otherwise rejecting the difference at the server;

rejecting the difference received second in time at the server; and

transmitting a third difference from the server to the device associated with the difference received second in time, and applying the third difference to the second copy of the base file stored at the device.

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

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

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

17. The computer-readable medium of claim 13, further comprising computer-executable instructions for, if the difference is rejected at the server, transmitting an additional difference from the server to the first device, and applying the additional difference to the second copy of the base file stored at the device associated with the difference received first in time.

18. The computer-readable medium of claim 13, 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.

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

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

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

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

23. The computer-readable medium of claim 13, 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.

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