IN DISTRIBUTED COMPUTING

CROSS-REFERENCE TO RELATED APPLICATION(S)

[0001] This application claims the benefit of United States Provisional Application Serial No. 62/671 ,931 titled“METHOD AND APPARATUS FOR CONFLICT RESOLUTION” filed May 15, 2018, which is incorporated herein by reference for all purposes in its entirety.

BACKGROUND

[0002] One of the defining features of mobile devices is the fact that one can never count on being online. Loss of connectivity is a fact of life, and so are slow networks and choppy connections. But people still expect their apps to work. This means that there may be two or more users making changes to the same piece of data independently, thus creating conflicts. This can happen even with perfect connectivity because the latency of communicating between the mobile device and the server may be slow enough that two or more mobile devices can end up creating conflicting changes at the same time.

SUMMARY

[0003] Embodiments are directed to resolving conflicts that arise in changes made to data by multiple computing devices. The embodiments resolve a data conflict through the application of rules to the data manipulation operations performed by the computing devices. In some embodiments, although the data is shared among multiple computing devices, each computing device may have a copy of the shared data. The rules ensure that data at each of the multiple computing devices will eventually be consistent.

[0004] When changes are made to a data object, e.g., by a user associated with a computing device, the computing device generates changesets corresponding to the data manipulation operations. In some embodiments, a changeset contains instructions corresponding to a data manipulation operation performed on a data object. Each of the computing devices can generate their own changesets representing data manipulation operations performed on the data object at the respective computing devices. The data is synchronized by exchanging these changesets between the computing devices and merging the changesets on each of the computing devices. A conflict can arise when two changesets are merged on a computing device. The embodiments can resolve the conflict by merging the two changesets based on a set of merging rules. The merging rules are defined as a function of the type of data manipulation operations in each of the two changesets and a timestamp associated with each of the two changesets. For example, if a first changeset, which is generated at a first computing device, represents a delete operation on a data object at the first computing device and a second changeset, which is generated at a second computing device, represents an updating a value of an attribute of the data object at the second computing device, the delete operations emerges as a winner in the conflict and the update operation is discarded as part of the merge operation. The merge operation is executed at both the devices. In another example, if the first changeset represents a“set” operation that sets an attribute of the data object to a first value and the second changeset also represents a“set” operation that sets an attribute of the data object to a second value, the operation that has a later timestamp emerges as a winner in the merge operation.

[0005] Each of the computing devices upload their changesets to a server computing device (“server”), which stores changesets in the order they are received. Whenever a computing device synchronizes with the server, the computing device can download the changesets of other computing devices from the server and execute the merge operations on the downloaded changesets. BRIEF DESCRIPTION OF THE DRAWINGS

[0006] FIG. 1 is a block diagram of an environment in which the disclosed embodiments can be implemented.

[0007] FIG. 2A is a block diagram of an example for merging local changesets with remote changesets at a first client device, consistent with various

embodiments.

[0008] FIG. 2B is a block diagram of another example for merging local changesets with remote changesets at the first client device, consistent with various embodiments.

[0009] FIG. 2C is an example timeline of changesets, consistent with various embodiments.

[0010] FIG. 2D is a block diagram illustrating merging of changesets at the first client device for various types of operations, consistent with various

embodiments.

[0011] FIG. 3 is a flow diagram of a process for synchronizing data between multiple client devices, consistent with various embodiments.

[0012] FIG. 4 is a flow diagram of a process for determining a merging rule to resolve conflict between two changesets, consistent with various embodiments.

[0013] FIG. 5 is a flow diagram of a process for uploading changesets from and downloading changesets to a client device, consistent with various

embodiments.

[0014] FIG. 6 is a block diagram of a processing system that can implement operations of the disclosed embodiments.

DETAILED DESCRIPTION

[0015] FIG. 1 is a block diagram of an environment 100 in which the disclosed embodiments can be implemented. The environment 100 includes multiple client devices such as a first client device 1 10 and a second client device 115. The client devices can execute one or more applications, which can access data stored in their corresponding databases. For example, a first app 130 executing at the first client device 1 10 can access a first database 140, and a second app 135 executing at the second client device 1 15 can access a second database 145. In some embodiments, at least a portion of the data stored in the first and second

databases is shared between the client devices. That is, each of the client devices can access, e.g., read and/or write, the shared data and any changes made to the shared data will be applied to the data in all the client devices. A client device can be any network accessible computing device such as a desktop, a laptop, a smartphone, a tablet PC, or a wearable device. Each of the first app 130 and the second app 135 can be a mobile app or a browser-based application.

[0016] The client devices can perform data manipulation operations

(“operations”) on a data object stored in a database to make changes to the data object and each of the operations is represented as a changeset, which contains instructions regarding the operation to be performed on the data object. Examples of an operation that a changeset can represent include, but is not limited to,“set property,”“set default value,”“set integer,”“add integer,”“set string,”“substring insert,”“substring delete,”“set primary key,”“link list insert,”“delete object,” and “clear table.” In some embodiments, the set property operation sets an attribute or property of a data object to a specified value. In some embodiments, the set default value operation sets a default value of an attribute of a data object to a specified value. In some embodiments, the set integer operation sets an integer attribute of a data object to a specified integer value. In some embodiments, the add integer operation adds an integer value to a value of an integer attribute of a data object. In some embodiments, the set string operation sets a string attribute of a data object to a specified string value. In some embodiments, the substring insert operation adds a string to a string value of an attribute of a data object. In some embodiments, the substring delete operation deletes a portion of a string value of an attribute of a data object. In some embodiments, the set primary key operation sets a specified value of an attribute of a data object as a primary key, which causes the specified value to be unique across all data objects. In some embodiments, the link list insert operation inserts a list item to a linked list data object having one or more list items. In some embodiments, the delete object operation deletes a data object from the database. In some embodiments, the clear table operation clears the contents of a table data object.

[0017] Whenever changes are made to the data at a client device, the client device can generate a changeset. For example, when the first client device 1 10 performs a first operation, such as setting a default value of an attribute of a data object stored in the first database 140, the first client device 1 10 generates a first changeset Cn 115a having instructions for performing the set default value operation. Similarly, a second changeset C121 16a can correspond to a second operation performed by the first client device 1 10 to update the data object. The second client device 1 15 can also, similarly, generate a third changeset C21 125a, which can correspond to a third operation performed by the second client device 1 15 to update a data object stored in the second database 145, and a fourth changeset C22 126a, which can correspond to a fourth operation performed by the second client device 1 15 to update the data object in the second database 145. Note that the operations at the first client device 1 10 and the second client device 1 15 can occur independent of the operations at the other client device. In some embodiments, the changesets at a client device are stored in a client transaction log 155. For example, the first changeset C11 1 15a and the second changeset C12 1 16a are stored in a client transaction log 155a at the first client device 1 10.

[0018] The changesets from each of the client devices are uploaded to a server 105, which facilitates data synchronization between the client devices. For example, the first client device 1 10 can upload the first changeset Cn 1 15a and the second changeset C121 16a to the server 105, which are stored as a first changeset C1 1 1 15b and a second changeset C12 116b, respectively. Similarly, the second client device 1 15 can upload the third changeset C21 125a and the fourth changeset C22 126a, to the server 105, which are stored as a third changeset C21 125b and a fourth changeset C22126b, respectively. The server 105 stores the changesets in a server transaction log 150. In some embodiments, the server 105 adds the changesets to the server transaction log 150 in the order they are received from the client devices, which can be different from, or the same as, the order in which they were generated at the corresponding client devices.

[0019] As part of synchronization process 165, a client device can upload its changesets, if any, to the server 105, and download changesets, if any, of other client devices from the server 105 and apply them to its database. For example, as part of the synchronization process 165a, the first client device 1 10 can

synchronize the first database 140 with other client devices, such as the second client device 1 15, by downloading the third changeset C21 125b and the fourth changeset C22 126b from to the server 105 and applying them to the first database 140. The first client device can also upload any changesets, such as the first changeset C1 1 115a and the second changeset C12 1 16a, that are not yet uploaded to the server 105, as part of the synchronization process 165a.

[0020] After downloading the third changeset C21 125b and the fourth changeset C22 126b from to the server 105, the first client device 1 10 can apply them to the first database 140 to update the changes. Since changes have been made to the first database 140 locally too, e.g., via the first changeset C11 1 15a and the second changeset C12 1 16a, the changes made by the remote device, such as the second client device 1 15, can potentially conflict with the local changes. If the local changes and the remote changes are causally related or for different portions of the data, there may not be a conflict, and the remote changes can be applied to the first database 140 without any worries about the conflict. However, if the local changes and the remote changes are not causally related, or for the same portion of the data, e.g., for the same data object, there can be a conflict in applying the remote changes. The synchronization process 165 can resolve such a conflict by using a merge operation 160, which merges the local changesets with the remote changesets based on the application of merging rules.

[0021] The merging rules determine which of the changesets, e.g., a local changeset, a remote changeset, or both have to applied to the first database 140. The merging rules are defined based on at least one of a type of the operation or a timestamp associated with each of the changesets. For example, to merge the remote changesets, such as the third changeset C21 125b and the fourth changeset C22 126b, with the local changesets, such as the first changeset C1 1 1 15a and the second changeset C121 16a, the first client device 1 10 determines the type of operation in each of the changesets and/or the timestamp associated with each of the changesets and then determines the changesets that have to be applied to the first database 140, details of which are described at least with reference to FIGS 2A-2D below.

[0022] The second client device 1 15 can also similarly merge the local changes, such as the third changeset C21 125a and the fourth changeset C22126a, with the remote changesets, such as first changeset C1 1 115b and the second changeset C12 116b, as described above with respect to the first client device 1 10.

[0023] Whenever a changeset is uploaded to or downloaded from the server 105, e.g., as part of a synchronization request, the synchronization process 165 ensures that only the unsynchronized changesets, such as those that were not yet uploaded or downloaded as part of a prior synchronization request, are uploaded or downloaded. In some embodiments, the synchronization process uses checkpoints to achieve the above result. For example, after downloading the fourth changeset 126b from the server 105 and applying all the downloaded changesets to the first database 140, the synchronization process 165a can insert a server checkpoint 175 in the server transaction log 150 pointing to the fourth changeset 126b. In some embodiments, the server checkpoint 175 indicates that all changesets of other client devices added to the server transaction log 150 up to the server checkpoint 175 have been synchronized (e.g., downloaded and applied to the first database 140) by the first client device 110. When the first client device 1 10 synchronizes with the server 105 next, the synchronization process 165a ensures that only those changesets (e.g., changeset C2x) that are added to the server transaction log 150 after the server checkpoint 175 is added are

downloaded to the first client device 1 10. Similarly, the first client device 1 10 can also add a client checkpoint 170 in the client transaction log 155 to indicate that all changesets in the client transaction log 155 up until the client checkpoint 170 are uploaded to the server 105. When the first client device 1 10 synchronizes with the server 105 next, the synchronization process 165a ensures that only those changesets (e.g., changeset C-ix) that are added to the client transaction log 155 after the client checkpoint 170 is inserted are uploaded to the server 105.

[0024] The second client device 1 15 can also have its own pair of server and client checkpoints to ensure that only unsynchronized changesets are

synchronized by the second client device 1 15, as describe above with respect to the first client device 110. Further, in some embodiments, the client devices can assign version numbers (e.g., client version number and server version number) to the changesets instead of inserting checkpoints to ensure that only unsynchronized changesets are synchronized.

[0025] FIG. 2A is a block diagram of an example 205 for merging local changesets with remote changesets at the first client device 1 10, consistent with various embodiments. In the example 205, a data object 206 is shared between the first client device 110 and the second client device 1 15. Each client device has a copy of the data object 206 in their corresponding database. For example, the first client device 1 10 stores a data object 206a, which is a copy of the data object 206, in the first database 140 and the second client device 1 15 stores a data object 206b, which is another copy of the data object 206, in the second database 145. Any changes made to the data object 206a may have to be applied to the data object 206b, or vice versa.

[0026] In the example 205, the first client device 1 10 is offline, that is, the first client device 1 10 is not connected to the server 105. Since the first client device 1 10 is offline, the local changesets, such as the first changeset Cn 115a and the second changeset C121 16a, corresponding to local changes made to the data object 206a, e.g., by a first user 11 1 associated with the first client device 1 10, are not uploaded to the server 105.

[0027] The second client device 1 15 is online, that is, connected to the server 105 and has uploaded its changesets, such as the third changeset C21 125a and the fourth changeset C22 126a, to the server 105. The third changeset C21 125a and the fourth changeset C22 126a correspond to the changes made to the data object 206b, e.g., by a second user 1 12 associated with the second client device 1 15. In some embodiments, the data object 206 is shared between the first client device 1 10 and the second client device 1 15. Any changes made to the data object 206a may have to be applied to the data object 206b, or vice versa.

[0028] In the example 205, since the first client device 1 10 is offline, the first client device 1 10 does not have access to the changesets of the second client device 1 15, nor does the second client device 1 15 have access to the changesets of the first client device 1 10. However, the users 1 1 1 and 1 12 can continue to make changes to the data object 206a and 206b, respectively, and be assured that the data objects 206a and 206b will eventually be consistent, e.g., after both the client devices synchronize with the server 105 to obtain the changesets of the other client device.

[0029] FIG. 2B is a block diagram of another example 225 for merging local changesets with remote changesets at the first client device 1 10, consistent with various embodiments. In the example 225, the first client device 1 10 goes online, and synchronizes with the server 105, e.g., by sending a synchronization request 226 to the server 105. In some embodiments, the synchronization can also be initiated by the server 105. After receiving the synchronization request 226, the server 105 allows the first client device 1 10 to download the changesets of the second client device 1 15, such as the third changeset C21 125b and the fourth changeset C22 126b, from the server transaction log 150. In some embodiments, the first client device 110 downloads those changesets that are generated by client devices other than the first client device 1 10 and that are not already downloaded by the first client device 1 10, e.g., as part of prior synchronization requests.

Further, the first client device 1 10 can also upload the first changeset 1 15a and the second changeset 1 16a to the server 105.

[0030] Since the server transaction log 150 of the server 105 has new changesets, e.g., the first changeset 1 15b and the second changeset 1 16b of the first client device 1 10, the second client device 1 15 can synchronize with the server 105 to download those changesets. The server 105 can notify the second client device 1 15 of the availability of new changesets or the second client device 1 15 may periodically check with the server 105 for the new changesets.

[0031] FIG. 2C is an example 235 of a timeline of generation of changesets, consistent with various embodiments. Each changeset is tagged with a timestamp that indicates the time at which the changeset is generated at the corresponding client device. In some embodiments, the timestamp is indicative of the real-world time, as indicated by the internal clock of the client device generating the

changeset. In the example 235, the changesets are ordered on a timeline 236 according to a timestamp of the changesets. The timeline 236 indicates that the first changeset C11 1 15a was generated at the first client device 1 10 at time to, the third changeset C21 125b was generated at the second client device 115 at time t-i, the fourth changeset C22126b was generated at the second client device 115 at time t2, and the second changeset C12 1 16a was generated at the first client device 1 10 at time t3, where to<ti<t2<t3. In some embodiments, the merging rules consider the

timestamp of a changeset to resolve a conflict, as described with various examples of FIG. 2D below. [0032] FIG. 2D is a block diagram illustrating merging of changesets at the first client device 1 10 for various types of operations, consistent with various embodiments. As described above, the merging rules considers at least one of a type of the operation or a timestamp associated with each of the changesets to determine one or more operations that wins the conflict and updates the data object based on the winning operation.

[0033] In the first example 250, consider that the first changeset Cn 1 15a and the third changeset C21 125b correspond to a“set property” operation on the data object 206a and 206b, respectively, such as setting a color (attribute) of a car (data object). The first changeset C1 1 1 15a corresponds to setting the color of the car to “blue,” and the third changeset C21 125b corresponds to setting the color of the car to“red.” In some embodiments, if both the changesets are of type“set property”, then the merging rules define that a changeset having a later timestamp wins and the other changeset is to be discarded. Accordingly, since the timestamp, t1 , of the third changeset C21 125b is later than the timestamp, to of the first changeset C1 1 1 15a (as indicated in the example 235 of FIG. 2C), the first client device 1 10 determines that the third changeset C21 125b wins, and discards the first changeset C1 1 1 15a as a result of the merge operation 160a. Accordingly, the first client device 1 10 sets the color of the car to“red” by applying the third changeset C21 125b to the data object 206a.

[0034] In the second example 255a, consider that the first changeset C11 115a and the third changeset C21 125b correspond to a“set default value” operation on the data object 206a and 206b, respectively, such as setting a default value of a color attribute of a car data object. In some embodiments, if both the changesets are of type“set default value” and the default values are the same, then the merging rules define that the both the changesets are to be discarded. For example, if both the first changeset C1 1 1 15a and the third changeset C21 125b correspond to setting the color of the car to“blue,” the first client device 1 10 discards both the changesets as a result of the merge operation 256a and no changes are made to the data object 206a. On the other hand, if the default values of the changesets are different, then the merging rules define that a changeset having a later timestamp wins and the other changeset is to be discarded. For example, if the first changeset Cn 1 15a corresponds to setting default value of the color to“blue,” and the third changeset C21 125b to“red,” as illustrated in the second example 255b, then the third changeset C21 125b wins, and the first changeset C1 1 115a is discarded as a result of the merge operation 160a because timestamp, t-i, of the third changeset C21 125b is later than the timestamp, to of the first changeset C11 1 15a (as indicated in the example 235 of FIG. 2C). Accordingly, the first client device 110 sets the default value of the color of the car to“red” by applying the third changeset C21 125b to the data object 206a.

[0035] In the third example 260, consider that the first changeset C11 1 15a corresponds to an“add integer” operation on the data object 206a, such as adding an integer value of“2” to valves attribute of a car data object, which has a value of “4,” and that the third changeset C21 125b corresponds to a“set integer” operation on the data object 206b, such as setting an integer value of“8” to the valves attribute of the car data object. In some embodiments, if one changeset

corresponds to an“add integer” operation and another corresponds to a“set integer” operation, then the merging rules define that a changeset with the later timestamp wins. Accordingly, since the timestamp, t1 , of the third changeset C21 125b is later than the timestamp, to, of the first changeset C11 1 15a (as indicated in the example 235 of FIG. 2C), the first client device 1 10 determines that the third changeset C21 125b wins, and discards the first changeset C11 1 15a as a result of the merge operation 160a. Accordingly, the first client device 1 10 sets the value of the valves of the car to“8” by applying the third changeset C21 125b to the data object 206a.

[0036] In the fourth example 265, consider that the first changeset C1 1 1 15a corresponds to an“substring” insert or delete operation on the data object 206a, such as inserting a substring“hard top” to a car type attribute of a car data object, which has a value of“convertible,” and that the third changeset C21 125b

corresponds to a“set string” operation on the data object 206b, such as setting a string value of“SUV” to the car type attribute of the car data object. In some embodiments, if one changeset corresponds to a substring operation and another corresponds to a“set string” operation, then the merging rules define that a changeset corresponding to the“set string” wins and the changeset corresponding to the substring operation is to be discarded. Accordingly, the first client device 1 10 determines that the third changeset C21 125b wins, and discards the first changeset C1 1 1 15a as a result of the merge operation 160a. Accordingly, the first client device 1 10 sets the value of the car type of the car to“SUV” by applying the third changeset C21 125b to the data object 206a.

[0037] In the fifth example 270, consider that the first changeset C1 1 1 15a and the third changeset C21 125b correspond to a“set primary key” operation on the data object 206a and 206b, respectively, such as setting an ID (attribute) of a student (data object) as a primary key. The first changeset C11 1 15a corresponds to setting the ID having value“1” of a first student data object as a primary key, and the third changeset C21 125b corresponds to setting the ID having value“1” of a second student data object also as the primary key. In some embodiments, if both the changesets are setting the same primary key on two different objects, then the merging rules define that a changeset having an earlier timestamp wins and the other changeset is to be discarded and the data object corresponding to the other changeset is to be deleted. Accordingly, since the timestamp, to of the first changeset C1 1 1 15a is earlier than the timestamp, t1 , of the third changeset C21 125b (as indicated in the example 235 of FIG. 2C), the first client device 1 10 determines that the first changeset C11 1 15a wins, and discards the third changeset C21 125b as a result of the merge operation 160a. Accordingly, the first client device 1 10 sets the ID having value“1” of the first student object as the primary key by applying the first changeset C11 1 15a to the data object 206a, and deletes the second student data object. [0038] In the sixth example 275, consider that the first changeset Cn 1 15a and the third changeset C21 125b correspond to a“LinkList insert” operation on the data object 206a and 206b, respectively, such as inserting a list item to a linked list (data object). The first changeset C1 1 115a corresponds to inserting a list item“A” to a tail of a linked list data object having n list items, and the third changeset C21 125b corresponds to inserting a list item“B” to the tail of the linked list data object. In some embodiments, if both the changesets are inserting a list item to a linked list data object, then the merging rules define that the order in which the list items are inserted depends on the timestamps of the corresponding changesets.

Accordingly, since the timestamp, to of the first changeset C1 1 1 15a is earlier than the timestamp, t-i, of the third changeset C21 125b (as indicated in the example 235 of FIG. 2C), the first client device 1 10 determines that the first changeset C1 1 1 15a is to be applied first and then the third changeset C21 125b as a result of the merge operation 160a. Accordingly, the first client device 1 10 inserts the list item“A” to the tail of the linked list first and then inserts the list item“B” to the tail of the linked list by applying the first changeset C1 1 115a and the third changeset C21 125b to the data object 206a in the order of their timestamps.

[0039] In the seventh example 280, consider that the first changeset C11 115a to a“delete object” operation on the data object 206a, such as deleting a car data object, and that the third changeset C21 125b corresponds to any update operation on the data object 206b, such as updating a color attribute of the car data object.

In some embodiments, if one of the changesets corresponds to deleting a data object and the other corresponds to updating the data object, then the merging rules define that the delete operation wins and the other changeset is to be discarded as a result of the merge operation 160a. Accordingly, the first client device 1 10 deletes the car data object by applying the first changeset C1 1 1 15a to the data object 206a.

[0040] Similar to the above seventh example, if one changeset corresponds to “clear content” operation on a database table and the other changeset corresponds to updating contents of the database table, the merging rules define that the“clear content” operation wins and the other changeset is to be discarded as a result of the merge operation 160a.

[0041] In the eight example 285, consider that the first changeset Cn 1 15a corresponds to an“increment counter” (or“decrement counter”) operation on the data object 206a, such as incrementing (or decrementing) a value of a valves attribute of a car data object, which has a value of“4,” and that the third changeset C21 125b also corresponds to an“increment counter” (or“decrement counter”) operation on the valves attribute of the car data object. In some embodiments, if both the changesets correspond to an“increment counter” (or“decrement counter”) operation, then the merging rules define that both the changesets are to be applied. Accordingly, the first client device 1 10 increments the value of the valves of the car to“6” by applying both first changeset C11 1 15a and the third changeset C21 125b to the data object 206a as part of the merge operation 160a.

[0042] The above operations are just example operations used to describe how a conflict is resolved between two operations. The merge operation is not limited to resolving conflicts for the above operations, and can resolve conflicts various other operations based on the above techniques. Further, the above examples are described with respect to resolving conflict at the first client device 1 10. However, the merge operation can resolve the conflicts at the second client device 1 15 similar to the merge operation described with reference to the first client device 1 10. For example, like the first client device 1 10 downloads the third changeset 125b and the fourth changeset 126b of the second client device 1 15 from the server 105, the second client device 1 15 can download the first changeset 1 15b and the second changeset 1 16b of the first client device 1 10 from the server 105 and merge them with its local changesets based on the type of operations and timestamps, as described above with respect to the first client device 1 10.

[0043] Further, the above examples describe resolving any potential conflicts between the first changeset C11 1 15a and the third changeset C21 125b. However, any potential conflicts with the remaining changesets - the fourth changeset C22 126b and the second changeset C12 116a - can also be similarly resolved.

[0044] FIG. 3 is a flow diagram of a process 300 for synchronizing data between multiple client devices, consistent with various embodiments. In some embodiments, the process 300 can be implemented in the environment 100. At block 305, the first client device 1 10 establishes a communication session between the first client device 110 and the server 105. In some embodiments, the first client device 1 10 can send a synchronization request, such as the synchronization request 226 of FIG. 2B, to the server 105 when the communication session is established. The first client device 1 10 can also send information such as a client identification (ID) that uniquely identifies the first client device 110, the server checkpoint, and the client checkpoint associated with the first client device 1 10 to the server 105 (e.g., as part of the synchronization request), which can be used for synchronizing the data at the first client device 1 10.

[0045] At block 310, the first client device 1 10 downloads a remote changeset, e.g., a changeset of another client device that is representative of an operation performed on a data object by the other client device, from the server 105. For example, the first client device 1 10 downloads the third changeset 125b and the fourth changeset 126b from the server 105, which represent operations performed by the second client device 1 15 on the data object 206b stored at the second client device 1 15.

[0046] At block 315, the first client device 1 10 accesses a local changeset, e.g., a changeset representing an operation performed on the data object by the first client device 1 10. For example, the first client device 1 10 accesses the first changeset 1 15a and the second changeset 116a that represent operations performed on the data object 206a stored at the first client device 1 10. The first client device 1 10 can generate a changeset in response to an operation performed on the data object, e.g., by the user 1 1 1 , that changes a state (e.g., a value) of the data object. The first changeset 1 15a and the second changeset 1 16a may be generated in response to a first operation and a second operation on the data object 206a, respectively. In some embodiments, the data object 206 is shared between the multiple client devices and each of the multiple client devices can store a copy of the data object locally (e.g., at the client device). Accordingly, any changes made to the data object in one client device may have to be applied to the data object stored in the other client devices for the data object to be consistent across the multiple client devices.

[0047] At block 320, the first client device 1 10 merges the local changesets and the remote changesets based on the merging rules to update the data object 206a at the first client device 1 10. For example, the first client device 1 10 merges the first changeset 115a, second changeset 1 16a, third changeset 125b and fourth changeset 126b based on the merging rules and updates the data object 206a, e.g., as described at least with reference to FIGS. 2A-2D. The process 300 resolves any potential conflict that can arise in applying the changesets to the data object 206a based on the merging rules, which are defined as a function of the type of operations in each of the changesets and a timestamp associated with each of the changesets.

[0048] In some embodiments, the process 300 is performed as part of the synchronization process 165a of FIG. 1 and the merge operation 160a.

[0049] FIG. 4 is a flow diagram of a process 400 for determining a merging rule to resolve conflict between two changesets, consistent with various

embodiments. In some embodiments, the process 400 can be implemented in the environment 100 of FIG. 1 and as part of the merge operation 160a. In some embodiments, the process 400 can be implemented as part of block 320 of FIG. 3. At block 305, the first client device 1 10 determines a type of operation in the local changeset and a timestamp of the local changeset. For example, the first client device 1 10 determines the type of operation in the first changeset 1 15a and a timestamp associated with the first changeset 1 15a, which is indicative of the time at which the first changeset 1 15a was generated at the first client device 1 10.

[0050] At block 410, the first client device 1 10 determines a type of operation in the remote changeset and a timestamp of the remote changeset. For example, the first client device 110 determines the type of operation in the third changeset 125b and a timestamp associated with the third changeset 125b, which is indicative of the time at which the third changeset 125b was generated at the second client device 1 15.

[0051 ] At block 415, the first client device 1 10 determines the merging rules based on the type of operations in and the timestamps of the local and remote changesets. For example, as described at least with reference to FIG. 2C, if the first changeset Cn 1 15a represents a“set property” operation and the third changeset 125b also represents a“set property” operation on the data object 206, then the first client device 1 10 identifies a merging which states that if the type of operation in both the changesets represent a“set property” operation, the changeset that has a later timestamp emerges as a winner in the merge operation.

[0052] In some embodiments, the merging rules can be stored in a rule log or a rule lookup table, and a merging rule can be determined by looking up the lookup table based on the type of operations. The merging rules can be maintained at the server 105 and each of the client devices can have a copy of the merging rules.

[0053] At block 420, the first client device 1 10 applies at least one of the local changeset or remote changeset to the data object 206a at the first client device 1 10 based on the merging rule that is determined in block 420. Continuing with example described in block 415, the first client device 1 10 applies the“set property” operation of the first changeset Cn 1 15a or the third changeset 125b that has a later timestamp to the data object 206a and updates the data object 206a accordingly.

[0054] FIG. 5 is a flow diagram of a process 500 for uploading changesets from and downloading changesets to a client device from the server of FIG. 1 , consistent with various embodiments. In some embodiments, the process 500 can be implemented in the environment 100 of FIG. 1. In some embodiments, the process 500 can be implemented as part of the synchronization process 165a of FIG. 1. At block 505, the first client device 1 10 establishes a communication session between the first client device 1 10 and the server 105. In some

embodiments, the first client device 1 10 can send a synchronization request, such as the synchronization request 226 of FIG. 2B, to the server 105 when the communication session is established. The first client device 1 10 can also send information such as a client ID of the first client device 1 10, the server checkpoint, and the client checkpoint associated with the first client device 110 to the server 105.

[0055] At block 510, the first client device 1 10 uploads local changesets, e.g., changesets generated at the first client device 1 10, to the server 105. For example, after the first client device 1 10 uploads the first changeset 1 15a and the second changeset 1 16a to the server 105.

[0056] At block 515, the first client device 1 10 inserts a checkpoint in the transaction log (“client checkpoint”) of the first client device 1 10 to indicate the last uploaded changeset. The first client device 1 10 uploads only the unsynchronized changesets to the server 105, that is, the changesets that are not already uploaded to the server 105. Whenever the first client device 1 10 synchronizes with the server 105, the first client device 1 10 ensures that only those local changesets that are added to the client transaction log after the last client checkpoint is added are uploaded to the server 105. For example, after the first client device 1 10 uploads the first changeset 115a and the second changeset 1 16a to the server 105 as illustrated in FIG. 2B, the first client device 1 10 can add a client checkpoint 170 in the client transaction log 155a at the second changeset 1 16a. When the first client device 1 10 synchronizes with the server 105 next time, only those changesets that are added to the client transaction log 155a after the client checkpoint 170 are uploaded to the server 105. [0057] At block 520, the first client device 1 10 downloads remote changesets, e.g., a changeset of another client device that is representative of an operation performed on a data object by the other client device, from the server 105. For example, the first client device 1 10 downloads the third changeset 125b and the fourth changeset 126b from the server 105, which represent operations performed by the second client device 1 15 on the data object 206b.

[0058] At block 525, the first client device 1 10 inserts a checkpoint in the transaction log (“server checkpoint”) of the server 105 to indicate the last

downloaded changeset in the communication session. The first client device 1 10 downloads only the unsynchronized changesets from the server 105, that is, the changesets that are not already downloaded from the server 105. Whenever the first client device 1 10 synchronizes with the server 105, the first client device 1 10 ensures that only those remote changesets that are added to the server transaction log after the last server checkpoint is added are downloaded from the server 105. For example, after the first client device 1 10 downloads the third changeset 125b and the fourth changeset 126b from the server 105 as illustrated in FIG. 2B, the first client device 1 10 can insert a server checkpoint 175 in the server transaction log 150 at the fourth changeset 126b. When the first client device 1 10

synchronizes with the server 105 next time, only those changesets that are added to the server transaction log 150 after the server checkpoint 175 are downloaded from the server 105.

[0059] Note that the processes 300-500 of FIGS. 3-5 are described with reference to the first client device 1 10. These processes can also be executed at other client devices, e.g., the second client device 115, to synchronize the data at those client devices.

[0060] FIG. 6 is a block diagram of a computer system as may be used to implement features of the disclosed embodiments. The computer system 600 may be used to implement any of the entities, components, modules, processes, or services depicted in the examples of the foregoing figures (and any other entities described in this specification). The computer system 600 may include one or more central processing units (“processors”) 605, memory 610, input/output devices 625 ( e.g ., keyboard and pointing devices, display devices), storage devices 620 {e.g., disk drives), and network adapters 630 {e.g., network interfaces) that are connected to an interconnect 615. The interconnect 615 is illustrated as an abstraction that represents any one or more separate physical buses, point to point connections, or both connected by appropriate bridges, adapters, or controllers. The interconnect 615, therefore, may include, for example, a system bus, a Peripheral Component Interconnect (PCI) bus or PCI-Express bus, a HyperTransport or industry standard architecture (ISA) bus, a small computer system interface (SCSI) bus, a universal serial bus (USB), IIC (I2C) bus, or an Institute of Electrical and Electronics Components (IEEE) standard 1394 bus, also called“Firewire”.

[0061] The memory 610 and storage devices 620 are computer-readable storage media that may store instructions that implement at least portions of the described embodiments. In addition, the data structures and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communications links may be used, such as the Internet, a local area network, a wide area network, or a point-to-point dial-up connection. Thus, computer readable media can include computer-readable storage media {e.g., "non-transitory" media) and computer-readable transmission media.

[0062] The instructions stored in memory 610 can be implemented as software and/or firmware to program the processor(s) 605 to carry out actions described above. In some embodiments, such software or firmware may be initially provided to the computer system 600 by downloading it from a remote system through the computer system 600 {e.g., via network adapter 630).

[0063] The embodiments introduced herein can be implemented by, for example, programmable circuitry {e.g., one or more microprocessors) programmed with software and/or firmware, or entirely in special-purpose hardwired (non programmable) circuitry, or in a combination of such forms. Special-purpose hardwired circuitry may be in the form of, for example, one or more ASICs, PLDs, FPGAs, etc.

Remarks

[0064] The above description and drawings are illustrative and are not to be construed as limiting. Numerous specific details are described to provide a thorough understanding of the disclosure. However, in some instances, well- known details are not described in order to avoid obscuring the description.

Further, various modifications may be made without deviating from the scope of the embodiments. Accordingly, the embodiments are not limited except as by the appended claims.

[0065] Reference in this specification to "one embodiment" or "an

embodiment" means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the disclosure. The appearances of the phrase "in one embodiment" in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Moreover, various features are described which may be exhibited by some embodiments and not by others. Similarly, various requirements are described which may be requirements for some embodiments but not for other embodiments.

[0066] The terms used in this specification generally have their ordinary meanings in the art, within the context of the disclosure, and in the specific context where each term is used. Terms that are used to describe the disclosure are discussed below, or elsewhere in the specification, to provide additional guidance to the practitioner regarding the description of the disclosure. For convenience, some terms may be highlighted, for example using italics and/or quotation marks. The use of highlighting has no influence on the scope and meaning of a term; the scope and meaning of a term is the same, in the same context, whether or not it is highlighted. It will be appreciated that the same thing can be said in more than one way. One will recognize that“memory” is one form of a“storage” and that the terms may on occasion be used interchangeably.

[0067] Consequently, alternative language and synonyms may be used for any one or more of the terms discussed herein, nor is any special significance to be placed upon whether or not a term is elaborated or discussed herein.

Synonyms for some terms are provided. A recital of one or more synonyms does not exclude the use of other synonyms. The use of examples anywhere in this specification including examples of any term discussed herein is illustrative only, and is not intended to further limit the scope and meaning of the disclosure or of any exemplified term. Likewise, the disclosure is not limited to various

embodiments given in this specification.

[0068] Those skilled in the art will appreciate that the logic illustrated in each of the flow diagrams discussed above, may be altered in various ways. For example, the order of the logic may be rearranged, substeps may be performed in parallel, illustrated logic may be omitted; other logic may be included, etc.

[0069] Without intent to further limit the scope of the disclosure, examples of instruments, apparatus, methods and their related results according to the embodiments of the present disclosure are given below. Note that titles or subtitles may be used in the examples for convenience of a reader, which in no way should limit the scope of the disclosure. Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains. In the case of conflict, the present document, including definitions will control.