Устранение конфликтов сохранения в облаке

В этой статье описывается, как разрабатывать надежные стратегии разрешения конфликтов для приложений, которые хранят данные в облаке с помощью службы Cloud Save. Сервис Cloud Save позволяет хранить данные приложений пользователей на серверах Google. Ваше приложение может получать и обновлять пользовательские данные на Android устройствах, iOS устройствах, или из веб-приложений с помощью Cloud Save API.

Процесс сохранения и загрузки в/из Cloud Save прост: необходимо всего лишь сериализовать данные в/из массива байтов и хранения этих массивов в облаке. Однако, когда ваш пользователь имеет несколько устройств, и два или более из них пытаются сохранить данные в облако, сохранения могут конфликтовать, и вы должны решить, как устранить конфликт. Структура ваших данных в облаке в значительной степени определяет, насколько надежным может быть ваше разрешение конфликтов, поэтому вы должны разрабатывать структуру данных тщательно, чтобы позволить вашей логике разрешения конфликтов обрабатывать каждый случай правильно.

Статья начинается с описания нескольких несовершенных подходов и объясняет, в чем их ошибки. Затем она предоставляет решение для разрешения конфликтов. Основное внимание уделяется играм, но вы можете применять те же принципы для любых приложений, которые хранят данные в облаке.

Уведомления о конфликтах

OnStateLoadedListener методы отвечают за загрузку данных о состоянии приложения с серверов Google. Метод обратного вызова OnStateLoadedListener.onStateConflict предоставляет механизм для вашего приложения для разрешения конфликтов между локальным состоянием устройства пользователя и состоянием в облаке:

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

На этот момент приложение должно выбрать один из наборов данных, или оно может послать новый набор данных, представляющий объединенные данные. Вы должны сами реализовать свою логику разрешения конфликтов.

Важно понимать, что служба Cloud Save синхронизирует данные в фоновом режиме. Таким образом, вы должны убедиться, что ваше приложение будет готово получать обратные вызовы вне контекста, где вы создаете данные. В частности, если приложение Google Play обнаруживает конфликт в фоновом режиме, функция обратного вызова будет вызвана в следующий раз, когда вы попытаетесь загрузить данные, что может и не произойти до следующего запуска приложения.

Таким образом, дизайн сохранения ваших данных в облако и разрешения конфликтов должны быть контекстно-независимыми: учитывая оба конфликтных набора данных, вы должны быть в состоянии разрешить конфликт, используя только доступные данные, без консультаций с каким либо внешним контекстом.

Обработка простых случаев

Вот несколько простых примеров разрешения конфликтов. Для многих приложений, достаточно использовать одну из приведенных ниже стратегий:

  • Новые лучше, чем старые. В некоторых случаях, новые данные всегда должны заменить старые данные. Например, если данные представляют собой выбор игрока для цвета рубашки персонажа, то более поздний выбранный цвет должен переопределить предыдущий. В этом случае, вам нужно хранить в облаке также время, когда выбор был сделан. При разрешении конфликта, выберите набор данных с самой последней временной отметкой (не забудьте использовать надежные часы, и будьте осторожны с различными часовыми поясами).
  • Один набор данных явно лучше, чем другой. В других случаях, всегда будет ясно, какие данные являются "лучшими". Например, если данные представляют лучшее время игрока в гоночной игре, то становится ясно, что в случае конфликта вы должны оставить лучшее (наименьшее) время.
  • Объединение данных. Иногда, можно разрешить конфликт путем слияния двух конфликтующих множеств. Например, если данные представляют собой набор уровней, которые игрок разблокировал, то решить конфликт данных можно просто путем объединение двух конфликтующих множеств. Таким образом, игроки не потеряют уровни, которые они разблокировали. CollectAllTheStars - пример игры использующий данный вариант стратегии.

Разработка стратегии для более сложных случаев

Более сложный случай происходит, когда ваша игра позволяет игроку собирать взаимозаменяемые детали или блоки, такие как золотые монеты или очки опыта. Рассмотрим гипотетическую игру под названием Монетные Гонки, бесконечно бегущий персонаж, целью которого является собирание монет. Каждая собранная монета будет добавлена в копилку игрока.

В следующих разделах описаны три стратегии разрешения конфликтов синхронизации между несколькими устройствами: два, которые звучат хорошо, но в конечном итоге не могут успешно решить все сценарии, и одно окончательное решения, которое может разрешить конфликты любого количества устройств.

Первая попытка: Хранение только суммарных значений

На первый взгляд, может показаться, что облако должно просто хранить количество монет в банке. Но если это и все доступные данные, то разрешение конфликтов будет сильно ограничено. Лучшее, что вы могли бы сделать это взять самое большое из двух чисел в случае конфликта.

Рассмотрим сценарий, показанный в таблице 1. Предположим, игрок изначально имеет 20 монет, а затем собирает 10 монет на устройства А и 15 монет на устройства B. Тогда устройство В сохраняет состояние в облако. Когда устройство А пытается сохранить, возникает конфликт. Алгоритм разрешения конфликтов "Хранение только суммарных значений" для решения конфликта запишет 35 (самое большое из двух чисел).

Таблица 1. Хранение только общего количества монет (неудачная стратегия).

Событие Данные на устойстве А Данные на устойстве B Данные в облаке Фактическое значение
Начальные условия 20 20 20 20
Игрок собирает 10 монет на устройстве А 30 20 20 30
Игрок собирает 15 монет на устройстве B 30 35 20 45
Устройство B сохраняет состояние в облако 30 35 35 45
Устройство А пытается сохранить состояние в облако.
Обнаружен конфликт.
30 35 35 45
Устройство А решает конфликт, выбирая самое большое из двух чисел. 35 35 35 45

Эта стратегия потерпит неудачу — банк игрока прошел путь от 20 до 35, хотя пользователь на самом деле собрал в общей сложности 25 монет (10 на устройства А и 15 на устройства В). Так что 10 монет были потеряны. Хранить в облаке только общее количество монет недостаточно для реализации надежного алгоритма разрешения конфликтов.

Вторая попытка: Хранение суммарных значений и дельты

Иной подход будет включать дополнительное поле в сохраняемых данных: добавленное количество монет (дельта) со времени последнего сохранения. При таком подходе сохраняемые данные могут быть представлены в виде кортежа (T,d) где T это общее количество монет и d это количество монет, которые вы только что добавили.

С этой структурой, ваш алгоритм разрешения конфликтов должен быть более надежным, как показано ниже. Но такой подход всё еще не дает вашему приложению достоверную картину общего состояния игрока.

Вот алгоритм разрешения конфликтов, включающий дельту:

  • Локальные данные: (T, d)
  • Данные облака: (T', d')
  • Данные после разрешения конфликта: (T' + d, d)

Например, когда у вас конфликт между локальным состоянием (T,d) и состоянием облака (T',d'), вы можете решить конфлик как (T'+d, d). Это означает, что вы берете дельту ваших локальных данных и объединяете с облачными данными, надеясь, что это будет правильно учитывать любые золотые монеты, которые были собраны на другом устройстве.

Такой подход может показаться многообещающим, но он ломается в динамической мобильной среде:

  • Пользователи могут сохранить состояние, когда устройство находится в автономном режиме. Эти изменения будут в очереди на отправку, когда устройство снова подключится к сети.
  • Синхронизация работает таким образом, что самое последнее изменение переопределяет все предыдущие изменения. Другими словами, только вторая версия отправляется в облако (это происходит, когда устройство в конечном итоге снова онлайн), а дельта первой записи игнорируется.

Для иллюстрации, рассмотрим сценарий показанный в Таблице 2. После серии операций, показанных в таблице, состояние облака будет (130, +5). Это означает, что после пересчета состояние будет (140, +10). Это неверно, потому что в общей сложности, пользователь собрал 110 монет на устройства А и 120 монет на устройства В. Общая сумма должна быть 250 монет.

Таблица 2. Некорректный сценарий для стратегии сумма+дельта.

Событие Данные на устойстве А Данные на устойстве B Данные в облаке Фактическое значение
Начальные условия (20, x) (20, x) (20, x) 20
Игрок собирает 100 монет на устройстве А (120, +100) (20, x) (20, x) 120
Игрок собирает ещё 10 монет на устройстве А (130, +10) (20, x) (20, x) 130
Игрок собирает 115 монет на устройстве B (130, +10) (125, +115) (20, x) 245
Игрок собирает еще 5 монет на устройстве B (130, +10) (130, +5) (20, x) 250
Устройство B загружает свои данные в облако (130, +10) (130, +5) (130, +5) 250
Устройство А пытается загрузить свои данные в облако.
Обнаружен конфликт.
(130, +10) (130, +5) (130, +5) 250
Устройство А разрешает конфликт, применяя локальную дельту к общей сумме облака. (140, +10) (130, +5) (140, +10) 250

(*): x представляет данные, которые не имеют отношения к нашему сценарию.

Вы могли бы попытаться решить эту проблему, не сбрасывая дельту после каждого сохранения, так что второе сохранение на каждом устройстве продолжает суммировать монеты. С учетом этого изменения второе сохранение сделанное устройством А будет (130, +110) вместо (130, +10). Тем не менее, тогда вы столкнётесь с проблемой, показанной в таблице 3.

Таблица 3. Некорректный сценарий для модифицированного алгоритма.

Событие Данные на устойстве А Данные на устойстве B Данные в облаке Фактическое значение
Начальные условия (20, x) (20, x) (20, x) 20
Игрок собирает 100 монет на устройстве А (120, +100) (20, x) (20, x) 120
Устройство А сохраняет состояние в облако (120, +100) (20, x) (120, +100) 120
Игрок собирает ещё 10 монет на устройстве А (130, +110) (20, x) (120, +100) 130
Игрок собирает 1 монету на устройстве B (130, +110) (21, +1) (120, +100) 131
Устройство B пытается сохранить состояние в облако.
Обнаружен конфликт.
(130, +110) (21, +1) (120, +100) 131
Устройство B решает конфликт, применяя локальную дельту к общей сумме из облака. (130, +110) (121, +1) (121, +1) 131
Устройство А пытается загрузить свои данные в облако.
Обнаружен конфликт.
(130, +110) (121, +1) (121, +1) 131
Устройство А разрешает конфликт, применяя локальную дельту к общей сумме облака. (231, +110) (121, +1) (231, +110) 131

(*): x представляет данные, которые не имеют отношения к нашему сценарию.

Теперь у вас есть противоположная проблема: вы даете игроку слишком много монет. Игрок получил 211 монет, когда на самом деле он собрал только 111 монет.

Решение: Храните промежуточные суммы на устройстве

Анализируя предыдущие попытки, кажется, что эти стратегии принципиально упускают возможность узнать, какие монеты уже были подсчитаны и какие монеты еще не были подсчитаны, особенно при наличии нескольких последовательных сохранений, поступающих от различных устройств.

Решение проблемы заключается в изменении структуры ваших облачных данных на таблицу, которая связывает строки и целые числа. Каждая пара ключ-значение в этой таблице представляет собой "ящик", который содержит монеты, а общее количество монет при сохранении это сумма значений всех записей. Фундаментальный принцип этого подхода это то, что каждое устройство имеет свой собственный ящик, и только само устройство может положить монеты в этот ящик.

Структура таблицы: (A:a, B:b, C:c, ...), где 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 не имеет существенного значения — нам все равно откуда эти исходные данные пришли.
  • Когда игрок собирает 100 монет на устройстве А, это изменение сохраняется в виде таблицы в облако. Значение равно 100, потому что это количество монет, которое игрок собрал на устройстве А. В этот момент расчет данных не выполняется — устройства А просто отчитывается о количестве монет, которые игрок на нем собрал.
  • Каждая новая отправка монет упаковывается в виде таблицы, и связанное с устройством значение сохраняется в облако. Например, когда игрок собирает ещё 10 монет на устройстве А, значение связанное с устройством А обновляется до 110.
  • Конечным результатом является то, что приложение знает общее количество монет игрока, собранных на каждом устройстве. Таким образом, можно легко вычислить сумму.

Таблица 4. Успешная стратегия приложения с помощью пар ключ-значение.

Событие Данные на устойстве А Данные на устойстве B Данные в облаке Фактическое значение
Начальные условия (X:20, x) (X:20, x) (X:20, x) 20
Игрок собирает 100 монет на устройстве А (X:20, A:100) (X:20) (X:20) 120
Устройство А сохраняет состояние в облако (X:20, A:100) (X:20) (X:20, A:100) 120
Игрок собирает ещё 10 монет на устройстве А (X:20, A:110) (X:20) (X:20, A:100) 130
Игрок собирает 1 монету на устройстве B (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
Устройство А пытается загрузить свои данные в облако.
Обнаружен конфликт.
(X:20, A:110) (X:20, A:100, B:1) (X:20, A:100, B:1) 131
Устройство А разрешает конфликт (X:20, A:110, B:1) (X:20, A:100, B:1) (X:20, A:110, B:1)
итого: 131
131

Очистка ваших данных

Существует ограничение на размер сохраненных данных в облаке, поэтому в соответствии со стратегией изложенной в этой статье, вы не должны создавать слишком большие таблицы. На первый взгляд может показаться, что таблица будет иметь только одну запись на устройство, и даже с большим энтузиазмом вряд ли пользователь будет иметь тысячи устройств. Однако получение идентификатора устройства является трудным и считается плохой практикой, поэтому вместо этого вы должны использовать идентификатор инсталяции, которую легче получить. Это означает, что таблица может иметь одну запись для каждой инсталяции пользователя вашего приложения на каждом устройстве. Предположим, что каждая пара ключ-значение занимает 32 байта, а поскольку индивидуальный буфер в облаке может быть размером до 128К, то вы безопасно можете сохранить до 4096 записей.

В реальной жизни ваши данные, вероятно, будут более сложными, чем количество монет. В этом случае количество записей в этой таблице может быть более ограниченно. В зависимости от реализации, возможно, имеет смысл хранить временную метку изменения каждой записи. Когда вы обнаружите, что данная запись не менялась в течение последних нескольких недель или месяцев, то, вероятно, можно переместить монеты в другую запись и удалить старую.