解决云同步的保存冲突

编写:jdneo - 原文:http://developer.android.com/training/cloudsave/conflict-res.html

这篇文章将介绍当应用使用Cloud Save service存储数据到云端时,如何设计一个鲁棒性较高的冲突解决策略。云存储服务允许我们为每一个在Google服务上的应用用户,存储他们的应用数据。应用可以通过使用云存储API,从Android设备,iOS设备或者Web应用恢复或更新这些数据。

云存储中的保存和加载过程非常直接:它只是一个数据和byte数组之间序列化转换,并将这些数组存储在云端的过程。然而,当用户有多个设备,并且有两个以上的设备尝试将它们的数据存储在云端时,这一保存的行为可能会引起冲突,因此我们必须决定应该如何处理这类问题。云端数据的结构在很大程度上决定了冲突解决方案的鲁棒性,所以务必小心地设计我们的数据存储结构,使得冲突解决方案的逻辑可以正确地处理每一种情况。

本篇文章从一些有缺陷的解决方案入手,并解释他们为何具有缺陷。之后会呈现一个可以避免冲突的解决方案。用于讨论的例子关注于游戏,但解决问题的核心思想是可以适用于任何将数据存储于云端的应用的。

冲突时获得通知

OnStateLoadedListener方法负责从Google服务器下载应用的状态数据。回调函数OnStateLoadedListener.onStateConflict用来给应用在本地状态和云端存储的状态发生冲突时,提供了一个解决机制:

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

此时应用必须决定要保留哪一个数据,或者它自己提交一个新的数据来表示合并后的数据状态,解决冲突的逻辑由我们自己来实现。

我们必须要意识到云存储服务是在后台执行同步的。所以我们应该确保应用能够在创建这一数据的Context之外接收回调。特别地,如果Google Play服务应用在后台检测到了一个冲突,该回调函数会在下一次加载数据时被调用,通常来说会是在下一次用户启动该应用时。

因此,我们的云存储代码和冲突解决代码的设计必须是和当前Context无关的:也就是说当我们拿到了两个彼此冲突的数据,我们必须仅通过数据集内获取的数据去解决冲突,而不依赖于任何其它任何外部Context。

处理简单情况

下面列举一些解决冲突的简单例子。对于很多应用而言,用这些策略或者其变体就足够解决大多数问题了:

新的比旧的更有效:在一些情况下,新的数据可以替代旧的数据。例如,如果数据代表了用户所选择角色的衣服颜色,那么最近的新的选择就应该覆盖老的选择。在这种情况下,我们可能会选择在云存储数据中存储时间戳。当处理这些冲突时,选择时间戳最新的数据(记住要选择一个可靠的时钟,并注意对不同时区的处理)。

一个数据好于其他数据:在一些情况下,我们是可以有方法在若干数据集中选取一个最好的。例如,如果数据代表了玩家在赛车比赛中的最佳时间,那么显然,在冲突发生时,我们应该保留成绩最好的那个数据。

进行合并:有可能通过计算两个数据集的合并版本来解决冲突。例如,我们的数据代表了用户解锁关卡的进度,那么我们需要的数据就是两个冲突数据的并集。通过这个方法,用户的关卡解锁进度就不会丢失了。这里的例子使用了这一策略的一个变形。

为更复杂的情况设计一个策略

当我们的游戏允许玩家收集可交换物品时(比如金币或者经验点数),情况会变得更加复杂一些。我们来假想一个游戏,叫做“金币跑酷”,游戏中的角色通过跑步不断地收集金币使自己变的富有。每个收集到的金币都会加入到玩家的储蓄罐中。

下面的章节将展示三种在多个设备间解决冲突的方案:有两个看上去还不错,可惜最终还是不能适用于所有情况,最后一个解决方案可以解决多个设备间的数据冲突。

第一个尝试:只保存总数

首先,这个问题看上去像是说:云存储的数据只要存储金币的数量就行了。但是如果就只有这些数据是可用的,那么解决冲突的方案将会严重受到限制。此时最佳的方案只能是在冲突发生时存储数值最大的数据。

想一下表1中所展现的场景。假设玩家一开始有20枚硬币,然后在设备A上收集了10个,在设备B上收集了15个。然后设备B将数据存储到了云端。当设备A尝试去存储的时候,冲突发生了。“只保存总数”的冲突解决方案会存储35作为这一数据的值(两数之间最大的)。

表1. 值保存最大的数(不佳的策略)

事件 设备A的数据 设备B的数据 云端的数据 实际的总数
开始阶段 20 20 20 20
玩家在A设备上收集了10个硬币 30 20 20 30
玩家在B设备上收集了15个硬币 30 35 20 45
设备B将数据存储至云端 30 35 35 45
设备A尝试将数据存储至云端,发生冲突 30 35 35 45
设备A通过选择两数中最大的数来解决冲突 35 35 35 45

这一策略显然会失败:玩家的金币数从20变成35,但实际上玩家总共收集了25个硬币(A设备10个,B设备15个),所以有10个硬币丢失了。只在云端存储硬币的总数是不足以实现一个健壮的冲突解决算法的。

第二个尝试:存储总数和变化值

另一个方法是在存储数据中包括一些额外的数据,如:自上次提交后硬币增加的数量(delta)。在这一方法中,存储的数据可以用一个二元组来表示(T, d),其中T是硬币的总数,而d是硬币增加的数量。

通过这样的数据存储结构,我们的冲突检测算法在鲁棒性上会有更大的提升空间。但是这个方法在某些情况下依然会存在问题。

下面是包含delta数值的冲突解决算法过程:

  • 本地数据:(T, d)
  • 云端数据:(T', d')
  • 解决后的数据:(T'+d, d)

例如,当我们在本地状态(T, d)和云端状态(T', d)之间发生了冲突时,可以将它们合并成(T'+d, d)。这意味着我们从本地拿出delta数据,并将它和云端的数据结合起来,乍一看,这种方法可以很好的计量多个设备所收集的金币。

该方法看上去很可靠,但它在具有移动网络的环境中难以适用:

  • 用户可能在设备不在线时存储数据。这些改变会以队列形式等待手机联网后提交。
  • 这个方法的同步机制是用最新的变化覆盖掉任何之前的变化。换句话说,第二次写入的变化会提交到云端(当设备联网了以后),而第一次写入的变化就被忽略了。

为了进一步说明,我们考虑一下表2所列的场景。在表2列出的一系列操作发生后,云端的状态将是(130, +5),最终冲突解决后的状态是(140, +10)。这是不正确的,因为从总体上而言,用户一共在A上收集了110枚硬币而在B上收集了120枚硬币。总数应该为250。

表2. “总数+增量”策略的失败案例

事件 设备A的数据 设备B的数据 云端的数据 实际的总数
开始阶段 (20, x) (20, x) (20, x) 20
玩家在A设备上收集了100个硬币 (120, +100) (20, x) (20, x) 120
玩家在A设备上又收集了10个硬币 (130, +10) (20, x) (20, x) 130
玩家在B设备上收集了115个硬币 (130, +10) (125, +115) (20, x) 245
玩家在B设备上又收集了5个硬币 (130, +10) (130, +5) (20, x) 250
设备B将数据存储至云端 (130, +10) (130, +5) (130, +5) 250
设备A尝试将数据存储至云端,发生冲突 (130, +10) (130, +5) (130, +5) 250
设备A通过将本地的增量和云端的总数相加来解决冲突 (140, +10) (130, +5) (140, +10) 250

注:x代表与该场景无关的数据

我们可能会尝试在每次保存后不重置增量数据来解决此问题,这样的话在每个设备上第二次存储的数据就能够代表用户至今为止收集到的所有硬币。此时,设备A在第二次本地存储完成后,数据将是(130, +110)而不是(130, +10)。然而,这样做的话就会发生如表3所述的情况:

表3. 算法改进后的失败案例

事件 设备A的数据 设备B的数据 云端的数据 实际的总数
开始阶段 (20, x) (20, x) (20, x) 20
玩家在A设备上收集了100个硬币 (120, +100) (20, x) (20, x) 120
设备A将状态存储到云端 (120, +100) (20, x) (120, +100) 120
玩家在A设备上又收集了10个硬币 (130, +110) (20, x) (120, +100) 130
玩家在B设备上收集了1个硬币 (130, +110) (21, +1) (120, +100) 131
设备B尝试向云端存储数据,发生冲突 (130, +110) (21, +1) (120, +100) 131
设备B通过将本地的增量和云端的总数相加来解决冲突 (130, +110) (121, +1) (121, +1) 131
设备A尝试将数据存储至云端,发生冲突 (130, +110) (121, +1) (121, +1) 131
设备A通过将本地的增量和云端的总数相加来解决冲突 (231, +110) (121, +1) (231, +110) 131

注:x代表与该场景无关的数据

现在我们碰到了另一个问题:我们给予了玩家过多的硬币。这个玩家拿到了211枚硬币,但实际上他只收集了111枚。

解决办法:

分析之前的几次尝试,我们发现这些策略存在这样的缺陷:无法知晓哪些硬币已经计数了,哪些硬币没有被计数,尤其是当多个设备连续提交的时候,算法会出现混乱。

该问题的解决办法是将我们在云端的数据存储结构改为字典类型,使用字符串+整形的键值对。每一个键值对都代表了一个包含硬币的“委托人”,而总数就应该是将所有记录的值加起来。这一设计的宗旨是每个设备有它自己的“委托人”,并且只有设备自己可以把硬币放到它的“委托人”当中。

字典的结构是:(A:a, B:b, C:c, ...),其中a代表了“委托人”A所拥有的硬币,b是“委托人”B所拥有的硬币,以此类推。

这样的话,新的冲突解决策略算法将如下所示:

  • 本地数据:(A:a, B:b, C:c, ...)
  • 云端数据:(A:a', B:b', C:c', ...)
  • 解决后的数据:(A:max(a,a'), B:max(b,b'), C:max(c,c'), ...)

例如,如果本地数据是(A:20, B:4, C:7)并且云端数据是(B:10, C:2, D:14),那么解决冲突后的数据将会是(A:20, B:10, C:7, D:14)。当然,应用的冲突解决逻辑可以根据具体的需求而有所差异。比如对于有一些应用,我们可能希望挑选最小的值。

为了测试新的算法,将它应用于任何一个之前提到过的场景。你将会发现它都能取得正确地结果。

表4阐述了这一点,它使用了表3中所提到的场景。注意下面所列出的关键点:

在初始状态,玩家有20枚硬币。该数据准确体现在了所有设备和云端中,我们用字典:(X:20)来代表它,其中X我们不用太多关心,初始化的数据是哪儿来对该问题没有影响。

当玩家在设备A上收集了100枚硬币,这一变化会作为一个字典保存到云端。字典的值是100是因为这就是玩家在设备A上收集的硬币数量。在这一过程中,没有要执行数据的计算(设备A仅仅是将玩家所收集的数据汇报给了云端)。

每一个新的硬币提交会打包成一个与设备关联的字典并保存到云端。例如,假设玩家又在设备A上收集了100枚硬币,那么对应字典的值被更新为110。

最终的结果就是,应用知道了玩家在每个设备上收集硬币的总数。这样它就能轻易地计算出实际的总数了。

表4. 键值对策略的成功应用案例

事件 设备A的数据 设备B的数据 云端的数据 实际的总数
开始阶段 (X:20, x) (X:20, x) (X:20, x) 20
玩家在A设备上收集了100个硬币 (X:20, A:100) (X:20) (X:20) 120
设备A将状态存储到云端 (X:20, A:100) (X:20) (X:20, A:100) 120
玩家在A设备上又收集了10个硬币 (X:20, A:110) (X:20) (X:20, A:100) 130
玩家在B设备上收集了1个硬币 (X:20, A:110) (X:20, B:1) (X:20, A:100) 131
设备B尝试向云端存储数据,发生冲突 (X:20, A:110) (X:20, B:1) (X:20, A:100) 131
设备B解决冲突 (X:20, A:110) (X:20, A:100, B:1) (X:20, A:100, B:1) 131
设备A尝试将数据存储至云端,发生冲突 (X:20, A:110) (X:20, A:100, B:1) (X:20, A:100, B:1) 131
设备A解决冲突 (X:20, A:110, B:1) (X:20, A:100, B:1) (X:20, A:110, B:1),total 131 131

清除你的数据

在云端允许存储数据的大小是有限制的,所以在后续的论述中,我们将会关注如何避免创建过大的词典。一开始,看上去每个设备只会有一条词典记录,即使是非常激进的用户也不太会拥有上千种不同的设备(对应上千条字典记录)。然而, 获取设备ID的方法很难,并且我们认为这是一种不好的实践方式,所以我们应该使用一个安装ID,这更容易获取也更可靠。这样的话就意味着,每一次用户在每台设备安装一次就会产生一个ID。假设每个键值对占据32字节,由于一个个人云存储缓存最多可以有128K的大小,因此最多可以存储4096条记录。

在现实场景中,你的数据可能更加复杂。在这种情况下,存储数据的记录条数也会进一步受到限制。具体而言则需要取决于实现,比如可能需要添加时间戳来指明每条记录是何时修改的。当你检测到有一条记录在过去几个礼拜或者几个月的时间内都没有被修改,那么就可以安全地将金币数据转移到另一条记录中并删除老的记录。