Оптимистическая репликация

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

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

Алгоритмы

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

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

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

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

Примеры

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

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

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

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

Usenet и другие системы, использующие правило записи Томаса (см. Rfc677 ).
Репликация базы данных с несколькими хозяевами ^[4]
система Coda Распределенная файловая
Операционная трансформация , теоретическая основа группового редактирования.
Одноранговые вики
Бесконфликтные реплицируемые типы данных
Байю ^[5] распределенная база данных
IceCube ^[6]

Подразумеваемое

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

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

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

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

Ссылки

^ Ладен, Р.; Лисков Б.; Шрира, Л.; Гемават, С. (1992). «Обеспечение высокой доступности с помощью ленивой репликации». Транзакции ACM в компьютерных системах . 10 (4): 360–391. CiteSeerX 10.1.1.586.7749 . дои : 10.1145/138873.138877 . S2CID 2219840 .
^ Ладен, Р.; Лисков Б.; Шрира, Л. (1990). Ленивая репликация: использование семантики распределенных сервисов . Материалы девятого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 43–57. дои : 10.1145/93385.93399 .
^ Сайто, Ясуси; Шапиро, Марк (2005). «Оптимистическая репликация». Обзоры вычислительной техники ACM . 37 (1): 42–81. CiteSeerX 10.1.1.324.3599 . дои : 10.1145/1057977.1057980 . S2CID 1503367 .
^ Грей, Дж .; Хелланд, П.; О'Нил, П .; Шаша, Д. (1996). Опасности репликации и решение (PDF) . Материалы Международной конференции ACM SIGMOD 1996 года по управлению данными . стр. 173–182. дои : 10.1145/233269.233330 . ^{[ постоянная мертвая ссылка ]}
^ Терри, Д.Б.; Теймер, ММ; Петерсен, К.; Демерс, Эй Джей; Спрейцер, MJ; Хаузер, CH (1995). Управление конфликтами обновлений в Bayou — слабосвязной реплицируемой системе хранения . Материалы пятнадцатого симпозиума ACM по принципам операционных систем. стр. 172–182. дои : 10.1145/224056.224070 .
^ Кермаррек, AM; Роустрон, А.; Шапиро, М.; Друшель, П. (2001). Подход IceCube к согласованию расходящихся реплик . Материалы двадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 210–218. дои : 10.1145/383962.384020 .

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

Сайто, Ясуси; Шапиро, Марк (сентябрь 2003 г.). «Оптимистическая репликация» (PDF) . Майкрософт.

[Ladin1992-1] Ладен, Р.; Лисков Б.; Шрира, Л.; Гемават, С. (1992). «Обеспечение высокой доступности с помощью ленивой репликации». Транзакции ACM в компьютерных системах . 10 (4): 360–391. CiteSeerX 10.1.1.586.7749 . дои : 10.1145/138873.138877 . S2CID 2219840 .

[Ladin1990-2] Ладен, Р.; Лисков Б.; Шрира, Л. (1990). Ленивая репликация: использование семантики распределенных сервисов . Материалы девятого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 43–57. дои : 10.1145/93385.93399 .

[saito2005-3] Сайто, Ясуси; Шапиро, Марк (2005). «Оптимистическая репликация». Обзоры вычислительной техники ACM . 37 (1): 42–81. CiteSeerX 10.1.1.324.3599 . дои : 10.1145/1057977.1057980 . S2CID 1503367 .

[Gray1996-4] Грей, Дж .; Хелланд, П.; О'Нил, П .; Шаша, Д. (1996). Опасности репликации и решение (PDF) . Материалы Международной конференции ACM SIGMOD 1996 года по управлению данными . стр. 173–182. дои : 10.1145/233269.233330 . ^{[ постоянная мертвая ссылка ]}

[Terry1995-5] Терри, Д.Б.; Теймер, ММ; Петерсен, К.; Демерс, Эй Джей; Спрейцер, MJ; Хаузер, CH (1995). Управление конфликтами обновлений в Bayou — слабосвязной реплицируемой системе хранения . Материалы пятнадцатого симпозиума ACM по принципам операционных систем. стр. 172–182. дои : 10.1145/224056.224070 .

[Kermarrec2001-6] Кермаррек, AM; Роустрон, А.; Шапиро, М.; Друшель, П. (2001). Подход IceCube к согласованию расходящихся реплик . Материалы двадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . стр. 210–218. дои : 10.1145/383962.384020 .

[1]

[2]

[3]

[4]

[5]

[6]