From 9c309d3db95b1fc63925a18b81e6ceabcaa18407 Mon Sep 17 00:00:00 2001 From: kmccormick Date: Tue, 11 Jun 2013 13:17:55 -0700 Subject: Cherrypick from jb-mr2-dev docs: cloud save Change-Id: Ie20b2c7aca3f0724c9b04c6403deb18e1a07d322 Change-Id: I32fe3880852ed8bcbacec0bb5bf385b0022a791f --- docs/html/training/cloudsave/conflict-res.jd | 597 +++++++++++++++++++++++++++ docs/html/training/cloudsync/gcm.jd | 5 - docs/html/training/training_toc.cs | 7 +- 3 files changed, 603 insertions(+), 6 deletions(-) create mode 100644 docs/html/training/cloudsave/conflict-res.jd diff --git a/docs/html/training/cloudsave/conflict-res.jd b/docs/html/training/cloudsave/conflict-res.jd new file mode 100644 index 0000000..0ff50e2 --- /dev/null +++ b/docs/html/training/cloudsave/conflict-res.jd @@ -0,0 +1,597 @@ +page.title=Resolving Cloud Save Conflicts +page.tags="cloud" + +page.article=true +@jd:body + + + +
+ +
+ +

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 +{@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.

+ +

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:

+ + + +

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).

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
EventData on Device AData on Device BData on CloudActual Total
Starting conditions20202020
Player collects 10 coins on device A30202030
Player collects 15 coins on device B30352045
Device B saves state to cloud30353545
Device A tries to save state to cloud.
+ Conflict detected.		30353545
Device A resolves conflict by picking largest of the two numbers.35353545
+ +

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:

+ + + +

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.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
EventData on Device AData on Device BData on CloudActual 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.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
EventData on Device AData on Device BData on CloudActual 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:

+ + + +

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.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
EventData on Device AData on Device BData on CloudActual 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.

\ No newline at end of file diff --git a/docs/html/training/cloudsync/gcm.jd b/docs/html/training/cloudsync/gcm.jd index fa395e4..6303372 100644 --- a/docs/html/training/cloudsync/gcm.jd +++ b/docs/html/training/cloudsync/gcm.jd @@ -1,12 +1,7 @@ page.title=Making the Most of Google Cloud Messaging -parent.title=Syncing to the Cloud -parent.link=index.html trainingnavtop=true -previous.title=Using the Backup API -previous.link=backupapi.html - @jd:body
diff --git a/docs/html/training/training_toc.cs b/docs/html/training/training_toc.cs index ee6913c..563acf0 100644 --- a/docs/html/training/training_toc.cs +++ b/docs/html/training/training_toc.cs @@ -375,7 +375,6 @@
+
  • Resolving Cloud Save Conflicts + +
    • -- cgit v1.1