Оптимистичная репликация - Optimistic replication

Оптимистичная репликация, также известен как ленивая репликация,[1][2] это стратегия для репликация, в котором реплики могут расходиться.[3]

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

Алгоритмы

Оптимистичный алгоритм репликации состоит из пяти элементов:

  1. Подача операции: Пользователи отправляют операции на независимых сайтах.
  2. Распространение: Каждый сайт разделяет операции, о которых он знает, с остальной частью системы.
  3. Планирование: Каждый сайт определяет порядок операций, о которых он знает.
  4. Решение конфликта: Если есть какие-либо конфликты среди операций, запланированных сайтом, он должен каким-то образом их изменить.
  5. Обязательство: Сайты согласовывают окончательный график и результат разрешения конфликта, и операции становятся постоянными.

Существует две стратегии распространения: передача состояния, при которой сайты распространяют представление о текущем состоянии, и передача операций, при которой сайты распространяют операции, которые были выполнены (по сути, список инструкций о том, как достичь нового состояния).

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

Примеры

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

  1. Представление операции: пользователи редактируют локальные версии файлов.
  2. Распространение: пользователи вручную получают обновления с центрального сервера или отправляют изменения, когда пользователь чувствует, что они готовы.
  3. Планирование: операции планируются в порядке их получения центральным сервером.
  4. Разрешение конфликтов: когда пользователь отправляет или извлекает данные из центрального репозитория, любые конфликты будут помечены, чтобы этот пользователь мог исправить вручную.
  5. Обязательство: после того, как центральный сервер принимает изменения, которые нажимает пользователь, они фиксируются навсегда.

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

Другие примеры включают:

Последствия

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

В качестве простого примера, если приложение содержит способ просмотра некоторой части состояния базы данных и способ его редактирования, то пользователи могут редактировать это состояние, но не видеть его изменения в средстве просмотра. Обеспокоенные тем, что их правка «не сработала», они могут попробовать ее снова, возможно, более одного раза. Если обновлений нет идемпотент (например, они увеличивают значение), это может привести к катастрофе. Даже если они идемпотентны, ложные обновления базы данных могут привести к снижению производительности, особенно когда системы баз данных обрабатывают большие нагрузки; это может превратиться в порочный круг.

Тестирование приложений часто проводится в тестовой среде меньшего размера (возможно, только с одним сервером) и менее загруженной, чем «живая» среда. Поведение при репликации такой установки может отличаться от реальной среды, что означает, что задержка репликации вряд ли будет наблюдаться при тестировании, маскируя ошибки, связанные с репликацией. Разработчики приложений должны быть очень осторожны с предположениями, которые они делают о влиянии обновления базы данных, и обязательно имитировать задержку в своих тестовых средах.

Оптимистически реплицируемые базы данных должны быть очень осторожны с предложением таких функций, как ограничения достоверности данных. Если любое данное обновление может быть принято или не принято в зависимости от текущего состояния записи, тогда два обновления (A и B) могут быть индивидуально законными по отношению к начальному состоянию системы, но одно или несколько обновлений могут быть незаконными. против состояния системы после другого обновления (например, A и B оба допустимы, но AB или BA - незаконны). Если A и B оба инициируются примерно в одно и то же время в базе данных, то A может быть успешно применен на некоторых узлах, а B - на других, но как только A и B «встречаются», и одна попытка выполняется на узле, который уже применив другой, будет обнаружен конфликт. В этом случае система должна решить, какое обновление окончательно «выиграет», и принять меры к тому, чтобы все узлы, которые уже применили проигравшее обновление, вернули его. Однако некоторые узлы могут временно раскрыть состояние с отмененным обновлением, и может не быть способа сообщить пользователю, который инициировал обновление, о его сбое, не требуя от них ожидания (потенциально вечно) подтверждения принятия на каждом узле.

использованная литература

  1. ^ Ладин, Р .; Лисков, Б .; Shrira, L .; Гемават, С. (1992). «Обеспечение высокой доступности с помощью ленивой репликации». ACM-транзакции в компьютерных системах. 10 (4): 360–391. CiteSeerX  10.1.1.586.7749. Дои:10.1145/138873.138877. S2CID  2219840.
  2. ^ Ладин, Р .; Лисков, Б .; Шрира, Л. (1990). Ленивая репликация: использование семантики распределенных сервисов. Материалы девятого ежегодного ACM Симпозиум по принципам распределенных вычислений. С. 43–57. Дои:10.1145/93385.93399.
  3. ^ Сайто, Ясуши; Шапиро, Марк (2005). «Оптимистическая репликация». Опросы ACM Computing. 37 (1): 42–81. CiteSeerX  10.1.1.324.3599. Дои:10.1145/1057977.1057980. S2CID  1503367.
  4. ^ Грей, Дж.; Helland, P .; О’Нил, П.; Шаша, Д. (1996). Опасности репликации и решение (PDF). Труды 1996 г. ACM SIGMOD Международная конференция по управлению данными. С. 173–182. Дои:10.1145/233269.233330.[постоянная мертвая ссылка ]
  5. ^ Терри, Д. Б.; Theimer, M.M .; Петерсен, К .; Demers, A.J .; Spreitzer, M.J .; Хаузер, К. (1995). Управление конфликтами обновлений в Bayou, слабо подключенной реплицированной системе хранения.. Труды пятнадцатого симпозиума ACM по принципам операционных систем. С. 172–182. Дои:10.1145/224056.224070.
  6. ^ Kermarrec, A.M .; Rowstron, A .; Шапиро, М .; Друщель, П. (2001). Подход IceCube к согласованию расходящихся реплик. Материалы двадцатого ежегодного ACM Симпозиум по принципам распределенных вычислений. С. 210–218. Дои:10.1145/383962.384020.

внешние ссылки