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.
The {@code OnStateLoadedListener} methods are responsible for loading an application's state data from Google's servers. The callback {@code 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.
Here are some simple cases of conflict resolution. For many apps, it is sufficient to adopt a variant of one of these strategies:
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.
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.
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:
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:
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.
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:
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: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 |
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.