Race condition handling in a system which incrementally updates clients with events that occurred in a cloud-based collaboration platform

• US 9,396,245 B2
• Filed: 01/02/2014
• Issued: 07/19/2016
• Est. Priority Date: 01/02/2013
• Status: Active Grant

• Current Assignee: Box Incorporated
• Original Assignee: Box Incorporated
• Inventors: Mackenzie, David, Spielberg, Miles
• Primary Examiner(s): Lu, Kuen
• Application Number:
  US14/146,658
• Publication Number:
  US 20140188798A1
• Time in Patent Office: 929 Days
• Field of Search: 707/625
• US Class Current: 1/1
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/275 Synchronous replication

Abstract

Techniques are disclosed for race condition handling in a system which incrementally updates clients with what occurred in a cloud-enabled platform. In one embodiment, a method comprises, in response to an event received at a synchronization client which indicates a modification to an item, comparing a sequence identifier of the item in the event with a current sequence identifier of the item. The sequence identifier of the item can be numeric and can monotonically increase as a state of the item changes. The method further comprises, if the sequence identifier in the event is larger than the current sequence identifier of the item, determining a difference between the item'"'"'s state as represented in the event and a current state of the item; and, based on the difference, generating at least one synchronization step to update the current state of the item to the item'"'"'s state as represented in the event.

Claims

1. A method for resolving race conditions when updating remote clients with what occurred in a cloud-based platform, the method comprising:

in response to one or more events received which indicates a modification to at least one item, comparing a sequence identifier of the at least one item in the one or more events with a current sequence identifier of the at least one item, wherein the sequence identifier of the at least one item is numeric and monotonically increases as a state of the at least one item changes,

wherein if the at least one item is a folder and the modification results in the folder entering or leaving a synchronization scope, performing a scan of a tree structure of synchronized folders, wherein the scan includes information regarding (i) all items deleted within a select time period of the scan, or (ii) all unsynchronized folders which are located inside a synchronized folder;

if the sequence identifier in the one or more events received is larger than the current sequence identifier of the at least one item, determining a difference between a state of the at least one item as represented in the one or more events and a current state of the at least one item; and

based on the difference, generating at least one synchronization step to update the current state of the at least one item to the state of the at least one item as represented in the one or more events.

2. The method of claim 1, further comprising:

if the sequence identifier in the one or more events is not larger than the current sequence identifier of the at least one item, discarding the one or more events.

3. The method of claim 1, further comprising:

if the difference does not exist, updating the current sequence identifier of the at least one item to the sequence identifier of the at least one item in the one or more events.

4. The method of claim 1, further comprising:

if the modification is deletion and if the at least one item does not exist, generating a creation event for the at least one item with a mark which indicates the at least one item as deleted.

5. The method of claim 4, wherein the creation event triggers no file system operation but allows persisting of the sequence identifier of the at least one item at a moment when it is deleted.

6. The method of claim 1, further comprising:

identifying a timestamp of the scan; and

discarding all events which occurred before the scan.

7. The method of claim 1, further comprising:

generating a synchronization event for a lowest partially synchronized folder in a path when a last fully synchronized folder is moved out from the path to a new path.

8. The method of claim 1, further comprising:

if there exists nested collaborations and if the modification results in removal of a top-level collaboration, initiating scans on both a former top-level collaborated folder and a current top-level collaborated folder.

9. The method of claim 1, further comprising:

detecting duplicate folder move, copy, synchronization, or unsynchronization events; and

initiating scans only on a first event received.

10. The method of claim 9, wherein the detecting is based on an event identifier other than the sequence identifier.

11. The method of claim 1, wherein the modification is a folder move, wherein the scan is not performed for moves between folders which are already synchronized, and wherein the folder move is logged recursively.

12. The method of claim 1, wherein the scan is not performed for unsynchronization events, and wherein an order in which synchronization and unsynchronization events are executed on the tree is preserved.

13. The method of claim 1, wherein the scan is not performed for echoback move events.

14. The method of claim 1, wherein the at least one item is a file.

15. The method of claim 1, wherein the state of the at least one item changes when a name, a parent folder, or a checksum of the at least one item changes.

16. The method of claim 1, wherein the platform is a collaboration environment shared among a user and collaborators of the user.

17. A system for resolving race conditions when incrementally updating remote clients with what occurred in a cloud-based platform, the system comprising:

a processor;

a memory having stored thereon instructions which, when executed by the processor, cause the processor to;

in response to one or more events received which indicates a modification to at least one item, compare a sequence identifier of the at least one item in the one or more events with a current sequence identifier of the at least one item, wherein the sequence identifier of the at least one item is numeric and monotonically increases as a state of the at least one item changes,

wherein if the at least one item is a folder and the modification results in the folder entering or leaving a synchronization scope, perform a scan of a tree structure of synchronized folders, wherein the scan includes information regarding (i) all items deleted within a select time period of the scan, or (ii) all unsynchronized folders which are located inside a synchronized folder;

if the sequence identifier in the one or more events received is larger than the current sequence identifier of the at least one item, determine a difference between a state of the at least one item as represented in the one or more events and a current state of the at least one item; and

based on the difference, generate at least one synchronization step to update the current state of the at least one item to the state of the at least one item as represented in the one or more events.

18. The system of claim 17, wherein the processor is further caused to:

if the sequence identifier in the one or more events is not larger than the current sequence identifier of the at least one item, discard the one or more events.

19. The system of claim 17, wherein the processor is further caused to:

if the difference does not exist, update the current sequence identifier of the at least one item to the sequence identifier of the at least one item in the one or more events.

20. The system of claim 17, wherein the processor is further caused to:

if the modification is deletion and if the at least one item does not exist, generate a creation event for the at least one item with a mark which indicates the at least one, item as deleted.

21. The system of claim 20, wherein the creation event triggers no file system operation but allows persisting of the sequence identifier of the at least one item at a moment when it is deleted.

22. The system of claim 17, wherein the processor is further caused to:

identify a timestamp of the scan; and

discard all events which occurred before the scan.

23. The system of claim 17, wherein the processor is further caused to:

generate a synchronization event for a lowest partially synchronized folder in a path when a last fully synchronized folder is moved out from the path to a new path.

24. The system of claim 17, wherein the processor is further caused to:

if there exists nested collaborations and if the modification results in removal of a top-level collaboration, initiate scans on both a former top-level collaborated folder and a current top-level collaborated folder.

25. The system of claim 17, wherein the processor is further caused to:

detect duplicate folder move, copy, synchronization, or unsynchronization events; and

initiate scans only on a first event received.

26. The system of claim 25, wherein the detecting is based on an event identifier other than the sequence identifier.

27. The system of claim 17, wherein the modification is a folder move, wherein the scan is not performed for moves between folders which are already synchronized, and wherein the folder move is logged recursively.

28. The system of claim 17, wherein the scan is not performed for unsynchronization events, and wherein an order in which synchronization and unsynchronization events are executed on the tree is preserved.

29. The system of claim 17, wherein the scan is not performed for echoback move events.

30. The system of claim 17, wherein the at least one item is a file.

31. The system of claim 17, wherein the state of the at least one item changes when a name, a parent folder, or a checksum of the at least one item changes.

32. The system of claim 17, wherein the platform is a collaboration environment shared among a user and collaborators of the user.

33. A non-transitory computer readable storage medium having instructions stored thereon, which when executed by one or more processors of a system, cause the system to:

in response to one or more events received which indicates a modification to at least one item, comparing a sequence identifier of the at least one item in the one or more events with a current sequence identifier of the at least one item, wherein the sequence identifier of the at least one item is numeric and monotonically increases as a state of the at least one item changes,

wherein if the at least one item is a folder and the modification results in the folder entering or leaving a synchronization scope, performing a scan of a tree structure of synchronized folders, wherein the scan includes information regarding (i) all items deleted within a select time period of the scan, or (ii) all unsynchronized folders which are located inside a synchronized folder;

if the sequence identifier in the one or more events is larger than the current sequence identifier of the at least one item, determining a difference between a state of the at least one item as represented in the one or more events and a current state of the at least one item; and

based on the difference, generating at least one synchronization step to update the current state of the at least one item to the state of the at least one item as represented in the one or more events.