Вектор версий
Вектор версий — это механизм отслеживания изменений данных в распределенной системе , где несколько агентов могут обновлять данные в разное время. Вектор версий позволяет участникам определить, предшествовало ли одно обновление другому ( случилось-раньше ), последовало за ним или два обновления произошли одновременно (и, следовательно, могут конфликтовать друг с другом). Таким образом, векторы версий позволяют отслеживать причинно-следственные связи между репликами данных и являются базовым механизмом оптимистической репликации . С математической точки зрения вектор версий генерирует предварительный заказ , который отслеживает события, которые предшествуют и, следовательно, могут влиять на последующие обновления.
Векторы версий поддерживают состояние, идентичное состоянию векторных часов , но правила обновления немного отличаются; в этом примере реплики могут либо подвергаться локальным обновлениям (например, пользователь редактирует файл на локальном узле), либо синхронизироваться с другой репликой:
- Первоначально все векторные счетчики равны нулю.
- Каждый раз, когда реплика сталкивается с событием локального обновления, она увеличивает свой счетчик в векторе на единицу.
- Каждый раз, когда две реплики a и b синхронизируются, они обе устанавливают элементы в своей копии вектора на максимум элемента по обоим счетчикам: . После синхронизации две реплики имеют идентичные векторы версий.
![{\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edd5c158c15a0c45f4ffa677f78f6486a1acbf3b)
Пары реплик a , b можно сравнить, проверив их векторы версий, и определить, что они либо: идентичны ( ), одновременно ( ), или приказал ( или ). Упорядоченное отношение определяется как: Вектор тогда и только тогда, когда каждый элемент меньше или равно соответствующему элементу в , и хотя бы один из элементов строго меньше. Если ни один или , но векторы не идентичны, то эти два вектора должны совпадать.
Векторы версий [1] или варианты используются для отслеживания обновлений во многих распределенных файловых системах, таких как Coda (файловая система) и Ficus, и являются основной структурой данных, лежащей в основе оптимистической репликации. [2]
Другие механизмы
[ редактировать ]- Хэш-истории [3] избегайте использования счетчиков, сохраняя набор хешей каждой обновленной версии и сравнивая эти наборы путем включения набора. Однако этот механизм может дать лишь вероятностные гарантии.
- Краткая версия векторов [4] позволяют значительно сэкономить пространство при работе с несколькими реплицируемыми элементами, например, в структурах каталогов файловых систем.
- Марки версий [5] разрешить отслеживание переменного количества реплик и не прибегать к счетчикам. Этот механизм может отображать проблемы масштабируемости в некоторых настройках, но его можно заменить часами интервального дерева.
- Интервальные древовидные часы [6] обобщать векторы версий и векторные часы и обеспечивает динамическое количество реплик/процессов.
- Векторы ограниченной версии [7] разрешить ограниченную реализацию со счетчиками ограниченного размера, если пары реплик могут быть атомарно синхронизированы.
- Векторы пунктирной версии [8] масштабируемость адреса с небольшим набором серверов, обеспечивающих доступ к реплике для большого количества одновременных клиентов.
Ссылки
[ редактировать ]- ^ Дуглас Паркер, Джеральд Попек, Джерард Рудисин, Аллен Стоутон, Брюс Уокер, Эвелин Уолтон, Джоанна Чоу, Дэвид Эдвардс, Стивен Кайзер и Чарльз Клайн . Обнаружение взаимной несогласованности в распределенных системах. Труды по программной инженерии. 1983 год
- ^ Дэвид Ратнер, Питер Райхер и Джеральд Попек. Динамическое обслуживание векторов версий. Технический отчет CSD-970022, факультет компьютерных наук, Калифорнийский университет, Лос-Анджелес, 1997 г.
- ^ БюнгХун Кан, Роберт Виленски и Джон Кубятович.Подход хеш-истории для устранения взаимных несогласованностей. ICDCS, стр. 670–677, Компьютерное общество IEEE, 2003.
- ^ Далия Малхи и Дуг Терри. Векторы краткой версии в WinFS. Распределенные вычисления, Vol. 20, 2007.
- ^ Пауло Алмейда, Карлос Бакеро и Виктор Фонте. Штампы версий: децентрализованные векторы версий. ICDCS, стр. 544–551, 2002 г.
- ^ Пауло Алмейда, Карлос Бакеро и Виктор Фонте. Интервальные древовидные часы. OPODIS, Конспекты лекций по информатике, Vol. 5401, стр. 259–274, Спрингер, 2008 г.
- ^ Хосе Алмейда, Пауло Алмейда и Карлос Бакеро. Векторы ограниченной версии. ДИСК: Международный симпозиум по распределенным вычислениям, LNCS, 2004 г.
- ^ Нуно Прегиса, Карлос Бакеро, Паулу Алмейда, Виктор Фонте и Рикардо Гонсалвес. Краткое объявление: Эффективное отслеживание причинно-следственных связей в распределенных системах хранения данных с векторами версий. ACM PODC, стр. 335-336, 2012.