Vector de versión

Un vector de versiones es un mecanismo para rastrear los cambios en los datos de un sistema distribuido , donde múltiples agentes pueden actualizar los datos en diferentes momentos. El vector de versiones permite a los participantes determinar si una actualización precedió a otra ( sucedió antes ), la siguió o si ambas se produjeron simultáneamente (y, por lo tanto, podrían entrar en conflicto). De esta forma, los vectores de versiones permiten rastrear la causalidad entre las réplicas de datos y constituyen un mecanismo básico para la replicación optimista . En términos matemáticos, el vector de versiones genera un preorden que registra los eventos que preceden a las actualizaciones posteriores y que, por consiguiente, pueden influir en ellas.

Los vectores de versión mantienen un estado idéntico al de un reloj vectorial , pero las reglas de actualización difieren ligeramente; en este ejemplo, las réplicas pueden experimentar actualizaciones locales (por ejemplo, cuando el usuario edita un archivo en el nodo local) o pueden sincronizarse con otra réplica:

• Inicialmente, todos los contadores vectoriales son cero.
• Cada vez que una réplica experimenta un evento de actualización local, incrementa su propio contador en el vector en uno.
• Cada vez que dos réplicas a y b se sincronizan, ambas establecen los elementos de su copia del vector al valor máximo del elemento en ambos contadores: ${\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}$Tras la sincronización, las dos réplicas tienen vectores de versión idénticos.

Los pares de réplicas, a , b , se pueden comparar inspeccionando sus vectores de versión y determinar si son: idénticos (${\displaystyle a=b}$), concurrente (${\displaystyle a\parallel b}$), o ordenado (${\displaystyle a<b}$o${\displaystyle b<a}$). La relación ordenada se define como: Vector${\displaystyle a<b}$si y solo si cada elemento de${\displaystyle V_{a}}$es menor o igual que su elemento correspondiente en${\displaystyle V_{b}}$y al menos uno de los elementos es estrictamente menor que. Si ninguno${\displaystyle a<b}$o${\displaystyle b<a}$, pero los vectores no son idénticos, entonces los dos vectores deben ser concurrentes.

Los vectores de versión ^{[ 1 ]} o variantes se utilizan para rastrear las actualizaciones en muchos sistemas de archivos distribuidos, como Coda (sistema de archivos) y Ficus, y son la principal estructura de datos detrás de la replicación optimista. ^{[ 2 ]}

• Los historiales hash ^{[ 3 ]} evitan el uso de contadores al mantener un conjunto de hashes de cada versión actualizada y comparar esos conjuntos por inclusión de conjuntos. Sin embargo, este mecanismo solo puede brindar garantías probabilísticas.
• Los vectores de versión concisos ^{[ 4 ]} permiten un ahorro de espacio significativo al manejar múltiples elementos replicados, como en las estructuras de directorios en los sistemas de archivos.
• Los sellos de versión ^{[ 5 ]} permiten el seguimiento de un número variable de réplicas y no utilizan contadores. Este mecanismo puede presentar problemas de escalabilidad en algunos casos, pero puede sustituirse por relojes de árbol de intervalos .
• Los relojes de árbol de intervalo ^{[ 6 ]} generalizan los vectores de versión y los relojes vectoriales y permiten números dinámicos de réplicas/procesos.
• Los vectores de versión acotados ^{[ 7 ]} permiten una implementación acotada, con contadores de tamaño acotado, siempre que los pares de réplicas puedan sincronizarse atómicamente.
• Los vectores de versión punteados ^{[ 8 ]} abordan la escalabilidad con un pequeño conjunto de servidores que median el acceso de réplica por parte de un gran número de clientes concurrentes.

• Por qué los relojes lógicos son fáciles (Comparación de historias causales, relojes vectoriales y vectores de versión)