Sharing and synchronizing electronically stored files

• US 9,244,934 B2
• Filed: 04/23/2012
• Issued: 01/26/2016
• Est. Priority Date: 04/23/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Besen, Adam, Cheong, Hwi, DeNeui, Alexander, Pape, Frank, Vasishth, Himanshu
• Primary Examiner(s): BROWN, SHEREE N
• Application Number:
  US13/453,748
• Publication Number:
  US 20130282785A1
• Time in Patent Office: 1,373 Days
• Field of Search: 709/201, 709/205, 709/224, 707/625, 707/802, 707609-615, 707/617, 707/618, 707/620, 707/624, 790/799
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems

Abstract

Aspects of the present disclosure are directed to architectures, methods and systems and structures that facilitate the sharing and synchronization of electronically stored files among and between cloud entities and a number of computers, systems, devices and/or users. One particular exemplary architectural aspect includes the serial processing and ordering of work items associated with file system changes such that correct parallel execution of the work items may proceed resulting in the synchronization of the cloud file system and the client computer file system.

Claims

1. A computer implemented method for dispatching work items that effect sharing and synchronization of electronically stored files between a client file system and a cloud file system, the method comprising:

ordering the work items in a queue from oldest to newest;

sequentially examining from oldest to newest the queued work items;

for a particular work item under examination;

comparing a first set of dependencies with a second set of dependencies to determine whether there is at least one match between the first set of dependencies and the second set of dependencies, wherein;

the first set of dependencies correspond to dependencies affected by the particular work item, and

the second set of dependencies are in a dependency map and includes dependencies affected by a set of previously dispatched work items that are currently being processed by at least one worker thread;

when there is no match,

dispatching the particular work item to one of the at least one worker thread for processing, and

updating the second set of dependencies to reflect the processing of the dispatched particular work item when the one of the at least one worker thread completes the processing; and

when there is at least one match, proceeding to examine a next work item in the queue;

wherein a relative order of the work items in the queue that are not dispatched is maintained.

2. The computer implemented method of claim 1, wherein the entries in the dependency map include inodes of files undergoing synchronization, and wherein the files undergoing synchronization are affected by the operations being performed by the at least one worker thread.

3. The computer implemented method of claim 1, wherein the entries in the dependency map include resourcelDs of files undergoing synchronization and electronically stored in the cloud file system.

4. The computer implemented method of claim 1, wherein the entries in the dependency map include names of files undergoing synchronization.

5. The computer implemented method of claim 1, wherein the ordering, examining and dispatching of work items are performed concurrently with the processing of the set of previously dispatched work items by the at least one worker thread.

6. A computer implemented method of processing work items associated with sharing and synchronization of electronically stored files between a client file system and a cloud file system, the method comprising:

receiving a work item from a queue in which a plurality of work items including the work item are sequentially examined from oldest to newest;

comparing a first set of dependencies with a second set of dependencies to determine whether there is at least one match between the first set of dependencies and the second set of dependencies, wherein;

the first set of dependencies correspond to dependencies affected by the received work item, and

the second set of dependencies are in a dependency map and includes dependencies affected by a previously dispatched work item that is currently being processed by at least one worker thread; and

dispatching the received work item to one of the at least one worker thread if there is no match;

wherein the one of the at least one worker thread processes the dispatched received work item to cause the sharing and synchronization of an electronically stored file between the client file system and the cloud file system.

7. The computer implemented method of claim 6, further comprising enqueueing the received work item in the queue ordered from oldest to newest.

8. The computer implemented method of claim 7, further comprising updating the dependency map to reflect any operations associated with the dispatched received work item.

9. The computer implemented method of claim 8, wherein when the one of the at least one worker thread completes the processing of the dispatched received work item, the method further comprises updating the dependency map to reflect that the processing of the dispatched received work item is complete.

10. The computer implemented method of claim 9, wherein entries in the dependency map include inodes of electronically stored files undergoing synchronization, and wherein the files undergoing synchronization are affected by the operations being performed by the at least one worker thread.

11. The computer implemented method of claim 9, wherein entries in the dependency map include resourcelDs of files electronically stored in the cloud file system undergoing synchronization.

12. The computer implemented method of claim 9, wherein entries in the dependency map include names of electronically stored files undergoing synchronization.

13. A non-transitory computer storage medium having computer executable instructions which when executed by a computer cause the computer to perform operations comprising:

ordering the work items in a queue from oldest to newest;

sequentially examining from oldest to newest the queued work items;

for a particular work item under examination;

comparing a first set of dependencies with a second set of dependencies to determine whether there is at least one match between the first set of dependencies and the second set of dependencies, wherein;

the first set of dependencies correspond to dependencies affected by the particular work item, and

the second set of dependencies are in a dependency map and includes dependencies affected by a set of previously dispatched work items that are currently being processed by at least one worker thread;

when there is no match,

dispatching the particular work item to one of the at least one worker thread for processing; and

when there is at least one match, proceeding to examine a next work item in the queue;

wherein a relative order of the work items in the queue that are not dispatched is maintained; and

wherein the one of the at least one worker thread processes the dispatched work item to cause sharing and synchronization of an electronically stored file between a client file system and a cloud file system.

14. The non-transitory computer storage medium of claim 13, wherein the computer executable instructions further cause the computer to compare a current state of the Cloud file system to a graph to determine any changes to files in the Cloud file system.

15. The non-transitory computer storage medium of claim 13, wherein the computer executable instructions further cause the computer to update the second set of dependencies to reflect the processing of the dispatched particular work item when the one of the at least one worker thread completes the processing.

16. The non-transitory computer storage medium of claim 13, wherein the computer executable instructions further cause the computer to update the dependency map to reflect that the processing of the dispatched work item is complete when the one of the at least one worker thread completes the processing of the dispatched work item.