Resolving Cloud Save Conflicts

This article describes how to design a robust conflict resolution strategy for apps that save data to the cloud using the Cloud Save service. The Cloud Save service allows you to store application data for each user of an application on Google's servers. Your application can retrieve and update this user data from Android devices, iOS devices, or web applications by using the Cloud Save APIs.

Saving and loading progress in Cloud Save is straightforward: it's just a matter of serializing the player's data to and from byte arrays and storing those arrays in the cloud. However, when your user has multiple devices and two or more of them attempt to save data to the cloud, the saves might conflict, and you must decide how to resolve it. The structure of your cloud save data largely dictates how robust your conflict resolution can be, so you must design your data carefully in order to allow your conflict resolution logic to handle each case correctly.

The article starts by describing a few flawed approaches and explains where they fall short. Then it presents a solution for avoiding conflicts. The discussion focuses on games, but you can apply the same principles to any app that saves data to the cloud.

Get Notified of Conflicts

The OnStateLoadedListener methods are responsible for loading an application's state data from Google's servers. The callback OnStateLoadedListener.onStateConflict provides a mechanism for your application to resolve conflicts between the local state on a user's device and the state stored in the cloud:

@Override
public void onStateConflict(int stateKey, String resolvedVersion,
    byte[] localData, byte[] serverData) {
    // resolve conflict, then call mAppStateClient.resolveConflict()
 ...
}

At this point your application must choose which one of the data sets should be kept, or it can submit a new data set that represents the merged data. It is up to you to implement this conflict resolution logic.

It's important to realize that the Cloud Save service synchronizes data in the background. Therefore, you should ensure that your app is prepared to receive that callback outside of the context where you originally generated the data. Specifically, if the Google Play services application detects a conflict in the background, the callback will be called the next time you attempt to load the data, which might not happen until the next time the user starts the app.

Therefore, design of your cloud save data and conflict resolution code must be context-independent: given two conflicting save states, you must be able to resolve the conflict using only the data available within the data sets, without consulting any external context.

Handle the Simple Cases

Here are some simple cases of conflict resolution. For many apps, it is sufficient to adopt a variant of one of these strategies:

• New is better than old. In some cases, new data should always replace old data. For example, if the data represents the player's choice for a character's shirt color, then a more recent choice should override an older choice. In this case, you would probably choose to store the timestamp in the cloud save data. When resolving the conflict, pick the data set with the most recent timestamp (remember to use a reliable clock, and be careful about time zone differences).
• One set of data is clearly better than the other. In other cases, it will always be clear which data can be defined as "best". For example, if the data represents the player's best time in a racing game, then it's clear that, in case of conflicts, you should keep the best (smallest) time.
• Merge by union. It may be possible to resolve the conflict by computing a union of the two conflicting sets. For example, if your data represents the set of levels that player has unlocked, then the resolved data is simply the union of the two conflicting sets. This way, players won't lose any levels they have unlocked. The CollectAllTheStars sample game uses a variant of this strategy.

Design a Strategy for More Complex Cases

A more complicated case happens when your game allows the player to collect fungible items or units, such as gold coins or experience points. Let's consider a hypothetical game, called Coin Run, an infinite runner where the goal is to collect coins and become very, very rich. Each coin collected gets added to the player's piggy bank.

The following sections describe three strategies for resolving sync conflicts between multiple devices: two that sound good but ultimately fail to successfully resolve all scenarios, and one final solution that can manage conflicts between any number of devices.

First Attempt: Store Only the Total

At first thought, it might seem that the cloud save data should simply be the number of coins in the bank. But if that data is all that's available, conflict resolution will be severely limited. The best you could do would be to pick the largest of the two numbers in case of a conflict.

Consider the scenario illustrated in Table 1. Suppose the player initially has 20 coins, and then collects 10 coins on device A and 15 coins on device B. Then device B saves the state to the cloud. When device A attempts to save, a conflict is detected. The "store only the total" conflict resolution algorithm would resolve the conflict by writing 35 (the largest of the two numbers).

Table 1. Storing only the total number of coins (failed strategy).

Event	Data on Device A	Data on Device B	Data on Cloud	Actual Total
Starting conditions	20	20	20	20
Player collects 10 coins on device A	30	20	20	30
Player collects 15 coins on device B	30	35	20	45
Device B saves state to cloud	30	35	35	45
Device A tries to save state to cloud. Conflict detected.	30	35	35	45
Device A resolves conflict by picking largest of the two numbers.	35	35	35	45

This strategy would fail—the player's bank has gone from 20 to 35, when the user actually collected a total of 25 coins (10 on device A and 15 on device B). So 10 coins were lost. Storing only the total number of coins in the cloud save is not enough to implement a robust conflict resolution algorithm.

Second Attempt: Store the Total and the Delta

A different approach is to include an additional field in the save data: the number of coins added (the delta) since the last commit. In this approach the save data can be represented by a tuple (T,d) where T is the total number of coins and d is the number of coins that you just added.

With this structure, your conflict resolution algorithm has room to be more robust, as illustrated below. But this approach still doesn't give your app a reliable picture of the player's overall state.

Here is the conflict resolution algorithm for including the delta:

• Local data: (T, d)
• Cloud data: (T', d')
• Resolved data: (T' + d, d)

For example, when you get a conflict between the local state (T,d) and the cloud state (T',d'), you can resolve it as (T'+d, d). What this means is that you are taking the delta from your local data and incorporating it into the cloud data, hoping that this will correctly account for any gold coins that were collected on the other device.

This approach might sound promising, but it breaks down in a dynamic mobile environment:

• Users might save state when the device is offline. These changes will be queued up for submission when the device comes back online.
• The way that sync works is that the most recent change overwrites any previous changes. In other words, the second write is the only one that gets sent to the cloud (this happens when the device eventually comes online), and the delta in the first write is ignored.

To illustrate, consider the scenario illustrated by Table 2. After the series of operations shown in the table, the cloud state will be (130, +5). This means the resolved state would be (140, +10). This is incorrect because in total, the user has collected 110 coins on device A and 120 coins on device B. The total should be 250 coins.

Table 2. Failure case for total+delta strategy.

Event	Data on Device A	Data on Device B	Data on Cloud	Actual Total
Starting conditions	(20, x)	(20, x)	(20, x)	20
Player collects 100 coins on device A	(120, +100)	(20, x)	(20, x)	120
Player collects 10 more coins on device A	(130, +10)	(20, x)	(20, x)	130
Player collects 115 coins on device B	(130, +10)	(125, +115)	(20, x)	245
Player collects 5 more coins on device B	(130, +10)	(130, +5)	(20, x)	250
Device B uploads its data to the cloud	(130, +10)	(130, +5)	(130, +5)	250
Device A tries to upload its data to the cloud. Conflict detected.	(130, +10)	(130, +5)	(130, +5)	250
Device A resolves the conflict by applying the local delta to the cloud total.	(140, +10)	(130, +5)	(140, +10)	250

(*): x represents data that is irrelevant to our scenario.

You might try to fix the problem by not resetting the delta after each save, so that the second save on each device accounts for all the coins collected thus far. With that change the second save made by device A would be (130, +110) instead of (130, +10). However, you would then run into the problem illustrated in Table 3.

Table 3. Failure case for the modified algorithm.

Event	Data on Device A	Data on Device B	Data on Cloud	Actual Total
Starting conditions	(20, x)	(20, x)	(20, x)	20
Player collects 100 coins on device A	(120, +100)	(20, x)	(20, x)	120
Device A saves state to cloud	(120, +100)	(20, x)	(120, +100)	120
Player collects 10 more coins on device A	(130, +110)	(20, x)	(120, +100)	130
Player collects 1 coin on device B	(130, +110)	(21, +1)	(120, +100)	131
Device B attempts to save state to cloud. Conflict detected.	(130, +110)	(21, +1)	(120, +100)	131
Device B solves conflict by applying local delta to cloud total.	(130, +110)	(121, +1)	(121, +1)	131
Device A tries to upload its data to the cloud. Conflict detected.	(130, +110)	(121, +1)	(121, +1)	131
Device A resolves the conflict by applying the local delta to the cloud total.	(231, +110)	(121, +1)	(231, +110)	131

(*): x represents data that is irrelevant to our scenario.

Now you have the opposite problem: you are giving the player too many coins. The player has gained 211 coins, when in fact she has collected only 111 coins.

Solution: Store the Sub-totals per Device

Analyzing the previous attempts, it seems that what those strategies fundamentally miss is the ability to know which coins have already been counted and which coins have not been counted yet, especially in the presence of multiple consecutive commits coming from different devices.

The solution to the problem is to change the structure of your cloud save to be a dictionary that maps strings to integers. Each key-value pair in this dictionary represents a "drawer" that contains coins, and the total number of coins in the save is the sum of the values of all entries. The fundamental principle of this design is that each device has its own drawer, and only the device itself can put coins into that drawer.

The structure of the dictionary is (A:a, B:b, C:c, ...), where a is the total number of coins in the drawer A, b is the total number of coins in drawer B, and so on.

The new conflict resolution algorithm for the "drawer" solution is as follows:

• Local data: (A:a, B:b, C:c, ...)
• Cloud data: (A:a', B:b', C:c', ...)
• Resolved data: (A:max(a,a'), B:max(b,b'), C:max(c,c'), ...)

For example, if the local data is (A:20, B:4, C:7) and the cloud data is (B:10, C:2, D:14), then the resolved data will be (A:20, B:10, C:7, D:14). Note that how you apply conflict resolution logic to this dictionary data may vary depending on your app. For example, for some apps you might want to take the lower value.

To test this new algorithm, apply it to any of the test scenarios mentioned above. You will see that it arrives at the correct result.

Table 4 illustrates this, based on the scenario from Table 3. Note the following:

• In the initial state, the player has 20 coins. This is accurately reflected on each device and the cloud. This value is represented as a dictionary (X:20), where the value of X isn't significant—we don't care where this initial data came from.
• When the player collects 100 coins on device A, this change is packaged as a dictionary and saved to the cloud. The dictionary's value is 100 because that is the number of coins that the player collected on device A. There is no calculation being performed on the data at this point—device A is simply reporting the number of coins the player collected on it.
• Each new submission of coins is packaged as a dictionary associated with the device that saved it to the cloud. When the player collects 10 more coins on device A, for example, the device A dictionary value is updated to be 110.
• The net result is that the app knows the total number of coins the player has collected on each device. Thus it can easily calculate the total.

Table 4. Successful application of the key-value pair strategy.

Event	Data on Device A	Data on Device B	Data on Cloud	Actual Total
Starting conditions	(X:20, x)	(X:20, x)	(X:20, x)	20
Player collects 100 coins on device A	(X:20, A:100)	(X:20)	(X:20)	120
Device A saves state to cloud	(X:20, A:100)	(X:20)	(X:20, A:100)	120
Player collects 10 more coins on device A	(X:20, A:110)	(X:20)	(X:20, A:100)	130
Player collects 1 coin on device B	(X:20, A:110)	(X:20, B:1)	(X:20, A:100)	131
Device B attempts to save state to cloud. Conflict detected.	(X:20, A:110)	(X:20, B:1)	(X:20, A:100)	131
Device B solves conflict	(X:20, A:110)	(X:20, A:100, B:1)	(X:20, A:100, B:1)	131
Device A tries to upload its data to the cloud. Conflict detected.	(X:20, A:110)	(X:20, A:100, B:1)	(X:20, A:100, B:1)	131
Device A resolves the conflict	(X:20, A:110, B:1)	(X:20, A:100, B:1)	(X:20, A:110, B:1) total 131	131

Clean Up Your Data

There is a limit to the size of cloud save data, so in following the strategy outlined in this article, take care not to create arbitrarily large dictionaries. At first glance it may seem that the dictionary will have only one entry per device, and even the very enthusiastic user is unlikely to have thousands of them. However, obtaining a device ID is difficult and considered a bad practice, so instead you should use an installation ID, which is easier to obtain and more reliable. This means that the dictionary might have one entry for each time the user installed the application on each device. Assuming each key-value pair takes 32 bytes, and since an individual cloud save buffer can be up to 128K in size, you are safe if you have up to 4,096 entries.

In real-life situations, your data will probably be more complex than a number of coins. In this case, the number of entries in this dictionary may be much more limited. Depending on your implementation, it might make sense to store the timestamp for when each entry in the dictionary was modified. When you detect that a given entry has not been modified in the last several weeks or months, it is probably safe to transfer the coins into another entry and delete the old entry.