Versión vectorial

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

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, 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 en su copia del vector en el máximo del elemento en ambos contadores: . Después de la sincronización, las dos réplicas tienen vectores de versión idénticos. ${\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}$

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

Los vectores de versión ^[1] o variantes se utilizan para rastrear 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]

Otros mecanismos

• Los historiales de hashes ^[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 concisa ^[4] permiten un ahorro de espacio significativo al manejar múltiples elementos replicados, como en estructuras de directorio en sistemas de archivos.
• Los sellos de versión ^[5] permiten realizar el seguimiento de un número variable de réplicas y no recurren a contadores. Este mecanismo puede representar problemas de escalabilidad en algunas configuraciones, pero puede reemplazarse por relojes de árbol de intervalos.
• Los relojes de árbol de intervalos ^[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 limitada ^[7] permiten una implementación limitada, con contadores de tamaño limitado, siempre que los pares de réplicas puedan sincronizarse atómicamente.
• Los vectores de versión punteada ^[8] abordan la escalabilidad con un pequeño conjunto de servidores que median el acceso a la réplica por parte de una gran cantidad de clientes simultáneos.

Referencias

1. Douglas Parker, Gerald Popek, Gerard Rudisin, Allen Stoughton, Bruce Walker, Evelyn Walton, Johanna Chow, David Edwards, Stephen Kiser y Charles Kline. Detección de inconsistencia mutua en sistemas distribuidos. Transactions on Software Engineering. 1983
2. David Ratner, Peter Reiher y Gerald Popek. Mantenimiento de vectores de versiones dinámicas. Informe técnico CSD-970022, Departamento de Ciencias de la Computación, Universidad de California, Los Ángeles, 1997
3. ByungHoon Kang, Robert Wilensky y John Kubiatowicz. El enfoque de la historia de hash para conciliar la inconsistencia mutua. ICDCS, págs. 670-677, IEEE Computer Society, 2003.
4. Dahlia Malkhi y Doug Terry. Versión concisa de Vectores en WinFS. Computación distribuida, vol. 20, 2007.
5. Paulo Almeida, Carlos Baquero y Victor Fonte. Version Stamps: Decentralized Version Vectors. ICDCS, pp. 544-551, 2002.
6. Paulo Almeida, Carlos Baquero y Victor Fonte. Relojes de árbol de intervalos. OPODIS, Lecture Notes in Computer Science, vol. 5401, págs. 259-274, Springer, 2008.
7. José Almeida, Paulo Almeida y Carlos Baquero. Vectores de versión limitada. DISC: Simposio Internacional sobre Computación Distribuida, LNCS, 2004.
8. Nuno Preguiça, Carlos Baquero, Paulo Almeida, Victor Fonte y Ricardo Gonçalves. Breve anuncio: Seguimiento eficiente de la causalidad en sistemas de almacenamiento distribuido con vectores de versión punteada. ACM PODC, págs. 335-336, 2012.

Enlaces externos

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