Question

編寫: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條記錄。

在現實場景中，你的數據可能更加複雜。在這種情況下，存儲數據的記錄條數也會進一步受到限制。具體而言則需要取決於實現，比如可能需要添加時間戳來指明每條記錄是何時修改的。當你檢測到有一條記錄在過去幾個禮拜或者幾個月的時間內都沒有被修改，那麼就可以安全地將金幣數據轉移到另一條記錄中並刪除老的記錄。