Вектор версии - Version vector

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

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

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

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

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

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

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

Рекомендации

внешняя ссылка

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