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

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

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

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

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

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

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

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