Версия вектора

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

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

• Изначально все векторные счетчики равны нулю.
• Каждый раз, когда реплика сталкивается с событием локального обновления, она увеличивает свой счетчик в векторе на единицу.
• Каждый раз, когда две реплики a и b синхронизируются, они обе устанавливают элементы в своей копии вектора на максимум элемента по обоим счетчикам: . После синхронизации две реплики имеют идентичные векторы версий. ${\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}$

Пары реплик, a , b , можно сравнить, проверив их векторы версий, и определить, являются ли они: идентичными ( ), параллельными ( ) или упорядоченными ( или ). Упорядоченное отношение определяется как: Вектор тогда и только тогда, когда каждый элемент из меньше или равен своему соответствующему элементу в , и по крайней мере один из элементов строго меньше. Если ни один из них или , но векторы не идентичны, то два вектора должны быть параллельными. ${\displaystyle a=b}$ ${\displaystyle a\parallel b}$ ${\displaystyle a<b}$ ${\displaystyle b<a}$ ${\displaystyle a<b}$ ${\displaystyle V_{a}}$ ${\displaystyle V_{b}}$ ${\displaystyle a<b}$ ${\displaystyle b<a}$

Векторы версий ^[1] или варианты используются для отслеживания обновлений во многих распределенных файловых системах, таких как Coda (файловая система) и Ficus, и являются основной структурой данных, лежащей в основе оптимистической репликации. ^[2]

Другие механизмы

• Hash History ^[3] избегают использования счетчиков, сохраняя набор хешей каждой обновленной версии и сравнивая эти наборы путем включения набора. Однако этот механизм может дать только вероятностные гарантии.
• Сжатые векторы версий ^[4] позволяют существенно экономить место при обработке нескольких реплицированных элементов, например, в структурах каталогов в файловых системах.
• Version Stamps ^[5] позволяют отслеживать переменное количество реплик и не прибегают к счетчикам. Этот механизм может отображать проблемы масштабируемости в некоторых настройках, но может быть заменен Interval Tree Clocks.
• Интервальные древовидные часы ^[6] обобщают векторы версий и векторные часы и допускают динамическое количество реплик/процессов.
• Векторы с ограниченными версиями ^[7] допускают ограниченную реализацию с ограниченными размерами счетчиков, при условии, что пары реплик могут быть атомарно синхронизированы.
• Векторы точечных версий ^[8] решают проблему масштабируемости с помощью небольшого набора серверов, выступающих посредниками в доступе к репликам большого числа одновременных клиентов.

Ссылки

1. Дуглас Паркер, Джеральд Попек, Джерард Рудисин, Аллен Стоутон, Брюс Уокер, Эвелин Уолтон, Джоанна Чоу, Дэвид Эдвардс, Стивен Кисер и Чарльз Клайн. Обнаружение взаимной несогласованности в распределенных системах. Труды по программной инженерии. 1983
2. Дэвид Ратнер, Питер Рейхер и Джеральд Попек. Поддержка динамического вектора версий. Технический отчет CSD-970022, Кафедра компьютерных наук, Калифорнийский университет, Лос-Анджелес, 1997
3. Бёнхун Канг, Роберт Виленски и Джон Кубиатович. Подход к хэш-истории для согласования взаимной несогласованности. ICDCS, стр. 670-677, IEEE Computer Society, 2003.
4. Далия Малхи и Дуг Терри. Сжатые версии векторов в WinFS. Распределенные вычисления, т. 20, 2007.
5. Пауло Алмейда, Карлос Бакеро и Виктор Фонте. Версии марок: децентрализованные векторы версий. ICDCS, стр. 544-551, 2002.
6. Пауло Алмейда, Карлос Бакеро и Виктор Фонте. Интервальные деревянные часы. OPODIS, Lecture Notes in Computer Science, Vol. 5401, стр. 259-274, Springer, 2008.
7. Хосе Альмейда, Пауло Альмейда и Карлос Бакеро. Векторы ограниченной версии. DISC: Международный симпозиум по распределенным вычислениям, LNCS, 2004.
8. Нуно Прегиса, Карлос Бакеро, Паулу Алмейда, Виктор Фонте и Рикардо Гонсалвес. Краткое объявление: Эффективное отслеживание причинно-следственных связей в распределенных системах хранения данных с точечными векторами версий. ACM PODC, стр. 335–336, 2012 г.

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

• Почему логические часы просты (сравнение причинно-следственных историй, векторных часов и векторов версий)